Коммутирующее устройство для многопроцессорной вычислительной системы Советский патент 1986 года по МПК H03K17/00 

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

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

На фиг, i изображена структурная схема ком1-1утирующего устройства для многопроцессорной вычислительной системы, содержащего три каскада KONMyTaTopoB, соответственно, два каскада из г коммутаторов (п х п) и один кйскад из п коммутаторов (гхг) на фиг. 2 структурная схема потакт ного моделирования в двухкоординат- ном устройстве работы известного трехкаскадного коммутирующего устройства; на фиг, 3 и 4 - геометрическая Модель двухкоординатного и трехкоординатного коммутирующих устройств J на фиг 8 5 и б - структурные схемы пятикаскадного и девятикаскад™ ного устройств, на которых штрих- пунктирньши линиями указаны места . подключения вентилей, а также вход- и выходных шин дроцессорово

Ког-шутирунядее устройство содержит первые выходные шины процессоров, объединенные в группы 2 первых выходных шин, пронумерованные с 2-1 по 2-г, причем первые выходные шины внутри своей группы пронумерованы с 1 - 1 до 1-п; первые входные :иины 3 . процессоров3 объединенные в группы 4 первьи входных шин, пронумерованные с 4-1 по причем первые входные шины 3 внутри своей группы пронумерованы с 3-1 по 3-п; п квадратньк коммутаторов 5 размера (г х г) пронумерованных е 5 по 5-п, входы в которых пронумерованы с 6-1 по 6-г, а выходы 7 - с по 7-г; г квадратX п),

ных коммутаторов 8 размера (п пронумерованных с 8-1 по S-r, вхюДы 9 которых пронумерованы с 9-1 по

а выходы 10 которых пронумерованы с 0-1 по 10-п; вторые выходные шины 11 процессоров, объединенные в группы 12 вторых выходных шин, пронумерованные с 12-1 по 12-г, причем вторые выходные шины М внутри своей группы пронумерованы с 1J-1 по вторые входные шины J3 процессоров, объединеншзЮ в группы 14 вторы, входных шин, пронумерованные с 14-1 по 14-г, причем вторые входные шины 13 внутри своей группы пронумер.ованы с 13-1 по вентили 15, г групп которых пронумерованы с J5-1 по IS-r

а сами Е:ентили внутри J-й группы

пронум,ерованы с I5-J-I TIO причем вход 9-i коммутатора 8-j подключен к первой выходной пшне.1-i группы 2-J первых выходных шин, выход

10-1 коммутатора 8-j соединен с первой входной шиной 3-i группы 4-J первых входных шин, вход 6-J коммутатора 5-1 подключен к второй выходной шине 11-1 группы 12-J вторых выходных

шин, а выход 7-J коммутатора 5-1 соединен с второй входной шиной 13-1 группы 14-,1 вторых входных шин процессоров г дополнительных коммутаторов ,16 размера (п х п) пронумеро-

ванных с 16-1 по 16-г, входы 17 которых пронумерованы с 17-1 по 17-п, а выходы 18 пронумерованы с 18-1 по 18-п, третьи выходные шины 19 процессоров, объединенные в группы 20

третьих выходных шин, пронумерованные с по 20-г, причем третьи выходные ш:ины 19 внутри-,с-воей группы пронумерованы с 19-1 по l-9-n, третьи входные шины 21 процессоров, объединенные в группы 22 третьих входных шин,, пронумерованных с 22-,1 па 22-г, причем третьи входные шины 21 внутри своей группы пронумерованы с 21-1 по 21-П5 дополнительные вентили 23 г

групп которых пронумерованы с 23-1 по 23-г. а дополнительные вентили внутри j-й группы пронумерованы с 23-J-1 по 23-j-n5 вторая входная 13--i шина группы 14-j вторых входных шин процессоров подключена через вентиль 23-j-i - к третьей выходной шине 19--1 группы 20-J третьих входййх

шин процессоров,

В качестве коммутаторов (п х п)

и

(г X г,1 могут использоваться любые в:еблокирующие коммутаторы указанной размерности, например, перекрестные коммутаторы, матричные переключатели, кольцевые сдвиговые регистры, в т.ч.

и многокаскадные коммутирующие устройства.

Устройство работает следующим образом.

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

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

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

5 5 0

5

0

5

0

5

0

В двухкаскадном устройстве можно вьшолнить перестановку данных произвольного вида за два такта: на первом такте реализуется частичная перестановка данных, которая соответствует .перестановке, выполняемой в первых двух каскадах коммутаторов в известном устройстве,(в этом случае инфор- мадионный сигнал испытывает задержку не только в коммутаторах размера (п X п) и (г X г), но и в вентилях 15); на втором такте перестановка данньгх заканчивается (реализуется перестановка данных, вьтолняемая в третьем каскаде коммутаторов известного устройства после предварительной перенастройки коммутаторов размера (п X п) на перестановку третьего каскада).

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

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

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

Во всех ош- санных выше вариантах предлагаемое устройство содержит меньше коммутаторов, чем известноеj за счет исключения в нем всех ком мутаторов,, расположенных в известном устройстве после среднего каскада. При выполнении пересылок данных произвольного вида такое исключение становится возможным благодаря повторному использованию каскадов коммутаторов, расположенных в известном устройстве до среднего каскада. С увеличением количества каскадов Koi MyTa торов количество тактов, затрачивае- мьк на выполнение пересьшки данных произвольного зидав возрастает в чигшо раз,-, равное числу каскадов, имеюпщхся э соответствующем: варианте известного устройства, а время одного такта примерно во столько же раз уменьшается о Таким образом, время выполнения перестановки данных про- . извольного вида., если ке учитывать весьма непродолжительные по времени пересылки данных с входных тин на выходные, в данном и известном устройствах примерно одно и Т О же.

Перестановв:к данных регулярного вида выполняются в устройстве следующим образомо

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

447896

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

Эффект упрощения программирования и повышения быстроде.йствия за счет ускорения по.лучения кодов настройки в двухкаскадном устройстве по сравнению с известным трехкаскадньп- уст- . ройством нагляден на примере реализации базового алгоритма быстрого преобразования Фурье (ВПФ), При реализации БПФ на каждом очередном шаге вычислений выполняются взаимные перестановки данных меладу парами процессоров, разность номеров которьгх для всех пар одинакова и равна 2 ., где I: - номер очередного шага вьмислений, Число С 1, 2, З.,.,,. где Р , а Н - размерность вычисляемого спектра БПФо Например, Б том случае пели вычисляется спектр, БПФ размерностью N 1024, то Р log- 024 i CU Пусть, пре.длагаемое двух- групповое: коммутирующее устройство реализует коммутатор 1024 х 1024 и пусть такие размерности используемых. в нем коммутаторов (г х г) и (п х п) являются числами, выраженнами степенью числа 2, например г 256, а п 16 В рассматриваемом случае на первом четвертом шагах вычислений пе.рестановки данных выполняются с

7

помощью коммутаторов (п х п), , 16 X 16, Разность номеров пар процессоров на первом-чствертом шагах вычислений равна 2 , где 2 I, 2, 4, 8, На пятом - восьмом шагах равна где 2 16, 22, 64j 126, На девятом и десятом шагах вычислений снова используются коммутаторы (п .х п), т,е, (16 X 16), Разность номеров пар процессоров -равна 2, где 2 256, 512 Таким образом, на каждом шаге вычислений выполняются пересьшки данных . только по вертикальным, либо только по горизонтальным стержням, т,е, все перестановки данных выполняются за один такт внутри одного каскада. Можно показать, что пересьшки данньп на первом - четвертом и девятом - десятом шагах выполняю1 ся только вну .три стоек, т.е. с -большей тактовой частотой, чем в известных устройствах.

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

510 t5 20

25 о ,

35

0

5

0

5

789 - 8

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

Формула изобретения

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

с целью упрощения устройства с одно- вpeмeнны i повышением быстродействия, в него введено пг вентилей, причем i-й вход j-ro коммутатора размера (п X п) соединен с первой выходной шиной i-ro процессора j-й группы, а j-й вход и j-й выход i-ro коммутатора размера (г х г) подключены соответственно к второй выходной и второй входной шинам i-ro процессора j-й группы, причем первая входная шина каждого процессора подключена к его второй выходной шине через соответствующий вентгшь.

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

j-1 g-.

W-J 3-7

I

H 3-i

l-f S:

у-г

fO Э-i

7 ff j1-i

1-1 9-i

fO l 3-f

гг S-;

tO-2 y-f

-i 9-1

e-f

a-t

/// Л7-/

If- 17-2

19-i 17-L

13-n 7-fi

If-I

Lt

г;-I

m.

tl-2

rs-i. a-i

гг-f

V-f 7-l

re-t jt

Л

а-г

te-ill-i

гг-г

Изобретение относится к устройствам автоматической цифровой коммутации. Может быть использ.овано в составе микропроцессорных вычислитель ных систем для межблочногообмена данными. Целью изобретения является упрощение устройства с одновременным повышением быстродействия. Кроме того, в устройстве обеспечивается упрощение. программирования и диагностирования за счет организации передачи данных не через все, а только через заданные каскады коммутаторов, одновременная пересыпка данных по сокращенным путям, а также выполнение регулярных перестановок,данных между всеми процессорами и произвольные перестановки данных между некоторыми процессорами. Структурная схема устройства содержит два каскада из г коммутаторов размера (п X п) и один каскад из г коммутаторов размера (п х п), где г и п являются целыми числами, вьфаженными степенью числа 2. В качестве коммутаторов (пхп) и(гхг) могут использоваться любые неблокирующие коммута- торы указанной размерности, например перекрестные коммутаторы, матричные переключатели, кольцевые сдвиговые регистры. Структурные схемы устройства, . а также потактного моделирования, схемы пяти и девяти каскадных устройств и геометрические модели 2- и 3-коор- динатного коммутирующего устройства .приводятся в описании изобретения. 1 з.п. ф-лы, 6 ил. с е сл 4;: 00 ;о

t-1 t

is-j г-/

г-г f

t-i J-4J

l-n . tf;/г

в-i

1

j-г

j-t

,03-n

,

m-i 3-1

г-1

If f

1-1 i-i

f-n. 3-,

8-1

w-t 1-г

fo- :j-i

w-g :з./

4-/

/77

/Г

J28

ff9

728

if-ua

5/г

4РЯ:

MS6«ОМ

Составитель С. Куст Редактор М. Товтин Техред Н.Бонкало Корректор0. Луговая

Заказ 3927/58 Тираж 816 Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий . 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4