Устройство для управления вычислительной системой Советский патент 1983 года по МПК G06F9/48 G06F9/50 

запуска первого распределителя импульсов каждый выход которого соединен с вторым входом одноименного элемента И второй группы, третий вход которого подключен к единично.му выходу одноименного триггера группы, Каждый вход первой группы кодовых входов устройства соединен с входом одноименного регистра первой группы, выход которого подключен к второму входу одноименного блока элементов И первой группы, выход которого соединен с соответствующим входом первого блока элементов ИЛИ, выход которого подключен к первым входам блокое элементов И второй группы, выход каждого блока элементов И второй группы соединен с входом одноименного регистра второй группы, выход которого подключен к первому входу одноименного блока элементов И третьей группы, выход каждого из которых соединен с соответствующим входом второго.блока элемен тов ИЛИ, выход которого подключен к первым входам блоков элементов И четвертой группы, выход третьего счетчика соединен с первым входом .блока элементов И и входом первого дешифратора, каждый выход которого подключен к вторым входам одноименного блока .элементов И второй группы каждый вход группы сигнальных входов устройства соединен с вторым входом одноименного блока элементов И четвертой группы и с соответствующим входом четвертого элемента ИЛИ., выход которого подключен к первому входу второго элемента И, выход которого соединен со счетным входом второго счетчика, выход которого подключен к второму входу блока элементов

И и входу первого дешифратора, каждый выход которого соединен с первым входом ,однои2;(енного блока элементов И третьей группы, выходыблока элементов И соединены с входаг элемента И-НЕ, выход которого подключен к второму входу второго элемента И, каждый вход группы сигнальных входов устройства соединен с входом одноименного элемента НЕ группы, выход которого подключен к третьим входам блоков элементов И четвертой группы, начиная с второго блока, выход каждого блока элементов И четвертой группы соединен с соответст ующим выходом,группы информационных выходов устройства, каждый вход второй группы кодовых входов

устройства подключен к первому входу одноименного блока элементов И пятой группы, выход которого соединен с соответствующим входом третьего блока элементов ИЛИ , выход которого подключен к входу второго дешифратора, каждый выход которого соединен с нулевы входами триггеров одноименной строки матрицы формирователей дуг и соответствующим

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

блока элементов И пятой группы, последний выход второго распределителя импульсов соединен с вторым входом шестого элемента ИЛИ.

УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМОЙ, содержащее матрицу формирователей дуг, включающую N групп по N (N - число заданий ) триггеров в каждой, группу элементов ИЛИ, первую группу элементов И, первый счетчик, труппу счетчиков и группу схем сравнения, единичные выходы триггеров каждого столбца матрицы формирователей дуг соединены с входами одноименного элемента ИЛИ первой группы, выход которого под,ключей к первому входу одноименного элемента И первой группы, выход которого соединен со счетным входом одноименного счетчика группы, выход которого подключен к первому входу одноименной схемы сравнения группы, второй вход которой роединен -с выходом первого счетчика, отличающее с я тем что,с целью сокращения среднего времени обслуживания заданий в вычислительной системе, в него введены первый, второй, третий,четвертый, пятый и шестой элементы ИЛИ, первый и второй распределители импульсов, группа триггеров, вторая и третья группы элементов И, первый и второй элементы задержки, первая и вторая группы регистров, первая, вторая, третья, четвертая и пятая группы блоков элементов И, первый, второй и Третий блоки элементов ИЛИ, второй и третий счетчики, первый, второй и третий дешифраторы, первый и второй элементы И, группа элементов НЕ, элемент НЕ и элемент И-НЕ, причем каждый вход группы информационных ВХОДОВ устройства подключен к единичным входам триггеров одноименной строки матрицы формирователей дуг, вход запуска устройства соединен с первым входом первого и второго элементов ИЛИ, с единичными входами триггеров группы и входом сброса второго счетLMKa, выход первого элемента ИЛИ подключен к счетСО ному входу первого счетчика, вторым входам элементов И первой группы и к входу первого элемента задержки,выходы элементов ИЛИ первой группы соединены с входа) третьего элемента ИЛИ, выход которого подключен к первому входу первого элемента И и через со элемент НЕ и второй элемент задержки - к выходу конца обслуживания ND устройства и входам сброса первого а и третьего счетчиков ;й счетчиков н группы, выход каждой схемы сравнения группы соединен с первым входом одноименного элемента И второй группы , выход которого подключен к нулевому входу одноименного триг- гера группы, к первому входу одноименного блока элементов И педвой группы и к соответствующему входу третьего элемента ИЛИ, выход которого соединен со счетным входом третьего счетчика, выход первого элемента задержки подключен к входу

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

Мз вестно устрбйст во для опредё.ления кратчайшего пути в графе,содержаще генератор импульсов и матрицу формирователей дуг СОНедостатком этого устройства яв ляется невозможность распределения узлов графов по рангам.

Наиболее близким по техничес5 , кой сущности к изобретению является устройство для моделирования сетевых графов, содержащее матрицу формирователей дуг, блок управления, генератор импульсов, триггеры формирователей дуг, элементы ИЛИ и И, регистрирующие счетчики, счетtiHK числа импульсов, блоки сраа- нения. Элементы устройства-соединен следующим образом. Выход генератоpa импульсов соединен с входом блока управления, выход которого по ;ключен к счетному входу счетчика и .пульсов и к вторым входам элемен5;ов И. Выход счетчика числа импуль сов соединен с вторыми входами блоков- сравнения. Единичные выходы триггеров формирователей дуг каждого столбца матрицы формирователей дуг подключены к входам соответствующего элемента ИЛИ, выход которого соединен с первым входом ответствующего элемента И, Выходы элементов И соединены со счетными входами регистрирующих счетчиков, выходы которых подключены к первым входам блоков сравнения. Выход соответствующего блока сравнения соединен с нулевыми входами тр геров формирователей дуг соответствующей строки матрицы формирователей 3. Недостатком известного устройства является большое среднее врем обслуживания заданий в вычислитель ной системе. Целью изобретения является сокращение среднего времени обулужива ния заданий в вычислительной систе ме. Поставленная цель достигается тем, что в устройство для управления вычислительной системой, содер жащее матрицу формирователей дуг, включающую N групп по N триггеров в каждой (N - число заданий), груп элементов ИЛИ, первую группу элеме тов И, первый счетчик, группу счет ков и группу схем сравнения, едини ные выходы триггеров каждого столбца матрицы формирователей дуг соединены с входами одноименного элемента ИЛИ первой группы, выход которого подключен к первому входу одноименного элемента И первой гру пы, выход которого соединен с счет ным входом одноименного счетчика группы, выход которого подключен к первому входу одноименной схемы сравнения группы, второй вход кот рой соединен с выходом первого счетчика, введены первый, второй, третий, Четвертый, пятый и шестой элементы,ИЛИ, первый и второй распределители импульсов, группа триггеров , .вторая и третья группы элементов; И, первый и второй элементы задержки, первая и вторая группы per гистров, первая, вторая, третья, четвертая и пятая группы блоков элементов-И, первый, второй и третий блоки элементов ИЛИ, второй и третий счетчики, первый, второй и третий дешифраторы, первый и второй элементы И, группа элементов НЕ, элемент НЕ и элемент И-НЕ, причем каждмй вход группы информационных входов, устройства подключен к единичным входам триггеров одноименной строки матрицы формирователей дуг, вход запуска устройства соединен с первым входом первого и второго элементов ИЛИ, с единичными входами триггеров группы и входом сброса второго счетчика, выход первого элемента ИЛИ подключен к счетному входу первого счетчика, вторым входам элементов И первой группы и к входу первого . мента задержки, выходы элементов ИЛИ первой группы соединены с входами третьего элемента ИЛИ,выход которого подключен к первому входу первого элемента И и через элемент НЕ и второй элемент задержки - к выходу конца обслуживания устройства и входам сброса первого и третьего счетчиков и счетчиков группы, выход каждой схемы сравнения группы соединен с входом одноименного элемента И второй группы, выход которого подключен к нулевому входу одноимённого триггера группы, к первому входу од- , ноименного блока элементов И первой группы и к соответствующему входу третьего элемента ИЛИ, выход которого соединен со счетным входом третьего счетчика, выход первого элемента задержки подключен к входу Запуска первого распределителя импульсов,каждый выход которого соединен с вторым входом одноименного элемента И второй группы, третий вход которого подключен к единичному выходу одноименного триггера группы, каждый вход первой группы кодовых входов устройства соединен с входом одноименного регистра первой группы, выход которого подключен к второму входу одноименного блока элементов И первой группы, выход которого соединен с соответствующим входом первого блока элементов ИЛИ, выход которого подклю-

чен к первым входам блоков элементов И второй группы, выход каждого блока элементов И второй группы соединен с входом одноименного регистра второй группы, выход которого подключен к первому входу одноименного блока элементов И третьей группы, выход каждого из которых соединен с соответ ствую1дим входом второго блока элементов ИЛИ, выход которого подключен к первым входам блоков элементов И четвертой группы, выход третьего счетчика соединен с первым входом блока элементов И и входом первого дешифратора, каждый выход которого подключен к вторым входам одноименного блока элементов И второй группы, каждый вход группы сигнальных входов устройства соединен с вторым вхо1дом одноименного блока элементов. И четвертой группы и с соответствую- , щим входом четвертого элемента ИЛИ, аыход которого подключен к первому входу второго элемента И, выход которого соединен со счетным входом второго счетчика, выход которого подключен к второму входу блока элементов И и входу первого дешифратора, каждый выход KOTOpQro соединен с первым входом одноименного блока элементов И третьей группы выходы ,блока элементов И соединены с вхо; дами элемента И-НЕ, выход которого : подключен к второму входу второго Элемента И, каждый вход группы сигнальных входов устройства соединен i с входом одноименного элемента НЕ группы, выход которого подключен к третъим входам блоков элементов И четвертой группы, начиная с второго блока, выход каждого блока элементов И четвертой группы соединен с соответствующим выходом группы информационных выходов устройства, каждый вход второй группы кодовых входов устройства подключен к первому входу одноименного блока элементов И пятой группы, выход которого соединен с соответствующим входом третьего блока элементов ИЛИ, выход которого подключен к входу второго дешифратора, каждый выход которого соединен с нулевыми входами триггеров одноименной строки матрицы формирователей дуг и соответствующим входом пятого элемента .: ИЛИ, выход которого подключен к второму зходу первого элемента ИЛИ., выход второго элемента ИЛИ соединен с

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

На чертеже даыа структурная схема устройства.

Устройство содержит матрицу 1 (рамером NxN ) формирователей дуг,первый элемент ИЛИ 2, распределитель 3 импульсов, группы триггеров , группу элементов ИЛИ 5, группу элементов И 6, группу счетчиков 7, счетчик 8, группу схем 9 сравнения,группу триггеров 10, группу элементов И 11, элемент 12 задержки, группу регистров 13« группу блоков элементов И l, блок элементов ИЛИ 15, .элемент ИЛИ 1 счетчик 17 дешифратор 18, группу блоков элементов И 19 группу регистров 20, группу блоков элементов И 21, блок элементов И 22, счетчик 23f дешифратор 2k, первый элемент И 25, второй блок элементов ИЛИ 26, группу элементов НЕ 27, элемент ИЛИ 28, группу блоков элементов И 29 группу блоков элементов И 30, блок элементов ИЛИ 31, дешифратор 32, эле мент ИЛИ 33., распределитель 3 импульсов, элемент И 35, элементы ИЛИ Зб и 37, элемент НЕ 38, элемент И-НЕ 39, элемент 40 задержки, группу информационных входов 41 устройства, группу кодовых входов 42 устройства, группу сигнальных входов 43 устройства, группу кодовых входов 44 устройства, вход 45 запуска устройства, выход 46 конца обслуживания устройства, группу информационных выходов 47 устройства.

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

8 исходном состоянии триггеры 4 и 10 , счетчики 7,8 и 17 обнулены. Первоначально в триггеры 4 матрицы 1 формирователей дуг по входам 41 заносится информация с топологии графа (вершины-которого соответствуют заданиям, а - информационноуправляющим связям между ними). При этом триггеры 4 устанавливаются в единичное состояние.

8 соответствующий регистр 13 по входу 42 заносится код номера задания . и исходный данные для его выпол нения., Номер триггера, установленного в единичное состояние, определяется пе ресечением строки с номером, равным номеру начальной вершины ветви, и столбца с номером, разным номеру ее вершины. В работе устройства можно выделит три этапа. На первом этапе производится определение независимых заданий (планирование обработки заданий).. При этом на выходе элементов ИЛИ 5 в столбцах, соответствующих начальным вершинам информационно-управляющего графа, появятся низкие потенциалы, так как начальные вершины не содержат входящих ветвей и триггеры 4 в этих столбцах будут в нулевом состоя нии. Импульс запуска по входу i5 через элемент ИЛИ 2 поступает на вторые входы всех элементов И 6 и счет ный вход счетчика 8. Импульс запуск устанавливает в единичное состояние все триггеры 10 и обнуляет счетчик 23. При этом импульс запуска не про ходит через элементы И 6 на счетчики 7 тех столбцов матрицы 1, все триггеры k которых находятся в нулевом состоянии. Далее содержимое каждого счетчиi(a 7 поступает на первый вход соответствующей схемы 9. а на другой вход этой схемы поступает информация со счетчика 8. При несовпадении показаний счетчиков 7 и 8 схема вырабатывает сигнал, который поступ ет на первый вход соответствующего элемента И.11. Импульсы с распределителя 3 импульсов разрешают поочередное прохождение импульсов схем 9тех столбцов матрицы 1, триггеры 10которых находятся в единичном состоянии, на вторые входы элементо И U. На втором этапе работы устройств производится выбор независимых зада ний, запись кодов их номеров и исходных данных в регистры 20. Импульсы с выходов элементов И 11 поочередно через элемент ИЛИ 1 поступают на счетный вход счетчика 17 и обнуляют триггеры 10. Дешифратор 18 декодирует содержимое счетчика 17 и поочередно открывает один из блоков элементов И 19. Содержимо регистров 13 поочередно через блоки 78 элементов И И, ИЛИ 15 и И 19 записывается в соответствующие регистры 20j На третьем этапе.работы устройства обеспечивается распределение независимых заданий по процессорам, выдача процессорам вычислительной системы исходных данных для обслуживания заданий и установка в нулевое состояние триггеров k матрицы 1 тех строк, номера которых соответствуют кодам номеров заданий, обслужек- ных процессорами. Сигналы готовности процессоров по входам устройства через элемент ИЛИ 28 и при наличии нераспределенных заданий в блоке регистров 20 {о чем свидетельствует единичный сигнал с выхода элемента И-НЕ 39, т.е. содержимое счетчиков 17 и 23 не совпадает) через элемент И 25 поступают на счетный вход счетчика 23. Дешифратор 2k декодирует содержимое счетчика 23 и разрешает прохождение информации из регистра 20 через элементы И 21, ИЛИ 26 и И 29 на свободный процессор по выходам 7 устройства. При этом, если в данный момент времени свободны два и более процессоров (т.е. по нескольким входам поступают единичные сигналы), то задание поступит на выход 7 устройства с меньшим номером, что обеспечивается элементами НЕ 27. По окончании обслуживания задания процессором по соответствующему входу 3 поступит сигнал готовности, а по входу код номера обслуженного задания. Если одновременно закончено обслуживание двух и более заданий, то распределитель 3 импульсов разрешит поочередное прохождение кодов номеров обслуженных заданий через элементы И 30 и ИЛИ 31. Дешифратор 32 декодирует код номера обслуженного задания. Импульс с выхода дешифратора 32 установит в нулевое состояние триггеры k соответствующей строки матрицы 1 и через элемент 33 поступит на второй вход элемента ИЛИ 2. При этом импульс с выхода дешифратора 32 будет выполнять функции импульса запуска и начнется повторное выполнение первого этапа работы устройства. При обнулении всех триггеров А матрицы 1 на выходах всех элементов ИЛИ 5. и выходе элемент а ИЛИ 36 будет нулевой сигнал, который запретит запуск по элементу И 35 распределителя З импульсов и поступит на вход элемента НЕ 38. Единичный сигнал с выхода элемента НЕ 38 через элемент 0 задержки (необходимо время для записи в регистры 20 информации по всем оставшимся иевыбранным независимым заданиям из регистров 13) обнуляет счетчики 7,8,17 и поступает на выход Ц6 устройстве. На этом работа устройства заканчивается.

Применение изобретения позволяет сократить среднее время обслуживания заданий в вычислительной систем е,