Классификация вычислительных систем

Сентябрь 3, 2022

Главная
Алгебра
Классификация вычислительных систем

Содержание

2. Классификация ПВС по архитектуре Архитектура ВС - общая логическая организация ВС: определяющая процесс обработки данных, включающая
3. Основные типы ВС по Флинну (Michael J. Flynn, Таксономия Флинна - 1966 г.) АЛГОРИТМЫ И ТЕХНОЛОГИИ
4. Основные типы ВС по Флинну SISD (Single Instruction Single Data) – 1 поток команд, 1 поток
5. Основные типы ВС по Флинну SIMD (Single Instruction Multiple Data) – 1 поток команд, много потоков
6. Основные типы ВС по Флинну MISD (Multiple Instruction Single Data) – много потоков команд, 1 поток
7. Разновидности ВС типа MIMD Дальнейшая классификация ВС – по способам организации оперативной памяти: Мультипроцессоры – ВС
8. Мультипроцессоры – способы построения общей памяти Единая общая память с равноправным (однородным) доступом (Uniform Memory Access,
9. Архитектура систем UMA АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 2
10. Cache memory – кэш-память, кэш: промежуточный буфер с быстрым доступом, содержащий информацию, которая может быть запрошена
11. Проблемы UMA. Однозначность данных Доступ с разных процессоров к общим данным ? Необходимо обеспечивать однозначность (когерентность)
12. Копии значения переменной x – в разных кэшах ? Возможно изменение х одним из процессоров. АЛГОРИТМЫ
13. Проблемы UMA. Синхронизация Доступ с разных процессоров к общим данным ? Необходимость синхронизации взаимодействия одновременно выполняемых
14. Синхронизация. Семафор Семафор – системный объект, с набором методов. В C/C++, C# можно работать с семафорами
15. Синхронизация. Мьютекс Мьютекс – системный объект, с набором методов. В C/C++, C# можно работать с мьютексами
16. Синхронизация. Критические секции Критическая секция - участок кода, который может одномоментно выполнять только один поток. В
17. Синхронизация. События Событие - объект, который может быть в состоянии нейтральном или сигнализирующем. Поток может ждать
18. Мультипроцессоры – способы построения общей памяти 2. Физически распределенная общая память с неравноправным (неоднородным) доступом (Non-Uniform
19. Архитектура систем NUMA АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 2
20. NUMA системы Для данных используются только локальные кэши процессоров – нет общей памяти => нет проблемы
21. Мультикомпьютеры МК – ВС с распределенной памятью самостоятельных компьютеров, объединенных в сеть МК – системы типа
22. Основные типы МК – многопроцессорных вычислительных систем Массивно (массово)-параллельные системы, MPP-системы (Massively Parallel Processing – массово-параллельная
23. Основные типы МК – многопроцессорных вычислительных систем Кластер - набор рабочих станций (или даже ПК) общего
24. Классификация многопроцессорных ВС (подробно см. http://parallel.ru/computers/classes.html) АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 2
25. Коммуникация в МВС Коммуникация между процессорами обеспечивает: взаимодействие, синхронизацию, взаимоисключения выполняемых процессов ? Коммуникационная «трудоемкость» алгоритма
26. Примеры топологий сетей в МВС АЛГОРИТМЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ. ЛЕКЦИЯ 2
27. Особенности топологий сетей передачи данных Тип - Преимущества - Реализация Полный граф – минимум затрат на
28. Характеристики топологий сети Диаметр – определяет время передачи данных через max расстояние между 2 CPU сети
30. Скачать презентацию

Слайд 2

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

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

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

Слайд 3

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

1966 г.)

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

Слайд 4

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

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

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

Слайд 5

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

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

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

Слайд 6

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

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

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

Слайд 7

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

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

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

Слайд 8

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

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

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

Слайд 9

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

Слайд 10

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

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

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

Слайд 11

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

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

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

Слайд 12

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

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

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

Слайд 13

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

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

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

Слайд 14

Синхронизация. Семафор
Семафор – системный объект, с набором методов.
В C/C++, C# можно

работать с семафорами через стандартные классы.
Семафор может обеспечить:
запрет одновременного выполнения заданных процессов или потоков;
ограничение на число параллельных потоков;
поочерёдный доступ к ресурсам, для которых невозможен одновременный доступ.

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

Слайд 15

Синхронизация. Мьютекс
Мьютекс – системный объект, с набором методов.
В C/C++, C# можно

работать с мьютексами через стандартные классы.
Мьютекс может находиться в 2 состояниях:
свободен;
занят.
Мьютекс может обеспечить поочередное выполнение 2 потоков, работающих с общим ресурсом.
Мьютекс по работе = двоичному семафору

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

Слайд 16

Синхронизация. Критические секции
Критическая секция - участок кода, который может одномоментно выполнять

только один поток.
В программах помечается:
вход;
выход.
Критическая секция может обеспечить защищенное изменение глобальных переменных.

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

Слайд 17

Синхронизация. События
Событие - объект, который может быть в состоянии нейтральном или

сигнализирующем.
Поток может ждать сигнала о событии для начала выполнения.
Возможно взаимооповещение потоков (процессов) о событиях.
Рисунки из статьи
http://www.viva64.com/ru/a/0037/
http://www.osp.ru/pcworld/2007/10/4623726/
Игорь Орещенков

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

Слайд 18

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

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

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

Слайд 19

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

Слайд 20

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

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

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

Слайд 21

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

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

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

Слайд 22

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

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

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

Слайд 23

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

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

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

Слайд 24

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

Слайд 25

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

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

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

Слайд 26

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

Слайд 27

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

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

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

Слайд 28

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

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

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

Классификация вычислительных систем

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

Синхронизация. Семафор Семафор – системный объект, с набором методов.В C/C++, C# можно

Синхронизация. Мьютекс Мьютекс – системный объект, с набором методов.В C/C++, C# можно

Синхронизация. Критические секцииКритическая секция - участок кода, который может одномоментно выполнять

Синхронизация. СобытияСобытие - объект, который может быть в состоянии нейтральном или

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Синхронизация. Семафор
Семафор – системный объект, с набором методов.
В C/C++, C# можно

Синхронизация. Мьютекс
Мьютекс – системный объект, с набором методов.
В C/C++, C# можно

Синхронизация. Критические секции
Критическая секция - участок кода, который может одномоментно выполнять

Синхронизация. События
Событие - объект, который может быть в состоянии нейтральном или

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

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

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

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

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

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

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

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

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

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

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