Устройство для расчета больших сетей Советский патент 1980 года по МПК G06G7/48 

- -; / . . .:

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

непрерывных средах.

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

Наиболее, близким по технической сущности к предлагаемому является устройство для расчета больших сетей, содержащее блок моделирования ветвей, первый выход которого соединен do вхо дом, а. первый вход - с выходом блока управления, первый вход которого свя:заа с первым выходом внешнего запомина1о- v шего блока, вход и второй выход которого соединены соответственно со втодым.

выходом и вторым входом блока моделирования ветвей, и блок элементов памяти f 23.

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

Целыб настЬяще.го изобретения является повьпиение быстройёйствня. .

У казанная цель достигается тем, что в устройство дополнительно введены входной и выходной логические. коммутаторы и блок поиска фрагментов среды, причем выходы блока элементов памяти соединены соответственно со вход1ами входного логического коммутатора, выходы которого подключ.ены соответственно к группе входов блрК|Э моделирования ветвей, первая группа выходов которого соединена соответственно со. входами йка поиска фрагментов I среды, а вторая группа выходов подключена соответственно к группе входов выходногб логического коммутатора, выходы которого .соединены соответственно со входами блока элементов памяти, а вход подклйчён к pbixeay поиска . фрагментов среды. Блок поиска фрагментов среды содерясит матрицу запоминания направлений, узел передачи направлений, счетчик/К(Эй йчёствасдвигов и реверсивны регистр сдвига, причем первая группа вхо дов матрицы запоминания направлений яв- . ляется г|эуппой входов блока, вторая груп па входов матрицы запоминания неправлений соответственно соединена с вьгходами реверсивного регистра сдвига, выходы матрицы запоминания направлений Соединены соответственно с группой уйла передачи направленйС пёрвйй выход которого соединен со входом реверсивнюго регистра сДбйга, второй вь1ход связан со входом счетчика количества сдвигов, а третий вьгхой является в ыходом блока, выход счетчика кбличестВй сдвигов соединен со входом узла пере ЙачИHanjpiaBrieHHjiii. На фиг. 1 представлена бпок-Ьхема ус ройства, на фиг. 2 пбказан блок поиска фрагментов среды, на фиг. 3 приведен пример, иллюстрирующий работу устройст- ;ва.;--.; .;;.. -;-/v - --; Блок-схема устройства (см. фиг. 1) содержит блок моделирования ветвей 1, у внешний .запоминающий блок 2, блок, эле. . памяти 3, блок уп|равлёния 4, выходной логический коммутатор 5, входной логический коммутатор 6и блок поиска фрйГШнтов среды 7. Блок элементов памяти 3 в сочетании с выходным 5 и вход ньлм 6 коммутаторами представляет собой блок а:в 6матичёс:кого сбпряженИя фрагментов 8, .,.,..-,; . . Блок поиска фрагментов среды 7 (см. фиг. 2) состоитИз матрйць запоминания направлений пути 9, реверсивного регист ра сдвига 10, счетчика коли 1еСтва сдвигов 11 и узла передачи направлений 12. С целью иллюстрации работы устройст ва рассмотрим пример (см. фиг. 3), где в непрерывной неоднородной среде необ хОдимЬ Ьп{эеделить оптимальный пут например; между двумя точками 1 и 11. ; Исследуемая Среда Покрывается графомрешеткой, например, прямоугольной конфигурации с узлами 1-25 (связи между узлами граф-решетки на фиг. 3 опуще „1.т -. . -3 --.--... /.. .:,-.,-,.,.-i,-;:.,-. НЫ/ . - .... -л.Принцин работы устройства следующий Блок управления 4 (см. фиг. 1) обеспечивает работу устройства в два этапа. На первом этапе из внешнего Запоминающего блока 2 в блок моделирования ветвей 1 31аносятся веса, представляющие собой интегральные характеристики, определенные по соответствующей прямоугольной площадке, и определяется кратчайший путь из узла 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.- и определение на каждом фрагменте дерева кратчайших путей из начальных граничных узлов, задаваемых направлением выхода кратчайшего пути из предыдущего узла, в конечные граничные узлы, определяемые направлением выхода кратчайшего пути из рассматриваемого узла с помощью блока сопряжения фрагментов последовательно на каждом фрагменте, запоминаются во внешнем запомнййЙэщШ блоке 2, а затем выделяется кратчайиий путь из начального узла 1 в конечный , узел 11. Если полученный путь удовлётворяет условиям задачи, то работа устройства прекращается, если нет, то вто рой этап повторяется для новой въщеленной зоны, определяемой полученным крат чайшим путем. Рассмотрим отдельно оба режима работы устройства. Выбор фрагмента производится с помощью .блока поиска фрагментов 7 (см. фиг. 2). Первый фрагмент задается начальным узлом, из йотOpbFd исходит кратчайший путь. Последующие фрагменты определяются с помощью ре- версивного регистра сдвига 10. При этом из матрицы 9 выбирается информация о направлении выхода иутп «зШЧШь ного узла и переписьюается в уэёл передачи направлений 12. На основании этой «.информации при соответствующей нумерации узлов модели сети узлом передали направлений 12 определяется номерпо-г следующего узла, т. е. формируется число сдвигов и направление сдвига реверсивного сдвига 10, Количество сдвигов регистра 10 контролируе тся счетчйКОКг 11. - .. / -.;-. Для того чтобы перейти, например, от первого фрагмента, задаваемого нач альным узлом 1 (см. фиг. 3), ко второму фрагменту, определенному направлёййё1й выхода кратчайшего пути из этого узда, т. е. к фрагменту, определяемому узлом 8, необходимо регистр сдвига 10 сдви,нуть вправо на 7 разрядов. Этот сдвиг производится следующим образом. Из мат рицы 9 (см. фиг. 2) направление выхода пути из узла 1 передается в узел передачи направления 12. В нем производится анализ, на основе которого в счётчике 11 в обратном коде устанавливается число сдвигов и затем производитсяс сдвиг регистра 10. Импульс переполнения со счетчика 11 превращает сдвиг регистра сдвига 10. Если номер последующего узла имеет меньшую нумёрйцйй, как это происходит, например. При п0рёходе от фрагмента, определяемого уапом 17 к фрагменту, определяемому узлом 14, регистр сдвига 10 сдвигаешься влево на три разряда. Сопряжение результа- тов, полученных при последовательном исследовании фрагментов,производитс;яjc пОмошью блока сопряжения фрагментов 8 (см. фиг. 1). Блок элементов памд-; ти 3, ВХОДЯЩИЙ в состав блока сопряжения фрагментов 8, состоит из двух групп счетчиков l - KI l , -К , которые поочередно подключаются к начальным и граничнык узлам блока 1 моделирования ветвей на данном фрагменте. При анализе первого фрагмента любая из групп счетчиков блока элементов памяти 3, подключается к конечным граничным узлам этого фрагмента. П.р|1 анализе второго/фрагмента та группа, которая была подключена к конечным граничным узлам первого фрагмента, подключается к начальным, а другая к конечным граничным узлам, последующего фрагмента. В группу счетчиков, поаключаемь1х Кконечных гранйчйыУ узлам первого фрагмента, заносится число импульсов, характёрйзующёевременной сдвиг между путями, ведущими в крнечйьЖ ТрШГ« Ш§УШЙг: Эта информация определяет начальные условия для начальных граничнЬпс узлов второго фрагмента. Во второй группе счетчиков, подключенных к конечным граничным узлам второго фрагмента, полученная информация определяет временной сдвиг между путями, ведущими из начального узла первого фрагмента в конечные узлы второго фрагмента ИТ, д,. Длина коатчайше-. го пути в граничные углы второго фрагмента будет фиксироваться в счетчике измерения, находящемся в блоке управления. Аналбгитао производится расчет путей на последующих фрагментах, коммутация конечных и начальных граничных узлов с соответствующей группой счетчиков блока .элементов памяти выполняется соотвётственно с помо1 1ью выходного 5 и входного 6 логических .коммутаторов. Таким образом выполнение устройства в. соответствии с изобретением позволяет значительно сократить время решения задачи за Ьчет уменьшения количества фрагментов, а также за счет автоматизации .перестройки устройства от фрагмента к фрагменту. Формула изобретения 1, Устройство для расчета больши х сетей, содержащее блок моделирования ветвей, первый выход которого соединен со входом, а первый вход - с выходом блока управления, первый вход которого связан с первым выходом внешнего запоминающего блока, вход и второй вы-

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

входного логического коммутатора, вы..,. „.„., fer

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

блокТ элементов памяти, а tioiftaito ченк выходу блока поиска фрагментов среды.- /

2. Устройство по п. 1 о т л и ч а ю ще е с я тем, что блок поиска фраг мёйто1в среды содержит матрицу эапомйнМнйя йаправлений, узел передачи направлений,. сметчик количества сдвигов и реверсивный регистр сдвига, причем первая группа входов матрицы запоминания Направлений является группой входов блока, вторая группа входов матрицы запоминания направлений соответственно соединена с выходами реверсиююго регистра сдвига, выходы матрицы запоминания направлений соединень соответственно с группой входов узла передачи направлений, первый выход которого соединен со входом реверсивного регистра сдвига, второй выход связан со входом счетчика количества сдвигов, а третий вШод является выходом блока, выход Ёчетчик количества сдвигов соеаияеп со входом yai/ia передачи направлений. Источники информации,

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

1. Васшьев В. В. Приближенный Мбт,оп решения некоторых вариаци6ннь1х задач с локальными функцноналамя. Вестник АН УССР, 1974, fc 11.

, 2. ДоДонов А. Г., Хаджинов В, В, Об одном/методе решения: больших сетей на цй(}ровых аналогах. Сб. Гибридные вычислительные машины и комплексы, Киев, Наукова думка 1975 (прототип).

иг f

. ,

иг,2

иг.З