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

2 титут проблем управления и(72) А, А. Чудин и Ю. И. Тараторин т (.53) 621,382(088.8) п (56) С 1 оя. А Я 1 цйу оГ попЫосК я ц яЫ 1 сИпд пе 1 чогКя. - Ве 11 Яуя ТесЬ.Чо 1. 3, рр. 406-424, 1953,Оеогяу Вгооше 11 апй,Т. Бодег 1 дНеа 1 И. С 1 аяяГсаСоп СаСеяогея р ап 6 Нья 1 огса 1 Эече 1 орп)епй оГ Сгсц- т Се ЯчЫсМпц Торо 1 одея, - АСМ Сошрц- я 11 щ Яцгчеу, 15, 1983 Хцпе, Р 2. с (54) КОММУТИРУЮЩЕЕ УСТРОЙСТВО ДЛЯ т МНОГОПРОЦЕССОРНОЙ, ВЫЧИСЛИТЕЛЬНОЙ СИ- э СТЕИЫ т (57) Изобретение относится к устрой- п ствам автоматической цифровой комму- и тации. Может быть использовано в со- г ставе микропроцессорных вычислитель - а ных систем для межблочного обмена дан- мь ными. Целью изобретения является упро- и щение устройства с одновременным по- д вышением быстродействия. Кроме того, .п в устройстве обеспечивается упрощение 1 ГОСУДАРСТ 8 ЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ программирования и диагностирования за счет органиэации передачи данных не через все, а только через заданные каскады коммутаторов, одновременная ересылка данных по сокращенным пуям, а также выполнение регулярных ерестановок,данных между всеми проессорами и произвольные перестановки анных между некоторыми процессорами. труктурная схема устройства содержит ва каскада из г коммутаторов раэмеа (и х и) и один каскад из г коммуаторов размера (и х и), где г и п вляются целыми числами, выраженными тепенью числа 2, В качестве коммутаоров (и х и) и (г х г) могут исполь- Я оваться любые неблокирующие коммута- оры указанной размерности, например ерекрестные коммутаторы, матричные ереключатели, кольцевые сдвиговые реистры. Структурные схемы устройства, .стакже потактного моделирования, схе пяти и девяти каскадных устройствгеометрические модели 2- и 3-кооринатного коммутирующего устройства риводятся в описании изобретения.з.п. ф-лы, 6 ил.1244789 Коммутирующее устройство содержит ф первые выходные шины 1 процессоров., объединенные в группыпервых выходных шин, пронумерованные с 2-1 по 2-г, причем первые выходные шины 1 внутри своей группы пронумерованы с 1-1 до 1-и, первые входные шины 3 процессоров, объединенные в группы 4 первых входных шин, пронумерованные с 4-1 по 4-г причем первые входные шины 3 внутри свосй группы пронумеровапы с 3-1 по 3-и; и квадратных коммутаторов 5 размера (г х г), пронумерованных с 5-1 по 5-п, входы в которых пронумерованы с 6-1 по б-г, а выходы 7 - с 7-1 по 7-г; т квадратньх коммутаторов 8 размера (и х п), пронумерованных с 8-1 по 8-г, входы 9 которых пронумерованы с 9-1 по 9-п,Изобретение относится к автоматикеи вычислительной технике, в частностик устройствам электронной коммутации,и может применяться в састае многопроцессорных вычислительных системдля межблочного обмена данными.Цель изобретения - упрощение устройства с одновременным повышениембыстродейс твия, а также упрощениепрограммирования и диагностированияэа счет органиэации передачи данныхне через все, а только через заданные каскады коммутаторов сдновременной пересылки данных по сокращеннымпутям, а также выполнения регулярныхперестановок данных между всеми процессорами и произвольных перестановок данных между некоторыми процессорами,На фиг. 1 изображена структурнаясхема коммутирующего устройства длямногопроцессорной вычислительнойсистемы, содержащего три каскадакоммутаторов, соответственно, двакаскада из г коммутаторов (п х и) иодин каскад изкоммутаторов (г х г)на Фиг. 2 - структурная схема потактного моделирования в двухкоординатном устройстве работы известноготрехкаскадного коммутирующего устройста; на йиг 3 и 4 - геометрическая Модель двухкоординатного итрехкоординатного коммутирующих устройств. на вериг, 5 и о " структурныесхемы пятикаскадного и девятикаскадного устройств, на которых штрихпунктирными линиями указаны местаподключения вентилей, а также входных и выходных шин процессоров. а выходы 10 которых пронумерованы с10-1 ло 10-п, вторые выходные шины11 процессоров, объединенные в группы 12 вторых выходных шин, пронумерованные с 12-1 по 12-г, причем вторые выходные шины 11 внутри своейгруппы пронумерованы с 11-1 по 11-и;вторые входные шины 13 процессоров,объединенные в группы 14 вторыз входных шин, пронумерованные с 14-1 по14-г, причем вторые входные шины 13внутри своей группы пронумерованы с13-1 по 13-п, вентили 15, г группкоторых пронумерованы с 15- по 15-г,а сами вентили внутри 1-й группыпронумерованы с 151 по 15-1-и причем вход 9- коммутатора 8-, подключен к первой выходной шине.1- группы 2-) первых выходных шин, выходо 1 О- коммутатора 8-) соединен с первой входной шиной 3-х группы 4-, перьвых входных шин, вход 6-,) коммутатора 5- подключен к второй выходнойшине 11- группы 2-7 вторых выходных5 шин, а выход 7-,) коммутатора 5- соединен с второй входной шиной 13-группы 14-,1 вторых входных шин, процессоров г дополнительных коммутаторов 16 размера (и х и) пронумерованных с 16-1 по 16-г, входы 17 которых пронумерованы с 17-1 по 17-п, авыходы 18 пронумерованы с 18-1 по1 Я-п, третьи выходные шины 19 процессоров, объединенные в группы 20третьих выходных шин, пронумерованные с 0-1 по 20-г, причем третьи выходные шины 19 внутри;своей группыпронумерованы с 19-1 по 9-п, третьивходные шины 21 процессоров, объединенные в группы 22 третьих входныхшин, пронумерованных с 22-1 па 22-г,причем третьи входные шины 21 внутрисоей группы пронумерованы с 21-1 по21-п, дополнительные вентили 23, ггругп которых пронумерованы с 23-1по 23-г, а. сами дополнительные вентили путри,1-й группы пронумерованыс 23-,-1 по 23-,1-п, вторая входная13- шина группы 14-,) вторых входныхшин процессоров подключена через вентиль 23-,)- - к третьей выходной шине 19- . группы 20-,) третьих входййхшин процессоров,В качестве коммутаторов (н х и) и(г х) могут использоваться любыенеблокирующие коммутаторы укаэаннойраэмерпости, например, перекрестныекоммутаторы матричные переключателикольцевые сдвиговые регистры, в т,ч.и многокаскадные коммутирующие устройства.Устройство работает следующим образом.Каждому сеансу обмена данными между процессорами системы предшествует настройка коммутирующего устройства, Определение кодов настройки коммутирующего устройства, т.е. его программирование, сводится.к прокладьванию маршрутов прохождения пересылаемых данных через его коммутаторы таким образом, чтобы по каждому возможному маршруту проходило бы в один и тот же момент времени не более одного данного. Эта.задача носит комбинаторный характер, но ее можно решать с помощью известных алгоритмов, в т.ч. разработанных для.многокаскадных систем коммутации, например, с помощью алгоритма Цао-Ву и Опфермана. 5 1 О 15 20 30 55 Выполнение перестановки данных произвольного вида в предлагаемом двухкаскадном устройстве осуществляется следующим образом. Пусть с помощью некоторого алгоритма вычислены коды настройки длякоммутаторов предлагаемого устройства. Предположим эта перестановкаданных выполняется в устройстве затри такта: на первом такте выполняется частичная перестановка данныхс помощью г коммутаторов (и х и),обозначенных на фиг. 2 с 8-1 по 8-г,и осуществляется пересылка данных спервых выходных шин (с 1-1 по 1-п)на первые входные шины.(с 3-1 по 3 п); на втором такте данные частичнбпереставляются с помощью п коммутаторов (г х г), обозначенных нафиг. 2 с 5-1 по 5-и; на третьем такте необходимо г коммутаторов (и х и),обозначенных на фиг. 2 с 8-1 по 8-гперенастроить на выполнение перестановки данных, которые выполняютсяв известном устройстве - в его третьем каскаде. С тем, чтобы такаяперестройка коммутаторов не замедлила процесс выполнения произвольнойперестановки данных, ее выполняют втечение второго такта. Поскольку изо/браженная на фиг. 2 пересылка данныхполностью эквивалентна пересылке данных, реализуемой в известном устройстве, то предлагаемое устройство прии ) г также является неблокирующим,как и известное,35 40 45 50 В двухкаскадном устройстве можно выполнить перестановку данных произвольного вида эа два такта: на первом такте реализуется частичная перестановка данных, которая соответствует перестановке, выполняемой в первых двух каскадах коммутаторов в известном устройстве.(в этом случае информационный сигнал испытывает задержку не только в коммутаторах размера (п х п) и (г х г), но и в вентилях 15); на втором такте перестановка данных заканчивается (реализуется перестановка данных, выполняемая в третьем каскаде коммутаторов известного устройства после предварительной перенастройки коммутаторов размера (и х и) на перестановку третьего каскада).Используя известный принцип уменьшения количества коммутирующих элементов, возможно путем преобразования коммутаторов (г х г) среднегокаскада в известном устройстве превращать его из трехкаскадного устройства в пятикаскадное, иэ пятикаскадного в семикаскадное,и т.п. Точнотак же путем преобразования одногокаскада коммутаторов, например, (г хх г) можно превратить двухкаскадное устройство в трехкаскадное, затем вустройство, содержащее четыре каскада коммутаторов и т,д, По своим ком,мутационным возможностям предлагаемоедвухкаскадное устройство соответствует известному трехкаскадному, трехкаскадное - пятикаскадному, четырехкаскадное - семикаскадному и т,д.В предлагаемом устройстве становятсяизлишними все каскады коммутаторов,расположенные в известном устройствепосле среднего каскада.Двухкаскадное устройство удобногеометрически интерпретировать двумерной стержневой решеткой, узламикоторой являются процессоры многопроцессорной вычислительной системы, акаждый стержень представляет собойквадратный неблокирующий коммутаторсоответствующей размерности. Пусть,например, все продольные стержни соответствуют коммутаторам (г х г), авсе поперечные - коммутаторам (и х и)(г х г) в двухкаскадные устройства,состоящие иэ коммутаторов меньшейразмерности, соответствует преобра эованню всех продольных стержней в двумерные "стержневыеп решетки. В результате такого преобразования предлагаемое двухкаскадное устройство становится трехкаскадным, геометрическая интерпретация которого описывается трехмерной модельк (фиг. 4). По своим возможностям оно соответствует известному пятикаскадному устройству. Последующее преобразование одного из каскадов коммутаторов впредлагаемом каскадном устройстве делает его четырехкаскадным и т.д.Во всех описанных выше вариантах предлагаемое устройство содержит меньше коммутаторов, чем известное, за счет исключения в нем всех коммутаторов расположенных в известном устройстве после среднего каскада, При выполнении пересылок данных про извольного вида такоеисключение становится возможным благодаря повторному использованию каскадов коммутаторов, расположенных в известном устройстве до среднего каскада. С уве лнчением количества каскацов коммутаторов количество тактов, затрачивае-.: мых на выполнение пересылки дачныхпроизвольного вида, возрастает в число раз, равпое числу каскадов имеющихся в соответствующем варианте известного устройства, а время одного такта примерно во столько же раз уменьшается. Таким образом, время выполнения перестановки данных про.иэвельного вида, если не учитывать весьма непродолжительные по времени пересылки данных с входных шип на выходные, в данном и известном устройствах примерно одно и то же,Перестановки данных регулярного вида выполняются в устройстве следующим образом.Иэ общего ус гройства управления во все процессоры-передатчики много- - процессорной вычислительной системы поступает заданная разность координат номеров пар процессоров передатчиков и приемников н суммируется там с собственными координатами процессоров-передатчиков. Число тактов выполнения регулярной перестановки данных в предлагаемом устройстве зависит от числа координат., по которым отличаются между собой номера пар процессоров приемников и передатчиков. В том случае, если они отличаются только по одной координате,вышеуказанные перестановки выполняются за один такт, Можно показать, что регулярные перестановки всегда являются.оцнотактными в том случае, когда размерности коммутаторов, т.е. г и и, являются числами, выраженными степенью числа 2, а разность номеров пар процессоров приемников и передатчиков являются числом, также выраженным степенью числа 2. Полученные в результате суммирования двухкоординатные номера процессоров-приемников используются для, настройки тех коммутаторов, с которыми каждьвй процессор-передатчик связан через соответствующую выхоцную шину. Полученные таким образом коды настройки являются неблокирующими. Это происходит потому что маршруты движения данных при регулярной их перестановке начинаются из процессоров-передатчиков, имеющих разные номера, а номера промежуточных и конечных процессоров, через которые, проходят эти маршруты, получающиеся в результате суммирования различных чисел с одним и тем же числом (разностью координат), также различны, поэтому блокировки не происходит.Зйфект упрощения программирования и повышения быстродействия за счет ускорения получения кодов настройки в двухкаскадном устройстве по сравнению с известным трехкаскадным устройством нагляден на примере реализации базового алгоритма быстрого преобразования Фурье (БПФ). При реализации БПФ на каждом очередном шаге вычислений выполняются взаимные перестановки дачных между парами процессоров, разность номеров котояых для всех пар одинакова и равна. 2где 1: - номер очередного шага вычислений. Число 1 =: , 2, ЗР. где Р - ТОГ 21, а М - размерность вычисляемого спектра БПФ. Например, в том случае если вычисляется спектр БПФ 1 яазмерностью И = 1024, то Р = 1 оР;2 1024 = 10, Пусть, предлагаемое двухгруппсвое коммутирующее устройство реализует коммутатор 1024 х 1024 и пусть такие размерности используемых, в нем коммутаторов (г х г) и (и х и) являются числами, выраженными степенью числа 2, например г = 25 б, а г. =16. В рассматриваемом случае на первом - четвертом шагах вычислений перестановки данных выполняются с1244 Выполнение перестановки данных произвольного вида в трехкаскадном ,25 устройстве осуществляется только за один такт почти точно так же, как в известном устройстве, только информационному сигналу приходится испытывать дополнительные задержки на вентилях 15 и 23. Выполнение же регулярных перестановок данных выполняется точно так же, как и в двух-.каскадном устройстве, с тем же быстрым вышеописанным способом получения кода настройки эа один-два ша 35 га вычислений. Наличие в предлагаемом трехкаскадном устройстве двух каскадов из г коммутаторов размера (и х и), непосредственно подключенных с помощью входных и выходных шин к процессорампозволяет выполнять перестановки данных в группах по и процессоров значительно быстрее, чем в известных устройствах. Такое повьппе ние быстродействия происходит в том случае, когда указанные пересылки данных выполняются только внутри стоек, а также последовательно (или параллельно-последовательно) по разрядам, Полностью параллельная поразрядная перестановка данных обычно приводит к чрезмерно большим аппаратурным затратам, поскольку для одновременной пересылки каждого из й раэря 55 дов пересылаемых данных необходимо иметь Й предлагаемых коммутирующих 7помощью коммутаторов (и х и), т.е, 16 х 16, Разность номеров пар процессоров на первом-четвертом шагах вызР.числений равна 2 , где= 1, 2, 4, 8, На пятом - восьмом шагах равна где 2 = б, 22, 64, 126, На девятом и десятом шагах вычислений снова используются коммутаторы (п,х и), т,е. (6 х 16), Разность номеров пар процессоров равна 2 , где " = 256, 512. 1 О Таким образом, на каждом шаге вычислений выполняются пересылки данных только по вертикальным, либо только по горизонтальным стержням, т.е, все перестановки данных выполняются за 15 один такт внутри одного каскада. Можно показать, что пересылки данных на первом - четвертом и девятом - десятом шагах выполняются только внутри стоек, т.е. с большей тактовой 20 частотой, чем в известных устройствах. 789 8устройств и поэтому на практике обычно ограничиваются параллельно-последовательным способомВ рассматриваемом случае удается одновременно пе-, ресылать в два раза больше разрядов данныхОдна группа из г коммутаторов размера (п х и) используется для передачи одних разрядов, а другая для других разрядов данных, При отказе всех коммутаторов размера (и х и), например, третьего каскада, устройство выполняет заданную перестановку данных, но с меньшим быстродействием,Формула изобретенияКоммутирующее устройство длямногопроцессорной вычислительнойсистемы, реализующее неблокирующийкоммутатор размера (гп х гп), содержащее и коммутаторов размера (г х г)и г коммутаторов размера (и х и),подключенных выходами к первым входным шинам процессоров, объединенныхв г групп по и процессоров, причем(и х и) соединен с первой входнойшиной 1-го процессора .1-и группы,о т л и ч а ю щ е е с я тем, что,с целью упрощения устройства с одновременным повышением быстродействия,в него введена пг вентилей, причем,)-й вход и "-й выход -го коммутатора размера (г и г, подключены соответственно к второй выходной и второйвходной шинам 1.-го процессора 1-йгруппы, причем первая входная шинакаждого процессора подключена к еговторой выходной шине через соответствующий вентиль,2, Устройство по п. 1, .о т л и -ч а ю щ е е с я тем, что, с цельюповышения надежности, в него введеног дополнительных коммутаторов размера (и х и) и пг дополнительных вентилей, причем 1-й вход и -й выход.1-го дополнительного коммутатораразмера (и х п) подключены соответственно к третьей выходной и третьейвходной шинам -го процессора 1-йгруппы, причем вторая входная шинакаждого процессора подключена к еготретьей выходной шине через соответствующий дополнительный вентиль.12 ч 4789 Фиу б оставитель С. Кустехред Н.Бонкало Корректор О. Луговая ов тин едакт Заказ 3927/58 водственно-полиграфическое предприятие, г. Ужгород, ул. Проектная,Тираж 816НИИПИ Государстпо делам изобр035, Москва, ЖПодписноеенного комитета ССтений и открытий .5, Раушская наб.,