Распараллеливание программ

Федеральное агентство по образованию 
российской Федерации

Федеральное государственное образовательное учреждение
высшего профессионального образования
«юЖнЫй ФедеральнЫй Университет»

В. А. САВельеВ, Б. Я. ШтейнБерг

рАСпАрАллелиВАние  

прогрАмм 

ростов-на-дону
издательство южного федерального университета
2008

© савельев в. а., 2008
© Штейнберг б. Я., 2008
© южный федеральный университет, 2008
©  оформление. Макет. издательство  
южного федерального университета, 2008

УДК 519.6+681.3.012
ББК  22.193+32.973.26–018.2 
С 13

Печатается по решению редакционно-издательского совета 
Южного федерального университета

Учебник подготовлен и издан 
в рамках национального проекта 
«Образование» по «Программе развития федерального 
государственного образовательного учреждения 
высшего профессионального образования  
″Южный федеральный университет″ на 2007–2010 гг.»

 
Савельев В. А., Штейнберг Б. Я.
с 13 
 
распараллеливание программ: учебник / в. а. савельев, б. Я. Штейнберг. – 
ростов н/д: изд-во юФУ, 2008. – 192 с.
 
 
ISBN 978-5-9275-0547-0
Учебник посвящен параллельным вычислениям, которые сегодня занимают все 
большее место в теории и практике программирования. рассматривается как теория 
преобразований и распараллеливания программ, так и инструменты практического параллельного программирования.
адресован студентам и аспирантам математических и естественнонаучных спе- 
циальностей.
 
УДК 519.6+681.3.012
ISBN 978-5-9275-0547-0 
ББК 22.193+32.973.26–018.2

оглавление

введение  .........................................................................................................................5

1.  распараллеливаюЩие/оптиМизирУюЩие преобразованиЯ 
програММ  ....................................................................................................................7

програММнЫе зависиМости и базовЫе преобразованиЯ .................7

преобразованиЯ линейнЫХ УЧастков  ......................................................19

преобразованиЯ циклов  ...................................................................................34

реШетЧатЫй граФ как Модель инФорМационной  
зависиМости в гнездаХ циклов  ..................................................................61

распараллеливание  ............................................................................................72

конвейернЫе вЫЧислениЯ  ..............................................................................89

2.  основнЫе средства параллельного програММированиЯ  ..........103

использование OpenMP ......................................................................................103
основные понятия .................................................................................................104
директивы OpenMP API ........................................................................................106
Функции времени выполнения OpenMP ..............................................................116
комбинированные конструкции ...........................................................................117
простые примеры использования OpenMP .........................................................118

библиотека POSIX® thread ....................................................................................124
типы данных pthread .............................................................................................125
Управление нитями ................................................................................................126
простой пример .....................................................................................................132
синхронизация .......................................................................................................133
Частные данные нити ............................................................................................139

передаЧа сообЩений  .......................................................................................143
обзор языков и систем  .........................................................................................143
PVM  ........................................................................................................................145
Erlang  ......................................................................................................................148
Parallaxis III  ............................................................................................................154

програММирование на MPI .............................................................................160
основные свойства ................................................................................................161
среда выполнения ..................................................................................................165
взаимодействия точка-точка .................................................................................166
коллективные взаимодействия .............................................................................175
коммуникаторы ......................................................................................................180
интеркоммуникаторы ............................................................................................183
топология ................................................................................................................184
пользовательские типы данных ...........................................................................184

прилоЖение. использование Pthreads-Win32 .........................................................188

список литератУрЫ ................................................................................................190

СпиСоК СоКрАЩений

Мвс 
– многопроцессорная вычислительная система
пЭ 
– процессорный элемент
плис – программируемая логическая интегральная схема
орс 
– открытая распараллеливающая система 
MIMD – many instructions, multiple data 
SIMD 
– single instructions, multiple data 
SPMD – single program multiple data 
MPMD – muliple program multiple data 
VLIW – vary long instruction word
SUIF 
– Stanford University Intermediate Format
MPI 
– massage passing interface 
SMP 
– Symmetric Multi Processing 
FPGA 
– Field Processing Gate Array – плис

ВВЕДЕНИЕ 

данный учебник посвящен параллельным вычислениям, которые, особенно 
в последние годы, занимают все большую долю в теории и практике программирования. 
закон Мура об ускорении быстродействия вычислительной техники подтверждается уже десятилетиями. но изменилось не только быстродействие 
компьютеров, но и соотношение времени на подготовку данных и времени на 
их обработку. а это означает, что разные программы стали работать быстрее в 
разной степени. 
У сравнительно массового отечественного суперкомпьютера 80-х годов пс2000 обращение к памяти (чтение/записать) длилось 3 такта, сложение 1 такт, 
пересылка числа из одного процессорного элемента в другой (соседний) по 
кольцевому сдвиговому регистру 1 такт. в современных массовых процессорах 
умножение в 15 раз быстрее обращения к оперативной памяти и на два порядка быстрее пересылки по сети. если на пс-2000 был смысл распараллеливать 
цикл, вычисляющий сумму 100 слагаемых, то на кластере даже из двух компьютеров такое распараллеливание вместо ускорения вызовет замедление. 
таким образом, соотношение времён подготовки и обработки данных влияет 
на эффективность распараллеливающих преобразований. 
переменчивы приоритеты и в скалярной оптимизации. рассмотрим вопрос 
об эффективности замены оператора 

X(i+2) = X(i+2)+5

следующим кодом 

k = i+2
X(k) = X(k)+5 

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

For I = 1 to N do 
X[i] = 2*X[i+1]

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

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

1. РАСПАРАЛЛЕЛИВАЮЩИЕ/ 
ОПТИМИЗИРУЮЩИЕ  
ПРЕОБРАЗОВАНИЯ ПРОГРАММ 

теория оптимизирующих преобразований программ насчитывает несколько 
десятилетий. Эти преобразования используются автоматически в компиляторах 
и вручную. при этом описываются преобразования, как правило, на примерах 
высокоуровневых программ. более всего литература по теории преобразования 
программ ориентируется на программы языка Фортран. с течением времени 
накапливаются все новые и новые преобразования программ. в данной главе 
описаны наиболее используемые высокоуровневые преобразования, в основном, преобразования циклов. распараллеливания циклов и решетчатый граф 
программы иллюстрируются экранными формами, полученными с помощю 
орс – открытой распараллеливающей системы, которая разрабатывается в 
южном федеральном университете www.ops.rsu.ru. 

ПРОГРАММНЫЕ ЗАВИСИМОСТИ  
И БАЗОВЫЕ ПРЕОБРАЗОВАНИЯ

 УпрАВлЯюЩий грАф прогрАммы
Управляющий граф [8], [12] – это одна из основ преобразования программ. 
даже если в описании преобразования управляющий граф не упоминается, то 
он, как правило, подразумевается. в явном или неявном виде управляющий 
граф присутствует во внутренних представлениях оптимизирующих/распараллеливающих компиляторов. 
перед описанием преобразований и управляющего графа программ следует 
определиться, о каких программах будет идти речь. 
программы – это предложения языков программирования. в научной литературе высокоуровневые преобразования более всего описаны для программ 
языка Фортран. встречаются также описания преобразований для языков си 
и паскаль, реже – для других высокоуровневых языков. абстрагируемся от этих 
конкретных языков, чтобы преобразования носили как можно более общий характер. будем считать, что рассматриваемые программы содержат следующие 
операторы: 
операторы присваивания, 
циклы со счетчиком (параметром, считающим итерации), 
блочные условные операторы, 
операторы безусловного перехода на метку GOTO, 
пустые операторы, 
блочные операторы (операторные скобки), 

операторы вызова подпрограммы (процедуры или функции). 
предполагается, что в рассматриваемом языке программирования допускается конкатенация операторов. 
данные описываются только константами, скалярными переменными и массивами. 
программы могут исполняться, изменяя этим самым состояние памяти компьютера. 
исполнение программы состоит в чтении единиц языка (операторов, линейных участков), сопоставлении переменных, входящих в выражения с их значениями и изменении значений переменных (соответствующих им состояний ячеек памяти). последовательность чтения единиц языка определяется семантикой 
языка программирования. если две единицы языка могут прочитаться при некотором исполнении программы одна после другой, то говорят, что они связаны 
передачей управления. 
Фрагмент программы – это такая часть подряд идущих по тексту операторов, 
заключение в скобки которой приводит к программе, эквивалентной исходной. 
базовый блок или линейный участок программы – это фрагмент, состоящий 
только из операторов присваивания. 
в частности, у программы выделяются входные данные и выходные данные. 
две программы считаются эквивалентными, если при одних и тех же входных 
данных в результате исполнения выходные данные у этих программ тоже совпадают. 
вершины управляющего графа – это некоторые элементы языка программирования (в научной литературе чаще всего операторы или линейные участки), а 
дуги – это передачи управления. 
отметим, что ранее в литературе в качестве вершин управляющего графа 
предполагалось использовать только операторы программы. такой подход вполне удобен для программ языка Фортран, но уже не удобен для языка паскаль, 
в котором циклу с постусловием «repeat-until» неудобно сопоставлять одну вершину (вместо «repeat» или вместо «until»?). если вершины управляющего графа – операторы, то управляющий граф, соответствующий линейному участку 
имеет вид простого пути. поэтому такие фрагменты программы и называются 
«линейными участками». иногда линейные участки рассматривают в качестве 
вершин управляющего графа, чтобы сократить размеры графа, сохраняя его топологию. 
если операторы программы связаны конкатенацией, то передача управления 
между ними происходит в порядке следования этих операторов. Условный оператор и оператор цикла имеют по две передачи управления. 
в языках программирования встречаются сложные операторы, которые 
определяются через другие операторы. обычно, такие операторы имеют вид 
<сложный оператор> ::= term1 statement1 term2 statement2 … 
termn statementn termn+1 

здесь term1 , term2 , … termn , termn+1 – некоторые зарезервированные слова 
языка, statement1 , statement2 , … statementn – операторы или выражения. такой 
вид имеют операторы цикла, условные операторы, блочный оператор, оператор 
case в языке паскаль, оператор switch в языке си. 
пусть G ориентированный граф, вершинами которого являются единицы 
языка term1 , statement1 , term2 , statement2 ,…, termn , statement , termn+1 . пусть 
этот граф имеет единственный источник и единственный сток term1 и termn+1 соответственно. дуги этого графа будем считать передачами управления в сложном операторе. 
следует отметить, что при внешней схожести операторов case в языке паскаль и switch в языке си, передачи управления у них организованы по-разному. 
вершины, как бы одинаковые, а дуги связывают эти вершины по-разному. графы передач управления этих операторов не изоморфны. 
приведенное выше аксиоматическое определение передач управления в 
сложных операторах – элемент семантики этих операторов. 
при преобразованиях программ следует контролировать сохранение синтаксической и семантической корректности. 

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

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

Пример 2. в данном примере у фрагмента, состоящего из одного оператора 
999, по крайней мере, два входа: один от предыдущего присваивания, а другой – 
от условного оператора. 

 IF BOOLEXPR THEN 
 A = 1
999 X = 1
Конец примера. 
иногда перед выполнением преобразования рассматриваемый фрагмент необходимо заключать в операторные скоби. в работе [26] преобразуемые циклы 
приводятся к такому виду, в котором перед заголовком и после тела ставятся 
пустые операторы с метками, которые перехватывают передачи управления, 
входящие в рассматриваемый цикл и выходящие из него. 
Пример 3. в этом примере все операторы информационно независимы. 
Управление передается от каждого предыдущего оператора к последующему. 

но операторы 3 и 4 можно менять местами, а операторы 1 и 2 – нельзя. заметим, что перестановка операторов 1 и 2 приводит к программе синтаксически 
и семантически корректной, но не эквивалентной исходной. по этой причине 
иногда приходиться оговаривать, какие именно операторы входят в рассматриваемый фрагмент. 

1 GOTO 2
2 X = 1 
3 Y = 2 
4 Z = 3 
Конец примера. 

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

информационная зависимость в программе

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

Пример 4. в следующем операторе присваивания 

 
A (I + B( J + 2)) = D( I–1, B( I))+3* A(1)- I+5
 
1  2 
3 4 
5  6 
7 8  
9  
10 

десять вхождений переменных (их номера проставлены снизу) – и только первое является генератором. 
Конец примера. 

 Пример 5. в следующем выражении языка с 

A = B++ 

вхождение переменной B является одновременно и использованием и генератором. 
Конец примера. 

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

Пример 6. 

 
DO 99 I=1,100
99 A(I)=D(I,I-1)+A(I-1)

в операторе с меткой 99 вхождения переменной A информационно зависимы, поскольку оба обращаются к ячейке памяти A(10): вхождение A(I) на десятой итерации, а A(I-1) – на одиннадцатой итерации цикла. 
Конец примера. 

граф информационных связей – это ориентированный граф, вершины которого соответствуют вхождениям, а дуга соединяет пару вершин (v, u), если 
выполняется одно из следующих условий: 
1. Эти вхождения обращаются к одной и той же ячейке памяти (т. е. порождают информационную зависимость), причем вхождение v раньше, чем u и хотя 
бы одно из этих вхождений является генератором. 
2. вхождение u является генератором, а вхождение v принадлежит этому же 
оператору присваивания. такие дуги будем называть тривиальными. 
генератор будем обозначать – out (output), а использование – in (input). дуги 
графа информационных связей бывают трех типов в зависимости от типов инцидентных им вершин: out-in – истинная информационная зависимость (true 
dependence), in-out – антизависимость (antidependence), out-out – выходная зависимость (output dependence) [4, с. 95].
если информационная зависимость связывает два использования, то мы 
будем говорить об in-in зависимости. Эти зависимости не влияют на эквивалентность преобразований программ и используются только при распределении 
данных в параллельной памяти. 
иногда бывает трудно определить, существует или нет информационная зависимость между парой вхождений. при преобразованиях программ в таких 
случаях предполагают худшее – считают, что такая зависимость существует, и 
на графе соответствующие вершины соединяют дугой. 
Пример 7. 

 
DO 99 I=1,N
99 X(2*I)=X(2*I+k)

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