Основы многопоточного и распределенного программирования

       

Конвейерные алгоритмы


Напомним, что процесс-фильтр получает данные из входного порта, обрабатывает их и от­сылает результаты в выходной порт. Конвейер — это линейно упорядоченный набор процессов-фильтров. Данная концепция уже рассматривалась в виде каналов Unix (раздел 1.6), сортирую­щей сети (раздел 7.2), а также как способ циркуляции значений между процессами (раздел 7.4). Здесь показано, что эта парадигма полезна и в синхронных параллельных вычислениях.

В решении задач параллельных вычислений обычно используется несколько рабочих процессов. Иногда их можно программировать в виде фильтров и соединять в конвейер па­раллельных вычислений. Есть три базовые структуры таких конвейеров (рис. 9.1): открытая, закрытая и циклическая (круговая). Рабочие процессы обозначены символами от Wt до Wf В открытом конвейере входной источник и выходной адресат не определены. Такой конвей­ер можно включить в любую цепь, для которой он подходит. Закрытый конвейер — это от­крытый конвейер, соединенный с, управляющим процессом, который производит входные дан­ные для первого рабочего процесса и потребляет результаты, вырабатываемые последним ра­бочим процессом. Пример открытого конвейера — команда Unix "grep pattern file | we", которую можно поместить в самые разные места. Выполняясь в командной строке, эта команда становится частью закрытого конвейера с пользователем в качестве управляющего процесса. Конвейер называется циклическим (круговым), если его концы соединены; в этой ситуации данные циркулируют между рабочими процессами.

В разделе 1.8 были представлены две распределенные реализации умножения матриц а х Ь = с, где а, Ь и с — плотные матрицы размерами n x п. В первом решении работа просто делилась между n рабочими процессами, по одному на строку матриц а и с, но каж­дый процесс должен был хранить всю матрицу Ь. Во втором решении также использовались n рабочих процессов, но каждый из них должен был хранить только один столбец матрицы Ь. В этом решении в действительности применялся круговой конвейер, в котором между рабо­чими процессами циркулировали столбцы матрицы Ь.


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





340                                                                            Часть 2 Распределенное программирование

чения а [ i, * ]. Во второй фазе рабочие процессы получают столбцы матрицы Ь, сразу пере­дают их следующему рабочему процессу и вычисляют одно промежуточное произведение. Эту фазу каждый рабочий процесс повторяет п раз, получая в результате значения с [ i, * ]. В третьей фазе каждый рабочий процесс отсылает свою строку матрицы с следующему рабо­чему процессу, затем получает и передает далее строки матрицы с от предшествующих про­цессов конвейера. Последний рабочий процесс передает свою и остальные полученные стро­ки матрицы с управляющему. При этом строки передаются в порядке от с[п-1,*] до с [ 0, * ], поскольку в этом порядке их получает последний рабочий процесс конвейера. При таком порядке передачи снижаются задержки взаимодействия, а последнему рабочему про­цессу не нужна локальная память для хранения всей матрицы с.

Действия рабочих процессов показаны в листинге 9.5, б. Три фазы работы процессов от­мечены комментариями. Учтены отличия последнего рабочего процесса от остальных.



Глава 9. Модели взаимодействия процессов                                                                            341

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

Во-вторых, чтобы первый рабочий процесс получил все строки матрицы а и передал их далее, нужно n циклов передачи сообщений. Еще п-1 циклов нужно, чтобы заполнить кон­вейер, т.е.




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

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

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

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

J.3.2. Блочное умножение матриц

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


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

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

Вернемся к задаче вычисления произведения двух матриц а и Ь с размерами n x n и со­хранения результата в матрице с. Чтобы упростить код, используем отдельный рабочий про­цесс для каждого элемента матрицы и пронумеруем строки и столбцы от 1 до п. (В конце раз­дела описано использование блоков значений.) Пусть массив Worker [ 1.- n, 1.- n ] — это мат­рица рабочих процессов. Матрицы а и Ь вначале распределены так, что у каждого процесса Worker [ i, j ] есть соответствующие элементы матриц а и Ь.

342                                                                            Часть 2. Распределенное программирование

Для вычисления с I i, j ] рабочему процессу Worker [ i, j ] нужно умножить каждый эле­мент строки i матрицы а на соответствующий элемент столбца j матрицы b и сложить ре­зультаты. Однако порядок выполнения операций умножения на результат не влияет! Вопрос в том, как организовать циркуляцию данных между рабочими процессами, чтобы каждый из них получил все необходимые пары чисел.

Для начала рассмотрим процесс Worker [1,1]. Для вычисления значения с [ 1,1 ] этому процессу нужны все элементы строки 1 матрицы а и столбца 1 матрицы Ь.


Вначале у процес­са есть а[1,1] и Ь [ 1,1 ], поэтому их можно сразу перемножить. Если теперь переместиться на 1 вправо по строке матрицы а и вниз по столбцу матрицы Ь, то процесс Worker [1,1] получит значения элементов а[1,2] и Ь[2,1 ], которые можно умножить и прибавить к значению с [ 1,1 ]. Если эти действия повторить еще п-2 раза, перемещаясь вправо по строке матрицы а и вниз по столбцу матрицы Ь, то процесс Worker [1,1] получит все необходимые ему данные.

К сожалению, такая последовательность сдвигов и умножений годится только для процес­са, обрабатывающего диагональные элементы матрицы. Другие рабочие процессы тоже уви­дят необходимые им значения элементов матриц, но в неправильной последовательности. Однако перед началом умножений и перемещений элементы матриц а и Ь можно переупоря­дочить. Для этого нужно сначала циклически сдвинуть строку i матрицы а влево на i столб­цов, а столбец j матрицы Ь вверх на j строк. (Причины, по которым такое перемещение эле­ментов работает, не очевидны; этот порядок перемещения элементов был получен после ис­следований, проведенных для небольших матриц, и обобщения результатов.) Ниже показан результат предварительной перестановки значений матриц а и Ь с размерами 4x4. ai,2, b2,i ai,3, Ьз,2 ai,4, bi,3 ai,i, bi,i

32,3,     Ьз,1         32,4,     bt,2         32,1/     t>l,3         32,2.     Ь2,4

аз,4,   b4,i        аз,1,   bi,2        аз,2,   Ь2,з        аз,з,   Ьз,4

a4,i,   bi.i         34,2,   Ь2,2         а4,з,   Ьз,з         а4,4,   Ьа,4

После предварительной перестановки значений каждый рабочий процесс имеет два зна­чения, которые он записывает в локальные переменные aij и bij. Затем рабочий процесс инициализирует переменную cij значением aij *bij и выполняет п-1 циклов сдвига и ум­ножения. В каждом цикле значения aij передаются на один столбец влево, а значения bij — на строку выше; процесс получает новые значения, перемножает их и прибавляет произведе­ние к текущему значению переменной cij.


Когда рабочие процессы завершаются, произве­дение матриц хранится в переменных cij всех рабочих процессов.

В листинге 9.6 показан код, реализующий этот алгоритм умножения матриц. Рабочие процессы совместно используют п2 каналов для циркуляции данных влево и еще п2 каналов для циркуляции данных вверх. Из каналов формируются 2п пересекающихся циклических конвейеров. Рабочие процессы одной строки связаны в циклический конвейер, через кото­рый данные перемещаются влево; рабочие процессы одного столбца связаны в циклический конвейер, по которому данные идут вверх. Константы LEFT1, UP1, LEFTI и UPJ в каждом ра­бочем процессе инициализируются соответствующими значениями и используются в опера­торах send для индексации массивов каналов.





программа в листинге у.о явно неэффективна (если только она не реализована аппарат-но). В ней используется слишком много процессов и сообщений, а каждый процесс произво­дит слишком мало вычислений. Но этот алгоритм легко обобщается для использования квад­ратных или прямоугольных блоков. Каждый рабочий процесс назначается для блоков матриц а и Ь Рабочие процессы сначала сдвигают свои блоки матрицы а влево на i блоков столбцов, а блоки матрицы Ь — вверх на j блоков строк. Затем каждый рабочий процесс инициализиру­ет свой блок результирующей матрицы с промежуточными произведениями своих новых блоков матриц а и Ь. Затем рабочие процессы выполняют п-1 циклов сдвига матрицы а на блок влево и сдвига матрицы Ь на блок вверх, вычисляют новые промежуточные произведе­ния и прибавляют их к с. Подробности этого процесса читатель может выяснить самостоя­тельно (см. упражнения в конце главы).

Дополнительный способ повысить эффективность кода в листинге 9.6 — выполнять при сдвиге данных оба оператора send до выполнения операторов receive. Изменим последо­вательность операторов

send/receive/send/receive на

send/send/receive/receive.

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


Содержание раздела