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

1.

ВВОДНАЯ ЛЕКЦИЯ.
ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ
ПРОЦЕССЫ И
СИСТЕМЫ
Д.т.н. , с.н.с. Толстолужская Е.Г.

2. Структура курса:

Тема 1. Архитектура и функционирование
параллельных процессоров и
многопроцессорных систем.
Тема 2. Автоматизация проектирования
параллельных программ.
Тема 3. Методы параллельной обработки
данных.

3.

Модуль 1. Архітектура та функціонування сучасних паралельних процесорів та багатопроцесорних систем.
Тема 1. Класифікація паралельних процесорів. Архитектура та функціонування суперскалярних процесорів.
Тема 2. Паралельні архитектури. Класифікація паралельних систем по Флінну.
Тема 3. Архітектура і функціонування паралельних процесорів з довгим командним словом VLIW.
Тема 4. Архітектура і функціонування паралельних процесорів з управлінням потоком даних.
Тема 5. Багатопроцесорні ЕОМ з розділяємою пам`яттю. Багатомашинні системи.
Модуль 2. Автоматизація проектування паралельних програм.
Тема 1. Класифікація паралельних програм. Особливості програмування паралельних обчислювань.
Тема 2. Основні напрямки рішення проблем паралельного програмування.
Тема 3. Введення в паралельне програмування з використанням MPI («Інтерфейс Передачі Повідомлень»).
Тема 4. Обмін даними в MPI. Колективний обмін даними в MPI.
Тема 5. Введення в паралельне програмування з використанням PVM (Parallel Virtual Machine).
Програмування з використанням PVM.
Модуль 3. Методи паралельної обробки даних.
Тема 1. Вступ. Загальні відомості про паралельні обчислювальні процеси та системи.
Тема 2. Статичні та часові паралельні алгоритми і процеси.
Тема 3. Часові паралельні алгоритми.
Тема 4. Показники ефективності паралельної реалізації алгоритмів та їх зв`язок з вимогами
практики.
Тема 5. Метод суміщення незалежних операцій. Метод формального синтеза паралельних
часових моделей алгоритму.

4. Литература:

1.
Гергель, В.П., Стронгин, Р.Г. (2003, 2 изд.). Основы параллельных
многопроцессорных вычислительных систем. - Н.Новгород, ННГУ.
вычислений
для
2.
Воеводин В.В., Воеводин Вл.В. (2002). Параллельные вычисления. – СПб.: БХВ-Петербург.
3.
Немнюгин С. (2009). Модели и средства программирования для многопроцессорных систем– СПб.:
БХВ-Петербург.
4.
Хьюз К., Хьюз Т.(2004). Параллельное и распределенное программирование на С++.: Пер. с англ. –
М.: Издательский дом «Вильямс», 2004. – 672с.
5.
Поляков Г.А., Шматков С.И., Толстолужская Е.Г., Толстолужский Д.А. (2012). Синтез и анализ
параллельных процессов в адаптивных времяпараметризованных вычислительных системах. – Х.:
ХНУ имени В.Н. Каразина, 2012.-672с.
6.
Grama, A., Gupta, A., Kumar V. (2003, 2nd edn.). Introduction to Parallel Computing. – Harlow, England:
Addison-Wesley.
7.
Quinn, M. J. (2004). Parallel Programming in C with MPI and OpenMP. – New York, NY: McGraw-Hill.
8.
Parallel Programming in OpenMP. Morgan Kaufmann Publishers.
9.
Culler, D., Singh, J.P., Gupta, A. (1998) Parallel Computer Architecture: A Hardware/Software Approach. Morgan Kaufmann.
10.
Tanenbaum, A. (2001). Modern Operating System. 2nd edn. – Prentice Hall (русский перевод Таненбаум
Э. Современные операционные системы. – СПб.: Питер, 2002)

5.

6.

Руководители проекта Top500 представили очередной
рейтинг самых мощных в мире суперкомпьютеров. Список
систем в порядке убывания быстродействия приводится на
сайте top500.org.
Tianhe-2, расположенная в
Национальном суперкомпьютерном центре в
Тянжине
в
Китае,
максимальная
производительность которой составляет 33,86
Пфлоп/с
Tianhe-2 (MilkyWay-2) : National University of Defense
Первое место заняла
Technology
No. 1 system since June 2013
Tianhe-2, a supercomputer developed by China’s National University
of Defense Technology, retains its position as the world’s No. 1
system with a performance of 33.86 petaflop/s (quadrillions of
calculations per second) on the Linpack benchmark. It was built by
China's National University of Defense Technology (NUDT) in
collaboration with the Chinese IT firm Inspur.
According to NUDT, Tianhe-2 will be used for simulation, analysis,
and government security applications. With 16,000 computer nodes,
each comprising two Intel Ivy Bridge Xeon processors and
three Xeon Phi chips, it represents the world's largest installation of
Ivy Bridge and Xeon Phi chips, counting a total of 3,120,000 cores.
[3] Each of the 16,000 nodes possess 88 gigabytes of memory (64
used by the Ivy Bridge processors, and 8 gigabytes for each of the
Xeon Phi processors). The total CPU plus coprocessor memory is
1,375 TiB (approximately 1.34 PiB). MPI: MPICH2.

7.

Titan: Oak Ridge National Laboratory
No. 1 system in November 2012
When the 40th edition of the list was released at the start of SC12, the No. 1
position was claimed by Titan, a 552,960 processor system with a Linpack
performance of 17.6 petaflop/s. Oak Ridge National Laboratory's Titan is a
Cray XK7 system that relies on a combination of GPUs and traditional
CPUs to make it the world's most powerful supercomputer. Each of Titan's
18,688 nodes contains an NVIDIA Tesla K20 GPU along with a 16-core
AMD Opteron 6274 CPU processor, giving the system a peak performance
of more than 27 petaflops. Titan also has more than 700 terabytes of
memory.
Titan's use of GPUs also points the way for future scientific
supercomputers. Because GPUs provide high-performance and energyefficient computing power, they will allow supercomputing systems to
become ever more powerful while avoiding the obstacles inherent in
growing size and power consumption.
Пользователи - Бостонский
Области применения:
•медико биологические науки;
• финансовое моделирование;
• гидродинамика;
• квантовая химия;
• молекулярная динамика;
•астрономия и космические
исследования.
университет, Нидерландский фонд
астрономических исследований
(ASTRON), японский Институт перспективных
научных и технологических исследований
(AIST), компания NIWS (Япония),
Национальный центр атмосферных
исследований США (NCAR), Эдинбургский
университет, Суперкомпьютерный центр в
Сан-Диего, Аргоннская национальная
лаборатория, Федеральный политехнический
институт в Лозанне (EPFL) и центр IBM Deep
Computing Capacity on Demand

8.

Blue Gene "по требованию"
Центр высокопроизводительных вычислений "по
требованию" IBM (Deep Computing Capacity on
Demand Center) в Рочестере (шт. Миннесота)
впервые в истории предоставил заказчикам и
партнерам IBM дистанционный доступ к системе
Blue Gene через выделенную сеть VPN с высокой
степенью защиты, причем пользователь
Blue Gene: цифровая модель мозга
оплачивает только заказанные им системные
В июне 2005 г. корпорация IBM и Федеральный
ресурсы.
политехнический институт в Лозанне
Blue Gene: исследования климата и погоды
Национальный центр атмосферных исследований США
(NCAR) и университет Колорадо приобрели суперкомпьютер
IBM Blue Gene, который планируется использовать для
имитационного моделирования океанических, погодных и
климатических явлений, оказывающих влияние на
сельскохозяйственное производство, цены на топливо
коммунально-бытового назначения и глобальное потепление.
представили крупномасштабную совместную
исследовательскую инициативу Blue Brain
Project, призванную поднять на новый уровень
исследования мозга. Используя
вычислительные мощности суперкомпьютера
IBM Server Blue Gene, создается детальная
модель нейронной структуры неокортекса,
самой большой и сложной части коры
головного мозга человека. Постепенно включая
в проект моделирование других частей мозга,
ученые в конечном счете надеются построить
Моделирование автомобильных аварий
Volvo Car Corporation выбрала IBM в качестве поставщика
суперкомпьютера, предназначенного для проведения важнейших
модельных расчетов автомобильных аварий. IBM предоставляет
как оборудование, так и услуги для реализации концепции
"безопасного проектирования", которой придерживается этот
автомобильный концерн.

9.

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

10.

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

11.

Типичная архитектура построения параллельной и
распределенной программ

12.

ПРЕИМУЩЕСТВА ПАРАЛЛЕЛЬНОГО
ПРОГРАММИРОВАНИЯ
Программы, надлежащее качество проектирования которых позволяет
воспользоваться преимуществами параллелизма, могут выполняться
быстрее, чем их последовательные эквиваленты, что повышает их
рыночную стоимость. Иногда скорость может спасти жизнь. В таких
случаях быстрее означает лучше. Иногда решение некоторых проблем
представляется естественнее в виде коллекции одновременно выполняемых
задач. Это характерно для таких областей, как научное программирование,
математическое и программирование искусственного интеллекта. Это
означает, что в некоторых ситуациях технологии параллельного
программирования снижают трудозатраты разработчика ПО, позволяя ему
напрямую реализовать структуры данных, алгоритмы и эвристические
методы,
разрабатываемые
учеными.
При
этом
используется
специализированное оборудование.
Применение
более
совершенных
технологий
параллельного
программирования открывает двери к архитектурам ПО, которые
специально разрабатываются для параллельных сред. Например,
существуют специальные мультиагентные архитектуры и архитектуры,
использующие методологию "классной доски", разработанные специально
для среды с параллельными процессорами.

13.

Простейшая модель параллельного программирования
(PRAM)
В качестве простейшей модели, отражающей базовые концепции
параллельного программирования, рассмотрим модель PRAM (Parallel
Random Access Machine — параллельная машина с произвольным
доступом). PRAM — это упрощенная теоретическая модель с и
процессорами, которые используют общую глобальную память.
Простая модель PRAM изображена на рис. 1.2.

14.

Все процессоры имеют доступ для чтения и записи к общей
глобальной памяти. В PRAM-среде возможен одновременный доступ.
Предположим, что все процессоры могут параллельно выполнять
различные арифметические и логические операции.
Кроме того, каждый из теоретических процессоров (см. рис. 1.2)
может обращаться к общей памяти в одну непрерываемую единицу
времени. PRAM-модель обладает как параллельными, так и
исключающими алгоритмами считывания данных.
Параллельные алгоритмы считывания данных позволяют
одновременно обращаться к одной и той же области памяти без
искажения (порчи) данных. Исключающие алгоритмы считывания
данных используются в случае, когда необходима гарантия того, что
никакие два процесса никогда не будут считывать данные из одной и той
же области памяти одновременно. PRAM- модель также обладает
параллельными и исключающими алгоритмами записи данных.
Параллельные алгоритмы позволяют нескольким процессам
одновременно записывать данные в одну и ту же область памяти, в то
время как исключающие алгоритмы гарантируют, что никакие два
процесса не будут записывать данные в одну и ту же область памяти
одновременно.

15.

Таблица 1.1. Четыре базовых алгоритма считывания и записи
данных
Типы алгоритмов
Описание
EREW
Исключающее
считывание/исключающая запись
CREW
Параллельное
считывание/исключающая запись
ERCW
Исключающее
считывание/параллельная запись
CRCW
Параллельное
считывание/параллельная запись
Необходимо отметить, что хотя PRAM — это упрощенная теоретическая модель, она успешно
используется для разработки практических программ, и эти программы могут соперничать по
производительности с программами, которые были разработаны с использованием более сложных
моделей параллелизма.

16.

Преимущества распределенного программирования
Методы
распределенного
программирования
позволяют
воспользоваться преимуществами ресурсов, размещенных в Internet, в
корпоративных Intranet и локальных сетях.
Распределенное программирование обычно включает сетевое
программирование в той или иной форме. Это означает, что программе,
которая выполняется на одном компьютере в одной сети, требуется
некоторый аппаратный или программный ресурс, который принадлежит
другому компьютеру в той же или удаленной сети.
Распределенное
программирование подразумевает общение одной программы с другой
через сетевое соединение, которое включает соответствующее
оборудование (от модемов до спутников). Отличительной чертой
распределенных программ является то, что они разбиваются на части.
Эти части обычно реализуются как отдельные программы, которые, как
правило, выполняются на разных компьютерах и взаимодействуют друг с
другом через сеть.
Методы распределенного программирования предоставляют
доступ к ресурсам, которые географически могут находиться на большом
расстоянии друг от друга.

17.

Простейшие модели распределенного программирования
модель типа "клиент/сервер".
Самой простой и распространенной моделью распределенной
обработки данных является модель типа "клиент/сервер". В этой модели
программа разбивается на две части: одна часть называется сервером, а
другая — клиентом. Сервер имеет прямой доступ к некоторым
аппаратным и программным ресурсам, которые желает использовать
клиент.
В большинстве случаев сервер и клиент располагаются на
разных компьютерах. Обычно между клиентом и сервером существует
отношение типа "множество-к-одному", т.е., как правило, один сервер
отвечает на запросы многих клиентов.
Сервер часто обеспечивает опосредованный доступ к огромной
базе данных, дорогостоящему оборудованию или некоторой коллекции
приложений. Клиент может запросить интересующие его данные, сделать
запрос на выполнение вычислительной процедуры или обработку другого
типа.
Несмотря на то что клиент и сервер представляют собой
отдельные программы, выполняющиеся на разных компьютерах, вместе
они составляют единое приложение. Разделение ПО на части клиента и
сервера и есть основной метод распределенного программирования.

18.

Мультиагентные распределенные системы
Агенты — рациональные компоненты ПО, которые характеризуются
самонаведением и автономностью и могут постоянно находиться в
состоянии выполнения. Агенты могут как создавать запросы к другим
программным компонентам, так и отвечать на запросы, полученные от
других программных компонентов. Агенты сотрудничают в пределах групп
для коллективного выполнения определенных задач. В такой модели не
существует конкретного клиента или сервера. Это — модель сети с
равноправными узлами (peer-to-peer), в которой все компоненты имеют
одинаковые права, и при этом у каждого компонента есть что предложить
другому.
Агенты являются распределенными, поскольку все они
размещаются на разных серверах в Internet. Для связи агенты используют
согласованный Internet-протокол. Для одних типов распределенного
программирования лучше подходит модель типа "клиент/сервер", а для
других — модель равноправных агентов.

19.

20.

ОСНОВНЫЕ КЛАССЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ
СРЕДСТВ
Классы параллельных
вычислительных средств
Универсальные
процессоры
а) скалярные и суперскалярные процессоры;
б) параллельные процессоры / ЭВМ с
управлением потоком
данных;
в) процессоры с длинным
командным словом ,
VLIW.
Многопроцессорные
ЭВМ
а) с симметричной мультипроцессорной
обработкой (SMP, NUMA);
б) с массово-параллельной
обработкой (МРР);
в) многопроцессорные
кластерные системы
(CLUSTER).
Параллельные
спецпроцессоры
а) аппаратные с жесткой
структурой;
б) аппаратные с перестраиваемой структурой;
в) программно управляемые контроллеры.

21.

Особенности скалярных и суперскалярных процессоров
организация вычислительного процесса в виде одной нити (в скалярных
процессорах) или нескольких одновременно (параллельно) выполняемых нитей (в
суперскалярных процессорах);
реализация нитей на основе метода конвейерной обработки данных.
«Нить» (thread) – неразветвляющаяся последовательность операций/машинных
Особенности параллельных процессоров с длинным командным словом
команд.
(Very
Long Instruction Word, VLIW):
•разбиение
множества команд программы на фрагменты независимых команд,
реализация которых может начинаться в один и тот же момент времени;
•представление
каждого фрагмента
в виде длинной команды и оформление
параллельной программы в виде последовательности «длинных команд»;

22.

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

23.

24.

Эффективность вычислительной системы - способность системы обеспечивать решение задачи
(множества задач) c удовлетворением предъявленной системе требований/ ограничений и достижением
определенных качественных и количественных пользовательских эффектов.
Потенциальная эффективность ВС - способность выполнять решение задач «наилучшим образом»,
понимая под этим максимально возможное приближение к некоторому теоретическому (потенциально
возможному) пределу.
Реальная эффективность определяется количеством стандартных прикладных задач, решение
которых обеспечивает компьютер на заданном интервале времени.
Основные пути повышения эффективности ВС
разработка новой элементной базы с
использование параллельной
улучшенными характеристиками
обработки информации при
создании и применении
высокоинтеллектуальных

25.

ЦЕНТРАЛЬНАЯ ПРОБЛЕМА
современной вычислительной техники - повышение эффективности и расширение
областей применения ЭВМ.
ОСНОВНОЙ ПУТЬ РАЗРЕШЕНИЯ – параллельное решение задач.
ОБЪЕКТИВНЫЕ ПОСЛЕДСТВИЯ усложнение архитектуры параллельных
ЭВМ, рост интеллектуальной сложности и
размерности задач проектирования
аппаратных средств, рост интеллектуальной
сложности и размерности задач
параллельного программирования,
увеличение вероятности получения
неоптимальных аппаратно-программных
продуктов.
НЕЖЕЛАТЕЛЬНЫЕ
РЕЗУЛЬТАТЫ - возможность
снижения эффективности
параллельных ЭВМ, усложнение
применения ЭВМ и ограничения
на области эффективного
использования параллельных
ЭВМ.
ВЫХОД ИЗ ПРОТИВОРЕЧИЯ создание и применение
Самоорганизующихся
Вычислительных Систем, способных
автоматически, средствами самой
системы, целенаправленно изменять
архитектуру параллельных
аппаратно-программных средств,
характеристики и функционирование при изменении областей
применения, требований и
решаемых задач.

26. ЗАКОНЫ АМДАЛА

Пусть пиковая производительность однопроцессорной системы равна Т1 , тогда пиковая
производительность системы, состоящей из р таких процессоров, увеличивается в р раз, Т=
рТ1 .
Ускорением параллельной системы R назовем отношение ее производительности к
производительности соответствующей однопроцессорной системы. Тогда пиковое ускорение
ПервыйR=T/T1=p.
закон Амдала.
Производительность вычислительной системы, состоящей из нескольких
связанных между собой устройств, определяется самым непроизводительным
устройством.
Второй закон Амдала.
Пусть вычислительная система состоит из р процессоров. Предположим, что k
из
k/N
N операций алгоритма могут выполняться только последовательно. Пусть
0 1
- доля последовательных операций в алгоритме,
1
R возможное ускорение системы
Тогда максимально
(1 ) / p
.

27.

КОНЦЕПЦИИ ПОСТРОЕНИЯ САМООРГАНИЗУЮЩИХСЯ
ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
Мультипараллельность - применение всех или части
известных методов параллельной обработки данных
с автоматической оптимизацией их состава для
конкретных областей применения, решаемых задач и
требований пользователей.
Автоматический аппаратно-программный
компромисс- решение задачи выбора
оптимального соотношения аппаратных и
•.
программных средств
Адаптивность - обеспечение высокой
эффективности при изменении областей
применения, решаемых задач и требований, а
также при отказах и сбоях.
Самоорганизующийся элементный базис - на основе
динамически программируемых, перестраиваемых и
самоорганизующихся СБИС.
Самоорганизация параллельного аппаратнопрограммного обеспечения - автоматическое
проектирование новых архитектур параллельных
аппаратных и программных средств

28.

29.

МЕТОДЫ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ДАННЫХ
Методы параллельной цифровой
обработки информации
Совмещени
е операций
Конвейерны
й метод
задачи
Кодовоматричны
й метод
Декомпози
-ционный
метод
Метод параллельной
смеси задач
Эффекты от применения методов
параллельной обработки
Время
решения задач,
быстродействие
Тактовая
частота, производительность
Надежность,
достоверность,
живучесть
Сложность/
стоимость

30.

Метод совмещения независимых операций (СО) направлен на уменьшение времени решения задач
за счет совмещения выполнения независимых (по данным и по управлению) операций/функций.
Метод
обеспечивает
возможности
увеличения
быстродействия
и
производительности
вычислительных систем.
Кодово-матричный метод (КМ) обеспечивает уменьшение времени решения задач и увеличение тактовой
частоты обработки данных (за счет уменьшения времени выполнения операций/функций при переходе к
представлению обрабатываемых данных двух - многорядными кодами или кодовыми матрицами).
Применение этого метода обеспечивает повышение быстродействие и производительность ВС.
Метод конвейерной обработки (КО) обеспечивает увеличение тактовой частоты обработки данных за счет
разделения задачи на фрагменты и временного совмещения
выполнения различных фрагментов,
относящихся к различным смежным наборам входных данных задачи; одновременно с этим возрастает
время решения задачи для каждого конкретного набора входных данных
Декомпозиционный метод (ДК) обеспечивает возможности дальнейшего (по сравнению с конвейерной
обработкой) увеличения тактовой частоты за счет частичного временного совмещения процессов
конвейерной обработки ряда смежных наборов входных данных задачи
Метод смеси алгоритмов (СА) обеспечивает возможность достижения 100% - ой загрузки оборудования за
счет одновременной реализации подмножеств операций/функций, относящихся к различным алгоритмам
смеси совместно выполняемых задач.

31.

t1
t2
t3
t4
t5
+
1
+
2
*
3
*
4
/
5
t1
A
B
C
D
M
N
K
L
+
1
+
2
*
4
/
5
t2
t3
t6
t7
6
/
7
t8
а)
Y
Время t
t4
*
3
/
7
б)
Y
6
Время t
Последовательный (а) и параллельный (б) графы решения задачи,
иллюстрирующие метод совмещения независимых операций

32.

МЕТОДЫ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ДАННЫХ
Методы параллельной
обработки данных
Совмещение
операций
Конвейерный
метод
Кодово–
матричный
метод
ТА
Алгоритм 1
Метод смеси
алгоритмов
ТА
ФА 1’ ФА 1’’
ТА
…
Декомпозиционный метод
Алгоритм K
t
Время решения ТА(K)=K ТА
Т
ФА 2’ ФА 2’’
Т
ФА j’ ФА j’’
Т
ФА k’ ФА k’’
Фрагменты
алгоритмов
операций
t
Время решения
ТКОН(K)=ТА+(K-1) T
Последовательное выполнение алгоритмов
Конвейерное выполнение алгоритмов