Это 21-й день моего участия в августовском испытании обновлений.Подробности о событии:Испытание августовского обновления

Модель параллельных вычислений

Модель параллельных вычислений обычно относится к абстрагированию основных характеристик различных параллельных компьютеров (по крайней мере, определенного типа параллельных компьютеров) из разработки и анализа параллельных алгоритмов для формирования абстрактной модели вычислений.

В более широком смысле модель параллельных вычислений предоставляет аппаратный и программный интерфейс для параллельных вычислений.В соответствии с соглашением об интерфейсе разработчики аппаратного обеспечения и разработчиков программного обеспечения параллельной системы могут разработать механизм поддержки параллелизма, тем самым повышая производительность системы.

Общие модели параллельных вычислений: модель BSP, модель PRAM, модель LogP, модель C3, модель BDM.

Зачем нужна модель параллельных вычислений?

Spark и Hadoop — это итеративные модели, которые подходят только для общих вычислений.В областях машинного обучения и других областях, требующих больших вычислительных ресурсов, традиционные итерационные модели больше не применимы. Модель параллельных вычислений предназначена для решения вычислительной задачи в некоторых конкретных сценариях.

BSP-модель

(Bulk Synchronous Parallel, общая модель синхронных параллельных вычислений) — модель параллельных вычислений, предложенная британским ученым-компьютерщиком Вилиантом в 1980-х годах.

Статья, опубликованная Google (Pregel: A System for Large-scale Graph Processing), сделала эту концепцию более широко известной.

Как и Mapreduce, Google не открывает исходный код Pregel, а Apache предоставляет аналогичный фреймворк Hama, основанный на идеях Pregel.

Основные принципы модели BSP

Модель BSP представляет собой асинхронную модель MIMD-DM (DM-Distributed Memory, SM — Shared Memory), которая поддерживает систему передачи сообщений, внутриблочный асинхронный параллелизм и межблочную синхронизацию конфигурации.

Модель основана на мастер-координации, все воркеры выполняются синхронно (lock-step), а данные считываются из входной очереди.

Вычислительная модель BSP — это не только архитектурная модель, но и метод проектирования параллельных программ.

Критерием разработки программы BSP является Bulk Synchrony, а ее уникальность заключается во введении концепции Super Step.

Программа BSP имеет как горизонтальную, так и вертикальную структуру. С вертикальной точки зрения программа BSP состоит из серии последовательных супершагов (Super Step), как показано на рисунке, эта структура аналогична структуре последовательной программы.

По горизонтали в супершаге все процессы выполняют локальные вычисления параллельно. Супершаг можно разделить на три фазы, как показано на рисунке.

1. На этапе локальных вычислений каждый процессор выполняет локальные вычисления только с данными, хранящимися в локальной памяти.
2. Фаза глобальной связи, которая работает с любыми нелокальными данными.
3. Фаза синхронизации забора, ожидание завершения всех коммуникационных действий.

Модель параллельных вычислений BSP можно описать четырьмя параметрами: p, s, g и i.

1. p — количество процессоров (с памятью).
2. s - вычислительная скорость процессора.
3. g — количество локальных вычислительных операций в секунду / количество байтов, передаваемых в секунду по сети связи, которое называется пропускной способностью маршрутизатора и рассматривается как коэффициент пропускной способности.
4. i — это накладные расходы времени глобальной синхронизации, которые называются временным интервалом между глобальными синхронизациями (время барьерной синхронизации).

Предполагая, что имеется p процессоров для одновременной передачи h байтов информации, gh — это издержки связи. Затраты на синхронизацию и связь нормализуются для указанного количества процессоров.

Особенности модели BSP

1. Модель BSP делит вычисление на один супершаг (Super Step), что позволяет избежать взаимоблокировок.
2. Он разделяет процессор и маршрутизатор.Маршрутизатор выполняет только двухточечную передачу сообщений и не обеспечивает таких функций, как объединение, репликация и широковещательная рассылка.Это не только охватывает конкретную топологию сети взаимосвязи, но также упрощает протокол связи.
3. Барьерная синхронизация — это аппаратно реализованная глобальная синхронизация, которой можно управлять на грубом уровне, что обеспечивает эффективный способ выполнения тесно связанных синхронных параллельных алгоритмов без чрезмерной нагрузки на программиста.
4. При анализе производительности модели BSP предполагается, что локальные операции могут быть выполнены за один временной шаг, и на каждом супершаге процессор отправляет или получает не более h сообщений (называемых h-отношением).
5. Алгоритмы, разработанные для модели PRAM, могут быть реализованы путем моделирования некоторых процессоров PRAM на каждом процессоре BSP.

Оценка модели BSP

1. В параллельных вычислениях Viliant пытается построить мост между программным и аппаратным обеспечением наподобие машины фон Неймана, и модель BSP может играть такую ​​роль. Из-за этого модель BSP также известна как модель моста.
2. Вообще говоря, программируемость модели MIMD с распределенным хранилищем относительно плохая, но в модели BSP, если вычисления и обмен данными могут быть должным образом сбалансированы, она покажет большее преимущество в программируемости.
3. Некоторые важные алгоритмы (такие как умножение матриц, параллельная операция предварительного порядка, БПФ и сортировка и т. д.) напрямую реализованы в модели BSP, что позволяет избежать дополнительных накладных расходов на автоматическое управление памятью.
4. Модель BSP может быть эффективно реализована в сети гиперкуба и технологии межсоединений с оптическими кроссбарами, что показывает, что модель не зависит от конкретной реализации технологии, если маршрутизатор имеет определенную пропускную способность связи.
5. В модели BSP длина «супершага» должна быть достаточной для размещения любого h-отношения.
6. В модели BSP сообщение, отправленное в начале «супершага», может быть использовано только в следующем «супершаге», даже если время задержки в сети меньше длины «супершага».
7. Предположение о глобальной барьерной синхронизации в модели BSP поддерживается специальным оборудованием, которое может отсутствовать на многих параллельных машинах.

Реализация модели BSP

Существует множество реализаций вычислительной среды BSP, наиболее известной из которых является крупномасштабная среда графовых вычислений Google Pregel, которая впервые предложила применить модель BSP к графовым вычислениям.

Apache Giraph, предоставленный Yahoo!, фокусируется на вычислениях графов поколений (таких как PageRank, кратчайшее соединение и т. д.), и каждое задание представляет собой задание Hadoop без процесса Reducer.

Apache Hama также является проектом-инкубатором сообщества ASF.В отличие от Giraph, это реализация модели BSP на чистом языке Java, которая не только используется для вычислений графов, но и предназначена для обеспечения общей среды приложений для модели BSP.

Модель детской коляски

Модель PRAM (Parallel Random Access Machine, параллельная машина с произвольным доступом), также известная как модель SIMD с общей памятью, представляет собой абстрактную модель параллельных вычислений, которая непосредственно разработана на основе модели последовательной RAM. В этой модели предполагается, что существует общая память с бесконечной емкостью, а также конечные или бесконечные процессоры с одинаковыми функциями, и все они имеют простые арифметические операции и функции логического суждения.В любой момент каждый процессор может обрабатывать данные. обмениваются друг с другом через общие единицы хранения.

Преимущества модели PRAM

1. Модель PRAM особенно удобна для выражения, анализа и сравнения параллельных алгоритмов.Она проста в использовании, и многие низкоуровневые детали о параллельных компьютерах, такие как межпроцессорное взаимодействие, управление системой хранения и синхронизация процессов, неявны. в модели;
2. Алгоритмы могут быть легко спроектированы и модифицированы для работы на различных параллельных компьютерных системах; при необходимости в модель PRAM можно добавить некоторые аспекты, такие как синхронизация и обмен данными.

Недостатки модели PRAM

1. В модели используется глобальная разделяемая память, а объем локальной памяти невелик, что недостаточно для описания узкого места производительности мультипроцессоров с распределенной основной памятью, а предположение об общей единой памяти явно не подходит для MIMD-машин с распределенной памятью. структура.
2. Модель PRAM является синхронной, что означает, что все инструкции работают в режиме такта. Хотя пользователи не ощущают наличия синхронизации, наличие синхронизации действительно отнимает много времени и не может отражать асинхронность многих систем в реальности.
3. Модель PRAM предполагает, что каждый процессор может получить доступ к любой единице разделяемой памяти за единицу времени, поэтому она не требует задержки, неограниченной пропускной способности и не требует дополнительных ресурсов для межпроцессорного взаимодействия. Нереалистично предполагать, что каждый процессор может получить доступ к любой ячейке памяти в единицу времени, игнорируя практические разумные детали, такие как конкуренция за ресурсы и ограниченная пропускная способность.
4. В нем не описаны методы многопоточности и конвейерной предварительной выборки, которые сегодня являются наиболее распространенными методами, используемыми в параллельных архитектурах.

Модель LogP

Модель LogP, предложенная Culler (1993), представляет собой многопроцессорную модель распределенного хранилища и двухточечной связи. Там, где связь описывается набором параметров, выполняется неявная синхронизация.

Коммуникационная сеть модели LogP описывается четырьмя основными параметрами.

1. L (задержка): указывает верхний предел времени ожидания или отсрочки, необходимого процессору-источнику для связи с процессором-получателем для сообщения (одно или несколько слов), и представляет собой задержку сообщения в сети.
2. o(накладные расходы): указывает время (включая накладные расходы на ядро ​​операционной системы и накладные расходы на сетевое программное обеспечение) процессора, готовящегося к отправке или получению каждого сообщения, в течение которых процессор не может выполнять другие операции.
3. g(gap): Указывает минимальный интервал времени, когда процессор отправляет или получает сообщения дважды подряд, и его обратным значением является пропускная способность связи микропроцессора.
4. P (процессор): количество процессоров/модулей памяти

Особенности модели LogP

1. Захватите узкое место производительности между сетью и процессором. g отражает пропускную способность канала связи, и в единицу времени между процессорами может быть передано не более Lg сообщений.
2. Процессоры работают асинхронно и синхронизируются посредством обмена сообщениями между процессорами.
3. Есть определенные размышления о технологии многопоточности. Каждый физический процессор может имитировать несколько виртуальных процессоров (VP).Когда у VP есть запрос на доступ, расчет не будет прекращен, но количество VP ограничено пропускной способностью связи и накладными расходами на переключение контекста. VP ограничен пропускной способностью сети, и существует не более Lg VP.
4. Задержка сообщения не определена, но не превышает L. Задержка сообщения непредсказуема, но может достигать L без блокировки.
5. Модель LogP побуждает программистов использовать некоторые хорошие стратегии, такие как распределение заданий, дублирование вычислений и коммуникации, а также сбалансированные модели коммуникации.
6. Можно оценить фактическое время работы алгоритма.

Слабые стороны модели LogP

1. Режим связи в сети описан недостаточно глубоко, например, сообщение о повторной передаче может занимать полосу пропускания, кеш промежуточного маршрутизатора переполнен и т. д.
2. Модель LogP в основном подходит для разработки алгоритмов передачи сообщений.Для режима общего хранилища просто считается, что операция удаленного чтения эквивалентна двум передачам сообщений, без учета технологии предварительной выборки конвейера, несогласованности данных, вызванной кешем , а также влияние частоты попаданий в кэш на вычисление.
3. Накладные расходы контекста методов многопоточности не учитываются.
4. Модель LogP предполагает связь с маршрутизаторами сообщений «точка-точка», что увеличивает нагрузку на программиста, связанную с рассмотрением связанных операций связи на маршрутизаторах.

модель С3

Модель C3 предполагает, что процессор не может отправлять и получать сообщения одновременно, а его анализ производительности супершагов разделен на две части:

1. Вычислительная единица (CU), которая зависит от объема локальных вычислений;
2. Коммуникационный блок (COU) зависит от того, сколько данных процессор отправляет и получает, от задержки сообщений и количества перегрузок, вызванных связью.

Модель учитывает влияние двух видов маршрутизации (маршрутизация с промежуточным хранением и маршрутизация с использованием червей) и двух видов примитивов отправки и получения (блокирующих и неблокирующих) на COU.

Особенности модели C3

1. CI и Cp используются для измерения влияния перегрузки сети на производительность алгоритма.
2. Рассмотрено влияние различных маршрутов и различных примитивов отправки или получения на связь.
3. Временная сложность супершагов может быть оценена без необходимости указания пользователем подробностей планирования.
4. Подобно иерархической структуре модели H-PRAM, модель C3 дает программистам представление об алгоритме маршрутизации К-уровня, то есть система делится на подсистемы К-уровня, и операции подсистем на каждый уровень не зависит друг от друга Sub PRAM в PRAM разделен.

Слабые стороны модели C3

1. Предпосылка метрики C заключается в том, что два процессора в одной и той же коммуникационной паре должны быть соответственно расположены в разных подсетях двусторонней сети.
2. В модели предполагается, что пропускная способность сети равна пропускной способности процессора, что влияет на корректное описание масштабируемых систем.
3. В алгоритме K-класса порядок между процессорами может иметь несколько перестановок, но модель C3 не может различать сложность разных перестановок.

БДМ модель

В 1996 году JFJaJa и др. предложили блочную распределенную модель (BDM), которая представляет собой мост между моделью программирования общего хранилища и распределенной системой хранения, основанной на передаче сообщений.

Он в основном имеет 4 параметра.

1. P: Количество процессоров.
2. t: максимальное время задержки процессора от выдачи запроса на доступ до получения удаленных данных, включая время на подготовку запроса, время маршрутизации пакета запроса в сети, время получения процессором назначения запроса , и возврат M последовательных слов в пакете к исходному процессорному времени.
3. M: Последовательные M слов в локальной памяти.
4. Время, когда процессор отправляет данные в сеть или получает данные из сети.

Особенности модели BDM

1. Используя M для отражения характеристик пространственной локальности, он предоставляет метод оценки производительности алгоритмов общей основной памяти и измеряет связь между процессорами, вызванную удаленным доступом.
2. BDM утверждает трубопроводную технологию. Время, необходимое для K предварительных выборок определенного процессора, равно +KMo (в противном случае K(r+Mo). Программируемость хорошая.
3. Рассмотрение конкуренции за память в общей основной памяти.
4. Может использоваться для анализа сетевой маршрутизации.

Слабые стороны модели BDM

1. Считается, что исходные данные размещаются во внутренней памяти, а для программистов программ с общей оперативной памятью требуются дополнительные операции перемещения данных
2. Факторы, влияющие на задержку в сети, такие как расположение процессора, сильная перегрузка сети и т. д., не учитываются.
3. Накладные расходы системы не учитываются.