Демьянович Ю.К., Иванцова О.Н. Технология программирования для распределенных параллельных систем

Подождите немного. Документ загружается.

Санкт-Петербургский государственный университет

Ю. К. Демьянович, О.Н.Иванцова

ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ

ДЛЯ РАСПРЕДЕЛЕННЫХ ПАРАЛЛЕЛЬНЫХ

СИСТЕМ

Курс лекций

Санкт-Петербург

2005

В В Е Д Е Н И Е

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

важнейших задач, в числе которых задачи прогнозирования по-

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

изменений (возникновения ураганов, тайфунов, резких изменений

температуры и т.п.), задачи геологии и геофизики (предсказания

землетрясений, вулканических извержений и т.д.), задачи астроно-

мии и астрофизики (предсказания поведения Солнца, столкновений

метеоритов и болидов с Землей, обоснование космогонических гипо-

тез), задачи, связанные с биологией и с чрезвычайно значимой для

человека областью — с медициной (последнее достижение — рас-

шифровка генома человека — один из ярч айши х примеров приме-

нения высокопроизводительных вычислительных систем). Конеч-

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

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

систем невозможно.

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

мыслятся без распараллеливания, ибо наиболее мощные вычисли-

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

(см., например, регулярно обновляемоый в Internet список TOP500,

содержащий перечень наиболее мощных компьютеров в мире, что-

бы убед иться в том, что все компьютеры в этом списке — парал-

лельные системы). Благодаря распараллеливанию удается достичь

производительности в десятки терафлопс (10

операций в секунду

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

и этого недостаточно: требуются вычислительные мощности с быст-

родействием в десятки пентафлопс. Достижение таких скоростей

трудно представить без распараллеливания (к моменту написания

этого введения уже достигнуто быстродействие 145 терафлопс).

Распараллеливание алгоритмов и написание параллельных про-

грамм — весьма сложное дело. Причины возникающих трудностей

различны: с одной стороны, идеология распараллеливания труд-

но воспринимается после приобретения навыков последовательно-

го программирования, а с другой стороны, метод ы распараллели-

вания задач недостаточно разработаны.

Заметим, что прямое численное моделирование соответствую-

щих физических или физико-химических явлений, которые по-

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

процессов, взаимодействующих друг с другом, является наиболее

естественным путем моделирования. Без связи с распараллелива-

нием моделирование процессов в том или ином смысле рассмат-

ривалось давно: метод частиц в ячейках, метод конечных элемен-

тов, метод с еток и другие методы, фактически, приводят к похо-

жему результату. Конечно, распараллеливание несет в себе боль-

шие трудности, но и вселяет значительные надежды. Исследова-

ния в этой области, пр актич еское освоение теоретических резуль-

татов, создание соответствующего программного обеспечения, от-

ладка программ на параллельных системах и проведение э ффек-

тивных вычислений представляются чрезвычайно важными.

Предлагаемый курс лекций посвящен в основном параллельно-

му программированию на вычислительных системах с распределен-

ной памятью, хотя часть представленной информации можно отне-

сти и к системам с обще й памятью. Использование параллельных

процессов существенн о усложняет программирование: эффектив-

ность увеличивается с увеличением независимости процессов, но

из-за этого приходится ослаблять контроль за вычислениями. Про-

цессы находятся в постоянной конкуре нтной борьбе за ресурсы, но

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

моменты синхронизации и обмена полученной информацией.

Для написании параллельных программ используются специ-

альные средства, которые могут предоставляться в виде специаль-

ных библиотек или расширений известных языков (например, биб-

лиотеки MPI, Open MP, PVM, язык Linda для Fortran, C, C++);

однако, основное внимание следует уделять принципам исп ользова-

ния этих средств: именно эти принципы рассматриваются в первую

очередь в данном курсе лекций. Поскольку курс расчитан на 36

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

ются в надежде, что любознательный читатель сможе т почерпнуть

недостающие сведения из книг [1-7], содержание которых частично

отражено в данном курсе лекций.

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

щена программированию с использованием передачи сообщений,

вторая — мониторам и условным переменным; в третьей главе вво-

дится понятие рандеву и рассматриваются активные мониторы, а

четвертая глава посвящена операторам взаимодействия. В пятой

главе дается представления о языках Occam, CSP, Linda. Наконец,

шестая глава посвящена удаленному вызову процедур и взаимо-

действию процессов, вопросам неделимости операций, устранению

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

критическим переменным. Во второй главе рассматривается зада-

ча о критической секции, активные блокировки, алгоритм разры-

ва узла, построению барьеров. В третьей главе излагаются вопро-

сы синхронизации с помощью семафоров. Рассматриваются реше-

ния задач “об обедающих философах”, “о читателях и писателях”,

“кратчайшее расстояние” и некоторых други х. В лекциях широко

использованы книг и [1–6], а также Интернет и книга [7], и з которых

почерпнуты примеры и стиль изложения.

Авторы курса надеются на быстрое усвоение читателями изло-

женных первоначальных сведений по методам параллельного про-

граммирования, что позволит им легко перейти к чтению более со-

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

Данная работа частично поддержана грантами РФФИ 04-01-

00692, 04-01-00026 и НШ-2268.2003.1.

Глава 1. ПРОГРАММИРОВАНИЕ

С ИСПОЛЬЗОВАНИЕМ ПЕРЕДАЧИ СООБЩЕНИЙ

§ 1. О распределенном программировании

В н астоящее время широкое распространение получили вычис-

лительные системы (ВС) — архитектуры с распределенной памя-

тью. Зачастую это многомашинные комплексы и сети, а иногда —

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

сорных систем . В этом случае процессоры (вычислительные моду-

ли, кратко – ВМ) имеют собственную локал ьную память и обща-

ются между собой с помощью коммуникационной сети, а не через

разделяемую (т.е. общую) память; предполагается, что общая па-

мять отсутствует.

Наиболее употребительны следуюшие виды коммуникационных

сред:

1) масштабируемый когерентный интерфейс SCI (Scalable

Coherent Interface); основными его элементами служат узлы

SCI, представляющие собой стандартизованные фрагменты кэш-

памяти, через которые ВМ с помощью адаптеров общаются с се-

тью;

2) коммуникационная среда MYRINET, в которой передачи

осуществляются по схеме адаптер ВМ-источника – коммутаторы

Myrinet – адаптер ВМ-приемника;

3) коммуникационная среда Raceway (с использованием

кристалла-коммутатора Cypress Raceway Crossbar и адаптеров, ра-

ботающая по схеме порт коммутатора – шина ВМ),

4) коннектор шин PC I: SRC 3266 DE (Serbing Ring Connection

для PCI), позволяющая соединить до 256 шин PCI;

5) Memory Channel фирмы DEC дл я кластерных систем;

6) коммуникационные среды на базе транспьютероподобных

микропроцессоров, характерными чертами которых является нали-

чие специальной сети для инициализации и линий стробирования

для передачи синхросигнала;

7) широко используются различные шинные структуры.

Вычислительные модули поддерживают процессы, а взаимодей-

ствие между проц есс ами поддерживает коммуникационнная сре да

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

каналы можно рассматривать как абстракцию сетей связи, обеспе-

чивающих физическую связь между вычислительными модулями.

Адаптеры, линки и коммутаторы обычно являются важными эле-

ментами коммуникационной среды. Для удобства программирова-

ния вводятся специальные операции, которые служат для передачи

сообщений.

Параллельные п рогр аммы, использующие передачу сообщений

называются распределенными программами.

Заметим, что распределенные программы могут работать и на

ВС с разделяемой (общей) памятью: в этом случае каналы генери-

руются с помощью разделяемой памяти.

В распр еде ле нных программах каналы чаще всего являются

важными, но не всегда единственными объектами, разделяемыми

вычислительными модулями; кроме каналов могут быть общими

также некоторые другие устройства (например, принтеры).

Пока что будем считать, что каждый процесс выполняется на

своем вычислительном модуле (иначе говоря, поток команд, обраба-

тываемых вычислительным модулем, рассматривается как отдель-

ный процесс). В этом случае переменная оказывается локальной по

отношению к своему процессу, который, таким образом, является

ее владельцем (caretaker). Эта переменная никогда не должна ста-

новится объектом параллельного доступа, а значит она нуждается

в использовании механизма взаимного исключения.

Общение процессов между собой происходит разными путями;

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

взаимодействия. Значение синхронизации здесь не меньше, а воз-

можно и больше, чем при программировании систем с разделяемой

памятью: как известно, важно постоянно поддерживать когерент-

ность иерархической памяти системы с распределенной памятью.

Взаимодействие процессов на разных стадиях может быть

– асинхронным (неблок ирующим ),

– синхронным (блокир ующим).

Различают:

1) асинхронную передачу сообщений,

2) синхронную передачу сообщений,

3) удаленный вызов процедур (remote procedure call — RPC),

4) рандеву.

Эти механизмы эквивалентны в том смысле, что программа,

написанная с помощью одного из ни х, может быть переписана в

программу, использующую другой механизм; однако, использова-

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

различной эффективности программной реализации алгоритма.

Замечание. В дальнейшем применяется программная нотация,

которая достаточна для описания примеров программ; она пред-

ставляется достаточно ясной и не требующей формализации.

§ 2. Асинхронная передача сообщений

Для асинхронной передачи сообщений канал является очередью

FIFO (First In – First Out); при этом сообщения могут быть отправ-

лены, но еще не получены.

Объявление канала имеет вид

chan ch(type

, . . . , type

); (1)

Здесь ch — имя канала, type

— тип поля (обязателен), id

—

имя поля (не является обязательным).

Пример 1.

chan input(char);

chan disk_access(int cylinder, int block, int count,

char*buffer);

Здесь объявлены два канала. Первый канал input исполь-

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

disk_access содержит сообщения с четырьмя полями: номер ци-

линдра, номер бл ока, число символов, адрес буфера.

Можно использовать массив каналов:

chan result[n](int);

здесь индексы (номера каналов) имеют значения от 0 до n-1.

Отправка сообщения по каналу ch (см. (1)) имеет вид

send ch(expr

, . . . , expr

); (2)

здесь выражение expr

должно иметь тип type

Выполнение операции send состоит в

1) в вычислении выражений expr

;

2) в отправке сообщения в конец очереди, связанной с каналом

ch.

Теоре тиче ски очередь не ограничена; поэтому посылка сообще-

ния не вызывает задержку, и следовательно операция send являет-

ся неблокирующим примитивом.

Процесс получающий сообщение из канала выполняет операцию

receive:

receive ch(var

, . . . , var

); (3)

Переменные должны иметь тот же тип, что и поля в объявлении ка-

нала (1). Процесс, получающий сообщение по команде (3), приоста-

навливается до тех пор, пока в очереди канала не появится хотя бы

одно сообщение. Итак, операция receive может вызвать задерж-

ку — поэтому это блокирующий примитив; процесс, принимающий

сообщение, не обязан использовать опрос канала для получения со-

общения.

Доступ к каждому каналу — неделимое действие; каждое пере-

данное сообщение будет прин ято в том порядке, в каком отправлено

(канал является очередью типа FIFO).

Пример 2. Формир ование строк из символов.

chan input(char), output(char[MAXLINE]);

process Char_to_Line{

char line[MAXLINE]; int i=0;

while(true){

receive input(line[i]);

while(line[i]!=CR and i<MAXLINE){

# line[0:i-1] содержит i входных символов

i=i+1;

receive input(line[i]);

}

line[i]=EOL;

send output(line);

i=0;

}

П о я с н е н и я : сначала объявляется канал input для отдель-

ных символов и канал output для получения строк. Далее объяв-

ляется процесс Char_to_Line, в котором, пока параметр “истина”,

получаем значения из канала input в переменную line[0] и до

тех пор пока line[i] не совпадет с CR (символ возврата каретки)

и i<MAXLINE присваиваем i=i+1 и получаем очередное line[i] из

канала input. По окончании цикла присваиваем line[i] зн ачение

EOL и посылаем полученную строку в канал output.

Каналы ис пользуются процессами совместно и потому объявля-

ются глобальными относительно всех процессов (с м. предыдущий

пример). Любой процесс м ожет отправлять данные в любой канал

и принимать из любого канала.

Если канал используется многими процессами, то он называется

портом (или общим почтовым ящиком).

В случае, когда у канала имеется только один получатель и мно-

го отправителей, то он называется входным портом (или индиви-

дуальным почтовым ящиком), а если у канала много получателей

и один отправитель его можно называть выходным портом.

Наконец, если у канала один отправитель и один получатель, то

он называется каналом связи.

Замечание. При выполнении команды receive часто процесс

вынужден ждать; однако, иногда предусматривается выполнение

другой работы, для которой не требуется предполагаемое сообще-

ние из затребованного канала.

Процесс может определить пуста ли очередь канала с именем

ch с помощью вызова

empty(ch)

который возвращает значение True, если канал пуст, и значение

False — в противном сл учае. Однако, при таком запросе может по-

лучится ложная ситуация: при появлении значения True в дей -

ствительности очередь может оказаться непустой, и, наоборот, при

получении значения False к моменту запроса очередь уже может

оказаться пустой. Таким образом, вызов empty сл едует применять

с осторожностью.

§ 3. Сортировка, фильтры

Фильтром называется процесс, получающий значения из одно-

го или нескольких входных каналов, и отправляющий значе ния в

выходные каналы (один или более).

Для иллюстрации рассмотрим процесс сортировки n чисел в по-

рядке возрастания. Пусть имеется два канала: input — входной ка-

нал, output — выходной и sent[i] — i-е значение, отправляемое в

output.

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

SORT: ( ∀ i: 1≤i<n: sent[i]≤sent[i+1])

{значения, отправляемые в output, состоят из чисел,

полученных в input}

Схема процесса такова:

process Sort {

получить значения из канала input;

отсортировать числа;

передать отсортированные числа в канал output

}

Напомним, что процесс receive является блокирующим. Для

того, чтобы Sort начал работу требуется, чтобы он определил мо-

мент получения всех n чисел, либо это число n должно быть переда-

но пр оцес су Sort заранее, либо (поскольку поставляющий процесс

обычно не имеет информации о количестве чисел заранее) поток

чисел, подлежащих сортировке, долже н заканчиваться специаль-

ным маркером EOS.

Интересно использовать параллелизм при слиянии (соедине-

нии). Это можно сделать следующим образом: пусть имеется про-

цесс сливающий (соединяющий) два отсортированных потока чисел

в один отсортированный поток (in1, in2 — входные каналы, out —

выходной канал):

GLUE: in1 и in2 пусты

sent[n+1]==EOS

(∀i: 1≤i<n: sent[i]≤sent[i+1])

{значения, отправляемые в канал out, являются

перестановкой чисел, полученных из каналов in1 и in2 }

П о я с н е н и я : в первой строке процесса GLUE сказано, что

in1 и in2 полностью использованы и в конец строки sent поставлен

символ EOS, во второй строке процесса указано, что значения в sent

расположены в порядке возрастания. В конце сказано, что значения

на выходе являются перестановкой значений входа.