Устройство для контроля распределения ресурсов

 

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

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

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

РЕСПУБЛИК (5g 4 С 06 F 11/00

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

H А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4328359/24-24 (22) 08. 10.87 (46) 23. 09.89. Бюл. № 35 (72) С. Н. Ткаченка, В, B. Герасименко, Г.Н. Тимонькин, В.С. Харченко, С.В. Хотименко и В.Г. Борисов (53) 681.3(088 ° 8) (56) Авторское свидетельство СССР

¹ 1015385, кл, С 06 F 11/00, G 06 F g!0(), 1983.

Tnternational Journal of Systems

Science, 1979, v. 10, № 5, р. 477483, fig.3.

„„Я0„„150989 А1

2 (54) УСТРОЙСТВО ДПЯ КОНТРОЛЯ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ (57) Изобретение относится к вычислительной технике и может найти применение в современных высокопроизводительных системах для контроля корректности распределения ресурсов.

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

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

Цель Йзобретения — повышение оперативности контроля.

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

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

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

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

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

Выходы 16 ° ij триггеров 17.Ы (i =

1,п) образуют вторую группу 16 прямых выходов регистра 1. Выходы 11.Ц триггеров 17.ij (i = 1,n j = 1,п;

4 j) образуют первую группу 11 прямых выходов регистра 1 а инверсные выходы 12. i ° j триггеров 17. i. j (i

1,п; j = 1,п) образуют группу 12 инверсных выходов регистра.

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

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

CI-вход регистра 1 соединен с синхровходами всех триггеров 17 регистра 1, а вход установки в нуль — с входами установки в нуль всех триггеров.

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

Каждый j-и разряд 11.i j (j = 1,п, 4 j) группы информационных входов коммутатора 4 ° i соединен с первьщи входами j-x элементов И каждого коммутатора 18.i ° j.

Каждый К вЂ” и разряд 11.1.К (К = 1,n;

1 = 1,п; К 1) группы информационных входов коммутатора 4.i соединен с вторыми входами 1-ro элемента И К-го коммутатора 1-го блока 4.х коммутаторов.

Первый 12.i.1-п-й I2,i.п разряды группы управляющих входов коммутатора 4.i соединены с третьими входайи всех элементов И соответственно первого 18.i.1-п-го 18.i.n коммутаторов блока 4.х коммутаторов.

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

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

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

По заднему фронту следующего тактового импульса, поступающему на

CS-вход регистра 1 через открытый элемент И 8, триггеры 17.1.3, 17.2 ° 1, 17.3,2 и 17.4.1 устанавливаются в единичное состояние. На выходах

11. 1.3, 11.2.1, 11. 3 ° 2 и 11.4. 1 регистра 1 формируются положительные потенциалы, которые поступают на соответствующие входы первой группы входов блоков коммутаторов. На вторые группы входов всех коммутаторов по-прежнему подаются высокие разрешающие потенциалы с группы 12 инверсных выходов регистра 1. В данном такте работы устройства отрабатывают коммутаторы 18.1.1, 18.2 ° 2, 18.3 3 и 18.4.2 соответственно блоков коммутаторов

4.1-4.4 и на соответствующих выходах

13,1.1, 13.2.2, 13.3.3 и 13.4.2 формируются высокие потенциалы, поступающие на соответствующие входы груп5 150989

Блоки 4.i коммутаторов предназначены дпя формирования сигналов управления, которые, поступая на группу

I-входов регистра 1 изменяют его

5 состояние в процессе обработки информации.

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

Элемент И 10 предназначен для hopмирования сигнала обнуления регистра 1 и установки в единицу триггера

3 режима, а также для блокирования !5 выработки этого сигнала во время обработки информации устройством.

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

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

Элемент И 7 предназначен для формирования сигнала обнуления триггеров управления 2 и режима 3, т.е. для останова работы устройства, РВссМоТрНМ функционирование устройства на примере анализа распределения ресурсов вычислительной системы, граф связности которых и соответствующее ему матричное представление изображены на фиг. 4. 40

В исходном состоянии триггеры 2 и

3 управления и режима находятся в нулевом состоянии.

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

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

В соответствии с графом связности распределенных ресурсов второй триггер 17 ° 1.2 первой группы 17. 1, третий триггер 17.2.3 второй группы 17.2, первый триггер 17.3.1 третьей группы

17.3 и третий триггер 17.4.3 четвертой группы 17.4 триггеров регистра устанавливаются в единичное состояние.

Остальные триггеры регистра 1 остаются в нулевом состоянии.

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

11.1.2, 11,2.3, 11.3. 1 и 11.4.3 поступают на соответствующие входы группы информационных входов блоков коммутаторов. На группы управляющих входов всех блоков коммутаторов подаются высокие потенциалы с группы 12 инверсных выходов регистра 1. В первом блоке 4. 1 коммутаторов срабатывает третий коммутатор 18.1.3, во втором 4.2 — первый коммутатор 18,2.1, в третьем 4.3 — второй 18.3.2, в четвертом 4.4 — первый 18,4. 1 и на соответствующих выходах 13 ° 1.3, 13.2. 1, 13.3.2 и 13.4.1 формируются высокие потенциалы, которые поступают на соответствующие I-входы группы IK-входов регистра 1.

1509898 пы Х-входов регистра 1. По заднему фронту очередного тактового импульса триггеры 17. 1, 1, 17.2.2, 17.3 . 3, 17.4.2 устанавливаются в едииничное состояние.

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

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

18.i-j.

В конце работы на выходах всех 15 коммутаторов 18. i. j формируются низкие потенциалы, которые подаются на инверсные входы элемента И 7 и по очередному :тактовому -импульсу íà его выходе:,формируется положительный по- 20 тенциал,--который поступает на входы установки в .нуль триггеров 2 и 3 управления и режима и обнуляет их. На этом работа устройства заканчивается.

С выходов 16. 1. 1, 16 ° 2. 2 и 16.3. 3 регистра .1, соединенных с группой 16 выходов устройства, снимается информация .о ресурсах, вовлеченных в тупиковую ситуацию. 30 . Если в процессе анализа на выходах всех блоков 4.1-4.п коммутаторов будут сформированы низкие потенциалы и устройство закончит свою работу, а ни одйи из триггеров 17.i-i (i

= 1,п) регистра 1 не будет в единичном состоянии, то это свидетельствует об отсутствии тупика и распределении ресурсов вычислительной систеMbl ° 40

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

УСтройство ддя контроля распредеЛения рееурсоВ, содержащее регистр, - 45 состоящий из счетных триггеров, триггер режима, с первого по и-й блоки коммутаторов, где и — число типов ресурсов системы, группу элементов

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

После сигСостояние

После 1-го После 2-го После 3-ro импульса импульса импульса нана пуска

1234

1234

12341234

Р входа в группе

1234 I 234 1234

234

1Х1 00 Iвко-001 0 1000

2 0 Х 1 0 ды ре 1 0 0 0 0 1 0 0

3 1 0ХА гист-:0 1 0 00 1 0

4 0 0 1 Х ра 1 1 0 0 0 0 1 0 0

0000

$-входы регистра 1

Примечание. Х вЂ” вход отсутствует. ф групп триггеров

1Ф группы входов

У триггеров в группе

40000

001 0

001 0

1010 (1110

110

1509898

Фиг.З ага

0 0.1

7 О О

0 О 1

Составитель Д. Ванюхин

Редактор О. Головач Техред N.Äèäûê Корректор М, Васильева

Заказ 5814/47 Тираж 668 Подпис ное

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 10!