Интернет Университет Суперкомпьютерных технологий

… если для нас представляют интерес реально работающие системы, то требуется убедиться, (и убедить всех сомневающихся) в корректности наших построений
… системе часто придется работать в невоспроизводимых обстоятельствах, и мы едва ли можем ожидать сколько-нибудь серьезной помощи от тестов
Dijkstra E.W.
1966
Предварительные замечания
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Методы построения параллельных алгоритмов и их свойства:
Статическая балансировка
метод сдваивания
геометрический параллелизм
конвейерный параллелизм
Динамическая балансировка
коллективное решение
диффузная балансировка загрузки
Содержание лекции
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Метод сдваивания
Москва, 2010 г.
Каскадная схема
Модифицированная каскадная схема
В.П.Гергель Основы параллельных вычислений, лекция 4, слайд 23
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Стена Фокса
Москва, 2010 г.
n – ширина стены
к – высота стены
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Метод геометрического параллелизма
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Метод коллективного решения (укладка паркета)
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Метод коллективного решения (укладка паркета)
Москва, 2010 г.
Число порций
Обработка порции
Обмен данными
r – размер порции
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Метод конвейерного параллелизма
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Москва, 2010 г.
?
Метод конвейерного параллелизма
Время выполнения на p процессорах
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Метод конвейерного параллелизма
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Метод конвейерного параллелизма
for(t=0;t
{
fnew[0]=g(t);
for(i=1;i
fnew[i]= f[i-1]+f[i]
for(i=0;i
f[i]= fnew [i]
}
0 1 2 3 4 5 6 7
f[i]
fnew[i]

Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3

Метод конвейерного параллелизма
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Объём хранимых данных
процессор 0 процессор 1 процессор 2 процессор 3

Причины дисбаланса вычислительной нагрузки
Разные процессоры
Внешнее воздействие
Разная вычислительная сложность заданий
Результат дисбаланса
Эффективная производительность определяется самым медленным процессором
Диффузная балансировка
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Медленный процессор
Москва, 2010 г.
Какой объем работ забрать у среднего процессора и кому его передать?
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Метод геометрического параллелизма
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Метод геометрического параллелизма
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Диффузная балансировка загрузки
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Диффузная балансировка загрузки
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Диффузная балансировка загрузки
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Статическое распределение
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Москва, 2010 г.
Постановка задачи диффузной балансировки
Дано:
Количество точек – N
Количество процессоров – p
Процессор i обработал ni точек за время ti
Требуется:
Найти количества точек n’i , которое следует обработать процессорам на следующем шаге
Определить сколько точек каждый из процессоров должен передать соседним процессорам
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Диффузная балансировка

Статическая и динамическая балансировка загрузки процессоров
Статическая балансировка
метод сдваивания
геометрический параллелизм
конвейерный параллелизм
Динамическая балансировка
коллективное решение
диффузная балансировка
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Резюме

Общая схема вычислений
Москва, 2010 г.
K = 1 000 000;
шаг_вывода = 10 000;
for(шаг=0;шаг
{
for(кирпич=rank*n/p;кирпич<(rank+1)*n/p;кирпич++)
Уложить (кирпич)
Обменяться данными о точках, прилегающих к внутренним границам()
if( шаг % шаг_вывода == 0 )
{
Вывести промежуточные результаты()
}
}
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

r=0;
for(i=0;i<=n;i++)
{
d=a[i]+b[i]+r;
c[i]=d%10;
r=d/10;
}
c[i]=r;
Определение суммы двух многоразрядных чисел
Москва, 2010 г.
T1= 4nτс
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Последовательное распространение разряда переноса на четырёх процессорах
«Параллельный» алгоритм
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Москва, 2010 г.
?
Параллельный алгоритм
« »
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Спекулятивное вычисление двух сумм
Спекулятивный алгоритм
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

r1=0;
r2=1;
for(i=0;i<=n1;i++)
{
d1=a[i]+b[i]+r1;
c1[i]=d1%10;
r1=d1/10;
d2=a[i]+b[i]+r2;
c2[i]=d2%10;
r2=d2/10;
}
Recv(&r)
if(r)c=c1;
else c=c2;
Спекулятивный алгоритм
Москва, 2010 г.
T’= 8n1τс
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Спекулятивное вычисление двух сумм
Спекулятивный алгоритм
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

Рассмотрены некоторые методы построения параллельных алгоритмов
Рассмотрен алгоритм диффузной балансировки загрузки процессоров
Представлен масштабируемый параллельный алгоритм, основанный на неэффективном последовательном алгоритме
Заключение
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.