Организация ЭВМ. Параллельные многопроцессорные вычислительные системы и комплексы

1. Организация ЭВМ

4. Параллельные
многопроцессорные
вычислительные системы и
комплексы
1

2. Организация ЭВМ

План
1 Классификация МП ВС и ВК
2 Классификация Флинна / Таненбаума
3 Проблемы распараллеливания
4 Закон Амдаля
5 Технологии программирования систем с
общей памятью (мультипроцессоров).
6 Векторные команды SSE
7 Технологии программирования
многопроцессорных вычислительных
комплексов (мультикомпьютеров)
2

3. Организация ЭВМ

1 Классификация МП ВС и ВК
1.1 По взаимодействию потоков команд и
данных (класcификация Флинна) :
- ОКОД (SISD);
- ОКМД (SIMD);
- МКОД (MISD);
- МКМД (MIMD);
3

4. Организация ЭВМ

1 Классификация МП ВС и ВК
1.2 По способу обмена между процессорами :
-обмен через общую память
(мультипроцессоры);
-обмен через передачу сообщений
(мультикомпьютеры или кластеры)
4

5. Организация ЭВМ

1 Классификация МП ВС и ВК
1.3 По используемому типу параллелизма :
- естественный (векторный, матричный);
- независимых ветвей (coarse grain);
- мелкозернистый (fine grain);
-смежных операций (instruction - level);
вариант (дихотомия) :
-параллелизм данных;
-параллелизм задач
5

6. Организация ЭВМ

1 Классификация МП ВС и ВК
1.4 По использованию совместной памяти :
- однородный доступ (UMA);
- неоднородный доступ (NUMA);
- только кэш (COMA).
6

7. Организация ЭВМ

1 Классификация МП ВС и ВК
1.5 По доступу к общим ресурсам :
- симметричный доступ (SMP);
- несимметричный доступ (Non – SMP,
master-slave).
7

8. Организация ЭВМ

1 Классификация МП ВС и ВК
1.6 По организации коммутации :
- общая шина;
- линейная или матричная;
- гиперкубы;
- полносвязная и др.
8

9. Организация ЭВМ

1 Классификация МП ВС и ВК
1.7 По управляющему потоку :
- поток команд (IF);
- поток данных (DF).
9

10. Организация ЭВМ

2 Классификация Флинна/Таненбаума
10

11. Организация ЭВМ

2 Проблемы распараллеливания
11

12. Организация ЭВМ

3 Проблемы распараллеливания
- распараллеливание алгоритма;
- создание параллельной программы;
- создание параллельной системы;
- перенос параллельной программы на
параллельную систему («вложение»)
12

13. Организация ЭВМ

4 Закон Амдаля
Kуск = Nп / ((Nп – 1) f + 1),
где Kуск – коэффициент ускорения,
Nп – количество процессоров в системе,
f – доля нераспараллеливаемого кода
(в долях единицы, по времени).
13

14. Организация ЭВМ

4.2 Следствия из закона Амдаля
1. Максимальное ускорение ограничено f.
2.Чем больше размерность задачи (матрицы,
например), тем выше Куск (производ.)
3. Чем больше доля обмена, тем ниже
производительность и т.д....
14

15. Организация ЭВМ

5 Технологии программирования систем с
общей памятью
1.На уровне процессов ОС (взаимодействие
процессов через сокеты, pipe, MPI). Процесс –
программа на этапе выполнения, процесс
характеризуется набором нитей выполнения, общей
памятью для них.
2. На уровне нитей (потоков) ОС – threads. Нить
разделяет с другими нитями процесса общую память,
но характеризуется собственной очередью команд.
15

16. Организация ЭВМ

5 Технологии многопоточного
программирования систем с общей памятью
1.На уровне API ОС (POSIX в UNIX,
WinAPI в Windows)
2.На уровне программных платформ
(.NET, Java 2EE), например System.Threading,
TPL (.NET 4.5) и др.
3.На уровне надстроек для ЯВУ (HLL),
прежде всего – OpenMP (С++/Fortran)
4. На уровне вычислительных библиотек (MKL, IPP, TBB)
5. На уровне прикладных пакетов (ANSYS, MatLab, etc.)
16

17. Организация ЭВМ

5 API OpenMP
1.Прагмы #pragma (C) – основной инструмент
2. Функции (информационные, управления)
3.Переменные окружения (например, количество
используемых потоков)
17

18. Организация ЭВМ

5 Пример OpenMP программы
// Умножение матрицы на вектор
void ParallelResultCalculation (float* pMatrix,
float* pVector, float* pResult, int Size) {
int i, j; // Loop variables
#pragma omp parallel for private (j)
for (i=0; i<Size; i++) {
for (j=0; j<Size; j++)
pResult[i] += pMatrix[i*Size+j]*pVector[j];
}
}
18

19. Организация ЭВМ

6 Векторные команды процессоров общего
назначения
1.Позволяют реализовать SIMD обработку (обработку
векторов, где вектора являются аргументами и
результатами операций)
2. Первая система – MMX (целочисленные операции,
максимум 8 элементов по 8 бит)
3. Следующее поколение – SSE (Streaming SIMD
Extrensions) и последующие ее версии – до 4 элементов
double (плавающая запятая).
(Сейчас автоматически вставляются компиляторами)
19

20. Организация ЭВМ

7 Технологии программирования систем
с передачей сообщений (кластеров)
1. Явная реализация передачи сообщений
1.1 На уровне протокола TCP (сокеты)
1.2 На уровне прикладных протоколов (например, HTTP)
1.3 С использованием технологий построения
распределенных приложений, использующих RPC/RMI
2. Использование интерфейса передачи сообщений
MPI (Message Passing Interface)
3. Использование модели общей памяти,
реализуемой через обмен сообщениями (PVM)
4. Надстройки над MPI (например, OpenTS и др.)
5. Вычислительные библиотеки, 6. Пакеты 20

21. Организация ЭВМ

7 Message Passing Interface
1. Большое количество функций передачи
сообщений (двухточечные, широковещательные,
групповые, синхронные, асинхронные и пр.),
очень сильно оптимизированные в реализациях
MPI (MPICH, MPICH2)
2. Возможность построения виртуальных
топологий сети поверх физических.
3. Возможность создания своих типов
данных для пересылки.
21

22. Организация ЭВМ

7 Структура MPI программы
#include "mpi.h"
int main ( int argc, char *argv[] ) {
int ProcNum, ProcRank;
//<программный код без использования MPI функций>
MPI_Init ( &agrc, &argv );
MPI_Comm_size ( MPI_COMM_WORLD, &ProcNum);
MPI_Comm_rank ( MPI_COMM_WORLD, &ProcRank);
//<программный код с использованием MPI функций >
MPI_Finalize();
//<программный код без использования MPI функций >
return 0;
}
22

23. Организация ЭВМ

7 Пример MPI программы
23