- •Многопроцессорные системы – общая характеристика, актуальность. Области применения. История развития. Виды параллелизма – расслоение памяти, векторно-конвейерная обработка, множественные фу.
- •2 Класса архитектур. Общая память – достоинства, недостатки.
- •Классификация Флинна. Примеры.
- •2 Варианта локальной памяти:
- •5. Иерархия памяти в современных компьютерах. Кэш. Терминология. 3 типа кэш-памяти. Стратегии поиска и замещения блоков. Сквозная и обратная запись. Достоинства и недостатки.
- •6. Проблема когерентности кэшей. Кэш с наблюдением (snooping) . Алгоритм mesi.
- •7. Уровни состоятельности. Строгая состоятельность – проблема поиска и проблема синхронизации записи. Владельцы и менеджеры данных. Write-broadcast и write-invalidate схемы записи.
- •Модели с ослаблением состоятельности.
- •Схемы, основанные на каталогах.
- •Виды коммуникационных сред. Составные части. Коммутаторы – простые и составные, с временным и пространственным разделением.
- •Классификация сетей. Терминология. Представление в виде графов. Топологии – решетка, тор, гиперкуб, челнок, дерево и др.
- •Массово-параллельные компьютеры – определение, основные понятия, история. Mpp. Asci Red и Cray t3e.
- •Измерение производительности. Терминология. Время отклика, время цп, таковая частота. Виды тестов. Фирменные тесты. Mips и mflops.
- •Тесты linpack. Ливерморские циклы. Spec. Тесты tpc.
- •Проектирование параллельных алгоритмов. 4 этапа. Характеристика этапов.
- •Декомпозиция – основная задача. 2 метода. Контрольные вопросы.
- •Определение коммуникаций. Варианты. Связь с 1 этапом.
- •Локальные и глобальные коммуникации. Контрольные вопросы.
- •Укрупнение. Цели. Методы. Контрольные вопросы.
- •Время простоя. Пример общей модели.
- •Эффективность и ускорение. Анализ масштабируемости – при фиксированном размере задачи, при переменном размере задачи.
- •Экспериментальные исследования – задачи, характеристика. Сравнение теоретических и экспериментальных данных. Возможные причины отклонений.
- •Модульность в параллельных программах. Виды композиции. Проблема перераспределения данных. Последовательная композиция – spmd. ScaLapack.
- •Параллельная композиция. Конкурентная композиция. Примеры. Правила применения.
- •Анализ производительности программы в целом. Усложняющие факторы. Пример.
- •Средства разработки параллельных программ. Классификация. Pvm – характеристика и идеология. Основные функции.
- •Нити. Синхронизация. Асинхронные коммуникации. Проблема детерминизма. Распределение по процессорам. – 2 фазы. Производительность.
- •Fortran 90 и hpf. Параллельные расширения f90. Основные понятия и директивы hpf. Примеры.
- •OpenMp – идея, технология, основные понятия. Основные директивы. Пример программы.
- •Linda – основные понятия. Функции. Пример – реализация барьерной синхронизации.
Определение коммуникаций. Варианты. Связь с 1 этапом.
Как правило, коммуникации между задачами описываются в терминах каналов, по которым задача может передавать и принимать информацию. Тогда определение коммуникаций включает 2 фазы. Вначале определяется структура каналов, которые связывают (непосредственно или опосредованно) задачи-потребители информации с задачами-поставщиками информации. Затем мы определяем сообщения, которые могут посылаться от одной задачи другой по этим каналам. В зависимости от реализации сами каналы могут и не создаваться. Например, в модели параллелизма данных каналы в явном виде не используются. Тем не менее, явное описание коммуникаций помогает количественной оценке эффективности алгоритма с учетом понятий локальности и затрат на коммуникации.
Определение структуры каналов требует затрат (интеллекта, труда), а передача по ним сообщений сопряжено с временными затратами. Поэтому следует избегать определения избыточных каналов и сообщений. Кроме того, мы стараемся увеличить производительность, распределяя коммуникации между задачами и предусматривая одновременное выполнение вычислений и обмена информацией.
Для подзадач, определенных при доменной декомпозиции, часто трудно определить коммуникации. При том, что основная часть таких подзадач, как правило, независимы, во многих случаях зависимости имеются. При этом их бывает нелегко выявить и правильно описать.
Наоборот, при функциональной декомпозиции структура коммуникаций обычно хорошо определена. Например, при декомпозиции модели климата связи между подзадачами соответствуют интерфейсам субмоделей – модель атмосферы вырабатывает данные, используемые моделью океана и т.д.
Структуры коммуникаций могут быть очень сложными. При описании этих структур используются следующие понятия:
локальные / глобальные коммуникации: при локальных коммуникациях задача обменивается данными с необходимым количеством других задач (соседей); при глобальных – с множеством других задач.
структурированные / неструктурированные – при структурированных коммуникациях задачи и их соседи образуют регулярную структуру; при неструктурированных это может быть произвольный граф.
при статических коммуникациях индивидуальности партнеров не меняются; при динамических – могут изменяться при синхронных коммуникациях поставщики и потребители обмениваются информацией согласованно, при асинхронной этого не требуется.
Локальные и глобальные коммуникации. Контрольные вопросы.
Локальные коммуникации.
В качестве примера задачи с локальными коммуникациями рассмотрим метод конечных разностей Якоби. В этом методе значения в узлах многомерной решетки периодически обновляется с учетом значений в некотором определенном количестве соседних узлов. Набор значений, необходимый для определения одного конкретного значения, называется stencil. Так, для двухмерной решетки с обновлением по 5 точкам используется такое выражение:
Структура задач и каналов.
При последовательном расчете лучшие результаты дает схема Гаусса-Зейделя. В этой схеме элементы вычисляются в определенном порядке, который обеспечивает использование последних значений других элементов.
Однако, в случае параллельного выполнения эта схема не столь удобна. Если в схеме Якоби все вычисления могут выполняться параллельно, то здесь одновременно могут выполняться только N/2 точек из N2. Поэтому при параллельных вычислениях используют некоторые модификации схемы Гаусса-Зейделя, например, шахматную схему.
Глобальные коммуникации.
Это операции, в которых участвуют множество задач. В этом случае недостаточно определить пары поставщик – потребитель. Это может привести к избыточному количеству обменов либо сильно ограничить возможности параллельного выполнения.
Этот пример иллюстрирует две принципиальные проблемы, возникающие при разработке алгоритма, исходя из «чисто локального» подхода к коммуникациям:
алгоритм централизован – вычисления и данные не распределены. Одна из задач участвует во всех операциях.
алгоритм «существенно последовательный» - не удается достичь одновременности выполнения.