Основные подходы к распараллеливанию

План

Конвейер
Матричная обработка
Распараллеливание циклов

Конвейер

Конвейерная обработка – метод распараллеливания существенно последовательных операций
Процессоры соединяются так, чтобы

Использование конвейера

Параллелизм на уровне инструкций
Конвейерная обработка в процессорах
Параллелизм на уровне процедур
Конвейерное

Когда конвейер эффективный

Три случая
С помощью конвейера необходимо решить несколько последовательных задач
С

Пример: конвейер первого типа

Пример: Нахождение суммы нескольких значений
Есть p процессоров
У каждого

Реализация

// i – номер поточного процессора
// d- дані поточного процесора
// sum

Время выполнения первой задачи

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

Время решения нескольких задач

Пусть задачу необходимо решить m раз для m

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

Предел коэффициента ускорения при m->∞
При очень

Иллюстрация

Графическая иллюстрация

Доля последовательных вычислений зависит от количества задач

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

Эффективность конвейера всегда меньше единицы
Для получения высоких

Конвейер второго типа

Пример: сортировка массива значений
На входе есть большой массив данных
Каждый

Программа

recv(i-1,x)
for(j=0;j<(n-i); j++){
recv(i-1,number)
if(number > x) {
Send(i+1,x);
} else {
send(i+1, number);
}
}

Оценка времени

Каждый процессор выполняет порядка n операций сравнения параллельно с остальными
Самый

Конвейер третьего типа

Одновременная передача данных и обработка (Send-ahead)
Если полученные от предыдущего

Пример конвейера третьего типа

Обратный ход метода Гаусса
Матрица треугольной формы

Решение

Последовательная программа

// по всем неизвестным
for(i=1; i<=n; i++){
sum=0;
// по всем найденным неизвестным
for(j=1;j

Параллельная программа

Процессор 1 –вычисляет x1 и передает его дальше
Процессор 2 принимает

Параллельная программа

for(j=1;j<=i; j++){
recv(p-1,x[j])
send(p+1,x[j])
}
sum=0;
for(j=1; i<=j; j++){ sum+=a[i][j]*x[j];
} x[i]=(b[i]-sum)/a[i][j]; send(p+1,x[i])

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

Последовательный алгоритм O(n2) операций
Параллельный алгоритм – каждый процессор порядка O(n) операций
Ускорение

Выводы относительно конвейера

Самый простой и дешевый вариант распараллеливания
Возможность распараллеливания принципиально последовательных

Матричная (векторная, параллельная) обработка

Каждый процессор получает часть своей задачи и выполняет

Ускорение

Ускорение при равномерной загрузке процессоров стремится к количеству процессоров
Эффективность стремится к

Преимущества

Высокая эффективность
Обмен мало влияет на скорость выполнения

Недостатки

Синхронный режим работы
Во время синхронизации процессоры простаивают
Нет возможности выполнять обмен одновременно

Векторно-конвейерная схема

Вектор – массив элементов одинакового типа
Векторные операции – большое количество

сложение двух чисел

Сложение чисел стандарт ANSI/IEEE
[A:] сравнение порядков и определение меньшего

Пример сложения

x+y, где x=1234,00 y = -567,8

Оценка времени

Время выполнения одной стадии t
Время сложения двух чисел 6t
Сложение двух

Диаграмма состояний

Конвейерное выполнение

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

Оценка времени

Время сложения двух векторов
Коэффициент ускорения

Параметры векторно-конвейерной системы

Размерность вектора, при котором скорость работы векторного процессора становится

Распараллеливание циклов

Циклы типа for() обычно хорошо распараллеливаются
Циклы типа while распараллеливаются обычно

Разбивка на блоки

for(i=0; i // тіло циклу
a[i]=b[i]+1;
}
Цикл разбивается на блоки
каждый блок выполняется

Пример разбивки на блоки

Цикл разбивается на p циклов
Каждый процессор выполняет свой

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

При отсутствии связи между данными внутри цикла эффективность стремится к 1

Развертка циклов

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

Векторизация циклов

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

Работа с большими матрицами

В прикладных задачах часто возникает проблема работы с

Блочные методы

Матрица разбивается на части – блоки (rxq блоков)
Каждый блок

Математика блочных операций

Математически операции с блочными матрицами выполняются так же, как

Распараллеливание блочных операций

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

Геометрическое распараллеливание

Процессоры, которые интенсивно взаимодействуют между собой должны находится «ближе»
например