Устройство для контроля распределения ресурсов Советский патент 1989 года по МПК G06F17/00 

;5

отор 5 импульсов, первый элемент И 7, четвертьй 8, третий 9 и второй 10 элементы И. Сущность изобретения состоит в -том, что новая совокупность конструктивных признаков позволяет повысить оперативность контроля и экономичность устройства путем шения времени для обнаружения тупика за счет распараллеливания процедуры поиска транзитивного замыкания рас1509898

10

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

Изобретение относится к области вычислительной техники и может найти применение в современных высокопроизводительных системах для контроля корректности распределения ресурсов. Цель изобретения - повышение оперативности контроля и экономичности устройства. Устройство для контроля распределения ресурсов содержит регистр 1, триггер режима 3, п блоков коммутаторов 4.1÷4.п, группу 6 элементов И, триггер 2 управления, генератор 5 импульсов, первый элемент И 7, четвертый 8, третий 9, второй 10 элементы И. Сущность изобретения состоит в том, что новая совокупность конструктивных признаков позволяет повысить оперативность контроля и экономичность устройства путем уменьшения времени для обнаружения тупика за счет распараллеливания процедуры поиска транзитивного замыкания распределенных ресурсов и уменьшения аппаратурных затрат за счет использования одного регистра для хранения исходной информации, формирования и фиксации выходной информации, а также за счет новой совокупности связей между выходами регистра и входами коммутаторов, которая позволяет уменьшить количество элементов И в коммутаторах. 4 ил., 1 табл.

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

Цель изобретения - повышение оперативности контроля,

На фиг. 1 представлена функциональная схема устройства для контроля распределения ресурсов; на фиг. 2 - фунющональная схема регистра; на фиг.З функциональная схема блока коммутато- ров; на фиг. 4 - пример графа связности распределенных ресурсов и соот

даетствующая ему матрица связностеи,

:

Устройство для контроля распределения ресурсов содержит (фиг.1) регистр 1, триггер-2 управления, триггер 3 режина, первьй 4.1-п-й 4.п блоки коммутаторов, генератор 5 импульсов, грзшпу 6 элементов И, первьш элемент И 7, четвертый 8, третий 9 и второй 10 элементы И, первуто группу

11прямых выходов регистра 1, группу

12инверсных выходов регистра 1, группы выходов 13.1-13,п блоков коммутаторов 4о 1-4.п, группу 14 информациюн- ных входов,вход 15 пуска, вторую груп пу 16 прямых выходов регистра 1,

Регистр 1 (фиг, 2) содержит первуто 17.1 -п-ю 17.П группы счетных триггеров.

Выходы 16.1Л. триггеров 17. id (i 1 ,n) образуют вторую грзт1пу 16 пря.мых выходов регистра 1. Выходы 11.ij триггеров 17.1, (1 1 ,п; j 1,ii; i 4 j)- образуют первую группу 11 прямых выходов регистра 1, а инверсные выходы 12.i.J триггеров 17.i.j (i 1,n; j 1,n) образуют группу 12 инверсных выходов регистра,

Разряды 13,1.1-13.п.п группы I- входов регистра 1 соединены с IK0

п

5

0

5

входами триггеров 17.1.1-17.п,п соответственно.

Соответствую1 1е разряды 14,1 (i 1,п; j 1 ,п; ) группы 14 единичных входов регистра 1 соединены с единичными входами соответству- кщих триггеров 17.

С1-ВХОД регистра 1 соединен с син- хровходами всех триггеров 17 регистра 1 , а вход установки в нуль - с входами установки в нуль всех триггеров .

Блок 4.1 коммутаторов .(фиг. 3) содержит п коммутаторов 18.1о1-18.1,п. Выходы 13.io1-13.i.n соответс твенно первого 18,1,1-п-го 18.1.п коммутаторов образуют группу 13.1 выходов коммутатора 4.1.

Каждью j-й разряд 11,i.j (j 1,n; i 7 j) группы информационнЬ1х входов коммутатора 4.1 соединен с первыми входами J-X элементов И каждого коммутатора 18,i.j,

Каждый К-й разряд 11.1.К (К 1,п; 1 1,п; К 7 1) грлгшы информационных входов кoм гyтaтopa 4.1 соединен с вторыми входами 1-го элемента И К-го коммутатора 1-го блока 4.1 коммутаторов.

Первый 12.1. 12.1.п разряды группы управляющих входов коммутатора 4.1 соединены с третьими вxoдa te всех элементов И соответственно первого. 18.1.1-п-го 18.1,п коммутаторов блока 4.1 коммутаторов.

Регистр 1 (фиг. 1) предназначен для приема информации о распределении ресурсов и для преобразования ее с целью выявления ресурсов, вовлеченньк в тупиковую ситуацию.

Триггер 2 управления предназначен для управления элементами И 8 и 9 во время работы-устройства.

Триггер 3 режима предназначен для управления генератором 5 импульсов.

Блоки 4.1 коммутаторов предназначены для формирования сигналов управления, которые, поступая на группу 1-входов регистра 1, изменяют его состояние в процессе обработки информации.

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

Элемент И 10 предназначен для формирования сигнала обнуления регистра 1 и установки в единицу триггера 3 режима, а также для блокирования выработки этого сигнала во время обработки информации устройством.

Элемент И 8 предназначен для формирования синхроимпульсов, подаваемых на С1-ВХОД регистра 1, во время об- работки информации устройством, и на прямой вход элемента И 7.

Элемент И 9 предназначен для формирования синхроимпульса, подаваемого на группу 6 элементов И для синхро низации, записи исходной информации в регистр 1, а также подаваемого на входы триггера 2 управления для перевода устройства в режим обработки информации. .

Элемент И 7 предназначен для формирования сигнала обнуления триггеров управления 2 и режима 3, т.е. для останова работы устройства.

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

В исходном состоянии триггеры 2 и 3 управления и режима находятся в кулевом состоянии.

По сигналу пуска, поступающему на вход 15 пуска устройства, открыва- ется элемент И 10, высоким потенциалом с его выхода производится обнуление регистра 1 и установка в единичное состояние триггера 3 режима. Низким потенциалом с его инверсного вы- хода элемент И 10 запирается, а высоким потенциалом с прямого выхода запускается генератор 5 импульсов. Импульсом с выхода генератора 5 импуль- ,hoB открьшается элемент И 9 и по пе- . реднему его фронту через группу 6 эле ,. ментов И происходит запись информации о связности распределенных ресзфсов в регистр 1 с группы 14 информацион

15П9а 8

0

5 0

0

5 0

5

ных входов устройства. По заднему фронту импульса триггер 2 управления устанавливается в единичное состояние, низким потенциалом с его и шерсного выхода запирается элемент И 9, а на первый вход элемента И 8 подается высокий потенциал.

В соответствии с графом связности распределенных ресурсов второй триггер 17.1.2 первой группы 17,1, третий триггер 17.2.3 второй группы 17.2, nepBbtfi триггер 17.3.1 третьей группы 17.3 и третий триггер 17.4.3 четвертой группы 17.4 триггеров регистра устанавливаются в единичное состояние. Остальные триггеры регистра 1 остаются в нулевом состоянии.

Высокие потенциалы с выходов

в третьем 4оЗ - второй 18.3.2, в четвертом 4.4 - первьй 18.4.1 и на соответствующих выходах 13.1,3, 13.2.1, 13.3с2 и 13о4.1 формируются высокие потенци алы, которые поступают на соответствующие 1-входы группы IK-BXO- дов регистра 1.

I.

По заднему фронту следуклцего тактового импульса, поступающему на CS-вход регистра 1 через открытый элемент И 8, триггеры 17.1.3, 17.2.1, 17.3.2 и 17.4.1 устанавливаются в единичное состояние. На выходах

Описанньй процесс иллюстрируется таблицей.

Пауза между тактовыми импульсами должна быть такой длительности, чтобы успевал пройти процесс изменения состояния регистра 1 и формирование сигналов на выходах коммутаторов 18.1.J.

В конце работы на выходах всех коммутаторов 18.i.j формируются низкие потенциалы, которые подаются на инверсные хрды элемента И 7 и по. о ерёййойу :та1 гтоврму гимпульсу на его febKOjite фс5рмир ется положит ел ьньй по- тешщал который поступает на входы установки в нузть триггеров 2 и 3 уп- равлейия и регкйма и обнуляет их. На этом работа устройства заканчивает- .- ; ;, ...;. -;, , . : У СвыХОйов: 16.1.1,; 16.2.2 и 16.3.3 регистра 1, соединенных с группой 16 выхрД153в Устройства, снимается информация о р есурса.х; вовлеченных в тупиковую ситуацию.

Если в процессе анализа на выхоах всех блоков А. 1-4.П коммутаторов будут сформированы низкие.потенциалы и устройство закончит свою работу, а ни один из триггеров 17.1.1 (i 1,ri) регистра 1 не будет в единичном состояний, то это свидетельствует об отсутствии тупика и распредеении ресурсов вычислительной системы. ..

Фор м у л а из обр е т е н и я

Устройство контроля распреде- 1ения peeypcdp, содержащее регистр, состоящий из счетных триггеров, триггер режима, с первого по п-й блоки

коммутаторов, где п - число типов ресурсов системы, группу элементов И, причем выходы элементов И группы соединены с группой асинхронных единичных входов регистра, группа информационных входов устройства соединена с первыми входами элементов И группы, первая группа прямых выходов ре- Q гистра соединена с группами информа- ционньк входов с первого по п-й блоков коммутаторов, отличающееся тем, что, с целью повышения оперативности контроля, устройство 5 содержит триггер управления, генератор импульсов и четыре элемента И, причем вторая группа прямых выходов регистра является группой выходов устройства, грзгппа инверсных выходов 0 регистра соединена с группами управ- ляклцих .входов с первогр по п-й блоков коммутаторов, группы выходов которых соединены с группой счетных входов регистра и инверсными входами первого 5 элемента И, вход пуска устройства соединен с первым входом второго элемента И, выход которого соединен с S-BXO- дом триггера режима и входом сброса регистра инверсный выход триггера 0 режима соединен с вторым входом второго элемента И, прямой .выход триггера режима соединен с входом пуска генератора импульсов, выход которого соединен с первыми входами третьего 5 и четвертого элементов И, вькод третьего элемента И соединен с синхронизируемым IK-ВХОДОМ триггера управления и с вторыми входами элементов И группы, инверсный и прямой выходы тригге- 0 ра зшравления соединены соответственно с вторыми входами третьего и четвертого элементов И, выход четвертого элемента И соединен с входом синхронизации регистра и прямым входом пер- 5 вого.Элемента И выход которого соединен с R-входами триггеров управления и режима.

О Г О 0

0о 1 о

1о о о, о о г О1