Характеристики

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

алгоритмов

Судаков А.А.

“Параллельные и распределенные вычисления” Лекция 13

План

Распараллеливание

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

Основные теоремы

Факторы снижения эффективности распареллеливания

Алгоритмы

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

Последовательный алгоритм – решение задачи на одном процессоре

Параллельный алгоритм – решение задачи на одновременно работающих процессорах

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

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

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

Декомпозиция данных

Декомпозиция функций

Комбинированная декомпозиция

Связь – взаимодействия между составными частями задачи

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

Эффективность

распараллеливания

Единственная цель распараллеливания

– уменьшение времени вычислений

Не все задачи одинаково эффективно распараллеливаются

Задачи теоретического анализа

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

Определить насколько та или иная схема эффективна

Модель

Система с p процессорами

Процессоры могут взаимодействовать между собой

В модели с общей памятью

каждый процессор может обращаться независимо к каждой ячейке памяти

При обращении к одной и той же ячейке на запись могут возникать конфликты

В модели с распределенной памятью

Каждые 2 процессора могут взаимодействовать между собой

CPU1 CPU2

память

CPU3 CPUp

CPU1 CPU2

коммутатор

CPU3 CPUp

Характеристики

алгоритмов

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

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

Количество операций последовательного алгоритма N1

Количество операций параллельного алгоритма Np

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

Характеристики

эффективности

распараллеливанияКоэффициент ускорения

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

p

Q kåkï kí

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

Время передачи единицы информации

Время начальной задержки

Латентность

Время установления связи

Отношение между временем обработки и временем передачи единицы информации

Отношение между временем обработки единицы информации и временем установления связи

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

алгоритма)Программы (алгоритмы) работают со входными данными

Чем больше данных, тем дольше они будут обрабатываться

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