2.3. Организация коммуникационной среды в системах

с распределённой памятью.

К настоящему времени разработано множество схем соединений ,

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

пример его структурной реализации на многоступенчатом переключателе показан на рис. 2.7,b. На рисунке представлена система соединения восьми процессоров. Как видно из рис. 2.7,а, всем процессорам присваиваются двоичные номера (Xm-1…X1Xo). Процессор с номером (Xm-1 ... X1Xo) соединяется с т процессорами , для номеров которых расстояние Хемминга равняется 1. В примере на рис. 2.7,а процессор (000) может быть соединен с каждым из процессоров с номерами (001), (010) и (100), а процессор (010) - с любым из процессоров с номерами (011), (000) и (110).

Рассмотрим теперь передачу данных от исходного процессора (Xm-1... X1Xo) в процессор-адресат (Ym-1 ... Y1Y0). Сначала сравниваются биты Xо и Y0 младших разрядов номеров процессоров. При Xо = Y0 данные из процессора (Xm-1 ... X1Xo), передаются в процессор (Xm-1 ... X1Xo) (на рис.2.7,а это обозначено знаком 1 в кружке). При Xо # Yо данные не передаются. Далее, в номерах процессоров (Xm-1 ... X1Xo) и (Ym-1…Y1Y0) сравниваются биты X1 и Y1 и осуществляется аналогичная процедура (на рис. 2.7,а обозначена индексом 2 в кружке). Этот процесс повторяется со всеми парами битов

стр.37

до самого старшего разряда; в результате m-кратного повторения описанной процедуры данные поступают в процессор (Ym-1...Y1Y0). Путь передачи данных от процессора (000) в процессор (111) на

рис. 2.7,a показан утолщенной линией. Рассмотрим реализацию данного способа с использованием многоступенчатого переключателя с m ступенями (log2 n ступеней).

Как видно из рис. 2.7,b , на каждой ступени размещается n/2

переключателей. На каждый из переключателей ступени 0 поступают

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

стр.38

ступени подаютсяданные от двух процессоров с номерами, различающимися значением i-го бита (например, на ступени 1 это (000) и (010), (001) и (Oil) и т.д. Для переключателей ступени i сравниваются бит Xi номера процессора-источника и бит Yi номера процессора-получателя; при Xi=Yi переключатель устанавливается в режим прямой связи, а при Xi не равным Yi - в режим диагональной связи. Таким образом, реализуется отмеченный ранее принцип n-кубической коммутации («прямая связь», когда данные не передаются, и «диагональная связь», когда данные передаются).

Например, при передаче данных из процессора (000) в процессор (111) управление переключателями производится в соответствии с пунктирной линией передачи на рис. 2.7,b. Поскольку для всех переключателей управление их режимов производится на основании сравнения Xi и Y , необходимо снабжать данные заголовком , представляющим собой поразрядную сумму X(Xm-1 ... X1Xо) и Y{Ym-1...Y1Yo) по модулю 2. Со стороны процессора - источника вычисляется Zi = Xi + Yi, где (+ - исключающее ИЛИ), и каждый переключатель при Zi = 0 устанавливается в режим прямой связи, а при Zi = 1 - в режим диагональной связи. Длина заголовка данных не превышает т бит.

При такой многоступенчатой коммутации возможна связь между

любыми процессорами. Однако при одновременной организации связи

между более чем двумя процессорами, как показано на рис. 2.7,b

штрихпунктирной линией , возможны конфликты переключателей

(блокирование). На рис. 2.7,b показана ситуация, когда одновременно

передаются данные от процессора 4 к процессору 0 и от процессора 6 к

процессору 4. При возникновении конфликтов данные запоминаются в

буфере переключателя и ожидают своей очереди на передачу.