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

О л и c A-3Ф"и" Й

ИЗОБРЕТЕНИЯ

590768

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕПЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 16.10.75 (21) 2182873/18-24

М. Кл. G 06G 7/48 с присоединением заявки ¹

Совета Министров СССР по делам изобретений ч открытий (43) Опубликовано 30.01.78. Бюллетень № 4 (45) Дата опубликования описания 14.02.78

УДК 681.335(088.8) (72) Авторы изобретения (71) Заявитель

Д. А. Мельников, Г. Д. Тавужнянский и В. П. 1Иилов

Одесский ордена Трудового Красного Знамени политехнический институт (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРИТИЧЕСКОГО

ПУТИ

Государственный комитет (23) Приоритет

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

Известно устройство для исследования графов, содержащее решающие усилители и логические элементы (1). Это устройство требует большого количества оборудования.

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

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

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

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

Устройство содер>кит модель 1 графа, генератор 2 импульсов, элемент задержки 3, распределитель 4 импульсов, коммутирующий

15 диод 5 и источник тока 6. Модель графа 1 состоит из моделей 7 ветвей. Каждая модель

7 содержит управляемый ключ 8, регулируемый источник напряжения 9, развязывающий диод 10, формирователь импульсов 11 и

20 запоминающий триггер 12.

Сигнал с генератора 2 поступает на распределитель 4, с выходов которого на управляющие входы ключей 8 одновременно поступают сигналы а, 1>, с, d, е и t, 11уть тока в мо25 дели 1 графа от источника б соответствует критическому пути в графе. При снятии сигналов а, К с. d, е и f модели 7 ветвей, не принадлежащие к критическому пути, оказываются отключенными, так как в их управлязо емых ключах 8 отсутствует ток. С задержкой 590768 т сигнал с генератора 2 через элемент задержки 3 поступает к начальной точке модели 1. При этом необходимо выполнение условия т) Т, где Т вЂ” длительность сигналов а, b, с, d е и f. В этом случае к моменту поступ- 5 ления сигнала к начальной точке модели 1 модели 7 ветвей, не принадлежащие к критическому пути, оказываются отключенными и сигнал проходит только через модели 7 критического пути. Сигналы а, b, с, d, е и 10 служат для индикации критичности моделей 7 и через формирователи импульсов 11 поступают для фиксации на запоминающие триггеры

12. Диоды 10 отражают факт направленности ветвей, а также служат для развязки цепей 15 прохождения сигналов а, b; с, d, е, f . Коммутирующий диод 5 служит для защиты схемы от перенапряжения при закрытых управляемых ключах 8. Величина критического пути может быть измерена в виде напряжения 20 между начальной и конечной точками модели

1 графа.

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

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

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

Источники информации, принятые во внимание при экспертизе

1. Васильев В. В., Клепикова А. Н. и Тимошенко А. Г, Решение задач оптимального планирования на электронных моделях. «Наукова думка», Киев, 1966.

2. Авторское свидетельство СССР №275540, кл. G 06G 7/48, 1969.

590768

Составитель Г. Сорокин

Тсхрсд А. Камышннкова

Редактор Н. Громов

Коррсктор 3. Тарасова

Подписное

Типография, пр. Сапунова, 2

Заказ 3331/1 Изд. № 175 Тира к 818

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

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