Параллельные вычисления; закон Амдала.
Определение
Параллельные вычисления — способ организации компьютерных вычислений, при котором программы разрабатываются как набор взаимодействующих вычислительных процессов, работающих параллельно (одновременно).
Способы синхронизации параллельного взаимодействия:
Взаимодействие через разделяемую память: на каждом процессоре мультипроцессорной системы запускается поток исполнения, который принадлежит одному процессу. Потоки обмениваются данными через общий для данного процесса участок памяти.
Рисунок 1. Синхронизация через разделяемую память
Особенности синхронизации через разделяемую память:
N потоков = N процессоров;
Создание потоков:
Средствами языка;
С помощью библиотек явно или декларативно;
Автоматически средствами компиллятора;
Использование:
Мьютексов;
Семафоров и пр.
Взаимодействие c помощью передачи сообщений: на каждом процессоре многопроцессорной системы запускается однопоточный процесс, который обменивается данными с другими процессами, работающими на других процессорах, с помощью сообщений.
Рисунок 2. Синхронизация через передачу сообщений
Особенности синхронизации через передачу сообщений:
Процессы создаются явно с помощью функции ОС;
Обмен сообщениями (асинхронный или с блокировкой отправителя до момента доставки сообщения):
Через библиотеку;
С помощью средств языка;
Гибридный способ: на многопроцессорных системах с распределённой памятью (DM-MIMD), где каждый узел системы представляет собой мультипроцессор с общей памятью (SM-MIMD), можно использовать гибридный метод программирования. На каждом узле системы запускается многопоточный процесс, который распределяет потоки между процессорами данного узла. Обмен данными между потоками на узле осуществляется через общую память, а обмен данными между узлами — через передачу сообщений. В этом случае количество процессов определяется количеством узлов, а количество потоков — количеством процессоров на каждом узле. Гибридный способ программирования более сложен (требуется особым образом переписывать параллельную программу), но наиболее эффективен в использовании аппаратных ресурсов каждого узла многопроцессорной системы.
Разумеется, в такой системе можно также использовать и исключительно метод передачи сообщений, то есть запустить на каждом процессоре каждого узла отдельный процесс. В этом случае количество процессов (и потоков) будет равно количеству процессоров на всех узлах. Этот способ проще (в параллельной программе надо только увеличить количество процессов), но является менее эффективным, так как процессоры одного и того же узла будут обмениваться друг с другом сообщениями, словно они находятся на разных машинах
Закон Амдала
Закон Амдала был сформулирован Джином Амдалом в 1967 году, он иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей. «В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения самого медленного фрагмента». Согласно этому закону, ускорение выполнения программы за счёт распараллеливания её инструкций на множестве вычислителей ограничено временем, необходимым для выполнения её последовательных инструкций.
Математическое выражение закона Амдала
Пусть
необходимо решить некоторую вычислительную
задачу. Предположим, что её алгоритм
таков, что доля
от общего объёма вычислений может быть
получена только последовательными
расчётами, а, соответственно, доля
может быть распараллелена идеально
(то есть время вычисления будет обратно
пропорционально числу задействованных
узлов
.
Тогда ускорение, которое может быть
получено на вычислительной системе из
процессоров, по сравнению с однопроцессорным
решением не будет превышать величины
Закон Амдала предлагает нам некий метод оценки потенциального ускорения времени исполнения некоторой задачи, которое мы можем ожидать от системы при улучшении её ресурсов.