LEC02
.pdfПараллельные вычисления
Учебный год – 2015, весенний семестр Группы 5110, 5116
Лекция 2
Преподаватели:
Балакшин Павел Валерьевич
(pvbalakshin@gmail.com),
Соснин Владимир Валерьевич
(vsosnin@gmail.com)
Балльно-рейтинговая система (БАРС)
Диапазон баллов |
Оценка |
|
|
[0; 60) |
2F |
|
|
[60;67] |
3E |
|
|
(67;74] |
3D |
|
|
(74;83] |
4C |
|
|
(83;90] |
4B |
|
|
(90;100] |
5A |
|
|
Основные подходы к распараллеливанию
•Распараллеливание по данным
(два дворника сначала подметают по полулицы каждый, затем красят ползабора каждый ).
•Распараллеливание по инструкциям
(пока первый дворник подметает всю улицу, второй в это же время красит весь забор).
3
Распараллеливание по данным
Все ядра (потоки) одновременно выполняют один и тот же набор инструкций; отличаются только входные данные для этих инструкций. В примере общий набор инструкций помечен зелёным цветом.
Массив A
A[0] |
|
|
|
|
|
|
|
|
A[9] |
A[10] |
|
|
|
|
|
|
|
|
A[19] |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ядро 1
for (i = 0; i < 10; i++) {
A[i] = i * sin (i*Pi/2); if (A[i] == 0) A[i] = 1;
}
Ядро 2
for (i = 10; i < 20; i++) {
A[i] = i * sin (i*Pi/2); if (A[i] == 0) A[i] = 1;
}
4
Распараллеливание по инструкциям
Все ядра одновременно выполняют разные никак не взаимосвязанные наборы инструкций; наборы данных могут как совпадать (синий пример), так и отличаться (зелёный пример).
Фрагмент программы:
1.Перемножить матрицы А и Б.
2.Транспонировать матрицу С.
3.Найти максимальный элемент матрицы С.
4.Найти минимальный элемент матрицы С.
Последовательное выполнение |
Параллельное выполнение |
2 4
1 |
2 |
3 |
4 |
t |
1 |
3 |
t |
|
Важно: операции 3 и 4 нельзя выполнять параллельно с операцией 2. 5
Краткая характеристика OpenMP
Параллельная архитектура |
SMP (shared memory |
|
parallelism) |
|
|
Год стандартизации |
1997 (последняя версия 4.0 |
|
описана в 2013 г.) |
|
|
Языки программирования |
С/С++, Фортран |
|
|
Поддержка популярными |
gcc, icc – OpenMP 4.0 |
компиляторами |
IBM compiler – OpenMP 3.0 |
|
MS VS2013 – OpenMP 2.0 |
|
Общий «знаменатель» – |
|
OpenMP 2.0 |
|
|
6
Сильные стороны OpenMP
•Кроссплатформенность (в меру кроссплатформенности языков С/С++).
•Возможность постепенного (инкрементного) распараллеливания.
•Прямая совместимость (forward compatibility) со старыми компиляторами.
•Распараллеливание требует минимальных изменений существующего кода.
•Серьёзная поддержка ведущими производителями, хорошие перспективы развития (AMD, IBM, Intel, HP, Nvidia, Oracle Corporation, ...).
7
Слабые стороны OpenMP
•Сложно искать и исправлять ошибки синхронизации и гонки. Обработка штатных ошибок не развита.
•Применим только в SMP-системах, поэтому масштабируемость ограничена архитектурой памяти.
•Требует явной поддержки компилятора.
•Ограниченная поддержка вычислений на GPU (только с версии OpenMP 4.0).
•Большие накладные расходы на обеспечение параллельной работы программы (ввиду высокоуровневости синтаксиса OpenMP).
•Нет механизмов привязки потоков к процессорам. 8
Схема работы OpenMP
По материалам проф. Бухановского |
9 |
Модификация закона Амдала (по проф. Бухановскому)
N – количество распараллеливаемых операция, M – количество нераспараллеливаемых операций, tc – время выполнения одной операции, p – количество вычислителей, Ti – время выполнения программы при использовании i параллельных потоков на i вычислителях, α – масштабирующий коэффициент.
10