Устройство для определения критического пути Советский патент 1978 года по МПК G06G7/48 

1

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

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

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

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

Кроме ТОГО;, модель ветви содержит управляемый ключ, регулируемый источник напряжения, развязывающий диод, формирователь импульсов и запоминающий триггер. Вход триггера через формирователь импульсов подключен к выходу регулируемого источника напряжения, который через развязывающий диод соединен с информационным выходом модели ветви. Информационный и управляющий входы МОДСЛ1И ветви соединены ссоогветствующими входами управляемого ключа, выход которого соединен со входом регулируемого источника напряжения. На фиг. 1 приведена блок-схема предлагаемого устройства; на фнг. 2 - функциональная схема модели ветви.

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

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

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

Сигнал с генератора 2 поступает на распределитель 4, с выходов которого на управляющие входы ключей 8 одновременно поступают сигналы а, Ь, с, d, е и f. .Нуть тока в модели 1 графа от источника 6 соответствует критическому пути в графе. При снятии сигналов а, Ь, с. d, е н f модели 7 ветвей, не принадлежащие к критическому пути, оказываются отключенными, так как в их управляемых ключах 8 отсутствует ток. С задержкой

т сигнал с генератора 2 через элемент задержки 3 поступает к начальной точке модели 1. При этом необходимо выполнение условия , где Т - длительность сигналов а, Ь, с, d, е и f. В этом случае к момеиту поступления сигнала к начальной точке модели 1 модели 7 ветвей, не принадлежащие к критическому пути, оказываются отключенными и сигнал проходит только через модели 7 критического пути. Сигналы а , Ь, с , d, е и / служат для индикации критичности моделей 7 и через формирователи импульсов 11 поступают для фиксации на запоминающие триггеры 12. Диоды 10 отражают факт направленности ветвей, а служат для развязки цепей прохождения еигналов а , Ь, с , d, е , f. Коммутирующий диод 5 служит для защиты схемы от перенапряжения при закрытых управляемых ключах 8. Величина критического пути может быть измереиа в виде напряжения между начальной и конечной точками модели 1 графа.

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

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

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

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

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

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

Источники информации,

принятые во внимание ири экспертизе

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

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