Характеристики параллельных алгоритмов

План

Распараллеливание
Характеристики алгоритмов
Основные теоремы
Факторы снижения эффективности распареллеливания

Алгоритмы

Алгоритм – набор действий, которые необходимо выполнить для решения задачи
Последовательный алгоритм

Декомпозиция, Связь, Синхронизация

Декомпозиция – разбиение задачи на составные части
Декомпозиция данных
Декомпозиция функций
Комбинированная

Эффективность распараллеливания

Единственная цель распараллеливания – уменьшение времени вычислений
Не все задачи одинаково

Модель

Система с p процессорами
Процессоры могут взаимодействовать между собой
В модели с общей

Характеристики алгоритмов

Время вычисления на одном процессоре
Время вычисления на p процессорах

Характеристики эффективности распараллеливания

Коэффициент ускорения
Во сколько раз время параллельный алгоритм быстрее
Идеальное ускорение

Характеристики системы обмена информацией

Время передачи единицы информации
Время начальной задержки
Латентность
Время установления

Масштабируемость (количество операций алгоритма)‏

Программы (алгоритмы) работают со входными данными
Чем больше данных,

Характеристики масштабируемости

Характерная размерность задачи
Количество входных данных
Количество операций алгоритма
Нотация большого O
Как ведет

Примеры характерных размерностей

Количество элементов массива n
Размер квадратной матрицы nxn

Примеры масштабируемости

Другие характеристики

Производительность системы
Цена алгоритма
Суммарные затраты процессорного времени

Основные свойства параллельных алгоритмов

На сколько вообще можно ускорить вычисления за счет

Граф операций

Граф операции-аргументы
Вершины графа – выполняемые операции
Дуги – какие результаты предыдущих

Постановка задачи в терминах графа

Последовательности операций соответствует путь на графе
Параллельно

Пример расписания (общая память)‏

Момент времени 1
H=(операция 1:загрузить а, процессор 1, момент1

Ограничения на расписание

В один и тот же момент времени один процессор

Определение времени выполнения параллельного алгоритма

Время выполнения соответствует максимально длинному пути графа
Соответствует

Некоторые свойства параллельных алгоритмов

Минимальное время выполнения параллельного алгоритма соответствует максимальной длине

Доказательство 2

Пусть есть расписание для получения минимально возможного времени
пусть оно соответствует

Доказательство 2 (продолжение)‏

Рассмотрим, что будет если при выполнении того же расписания

Доказательство 2 (продолжение)‏

Время выполнения алгоритма на p процессорах на i-м шаге
Оценим

Другие свойства

Можно показать, что максимально возможное ускорение при неизменном количестве операций

Использование описания с помощью графов

Вычислительную схему необходимо выбирать с графом минимального

Факторы ограничения и повышения производительности

Гипотеза Минского – принципиальная непараллельность алгоритма
Закон

Гипотеза Минского

Пусть программа имеет p последовательных участков
Пусть переход на тот или

Закон Амдала (Amdahl, 1967)‏

Наличие последовательных участков приводит к существенному снижению производительности
Пусть

Иллюстрация закона Амдаля

Оценка времени выполнения

Время выполнения последовательного алгоритма
Время выполнения последовательной части параллельного алгоритма
Время

Коэффициент ускорения и эффективность

Ускорение
Эффективность
Время выполнения на паракомпьютере
Оптимальное количество процессоров

Графики зависимостей

Примеры закона Амдала

Централизованная схема вычислений
Симметричная мультипроцессорная система
И другие суперкомпьютеры
Векторные, конвейерные процессоры
Обмен

Централизованная схема

Главный процессор раздает рабочим задачу
Рабочие выполняют задачу и возвращают результат

SMP система

Шина не может передавать данные от нескольких процессоров одновременно
Шина –

Конвейер

Пока конвейер не заполнен параллельной обработки нет
Заполнение конвейера – существенно последовательная

Закон Густафсона

Другая формулировка закона Амдала
Пусть параллельный алгоритм выполняется за время

Оценка времени для закона Густафсона

Время параллельной обработки
Время последовательной обработки (параллельная часть

Связь или противоречие?

Используются разные параметры
Амдал – доля последовательных операций последовательного

Практическое применение законов Амдала и Густафсона

При очень малом количестве последовательных

Гетерогенность

Гомогенная система – все процессоры одинаковы
Гетерогенная система – процессоры разные
Большинство

Дисбаланс нагрузки

Если алгоритм, рассчитанный на гомогенную систему запустить на гетерогенной, то

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

Для решения проблемы используют балансировку нагрузки
Статическая – на этапе запуска

Сверхлинейное ускорение

Сверхлинейное ускорение – ускорение большее, чем количество процессоров
Согласно рассмотренной теории

Аппаратное сверхлинейное ускорение

Возможно, если процессоры параллельной программы выполняют параллельный код с

Алгоритмическое сверхлинейное ускорение

Возможно, когда для выполнения параллельного алгоритма
Необходимо выполнить меньше операций
Не

Пример: подбор пароля

Пусть последовательный алгоритм поиска имеет p стадий
Стадия1: Перебор географических

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

Каждый процессор выполняет свою стадию
Процессор1 : Стадия1
Процессор2: Стадия 2
…

Иллюстрация

последовательный

параллельный

Счастливый случай

Как правило пользователи выбирают пароли, чтобы лучше запоминались
Если на какой-либо

Оценка времени последовательного алгоритма

Пусть последовательный алгоритм найдет результат в k-й стадии

Оценка времени параллельного алгоритма

Процессор параллельной системы, который выполняет k-ю стадию сразу

Ускорение

Коэффициент ускорения
Сверхлиненейное ускорение возможно, когда ускорение больше p
Условие
Если успешный подбор будет

Сравнение факторов ограничения производительности

Выводы

В большинстве случаев ускорение за счет распараллеливания не может быть больше