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

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


Вашему вниманию предлагается презентация «Принципы построения параллельных вычислительных систем.», с которой можно предварительно ознакомиться, просмотреть текст и слайды к ней, а так же, в случае, если она вам подходит - скачать файл для редактирования или печати.

Презентация содержит 39 слайдов и доступна для скачивания в формате ppt. Размер скачиваемого файла: 1.07 MB

Просмотреть и скачать

Pic.1
1. Введение в дисциплину Основные понятия. Принципы построения параллельных вычислительных систем. К
1. Введение в дисциплину Основные понятия. Принципы построения параллельных вычислительных систем. Классификация вычислительных систем. Типовые схемы коммуникации в многопроцессорных вычислительных системах.
Pic.2
Структура предметной области (Параллельные вычисления) Математические основы параллельных вычислений
Структура предметной области (Параллельные вычисления) Математические основы параллельных вычислений Архитектура параллельных вычислительных систем Технологии параллельного программирования Параллельные алгоритмы решения задач Параллельные вычисления в конкретных предметных областях
Pic.3
Литература В ИБЦ: Воеводин В. В. Параллельные вычисления. Богачев К. Ю. Основы параллельного програм
Литература В ИБЦ: Воеводин В. В. Параллельные вычисления. Богачев К. Ю. Основы параллельного программирования. Гергель В. П. Теория и практика параллельных вычислений. Учебные курсы Интернет Университета Информационных технологий Гергель В. П. Теория и практика параллельных вычислений. — Основы параллельного программирования с использованием Microsoft Visual Studio 2010. – Барский А. Б. Параллельное программирование. — Интернет-ресурсы:
Pic.4
Что такое параллельные вычисления? Параллельные вычисления – процесс обработки данных, в котором мог
Что такое параллельные вычисления? Параллельные вычисления – процесс обработки данных, в котором могут одновременно выполняться несколько операций вычислительной (компьютерной) системы (ВС). Такие системы называют параллельными вычислительными системами (ПВС). Способы построения и применения ПВС – технологии параллельной обработки данных
Pic.5
Параллельные вычислительные системы Параллельные вычисления – процесс обработки данных, в котором од
Параллельные вычислительные системы Параллельные вычисления – процесс обработки данных, в котором одновременно выполняется более одной операции. ПВС – вычислительная система, включающая не менее двух одновременно работающих обрабатывающих устройств (процессоров) или ядер одного процессора. Процессор – CPU (central processing unit), GPU (graphic processing unit). Ядро (core) – часть процессора, выполняющая один программный поток. Программный поток (thread) – последовательность команд, выполняющаяся независимо от других последовательностей. Каждая программа имеет минимум 1 поток. ОС назначает ресурсы каждому потоку. Поток может создавать другие потоки.
Pic.6
Теоретические и практические проблемы параллельных вычислений Разработка параллельных вычислительных
Теоретические и практические проблемы параллельных вычислений Разработка параллельных вычислительных систем (ПВС) Анализ эффективности параллельных вычислений Разработка обобщенных параллельных алгоритмов решения задач Создание СПО для ПВС Разработка параллельных алгоритмов решения прикладных задач
Pic.7
Показатели производительности параллельного выполнения Ускорение (Speedup) - за счёт параллельного в
Показатели производительности параллельного выполнения Ускорение (Speedup) - за счёт параллельного выполнения программы в N потоках: a(N) = T(1) / T(N) Эффективность (Efficiency) системы, реализующей N потоков E(N) = a(N) / N Масштабируемость (Scalability) системы - возможность ускорения вычислений пропорционально числу потоков, (т. е. линейное ускорение): a(N)=N Суперлинейное ускорение: a(N)>N Часто N связывают с числом процессоров или ядер.
Pic.8
Оценки производительности. Гипотеза Мински. Потери производительности при организации параллелизма Г
Оценки производительности. Гипотеза Мински. Потери производительности при организации параллелизма Гипотеза Марвина Ли Мински (Marvin Lee Minsky, искусственный интеллект, нейронные сети) a=С*log2N, С – коэффициент пропорциональности Пример: a=10 при N=1000, С=1 (не для любых алгоритмов!) НО возможно использование параллелизма на 100%
Pic.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)
Pic.10
Автор закона (конец 1960 г. г. ) – главный разработчик мейнфреймов серии IBM/360 Джин Амдал (Gene Am
Автор закона (конец 1960 г. г. ) – главный разработчик мейнфреймов серии IBM/360 Джин Амдал (Gene Amdahl), основатель Автор закона (конец 1960 г. г. ) – главный разработчик мейнфреймов серии IBM/360 Джин Амдал (Gene Amdahl), основатель Amdahl — американская корпорация, производитель IBM-совместимых серверов. Основана в 1968 году, с 1997 года принадлежит Fujitsu.
Pic.11
Закон Амдала (графики от riki-koen. livejournal. com/75235. html)
Закон Амдала (графики от riki-koen. livejournal. com/75235. html)
Pic.12
р=0. 1, с=0. 001, max=6. 25 (чем меньше с, тем быстрее обмен данными)
р=0. 1, с=0. 001, max=6. 25 (чем меньше с, тем быстрее обмен данными)
Pic.13
Организация параллельных вычислений – возможные режимы Многозадачный режим, или режим разделения вре
Организация параллельных вычислений – возможные режимы Многозадачный режим, или режим разделения времени: Псевдопараллельность – для выполнения нескольких программ используется один процессор  исполняется 1 программа (процесс, задание, задача), прочие – в очереди. Параллельное выполнение: Одномоментное выполнение нескольких команд обработки данных из разных потоков или с разными данными на нескольких процессорах (ядрах). Распределенные вычисления: Параллельное выполнение на удаленных устройствах  Возможны проблемы с обменом данными  Актуальны для специфических задач.
Pic.14
Основные типы ПВС Суперкомпьютер: ВС рекордной производительности, выпускаемая отдельными экземпляра
Основные типы ПВС Суперкомпьютер: ВС рекордной производительности, выпускаемая отдельными экземплярами на оригинальной схемотехнической базе. ВС ценой > млн. ВС, мощность которой только на порядок меньше необходимой для современных задач)). Способы построения и применения СК – технологии высокопроизводительных вычислений (ТВВ) – High Performance Computing (HPC). С 1980 г. г. СК стали ПВС  ТВВ взаимосвязаны с технологиями параллельной обработки данных (иногда синоним)
Pic.15
Основные типы ПВС Кластер – группа выделенных рабочих станций: объединены в ЛВС, эффективно и надежн
Основные типы ПВС Кластер – группа выделенных рабочих станций: объединены в ЛВС, эффективно и надежно работают как единый вычислительный ресурс, используется серийное, типовое оборудование (компьютерное и сетевое). Развитие сетевого оборудования (конец 1990г. г. )  суперкомпьютеры часто строятся по технологии кластеров. Пример – СК - кластер ИМКН: 2 IBM eServer BladeCenter™+ флагманское сетевое оборудование Cisco Systems + хранилище
Pic.16
Классификация ПВС по архитектуре Архитектура ВС - общая логическая организация ВС: определяющая проц
Классификация ПВС по архитектуре Архитектура ВС - общая логическая организация ВС: определяющая процесс обработки данных, включающая архитектуру ЭВМ, структуру и характеристики программного обеспечения, принципы его взаимодействия с аппаратными средствами. Основа классификации – систематика Флинна: анализ взаимодействия потоков выполняемых команд и потоков обрабатываемых данных  вид параллелизма (ПВС)
Pic.17
Основные типы ВС по Флинну (Michael J. Flynn, Таксономия Флинна - 1966 г. )
Основные типы ВС по Флинну (Michael J. Flynn, Таксономия Флинна - 1966 г. )
Pic.18
Основные типы ВС по Флинну SISD (Single Instruction Single Data) – 1 поток команд, 1 поток данных. е
Основные типы ВС по Флинну SISD (Single Instruction Single Data) – 1 поток команд, 1 поток данных. есть только один поток команд, все команды обрабатываются последовательно друг за другом, каждая команда инициирует одну операцию с одним потоком данных П. Стандартный компьютер фон Неймана.
Pic.19
Основные типы ВС по Флинну SIMD (Single Instruction Multiple Data) – 1 поток команд, много потоков д
Основные типы ВС по Флинну SIMD (Single Instruction Multiple Data) – 1 поток команд, много потоков данных. один поток команд, включающий векторные команды, может выполняться одна операция сразу над многими данными - элементами вектора. П1. Компьютер с векторным процессором (операнды – массивы). П2. Специализированные многопроцессорные ВС (одна команда одновременно выполняется с разными данными) для обработки видео, изображений и аудио, для ускорения 3D- и 2D-графики и других мультимедийных задач.
Pic.20
Основные типы ВС по Флинну MISD (Multiple Instruction Single Data) – много потоков команд, 1 поток д
Основные типы ВС по Флинну MISD (Multiple Instruction Single Data) – много потоков команд, 1 поток данных. Отказоустойчивые компьютеры, ВС с систолическим массивом (systolic array) процессоров. MIMD (Multiple Instruction Multiple Data) – много потоков команд, много потоков данных. Большинство многопроцессорных ПВС
Pic.21
Разновидности ВС типа MIMD Дальнейшая классификация ВС – по способам организации оперативной памяти:
Разновидности ВС типа MIMD Дальнейшая классификация ВС – по способам организации оперативной памяти: Мультипроцессоры – ВС с общей, разделяемой между процессорами памятью. Мультикомпьютеры – ВС с распределенной памятью самостоятельных компьютеров, объединенных в сеть (MPP-системы, Massively Parallel Processing).
Pic.22
Мультипроцессоры – способы построения общей памяти Единая общая память с равноправным (однородным) д
Мультипроцессоры – способы построения общей памяти Единая общая память с равноправным (однородным) доступом (Uniform Memory Access, UMA). Используется в ВС на основе: симметричных мультипроцессоров (SMP-системы, Symmetric Multiprocessing) П. IBM eServer, векторных параллельных процессоров, в которых предусмотрены команды однотипной обработки векторов независимых данных (PVP-системы, Parallel Vector Processor)
Pic.23
Архитектура систем UMA
Архитектура систем UMA
Pic.24
Cache memory – кэш-память, кэш: промежуточный буфер с быстрым доступом, содержащий информацию, котор
Cache memory – кэш-память, кэш: промежуточный буфер с быстрым доступом, содержащий информацию, которая может быть запрошена с наибольшей вероятностью. Cache memory – кэш-память, кэш: промежуточный буфер с быстрым доступом, содержащий информацию, которая может быть запрошена с наибольшей вероятностью. Доступ к данным в кэше быстрее, чем выборка исходных данных из оперативной памяти  Уменьшается время доступа к данным  Увеличивается общая производительность ВС. Кэширование применяется жесткими дисками, браузерами, Web-серверами, службами DNS и т. д.
Pic.25
Проблемы UMA Доступ с разных процессоров к общим данным  Необходимо обеспечивать однозначность (ког
Проблемы UMA Доступ с разных процессоров к общим данным  Необходимо обеспечивать однозначность (когерентность) содержимого разных кэшей (cache coherence problem). Решение: уведомление всех процессорных узлов (и кэшей!) об изменении значения в общей памяти
Pic.26
Копии значения переменной x – в разных кэшах  Возможно изменение х одним из процессоров.
Копии значения переменной x – в разных кэшах  Возможно изменение х одним из процессоров.
Pic.27
Проблемы UMA Доступ с разных процессоров к общим данным  Необходимость синхронизации взаимодействия
Проблемы UMA Доступ с разных процессоров к общим данным  Необходимость синхронизации взаимодействия одновременно выполняемых потоков команд (многопоточность) Методы синхронизации: Мьютекс (mutual exclusion, взаимоисключение) Семафор События …
Pic.28
Мультипроцессоры – способы построения общей памяти 2. Физически распределенная общая память с неравн
Мультипроцессоры – способы построения общей памяти 2. Физически распределенная общая память с неравноправным (неоднородным) доступом (Non-Uniform Memory Access, NUMA). Принцип: Блок памяти ↔ процессор (быстрый доступ) «Чужие» блоки ↔ процессор (медленный доступ – до нескольких порядков) – ОСНОВНАЯ ПРОБЛЕМА!
Pic.29
Архитектура систем NUMA
Архитектура систем NUMA
Pic.30
NUMA системы Для данных используются только локальные кэши процессоров – нет общей памяти => нет
NUMA системы Для данных используются только локальные кэши процессоров – нет общей памяти => нет проблемы когерентности (COMA-системы, Cache-Only Memory Architecture) Обеспечена когерентность локальных кэшей (аппаратно) (СС-NUMA-системы, Cache-Coherent) Не обеспечена когерентность локальных кэшей (NСС-NUMA-системы, Non-Cache-Coherent)
Pic.31
Мультикомпьютеры МК – ВС с распределенной памятью самостоятельных компьютеров, объединенных в сеть М
Мультикомпьютеры МК – ВС с распределенной памятью самостоятельных компьютеров, объединенных в сеть МК – системы типа NORMA (No-Remote Memory Access – «нет доступа к удаленной памяти») Архитектура аналогична архитектуре МП с распределенной памятью. НО!: Каждый процессор может использовать только свою локальную память. Для доступа к «чужим» данных д. б. явно выполнены операции передачи сообщений (message passing operations) – 1- или 2-сторонний обмен данными
Pic.32
Основные типы МК – многопроцессорных вычислительных систем Массивно (массово)-параллельные системы,
Основные типы МК – многопроцессорных вычислительных систем Массивно (массово)-параллельные системы, MPP-системы (Massively Parallel Processing – массово-параллельная обработка) Система состоит из однородных узлов (до 103), включающих: один или несколько ЦП (обычно RISC), локальную память (прямой доступ к памяти других узлов невозможен!), коммуникационный процессор или сетевой адаптер жесткие диски и/или другие устройства I/O
Pic.33
Основные типы МК – многопроцессорных вычислительных систем Кластер - набор рабочих станций (или даже
Основные типы МК – многопроцессорных вычислительных систем Кластер - набор рабочих станций (или даже ПК) общего назначения, используется в качестве дешевого варианта МРР-системы. Связь узлов - одна из стандартных сетевых технологий (Fast/Gigabit Ethernet, Myrinet и др. ) на базе шинной архитектуры или коммутатора.
Pic.34
Классификация многопроцессорных ВС (подробно см.
Классификация многопроцессорных ВС (подробно см.
Pic.35
Коммуникация в МВС Коммуникация между процессорами обеспечивает: взаимодействие, синхронизацию, взаи
Коммуникация в МВС Коммуникация между процессорами обеспечивает: взаимодействие, синхронизацию, взаимоисключения выполняемых процессов  Коммуникационная «трудоемкость» алгоритма влияет на выбор способа решения задачи Коммуникация определяется топологией сети – схемой расположения и соединения сетевых устройств.
Pic.36
Примеры топологий сетей в МВС
Примеры топологий сетей в МВС
Pic.37
Особенности топологий сетей передачи данных Тип - Преимущества - Реализация Полный граф – минимум за
Особенности топологий сетей передачи данных Тип - Преимущества - Реализация Полный граф – минимум затрат на передачу данных - - (кластер с соединением CPU через свитч с ограничением: только одна одномоментная операция приема-передачи данных для каждого процессора  взаимодействующие пары CPU не должны пересекаться). Линейка – идеально для конвейерных вычислений - + Кольцо - ? - + Звезда – для централизованных схем вычислений - + Решетка (2D, 3D) - + - +
Pic.38
Характеристики топологий сети Диаметр – определяет время передачи данных через max расстояние между
Характеристики топологий сети Диаметр – определяет время передачи данных через max расстояние между 2 CPU сети (расстояние равно величине кратчайшего пути). Связность – определяет наличие разных маршрутов передачи данных между CPU, min число дуг графа, которые надо удалить для получения 2 несвязных областей. Ширина бисекции – связность, но 2 области д. б. одинакового размера Стоимость – общее число линий передачи данных в МВС
Pic.39
Характеристики топологий (р – количество процессоров)
Характеристики топологий (р – количество процессоров)


Скачать презентацию

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