Лекции №1-2
Что такое гетерогенная параллелизация?
Гетерогенная параллелизация — это подход в параллельных вычислениях, при котором задачи распределяются между различными типами вычислительных устройств архитектурами (например, с разными центральные процессоры (CPU), графические процессоры (GPU).
Как называется основная память GPU, доступная всем потокам?
Глобальная память (global memory).
Какая структура данных применяется для представления иерархических и сложных связей между объектами?
Деревья и графы
Один студент делает весь проект сам, а другой делит работу между всей командой.
Какой принцип параллельных алгоритмов здесь используется?
Декомпозиция задачи
Что означает принцип FIFO и какая структура данных его реализует?
FIFO (First In, First Out) - первый добавленный элемент извлекается первым. Этот принцип реализует очередь.
Для чего используется кэш-память CPU?
Для ускорения доступа к часто используемым данным и инструкциям.
Как называются основные вычислительные блоки GPU, выполняющие потоки?
Поточные мультипроцессоры (Streaming Multiprocessors, SM).
Какая структура данных лучше всего подходит для хранения пар «ключ – значение»?
Хэш-таблица
У вас много исполнителей, но все постоянно тянутся к одному и тому же ресурсу, мешая друг другу.
Какой элемент параллельного алгоритма здесь спроектирован неправильно?
Распределение данных
В чём основное различие между стеком и очередью с точки зрения порядка обработки элементов?
Очередь использует принцип FIFO, а стек - принцип LIFO (Last In, First Out), где последний добавленный элемент извлекается первым.
Назовите одну область применения гетерогенной параллелизации.
Машинное обучение / научные вычисления / компьютерная графика.
Что означает параллелизм на уровне данных (Data Parallelism), характерный для GPU?
Одна и та же операция выполняется одновременно над большим количеством данных.
Какая структура данных состоит из узлов, соединенных указателями, и не хранит элементы подряд в памяти?
Список
Несколько потоков одновременно изменяют одну переменную, и результат каждый раз разный.
Какую проблему вы наблюдаете и какой принцип был нарушен?
Состояние гонки; отсутствие или неправильная синхронизация
Приведите пример задачи или алгоритма, где стек предпочтительнее очереди, и объясните почему.
Стек используется, например, в обходе графа в глубину (DFS), так как позволяет сначала обрабатывать последние добавленные узлы, реализуя глубинную стратегию.
Для чего используется директива #pragma omp parallel в OpenMP?
Для запуска параллельной области кода, выполняемой несколькими потоками одновременно.
Что такое конфликт банков разделяемой памяти?
Одновременный доступ потоков к одной ячейке памяти.
Какая структура данных одновременно обладает быстрым доступом по индексу и фиксированным размером?
Массив
Все исполнители делают одно и то же действие, но каждый — над своим объектом.
Какой это тип параллелизма и где он особенно эффективен?
Данные-параллелизм; особенно эффективен на GPU
Почему стандартные реализации std::queue и std::stack не являются безопасными для использования в параллельных программах?
Потому что при одновременном доступе нескольких потоков возможны гонки данных. Эти структуры не содержат встроенных механизмов синхронизации, поэтому требуется использование мьютексов или критических секций.
Объясните, почему GPU лучше подходит для массово-параллельных задач, а CPU - для управляющих и логических операций.
GPU имеет тысячи простых ядер и эффективен для однотипных параллельных вычислений, а CPU оптимизирован для последовательных, сложных логических задач и управления системой.
Почему чрезмерное использование регистров снижает производительность?
Происходит пролив данных в локальную память.
Назовите три класса параллельных структур данных и приведите пример каждой.
Линейные структуры: массивы, списки, очереди, стеки. Динамические структуры: деревья, графы, хэш-таблицы. Гибридные структуры: комбинации линейных и динамических структур.
Алгоритм формально параллельный, но работает медленно из-за постоянного обмена данными между исполнителями.
Какой принцип нарушен и почему это критично для гетерогенных систем?
Неправильная организация коммуникации; передача данных между устройствами (CPU–GPU) имеет высокую стоимость и снижает производительность.
Почему в параллельных алгоритмах очередь задач чаще используется, чем стек задач, и в каких случаях стек всё же предпочтительнее?
Очередь обеспечивает более равномерное распределение задач между потоками и снижает вероятность простаивания. Стек используется в задачах, где важна глубинная стратегия обработки, например, в поиске в глубину или рекурсивных алгоритмах.