Параллельное программирование

1.

Парадигмы программирования
(с примерами на языке R)
Параллельное программирование
Голубничий А.А.
[email protected]
@Golubnichij

2.

Структура занятия
• области применения;
• подходы к разработке параллельных программ;
• множественные потоки команд/данных;
• технологии и подходы;
• ускорение алгоритмов (закон Амдала);
• языки параллельного программирования.
2

3.

Области применения
• генетика;
• климатология;
• физика высоких энергий;
• астрономия;
• запросы массового обслуживания
(банковская система);
• и др.
3

4.

Основные понятия
Параллельные
вычисления
–
способ
организации
компьютерных
вычислений,
при
котором
программы
разрабатываются,
как
набор
взаимодействующих
вычислительных процессов, работающих асинхронно и при этом
одновременно.
Параллельное
программирование
–
это
техника
программирования,
которая
использует
преимущества
многоядерных или многопроцессорных компьютеров и является
подмножеством более широкого понятия многопоточности
(multithreading).
4

5.

Подходы к параллельному программированию
• Последовательное
программирование
с
дальнейшим
автоматическим распараллеливанием.
• Непосредственное формирование потоков параллельного
управления, с учетом особенностей архитектур параллельных
вычислительных систем или операционных систем.
• Описание параллелизма без использования явного управления
обеспечивается заданием только информационных связей.
Предполагается, что программа будет выполняться на
вычислительных системах с бесконечными ресурсами,
операторы будут запускаться немедленно по готовности их
исходных данных.
5

6.

Множественные потоки команд/данных
Одиночный поток данных
(Single Dаtа)
Множество потоков
данных (Multiple Dаtа)
Одиночный поток Множество потоков
команд
команд
(Single Instructiоn) (Multiple Instructiоn)
SISD (ОКОД)
MISD (МКОД)
SIMD (ОКМД)
MIMD (МКМД)
6

7.

Множественные потоки команд/данных
Класс Описание класса
SISD Исполнение одним процессором одного потока команд,
обрабатывающего данные, хранящиеся в одной памяти.
Классические последовательные машины, машины фоннеймановского типа.
SIMD Сохраняется один поток команд, включающий векторные
команды, что позволяет выполнять одну арифметическую
операцию сразу над многими данными – элементами вектора.
MISD Подразумевает наличие в архитектуре многих процессоров,
обрабатывающих один и тот же поток данных.
MIMD В вычислительной системе есть несколько устройств
обработки команд, объединенных в единый комплекс и
работающих каждое со своим потоком команд и данных. 7

8.

Технологии и подходы
SSE
OpenMP
MPI
8

9.

SSE (Streaming SIMD Extensions)
SSE (потоковое SIMD-расширение процессора) – это SIMD набор
инструкций, разработанный Intel и впервые представленный в
процессорах серии Pentium III как ответ на аналогичный набор
инструкций 3DNow! от AMD
Версия Возможности
1
Восемь 128-битных регистров для 4 чисел по 32
бит (с плавающей точкой)
2
Теперь 2 64-битных числа в регистре
3
13 инструкций
4.1
47 инструкций (ускорение видео)
4.2
54 инструкции (операции со строками)
9

10.

OpenMP
OpenMP (Open Multi-Processing) –
открытый стандарт для
распараллеливания программ на языках C, C++ и Fortran. Дает
описание совокупности директив компилятора, библиотечных
процедур и переменных окружения, которые предназначены для
программирования
многопоточных
приложений
на
многопроцессорных системах с общей памятью.
10

11.

MPI
Message Passing Interface (MPI, интерфейс передачи сообщений)
– программный интерфейс (API) для передачи информации, который
позволяет обмениваться
сообщениями между
процессами,
выполняющими одну задачу.
Разработан Уильямом Гроуппом, Эвином Ласком и другими.
11

12.

Закон Амдала
Закон
Амдала
(1967
год),
описывает
максимальный
теоретический выигрыш в производительности параллельного
решения по отношению к лучшему последовательному
решению.
где S – во сколько раз можно ускорить вычисления (ускорение);
p – количество процессоров (ядер),
a – доля последовательно вычисляемого кода
12

13.

Закон Амдала
13

14.

Языки параллельного программирования
Alice;
Chapel;
Cilk;
Concurrent ML;
Erlang; Fortress;
Global Arrays;
Intel Cilk Plus;
Linda; Occam;
Oz;
T++;
Unified Parallel C;
X10.
14

15.

Пример программы
15