Устройство для связи процессоров в вычислительной системе

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК А 1 Р 13/ 59 4 САНИЕ ИЗОБРЕТЕНИЯ ЙИДЕТЕЛЬСТ К АВТОРСНОМ зел 3 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(56) Авторское свидетельство СССР В 1130855, кл. С 06 Р 13/14, 1982.Авторское свидетельство СССР В 1332327, кл. С 06 Р 13/14, 1985. (54) УСТРОЙСТВО ДЛЯ СВЯЗИ 11 РОЦЕССО РОВ В ВЪЯИСЛИТЕЛЬНОЙ СИСТЕМЕ (57) Изобретение относится к вычис лительной технике и может быть использовано в многопроцессорных вычислительных системах для реализации межэадачного взаимодействия. Цель изобретения - расширение Функ циональных воэможностей за счет ко мутации процессоров при реализации сильно связанных параллельных алго ритмов. Устройство содержит группу интерфейсных блоков 2 усилителей,блок 4 регистров приоритета, укоммутации соединения, включающийузел коммутации, узел приоритетовпроцессов, группу управляющих регистров, три группы элементов И, первыйузел приоритета активного процесса,две группы Формирователей импульса,буФерные регистры запросов и готовности, две группы блоков элементов И,две группы управляющих триггеров,группу схем сравнения, три элементаИЛП 1, элемент И, триггер управления,генератор импульсов и узел выборапроцесса, состоящий из группы элементов И. Новым в устройстве является введение в узел коммутации соединения триггера пуска, элемента ИЛИ,элемента задержки, двух элементов И,второго узла приоритета активногопроцесса, а в узел выбора процесса - Сгруппы элементов И и двух групп элементов ИЛИ. 1 з.п. Ф-лы, 6 ил.Изобретение относится к вычислительной технике и может быть использовано в многопроцессорных вычислительных системах для реализации межэадачного взаимодействия.Целью изобретения является расширение функциональных возможностей эа счет коммутации процессоров при реализации сильно связанных параллельных алгоритмов.На фиг.1 приведена блок-схема предлагаемого устройства; на фиг.2 - функциональная схема блока регистров приоритета; на Фиг. 3 - то же, узла ком мутации соединения; на фиг.4 - схема узла выбора процессора; на фиг.5 - то же, узла приоритетов; на фигб -то же, узла коммутации.Устройство (фиг.1) содержит шины, 1 стандартного интерфейса связи, ин-20 терфейсные блоки 2 усилителей, узел 3 коммутации соединения, блок 4 регистров приоритета, шины 5 передачи, шины 6 приема, линии 7 запросов, шины 8 запросов, шины 9 группы выходов блока 4 регистров приоритета,Блок 4 регистров приоритета (фиг2) содержит коммутатор 10 и группу регистров 11 приоритета.Узел 3 коммутации соединения (фиг.3) содержит группу управляющих регистров 12, первую группу элементов И 13, узел 14 выбора процессора, синхровход 15, вход 16 управления, группу управляющих входов 17, группу запросных входов 18 и группу выходов 19 узла 14, буферный регистр 20 запросов, первую группу формирователей 21 импульса (дифференцирующих элементов), узел 22 приоритета процессоров, второй узел 23 приоритета активного процессора, первую группу блоков элементов И 24, третью группу элементов И 25, первую группу управляющих триггеров 26, первый элемент ИЛИ 27, вторую группу формирователей 28 импульса, первый элемент 29 задержки, третий элемент 30 задержки, триггер 3 1 управления, четвертый элемент ИЛИ 32, третий элемент И 33, вторую группу элементов И 34, второй элемент И 35, буферный регистр 36 готовности, вторую группу блоков элементов И 37, второй элемент ИЛИ 38, группу элементов 39 сравнения, первый элемент И 40, триггер 4 1 пуска, третий элемент ИЛИ 42, первый узел 43 приори 303540455055 тета активного процессора, второй элемент 44 задержки, вторую группу управляющих триггеров 45, узел 46 коммутации, выходы 47 триггеров 26 (первые адресные входы узла 46),группу выходов 48 формирователей 21 (первые входы сброса узла 46), выход 49 элемента 44 задержки (вход стробирования узла 46), группу выходов 50 формирователей 28 (вторые входы сброса узла 46), выходы 51 триггеров 45 (вторые адресные входы узла 46), первый 52 и второй 53 управляющие входы устройства, выходы 54 регистра 20 и . генератор 55 импульсов.Узел 14 выбора процессора (фиг.4) содержит вторую группу элементов ИЛИ 56, первую 57 и вторую 58 группы элементов И соответственно и первую группу элементов ИЛИ 59. Узел 22 приоритетов процессоров (фиг.5) содержит группу дешифраторов 60, группу элементов ИЛИ 61, группу элементов И 62, шифратор 63 и группу элементов 64 сравнения.Узел 46 коммутации (фиг.б) содержит каналы 65, каждый из которых включает в себя первую 66 и вторую 67 группы элементов И, регистр 68 и коммутатор 69 и группу элементов ИЛИ 70.Устройство работает следующим об. разом.При органиэации процессов в вычислительной системе каждому из них выделяется необходимое число процессоровНа этапе планирования вычислений операционной системой для определения последовательности организации межпроцессорных связей внутри созданных процессов каждому из них устанавливается приоритет двоичными кодами натурального ряда чисел, причем наивысшим приоритетом обладает процесс с меньшим приоритетнымкодом. Каждому процессору одного процесса задаются двоичный код приоритета данного процессора и одинаковый номер задачи (процесса) . Это дает возможность при организации обменов сигналы запросов и готовности сопровождать номером процесса. В каждом процессе ряд процессоров (активные) Формируют сигналы запросов, а остальные его процессоры (пассивные) ,сигналы готовности Эти сигналы со провождаются номером процесса и фик1515170сир уют ся в с оо тве тс тв ующем ре гис тре 12 (фиг.3).Каждый управляющий регистр 12 содержит два триггера хранящих сигФ5 налы запроса и готовности, и регистр для хранения двоичного кода номера процессаФункцию присвоения приоритетов может взять на себя любой из процессоров, входящих в вычислительную систему, который в данный момент является центральным. При этом блок 4 рассматривается как абонент для процессора, присваивающего приоритеты. Процессор вьщает код приоритета, который через соответствующий интерфейсный блок 2 поступает по шинам 5 на вход коммутатора 10 (фиг.1 и 2) и далее в соответствующий регистр 11 по управляющему сигналу на линиях 7.Межпроцессорный обмен начинается с фазы установления связи между процессорами, выделенными процессу, Ус тановление связи происходит в соответствии с присвоенными приоритетами процессам. Выбор приоритетного процесса происходит следующим образом.Исходное состояние устройства характеризуется тем, что триггеры 31 и41, регистры 20 и 36, триггеры 26 и45 (фиг.З), регистры 68 каналов 65(цепи установки не показаны).35При необходимости установлениясвязи активными процессорами по шинам 8 в регистры 12 заносйтся сигналы запросов и коды номеров процессов,а пассивными процессорами по шинам 8сигналы готовности и коды номеровпроцессов, а по входу 53 подаетсясигнал запуска, устанавливающий триггер 41 в состояние "1".Так как триггеры 31, 26 и 45 находятся в нулевых состояниях, то врегистрах 20 и 36 с помощью открытыхэлементов И 13 и 34 производится отслеживание состояния триггеров Т иТ регистра 12. При наличии в регистрах 20 и 36 единичных сигналов черезсоответствующие элементы ИЛИ 27 и 38открывается элемент И 40, и первымимпульсом генератора 55 триггер 31устанавливается в состояние "1". Приэтом элементы И 13 и 14 закрываются,чем фиксируются сигналы в регистрах20 и 36 в цикле установления межпроцессорных связей,Единичные сигналы с выходов регистра 20 поступают в узел 22 по входам 54, а единичным сигналом с единичного выхода триггера 31 открываются элементы И второго узла 23 приоритета активного процесса. В узле 22 (фиг.5) коды приоритетов посредством открытых по соответствующим входам 54 дешифраторов 60 преобразуются в унитарные. Одноименные выходы дешифратора объединяются одноименными элементами ИЛИ 61. С помощью элементов И 62, включенных с выходами элементов ИЛИ 6 1 по приоритетной схеме, производится вьщеление приоритетной младшей единицы и формирование унитарного кода на входах шифратора 63, преобразующего его в двоичный, Посредством элементов 64 сравнения определяется позиционный код числа активных процессоров приоритетного процесса. При этом номера возбужденных выходов 18 узла 22 соответствуют номерам активных процессоров, аФих количество - числу активных процессоров, требующих установления связи внутри приоритетного процесса, С помощью узла 23 приоритетного активного процесса иэ нескольких запросов приоритетного процесса производится выделение крайнего левого единичного сигнала из позиционного кода с выходов 18. Этим сигналом открываются элементы И блоков 24 и на объединенных выходах блоков 24 формируется двоичный код номера приоритетного процесса. Этот код поступает на входы элементов 39 сравнения. На другие входы элементов 39 сравнения через соответствуюцие открытые сигналами готовности регистра 36 блоки 37 поступают коды номеров процессов, пассивные процессоры которых выставили сигналы готовности к обмену.При этом возможны два случая: сигналы готовности приняты в регистр 36 от пассивных процессоров, не относящихся к выделенному приоритетному процессу; в регистре 36 зафиксированы сигналы готовности пассивныхпроцессоров, относящихся к вьщеленному приоритетному процессу.В первом случае на выходах элементов 39 сравнения установлен нулевой код, которым через элемент ИЛИ 42 закрыты элементы И 25, а по инверсным входам открыты элемент И 33 и элементы И 58 в узле 14 (фиг.З н 4), 1515170Через некоторое время, определяемое элементом 29 задержки, устанавливаются н состояния 0 нсе триггеры регистра 20, относящиеся к выделенному приоритетному процессу, посредством узла 14 выбора процессора следующим образом. Пусть к приоритетному процессору относятся сигналы в Т 20, и Т 20 . При этих условиях на выходах 18, и 18 узла 22 присутствуют единичные сигналы, образующие позиционный код: 1001. С помощью узла 23 формируется унитарный код на выходах 17 : 10;.;00. В узле 14 единичным сигналом с входа 17, открыты элементы И 57 по первому входу, элемент И 58, по третьему прямому входу и через элементы ИЛИ 56 - по третьим прямым входам элементы И 58, начиная с второго, По входу 18 по первому прямому входу открыт элемент И 58, . Таким образом, при поступлении сигнала по синхровходу 15 в узле 14 единичные сигналы формируются на выходе элемента И 57 и на выходе элемента ИЛИ 59поступающих с выхода элемента И 58. Сигналами с выходов 19 и 19 триггеры 20, и 20 устанавливаются в нулевые состояния. При этом, если в регистре 20 имеются сиг 30 налы запросов, то на выходе элемента ИЛИ 27 удерживается единичный сигнал, которым элементы И 33 и 35 закрыты по инверсным входам. Вследствие этого триггер 31 остается н единичном 35 состоянии и по второму импульсу генератора 55 организуется очередной такт работы устройства.Во втором случае единичным сигналом с выхода элемента ИЛИ 42 откры ваются элементы И 25 и закрываются по инверсным входам элементы И 58 в узле 14. Одновременно при наличии нескольких единичных сигналов на выходах элементов 39 сравнения с помощьюузла 43 выделяется крайняя левая единица из позиционного кода вьмодных сигналов элементов 39 сравнения, Задержанным сигналом с выхода элемента 29 задержки устанавливаются в состояние "1" соответствующие триггеры 26 и 45 в состояние "0" - через соответствующий элемент И 34 одноименный разряд регистра 36 и соответствующий разряд регистра 20. Пусть к 55 приоритетному процессу в данном случае относятся Т 20. и Т 20 , При этих условиях на входах 18 г, 18и 17 узла 14 присутствуют единичные сигналы. Единичным сигналом с входа 18открт элемент И 57 по первому нхогду, а элементы И 58 закрыты по инверсным входам. Поэтому импульсом ссинхронхода 15 только на выходе элемента И 57 формируется единичныйсигнал, поступающий через элементИЛИ 59 на выход 19 узла 14. Этимсигналом устанавливается н состояние "0" триггер 20 регистра 20.Если после установки в состояние "0"разряда регистра 36, выделенного длямежпроцессорной связи, в нем нет сигналов готовности от пассивных процессоров, единичный сигнал с выхода элемента ИЛИ 42 снимается. При этом элемент И 33 открывается по инверсномувходу нулевым сигналом с выхода элемента ИЛИ 42, а единичным сигналомс выхода элемента ИЛИ 27 по прямомувходу он удерживается в закрытом состоянии, Кроме того, элемент И 35 открыт по прямому входу единичным сигналом с выхода элемента ИЛИ 27 и поинверсному входу нулевым сигналом свыхода элемента ИЛИ 38. Поэтому дополнительно задержанным импульсом, элементом 30 задержки триггер 3 1 устанавливается н нулевое состояние, разрешая прием сигналов запросов и готовности соответственно в регистры20 и 36 через открытые элементы И 13и 34.Аналогичным образом триггер 31устанавливается в нулевое состояние,когда после установления связи междуактивным и пассивным процессорамирегистры 20 и 36 оказываются в нулевых состояниях, через элемент И 33.Если же после установки в состояние "0" разряда регистра 36, выделенного дчя межпроцессорной связи,в нем имеются сигналы готовности процессоров, не относящихся к приоритетному процессу, о чем свидетельствуетсигнал на выходе элемента ИЛИ 42, элементы И 33 и 35 закрыты по инверсным1входам единичными сигналами соответственно с выходов элементов ИЛИ38 и ИЛИ 27. Поэтому триггер 31 остается в единичном состоянии,Элемент И 40 удерживается в открытом состоянии единичными сигналами с выходов элементов ИЛИ 27 и 38, поэтому импульсом генератора 55 рассмотренным вьппе образом устанавли 1515170 10вается в состояние "0" разряд ре- навливается в состояние "О" чем и егйстра 20 приоритетного процесса. кращается подача импулимпульсов генератоТем самым обеспечивается установка ра 55.межпроцессорных связей для очеред- ования вновь устройства,Для использования ного по приоритету процесса при оно приводио о приводится в исходное состояниеналичии сигналов запросов и готовнос- После этогоого по входу 52 подается имти в регистрах 20 и 36. пульс запуска.Выходные сигналы триггеров 26 и Формула изобретения 45 используются для коммутации входов 1 1. Устройство для связи процесси- и выходов активного и пассивного про- ров в вычислительнойьнои системе, содер 46 ации. жащее группурфПусть в единичное состояние уста- усилителей, входы-выходы которых явновлены триггеры 26, и 45, Это одна- ляются группой входов-выходов устчает, что по сигналу запроса выходы 15 ройства для подключения к входам- первого процессора должны быть ском- выходам соответствующих процессх процессоров мутированы с входами и-го процессора, вычислительной системы, блок региствыходы которого, в свою очередь, ров приоритета, группа информациондолжны быть подключены к входам пер- ных и группа синхровходов которого вого процессора. Эта задача выполня- соединены соответственно с нф20о с информается узлом 46 следующим образом. Еди- ционными выходами и выходом сигнала ничным сигналом с входа 47 (фиг.6) запроса интерфейсных блоков усилиоткрыты элементы И 67 в канале 65, телей группы, узел коммутации соедин элемент И 66, в канале 65. Единич- нения, включающий узел коммутапии, ным сигналом с входа 51 открыт эле информационные входы группы и выходы мент И 6767 , в канале 651 и элемен- которого подключены соответственно к ты И 66 в канале 65, Через время за- информационным выходам группы и входержки, определяемое элементом 44 дам интерфейсных бл ок ов усилителей (фиг.З), триггеры 68 , в канале группы, узел приоритетов процессов,5, и 681 в канале 65 устанавли- группа информационных входов котороваются в е диничные состояния, При30го соединена с группой выходов блока этом шины 5, первого процесса комму- регистров приоритета, группу управтатором 69 подключаются к шинам 6, ляющих регистров, три группы элементаа шины 5коммутатором 69 подклю- тов И, первый узел приоритета активчаются к шинам 61, чем обеспечивается ного процесса, две группы формировадвухсторонняя связь первого процессо- З 5 телей импульсов, буферный регистр запросов, буферный регистр готовности,Период повторения импульсов гене- две группы блоков элементов И двеУ ратора 55 выбирается с учетом пара-группы управляющих триггеров, группу метров элементов 29 и 44 задержки. элементов сравнения, первый и второйПо окончании обмена сигналы запро- элементы задержки, первый, второй40сов и готовности снимаются. При этом и третий элементы ИЛИ, первый элесоответствующие триггеры регистра 12 мент И, триггер управления, узел выустанавливаются в состояние "О . Пе- бора процесса, состоящий иэ первой репады потенциалов на нулевых выхо- группы элементов И, вторые входы кодах дифференцируются соответствую- торых подключены к синхровходу этого45щими элементами 21 и 28, положитель- узла, и генератор импульсов, причем ными сигналами с выходов которых ус информационные входы управляющих ретанавливаются в нулевые состояния со- гистров группы соединены с входами- ответствующие триггеры 26 и 45 и в выходами соответствующих интерфейсуэле 46 триггеры 68 соответствующих 50 ных блоков усилителей, первый и втоканалов 65 через элементы ИЛИ 70. рой адресные входы узла коммутацииПри необходимости создания новых подключены соответственно к единичпроцессов, перераспределение приори- ным выходам триггеров первой и втотетов процессам или в других случаях, рой групп, нулевые входы которых соекогда надобность в установке межлро динены соответственно с первыми и цессорных связей исключена, то по вторыми входами сброса узла комму- входу 52 подается сигнал останова, тации и через соответствующие формипо которому триггер 4 1 пуска уста- рователи импульсов первой и второйгрупп - к инверсным выходам разрядов запроса и готовности управляющих регистров групп, прямые выходы разрядов запросов которого подключены к первым входам элементов И первой группы, а выходы разрядов кода номера зацачи - к информационным входам блоков элементов И первой и второй групп, выходы которь 1 х подключены соответственно к первым и вторым входам схем сравнения группы, выход первого элемента задержки соединен с вторыми входами элементов И третьей группы, с синхронизирующими входами 15 первого узла приоритета активного процесса и узла выбора процесса и через второй элемент задержки - с входом стробирования узла комиутаци, выходы элементов И третьей и первой групп подключены соответственно к единичным входам управляющих триггеров первой группы и буферного регистра запросов, группа выходов которого соединена с группой разрешающих вхо дов узла приоритета процессоров и с. группой входов первого элемента ИЛИ, первый вход группы управляющих выходов узла выбора процессора подключен к нулевому входу первого разряда буферного регистра запросов, единичный вход триггера управления годключен к входу первого элемента задерж - ки и выходу первого элемента И,первый, второй и третий входы которого соединены соответственно с выход,13 генератора импульсов, первого и второго элементов ИЛИ, группа входов которого соединена с управляющими входами блоков элементов И второй группы и группой выходов буферного40 регистра готовности, группа единичных входов которого соединена с выходами элементов И второй гругпы, первые входы которых подключены к45 единичным выходам разрядов готовности управляющих регистров группы,первые выходы управляющих триггеров первой и второй гругп соединены с вторыми входами элементов И соответственно первой и второй групп, треть ими входами подключенных к нулевому выходу триггера управления, третьи входы элементов И третьей группы попключены к выходу третьего элемента ИЛИ, группа входов которого соедин - 55 на с выходами схем сравнения группы и с группой запросных входов первого узла приоритета активного пропесса, группа выходов которого по;.,ключена к единичным входам управляющих триггеров второй группы и группе нулевых входов буферного регистра готовности, о т и и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет коммутации процессов при реализации сильно связанных .араллельных алгоритмов, в узел коммутации соединения введены триггер пуска, входы которого являются управляющими вхоцами устройства, четвертый элемент ИЛИ, третий элемент задержки, второй и третий элементы И, второй узел приоритета активного процесса, синхронизируюний вход которого подключен к единичному выходу триггера управления, группа выходов узла приоритета процессов соединена с группами запросных входов узла выбора процессора и второго узла приоритета активного процесса, группа выходов которого подключена к управляющим входам блоков элементов И первой группы, к первым входам элементов И третьей группы и к группе управляющих входов узла ьыбора процессора, вход управ ения кот рого соединен с выходом тре; его элемента ИЛИ и инверсным входам третьего элемента И, прямой вход которого соединен с выходом гретьего элеме .та задержки, входом подключенного выходу первого элемента задержки, и с первым прямым входом второго элемента И, инверсный вход которого п;дключен к выходу второ о элемента И, а второй прямой вход соединен с выходами первого элемента ИЛИ и с вторым инверсным входом третьего элемента И, выход которого подключен к первому входу четвертого элемента ИЛИ, вторым входом соединенного с выходом второго элемента И, а выходом - с нулевым ьходом триггера управления, единичный выход григгера пуска подключен к четвертому входу первого элемента И.2. Устройство по и. 1, о т л и ч а ю щ е е с я тем, что узел выбора процессора дополнительно содержит вторую группу элементов И и две группы элементов ИЛИ, вход синхронизации пгдключен к вторым прямым входам элементов И второй группы,инверсные входы которых соединены с входом управления узла выбора проессора, первый вход группы управляющих входов соединен с первым и третьим прямым входами соответственно элементов И первой и второй групп и с первыми входами элементов ШП 1 второй группы, второй вход группы управляющих кодов подключен к первому входу второго элемента И первой группы и вторым входам элементов ИЛИ второй группы, -й вход группы управляющих входов ( = Э, 4п, и - число процессоров) соединен с первым входом д-го элемента И первой группы и с д-м входом (д)-го, -го(п)-го элементов ИЛИ второй группы, 1-й вход группы запросных входов (1 = 2, 3, , и) подключенк первому прямому входу (1-1)-го элемента И второй группы, выход которого соединен с вторым входом Ц)-гоэлемента ИЛИ первой группы, первыйвход которого подключен к выходу1-го элемента И первой группы, выход (х)-го элемента ИЛИ второйгруппы соединен с третьим прямымвходом (д)-го элемента И второйгруппы, выход первого элемента Ипервой группы и выходы элементов ИЛИпервой группы являются группой выхо,дов узла выбора процессора.