Анализ трудоемкости основных операций передачи данных 38

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

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

..Передача данных между двумя процессорами сети

Трудоемкость данной коммуникационной операции может быть получена путем подстановки длины максимального пути (диаметра сети - см. табл. 3.1) в выражения для времени передачи данных при разных методах коммуникации (см. п. 3.2).

Таблица 3.2. Время передачи данных между двумя процессорами

Топология	Передача сообщений	Передача пакетов
Кольцо	tн + mtк(p / 2)	tн + mtк + tс(p / 2)
Решетка-тор	tн + 2mtк( / 2)	tн + mtк + 2tс( / 2)
Гиперкуб	tн + mtк log p	tн + mtк + tс log p

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

Операция передачи данных (одного и того же сообщения) от одного процессора всем остальным процессорам сети (one-to-all broadcast or single-node broadcast) является одним из наиболее часто выполняемых коммуникационных действий; двойственная операция передачи - прием на одном процессоре сообщений от всех остальных процессоров сети (single-node accumulation). Подобные операции используются, в частности, при реализации матрично-векторного произведения, решении систем линейных уравнений при помощи метода Гаусса, поиска кратчайших путей и др.

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

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

t_пд = (t_н + mt_к)(p / 2) .

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

t_пд = 2(t_н + mt_к)( / 2) .

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

t_пд = (t_н + mt_к) log p .

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

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

t_пд = (t_н + mt_к + t_с p / 2ⁱ) = (t_н + mt_к) log p + t_с(p – 1)

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

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

t_пд = (t_н + mt_к) log p + 2t_с( – 1) .

Для гиперкуба алгоритм рассылки (и, соответственно, временные оценки длительности выполнения) при передаче пакетов не отличается от варианта для метода передачи сообщений.

..Передача данных от всех процессоров всем процессорам сети

Операция передачи данных от всех процессоров всем процессорам сети (all-to-all broadcast or multinode broadcast) является естественным обобщением одиночной операции рассылки; двойственная операция передачи - прием сообщений на каждом процессоре от всех процессоров сети (multinode accumulation). Подобные операции широко используются, например, при реализации матричных вычислений.

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

1. Передача сообщений. Для кольцевой топологии каждый процессор может инициировать рассылку своего сообщения одновременно (в каком-либо выбранном направлении по кольцу). В любой момент времени каждый процессор выполняет прием и передачу данных; завершение операции множественной рассылки произойдет через (p – 1) цикл передачи данных. Длительность выполнения операции рассылки оценивается соотношением:

t_пд = (t_н + mt_к)(p – 1) .

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

t^'_пд = (t_н + mt_к)( – 1) .

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

t^''_пд = (t_н + m t_к)( – 1) .

Как результат, общая длительность операции рассылки определяется соотношением:

t_пд = 2t_н( – 1) + mt_к(p – 1) .

Для гиперкуба алгоритм множественной рассылки сообщений может быть получен путем обобщения ранее описанного способа передачи данных для топологии типа решетки на размерность гиперкуба N. В результате такого обобщения схема коммуникации состоит в следующем. На каждом этапе i, 1 ≤ i ≤ N, выполнения алгоритма функционируют все процессоры сети, которые обмениваются своими данными со своими соседями по i размерности и формируют объединенные сообщения. Время операции рассылки может быть получено при помощи выражения

t_пд = (t_н + 2^i-1mt_к) = t_н log p + mt_к(p – 1)

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

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

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

t_пд = (t_н + t_к) log p .

Другим типовым примером используемости операции множественной рассылки является задача нахождения частных сумм последовательности значений S_i (в зарубежной литературе эта задача известна под названием prefix sum problem)

S_k = x_i, 1 ≤ k ≤ p

(будем предполагать, что количество значений совпадает с количеством процессоров, значение x_i располагается на i процессоре и результат S_k должен получаться на процессоре с номером k).

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

..Обобщенная передача данных от одного процессора всем остальным процессорам сети

Общий случай передачи данных от одного процессора всем остальным процессорам сети состоит в том, что все рассылаемые сообщения являются различными (one-to-all personalized communication or single-node scatter). Двойственная операция передачи для данного типа взаимодействия процессоров - обобщенный прием сообщений (single-node gather) на одном процессоре от всех остальных процессоров сети (отличие данной операции от ранее рассмотренной процедуры сборки данных на одном процессоре (single-node accumulation) состоит в том, что обобщенная операция сборки не предполагает какого-либо взаимодействия сообщений (типа редукции) в процессе передачи данных).

Трудоемкость операции обобщенной рассылки сопоставима со сложностью выполнения процедуры множественной передачи данных. Процессор-инициатор рассылки посылает каждому процессору сети сообщение размера m и, тем самым, нижняя оценка длительности выполнения операции характеризуется величиной mt_k(p – 1).

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

t_пд = t_н log p + mt_k(p – 1)

(как и отмечалась выше, трудоемкость операции совпадает с длительностью выполнения процедуры множественной рассылки).

#######################################################################################

..Оценка трудоемкости операций передачи данных для кластерных систем 40

Для кластерных вычислительных систем (см. п. 1.3) одним из широко применяемых способов построения коммуникационной среды является использование концентраторов (hub) или переключателей (switch) для объединения процессорных узлов кластера в единую вычислительную сеть. В этих случаях топология сети кластера представляет собой полный граф, в котором, однако, имеются определенные ограничения на одновременность выполнения коммуникационных операций. Так, при использовании концентраторов передача данных в каждый текущий момент времени может выполняться только между двумя процессорными узлами; переключатели могут обеспечивать взаимодействие нескольких непересекающихся пар процессоров.

Другое часто применяемое решение при создании кластеров состоит в использовании метода передачи пакетов (реализуемого, как правило, на основе протокола TCP/IP) в качестве основного способа выполнения коммуникационных операций.

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

t_пд(m) = t_н + mt_k + t_с,

оценка подобного вида следует из соотношений для метода передачи пакетов при единичной длине пути передачи данных, т.е. при l = 1. Отмечая возможность подобного подхода, вместе с этим можно заметить, что в рамках рассматриваемой модели время подготовки данных t_н предполагается постоянным (не зависящим от объема передаваемых данных), время передачи служебных данных t_с не зависит от количества передаваемых пакетов и т.п. Эти предположения не в полной мере соответствуют действительности и временные оценки, получаемые в результате использования модели, могут не обладать необходимой точностью.

2. Учитывая все приведенные замечания, схема построения временных оценок может быть уточнена; в рамках новой расширенной модели трудоемкость передачи данных между двумя процессорами определяется в соответствии со следующими выражениями (модель В):

,

где n = m / (V_max – V_с) есть количество пакетов, на которое разбивается передаваемое сообщение, величина V_max определяет максимальный размер пакета, который может быть доставлен в сети (по умолчанию для операционной системы MS Windows в сети Fast Ethernet V_max = 1500 байт), а V_с есть объем служебных данных в каждом из пересылаемых пакетов (для протокола TCP/IP, ОС Windows 2000 и сети Fast Ethernet V_с = 78 байт). Поясним также, что в приведенных соотношениях константа t_нач0 характеризует аппаратную составляющую латентности и зависит от параметров используемого сетевого оборудования, значение t_нач1 задает время подготовки одного байта данных для передачи по сети. Как результат, величина латентности

t_н = t_нач0 + ν· t_нач1

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

t_н = t_нач0 + (V_max – V_с)· t_нач1

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

(m + V_с· n) ·t_к

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

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

t_пд(m) = t_н + m / R,

где R есть пропускная способность сети передачи данных.

4. Для проверки адекватности рассмотренных моделей реальным процессам передачи данных приведем результаты выполненных экспериментов в сети многопроцессорного кластера Нижегородского университета (компьютеры IBM PC Pentium 4 1300 Mгц, 256 MB RAM, 10/100 Fast Etherrnet card). При проведении экспериментов для реализации коммуникационных операций использовалась библиотека MPI [1].

Часть экспериментов была выполнена для оценки параметров моделей:

• значение латентности t_н для моделей А и С определялось как время передачи сообщения нулевой длины;
• величина пропускной способности R устанавливалась максимально наблюдаемой в ходе экспериментов скорости передачи данных, т.е.

R = (t_пд(m) / m),

• значения величин t_нач0 и t_нач1 оценивались при помощи линейной аппроксимации времен передачи сообщений размера от 0 до V_max.

В ходе экспериментов осуществлялась передача данных между двумя процессорами кластера, размер передаваемых сообщений варьировался от 0 до 8 Мб. Для получения более точных оценок выполнение каждой операции осуществлялось многократно (более 100000 раз), после чего результаты временных замеров усреднялись. Для иллюстрации ниже приведен результат одного эксперимента, при проведении которого размер передаваемых сообщений изменялся от 0 до 1500 байт с шагом 4 байта.

Рис. 3.3. Зависимость экспериментального времени и времени, полученного по моделям A, B, C, от объема данных

В табл. 3.3 приводятся ряд числовых данных по погрешности рассмотренных моделей трудоемкости коммуникационных операций (величина погрешности дается в виде относительного отклонения от реального времени выполнения операции передачи данных).

Таблица 3.3. Погрешность моделей трудоемкости операций передачи данных (по результатам вычислительных экспериментов)

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

#######################################################################################

..Параллельные численные методы для решения типовых задач вычислительной математики 41