Устройство для моделирования сетевого графика

 

ОПИСЛНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к ает. сеид-еу— (22) ЗайеЛеио 100577 (21) 2483177/18-24 с присоединением эаеаки М— (23) Приоритет—

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

СССР по делам изобретений и открытий

Опубликовано 1 5. 09.. 79. .Бюллетень Ио 34

Дата опубликоеанил описания 1809.79 (72) Авторы

H 3Q6p &79HR $I

А.И. Иутилов и Г.A. Поляков (71) Заявитель (5 4 ) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВОГО ГРАФИКА

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

Известно устройство для моделирования кратчайших. путей в графах, содержащее блок автоматического формирования топологии, блок управления, модели ветвей (1) . Для повышения надежности и быстродействия устройства выход блока автоматического формирования топологии соединен с блоком управления. Предв арительно в фор-15 мирователи адресов заносятся длительности ветвей, а в счетчики. — адреса узлов. Триггеры блокировки моделей и триггеры формирования топологии устанавливаются в единичное 20 состояние, разрешая прохождение измерительных импульсов через разрешенные модели работ и измерительное устройство. однако подсоединение блока автоматического формирования топологии к формирователю временных интервалов не позволяет автоматизировать процесс ввода данных в формирователи, счетчики, управляющие триггеры устройства.

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

686033

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

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

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

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

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

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

Функционирование начинается с того что структура графа (см.фиг.. 2) заносится в блоки 7, 6, 2, например, операционной системой ЭВМ на основе анализа входного потока заданий. В

i-ю ячейку блока 7 заносятся номера работ, непосредственно последующих

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

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

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

2О

ЗО

5О

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

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

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

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

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

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

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

686033

Фиг. 2

Б/75

БПБ

ББ2

БП7

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

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

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

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

1. Авторское авидетельство СССР

Р 485451, кл . G 06 F 15/20, 1971.

2. Авторское свидетельство СССР

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

686033

Тираж 780 Подписное

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

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

Закав 5461/48

Филиал ППП Патент, r ужгород ул. Проектная, 4

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

Редактор Н. Каменская Техред Н.Бабурка Корректор В. Бутяга