Устройство для распределения заданий в сетях электронных вычислительных машин

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