Устройство для моделирования сетевого графика Советский патент 1979 года по МПК G06F15/173 

(54) УСТРОЙСТВО для МОДЕЛИРОВАНИЯ СЕТЕВОГО ГРАФИКА

Изобретение относится к области вычислительной техники и может бить использовано для управления вычисли тельным процессом в многопроцессорных ЭВМ. Известно устройство для моделиро вания кратчайших путей в графах, со держащее блок автоматического форми рования топологии, блок управления, модели ветвей {. Для повышения на дежности и быстродействия устройства выход блока автоматического формирования топологии соединен с блоком управления. Предварительно в фор мирователи адресов заносятся длительности ветвей, а в счетчики - адреса узлов. Триггеры блокировки модеьпей и триггеры формирования топологии устангшливаются в единичное состояние, разрешая прохождение измерительных импульсов через разрешен ные модели работ и измерительное уст ройство. Однс1ко подсоединение блока автс 1атического формирования топологии к формирователю временных интервалов не позволяет автоматизировать процесс ввода данных в формирователи, счетчики, управляющие триггеры устройства. Наиболее близким техническим решением к данному изобретению является устройство для моделирования сетевого графика, содержащее блок управления, первьй выход которого соединен с первыми входами блока памяти индексов работ и блока памяти длительности работ, а вход блока управления подключен к первому выходу арифметического блока, первый вход которого подключен к выходу блока памяти длительности работ, а вторые вход и выход арифметического блока соединены соответственно с выходом и вторым входом блока памяти индексов работ, и регистр предшествующих работ, выход которого соединен со вторым входом блока памяти длительности работ и с третьим входом блока памяти индексов работ, четвертый вход которого подключен к выходу ре гистра последующих работ 2, Однако это устройство имеет низкое быстродействие. Значительное время ввода данных в устройство, обусловленное необходимостью перекоммутации связей на наборном поле, не позволяет применять подобные устройства в целях расчета сроков начала выполнения программ в многопроцессорных

ЭВМ, работающих в реальном масштабе времени.

Целью изобретения является повышение быстродействия устройства.

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

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

На фиг. 1 представлена структурная схема устройства для моделирования сетевого графика; на фиг. 2 структура графа на фиг. 3 - содержимое блоков памяти устройства; на фиг. 4 - временная диаграмма работы устройства.

Устройство содержит арифметический блок 1, блоки 2 и 3 памяти длительности работ и индексов работ, регистры 4 и 5 предшествующих и последующих работ, блоки б и 7 памяти непосредственно предшествуюгдах и непосредственно последующих работ и блок 8 управления.

Устройство работает следующим образом.

Функционирование начинается с того, что структура графа (см.фиг. 2) заносится в блоки 7,6, 2, например операционной системой ЭВМ на основе анализа вхЬдного потока заданий. В i-ю ячейку блока 7 заносятся номера работ, непосредственно последующих i-й работе, и их количество (см. фиг. 3,а). В i-ю ячейку блока 6 заносятся номера, непосредственно предшествуюцд х работ i-й работе, и их количество (см. фиг. 3,6) . Длительности работ заносятся в блок 2 (см. фиг. 3,в) . Блок 3 очищается, в него заносится код единицы во все разрядах.

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

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

регистр 4 содерх имое очередных ячеек. В блоке 1 происходит анализ принятых кодов, и, если они равны нулю, происходит запись в блок 3 индексов нулей по адресам, выдаваемым из блока 6. В блоке 7 работы, индекс которой определен, помечаются кодом номера этапа работы устройства.

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

Коды, считанные из блока 6, принимаются на регистр 4. По сигналам, вырабатываемым на третьем выходе блока управления 8, происходит обращение в блоки 2 и 3 по адресшч, принятнм на регистр 4. Управление последовательной выдачей адресов из регистра 4 в блоки 2 и 3 организовано с помощью счетчика и дешифратора (на чертеже не показаны),

Формирование индекса очередной, работы происходит следующим образом. Коды длительности и индексов работ, считанныеиз блоков 2 и 3, поступают в блок 1, который проверяет, отличен ли код, считанный из блока 3, от кода, равного единицам во всех разрядах (известен ли индекс непосредственно предшествующей работы). Если код равен единицам, блок 1 выдает сигнал на первый вход блока управления 8. По этому сигналу в счетчик (на чертеже не показан), управляющий выдачей кодов из регистра 5, добавляется единица, разрешая выдачу в блок б номера работы, индекс которой необходимо определить.

Если индекс очередной непосредственно предшествующей работы определен, блок 1 складывает его с кодом длительности работ. Если очередное значение суммы больше предыдущей суммы, блок 1 запоминает его. После просмотра всех работ, непосредственно предшествующих рассматриваемой, в блоке 1 сохраняется код, равный индексу данной работы. В счетчике (на чертеже не показан), управляющем выдачей из регистра 4, вырабатывается сигнал переполнения, по которому происходит запись содержимого блока 1 в блок 3, по адресу, выдаваемому из регистра 5. В блоке 7 делается пометка кодом номера этапа работы устройства в ячейке работы, индекс которой определен.

После просмотра в блоке 7 всех отмеченньк на предыдущем этапе работ устройство определяет индексы ближайшим последующим работам, добавляя единицу в счетчик этапов работы (на чертеже не показан) блока управления 8.

После определения индексов выходных работ графа при считывании из блока 7 в регистр 5 будут приняты нули (см, фиг. 3,а). Таким образом, окончание считывания из блока 7 всех ячеек, помеченных на предыдущем этапе, и нулевое содержимое регистра 5 являются условиями окончания работы устройства.

изобретения

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

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

0 непосредственно предшествующих работ и непосредственно последующих работ, выход первого из которых соединен со входом регистра предшествующих работ, а его входь подключены к вы5ходу регистра последующих работ и второму выходу блок,а управления, третий выход которого соединен с первым входом-блока памяти непосредственно последующих работ, второй

0 вход которого подключен к выходу регистра предшествующих рвбот, а его выход соединен со входом регистра последующих работ.

5

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

0 279173, кл. G 06 F 15/20, 1969.

fua.Z

ВПб

6П7

5ПЗ

бпг