Введение в параллельные методы решения задач

Серия
Суперкомпьютерное 
Образование

Координационный совет
Системы научно-образовательных центров
суперкомпьютерных технологий

Председатель Координационного совета
В. А.  Садовничий,
ректор МГУ имени М. В.  Ломоносова,
академик

Заместители председателя совета
Е. И.  Моисеев,
декан факультета вычислительной математики и кибернетики
МГУ имени М. В.  Ломоносова, 
академик

А. В.  Тихонравов,
директор Научно-исследовательского вычислительного центра
МГУ имени М. В.  Ломоносова, 
профессор

Члены совета

В. Н. Васильев, ректор Санкт-Пе тер  бургского национального исследовательского госу дар ственного университета инфор ма ционных технологий, механики 
и оптики, чл.-корр. РАН, профессор; В. Г. Захаревич, ректор Южного федерального университета, профессор; Н. Н. Кудрявцев, ректор Московского физико-технического института, чл.-корр. РАН, профессор; Г. В. Майер, 
ректор национального исследовательско го Томско го государственного университета, профессор; А. А. Фаткулин, проректор по науке и инновациям 
Дальневосточного федерального университета, профессор; Е. В. Чупрунов, 
ректор националь ного исследовательского Ниже городского го су дарственного 
университета, про фессор; А. Л. Шестаков, ректор национального исследовательского Южно- Уральского государственного университета, профессор; 
В. Н. Чубариков, декан механико-математического факультета МГУ имени 
М. В. Ломоносова, профессор; М. И. Панасюк, директор Научно-ис сле дова тельского института ядерной физики МГУ имени М. В.  Ломоно сова, профессор; Вл. В. Воеводин, заме ститель директора Научно-исследо ва тель ского 
вычислительного центра МГУ имени М. В.  Ломоносова, исполнительный директор 
НОЦ «СКТ-Центр», член-корреспондент РАН.

Издательство Московского университета
2013

Московский физико-технический институт 
(государственный университет)

Введение 
в параллельные методы 
решения задач

М.В.Якобовский

Допущено 
УМО по классическому университетскому образованию 
в качестве учебного пособия для студентов высших учебных заведений, 
обучающихся по направлениям ВПО 
010400 «Прикладная математика и информатика» 
и 010300 «Фундаментальная информатика 
и информационные технологии»

© Якобовский М. В., 2012 
© Издательство Московского 
университета, 2013
ISBN 978-5-211-06382-2

Якобовский М. В. 
Введение в параллельные методы решения задач: Учебное пособие / Предисл.: В. А. Садовничий. – М.: Издательство Московского 
университета, 2013. – 328 с., илл. – (Серия «Суперкомпьютерное образование»)

ISBN 978-5-211-06382-2

Я46

Курс, изложенный в учебном пособии, посвящен описанию базовых методов построения параллельных алгоритмов и программ для вычислительных 
систем с общей и с распределенной памятью. В первых четырех главах дается 
краткая характеристика архитектур параллельных вычислительных систем, 
рассматриваются основные области их применения, модели параллельных 
алгоритмов и программ, обсуждаются вопросы создания масштабируемых алгоритмов и излагаются базовые параллельные методы решения широкого 
круга задач. В следующих двух главах подробно рассмотрены методы построения масштабируемых параллельных алгоритмов сортировки больших объемов данных и особенности согласованной параллельной генерации последовательностей псевдослучайных чисел. Последние три главы посвящены 
обсуждению общих проблем применения многопроцессорных систем для решения сеточных задач: декомпозиции графов, динамической балансировки 
загрузки, визуализации сеточных данных.
В курсе обсуждаются методы построения эффективных масштабируемых 
параллельных алгоритмов, направленных на сокращение времени решения 
задач описываемых большими объемами данных. В связи с этим, существенное внимание уделяется анализу эффективности базовых параллельных 
алго ритмов и параллельных методов решения ряда задач обработки данных.
Пособие предназначено для широкого круга студентов, аспирантов и специалистов, желающих изучить и практически использовать методы создания 
алгоритмов для решения вычислительно трудоемких задач на параллельных 
вычислительных системах.
Учебное пособие основано на материалах лекций, читавшихся на протяжении многих лет в Московском физико-техническом институте (государст  венном университете).
Рекомендовано Советом учебно-методического объединения классических 
университетов по прикладной математике и информатике.
Ключевые слова: параллельные алгоритмы, высокопроизводительные вычислительные системы, масштабируемые параллельные методы и программы, декомпозиция графов, визуализация сеточных данных большого объема, 
параллельная сортировка, последовательности псевдослучайных чисел, суперкомпьютерное образование.
УДК 007 (075) 
ББК 32.973.2

УДК 007 (075) 
ББК 32.973.2
Я46

Уважаемый читатель!

Вы держите в руках одну из книг серии «Суперкомпьютерное образование», выпущенную в рамках реализации проекта комиссии 
Президента РФ по модернизации и технологическому развитию экономики России «Со здание системы подготовки высококвалифицированных кадров в области суперкомпьютерных технологий и специализированного 
программного 
обеспечения». 
Инициатором 
издания выступил Суперкомпью терный консорциум университетов 
России.
Серия включает более 20 учебников и учебных пособий, подготовленных ведущими отечественными специалистами в области 
супер компьютерных технологий. В книгах представлен ценный опыт 
преподавания супер компьютерных технологий в таких авторитетных вузах России, как МГУ, МФТИ, ННГУ, ТГУ, ЮУрГУ, СПбГУ 
ИТМО и многих других. При подготовке изданий были учтены рекомендации, сформулированные в Своде знаний и умений в области 
суперкомпьютерных технологий, подготовленном группой экспертов 
Суперкомпьютерного консорциума, а также международный опыт.
Современный уровень развития вычислительной техники и методов математического моделирования дает уникальную возможность 
для перехода промышленного производства и научных исследований на качественно новый этап. Эффективность такого перехода напрямую зависит от наличия достаточного числа высококвалифицированных специалистов. Данная серия книг предназначена для 
широкого круга студентов, аспирантов и специалистов, желающих 
изучить и практически использовать параллельные компьютерные 
системы для решения трудоемких вычислительных задач.

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

Ректор Московского университета,
Президент Суперкомпьютерного консорциума 
университетов России,
академик РАН  В. А. Садовничий

 Предисловие
6

Оглавление

Глава 1. Введение  ...................................................................................... 11

1.1. Современный компьютер — инструмент параллельной 
 
обработки данных .......................................................................11
1.2. Области применения многопроцессорных систем ...................16
1.3. Рассматриваемые параллельные архитектуры ..........................19
1.4. Пример параллельного алгоритма .............................................20
1.4.1. Последовательный рекурсивный алгоритм .....................21
1.4.2. Параллельный рекурсивный алгоритм ............................21
1.4.3. Последовательное вычисление членов ряда ....................22
1.4.4. Последовательный матричный алгоритм ........................23
1.4.5. Параллельный матричный алгоритм ...............................24

Глава 2. Основные понятия  ........................................................................ 28

2.1. Параллельная программа как ансамбль 
 
взаимодействующих последовательных процессов ..................28
2.2. Внутренний параллелизм ...........................................................29
2.2.1. Сложение многоразрядных чисел ....................................30
2.3. Ускорение и эффективность параллельных алгоритмов ..........38
2.4. Ускорение и эффективность относительно наилучшего 
 
последовательного алгоритма ....................................................41
2.4.1. Неравноправность условий выполнения — 
 
первая причина сверхлинейного ускорения ....................43
2.4.2. Алгоритмическая причина сверхлинейного 
 
ускорения ..........................................................................44
2.4.3. Формальное преобразование параллельного 
 
алгоритма в «наилучший» последовательный .................47
2.5. Априорная оценка эффективности параллельного 
 
алгоритма ....................................................................................49

Глава 3. Модели параллельных программ  ................................................... 53

3.1. Вычислительные системы с распределенной памятью .............54
3.2. Вычислительные системы с общей памятью .............................56
3.3. Гибридные архитектуры .............................................................58
3.4. Модель выполнения параллельной программы 
 
на распределенной памяти .........................................................59
3.5. Модель выполнения параллельной программы 
 
на общей памяти .........................................................................60
3.6. Средства взаимодействия последовательных процессов ..........62
3.6.1. Свойства канала передачи данных ...................................62
3.6.2. Методы передачи данных .................................................63

Оглавление
8

3.6.3. Семафор ............................................................................72
3.6.4. Барьерная синхронизация ................................................75

Глава 4. Базовые параллельные методы  ..................................................... 77

4.1. Метод сдваивания .......................................................................78
4.1.1. Быстрый алгоритм выбора частичных сумм ....................84
4.1.2. Барьерная синхронизация на основе 
 
синхронных обменов ........................................................86
4.1.3. Стена Фокса ......................................................................88
4.2. Метод геометрического параллелизма ......................................88
4.3. Метод конвейерного параллелизма ...........................................98
4.4. Метод коллективного решения ................................................ 107
4.5. Причины потери эффективности ............................................ 114

Глава 5. Сортировка данных  .................................................................... 117

5.1. Постановка задачи .................................................................... 117
5.2. Последовательные алгоритмы сортировки ............................. 120
5.2.1. Быстрая сортировка (runtime qsort, wsort) ....................... 123
5.2.2. Простое двухпутевое слияние (dsort) 
 
и слияние списков (lsort) ................................................. 124
5.2.3. Пирамидальная сортировка (hsort) ................................. 126
5.3 Свойства последовательных алгоритмов ................................. 128
5.3.1. Сортировка методом простого двухпутевого слияния .... 128
5.3.2. Пирамидальная сортировка ........................................... 135
5.3.3. Наилучший последовательный алгоритм 
 
сортировки dhsort ............................................................ 139
5.4. Масштабируемые алгоритмы сортировки ............................... 141
5.4.1. Сети сортировки ............................................................. 141
5.4.2. Сеть четно-нечетной сортировки .................................. 144
5.4.3. Сеть обменной сортировки со слиянием Бэтчера ......... 145
5.4.4. Сортировка больших массивов ...................................... 150
5.4.5. Сравнение алгоритмов сортировки ............................... 153
5.5. Результаты численных экспериментов .................................... 157

Глава 6. Генерация псевдослучайных чисел  .............................................. 161

6.1. Требования к генераторам псевдослучайных чисел 
 
для МВС .................................................................................... 162
6.2. Линейно-конгруэнтные генераторы ........................................ 168
6.3. M-последовательности ............................................................. 170
6.4. Проверка примитивности полиномов ..................................... 176
6.5. Тестирование генераторов ....................................................... 177

Оглавление

Глава 7. Декомпозиция сеточных графов  .................................................. 180

7.1. Пример двумерной сетки ......................................................... 180
7.2. Критерии декомпозиции графов ............................................. 182
7.2.1. Критерий 1: классический критерий 
 
декомпозиции графа ....................................................... 183
7.2.2. Критерий 2: выделение обособленных доменов ........... 184
7.2.3. Критерий 3: минимизация максимальной 
 
степени домена ................................................................ 185
7.2.4. Критерий 4: обеспечение связности графов 
 
каждого из доменов ......................................................... 186
7.3. Декомпозиция на основе исходной нумерации узлов ............ 189
7.4. Рекурсивная бисекция .............................................................. 191
7.5. Декомпозиция регулярных графов .......................................... 192
7.6. Методы декомпозиции произвольных графов ........................ 196
7.6.1. Иерархическая декомпозиция........................................ 196
7.6.2. Спектральная бисекция .................................................. 205
7.6.3. Алгоритм инкрементного роста ..................................... 210
7.7. Декомпозиция больших сеток .................................................. 217
7.7.1. Координатная рекурсивная бисекция ........................... 218
7.7.2. Двухуровневая стратегия обработки 
 
и хранения сеток ............................................................. 220

Глава 8. Динамическая балансировка загрузки процессоров  ...................... 223

8.1. Стратегии балансировки загрузки ........................................... 223
8.2. Метод диффузной балансировки ............................................. 224
8.3. Моделирование горения метанового факела .......................... 229
8.3.1. Постановка задачи динамической балансировки ......... 235
8.3.2. Алгоритм серверного параллелизма............................... 236
8.4. Адаптивное интегрирование .................................................... 248
8.4.1. Последовательные алгоритмы ........................................ 249
8.4.2. Параллельные алгоритмы ............................................... 256

Глава 9. Визуализация сеточных данных  .................................................. 278

9.1. Клиент-серверная технология ................................................. 280
9.2. Online или Offline-визуализация: плюсы и минусы ................ 281
9.2.1. Online-визуализация Offline-визуализация ................... 281
9.3. Этапы визуализации ................................................................. 285
9.4. Визуализация изоповерхностей ............................................... 290
9.4.1. Аппроксимация изоповерхности ................................... 293
9.4.2. Виды данных, описывающих триангуляцию ................. 296
9.4.3. Метод редукции .............................................................. 299

Оглавление

9.4.4. Заполняющие пространство триангуляции ................... 302
9.4.5. Параллельные алгоритмы построения 
 
аппроксимирующих триангуляций ................................ 303
9.4.6. Многоуровневое огрубление больших сеток ................. 304
9.4.7. Примеры визуализации .................................................. 306
9.5. Ввод-вывод сеточных данных .................................................. 308
9.5.1. Соотношение времени чтения данных и времени 
 
их обработки .................................................................... 308
9.5.2. Распределенный ввод-вывод .......................................... 309
9.5.3. Огрубление и сжатие скалярных сеточных функций .... 310

Список ссылок ......................................................................................... 317

Предметный указатель ............................................................................. 323

Глава 1

Введение

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

1.1. Современный компьютер — инструмент 
параллельной обработки данных

Рост производительности процессора определяется двумя 
основными факторами: рабочей частотой и архитектурой. На 
рис. 1 показаны характеристики процессоров Intel, обеспечивающих вычислительную мощность суперкомпьютеров верхней части списка пятисот крупнейших систем мира: top500.
org [1]. На рисунке 1 приведены частота и производительность 
одного процессорного ядра. При построении графика рассматривались системы традиционной архитектуры, не содержащие 

Глава 1. Введение

специализированных графических ускорителей, в том числе 
графических карт общего назначения. Производительность 
оценивалась как отношение пиковой производительности системы к общему числу процессорных ядер [2]. 

Таблица 1

Характеристики процессоров

Дата рейтин га

CPU, Intel

Частота (GHz)

Производи тельность 
ядра CPU (Gflops)

Число ядер

Про из во ди тель ность 
CPU (Gflops)

Позиция в top500

01.11.11
Xeon E5450 
4C 3.00 GHz
2,93
12,8
4
47
7

01.11.10
Xeon 7500 
Nehalem-EX
2,26
11,7
8
72
6

01.11.09
01.11.08
Xeon E54xx
Harpertown
3
11,9
4
48
6
3

01.11.07
Xeon 53xx
Clovertown
3
12
4
48
3

01.11.06
Xeon
3,6
7,2
2
14
6

01.11.05
01.11.04
Itanium 2
1,5
6
4
24
4
2

01.11.03
Pentium 4 
Xeon
3,06
6,1
2
12
4

01.11.02
Pentium 4 
Xeon
2,4
4,8
2
9,6
5

01.11.01
01.11.00
Pentium Pro
0,33
0,33
1
0,33
4
2

Глава 1. Введение

Как следует из таблицы 1, частота процессора (нижний 
график на рис. 1) не увеличивается уже несколько лет. Напротив, в последние годы отмечается ее снижение, обусловленное, в первую очередь, необходимостью уменьшения 
удельного энергопотребления вычислительных систем (отношения энергопотребления к вычислительной мощности). 
Производительность процессора, тем не менее, продолжает расти (рис. 2). Отметим крайне важную архитектурную 
особенность рассматриваемых процессоров: начиная с 2006 
го да они являются многоядерными. Это означает, что в одном корпусе на сверхбольшой интегральной схеме (СБИС) 
размещено несколько полноценных процессоров. Фактически следовало бы говорить «многопроцессорная СБИС», 
но вместо этого продолжают использовать термин процессор 
(или многоядерный процессор), содержащий несколько процессорных ядер. 
Рассмотрим подробнее, за счет чего на протяжении последних десяти лет росла производительность процессора. 
На рис. 3 приведено отношение производительности одного 
процессорного ядра (верхняя кривая рис. 1) к частоте работы процессора (нижняя кривая рис. 1). Полученные числа 

Рис. 1. Частота и производительность процессорного ядра

Глава 1. Введение

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

Рис. 3.  Число операций, выполняемых процессорным ядром 
за один такт

Рис. 2 . Производительность процессора