Устройство для выбора заданий Советский патент 1983 года по МПК G06F9/50 G06F9/54 

Изобретение относится к вычисли тельной технике и может быть испол зовано для автоматизации выбора за даний на решение в системе обработки данных. Известно устройство для определ ния кратчайшего пути в графе, содержащее генератор импульсов и мат цу формирователей дуг Недостатком устройства является невозможность распределения узлов графов по рангам. Наиболее близким техническим ре шением к изобретению является устройство для моделирования сетевых графов, содержащее матрицу формирователей дуг, блок управления, ге ратор импульсов, триггеры формирователей дуг, элементы ИЛИ, И, реги стрирукщие счетчики, счетчик числа импульсов, блоки сравнения 2, Недостатком устройства является невозможность распределения задани по рангам с учетом ограниченного ресурса. Цель изобретения - расширение области применения устройства за счет возможности выбора заданий по рангам с учетом ограниченного ресурса. Поставленная цель достигается тем, что в устройство для выбора заданий, содержащее матрицу тригге ров, группу элементов ИЛИ, первую группу элементов И, группу счетчико группу схем сравнения и счетчик так тов , причем единичные выходы тригге ров каждого столбца матрицы соединены с входами соответствующего эле мента ИЛИ группы, выход.каждого элемента ИЛИ группы соединен с первым входом соответствующего элемента И первой группы, выходы элементов И первой группы соединены со . счетными входами счетчиков группы, выходь которых соединены с первыми входами соответствующих схем сравнения группы, вторые входы которых соединены с выходом счетчика тактов, введены два элемента ИЛИ, элемент НЕ, счетчик ресурсов, элемент И,вторая, третья и четвертая группы элементов. И, первая и вторая группы триггеров и группа элементов задержки, причем первый вход элемента И соединен.с тактовым входом устрой ства, второй вход элемента И соединен с выходом первого элемента ИЛИ, входы которого соединены с выходами элементов ИЛИ группы, выход элемент И соединен с вторыми входами элемен тов И первой группы, со счетным вхо дом счетчика тактов и с входом первого элемента задержки группы, выход каждого элемента задержки группы соединен с первым входом одноименного элемента И второй группы и с входом следующего элемента, задержки группы, вторые входы элементов И второй группы соединены с единичными выходами соответствующих триггеров первой группы, нулевые ;и единичные входы которых соединены соответственно с единичными выходами триггеров второй группы и с выходами соответствующих элементов И третьей группы, первый и второй входы каждого элемента И третьей группы соединены соответственно с нулевьом выходом соответствующего триггера второй группы и с выходом соответствующей схемы сравнения группы, единичный вход каждого триггера второй группы соединен с вьдходом соответствующего элемента И четвертой группы, первый и второй входы каждого из которых соединены соответственно с выходом элемента НЕ и с выходом соответствующего элемента И второй группы, выходы элементов И четвертой группы соединены с нулевыми входами триггеров соответствующих строк матрицы и с группой информационных выходов устройства, выходы элементов И второй группы соединены -с входами второго элемента ИЛИ, выход которого соединен со счетным входом счетчика ресурсов, информационный вход которого соединен с информационным входом устройства, выход переполнения счетчика ресурсов соединен с входом элемента НЕ, На чертеже представлена структурная схема устройства. Предлагаемое устройство содержит матрицу 1, элемент И 2, первый элемент ИЛИ 3, триггеры 4 матрицы 1, группу элементов ИЛИ 5, группу элементов И б, группу счетчиков 7, счетчик 8 тактов, группу схем 9 сравнения, группу триггеров 10, группу элементов И 11, группу триггеров 12, группу элементов 13 задержки, riJynпы элементов И 14 и 15, элемент ИЛИ 16, счетчик 17 ресурсов, элемент НЕ 18, тактовый вход 19 устройства, информационный вход устройства- 20, информационные 5ЫХОДЫ 21 устройства. Устройство работает следующим образом. , . Первоначально в матрицу 1 с помощью управляющей программы заносится информация о топологии графа (связях между заданиями. При этом соответствующие триггерьа 4 устанавливаются в единичное состояние (единичные входы триггеров на чертеже не показаны;. Номер триггера 4 определяется пересечением строки с номером, равным номеру начального узла дуги, и столбца с номером, равным номеру ее конечного узла. При этом на выходе элементов ИЛИ 5 в столбцах, соответствующих начальным заданиям графа, появляются.

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

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

Одновременно единичный сигнал с выхода элемента НЕ 18 через соответствующий элемент И 15 устанавливает в нулевое состояние триггер 4 . ветствующей строки матрицы. При этом на соответствукнцем выходе 21 появляется единичный сигнал, свидетельствующий о наличии задания. Если для какогото задания графа данного ранга нет единицы ресурса (.число заданий дан-t ного ранга превышает число единиц ресурса;, то на выходе элемента НЕ 18 появляется нулевой сигнал и обнуление триггеров 12 и триггеров 4 стрюки матрицы 1 не происходит,

После управляющая программа системы обработки данных заносит в счетчик 17 ресурсов новое количество единиц ресурса, вырабатывает очередной импульс запуска и рассмотренный процесс повторяется,.Процесс заканчивается при обнулении всех триггеров 4 матрицы 1, Это свидетельствует о том, что все задания распределены по рангам с учетом ограниченного ресурса. При этом на выходе элемента ИЛИ 3 появляется нулевой сигнал, который запрещает прохождение импульсов запуска череэ элемент И 2, Максимальное число последовательных шагов при этсяч не превышает числа заданий, поступающих на обработку. Число импульсов, зафиксированное на каждом счетчике 7, соответствует номеру ранга каждого задания с учетом ограниченного ресурса, а на соответств ющих выходах 21 поочередно в ороцессе работы устройства появляются единичные- сигналы, которые свйдетельст- вуют о том, что задание конкретного ранга обеспечено единицей ресурса.

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

2J.

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