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

СОЮЗ СОВЕТСОЦИАЛ ИСТИЧРЕСПУБЛИК 09)(59 С 06 Г 1 / ПИСАНИ ИЗ ЕТ К АВТОРСКО ВИДЕТЕПЬСТ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И 01 НРЦТИЙ(56) 1. Авторское .свидетельство СССМ 525954, кл, 0 06 Р 15/20, 1977,2, Авторское свидетельство СССРУ 716043, кл, 6 06 Г 15/20, 1980(прототип),(54 )(57 ) УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕИОЙ, содержащее матрицу формирователей дуг, включаю . щую Й групп по й (й - число заданий триггеров в каждой, группу элементов ИЛИ, первую группу элементов И, первый счетчик, группу счетчиков и группу схем сравнения, единичные выходы триггеров каждого столбца матрицы формирователей дуг соединен с входами одноименного элемента ИЛИ первой группы, выход которого под, ключен к первому входу одноименного элемента И первой группы, выход которого соединен со счетным вхо" дом одноименного счетчика группы, выход. которого подключен к первому входу одноименной схемы сравнения группы, второй вход которой соединен с выходом первого счетчика, отличающеесятем, чтос целью сокращения среднего времени обслуживания заданий в вычислительной системе, в него введены первый, второй, третий, четвертый, пятый и шестой элементы ИЛИ, первый и второй распределители импульсов, группа триггеров, вторая и третья группы элементов И, первый и второй элементы задержки, первая и вторая группы регистров, первая, вторая, третья, четвертая и пятая группы блоков элементов И, первый, второй и третий блоки элементов ИЛИ, второй и третий счетчики, первый, второй и третий дешифраторы, первый и второй элементы И, группа элементов НЕ, элемент НЕ и элемент И-НЕ, причем каждый вход группы информационных входов устройства подключен к единичным входам триггеров одноименной строки матрицы формирователей дуг, вход запуска устройства соединен с первым входом первого и второго элементов ИЛИ, с единичными входами триггеров группы и входом а сброса второго счетчика, выход пер- ф ваго элемента ИЛИ подключен к счет" ному входу первого счетчика, вторым входам элементов И первой группы и к С входу первого элемента задержки,выхо. ды элементов ИЛИ первой. группы сое- ф динены с входами третьего элемента ИЛИ, выход которого подключен к первому входу .первого элемента И и через элемент НЕ и второй элемент задерж-ки - к выходу конца обслуживания устройства и входам сброса первого и третьего счетчиков,и счетчиков Ъ группы, выход каждой схемы сравнения ффс группы соединен с первым. входом одноименного элемента И второй группы , выход которого подключен к нулевому входу одноименного триг гера группы, к первому входу одно- ,фЬ именного блока элементов И первой группы и к соответствующему входу третьего элемента ИЛИ, выход которого соединен со счетным входом третьего счетчика., выход первого элемента задержки подключен к входу1037267 запуска первого распределителя импульсов каждый выход котсрого соединен с вторым входом одноименного элемента И второй группы, третий вход которого подключен к единично.му выходу одноименного триггера груп. пы, каждый вход первой группы кодовых входов устройства соединен с входом одноименного регистра первой группы, выход которсго подключен к второму входу одноименного блока элементов И первой группы, выход которого соединен с соответствующим входом первого блока элементов ИЛИ, выход которого подключен к первым входам блоков элементов И второй группы, выход каждого блока элементов И второй группы соединен с входои одноименного регистра второй гру ппы, выход которого подключен к первому входу одноименного блока эле ментов И третьей группы, выход каждого из которых соединен с соответствующим входом второго. блока элемен тов ИЛИ, выход которого подключен к первым входам блоков элементов И четвертой группы, выход третьего счетчика соединен с первым входом ,блока элементов И ъ входом первого дешифратора, каждый выход которого подключен к вторым входам одноименного блока .элементов И второй группы, каждый вход группы сигнальных входов устройстве соединен с вторцм входом одноименного блока элементов И четвертой группы и с соответствующим входом четвертого элемента ИЛИ выход которого подключен к первому входу второго элемента И, выход которого соединен со счетным входом вто" рого счетчика, выход которого подключен к второму входу блока элементов Изобретение относится к вычислительной технике, в частности, к устройствам для управления вычислительной системой. Известно устройство для опреде.ления кратчайшего пути в графе,содержащее генератор импульсов и матрицу Формирователей дуг.1 1. И и входу первого дешифратора, каждцйвыход которого соединен с первым входом,одноименного блока элементов Итретьей группы, выходы блока эле"ментов И соединены с входами элемента И-НЕ, выход которого подключен к второму входу второго элемента И, каждый вход группы сигнальных входов устройства соединен с входом одноименного элемента НЕ группы,выход которого подключен к третьим входам блоков элементов И четвертой группы, начиная с второгоблока, выход каждого блока элементовИ четвертой группы соединен с соответствующим выходом, группы информационных выходов устройства, каждыйвход второй группы кодовых входов устройства подключен к первому входу одноименного блока элементов Ипятой группы, выход которого соединен с соответствующим входом третьего блока элементов ИЛИ , выход которого подключен к входу второгодешифратора, каждый выход которогосоединен с нулевыми входами триггеров одноименной строки матрицы формирователей дуг и соответствующим.входом пятого элемента ИЛИ, выходкоторого подключен к второму входупервого элемента ИЛИ, выход второгоэлемента ИЛИ соединен с вторымвходом первого элемента И, выходкоторого подключен к входу запускавторого распределителя импульсов,каждый выход которсго соединенс вторым входом одноименногоблока элементов И пятой группы, последний выход второго распределителя импульсов . соединенс вторым входом шестого элемента ИЛИ,Недостатком этого устройства является невозможность распределения узлов графов по рангам.Наиболее близким по технической сущности к изобретению является устройство для моделирования сетевых графов, содержащее матрицу формирователей дуг, блок управления, генератор импульсов, триггеры037267 4 10 3формирователей дуг, элементы ИЛИ и И, регистрирующие счетчики, счет 4 ик числа импульсов, блоки сравнения. Элементы устройствасоединены следующим образом, Выход генератора импульсов соединен с входом блока управления, выход которого под ключен к счетному входу счетчика им,пульсов и к вторым входам элементов И, Выход счетчика числа импульсов соединен с вторыми входами блоков сравнения. Единичные выходы триггеров формирователей дуг каждого столбца матрицы формирователей дуг подключены к входам соответствующего элемента ИЛИ, выход которого соединен с первым входом соответствующего элемента И. Выходы элементов И соединены со счетными входами регистрирующих счетчиков, выходы которых подключены к первым входам блоков сравнения. Выход соответствующего блока сравнения соединен с нулевыми входами триг. геров формирователей дуг соответствующей строки матрицы формирователей дугГ 3Недостатком известного устройства является большое среднее время обслуживания заданий в вычислительной системе. Целью изобретения является сокращение среднего времени обулуживания заданий в вычислительной системе,Поставленная цель достигаетсятем, что в устройство для управления вычи сли тел ь ной системой, содержащее матрицу формирователей дуг,включающую М групп по М триггеров. в каждой (М - число заданий), группуэлементов ИЛИ, первую группу элементов И, первый ачетчик, группу счетчиков и группу схем сравнения, единичные выходы триггеров каждогостолбца матрицы формирователей дугсоединены с входами одноименногоэлемента ИЛИ первой группы, выходкоторого подключен к первому входуодноименного элемента И первой группы, выход которого соединен с счет-ным входом одноименного счетчикагруппы, выход которого подключен кпервому входу одноименной схемысравнения группы, второй вход которой соединен с выходом первогосчетчика, введены первый, второй,третий, четвертый, пятый и шестой элементы,ИЛИ, первый и второй распределители импульсов, группа триггеров вторая и трет ья группы элементов И, первый и второй элементызадержки, первая и вторая группы регистров, первая, вторая, третья,четвертая и пятая группы блоковэлементов И, первый, второй и третий блоки элементов ИЛИ, второй и третий счетчики, первый, второй и третий дешифраторы, первый и второйэлементы И, группа элементов НЕ,элемент НЕ и элемент И-НЕ, причемкажд й вход группы информационныхвходов устройства подключен к единичным входам триггеров одноименной стро.ки матрицы формирователей дуг, вход за-.пуска устройства соединен с первымвходом первого и второго элементовИЛИ, с единичными входами триггеровгруппы и входом сброса второго счетцика, выход первого элемента ИЛИподключен к счетному входу первогосчетчика, вторым входам элементов Ипервой группы и к входу первого зле,",мента задержки, выходы элементов ИЛИпервой группы соединены с входами третьего элемента ИЛИ,выход которогоподключен к первому входу первогоэлемента И и через элемент НЕ и второй элемент задержки - к выходу конца обслуживания устройства и входамсброса первого и третьего счетчикови счетчиков группы, выход каждой схемы сравнения группы соединен с первым входом одноименного элемента Ивторой группы, выход которого подключен к нулевому входу одноименноготриггера группы, к первому входу од 40ноименного блока элементов И первойгруппы и к соответствующему входутретьего элемента ИЛИ, выход которогосоединен со счетным входом третьегосчетчика, выход первого элемента за 45держки подключен к входу запускапервого распределителя импульсов,каждый выход которого соединен с вторымвходом одноименного элемента И второй группы, третий вход которого под 50ключен к единичному выходу одноименного триггера группы, каждый входпервой группы кодовых входов устройства соединен с входом одноименногорегистра первой группы, выход которого подключен к второму входу одноимен" 55 ного блока элементов И первой группы, выход которого соединен ссоответствующим входом первого блокаэлементов ИЛИ, выход которого подклю1037267 10 15 20 30 чен к первым входам блоков элементовИ второй группы, выход каждого блокаэлементов И второй группы соединен свходом одноименного регистра второй группы, выход которого подключенк первому входу одноименного блокаэлементов И третьей группы, выход каждого из которых соединен с соответ ствующим входом второго ь блока элементов ИЛИ, выход которого подключен к первым входам блоков элементов И четвертой группы, выход третьего счетчика соединен с первым входом блока элементов И и. входом первого дешифратора, каждый выход которого подключен к вторым входвм одноименно" го блока элементов И второй группы, каждый вход группы сигнальных входов устройства соединен с вторым вхо 1 дом одноименного блока элементов. И четвертой группы и с соответствую" щим входом четвертого элемента ИЛИ, выход которого подключен к первому входу второго элемента И, выход которого соединен со счетным входом второго счетчика, выход которого подключен к второму входу блока элементов И и входу первого дешифратора, каждый выход которого соединен с первым входом одноименного блока элементов И третьей группы; выходы блока элементов И соединены с вхо, дами элемента И-НЕ, выход которого подключен к второму входу второго элемента И, каждый вход группы сигнальных входов устройства соединен;с входом одноименного элемента НЕгруппы, выход которого подключен ктретьим входам блоков элементов Ичетвертой группы, начиная с второгоблока, выход каждого блока элементов.И четвертой группы соединен с соответствующим вцходом группы информационных выходов устройства, каждыйвход второй группы кодовых входовустройства подключен к первому входуодноименного блока элементов И пятойгруппы, выход которого. соединен с соответствующим входом третьего блока элементов ИЛИ, выход которого подключен к входу второго дешифратора, каждыйвыход которого соединен с нулевымивходами триггеров одноименной строкиматрицы Формирователей дуг и соот"ветствующим входом пятого элемента . 55ИЛИ, выход которого подключен к второму входу первого элемента ИЛИ, выход второго элемента ИЛИ соединен с вторым входом первого элемента И,выход которого Подключен к входу запуска второго распределителя импульсов, каждый выход которого соединен с вторым входом одноименного блока элементов И пятой группы, последний выход вто рого распределителя импульсов соеди" нен с вторым входом шестого элемента ИЛИ.На чертеже дгеа етруктурная схема устройства.Устройство содержит матрицу 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, элемент И-НЕ 39, элемент 40 задержки, группу информационных входов 41 устройства, группу кодовых входов 42 устройства, группу сигнальных входов 43 устройст. ва, группу кодовых входов 44 устройства, вход 45 запуска устройства, выход 46 конца обслуживания устройства, группу информационных выходов 47 устройства. Устройство работает следующим образом,8 исходном состоянии триггеры 4 и 10 , счетчики 7, 8 и 17 обнулены. Первоначально в триггеры 4 матрицы 1 формирователей дуг по входам 41 заносится информация с топологии графа (вершины которого соответствуют заданиям, а ветви - информационно. управляющим связям между ними).При этом триггеры 4 устанавливаются в единичное состояние.В соответствующий регистр 13 по входу 42 заносится код номера задания . и исходный данные для его выпол,нения,Номер триггера, установленного вединичное состояние, определяется пе.ресечением строки с номером, равнымномеру начальной вершины ветви, истолбца с номером, равным номеру ееконвчыой вершины.В работе устройства можно выделитьтри этапа.На первом этапе производится определение независимых заданий (планирование обработки заданий), Приэтом на выходе элементов ИЛИ 5 встолбцах, соответствующих начальнымвершинам информационно-управляющегографа, появятся низкие потенциалы,так как начальные вершины не содержат входящих ветвей и триггеры 4 вэтих столбцах будут в нулевом состоянии. Импульс запуска по входу 45 через элемент ИЛИ 2 поступает на вторые входы всех элементов И 6 и счетный вход счетчика 8. Импульс запускаустанавливает в единичное состояниевсе триггеры 1 О и обнуляет счетчик23. При этом импульс запуска не проходит через элементы И 6 на счетчики 7 тех столбцов матрицы 1,все триггеры 4 которых находятсяв нулевом состоянии. Далее содержимое каждого счетчика 7 поступает на первый вход соответствующей схемы 9, а на другой вход этой схемы поступает информация со счетчика 8. При несовпадении показаний счетчиков 7 и 8 схема вырабатывает сигнал, который поступа. ет на первый вход соответствующего элемента И. 11; Импульсы с распределителя 3 импульсов .разрешают поочередное прохождение импульсов схем 9 тех столбцов матрицы 1, триггеры 10 которых находятся в единичном состоянии, на вторые входы элементов И 14.На втором этапе работы устройства производится выбор независимых заданий, запись кодов их номеров и исходных данных в регистры 20.Импульсы с выходов элементов И 11 поочередно через элемент. ИЛИ 16 поступают на счетный вход счетчика 17.и обнуляют триггеры 10. Дешифратор 18 декодирует содержимое счетчика 17 и поочередно открывает один из блоков элементов И 19, Содержимое регистров 13 поочередно через блоки50 5 015 2025 30 3540 элементов И 14, ИЛИ 15 и И 19 записывается в соответствующие регистры 201.На третьем этапе, работы устройства обеспечивается распределение независимых заданий по процессорам, выдача процессорам вычислительной системы исходных данных для обслуживания заданий и установка в нулевое состояние триггеров 4 матрицы 1 тех строк, номера которых соответствуют кодам номеров заданий, обслуженных процессорами, Сигналы готовности процессоров по входам 43 устройства через элемент ИЛИ 28 и при наличии нераспределенных заданий в блоке регистров 20 (о чем свидетельствует единичный сигнал с выхода элемента И-НЕ 39, т.е. содержимое счетчиков 17 и 23 не совпадает) через элемент И 25 поступают на счетный вход счетчика 23. Дешифратор 24 декодирует со. держимое счетчика 23 и разрешает прохождение информации из регистра 20 через элементы И 21, ИЛИ 26 и И 29 на свободный процессор по выходам 47 устройства,При этом, если в данный момент времени свободны два и более процессоров (т.е. по нескольким входам 43 поступают единичные сигналы), то задание поступит на выход 47 устройства с меньшим номером, что обеспечивается элементами НЕ 27. По окончании обслуживания задания процессором по соответствующему входу 43 поступит сигнал готовности, а по входу 44- код номера обслуженного задания, Если одновременно законченообслуживание двух и более заданий,то распределитель 34 импульсов разрешит поочередное прохождение кодовномеров обслуженных заданий черезэлементы И 30 и ИЛИ 31. Дешифратор. 32 декодирует код номера обслуженного задания. Импульс с выхода дешифратора 32 установит в нулевое состояние триггеры 4 соответствующей строки матрицы 1 и через элемент 33 поступит на второй вход элемента ИЛИ 2. При этом импульс с выхода дешифратора 32 будет выполнять функции импульса запуска и начнется повторное выполнение первого этапа работыустройства.При обнулении всех триггеров 4 матрицы 1 на выходах всех элементов ИЛИ 5. и выходе элемента ИЛИ 36будет нулевой сигнал, который запретит запуск по элементу И 35 распПодписно аказ 601 ИПИ раж юВПроектная,Филиал ППП "Патент Ужгород 9 1 ределителя 3 ч импульсов и поступит на вход элемента НЕ 38. Единичный сигнал с выхода элемента НЕ 38 через элемент 40 задержки (необходимо время для записи в регистры 20 инФормации по всем оставшимся невыбранным независимым заданиям из реги 037267 30стров 13) обнуляет счетчики 7;8, 13 и поступает на выход 46 устройства.На этом работа устройства заканчивается.5 Применение изобретения позволяет сократить среднее. время обслуживания заданий в вычислительной системе.