Коммутирующее устройство для многопроцессорной вычислительной системы

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕОТУБЛИН (19) (1И (511 4 Н 03 К 177/00

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ. (21) 3857337/24-21 (22) 19.02.85 (46) 15,07.86. Бюл. В 26

:(71) Ордена Ленина институт проблем управления (72) А. А. Чудин и Ю. И. Тараторин (.53) 621.382(088.8) (56) Clos. А Study of nonblocking

svitching netvorks. — Bell Syst. Tech.

7 Vol. 3, рр. 406-424, 1953.

Georgy Broomell and J. Robert

Heath. Classification Categories

and Historical Development of Circuite Svitching Topologies — АСМ Computing Survey, 15, 1983, June, 9 2, (54) КОММУТИРУ10111ЕЕ УСТРОЙСТВО ДЛЯ

МНОГОПРОЦЕССОРНОЙ, ВЫЧИСЛИТЕЛЬНОЙ СИСТЕИЫ (57) Изобретение относится к устройствам автоматической цифровой коммутации. Может быть использовано в составе микропроцессорных вычислительных систем для межблочного обмена данными. Целью изобретения является упрощение устройства с одновременным повышением быстродействия. Кроме того, в устройстве обеспечивается упрощение программирования и диагностирования за счет органиэации передачи данных не через все, а только через заданные каскады коммутаторов, одновременная пересылка данных по сокращенным путям, а также выполнение регулярных перестановок, данных между всеми процессорами и произвольные перестановки данных между некоторыми процессорами.

Структурная схема устройства содержит два каскада из г коммутаторов размера (п х n) и один каскад из r коммутаторов размера (n x n), где r и и являются целыми числами, выраженными степенью числа 2. В качестве коммутаторов (n х п) и (r х r) могут исполь- g эоваться любые неблокирующие коммута- торы указанной размерности, например перекрестные коммутаторы, матричные переключатели, кольцевые сдвиговые регистры. Структурные схемы устройства, . а также потактного моделирования, схемы пяти и девяти каскадных устройств и геометрические модели 2- и 3-координатного коммутирующего устройства приводятся в описании изобретения.

1 з.п. ф-лы, 6 ил.

1244789

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

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

На фиг. 1 изображена структурная схема коммутирующего устройства для многопроцессорной вычислительной системы, содержащего три каскада коммутаторов, соответственно, два каскада из r коммутаторов (п х n) и один каскад из « коммутаторов (Г х Г) на фиг. 2 — структурная схема потактного моделирования в двухкоординатном устройстве работы известного трехкаскадного коммутирующего устройст«а; на фиг„ 3 и 4 — геометрическая модель,1«ухкоординатного и трехкоординатного коммутирующих устройств, ня Оиг, 5 и 6 -- структурные схемы пятикаскадного и девятикаскадного устройств, на которых штрихnyнктирными линиями указаны места подключения вентилей, а также входных и Выходных шин процессоров.

Коммутирующее устройство содержит первые выходные шины 1 процессоров., объединенные в группы ? первых выходных шин, пронумерованные с 2-1 по

2-Г, причем первые выходные шины 1 внутри своей группы пронумерованы с

1-1 до 1-n, первые входные шины 3 процессоров, объединенные в группы 4 первых входных шин, пронумерованные с 4-I no - ;-Г., причем первые входные шины 3 внутри своей группы:пронумеровапы с 3-1 по 3-и; и квадратных коммутаторов 5 размера (r x Г), пронумерованных с 5-1 Во 5-и> входы в которых пронумерованы с 6-1 по 6-r а выходы 7 — с 7-1 по 7-Г; r квадратнь|х коммутаторов 8 размера (n x n), пронумерованных с 8-1 по 8-r, входы

9 которых пронумерованы с 9-1 по 9-п, а выходы 10 которых пронумерованы с

10-1 ло 10-и; вторые выходные шины

11 процессоров, объединенные в группы 12 вторых выходных шин, пронумерованные с 12-1 по 12-Г, причем вто-. рые выходные шины 11 внутри своей группы пронумерованы с 11-1 по 11-и; вторые входные шины l3 процессоров, объединенные в группы 14 вторьж входных шин, пронумерованные с 14-1 по

l4-r, причем вторые входные шины 13 внутри своей группы пронумерованы с

13-1 по 13-п, вентили 15, r групп которых пронумерованы с 15-! по 15-r а сами вентили внутри )-й группы пронумерованы с 15-)-I по 15-1-n причем вход 9-i коммутатора 8-1 подклю-. чен к первой выходной шине.1-i группы 2-1 первых выходных шин, выход

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

5 шин, а выход 7-) коммутатора 5-i соединен с второй входной шиной 13-i группы 14-,j вторых входных шин, процессоров r дополнительных коммутаторов 16 размера (n x n) пронумерованных с 16-1 ПО 16-Гр Входы 17 кОторых пронумерованы с 17-1 по 17-п, а выходы 18 пронумерованы с 18-1 по

18-п, третьи выходные шины 19 процессоров, объединенные в группы 20 третьих выходных шин, пронумерованные с ?0-1 по 20-Г, причем третьи выходные шины 19 внутри;своей группы пронумерованы с 19-1 по l 9-п, третьи входные шины 21 процессоров, объеди ненные в группы 22 третьих входных шин, пронумерованных с 22-1 па 22-r, причем третьи входные шины 21 внутри с«оей группы пронумерованы с 21-1 по

21-п дополнительные вентили 23, Г гругп которых пронумерованы с 23-1

:;o 23--, а. сами дополнительные вентили «путри,1-й группы пронумерованы с 23-,I-I по 23-g-п, вторая входная

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

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

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

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

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

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

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

n ) r также является неблокирующим, как и известное.

S

2S

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

15); на втором такте перестановка данных заканчивается (реализуется перестановка данных, выполняемая в третьем каскаде коммутаторов известного устройства после предварительной перенастройки коммутаторов размера (n х n) на перестановку третьего каскада).

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

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

В предлагаемом устройстве становятся излишними все каскады коммутаторов, расположенные в известном устройстве после среднего каскада.

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

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

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

Во всех описанных выше вариантах предлагаемое устройство содержит меньше коммутаторов, чем известное, за счет исключения в нем всех коммутаторов,, расположенных в известном устройстве после среднего каскада, При выполнении пересылок данных про- 20 извольного вида такое исключение становится возможным благодаря повторному использованию каскадов коммутаторов, расположенных в известном устройстве до среднего каскада. С увеличением количества каскацсв коммута— торов колнчество тактов, затрачивае-.: мьг :: на выполнение пересылки дачных произвольного вида, возрастает в число раэ, равное числу каскадов,, имеющихся в соот«eòñòâóþùeì варианте известного устройства, а время одного такта примерно во столько же раз уменьшается. Таким образом, время выполнения перестановки данных про. извельного вида, если Ie ччитывать весьма непродолжительнь!e по времени пересылки данных с входных шип на выходные, в данном и известном устройствах примерно одно и то же.

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

Из оощего ус гройства управления во все процессоры-передатчики много- процессорной вычислительной системы .поступает заданная разность координат номеров пар процессоров передатчиков и приемников и суммируется там с собственными координатами процесcopva-передатчиков. Число тактов выполнения регулярной перестановки данных в предлагаемом устройстве зависит от числа координат., по которым отличаются между собой номера пар процессоров приемников и передатчиков. В том случае, если они отличаются только по одной координате, вышеуказанные перестановки выполняются за один такт, Можно показать, то регулярные перестановки всегда являются.однотактными в том случае, когда размерности коммутаторов, т.е. г и и, являются числами, выраженными степенью числа 2, а разность номеров пар процессоров приемников и передатчиков являются числом, также выраженным степенью числа 2. Полученные в результате суммирования двухкоординатные номера процессоров-приемников используютeÿ для, настройки тех коммутаторов, с которыми каждькй процессор-передатчик "âÿçàí через соответствующую выхоцную шину. Полученные таким образом коды настройки ялэляются неблокирующими. Это происходит потому что маршруты движения данных ! при регулярной их перестановке начинаются из процессоров-передатчиков, имеющих ра= íûå номера,,а номера промежуточных и конечных процессоров, через которые, проходят эти маршруты, получаюпрлеся в результате суммирования различных чисел с одним и тем же числом (разностью координат), также различны, поэтому блокировки не происходит.

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

1 — - номер очередного шага вычислений.

Число f =- !, 2, З,...,P. где P — 1оя 1 :, а М вЂ” размерносТь вычисляемого спектра БПФ. Например, в том случае если вычисляется спектр БПФ размерностью N =- 1024, то P = lop;

1024 = 1О, Пусть, предлагаемое двухгруппсвое коммутирующее устройство реализует коммутатор 1024 х 1024 и пусть такие размерности используемых, в нем коммутаторов (r х r,) и (и х и) являются числами, выраженными степенью числа 2, например r = 256, а г. =

16. В рассматриваемом случае на первом — четвертом шагах вычислений и pecTQHoBKH данных выполняются с

1244

7 помощью коммутаторов (n x n), т.е, 16 х 16, Разность номеров пар процессоров на первом-четвертом шагах выл числений равна 2, где - = 1, 2, 4, лг.

8, На пятом — восьмом шагах равна где 2 = 16, 22, 64, 126, На девятом и десятом шагах вычислений снова используются коммутаторы (и .х п), т,е. (!6 х 16). Разность номеров пар процессоров равна 2, где " = 256, 512. 10

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

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

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

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

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

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

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

j-га дополнительного коммутатора размера (n x n) подключены соответственно к третьей выходной и третьей входной шинам :.-га процессора 1-й группы, причем вторая входная шина ( каждого процессора подключена к его третьей выходной шине через саатветствуюший дополнительный вентиль.

1244789

1244789

I

S

1, J

I

1 2

1 г д

r6

57

7z

79 вп

eic8

43

72 . 512

1244789

Составитель С. Куст

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

Тираж 816 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий .

I1 3035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ 3927/58

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