ПиРВС. Лекция 1-2. Основные понятия(1)

1. Основные понятия и архитектура ПВС

Параллельные и
распределенные
вычислительные
системы
Лекция 1-2

2.

Содержание лекции
Область применения многопроцессорных систем
Технологии
Проблемы
Пути достижения параллелизма
Схемы коммуникации в многопроцессорных ВС
Классификация
Параллелизм
Меры качества: ускорение, эффективность,
масштабирование
Закон Амдала

3. Кризисы программного обеспечения

1)60-е годы 20 века
• появление машин на транзисторах
• переход от языков низкого уровня к языками высокого уровня
• модульное программирование
2)Конец 70-х, начало 80-х годов 20 века
• появление больших интегральных схем (БИС)
• переход к объектно-ориентированным языкам программирования
3)Начало 2000-х годов –
• появление многоядерных процессоров
• эмпирический закон Мура перестал действовать
Проблема: автоматического распараллеливания не существует.

4. Рост производительности

7-8 лет
12-13 лет
18-20 лет
ПК
60 Gflop/s
Mobile
1 Gflop/s

5. Суперкомпьютер

Суперкомпьютер – это вычислительная
система, обладающая предельными
характеристиками
по
производительности среди имеющихся
в каждый конкретный момент времени
компьютерных систем.

6.

Задача
Компьютер
(миллионы, миллиарды…)
Метод
Технологии
программирования
Алгоритм
Предметная сторона
Системное ПО
Программа
Компьютерная сторона

7. Области применения многопроцессорных систем

-временная сложность (научные расчеты)
-пространственная сложность (большой объем
данных)
-задачи реального времени (промышленность)
-системы высокой надежности (космические
аппараты)

8. Области применения многопроцессорных систем

Стратегических исследованиях (управляемый
термоядерный синтез, моделирование взрывов и
ядерных испытаний, разработка военной и
авиакосмической техники, системы ПВО)
- Биологии
(моделирование
микроструктур),
медицине (использование суперкомпьютера и мед.
аппаратуры)
- Нанотехнологиях
- Астрономии (моделирование поведения звезд,
рождения звезд)
- авиастроении
- Космологии (моделирование структуры галактики)
-

9. Проблемы

• высокая
стоимость
параллельных
систем
–
в соответствии с законом Гроша (Grosch), производительность
компьютера возрастает пропорционально квадрату его стоимости
• потери производительности для организации параллелизма –
согласно гипотезе Минского (Minsky), ускорение, достигаемое при
использовании параллельной системы, пропорционально
двоичному логарифму от числа процессоров
• постоянное совершенствование последовательных компьютеров
• существование
последовательных
вычислений
–
в соответствии с законом Амдаля (Amdahl)
• зависимость эффективности параллелизма от учета характерных
свойств параллельных систем (отсутствие мобильности для
параллельных
программ)

10. Технологии

• MPI (Message Passing Interface)
• OpenMP (стандарт для программирования в
модели общей памяти)
• Графические процессоры

11. Технологии разработки

Программирование на стандартных и широко распространённых языках программирования с
использованием высокоуровневых коммуникационных библиотек и интерфейсов (API) для организации
межпроцессного взаимодействия.
Введение специальных "распараллеливающих" конструкций в язык программирования. При этом могут
создаваться оригинальные параллельные языки или параллельные расширения существующих (с
сохранением преемственности).
ATLAS, Aztec, BlockSolve95, Distributed Parallelization at CWP, DOUG, GALOPPS, JOSTLE, NAMD, P-Sparslib, PIM,
ParMETIS, PARPACK, PBLAS, PETSc, PGAPack, PLAPACK, ScaLAPACK, SPRNG,
Использование инструментальных систем, облегчающих создание и проектирование параллельных
программ.
BERT 77, FORGE, KAP, PIPS, VAST, V-Ray.
Программирование на стандартных языках. Использование в качестве конструктивных элементов заранее
распараллеленных процедур из специализированных библиотек.
Параллельные расширения и диалекты языка Fortran: Fortran-DVM, Cray MPP Fortran, F--, Fortran 90/95, Fortran D95,
Fortran M, Fx, HPF, Opus, Vienna Fortran,
Параллельные расширения и диалекты языков C/C++: C-DVM, A++/P++, CC++, Charm/Charm++, Cilk, HPC, HPC++,
Maisie, Mentat, mpC, MPC++, Parsec, pC++, sC++, uC++,
Другие параллельные языки и расширения: НОРМА, ABCL, Adl, Ada, Concurrent Clean, MC#, Erlang, Linda, Modula3, NESL, Occam, Orca, Parallaxis, Phantom, Sisal, SR, ZPL
Использование средств автоматического распараллеливания последовательных программ.
ACE, ARCH, BIP, BLACS, BSPlib, CVM, Counterpoint, FM, Gala, GA, HPVM, ICC, JIAJIA, KELP, LPARX, MPI, MPL,
OOMPI, OpenMP, P4, Para++, Phosphorus, PVM, Quarks, ROMIO, ShMem, SVMlib, TOOPS, Treadmarks
CODE, HeNCE, GRADE, TRAPPER, EDPEPPS, Reactor, DEEP, Converse.
Использование специализированных прикладных пакетов.

12. Пути достижения параллелизма

• независимость функционирования отдельных
устройств ЭВМ – данное требование относится в
равной степени ко всем основным компонентам
вычислительной системы: к устройствам ввода-вывода,
обрабатывающим процессорам и устройствам памяти;
• избыточность элементов вычислительной системы –
организация избыточности может осуществляться в
следующих основных формах:
• - использование специализированных устройств, таких,
например, как отдельные процессоры для целочисленной и
вещественной арифметики, устройства многоуровневой памяти
(регистры, кэш);
• - дублирование устройств ЭВМ путем использования,
например, нескольких однотипных обрабатывающих
процессоров или нескольких устройств оперативной памяти.

13. Режимы выполнения

• многозадачный режим ( режим разделения времени ), при котором для
выполнения нескольких процессов используется единственный процессор.
Данный режим является псевдопараллельным, когда активным
(исполняемым) может быть один, единственный процесс, а все остальные
процессы
находятся
в
состоянии
ожидания
своей
очереди;
применение режима разделения времени может повысить эффективность
организации вычислений (например, если один из процессов не может
выполняться из-за ожидания вводимых данных, процессор может быть
задействован для выполнения другого, готового к исполнению процесса).
• параллельное выполнение, когда в один и тот же момент может
выполняться несколько команд обработки данных. Такой режим
вычислений может быть обеспечен не только при наличии нескольких
процессоров, но и при помощи конвейерных и векторных обрабатывающих
устройств;
• распределенные вычисления ; данный термин обычно применяют для
указания параллельной обработки данных, при которой используется
несколько обрабатывающих устройств, достаточно удаленных друг от
друга, в которых передача данных по линиям связи приводит к
существенным временным задержкам.

14. Характеристика типовых схем коммуникации в многопроцессорных вычислительных системах

15.

16.

17.

18.

19. Топология сети вычислительных кластеров

• диаметр – показатель, определяемый как максимальное расстояние
между двумя процессорами сети (под расстоянием обычно
понимается величина кратчайшего пути между процессорами). Эта
величина может характеризовать максимально необходимое время
для передачи данных между процессорами, поскольку время
передачи обычно прямо пропорционально длине пути;
• связность ( connectivity ) – показатель, характеризующий наличие
разных маршрутов передачи данных между процессорами сети.
Конкретный вид данного показателя может быть определен,
например, как минимальное количество дуг, которое надо удалить
для разделения сети передачи данных на две несвязные области;
• ширина бинарного деления ( bisection width ) – показатель,
определяемый как минимальное количество дуг, которое надо
удалить для разделения сети передачи данных на две несвязные
области одинакового размера;
• стоимость – показатель, который может быть определен, например,
как общее количество линий передачи данных в многопроцессорной
вычислительной системе.

20. Характеристики

21. Классификация Флинна (1966 г)

22. Параллельные и распределенные системы

Параллельная система – это система,
в которой события могут быть
частично
или
полностью
упорядочены
С этой точки зрения – каждая
распределенная система – это
подкласс параллельной системы, в
которой процессы автономны и их
адресные
состояния
не
перекрываются.
Классификация мультипроцессорных
систем по организации памяти:
параллельная система с общей
памятью
параллельная
система
с
распределенной памятью
Классификация по «связности»

23. Классификация MIMD машин

24. Параллельные и распределенные системы

Параллельная система – это система,
в которой события могут быть
частично
или
полностью
упорядочены
С этой точки зрения – каждая
распределенная система – это
подкласс параллельной системы, в
которой процессы автономны и их
адресные
состояния
не
перекрываются.
Классификация мультипроцессорных
систем по организации памяти:
параллельная система с общей
памятью
параллельная
система
с
распределенной памятью
Классификация по «связности»

25.

26. Машины с распределенной памятью (Distributed memory)

27. Машины с общей памятью (Shared memory)

28.

29. Классификация ПВС

• Мультипроцессоры с использованием единой общей
памяти (shared memory)…
• обеспечивается однородный доступ к памяти (uniform
memory access or UMA),
• являются основой для построения:
• векторных параллельных процессоров (parallel vector processor
or PVP). Примеры: Cray T90,
• симметричных мультипроцессоров (symmetric multiprocessor
or SMP). Примеры: IBM eServer, Sun StarFire, HP Superdome,
SGI Origin.
29

30. Классификация ПВС

• Мультипроцессоры с использованием единой общей
памяти…
Процессор
Процессор
Кэш
Кэш
Оперативная
память
30

31. Классификация ПВС

Мультипроцессоры с использованием единой общей
памяти
Проблемы:
• Доступ с разных процессоров к общим данным и
обеспечение, в этой связи, однозначности
(когерентности) содержимого разных кэшей
(cache coherence problem),
• Необходимость синхронизации взаимодействия
одновременно выполняемых потоков команд
31

32. Классификация ПВС

Мультипроцессоры с использованием физически распределенной
памяти (distributed shared memory or DSM):
• неоднородный доступ к памяти (non-uniform memory access or
NUMA),
• Среди систем такого типа выделяют:
• Сache-only memory architecture or COMA (системы KSR-1 и
DDM),
• cache-coherent NUMA or CC-NUMA (системы SGI Origin 2000,
Sun HPC 10000, IBM/Sequent NUMA-Q 2000),
• non-cache coherent NUMA or NCC-NUMA (система Cray T3E).
32

33. Классификация ПВС

Мультипроцессоры с использованием физически распределенной
памяти…
Процессор
Кэш
Процессор
Оперативная
память
Кэш
Оперативная
память
Сеть передачи данных
33

34. Классификация ПВС

• Мультипроцессоры
с использованием
физически
распределенной памяти:
• упрощаются проблемы создания мультипроцессоров
(известны примеры систем с несколькими тысячами
процессоров),
• возникают проблемы эффективного использования
распределенной памяти (время доступа к локальной и
удаленной памяти может различаться на несколько
порядков).
34

35. Классификация ПВС

• Мультикомпьютеры…
• не обеспечивают общий доступ ко всей имеющейся в
системах памяти (no-remote memory access or NORMA),
• каждый процессор системы может использовать только
свою локальную память,
• для доступа к данным, располагаемых на других
процессорах, необходимо явно выполнить операции
передачи сообщений (message passing operations).
35

36. Классификация ПВС Мультикомпьютеры

Процессор
Процессор
Кэш
Кэш
Оперативная
память
Оперативная
память
Сеть передачи данных
36

37.

• Мультикомпьютеры
Данный подход используется при построении двух важных
типов многопроцессорных вычислительных систем:
• массивно-параллельных систем (massively parallel
processor or MPP), например: IBM RS/6000 SP2, Intel
PARAGON, ASCI Red, транспьютерные системы
Parsytec,
• кластеров (clusters), например: AC3 Velocity и NCSA
NT Supercluster.
37

38.

• Мультикомпьютеры. Кластеры…
Кластер - множество отдельных компьютеров,
объединенных в сеть, для которых при помощи
специальных аппаратно-программных средств
обеспечивается возможность унифицированного
управления (single system image), надежного
функционирования (availability) и эффективного
использования (performance)
38

39.

• Мультикомпьютеры. Кластеры…
Преимущества:
• Могут быть образованы на базе уже существующих у
потребителей отдельных компьютеров, либо же сконструированы
из типовых компьютерных элементов;
• Повышение вычислительной мощности отдельных процессоров
позволяет строить кластеры из сравнительно небольшого
количества отдельных компьютеров (lowly parallel processing),
• Для параллельного выполнения в алгоритмах достаточно
выделять только крупные независимые части расчетов (coarse
granularity).
39

40.

• Мультикомпьютеры. Кластеры
Недостатки:
• Организация взаимодействия вычислительных узлов
кластера при помощи передачи сообщений обычно
приводит к значительным временным задержкам,
• Дополнительные ограничения на тип
разрабатываемых параллельных алгоритмов и
программ (низкая интенсивность потоков передачи
данных)
40

41. Параллелизм

Параллелизм— это возможность одновременного выполнения более
одной арифметико-логической операции или программной ветви.
Возможность параллельного выполнения этих операций определяется
правилом Рассела, которое состоит в следующем:
Программные объекты A и B (команды, операторы, программы)
являются независимыми и могут выполняться параллельно, если
выполняется следующее условие:
где In(A) — набор входных, а Out(A) — набор выходных переменных
объекта A. Если условие не выполняется, то между A и B существует
зависимость
и они не могут выполняться параллельно.

42. Виды параллелизма

Мелкозернистый параллелизм (он же параллелизм
смежных операций или скалярный параллелизм) –
Fine Grade
Крупнозернистый
параллелизм,
который
включает: векторный параллелизм и параллелизм
независимых ветвей.. - Coarse Grain

43. Мелкозернистый параллелизм

• При исполнении программы
регулярно
встречаются
ситуации, когда исходные
данные для i-й операции
вырабатываются
заранее,
например, при выполнении (i 2)-й или (i - 3)-й операции.
Тогда при соответствующем
построении вычислительной
системы можно совместить во
времени
выполнение
i-й
операции с выполнением (i 1)-й, (i - 2)-й, ... операций. В
таком понимании скалярный
параллелизм
похож
на
параллелизм
независимых
ветвей, однако они очень
отличаются длиной ветвей и
требуют
разных
вычислительных систем.

44. Крупнозернистый параллелизм

• Векторный
параллелизм.
Наиболее
распространенной в обработке структур данных
является векторная операция (естественный
параллелизм). Вектор— одномерный массив,
который образуется из многомерного массива,
если один из индексов не фиксирован и
пробегает все значения в диапазоне его
изменения.

45. Внутренний параллелизм

46. Меры качества параллельных программ

• Время работы
– Сколько времени программа работает на N ядрах?
• Ускорение
– Во сколько раз программа стала быстрее работать
на N ядрах по сравнению с одним ядром /
последовательной программой?
• Эффективность распараллеливания
– Какой процент времени работы программы идёт
на полезную работу?
• Масштабируемость
– Как быстро эффективность падает с ростом числа
ядер?

47.

48.

49.

50. Закон Амдала

51.

52. Пример

53. Умножение матрицы на вектор

54.

55.

56.

57.

58. Умножение матрицы на вектор

59.

60.

61. Геометрический параллелизм

62.

63.

Заключение
Предпосылками развития параллельных и распределенных
систем является появление многоядерных процессоров и
рост объемов вычислений и данных
К проблемам технологии можно отнести высокую стоимость
параллельных систем, потери производительности для
организации параллелизма, постоянное совершенствование
последовательных
компьютеров
и
ограничения
масштабирования системы, в связи с существование
последовательных вычислений, зависимость эффективности
параллелизма от учета характерных свойств параллельных
систем
Классификация параллельных систем основана на понятиях
процессов и данных
Мерами качества являются ускорение, эффективность,
масштабирование