Устройство для расчета больших сетей

 

В. В. Васильев, А. Г. Додонов и А. И. Левина (72) Авторы изобретения

Институт электродинамики АН Украинской ССР

1.(73) Заявитель (54) УСТРОЙСТВО ДЛЯ РАСЧЕТА БОЛЬШИХ .

СЕТЕЙ

:.1

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

Известно устройство для определения оптимального пути в непрерывной неоднородной среде как кратчайшего, определенного на графе- решетке произволь» ной конфигурации с информацией(в узлах, !

О покрывающего данную среду $1).

Наиболее близким по технической сущности к предлагаемому является уст- ройство для расчета больших сетей, со- держащее блок моделирования ветвей,: первый BbIxoll которого соединен со вхо- дом, а.первый вход - с выходом блока управления, первый вход которого связан с первым выходом внешнего запоминаю-, щего блока, вход и второй выход которого соедйнены соответственно со вторым выходом и вторым входом блока моделирования ветвей, и блок элементов памяти (Ц. 2

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

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

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

7177 вход подключен к выходу блока поиска фрагментов среды. Блок поиска фрагментов среды содержит матрицу запоминания направлений, узел йередачи направлений, счетчик количества сдвигов и реверсивный .5 регистр сдвига, причем первая группа входов матрицы запоминания направлений яв. ляется груйпой входов блока, вторая груп. па входов матрицы запоминания направ- лений соответственно соединена с выхо» !О дами реверсивного регистра сдвига, выходы матрицы запомйнания направлений соединены соответственно с группой вхо" дов узла передачи направленйй, первый выход которого соединен со входом ре- 15 версивнюго регистра сдвига, второй вы ход связан со входом счетчика количества сдвигов, а третий выход является вьгходом блока, выход счетчика количест-. ва сдвигов соединен со входом узла пере- 20 дачи направлений-.

На фиг. 1 представлена блок-схема уст ройства, на фиг. 2 показан блок поиска фрагментов среды, на фиг. 3 приведен прймер, иллюстрирующий работу устройства.

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

Блок поиска фрагментов срецы 7 (см. фиг. 2) состоит из матрицы запоминания направлений пути 9, реверсивного регист- о ра сдвига 10, счетчика количества сдвигов 1 1 и узла передачи направлений 12.

С целью иллюстрации работы устройства рассмотрим пример (см. фиг. 3), где в непрерывной неоднородной среде необ- 4 — ходима определить оптимальный путь, например, между двумя точками 1 и 11.

Исследуемая среда покрывается графомрешеткой, например, прямоугольной конфигурации с узлами 1-25 (связи между узлами граф-решетки на фиг. 3 опущены) .

Принцин работы устройства следующий.

Блок управления 4 (см. фиг. 1) обеспе- чивает работу устройства в два этапа.

На первом этапе из внешнего запоминающего блока 2 в блок моделирования ветвей 1 заносятся веса, представляющие

4 собой интегральные характеристики, определенные по соответствующей прямоу гольной площадке, и определяется кратчайший путь из узла 1 в узел 11 (см. фиг. 3). Выделенный кратчайший путь свидетельствует о том, что из исследуемой непрерывной неоднородной среды выделена зона, интегральные характеристики которой минимальны, поэтому предполагается наличие в ней искомого апти» мального пути. Информация о выделенном кратчайшем пути, а именно номера узлов, через которые проходит этот путь, в данном случае 1,8, 12, 16, 17, 14, 11, и направления выхода пути с каждого узла (для прямоугольной решетки с диагоналями это количество равно восьми), заносится в блок поиска фрагментов среды 7. Они используются на втором эта- пе решения задачи: номера узлов - для задания номеров фрагментов, а направления - для задания граничных узлов.

В блоке поиска фрагментов среды 7 (см. фиг. 2) информация запоминается в матрице запоминания направлений 9, которая представляет собой триггерную матрицу с логическим управлением. Количество строк матрицы 9 равна количеству элементов узлов в графе, а количество столбцов равно количеству направлений пути из узла. Запись информации в матрицу 9 производится параллельно при выделении кратчайшего пути из полученного дерева, т. е. при передаче сигнала логического нуля из конечного узла в начальный. При этом в строку, соответствующую номеру узла, записывается информация о направлении пути из него.

Количество узлов, лежащих на критическом пути определяет количество фрагментов, которые необходймо рассмотреть для отыскания искомого решения,.в дан-, ном примере - семь фрагментов (узлы 1, 8, 12, 16, 17, 14, 11).

На втором этапе блок управления 4 обеспечивает последовательно в заданном. порядке, т. е. в" порядке прохождения кратчайшего пути из начального узла в конечный, выбор фрагментов с помощью блока поиска фрагментов среды 7: и определение на каждом фрагменте дерева кратчайших путей из начальных граничных узлов, задаваемых направлением выхода кратчайшего пути из предыдущего узла, в конечные граничные узлы, определяемые направлением выхода кратчайшего пути из рассматриваемого узла с помощью блока сопряжения фрагментов

717790 последовательно на каждом фрагменте, запоминаются во внешнем запоминающем блоке 2, а затем выделяется кратчайший путь из начального узла 1 в конечный, узел 11. Если полученный путь удовлет- 5 воряет условиям задачи, то работа уст» ройства прекращается, если нет, То вто рой этап повторяется для новой въщеленной зоны, определяемой полученным кратчайшим путем.

Рассмотрим отдельно оба режима ра-. боты устройства. Выбор фрагмента про-изводится с помощью блока поиска фрагментов 7 (см. фиг. 2). Первый фрагмент задается начальным узлом, из которого ":" исходит кратчайший путь. Последующие фрагменты определяются с помощью реверсивного регистра сдвига 10. При этом из матрицы 9 выбирается информа- ция о направлении выхода пути из начйтьного узла и переписывается в узел передачи направлений 12. На основании этой

-:-информации при соответствующей нумерации узлов модели сети узлом передачи направлений 12 определяется номер по-.

25 следующего узла, т. е. формируется число сдвигов и направление сдвига ревер- сивного сдвига 10. Количество сдвигов регистра 10 контролируется счетчиком

11.

Для того чтобы перейти, например, от первого фрагмента, задаваемого начальным узлом 1 (см. фиг. 3), ко второму фрагменту, определенному направлением выхода кратчайшего пути из этого узла, . т. е. к фрагменту, определяемому узлом

8, необходимо регистр сдвига 10 сдвинуть вправо на 7 разрядов. Этот сдвиг производится следующим образом. Из мат40 рицы 9 (см. фиг. 2) направление выхода пути из узла 1 передается в узел передачи направления 12. В нем производится анализ, на основе которого в счетчике 1 1 в обратном коде устанавливается

45 число сдвигов и затем производится с сдвиг регистра 10. Импульс переполнения со счетчика 11 прекращает сдвиг -регистра сдвига 10. Если номер последующего узла имеет меньшую нумерацию, как это происходит, например, при перЕ= ходе от фрагмента, определяемого узлом

17 к фрагменту, определяемому узлом

14, регистр сдвига 10 сдвигается вле« во на три разряда. Сопряжение результатов, полученных при последовательноМ исследовании фрагментов, производится с помощью блока сопряжения фрагментов

8 (см. фиг. 1). Блок элементов памя-.

6 ти 3, входящий в состав блока сопряжения фрагментов 8, состоит из двух групп с четчиков 1 — К, 1, -, котои рые поочередно подключаются к начальным и граничным узлам блока 1 моделирования ветвей на данном фрагменте.

При анализе первого фрагмента любая из групп счетчиков блока элементов . памяти 3, подключается к конечным

E граничным узлам этого фрагмента. ПрИ анализе второго фрагмента та группа, которая была подклкнена к конечным граничным узлам первого фрагмента, подключается к начальным, а другая — . к конечным граничным узлам последующего фрагмента. В группу счетчиков, подключаемых к конечным" гранйчным узлам первого фрагмента, заносится число импульсов, - характеризующее временной сдвиг между путями, ведущими в конечные pf32fHR bf& "узйы. Эта информа« ция определяет начальные условия для начальных граничнйх узлов второго фрагмента. Во второй группе счетчиков, подключенных к конечным граничным узлам второго фрагмента, полученная информация определяет временной сдвиг между путями, ведущими из начального узла первого фрагмента в конечные узлы второго фрагмента и т. д,, Длина кпатчайше -. го пути в граничные углы второго фрагмента будет фиксироваться в счетчике измерения, находящемся в блоке управления. Аналогично производится расчет путей на пос ледующих фрагментах. коммутация конечных и начальных граничных узлов с соответствующей группой счетчиков блока элементов памяти выполняется соответственно с помофью выходйого 5 и входного 6 логических. коммутаторов.

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

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

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

--1 ход которого соединены "соответствейно со вторым выходом и вторым входом бло ка моделирования ветвей, и блок элементов памяти, о т л и ч а ю rrr e е с я тем, что, с целью повышения быстродей ствия, в него дополнительно введены в

" входной н" выходной логические коммутаторы и блок поиска фрагментов среды, прячем выходй блока цементов памятн соединены соответственно со входамн входного логического коммутато, выходы которого подключейй соотвйтствей=но к группе входов бщж@ моделирования ветвей, первая групйа выходЖ котОрЬ= го соединена;соответственно со входаМи 15 блока поиска фрагментов среды, а "вт -" рая группа выходов подключена соответ- ственно к группе входоъ выходного"логи--" ческого коммутатора,.вихрь которого соединены соответственно со входамй ...- 2 блока элемейтов памяти "а вход пофйй - чен к выходу блока:поиска фраi ìåíòîâ среды.

2. Устройство по п. 1, о т л и ч а ю rri е е с я тем, что блок поиска фраг.- "ментов "среды содержит матрицу запоми- нання"направлений, узел передачи направлейяй, счетчйк количества сдвигов и рекР : версивный регистр сдвига, причем первая группа входов матрицы запоминания направлений является группой входов блока, вторая группа входов матрицы запоминания направлений соответственно соединена с выходами реверсивного регистра сдвига, выходы матрицы запоминания направлений соединены соответственно с груййой входов узла передачи направлений, первый выход которого соединен со входом реверсивного регистра сдвйга, второй выход связан со входом

"счетчнка"количества сдвигов, а. третий

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

Источники информации, принятые во щщмание при экспертизе .1,: Васипьев B. В. Приближенный ме- тод решения некоторых вариационных .за дач с локальнымн функционаламн. Ве рт ник AH УССР, 1974, М 11.

2. додонов А. Г., Хаажинов В, В.

Об одном методе решения: больших сетей на цифровых аналогал". Сб.

Гибрйдные вычислительные машины и комплексы, .Киев, Наукова думка, 1975 (р ип).

717790

Составитель И. Лебедев

Редактор Н. Веселкина Техред Э. мужик Корректор Г. Назарова

Заказ 9850/68 Тираж 751 Подписное

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

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

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