ГОСЫ / Parallelnye_vychislenia

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

Анализ трудоемкости основных операций межпроцессорных обменов на примере выполнения коллективных операций передачи данных по схеме “от всех – всем” с рассмотрением обобщенного варианта.

Обобщенная передача данных (all to all) от всех процессоров всем процессорам сети представляет собой общий случай коммуникационных действий. Необходимость в выполнении подобных операций возникает в параллельных алгоритмах быстрого преобразования Фурье, транспонирования матриц и др.

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

1) Передача неделимых сообщений.

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

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

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

Время выполнения передач данных равна:

2) Передача пакетов.

Использование метода передачи пакетов не приводит к улучшению временных характеристик для операции обобщенной передачи данных. Например, для топологии гиперкуб передача может быть выполнена за p-1 последовательных итераций. На каждой итерации все процессоры разбиваются на взаимодействующие пары процессоров. Разбиение на пары может быть выполнено таким образом, чтобы передаваемые между разными парами процессоров сообщения не использовали одни и те же пути передачи данных. В этом случае время выполнения передач данных равно:

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

21

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

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

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

оценка подобного вида следует из соотношений для метода передачи пакетов при единичной длине пути передачи данных, т.е. при l = 1. Это модель, в которой предполагается, что время подготовки

данных - постоянно (не зависит от объема передаваемых данных), время передачи служебных

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

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

2. Поэтому более точная формула будет иметь следующий вид (модель В):

,

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

умолчанию для операционной системы MS Windows в сети Fast Ethernet =1500 байт), а - объем служебных данных в каждом из пересылаемых пакетов (для протокола TCP/IP, ОС Windows 2000 и

сети Fast Ethernet =78 байт). Величина	характеризует	аппаратную составляющую
латентности и зависит от параметров используемого сетевого оборудования, значение			задает
время подготовки одного байта данных для	передачи по	сети. Величина	латентности

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

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

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

22

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

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

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

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

Линейка (linear array or farm) – система, в которой каждый процессор, кроме первого и последнего, имеет линии связи только с двумя соседними. Такая схема просто реализуема, соответствует структуре передачи данных при организации конвейерных вычислений, но крайне не надежна.

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

Кольцо (ring) – получается из линейки процессоров соединением первого и последнего процессоров.

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

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

Гиперкуб (hypercube) – данный вариант широко распространен в практике построения вычислительных

систем и характеризуется рядом признаков:

а) два процессора имеют соединение, если двоичные представления их номеров имеют только одну различающуюся позицию;

б) N-мерный гиперкуб может быть разделен на два (N-1)-мерных гиперкуба (всего возможно N различных разбиений);

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

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

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

23

Двоичный код Грея G(i,N) (binary reflected Gray code) определяется следующими выражениями:

(1)

где i задает номер значения в коде Грея, а N есть длина этого кода. Для иллюстрации подхода показывается отображение кольцевой топологии на гиперкуб для сети из p=8 процессоров.

i	0, 1, 2, 3, 4, 5, 6, 7 - номера вершин кольца
s	1, 2, 3 - т.к. N=3, то i принимает перечисленные значения

G(0,1)=0 G(0,2)=G(0,1)=0 G(0,3)= G(0,2)=G(0,1)=0

G(1,1)=1 G(1,2)=G(1,1)=1 G(1,3)= G(1,2)=G(1,1)=1

Рассмотрим G(2,1). По формуле (1) 2>=21 , тогда G(2,1)= 21 +G(22-1-2,1)=3 G(2,2)=G(2,1)=3 G(2,3)= G(2,2)=G(2,1)=3

Рассмотрим G(3,1). По формуле (1) 3>=21 , тогда G(3,1)= 21 +G(22-1-3,1)=2 G(3,2)=G(3,1)=2 G(3,3)= G(3,2)=G(3,1)=2

Рассмотрим G(4,3). По формуле (1) 4<23 , тогда G(4,3)=G(4,2)

Рассмотрим G(4,2). По формуле (1) 4>=22 , тогда G(4,2)= 22 +G(23-1-4,2)=4+G(3,2)=6

Рассмотрим G(5,3). По формуле (1) 5<23 , тогда G(5,3)=G(5,2)

Рассмотрим G(5,2). По формуле (1) 5>=22 , тогда G(5,2)= 22 +G(23-1-5,2)=4+G(2,2)=7

Рассмотрим G(6,3). По формуле (1) 6<23 , тогда G(6,3)=G(6,2)

Рассмотрим G(6,2). По формуле (1) 6>=22 , тогда G(6,2)= 22 +G(23-1-6,2)=4+G(1,2)=5

Рассмотрим G(7,3). По формуле (1) 7<23 , тогда G(7,3)=G(7,2)

Рассмотрим G(7,2). По формуле (1) 7>=22 , тогда G(7,2)= 22 +G(23-1-7,2)=4+G(0,2)=4

Результат представлен в таблице.

я для N=1	ея для N=2	ея для N=3	омера процессоров
			перкуба	льца
0	0 0	0 0 0	0	0
1	0 1	0 0 1	1	1
	1 1	0 1 1	3	2
	1 0	0 1 0	2	3
		1 1 0	6	4
		1 1 1	7	5
		1 0 1	5	6
		1 0 0	4	7

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

Отображение топологии решетки на гиперкуб

Отображение топологии решетки на гиперкуб может быть выполняется аналогично кольцевой топологии. Тогда при отображении решетки на гиперкуб размерности 2r x 2s на гиперкуб размерности N=r+s элементу решетки с координатами (i,j), будет соответствовать процессор гиперкуба с номером G(i,j)||G(j,s), где операция || означает конкатенацию кодов Грея.

24