Устройство для выбора заданий

 

УСТРОЙСТВО ДЛЯ . ВЫБОРА ЗАДАН ИЙ , содержащее матрицу триггеров, ;группу элементов ИЛИ, первую группу элементов И, группу счетчиков, группу схем сравнения и счетчик тактов, причем единичные выходы триггеров ; каждого столбца матрицы соединены с входами соответствующего элемента ИЛИ группы, выход каждого элемента ИЛИ группы соединен с первым входом соответствующего элемента И первой . группы, выходы элементов И первсэй группы соединены со счетньами входами счетчиков группы, выходы которых соединены с первыми входами соответствующих схем сравнения группы, вто- . рые входы которых соединены с выходом счетчика тактов, о т л и ч а- . ю щ е е с я тем, что, с целью расширения области применения, устройство содержит два элемента ИЛИ, элемент НЕ, счетчик ресурсов, элемент И, вторую , третью и четвертую группы элементов Kf первую и вторую группы триггеров и группу элементов задержки , причем первый вход элемента И соединен соединен с тактовым входом устройства, второй вход элемента И соединен с выходом первого элемента ИЛИ, входы которого соединены с выходами элементов ИЛИ группы, вы;ход элемента И соединен с вторыми входами элементов И первой группы, со счетным входом счетчика тактов и с входом первого элемента задержки группы, выход каждого элемента задержки группы соединен с первым Bxot дом одноименного элемента И второй группы и с входом следующего элемента задержки группы, вторые входы элементов И второй группы соединены с единичными выходами соответствующих триггеров первой группы,, нулевые и единичные входы которых соединены соответственно с единичными выходами триггеров второй группы и с выходами соответствующих элементов И третьей группы, первый и второй входы каждого элемента И третьей О) группы соединены соответственно с нулевым выходом соответствующего . триггера второй группы и с выходом соответствующей схемы сравнения груп; пы, единичный «ход каждого триггера второй группы соединен с выходом соответствующего элемента И четвертой группы, первый и второй входы каждого из которых соединены соответственно с выходом элемента НЕ и с выходом соответствующего элемента И о: второй группы, выходы элементов И со четвертой группы соединены с нулевыми входами триггеров соответствуюOJ щих строк материцы и с группой инСА формационных выходов .устройства, выходы элементов И второй группы соединены с входами второго элемента ИЛИ, выход которого соединен со счетным входом счетчика ресурсов, информационный вход которого соединен с .информационным входом устройства, выход переполнения счетчика ресурсов соединен с входом элемента НЕ,

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

СОЦИАЛИСТИЧЕСКИХ

РЕСГ1УБЛИН

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВ,Ф (21)3317928/18-24. (22)17.07 ° 81 (46)23.04.83. Бюл, Р 15 (72)А, Х. Ганитулин, В, В, Мазаник и А, И. Шутилов .(53) 681. 325 (088. 8) (56)1, Авторское свидетельство СССР

Р 525954 кл, G 06 F 15/20 1974, 2, Авторское свидетельство СССР .Р 716043, кл. G 06 F 15/20, 1980 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ ВЫБОРА ЗАДАНИЙ, содержащее матрицу триггеров, группу элементов ИЛИ, первую группу элементов И, группу счетчиков, группу схем сравнения и счетчик тактов, причем единичные выходы триггеров каждого столбца матрицы соединены с входами соответствующего элемента

ИЛИ группы, выход каждого элемента

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

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

ИЛИ, входы которого соединены с выходами элементов ИЛИ группы, вы„„SU „„1013963 А э(5ВС 06 F 15 20; G 06 F 9 46 ход элемента И соединен с вторыми входами элементов И первой группы, со счетным входом счетчика тактов и с входом первого элемента задержки группы, выход каждого элемента задержки группы соединен с первым вхо» дом одноименного элемента И второй группы и с входом следующего элемента задержки группы, вторые входы элементов И второй группы соединены " с единичными выходами соответствующих триггеров первой. группы, нулевые и единичные входы которых соединены соответственно с единичными выходами триггеров второй группы и с выходами соответствующих элементов

И третьей группы, первый и второй 3 входы каждого элемента И третьей группы соединены соответственно с нулевым выходом соответствующего . триггера второй группы и с выходом соответствующей схемы сравнения группы, единичный вход каждого триггера второй группы соединен с выходом соот ветствующего элемента И четвертой группы, первый и.второй входы каждого из которых соединены соответ- 4 ) ственно с выходом элемента НЕ и с выходом соответствующего элемента И второй группы, выходы элементов И четвертой группы соединены с нуле- (© выми входами триггеров соответствую- ау щих строк материцы и с группой ин- ® » формационных выходов .устройства, вы- фф ходы элементов И второй группы соединены с входами второго элемента

ИЛИ, выход которого соединен со счет. .ным входом счетчика ресурсов, информационный вход которого соединен с ,информационным входом устройства, выход переполнения счетчика ресурсов соединен с входом элемента НЕ, .

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

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

Предлагаемое устройство содержит матрицу 1, элемент И 2, первый элемент ИЛИ 3, триггеры 4 матрицы 1, группу элементов ИЛИ 5, группу элементов И 6, группу счетчиков 7, счетчик 8 тактов, группу схем 9 сравнения, группу триггеров 10, группу элементов И 11, группу триггеров 12, группу элементов 13 задержки, группы элементов И 14 и 15, элемент ИЛИ

5 .16, счетчик 17 ресурсов, элемент HE

18, тактовый вход 19 устройства, информационный вход устройства- 20, информационные выходы 21 устройства.

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

30

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

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

И соединен с вторыми входами элементов И первой группы, со счетным входом счетчика тактов и с входом пер- . 60 вого элемента задержки группы, выход каждого элемента задержки группы соединен с первым входом одноименного элемента И второй группы и с входом следующего элемента за- 65

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

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

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

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

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

При этом на выходе элементов ИЛИ

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

1013963 нулевые сигналы, так как начальные задания не содержат входящих дуг и триггеры 4 в этом столбце находятся в нулевом состоянии, Регистрирующие счетчики 7, счетчик 8, счетчик 17 ресурсов, триггеры 10 и 12 находятся в нулевом состоянии, С появлением импульса запуска на входе 19 элемент И 2 разрешает его прохождение на вторые входы элементов И б и счетчик 8. При этом импульс запуска не проходит через элементы И б на .счетчики 7 тех столбцов матрицы 1, не все триггеры 4 которых находятся в нулевом состоянии, и управлякнцая программа системы обработки данных 15 по информационному входу 20 заносит в счетчик 17 ресурсов количество единиц свободного ресурса в дополнительном коде относительно полного ресурса системы. Далее содержимое регистрирующего счетчика 7 сравнивается с содержимым счетчика 8 на схеме 9 сравнения. При несовпадении содержимого счетчиков схема 9 сравнения вырабатывает импульс, который 25 устанавливает в единичное состояние триггер 12.

Единичные сигналы с единичных выходов триггеров 12 по задержанному сигналу с выхода элементов 13 за- .. держки поочередно поступают на счет30 ный вход счетчика 17 ресурсов, Если для задания данного ранга есть единица ресурса, то на выходе элемента

НЕ 18 находится единичный сигнал, кб" торый устанавливает триггер 10 в единичное состояние, единичный сигнал с единичного выхода которого устанавливает триггеры 12 в нулевое состояние, а нулевой сигнал с нулевого выхода запрещает прохождение импуль- 40 сов через соответствующий элемент

И 11.

Одновременно единичный сигнал с выхода элемента HE 18 через соответствующий элемент И 15 устанавливает в нулевое состояние триггер 4 соот.-. ветствующей строки матрицы, При этом на соответствующем выходе 21 появляется единичный сигнал, свидетельствующий о наличии задания. Если для какогото задания графа данного ранга нет единицы ресурса число заданий дан ного ранга превышает число единиц ресурса), то на выходе элемента HE 18 появ;|яется нулевой сигнал и обнуление триггеров .12 и триггеров 4 строки матрицы 1 не происходит, После этого управляющая программа системы обработки данных заносит в счетчик 17 ресурсов новое количество единиц ресурса, вырабатывает очередной импульс запуска и рассмотренный процесс повторяется..Процесс заканчивается при-обнулеиии всех триггеров 4 матрицы 1 ° Это свидетельствует о том, что все задания распределены по рангам с учетом ограниченного ресурса, При этом на выходе элемента ИЛИ 3 появляется нулевой сигнал, который запрещает прохождение импульсов запуска через элемент И 2.

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

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

Применение изобретения позволяет расширить область применения устройства.

1013963.

Составитель М. Кудряшев

Техред Т. Фанта Корректор И. Шулла

Редактор A. Шишкина филиал ППП "Патент", г, Ужгород, ул. Проектная, 4

Заказ 3006/58 Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб,, д. 4/5