Лекция: Виды параллелизма.
Декомпозиция по пространству (геометрический вид параллелизма).
Вся расчётная область разделяется на участки, каждый из которых закрепляется за своим процессом, границы между участками называются стыками. При обработке стыков вводят дополнительные точки, которые дублируют и по координате и по значению функции точки на соседнем процессе. Количество дополнительных точек определяется спецификой решаемой проблемы. Все процессы проводят вычисления на своих участках одновременно.
+ Можно обрабатывать большие расчётные области
+ Получаем ускорение за счёт одновременной работы всех процессов на своих участках.
− Наличие стыков, проблема с их обработкой
− Бывает необходимо передавать значения на стыках, что приводит к потере времени
Этот вид декомпозиции применяется при решении задач линейной алгебры, численного интегрирования, математической физики
Декомпозиция по задачам (функциональный вид параллелизма)
Решаемая задача разбивается на независимые подзадачи, каждая из которых закрепляется за своим процессом. Все процессы работают одновременно. Отдельные подзадачи неравноценны по затратам машинного времени, что приводит к простою некоторых процессов. При решении некоторых задач бывает необходимо выделить один процесс, который не занимается вычислениями, а только координирует работу других процессов.
+ Все процессы выполняют свои подзадачи одновременно, что даёт ускорение
− Подзадачи неравноценны по затратам машинного времени, что приведёт к простою некоторых процессов
− Выделение отдельного процесса для координации работы остальных процессов.
Применяется при решении систем ОДУ, систем нелинейных уравнений, в задачах оптимизации.
Конвейерный вид параллелизма.
Вся расчётная область разбивается на приблизительно одинаковые участки, каждый из которых закрепляется за своим процессом. Работу начинает нулевой процесс. Дойдя до стыка, он передаёт значения первому процессу и переходит к следующей итерации. Первый процесс начинает вычисления и, дойдя до стыка, передаёт значения второму и т.д. Все процессы последовательно включаются в работу и каждый работает на своей итерации. Как только все процессы включены в работу, все они работают одновременно, что даёт ускорение.
+ Можно обсчитывать большие расчётные области
+ Есть стыки, но нет проблем с их обработкой
+ Ускорение при одновременной работе всех процессов
− Простои в начале и конце вычислений
− Передача значений на стыках
Применяется при решении уравнений математической физики
Типы принятия коллективного решения (укладка паркета)
Вся расчетная область разделяется на приблизительно одинаковые участки по числу процессов, каждый процесс проводит вычисления на своем участке, и находит оптимальное решение – локальный оптимум. Затем некоторый процесс, например нулевой, находит глобальный оптимум среди локальных.
+ Все процессы независимы
+ Ускорение кратно числу процессов
+ В некоторых задачах не нужны передачи, значит не будет потерь времени
− Узкая область применения
− В некоторых задачах необходимы передачи найденных локальных оптимумов
Метод сдваивания (каскадный вид параллелизма)
Пусть дан большой массив чисел, необходимо найти сумму этих чисел. Разбиваем массив чисел на пары и суммируем каждую пару, далее все полученные суммы также разбиваем на пары и суммируем…
Тогда количество итераций равно log2N. Количество процессов необходимое для реализации равно N/2. При увеличении количества суммируемых значений эффективность уменьшается.