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

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

2-е издание, исправленное

Гергель В.П.

Национальный Открытый Университет “ИНТУИТ”
2016

2

УДК 004.42.032.24(07)
ББК 16
Г37
Теория и практика параллельных вычислений / Гергель В.П. - M.: Национальный Открытый
Университет “ИНТУИТ”, 2016 (Основы информационных технологий)
ISBN 978-5-94774-645-7

Учебное пособие содержит материал, для работы в области параллельного программирования.
Дается краткая характеристика принципов построения параллельных вычислительных систем,
рассматриваются математические модели параллельных алгоритмов и программ для анализа
эффективности параллельных вычислений, приводятся примеры конкретных параллельных методов
для решения типовых задач вычислительной математики. Рекомендовано Советом учебнометодическим объединением классических университетов России по прикладной математике и
информатике.

(c) ООО “ИНТУИТ.РУ”, 2007-2016
(c) Гергель В.П., 2007-2016

3

Введение

Применение параллельных вычислительных систем (ПВС) является стратегическим
направлением развития вычислительной техники. Это обстоятельство вызвано не
только принципиальным ограничением максимально возможного быстродействия
обычных последовательных ЭВМ, но и практически постоянным наличием
вычислительных задач, для решения которых возможностей существующих средств
вычислительной техники всегда оказывается недостаточно. Так, проблемы “большого
вызова” [54] возможностям современной науки и техники: моделирование климата,
генная инженерия, проектирование интегральных схем, анализ загрязнения
окружающей среды, создание лекарственных препаратов и др. - требуют для своего
анализа ЭВМ с производительностью более 1000 миллиардов операций с плавающей
запятой в секунду (1 TFlops).

Проблема создания высокопроизводительных вычислительных систем относится к
числу наиболее сложных научно-технических задач современности. Ее разрешение
возможно только при всемерной концентрации усилий многих талантливых ученых и
конструкторов, предполагает использование всех последних достижений науки и
техники и требует значительных финансовых инвестиций. Тем не менее достигнутые в
последнее время успехи в этой области впечатляют. Так, в рамках принятой в США в
1995 г. программы “Ускоренной стратегической компьютерной инициативы”
(Accelerated Strategic Computing Initiative – ASCI) [25] была поставлена задача
увеличения производительности суперЭВМ в 3 раза каждые 18 месяцев и достижение
уровня производительности в 100 триллионов операций в секунду (100 TFlops) в 2004
г. Одной из наиболее быстродействующих супер-ЭВМ в настоящее время является
компьютер SX-6 японской фирмы NEC с быстродействием одного векторного
процессора порядка 8 миллиардов операций в секунду (8 GFlops). Достигнутые
показатели быстродействия для многопроцессорных систем гораздо выше: например,
система ASCI Red фирмы Intel (США, 1997) имеет предельную (пиковую)
производительность 1,8 триллионов операций в секунду (1,8 TFlops). Список наиболее
быстродействующих вычислительных систем Top 500 на момент издания данного
курса лекций возглавляет вычислительный комплекс BlueGene/L, содержащий более 64
тысяч процессоров (!) с общей суммарной пиковой производительностью более чем
380 TFlops.

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

Однако следует отметить, что до сих пор применение параллелизма не получило столь
широкого распространения, как это ожидалось многими исследователями. Одной из

4

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

Другая и, пожалуй, теперь основная причина сдерживания массового распространения
параллелизма состоит в том, что для проведения параллельных вычислений
необходимо “параллельное” обобщение традиционной - последовательной технологии решения задач на ЭВМ. Так, численные методы в случае
многопроцессорных систем должны проектироваться как системы параллельных и
взаимодействующих между собой процессов, допускающих исполнение на
независимых процессорах. Применяемые алгоритмические языки и системное
программное обеспечение должны обеспечивать создание параллельных программ,
организовывать синхронизацию и взаимоисключение асинхронных процессов и т.п.

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

Потери производительности для организации параллелизма - согласно гипотезе
Минского (Minsky), ускорение, достигаемое при использовании параллельной
системы, пропорционально двоичному логарифму от числа процессоров (т.е. при
1000 процессорах возможное ускорение оказывается равным 10).

Комментируя данное высказывание, можно отметить, что, безусловно, подобная
оценка ускорения справедлива при распараллеливании определенных алгоритмов.
Вместе с тем существует большое количество задач, при параллельном решении
которых достигается практически 100%-е использование всех имеющихся процессоров
параллельной вычислительной системы.

Существование последовательных вычислений - в соответствии с законом Амдаля
(Amdahl) ускорение процесса вычислений при использовании p процессоров
ограничивается величиной

где f есть доля последовательных вычислений в применяемом алгоритме
обработки данных (т.е., например, при наличии всего 10% последовательных
команд в выполняемых вычислениях эффект использования параллелизма не
может превышать 10-кратного ускорения обработки данных).

Данное замечание характеризует одну из самых серьезных проблем в области

5

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

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

Для ответа на данное замечание следует отметить, что “однородность”
последовательных ЭВМ также является кажущейся и эффективное использование
однопроцессорных компьютеров тоже требует учета свойств аппаратуры. С другой
стороны, при всем разнообразии архитектур параллельных систем, тем не менее,
существуют и определенные “устоявшиеся” способы обеспечения параллелизма
(конвейерные вычисления, многопроцессорные системы и т.п.). Кроме того,
инвариантность создаваемых параллельных программ может быть обеспечена и при
использовании типовых программных средств поддержки параллельных вычислений
(программных библиотек MPI, PVM и др.).

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

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

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

6

современного специалиста по прикладной математике, информатике и вычислительной
технике.

Проблематика параллельных вычислений является чрезвычайно широкой областью
теоретических исследований и практически выполняемых работ и обычно
подразделяется на следующие направления деятельности:

разработка параллельных вычислительных систем – обзор принципов построения
параллельных систем приведен в лекции 1 данного курса лекций; дополнительная
информация по данному вопросу может быть получена в [11, 14, 16, 24, 28, 29, 47,
59, 76, 77];
анализ эффективности параллельных вычислений для оценки получаемого
ускорения вычислений и степени использования всех возможностей
компьютерного оборудования при параллельных способах решения задач –
вопросы данного направления работ рассматриваются в лекции 2 (анализ
эффективности организации процессов передачи данных как одной из важных
составляющих параллельных вычислений выполняется отдельно в лекции 3);
проблема анализа эффективности параллельных вычислений широко обсуждается
в литературе – см., например, [2, 7, 8, 22, 77];
формирование общих принципов разработки параллельных алгоритмов для
решения сложных вычислительно трудоемких задач – возможная практическая
методика получения параллельных вычислительных схем приводится в Лекции 4;
при рассмотрении данной важной темы может оказаться полезным материал,
излагаемый в [2, 32, 63];
создание и развитие системного программного обеспечения для параллельных
вычислительных систем – в лекции 5 описывается стандарт MPI ( Message Passing
Interface ), программные реализации которого позволяют разрабатывать
параллельные программы и, кроме того, снизить в значительной степени остроту
важной проблемы параллельного программирования – обеспечение мобильности
(переносимости между разными вычислительными системами) создаваемого
прикладного программного обеспечения. Дополнительные сведения в этой
области параллельных вычислений могут быть получены, например, в [4, 12, 27,
35, 40 – 42, 57, 63, 69]. Следует отметить, что использование MPI-библиотек для
разработки параллельных программ является практически общепринятой
технологией параллельного программирования для вычислительных систем с
распределенной памятью;
создание и развитие параллельных алгоритмов для решения прикладных задач в
разных областях практических приложений – примеры подобных алгоритмов
приведены в лекциях 6 – 11 данного курса; более широко сведения о
существующих параллельных методах вычислений для различных классов задач
представлены в [2, 5, 17, 22, 32, 33, 51, 62, 63, 66, 75, 77]; в этих же лекциях
рассмотрены возможные программные реализации рассматриваемых алгоритмов.

В завершение учебного материала в лекции 12 проводится рассмотрение учебноисследовательской программной системы Параллельная Лаборатория ( ПараЛаб ),
которая может быть использована для организации лабораторного практикума по
данному курсу для изучения и исследования эффективности параллельных алгоритмов.

7

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

В основе настоящего учебника лежит лекционный материал учебного курса
“Многопроцессорные вычислительные системы и параллельное программирование”,
который читается с 1996 г. в Нижегородском государственном университете на
факультете вычислительной математики и кибернетики для студентов, обучаемых по
специальности “Прикладная математика и информатика” и новому направлению
подготовки “Информационные системы”.

Часть необходимого теоретического материала была подготовлена во время научных
стажировок в университете г.Трир (Германия, декабрь 1996 г. - январь 1997 г.),
университете г.Роскильде и Датском техническом университете (Дания, май 2000 г.),
университете г.Делфт (октябрь 2005 г.), университете штата Северная Каролина (США,
октябрь – декабрь 2006 г.). Вычислительные эксперименты, необходимость которых
возникала при подготовке пособия, были выполнены на высокопроизводительном
вычислительном кластере Нижегородского университета (оборудование кластера
поставлено в ННГУ в рамках Академической программы компании Intel в 2001 г.,
описание состава и показатели производительности кластера приводятся в лекции 1
учебного курса).

Значительная часть работ по развитию учебно-методического и программного
обеспечения данного курса была проведена в 2002 – 2005 гг. в учебноисследовательской лаборатории “Информационные технологии” (ИТЛаб), созданной в
Нижегородском университете при поддержке компании Интел.

Подготовка публикуемого варианта учебных материалов была выполнена в 2005 – 2006
гг. в рамках учебно-исследовательского проекта, который был поддержан компанией
Майкрософт, по созданию учебно-методического обеспечения
высокопроизводительных кластеров, функционирующих под управлением недавно
разработанной системы Microsoft Compute Cluster Server.

Для проведения занятий по курсу “Многопроцессорные вычислительные системы и
параллельное программирование” были подготовлены электронные презентации,
содержание которых представлено на сайте (ссылка:
http://www.software.unn.ac.ru/ccam/?doc=98).

Данный вариант учебного курса является расширенной и переработанной версией
учебного пособия, опубликованного в Нижегородском университете в 2001 г. (второе
издание пособия было опубликовано в 2003 г.). За прошедший период учебный курс
активно использовался в разных формах подготовки и переподготовки кадров в
области современных компьютерных технологий более чем в 20 вузах страны.
Материалы учебного курса применялись в проводимых в Нижегородском университете
при поддержке компании Интел в 2004 – 2006 гг. Зимних школах по параллельному
программированию.

8

Разработанные учебные материалы послужили для компании Майкрософт одной из
важных причин выделения Нижегородского госуниверситета в числе 10 лучших
университетов мира в области высокопроизводительных вычислений.

Автор данного курса лекций считает своим приятным долгом выразить благодарность
за совместную успешную работу и дружескую поддержку своим коллегам –
преподавателям кафедры математического обеспечения ЭВМ факультета
вычислительной математики и кибернетики Нижегородского госуниверситета. Автор
глубоко признателен Л.В.Нестеренко (Интел), ценные замечания которой значительно
способствовали улучшению разрабатываемых учебных материалов. И, безусловно,
настоящее издание было подготовлено только благодаря неизменной дружеской
поддержке К.Фаенова (Майкрософт) и И.Р.Агамирзяна (Майкрософт).

9

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

Лекция посвящена рассмотрению принципов построения параллельных
вычислительных систем (ПВС). Дана краткая характеристика способов достижения
параллелизма, приведены примеры ПВС. Приводится классификация параллельных
вычислительных систем, рассматриваются типовые топологии сетей передачи данных
в ПВС

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

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

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

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

- дублирование устройств ЭВМ путем использования, например, нескольких
однотипных обрабатывающих процессоров или нескольких устройств оперативной
памяти.

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

Возможные пути достижения параллелизма детально рассматриваются в [2, 11, 14, 28,
45, 59]; в этих же работах описывается история развития параллельных вычислений и
приводятся примеры конкретных параллельных ЭВМ (см. также [24, 76]).

При рассмотрении проблемы организации параллельных вычислений следует
различать следующие возможные режимы выполнения независимых частей
программы:

многозадачный режим ( режим разделения времени ), при котором для

10