Источник: http://studdi.ru/lection/avs/lection8.html
Авторы: studdi.ru

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

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

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

Для гиперкуба покоординатная схема маршрутизации может состоять, например, в циклической передаче данных процессору, определяемому первой различающейся битовой позицией в номерах процессоров, на котором сообщение располагается в данный момент времени и на который сообщение должно быть передано.
 
Методы передачи данных
 
Время передачи данных между процессорами определяет коммуникационную составляющую (communication overhead) длительности выполнения параллельного алгоритма в многопроцессорной вычислительной системе. Основной набор параметров, описывающих время передачи данных, состоит из следующего ряда величин:
К числу наиболее распространенных методов передачи данных относятся следующие два основные способа коммуникаций. Первый из них ориентирован на передачу сообщений (МПС) как неделимых (атомарных) блоков информации. При таком подходе процессор, содержащий сообщение для передачи, готовит весь объем данных для передачи, определяет процессор, которому следует направить данные, и запускает операцию пересылки данных. Процессор, которому направлено сообщение, в первую очередь осуществляет прием полностью всех пересылаемых данных и только затем приступает к пересылке принятого сообщения далее по маршруту. Время пересылки данных tпд для метода передачи сообщения размером m байт по маршруту длиной l определяется выражением 
tпд = tн + (mtк + tc)l
При достаточно длинных сообщениях временем передачи служебных данных можно пренебречь и выражение для времени передачи данных может быть записано в более простом виде
tпд = tн + mtкl
Второй способ коммуникации основывается на представлении пересылаемых сообщений в виде блоков информации меньшего размера (пакетов), в результате чего передача данных может быть сведена к передаче пакетов (МПП). При таком методе коммуникации (cut-through routing or CTR) принимающий процессор может осуществлять пересылку данных по дальнейшему маршруту непосредственно сразу после приема очередного пакета, не дожидаясь завершения приема данных всего сообщения. Время пересылки данных при использовании метода передачи пакетов будет определяться выражением
tпд = tн + mtк + tcl
Сравнивая полученные выражения, можно заметить, что в большинстве случаев метод передачи пакетов приводит к более быстрой пересылке данных; кроме того, данный подход снижает потребность в памяти для хранения пересылаемых данных для организации приема-передачи сообщений, а для передачи пакетов могут использоваться одновременно разные коммуникационные каналы. С другой стороны, реализация пакетного метода требует разработки более сложного аппаратного и программного обеспечения сети, может увеличить накладные расходы (время подготовки и время передачи служебных данных); при передаче пакетов возможно возникновения конфликтных ситуаций (дедлоков).
Основными характеристиками быстродействия сети являются латентность (latency) и пропускная способность (bandwidth).
Под пропускной способностью R сети будем понимать количество информации, передаваемой между узлами сети в единицу времени (байт в секунду). Очевидно, что реальная пропускная способность снижается программным обеспечением за счет передачи разного рода служебной информации.
Латентностью (задержкой) называется время, затрачиваемое программным обеспечением и устройствами сети на подготовку к передаче информации по данному каналу. Полная латентность складывается из программной и аппаратной составляющих.
Различают следующие виды пропускной способности сети:
Значения пропускной способности будем выражать в мегабайтах в секунду (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 и т.д. Трудоемкость выполнения операции рассылки при таком методе передачи данных определяется соотношением
(как и ранее, при достаточно больших сообщениях, временем передачи служебных данных можно пренебречь).
Для топологии типа решетки-тора алгоритм рассылки может быть получен из способа передачи данных, примененного для кольцевой структуры сети, в соответствии с тем же способом обобщения, что и в случае использования метода передачи сообщений. Получаемый в результате такого обобщения алгоритм рассылки характеризуется следующим соотношением для оценки времени выполнения:
Для гиперкуба алгоритм рассылки (и, соответственно, временные оценки длительности выполнения) при передаче пакетов не отличается от варианта для метода передачи сообщений.
 
Сложные задачи. Масштабируемость параллельных вычислений. Функция изоэффективности
 
Эффективность функционирования вычислительных систем зависит от количества операций, которые требуется выполнить при решении задач и   от    числа     вычислителей,     на     котором       реализуются     P-алгоритмы    (точнее P-программы), от степени адекватности вложения структурных схем алгоритмов решения в структуры ВС. Среди показателей качества P-алгоритмов используют коэффициент накладных расходов, который представим в виде:
 
где V – количество операций, которые необходимо выполнить при решении задачи на ВС; n – число параллельных ветвей или число вычислителей, на которых решается задача, n≥2;
t(V,n) – время, затрачиваемое на:
T(V,n) – время, расходуемое системой собственно на счет.
            На основе анализа задач и опыта их решения (с использованием методики крупноблочного распараллеливания) на вычислительных системах установлено, что при n = const показатель ε(V,n) асимптотически стремится к нулю с ростом объема операций в задаче, т.е. имеет место: ε(V,n) → 0 при V → ∞. Значения ε(V,n) будут практически удовлетворительными при выполнении неравенства
V ≥n*10k
где k – эмпирический коэффициент, k≥1. Очевидно, что имеет место зависимость k от быстродействия ν каналов связей между вычислителями: k→ 1 при ν → ν*, где 1/ν* – время обращения к локальной памяти в вычислителе. При удовлетворении неравенства достигается адекватное размещение параллельной программы на системе из n вычислителей (при произвольной структуре сети связей) и обеспечивается эффективное использование этих вычислителей.
            Таким образом, если объем операций V, связанных с решением задачи, на несколько порядков превышает число вычислителей n, на которых должно осуществляться её решение, то достигается эффективное функционирование системы.
            Задачу, для которой выполняется последнее неравенство, будем называть сложной, или системной, или трудоемкой, или с большим объемом вычислений. Сложность задачи будем характеризовать количеством операций, которые необходимо выполнить при ее решении. Задача тем сложнее, чем больше V. Задачу, которая имеет небольшой объем вычислений и, следовательно, не допускает эффективного распараллеливания, будем называть простой. Простая задача требует для своего решения одного вычислителя.
                 Анализ масштабируемости параллельных вычислений
Целью применения параллельных вычислений во многих случаях является не только уменьшение времени выполнения расчетов, но и обеспечение возможности решения более сложных вариантов решаемых задач (таких постановок, решение которых не представляется возможным при использовании однопроцессорных вычислительных систем). Способность параллельного алгоритма эффективно использовать процессоры при повышении сложности вычислений является важной характеристикой выполняемых расчетов. В связи с этим, параллельный алгоритм называют масштабируемым (scalable), если при росте числа процессоров он обеспечивает увеличение ускорения при сохранении постоянного уровня эффективности использования процессоров. Возможный способ характеристики свойств масштабируемости состоит в следующем.
Оценим накладные расходы (total overhead), которые имеют место при выполнении параллельного алгоритма
T0 = pTp – T1
Накладные расходы появляются за счет необходимости организации взаимодействия процессоров, выполнения некоторых дополнительных действий, синхронизации параллельных вычислений и т.п. Используя введенное обозначение, можно получить новые выражения для времени параллельного решения задачи и соответствующего ускорения:
Tp = (T1+T0)/p,
Sp = T1/Tp = pT1/(T1+T0)
Используя полученные соотношения, эффективность использования процессоров можно выразить как
Ep = Sp/p = T1/(T1+T0) = 1/(1 + T0/T1)
Последнее выражение показывает, что если сложность решаемой задачи является фиксированной (T1=const), то при росте числа процессоров эффективность, как правило, будет убывать за счет роста накладных расходов T0. При фиксации числа процессоров эффективность использования процессоров можно улучшить путем повышения сложности решаемой задачи T1 (предполагается, что при росте параметра сложности n накладные расходы T0 увеличиваются медленнее, чем объем вычислений T1). Как результат, при увеличении числа процессоров, в большинстве случаев можно обеспечить определенный уровень эффек4тивности при помощи повышения сложности решаемых задач. В этой связи, важной характеристикой параллельных вычислений становится соотношение необходимых темпов роста сложности расчетов и числа используемых процессоров.
Пусть E=const есть желаемый уровень эффективности выполняемых вычислений. Из выражения для эффективности можно получить
T0/T1 = (1-E)/E или
T1 = KT0, K=E/(1-E)
Порождаемую последним соотношением зависимость n=F(p) между сложностью решаемой задачи и числом процессоров обычно называют функцией изоэффективности.
 
 Литература:
 
Гергель, В. Теория и практика параллельных вычислений / В.П. Гергель. - Бином. Лаборатория знаний, 2007. - 424 с.
Хорошевский, В. Архитектура вычислительных систем / В.Г. Хорошевский. Москва: МГТУ им. Баумана, 2008. - 520 с.