Алгоритмы маршрутизации. Методы передачи данных. Передача данных между двумя процессорами и широковещательная передача

Алгоритмы маршрутизации. Методы передачи данных. Передача данных между двумя процессорами и широковещательная  передача

Латентность и пропускная способность сети 

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

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

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

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

Методы передачи данных 

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

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

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

t_пд = t_н + (mt_к + t_c)l

При достаточно длинных сообщениях временем передачи служебных данных можно пренебречь и выражение для времени передачи данных может быть записано в более простом виде

t_пд = t_н + mt_кl

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

t_пд = t_н + mt_к + t_cl

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

Основными характеристиками быстродействия сети являются латентность (latency) и пропускная способность (bandwidth).

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

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

Различают следующие виды пропускной способности сети:

• пропускная способность однонаправленных пересылок («точка-точка», uni-directional bandwidth), равная максимальной скорости, с которой процесс на одном узле может передавать данные другому процессу на другом узле;
• пропускная способность двунаправленных пересылок (bi-directional bandwidth), равная максимальной скорости, с которой два процесса могут одновременно обмениваться данными по сети.

Значения пропускной способности будем выражать в  мегабайтах в секунду (MB/sec), значения латентности – в микросекундах (msec = 10^-6 sec).

Время T(L), необходимое на передачу сообщения длины L, можно определить следующим образом:

T(L)=s+L/R,

где s - латентность, а R - пропускная способность.

Для приложений с тонкой параллельной структурой (fine-grained parallelism), какими, как правило, являются вычислительные программы, крайне важны малые величины латентности; тогда как для приложений, использующих большие объемы пересылок (а это, как правило, коммерческие приложения БД), более важно максимальное увеличение пропускной способности. 

Передача данных между двумя процессорами и широковещательная  передача 

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

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

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

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

 

 

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

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

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

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

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

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

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

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

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

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

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