Принципы построения параллельных вычислительных систем.

Сентябрь 3, 2022

Главная
Алгебра
Принципы построения параллельных вычислительных систем.

Содержание

2. Структура предметной области (Параллельные вычисления) Математические основы параллельных вычислений Архитектура параллельных вычислительных систем Технологии параллельного программирования
3. Литература В ИБЦ: Воеводин В. В. Параллельные вычисления. Богачев К. Ю. Основы параллельного программирования. Гергель В.
4. Что такое параллельные вычисления? Параллельные вычисления – процесс обработки данных, в котором могут одновременно выполняться несколько
5. Параллельные вычислительные системы Параллельные вычисления – процесс обработки данных, в котором одновременно выполняется более одной операции.
6. Теоретические и практические проблемы параллельных вычислений Разработка параллельных вычислительных систем (ПВС) Анализ эффективности параллельных вычислений Разработка
7. Показатели производительности параллельного выполнения Ускорение (Speedup) - за счёт параллельного выполнения программы в N потоках: a(N)
8. Оценки производительности. Гипотеза Мински. Потери производительности при организации параллелизма Гипотеза Марвина Ли Мински (Marvin Lee Minsky,
9. Оценки производительности. Закон Амдала. Максимальный теоретический выигрыш для сочетания параллельных вычислений с последовательными: Закон Амдала: если
10. Автор закона (конец 1960 г.г.) – главный разработчик мейнфреймов серии IBM/360 Джин Амдал (Gene Amdahl), основатель
11. Закон Амдала (графики от riki-koen.livejournal.com/75235.html) АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1
12. р=0.1, с=0.001, max=6.25 (чем меньше с, тем быстрее обмен данными) АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ.
13. Организация параллельных вычислений – возможные режимы Многозадачный режим, или режим разделения времени: Псевдопараллельность – для выполнения
14. Основные типы ПВС Суперкомпьютер: ВС рекордной производительности, выпускаемая отдельными экземплярами на оригинальной схемотехнической базе. ВС ценой
15. Основные типы ПВС Кластер – группа выделенных рабочих станций: объединены в ЛВС, эффективно и надежно работают
16. Классификация ПВС по архитектуре Архитектура ВС - общая логическая организация ВС: определяющая процесс обработки данных, включающая
17. Основные типы ВС по Флинну (Michael J. Flynn, Таксономия Флинна - 1966 г.) АЛГОРИТМЫ И ТЕХНОЛОГИИ
18. Основные типы ВС по Флинну SISD (Single Instruction Single Data) – 1 поток команд, 1 поток
19. Основные типы ВС по Флинну SIMD (Single Instruction Multiple Data) – 1 поток команд, много потоков
20. Основные типы ВС по Флинну MISD (Multiple Instruction Single Data) – много потоков команд, 1 поток
21. Разновидности ВС типа MIMD Дальнейшая классификация ВС – по способам организации оперативной памяти: Мультипроцессоры – ВС
22. Мультипроцессоры – способы построения общей памяти Единая общая память с равноправным (однородным) доступом (Uniform Memory Access,
23. Архитектура систем UMA АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1
24. Cache memory – кэш-память, кэш: промежуточный буфер с быстрым доступом, содержащий информацию, которая может быть запрошена
25. Проблемы UMA Доступ с разных процессоров к общим данным ? Необходимо обеспечивать однозначность (когерентность) содержимого разных
26. Копии значения переменной x – в разных кэшах ? Возможно изменение х одним из процессоров. АЛГОРИТМЫ
27. Проблемы UMA Доступ с разных процессоров к общим данным ? Необходимость синхронизации взаимодействия одновременно выполняемых потоков
28. Мультипроцессоры – способы построения общей памяти 2. Физически распределенная общая память с неравноправным (неоднородным) доступом (Non-Uniform
29. Архитектура систем NUMA АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1
30. NUMA системы Для данных используются только локальные кэши процессоров – нет общей памяти => нет проблемы
31. Мультикомпьютеры МК – ВС с распределенной памятью самостоятельных компьютеров, объединенных в сеть МК – системы типа
32. Основные типы МК – многопроцессорных вычислительных систем Массивно (массово)-параллельные системы, MPP-системы (Massively Parallel Processing – массово-параллельная
33. Основные типы МК – многопроцессорных вычислительных систем Кластер - набор рабочих станций (или даже ПК) общего
34. Классификация многопроцессорных ВС (подробно см. http://parallel.ru/computers/classes.html) АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1
35. Коммуникация в МВС Коммуникация между процессорами обеспечивает: взаимодействие, синхронизацию, взаимоисключения выполняемых процессов ? Коммуникационная «трудоемкость» алгоритма
36. Примеры топологий сетей в МВС АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1
37. Особенности топологий сетей передачи данных Тип - Преимущества - Реализация Полный граф – минимум затрат на
38. Характеристики топологий сети Диаметр – определяет время передачи данных через max расстояние между 2 CPU сети
40. Скачать презентацию

Слайд 2

Структура предметной области (Параллельные вычисления)
Математические основы параллельных вычислений
Архитектура параллельных вычислительных систем
Технологии параллельного

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

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 3

Литература
В ИБЦ:
Воеводин В. В. Параллельные вычисления.
Богачев К. Ю. Основы параллельного программирования.
Гергель

В. П. Теория и практика параллельных вычислений.
Учебные курсы Интернет Университета Информационных технологий
Гергель В.П. Теория и практика параллельных вычислений. — www.intuit.ru/department/calculate/paralltp/
Основы параллельного программирования с использованием Microsoft Visual Studio 2010. –www.intuit.ru/department/se/baseppvs2010/
Барский А.Б. Параллельное программирование. — www.intuit.ru/department/se/parallprog
Интернет-ресурсы:
www.hpc-education.ru
www.supercomputers.ru

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 4

Что такое параллельные вычисления?
Параллельные вычисления – процесс обработки данных, в котором

могут одновременно выполняться несколько операций вычислительной (компьютерной) системы (ВС).
Такие системы называют параллельными вычислительными системами (ПВС).
Способы построения и применения ПВС – технологии параллельной обработки данных

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 5

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

выполняется более одной операции.
ПВС – вычислительная система, включающая не менее двух одновременно работающих обрабатывающих устройств (процессоров) или ядер одного процессора.
Процессор – CPU (central processing unit), GPU (graphic processing unit).
Ядро (core) – часть процессора, выполняющая один программный поток.
Программный поток (thread) – последовательность команд, выполняющаяся независимо от других последовательностей.
Каждая программа имеет минимум 1 поток.
ОС назначает ресурсы каждому потоку.
Поток может создавать другие потоки.

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 6

Теоретические и практические проблемы параллельных вычислений
Разработка параллельных вычислительных систем (ПВС)
Анализ эффективности

параллельных вычислений
Разработка обобщенных параллельных алгоритмов решения задач
Создание СПО для ПВС
Разработка параллельных алгоритмов решения прикладных задач

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 7

Показатели производительности параллельного выполнения
Ускорение (Speedup) - за счёт параллельного выполнения программы

в N потоках:
a(N) = T(1) / T(N)
Эффективность (Efficiency) системы, реализующей N потоков
E(N) = a(N) / N
Масштабируемость (Scalability) системы - возможность ускорения вычислений пропорционально числу потоков, (т.е. линейное ускорение):
a(N)=N
Суперлинейное ускорение:
a(N)>N
Часто N связывают с числом процессоров или ядер.

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 8

Оценки производительности. Гипотеза Мински.
Потери производительности при организации параллелизма
Гипотеза Марвина Ли Мински (Marvin

Lee Minsky, искусственный интеллект, нейронные сети)
a=С*log2N,
С – коэффициент пропорциональности
Пример: a=10 при N=1000, С=1
(не для любых алгоритмов!)
НО возможно использование параллелизма на 100%

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 9

Оценки производительности. Закон Амдала.
Максимальный теоретический выигрыш для сочетания параллельных вычислений с последовательными:
Закон

Амдала: если p – доля последовательных вычислений, то a<=1/(p+(1-p)/N)
Это асимптота с верхним пределом 1/p a= T(1)/T(N)= T(1)/(p*T(1)+(1-p)*T(1)/N)= 1/(p+(1-p)/N
Следствие: увеличение числа ядер менее эффективно, чем распараллеливание
Учет времени обмена данными между потоками(c*N) – есть max:
a<=1/(p+(1-p)/N+c*N)

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 10

Автор закона (конец 1960 г.г.) – главный разработчик мейнфреймов серии IBM/360

Джин Амдал (Gene Amdahl), основатель
Amdahl — американская корпорация, производитель IBM-совместимых серверов.
Основана в 1968 году, с 1997 года принадлежит Fujitsu.
http://chernykh.net/content/view/455/667/

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 11

Закон Амдала (графики от riki-koen.livejournal.com/75235.html)
АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ

Слайд 12

р=0.1, с=0.001, max=6.25 (чем меньше с, тем быстрее обмен данными)
АЛГОРИТМЫ И

ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 13

Организация параллельных вычислений – возможные режимы
Многозадачный режим, или режим разделения времени:
Псевдопараллельность

– для выполнения нескольких программ используется один процессор ? исполняется 1 программа (процесс, задание, задача), прочие – в очереди.
Параллельное выполнение:
Одномоментное выполнение нескольких команд обработки данных из разных потоков или с разными данными на нескольких процессорах (ядрах).
Распределенные вычисления:
Параллельное выполнение на удаленных устройствах ?
Возможны проблемы с обменом данными ?
Актуальны для специфических задач.

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 14

Основные типы ПВС
Суперкомпьютер:
ВС рекордной производительности, выпускаемая отдельными экземплярами на оригинальной

схемотехнической базе.
ВС ценой > $1 млн.
ВС, мощность которой только на порядок меньше необходимой для современных задач)).
Способы построения и применения СК – технологии высокопроизводительных вычислений (ТВВ) – High Performance Computing (HPC).
С 1980 г.г. СК стали ПВС ?
ТВВ взаимосвязаны с технологиями параллельной обработки данных (иногда синоним)

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 15

Основные типы ПВС
Кластер – группа выделенных рабочих станций:
объединены в ЛВС,
эффективно

и надежно работают как единый вычислительный ресурс,
используется серийное, типовое оборудование (компьютерное и сетевое).
Развитие сетевого оборудования (конец 1990г.г.) ? суперкомпьютеры часто строятся по технологии кластеров.
Пример – СК - кластер ИМКН: 2 IBM eServer BladeCenter™+ флагманское сетевое оборудование Cisco Systems + хранилище

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 16

Классификация ПВС по архитектуре
Архитектура ВС - общая логическая организация ВС:

определяющая процесс обработки данных,
включающая
архитектуру ЭВМ,
структуру и характеристики программного обеспечения, принципы его взаимодействия с аппаратными средствами.
Основа классификации – систематика Флинна: анализ взаимодействия потоков выполняемых команд и потоков обрабатываемых данных ? вид параллелизма (ПВС)

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 17

Основные типы ВС по Флинну (Michael J. Flynn, Таксономия Флинна -

1966 г.)

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 18

Основные типы ВС по Флинну
SISD (Single Instruction Single Data) –

1 поток команд, 1 поток данных.
есть только один поток команд,
все команды обрабатываются последовательно друг за другом,
каждая команда инициирует одну операцию с одним потоком данных
П. Стандартный компьютер фон Неймана.

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 19

Основные типы ВС по Флинну
SIMD (Single Instruction Multiple Data) –

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

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 20

Основные типы ВС по Флинну
MISD (Multiple Instruction Single Data) – много

потоков команд, 1 поток данных. Отказоустойчивые компьютеры, ВС с систолическим массивом (systolic array) процессоров.
MIMD (Multiple Instruction Multiple Data) – много потоков команд, много потоков данных. Большинство многопроцессорных ПВС

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 21

Разновидности ВС типа MIMD
Дальнейшая классификация ВС – по способам организации оперативной

памяти:
Мультипроцессоры – ВС с общей, разделяемой между процессорами памятью.
Мультикомпьютеры – ВС с распределенной памятью самостоятельных компьютеров, объединенных в сеть (MPP-системы, Massively Parallel Processing).

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 22

Мультипроцессоры – способы построения общей памяти
Единая общая память с равноправным (однородным)

доступом (Uniform Memory Access, UMA).
Используется в ВС на основе:
симметричных мультипроцессоров (SMP-системы, Symmetric Multiprocessing) П. IBM eServer,
векторных параллельных процессоров, в которых предусмотрены команды однотипной обработки векторов независимых данных (PVP-системы, Parallel Vector Processor)

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 23

Архитектура систем UMA
АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 24

Cache memory – кэш-память, кэш: промежуточный буфер с быстрым доступом, содержащий информацию, которая

может быть запрошена с наибольшей вероятностью.
Доступ к данным в кэше быстрее, чем выборка исходных данных из оперативной памяти ?
Уменьшается время доступа к данным ?
Увеличивается общая производительность ВС.
Кэширование применяется жесткими дисками, браузерами, Web-серверами, службами DNS и т.д.

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 25

Проблемы UMA
Доступ с разных процессоров к общим данным ?
Необходимо обеспечивать однозначность

(когерентность) содержимого разных кэшей (cache coherence problem).
Решение: уведомление всех процессорных узлов (и кэшей!) об изменении значения в общей памяти

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 26

Копии значения переменной x – в разных кэшах ? Возможно изменение

х одним из процессоров.

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 27

Проблемы UMA
Доступ с разных процессоров к общим данным ?
Необходимость синхронизации взаимодействия

одновременно выполняемых потоков команд (многопоточность)
Методы синхронизации:
Мьютекс (mutual exclusion, взаимоисключение)
Семафор
События
…

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 28

Мультипроцессоры – способы построения общей памяти
2. Физически распределенная общая память с

неравноправным (неоднородным) доступом (Non-Uniform Memory Access, NUMA).
Принцип:
Блок памяти ↔ процессор (быстрый доступ)
«Чужие» блоки ↔ процессор (медленный доступ – до нескольких порядков) – ОСНОВНАЯ ПРОБЛЕМА!

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 29

Архитектура систем NUMA
АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 30

NUMA системы
Для данных используются только локальные кэши процессоров – нет общей

памяти => нет проблемы когерентности (COMA-системы, Cache-Only Memory Architecture)
Обеспечена когерентность локальных кэшей (аппаратно) (СС-NUMA-системы, Cache-Coherent)
Не обеспечена когерентность локальных кэшей (NСС-NUMA-системы, Non-Cache-Coherent)

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 31

Мультикомпьютеры
МК – ВС с распределенной памятью самостоятельных компьютеров, объединенных в сеть
МК

– системы типа NORMA (No-Remote Memory Access – «нет доступа к удаленной памяти»)
Архитектура аналогична архитектуре МП с распределенной памятью.
НО!:
Каждый процессор может использовать только свою локальную память.
Для доступа к «чужим» данных д.б. явно выполнены операции передачи сообщений (message passing operations) – 1- или 2-сторонний обмен данными

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 32

Основные типы МК – многопроцессорных вычислительных систем
Массивно (массово)-параллельные системы, MPP-системы (Massively

Parallel Processing – массово-параллельная обработка)
Система состоит из однородных узлов (до 103), включающих:
один или несколько ЦП (обычно RISC),
локальную память (прямой доступ к памяти других узлов невозможен!),
коммуникационный процессор или сетевой адаптер
жесткие диски и/или другие устройства I/O

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 33

Основные типы МК – многопроцессорных вычислительных систем
Кластер - набор рабочих станций

(или даже ПК) общего назначения, используется в качестве дешевого варианта МРР-системы.
Связь узлов - одна из стандартных сетевых технологий (Fast/Gigabit Ethernet, Myrinet и др.) на базе шинной архитектуры или коммутатора.

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 34

Классификация многопроцессорных ВС (подробно см. http://parallel.ru/computers/classes.html)
АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ

Слайд 35

Коммуникация в МВС
Коммуникация между процессорами обеспечивает:
взаимодействие, синхронизацию, взаимоисключения выполняемых процессов

?
Коммуникационная «трудоемкость» алгоритма влияет на выбор способа решения задачи
Коммуникация определяется топологией сети – схемой расположения и соединения сетевых устройств.

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 36

Примеры топологий сетей в МВС
АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ

Слайд 37

Особенности топологий сетей передачи данных
Тип - Преимущества - Реализация
Полный граф – минимум

затрат на передачу данных - - (кластер с соединением CPU через свитч с ограничением: только одна одномоментная операция приема-передачи данных для каждого процессора ? взаимодействующие пары CPU не должны пересекаться).
Линейка – идеально для конвейерных вычислений - +
Кольцо - ? - +
Звезда – для централизованных схем вычислений - +
Решетка (2D, 3D) - + - +

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Слайд 38

Характеристики топологий сети
Диаметр – определяет время передачи данных через max расстояние

между 2 CPU сети (расстояние равно величине кратчайшего пути).
Связность – определяет наличие разных маршрутов передачи данных между CPU, min число дуг графа, которые надо удалить для получения 2 несвязных областей.
Ширина бисекции – связность, но 2 области д.б. одинакового размера
Стоимость – общее число линий передачи данных в МВС

АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Принципы построения параллельных вычислительных систем.

Содержание

ЛитератураВ ИБЦ:Воеводин В. В. Параллельные вычисления.Богачев К. Ю. Основы параллельного программирования.Гергель

Что такое параллельные вычисления?Параллельные вычисления – процесс обработки данных, в котором

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

Теоретические и практические проблемы параллельных вычисленийРазработка параллельных вычислительных систем (ПВС)Анализ эффективности

Показатели производительности параллельного выполненияУскорение (Speedup) - за счёт параллельного выполнения программы

Оценки производительности. Гипотеза Мински.Потери производительности при организации параллелизмаГипотеза Марвина Ли Мински (Marvin

Оценки производительности. Закон Амдала.Максимальный теоретический выигрыш для сочетания параллельных вычислений с последовательными:Закон

Автор закона (конец 1960 г.г.) – главный разработчик мейнфреймов серии IBM/360

Закон Амдала (графики от riki-koen.livejournal.com/75235.html)АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ

р=0.1, с=0.001, max=6.25 (чем меньше с, тем быстрее обмен данными)АЛГОРИТМЫ И

Организация параллельных вычислений – возможные режимыМногозадачный режим, или режим разделения времени:Псевдопараллельность

Основные типы ПВС Суперкомпьютер:ВС рекордной производительности, выпускаемая отдельными экземплярами на оригинальной

Основные типы ПВС Кластер – группа выделенных рабочих станций:объединены в ЛВС,эффективно

Классификация ПВС по архитектуре Архитектура ВС - общая логическая организация ВС:

Основные типы ВС по Флинну (Michael J. Flynn, Таксономия Флинна -

Основные типы ВС по Флинну SISD (Single Instruction Single Data) –

Основные типы ВС по Флинну SIMD (Single Instruction Multiple Data) –

Основные типы ВС по ФлиннуMISD (Multiple Instruction Single Data) – много

Разновидности ВС типа MIMDДальнейшая классификация ВС – по способам организации оперативной

Мультипроцессоры – способы построения общей памятиЕдиная общая память с равноправным (однородным)

Архитектура систем UMAАЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Cache memory – кэш-память, кэш: промежуточный буфер с быстрым доступом, содержащий информацию, которая

Проблемы UMA Доступ с разных процессоров к общим данным ?Необходимо обеспечивать однозначность

Копии значения переменной x – в разных кэшах ? Возможно изменение

Проблемы UMA Доступ с разных процессоров к общим данным ?Необходимость синхронизации взаимодействия

Мультипроцессоры – способы построения общей памяти2. Физически распределенная общая память с

Архитектура систем NUMAАЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

NUMA системыДля данных используются только локальные кэши процессоров – нет общей

МультикомпьютерыМК – ВС с распределенной памятью самостоятельных компьютеров, объединенных в сетьМК

Основные типы МК – многопроцессорных вычислительных системМассивно (массово)-параллельные системы, MPP-системы (Massively

Основные типы МК – многопроцессорных вычислительных системКластер - набор рабочих станций

Классификация многопроцессорных ВС (подробно см. http://parallel.ru/computers/classes.html)АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ

Коммуникация в МВСКоммуникация между процессорами обеспечивает: взаимодействие, синхронизацию, взаимоисключения выполняемых процессов

Примеры топологий сетей в МВСАЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ

Особенности топологий сетей передачи данныхТип - Преимущества - Реализация Полный граф – минимум

Характеристики топологий сетиДиаметр – определяет время передачи данных через max расстояние

Похожие презентации

Литература
В ИБЦ:
Воеводин В. В. Параллельные вычисления.
Богачев К. Ю. Основы параллельного программирования.
Гергель

Что такое параллельные вычисления?
Параллельные вычисления – процесс обработки данных, в котором

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

Теоретические и практические проблемы параллельных вычислений
Разработка параллельных вычислительных систем (ПВС)
Анализ эффективности

Показатели производительности параллельного выполнения
Ускорение (Speedup) - за счёт параллельного выполнения программы

Оценки производительности. Гипотеза Мински.
Потери производительности при организации параллелизма
Гипотеза Марвина Ли Мински (Marvin

Оценки производительности. Закон Амдала.
Максимальный теоретический выигрыш для сочетания параллельных вычислений с последовательными:
Закон

Закон Амдала (графики от riki-koen.livejournal.com/75235.html)
АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ

р=0.1, с=0.001, max=6.25 (чем меньше с, тем быстрее обмен данными)
АЛГОРИТМЫ И

Организация параллельных вычислений – возможные режимы
Многозадачный режим, или режим разделения времени:
Псевдопараллельность

Основные типы ПВС
Суперкомпьютер:
ВС рекордной производительности, выпускаемая отдельными экземплярами на оригинальной

Основные типы ПВС
Кластер – группа выделенных рабочих станций:
объединены в ЛВС,
эффективно

Классификация ПВС по архитектуре
Архитектура ВС - общая логическая организация ВС:

Основные типы ВС по Флинну
SISD (Single Instruction Single Data) –

Основные типы ВС по Флинну
SIMD (Single Instruction Multiple Data) –

Основные типы ВС по Флинну
MISD (Multiple Instruction Single Data) – много

Разновидности ВС типа MIMD
Дальнейшая классификация ВС – по способам организации оперативной

Мультипроцессоры – способы построения общей памяти
Единая общая память с равноправным (однородным)

Архитектура систем UMA
АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

Проблемы UMA
Доступ с разных процессоров к общим данным ?
Необходимо обеспечивать однозначность

Проблемы UMA
Доступ с разных процессоров к общим данным ?
Необходимость синхронизации взаимодействия

Мультипроцессоры – способы построения общей памяти
2. Физически распределенная общая память с

Архитектура систем NUMA
АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 1

NUMA системы
Для данных используются только локальные кэши процессоров – нет общей

Мультикомпьютеры
МК – ВС с распределенной памятью самостоятельных компьютеров, объединенных в сеть
МК

Основные типы МК – многопроцессорных вычислительных систем
Массивно (массово)-параллельные системы, MPP-системы (Massively

Основные типы МК – многопроцессорных вычислительных систем
Кластер - набор рабочих станций

Классификация многопроцессорных ВС (подробно см. http://parallel.ru/computers/classes.html)
АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ

Коммуникация в МВС
Коммуникация между процессорами обеспечивает:
взаимодействие, синхронизацию, взаимоисключения выполняемых процессов

Примеры топологий сетей в МВС
АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ

Особенности топологий сетей передачи данных
Тип - Преимущества - Реализация
Полный граф – минимум

Характеристики топологий сети
Диаметр – определяет время передачи данных через max расстояние