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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИУ

РЕСПУБЛИК

„„SU„„1037267

gmgG06F1/20

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР пО WJ1AM ИЗОБРЕТЕНИЙ V ОЪ ЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ - .

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21 ) 3433143/1В-24 (22 ) 30.04.62 (46 ) 23.08.83. Бюл . И 3 1 (72) B. В. Иазаник (53 ) 681.325 (088.8) (56) l Авторское .свидетельство СССР

М 525954, кл, G 06F 15/20, 1977.

2. Авторское свидетельство СССР и 716043, кл. G 06 F 15/20, 1980 (прототип). (54 )(57 ) УСТРОЙСТВО ДЛЯ УПРАВЛЕНИЯ

ВЫЧИСЛИТЕЛЬНОЙ СИСТЕИОЙ, содержащее матрицу формирователей дуг, включающую и групп по и (й - число заданий ) триггеров в каждой, группу элементов ИЛИ, первую группу элементов И, первый счетчик, группу счетчиков и группу схем сравнения, единичные выходы триггеров каждого столбца матрицы формирователей дуг соединены с входами одноименного элемента ИЛИ первой группы, выход которого под. ключен к первому входу одноименного элемента И первой группы, выход которого соединен со счетным входом одноименного счетчика группы, выход. которого подключен к первому входу одноименной схемы сравнения группы, второй вход которой соединен с выходом первого счетчика, отличающеесятем, чтос целью сокращения среднего времени обслуживания заданий в вычислительной системе, в него введены первый, второй, третий, четвертый, пятый и шестой элементы ИЛИ, первый и второй распределители импульсов, группа триггеров, вторая и третья группы элементов И, первый и второй элементы задержки, первая и вто° рая группы регистров, первая, вторая, третья, четвертая и пятая группы блоков элементов И, первый, второй и третий блоки элементов ИЛИ, второй и третий счетчики, первый, второй и третий дешифраторы, первый и второй элементы И, группа элементов НЕ элемент НЕ и элемент И-НЕ, причем каждый вход группы информационных .входов устройства подключен к единичным входам триггеров одноименной строки матрицы формирователей дуг, вход запуска устройства соединен с первым входом первого и второго элементов ИЛИ, с единичными входами триггеров группы и входом сброса второго счетчика, выход первого элемента ИЛИ подключен к счетному входу первого счетчика, вторым входам элементов И первой группы и к С входу первого элемента задержки,выходы элементов ИЛИ первой. группы сое- Я динены с входами третьего элемента

ИЛИ, выход которого подключен к первому входу .первого элемента И и через элемент НЕ и второй элемент эадерж- © ки - к выходу конца обслуживания устройства и входам сброса первого и третьего счетчиков;и счетчиков Cb группы, выход каждой схемы сравнения с группы соединен с первым. входом одноименного элемента И второй группы, выход которого подключен к нулевому входу одноименного триг-гера группы, к первому входу одно-,фЬ именного блока элементов И первой группы и к соответствующему входу. третьего элемента ИЛИ, выход которого соединен со счетным входом третьего счетчика., выход первого элемента задержки подключен к входу

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

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

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

Известно устройство для опреде.ления кратчайшего пути в графе,содержащее генератор импульсов и матрицу формирователей дуг. 1 ).

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

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

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

Недостатком этого устройства является невозможность распределения узлов графов по рангам.

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

037267 4

10 з 3 формирователей дуг, элементы ИЛИ и

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

Недостатком известного устройства является большое среднее время обслуживания заданий в вычислительной системе.

Целью изобретения является сокращение среднего времени обулуживания заданий в вычислительной системе.

Поставленная цель достигается тем, что в устройство для управления вычислительной системой, содержащее матрицу формирователей дуг, включающую N групп по N триггеров . s каждой (N - число заданий), группу элементов ИЛИ, первую группу элементов И, первый ачетчик, группу счетчиков и группу схем сравнения, единичные выходы триггеров каждого столбца матрицы формирователей дуг соединены с входами одноименного элемента ИЛИ первой группы, выход

- которого подключен к первому входу одноименного элемента И первой группы, выход которого соединен с счет- ным входом одноименного счетчика группы, выход которого подключен к первому входу одноименной схемы сравнения группы, второ" вход которой соединен с выходом первого счетчика, введены первый, второй, третий, четвертый, пятый и шестой элементы,ИЛИ, первый и второй распределители импульсов, групва триггеров,,вторая и третья группы элементов И, первый и второй элементы задержки, первая и вторая группы per гистров, первая, вторая, третья, четвертая и пятая группы блоков элементов И, первый, второй и третий блоки элементов ИЛИ, второй и третий счетчики, первый, второй и третий дешифраторы, первый и второй элементы И, группа элементов НЕ, элемент НЕ и элемент И-НЕ, причем кажд и вход группы информационных входов устройства подключен к единич-! ным входам триггеров одноименной строки матрицы формирователей дуг, вход за-. пуска устройства соединен с первым входом первого и второго элементов

ИЛИ, с единичными входами триггеров группы и входом сброса второго счетчика, выход первого элемента ИЛИ подключен к счетному входу первого счетчика, вторым входам элементов И первой группы и к входу первого зле.". мента задержки, выходы элементов ИЛИ первой группы соединены с входами третьего элемента ИЛИ,выход которого подключен к первому входу первого элемента И и через элемент НЕ и второй элемент задержки — к выходу конца обслуживания устройства и входам сброса первого и третьего счетчиков и счетчиков группы, выход каждой схе. мы сравнения группы соединен с пер-35 вым входом одноименного элемента И второй группы, выход которого подключен к нулевому входу одноименного триггера группы, к первому входу од40 ноименного блока элементов И первой группы и к соответствующему входу третьего элемента ИЛИ, выход которого со "динен со счетным входом третьего счетчика, выход первого элемента за45 держки подключен к входу запуска первого распределителя импульсов,каждый выход которого соединен с вторым входом одноименного элемента И второй группы, третий вход которого под50 ключен к единичному выходу одноименного триггера группы, каждый вход первой группы кодовых входов устройства соединен с входом одноименного регистра первой группы, выход которого подключен к второму входу одноимен55 ного блока элементов И первой группы, выход которого соединен с соответствующим входом первого блока элементов ИЛИ, выход которого подключ

1037267 чен к первым входам блоков элементов.

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

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

ro блока элементов И второй группы, каждый вход группы сигнальных входов устройства соединен с вторым вхо1дом одноименного блока элементов. И четвертой группы и с.соответствующим входом четвертого элемента ИЛИ, выход которого подключен к первому входу второго элемента И, выход которого соединен со счетным входом второго счетчика, выход которого подключен к второму входу блока weментов И и входу первого дешифратора, каждый выход которого соединен с первым входом одноименного блока элементов И третьей группы; выходы блока элементов И соединены с вхо; дами элемента И-НЕ, выход которого

: подключен к второму входу второго

t5

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

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

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

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

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

Устройство содержит матрицу 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, элемент HE 38, элемент

И-НЕ 39, элемент 40 задержки, группу информационных входов 41 устройства, группу кодовых входов 42 устройства, группу сигнальных входов 43 устройства, группу кодовых входов 44 устройства, вход 45 запуска устройства, выход 46 конца обслуживания устройства, группу информационных выходов

47 устройства.

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

8 исходном состоянии триггеры 4 и 10, счетчики 7, 8 и 17 обнулены °

Первоначально в триггеры 4 матрицы

1 формирователей дуг по входам 41 заносится информация с топологии графа (вершины которого соответствуют заданиям, а ветви - информационноуправляющим связям между ними).

При этом триггеры 4 устанавливаются в единичное состояние.

В соответствующий регистр 13 по входу 42 заносится код номера зада1037267 8 ния . и исходный данные для его выпол, нения.

Номер триггера, установленного в единичное состояние, определяется пересечением строки с номером, равным номеру начальной вершины ветви, и столбца с номером, равным номеру ее конвчыой вершины.

В работе устройства можно выделить три этапа.

На первом этапе производится определение независимых заданий (планирование обработки заданий), При этом на выходе элементов ИЛИ 5 в столбцах, соответствующих начальным вершинам информационно-управляющего графа, появятся низкие потенциалы, так как начальные вершины не содержат входящих ветвей и триггеры 4 в этих столбцах будут в нулевом состоя. нии. Импульс запуска по входу 45 через элемент ИЛИ 2 поступает на вторые входы всех элементов И 6 и счетный вход счетчика 8. Импульс запуска устанавливает в единичное состояние все триггеры 10 и обнуляет счетчик

23. При этом импульс запуска не проходит через элементы И 6 на счетчики 7 тех столбцов матрицы 1, все триггеры 4 которых находятся в нулевом состоянии.

Далее содержимое каждого счетчи-!

ice 7 поступает на первый вход соответствующей схемы 9, а на другой вход этой схемы поступает информация со счетчика 8. При несовпадении показаний счетчиков 7 и 8 схема вырабатывает сигнал, который поступает на первый вход соответствующего элемента И 11; Импульсы с распреде лителя 3 импульсов .разрешают поочередное прохождение импульсов схем

9 тех столбцов матрицы 1, триггеры

10 которых находятся в единичном состоянии, на вторые входы элементов

И 14.

На втором этапе работы устройства производится выбор независимых заданий, запись кодов их номеров и исходных данных в регистры 20.

Импульсы с выходов элементов

И 11 поочередно через элемент. ИЛИ 16 поступают на счетный вход счетчика

17 и обнуляют триггеры 10. Дешифратор 18 декодирует содержимое счетчика 17 и поочередно открывает один из блоков элементов И 19. Содержимое регистров 13 поочередно через блоки

55

40 элементов И 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 на выходах всех weментов ИЛИ 5 и выходе элемента ИЛИ 36 будет нулевой сигнал, который запретит запуск по элементу И 35 распВНИИПИ Заказ 6012/51 Тираж 706 Подписное

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4

9 1 редели теля 34 импульсов и поступит на вход элемента НЕ 38. Единичный сигнал с выхода элемента НЕ 38 через элемент 40 задержки (необходимо время для записи в регистры 20 информации по всем оставшимся невыбранным независимым заданиям из реги037267 10 стров 13) обнуляет счетчики 7;8,17 и поступает на выход 46 устройства.

На этом работа устройства заканчивается.

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