Параллельный алгоритм

В информатике , параллельный алгоритм в отличие от традиционного последовательного алгоритма , представляет собой алгоритм , который может выполнять несколько операций за заданное время. было традицией В информатике описывать последовательные алгоритмы в абстрактных моделях машин , часто известных как машины с произвольным доступом . Точно так же многие исследователи информатики использовали так называемую параллельную машину с произвольным доступом (PRAM) в качестве параллельной абстрактной машины (с общей памятью). ^[1]^[2]

Многие параллельные алгоритмы выполняются одновременно – хотя, как правило, параллельные алгоритмы представляют собой отдельную концепцию – и поэтому эти концепции часто объединяются, причем какой аспект алгоритма является параллельным, а какой параллельным, четко не различается. Кроме того, непараллельные и непараллельные алгоритмы часто называют « последовательными алгоритмами », в отличие от параллельных алгоритмов.

Возможность распараллеливания

Алгоритмы значительно различаются по степени распараллеливаемости: от легко распараллеливаемых до полностью нераспараллеливаемых. Кроме того, данная задача может включать в себя различные алгоритмы, которые могут быть более или менее распараллеливаемыми.

Некоторые проблемы легко разделить таким образом на части — их называют досадно параллельными задачами. Примеры включают множество алгоритмов для решения кубиков Рубика и поиска значений, которые приводят к заданному хешу . ^{[ нужна ссылка ]}

Некоторые проблемы невозможно разделить на параллельные части, поскольку для эффективного перехода к следующему шагу требуются результаты предыдущего шага. по своей сути серийная проблема . Примеры включают итерационные численные методы , такие как метод Ньютона , итеративные решения задачи трех тел и большинство доступных алгоритмов для вычисления числа Пи (π). ^{[ нужна ссылка ]} Некоторые последовательные алгоритмы можно преобразовать в параллельные с помощью автоматического распараллеливания . ^[3]

Во многих случаях разработка эффективного параллельного алгоритма решения какой-либо задачи требует привлечения новых идей и методов по сравнению с созданием последовательной версии алгоритма. Это, например, практически важные задачи поиска целевого элемента в структурах данных, вычисления алгебраического выражения и т. д. ^[4]

Мотивация

Параллельные алгоритмы на отдельных устройствах стали более распространенными с начала 2000-х годов из-за существенных улучшений в многопроцессорных системах и появления многоядерных процессоров. Вплоть до конца 2004 года производительность одноядерных процессоров быстро увеличивалась за счет масштабирования частоты , поэтому было проще построить компьютер с одним быстрым ядром, чем компьютер со многими более медленными ядрами с одинаковой пропускной способностью , поэтому многоядерные системы имели более ограниченные возможности. использовать. Однако с 2004 года масштабирование частоты зашло в тупик, и, таким образом, многоядерные системы стали более распространенными, что сделало параллельные алгоритмы более общими.

Проблемы

Коммуникация

Стоимость или сложность последовательных алгоритмов оценивается с точки зрения занимаемого ими пространства (памяти) и времени (циклов процессора). Параллельным алгоритмам необходимо оптимизировать еще один ресурс — связь между разными процессорами. Существует два способа взаимодействия параллельных процессоров: общая память или передача сообщений.

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

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

Если накладные расходы на связь дополнительных процессоров перевешивают выгоду от добавления еще одного процессора, происходит параллельное замедление .

Балансировка нагрузки

Другая проблема, связанная с параллельными алгоритмами, заключается в обеспечении достаточной балансировки нагрузки , гарантируя, что нагрузка (общая работа) сбалансирована, а не сбалансирован размер входных данных. Например, проверку всех чисел от единицы до ста тысяч на простоту легко разделить между процессорами; однако, если числа просто разделить поровну (1–1000, 1001–2000 и т. д.), объем работы будет несбалансированным, поскольку меньшие числа легче обрабатывать этим алгоритмом (проще проверить на простоту), и таким образом, некоторым процессорам будет выполняться больше работы, чем другим, которые будут простаивать до тех пор, пока загруженные процессоры не завершат работу.

Распределенные алгоритмы

Подтип параллельных алгоритмов, распределенные алгоритмы , представляют собой алгоритмы, предназначенные для работы в кластерных вычислениях и средах распределенных вычислений , где необходимо решать дополнительные проблемы, выходящие за рамки «классических» параллельных алгоритмов.

См. также

Ссылки

^ Блеллок, Гай Э.; Мэггс, Брюс М. «Параллельные алгоритмы» (PDF) . США: Школа компьютерных наук Университета Карнеги-Меллона . Проверено 27 июля 2015 г.
^ Вишкин, Узи (2009). «Параллельное мышление: некоторые основные алгоритмы и методы параллельного анализа данных, 104 страницы» (PDF) . Конспекты курсов по параллельным алгоритмам, преподаваемых с 1992 года в Университете Мэриленда, Колледж-Парке, Тель-Авивском университете и Технионе.
^ Мегсон ГМ; Чэнь Сянь (4 января 1997 г.). Автоматическое распараллеливание для класса регулярных вычислений . Всемирная научная. ISBN 978-981-4498-41-8 .
^ Кургалин Сергей; Борзунов, Сергей (2020). Рабочая тетрадь по дискретной математике: сопутствующее руководство по использованию Python . Тексты по информатике (2-е изд.). Чам, Швейцария: Springer Naturel. ISBN 978-3-030-42220-2 .

Внешние ссылки

Проектирование и реализация параллельных программ , Аргоннская национальная лаборатория США

[1] Блеллок, Гай Э.; Мэггс, Брюс М. «Параллельные алгоритмы» (PDF) . США: Школа компьютерных наук Университета Карнеги-Меллона . Проверено 27 июля 2015 г.

[2] Вишкин, Узи (2009). «Параллельное мышление: некоторые основные алгоритмы и методы параллельного анализа данных, 104 страницы» (PDF) . Конспекты курсов по параллельным алгоритмам, преподаваемых с 1992 года в Университете Мэриленда, Колледж-Парке, Тель-Авивском университете и Технионе.

[MXian1997-3] Мегсон ГМ; Чэнь Сянь (4 января 1997 г.). Автоматическое распараллеливание для класса регулярных вычислений . Всемирная научная. ISBN 978-981-4498-41-8 .

[4] Кургалин Сергей; Борзунов, Сергей (2020). Рабочая тетрадь по дискретной математике: сопутствующее руководство по использованию Python . Тексты по информатике (2-е изд.). Чам, Швейцария: Springer Naturel. ISBN 978-3-030-42220-2 .

[1]

[2]

[3]

[4]

v т и Параллельные вычисления
Общий	Распределенные вычисления Параллельные вычисления Массивная параллель Облачные вычисления Высокопроизводительные вычисления Многопроцессорность Многоядерный процессор ГПГПУ Компьютерная сеть Систолический массив
Уровни	Кусочек Инструкция Нить Задача Данные Память Петля Трубопровод
Многопоточность	Временной Одновременный (SMT) Одновременное и гетерогенное Спекулятивный (СпМТ) упреждающий Кооператив Кластерная многопоточная обработка (CMT) Аппаратный разведчик
Теория	Модель ПРАМ Модель PEM Анализ параллельных алгоритмов Закон Амдала Закон Густавсона Экономическая эффективность Метрика Карпа – Флатта Замедлять Ускорение
Элементы	Процесс Нить Волокно Окно инструкций Множество
Координация	Многопроцессорность Согласованность памяти Согласованность кэша Аннулирование кэша Барьер Синхронизация Контрольная точка приложения
Программирование	Потоковая обработка Программирование потоков данных Модели Неявный параллелизм Явный параллелизм Параллелизм Неблокирующий алгоритм
Аппаратное обеспечение	Таксономия Флинна СИСД SIMD Обработка массивов (SIMT) Конвейерная обработка Ассоциативная обработка МИСД МИМД Архитектура потока данных Конвейерный процессор Суперскалярный процессор Векторный процессор Мультипроцессор симметричный асимметричный Память общий распределенный распределенный общий ОДИН НУМА ЕСТЬ Массивно-параллельный компьютер Компьютерный кластер Кластер Беовульф Сетевой компьютер Аппаратное ускорение
API	Атчи ПХ Способствовать росту Часовня HPX Очарование++ Силк Коаррей Фортран ДРУГОЙ Дриада С++ AMP Глобальные массивы GPUОткрыть ИМБ OpenMP OpenCL OpenHMPP OpenACC Параллельные расширения НДС pthreads РафтЛиб РПЦм СКП TBB ЗПЛ
Проблемы	Автоматическое распараллеливание Тупик Детерминированный алгоритм Смущающе параллельно Параллельное замедление Состояние гонки Программная блокировка Масштабируемость Голод
Категория: Параллельные вычисления