автореферат диссертации по радиотехнике и связи, 05.12.14, диссертация на тему:Разработка и исследование специализированных вычислительных устройств для управления и проектирования сетей связи

>ГБ ОД

МИНИСТЕРСТВ) российская ФЕДЕРАЦИИ. ПО СВЯЗИ, ИНЮРМАТИКГ И КОСМОСУ

НОВОСИЫ1РСКИЙ .') Л Е КТРОТ Е У. И И Ч ЕС к и й ИНСТИТУТ СВЯЗИ им. Н. Д. ПСУРЦЕВА

На правах рукописи

С'Вл !___» !С>Ь)т д'

РЕПИН 5ЕСГГ:.. .'пЫЙ ВИКТОР КОНСТАНТИНОВИЧ мгкп.-

УДК 681.323

РАЗРАБОТКА И ИССЛЕДОВАНИЕ

СПЕЦИАЛИЗИРОВАННЫХ ВЫЧИСЛИТЕЛЬНЫХ УСТРОЙСТВ ДЛЯ УПРАВЛЕНИЯ И ПРОЕКТИРОВАНИЯ СЕТЕЙ СВЯЗИ

05.12.¡4 - Сети, уеду грязи и распределение информации 05.13.13 - Окислительные маежкы, .комплексы, системы и сети

Автореферат

диссертации на соискание ученой степени канли.гата технических наук

НОВОСИБИРСК

министерство российской хедера:;'::

ПО СЕЯЗК, ;ШФОРМАТЙКй V. КиОМОСл НОВОСИБИРСКИЙ ЗШСГРОТЕХНИЧБОРМ 7ДСТ;ГГУ7 ОТзЯЗК им. Р. Г. ПС У Р НЕВА

на правам рукописи

УДК 681.323 Репин Виктор Константинович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ СПЕЦИАЛИЗИРОВАННЫХ ВЫЧИСЛИТЕЛЬНЫХ УСТРОЙСТВ ДЛЯ УПРАВЛЕНИЯ И ПРОЕКТИРОВАНИЯ СЕТЕЙ СВЯЗИ

Сети, узлы сеязи и распределение информации Вычислительные малины, кокплэксы, системы / сети

.АВТОРЕФЕРАТ оиссергтцш на соискание ученой степени кандидатка технических чау :

05. 1?.. 14 -05.13.13 -

- г -

Работа выполнена в Новосибирском электротехническом институте связи им. Е Д. Псурцева'

Научный руководитель - доктор физико-математических наук

Шпков В. К.

Официальные оппоненты - доктор технических наук

Бандман О. Л

кандидат технических наук, . . доцент Егунов Ы.Н.

Ведущее предприятие - указано в решении специализированного совета

Защита состоится " 1994 г. в часов на

заседании специализированного совета Д118.07,01 в Новосибирском электротехническом институте связи им. Н.Д.йзурцева

Адрес: 6ЭЭ125, Новосибирск, ул. Кирова, 85

С диссертацией южно ознакомиться в библиотеке института

Автореферат разослан " 1994 г.

Учений секретарь спэдз;п tu тированного совета ick.il , профессор

4

!и

Б. И. КРУ К

- 3 -

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Оппмизационные задачи, возникавшие при управлении и проектировании сетей - задачи анализа и синтеза, имеют слогзый комбинаторный характер. Их вычислительная трудоемкость в значительной степени зависит от размера исследуемой сети. Еркхгеяенке спггегзлл-зкрованных вычислительных устройств в качестве средств аппаратной поддержи в автоматизированных системах управления и прсентярова-ния позволяет понизить трудоемкость резения оптимизационных задач за счет распараллеливания процесса вычисления. Это дает зсзмощность при'-равных временных затратах применять Солее слогзкэ, а следовательно, более точные методы оптимизации, или при адекватных методах сократить время решения.

Исследованиям в области специализированных вычислительных устройств для решения оптимизационных задач на графах и сетах уделяется большое внимание как в странах СНГ (А. Г. До донов, К К Васильев, Ю.Ф. Мухо'пад, К К Попков. Е. А. Ралдугин, Ю. 0. Черныаэв, С. Цой, К Ы. Курейчик и др.), так и за рубежом (Савадж Кариа, Атал-лах, 'Бхабани Сингх, Чанг-Биан Янг, С.Левитан, Р. Дехтер и др.). Особое внимание этим исследованиям уделяется в последнее Бремя в связи с достижениями в области микроэлектроники, позволяющими реализовать специализированные вычислительные устройства по технологии СБИС.

В Киеве в институте проблем регистрации информации в течение многих лет коллективом под руководством профессора Додонова А. Г. получен ряд фундаментальных теоретических результатов в области развития аппаратных средств и алгоритмов специализированных вычислительных устройств, которые нашли практические применения в серийно выпускаемых специализированных вычислительных машинах "АГОР', "РОТЫ", "МОЗАИКА", "СТРУКТУРА" и т.д., предназначенных

для решения задач сетевого планирования и оптимизации сетей.

Несмотря на обширные теоретические исследования и практические результаты в области специализированных вычислительных устройств, существует ряд вопросов, которые подлежат дальнейшему ис-• следованию. К ним относятся повышение быстродействия устройств, решение потоковых задач, вопросы применения устройств для управления и проектирования сетей связи.

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

Для достижения поставленной цели ь диссертационной работе решатся задачи:

1. Разработки аппаратных средств и алгоритмов работы специализированных вычислительных устройств.

2. Теоретического обоснования' алгоритмов и определения их вычислительной сложности:

3. Ш}сра и обоснования алгоритмов анализа и синтеза сеаей связи с помощью специализированных вычислительных устройств.'

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

5. Проработки технической реализации предложенных устройств в микроэлектронном исполнении.

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

Новые научные результаты:

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

анализа к синтеза сетей связи.

2. Способ автоматического формирования топологии исследуемого гра|>а с помощью система шин передачи адресов элементов сети.

3. Способ обмена информацией о параметрах между моделями эле-1тов сети с помо1ць;о пин передачи данных.

А. Методические рекомендации по проектированию и использова-з специализированных вычислительных устройств в системах связи.

5. Аппаратно-программные средства кентролл изделий РЭА.

Основные научные поколения, представляемые к защите:

1. Применение специализированных вычислительных устройств мо-зфуюзего типа для решения задач управления и проектирования се! связи позволяет сократить время или поеыскть точность решения счет распараллеливания процесса вычисления в моделях элементов ч:.

2. Сормироьание топологии исследуемой сети в спецнализирозан-: вычислительных устройствах посредством передачи параллельного ;а конечного узла с выхода модели свершенной ветви на входы всех ;елей повыпает быстродействие устройств моделирования.

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

4. Алгоритм управления потоками и маршрутизацией в сетях ктросвязи с использованием проблемно ориентированной вычислимой системы и аппаратно-программных средств.

5. Алгоритмы синтеза сетей электросвязи с использованием блемно ориентированной вычислительной системы.

6. Устройство и алгоритмы контроля изделий РЭА, использующее оды моделирования сетей и, вследствие этого, обладающие сокра-ным временем контроля при повышенной достоверности.

7.' Оригинальные конструкции специализированных вычислительных ■ ройств и рекомендации по их инженерному проектирование.

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

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

Реализация разул тагов работы. Рекомендации по проектированию и применению специализированных вычислительных устройств для анализа и силтеаа сетей связи использованы в отчетах по НИР Вычислительного ц?ктра 00 РАН. Мотору контроля монтажа использованы в уетронсть^ контроля монтажа в аппаратном производстве АО "Завод . С>.'БСТАНК'^ЭЛЕКИчШРйВОЛ" > что подтверждается соответствующими актами.

;.пр;б-йц,:я, рчСсгм. Основное полэкония и результаты дксеертаща оккс;: раос :ы оОеу^&глзь 'л получили одобрение на научно-техиичес-кпх семинара4' и совещаниях, в тон числе на ме»дуна-

род-|о/ научие- ге>:;-...^;-ской кокдор-.-нщш "Проблем:,! Функционирования пг^.а'ааалокгл.а сетг-Г ( Нозх-ибврзк, 1391 г.), на Всесоюзном соке сг:н:'.: "Прл'сладлае сздачи на грхд^х и сетях" ( Новосибирск, 1981 ;, кч П. III и IV £сесою?иых совеыааилх "кйтодц и программы ре-с-плвя;г>а.'глонных задач на грсфах и сетях ( Улан-Удэ, 1982 г. 1и:з;.л:?> 14-^4. г. , Новосибирск. 19&9 г.), на XXV областной научно- •,'Слн;-.".-.-олэ;1 г.окчср'зкцш: Н»0 РЭС им. А. С. Попова ( Нэвосибирск, г.}, 1С. р$гкон&л£зой коаферэкцки "Еичкслжельная техника к дискрет-¡от !.отеттк;са" ( ИэвэскСкрек, 1бй2 г.), на Всесоюзной ча-уч: -:о-тех:ь'.чгткоЛ кэьфпрзкцк'г: "Надекюет!. и качество функционере во лил ипСсрма'/л'онных сетей и их о-яемэнтоБ" ( Коьосибирск, 1965 г.), ка в^чаз-тюкдавско«* со^лнаре "Качество функционирования и надег. исс.'ь спете?.; автокпт; ческой кэту/х&а и сетей электросвязи" ( госизд- .в, 1&23 г.), : а гсосошксу к^аференшк! "ЬЪделированке сие тел: ил' ^.оюглблре;:, г.).

Т&Ц/''¡1" р^а;:-.ссио^лой работы опубликовал 14 1..- н;;.: г гаа- ьс.а с .а..?; и, 8 ¿окладов п 3 а!

работы изложено на 103 страницах машинописного текста, огягтр;*;»' ванного рисунками, графикам* и '.т.бяиогми на 46 страккгдх. Спис--'. цитируемой литературы кз 60 н&нг.'-^вачий приведен пч ь отр.лк-л-:-.

СОЛЕРКАНГ.»; РАБОТН

Во введении диссс-ртацлэккоЯ работ;,' содержится сбссис: «;«*;»:• туалт.кости разрабатываемой темы, формулируется цель рабгты I? пр;' ■ годится ее обсая характеристика", перечисляются новые научны- Результаты и основные положения, представляемые к з агенте.

Первый раздел зссертацяон::ои работы посвящен сгаг:.,• анализу сугггствукхзгс уетодов пссароения специявигир.*: -. лительных устройств, г. тага© методов построения щ; I; рованпьк вычислительных систем (ГОВЗ) для ое;книл гак,"-* '" • и сетях.

За последние годы значительно возрос интерес специалтс: , мух различных областей науки и техники к тгсрии графов и с2т>.?-оптимизации. С математической точки зрения больсинство гедъч кизацки косят слоянкЛ комбинаторный хараггер, количес.л еииое ■ нке которых в основном состоит з организации путей о различи«*« характеристиками среди некоторых компонент грз-Ьа и з еучис т-нлл параметров этих путей.

В,разделе приведены понятия и определения, используемые в диссертационной'работе: граф, сеть, элементы графа, пути в гр'-'Ь':: т. д. , алгсгигмы решения опия/из яшючкых задач на графах.

Еместе с развитием методов оптимизации систем сетевой структуры и появлением алгоритмов, базирующихся на применении ЭВМ в сетевом анализе при рекении реальных задач, слолидось такле научное направление, в котором исследуятся, разрабатываются, обобщится вопросы, связанные с постановкой различных праггических зада1: з сетевой форме и построением алпапатно-ориентирэванных алгоритмов специализированных вычислительных средств для их решения.

' Специализированные средства - наиболее эффективные и экономичные устройства обработки информации ввиду ориентации на выполнение алгоритмов определенного класса задач.

Специализированные вычислительные средства разделяются на ) крупных класса - устройства, моделирующие структуру ксследуемогс объекта непосредственно, и устройства, моделирующие математичо« модель задач!! (например, матрицу инцкденцлй или алгоритм решени» К первым относятся модели прямой аналогия, которые предполагает адекватное отображение не- только математических зависимостей, не пространственно-временных соотношений. Параллельное шделироваш на аппаратном уровне непосредственно реализуется в однородных ш неоднородных вычислительных структурах в аналоговых, цифровых и аналого-цифровых специализированных вычислительных системах раз-дачного назначения.

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

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

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

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

1. Низкое быстродействие при формировании топологии'за счет передачи адресной информации число-импульсным кодой.

¡¿. .Низкое быстродействие при моделировании, обратно пропорциональное точности вычислений.

3. Оптимизация в них может осуществляться только по одному параметру, что ограничивает функциональные возможности этих уст-

ройств.

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

1. Гринцш автоматического формирования топологии исследуемого графа с помощья системы пин передачи адресов элементов сети.

2. Принцип обмена информацией о параметрах между моделями элементов сети с помощью шин передачи данных.

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

Второй раздел посвящен исследованию принципов построения специализированных вычислительных устройств.

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

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

Потоковые задачи представляет наибольший интерес в оптимизации на сетях. К задачам о максимт^ьном потоке и потоке кт-шимальной стоимости сводятся задачи управления потсгами на сетях с коммутацией каналов и сообщений.

Решение этих задач на специализированных вычислительных устройствах сводится к шогскра-гисму нахождению пути (кратчайшего) приращения потока и заполони--» его потоком. Путь приращения потока ищется волновым поиском на :,:од?лях ветвей, которые ограничивают потоки, протекающие ь г.:адсл модели, величиной пропускной способ- • ности ветви. Кроме того они !<о позволяют протекать потокам в обратном направлении, ее;:: по ;к.:шоа модели не был пропущэн поток на предыдущих итерациях !;.-."1;: -:;;л пути приращения потока.

Предложено устроАстг/; д:;л моделирования максимального потока., состоящее из блока моде:;;. нет-г..:!, блок.:-. формирования топологии и блока управления. Устрог аю ;< холл каждой итерации определения пути приращения потока ясо.:£.",оваг«.ако проходит три режима работы: волновой процесс, режим пути и процесс записи потока.

Путь приращения потека :1дел;;руегсп распространением фронта . •волнк от узла-истска сети до узла-стока. 'Пои этом последовательно от узла к узлу иницкализирух!а: модели :;.э:зей, способные передать поток - прямые и обратные. Ре^лм завершается при достижении фронтом волны узла-стога.

Б реляме определения г.у .-я :: П'-т-ка ¿рент волны продвигается в противоположном направлении. Яри этом определяется величина потока и принадлежность ветвей дачному пути.

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

Для решения задачи о потоке минимальной стоимости предлагается три варианта-реализации зтого устройства:

1. С использованием шинных структур - вычислительная сложность алгоритма - 0(ш(Г+а), где ¥ - величина потока в сети, а -стоимость передачи единицы потока.

2. С использованием спискового представлен;'?! топологии и

децентрализованным процессом распределения потека - 0(г,Са+ 2пг).

3. С централизованным распределением потока -0( т( а+2Р( 1 +2п))).

Для решения задач управления и проектирования сетей связи предлагается ПОВС, которая состоит из спецпроцессора и микро-ЭВМ. Спецпроцессор представляет собой устройство для моделирования потока минимальной стоимости. Мкро-ЗВМ предназначена для гвода/вн-вода решаемой задачи и ее результатов, а также для управления ходом решете:7 задачи - зводсм задачи в модели элементов спецпроцессора в ссо? :.г.'С'Тьи/ с алгоритмом ептадаацш.

В ?_?>•-':: -;н разделе рассмотрены вопросы применения ПОВС для уг-равлекил и •."•■о'исировакия сетей электросвязи.

Наг.'оестезгрэнякм способом управления сетевыми структурами является модслхэогшя« процессов, протекающих в-них с г?могз>в специажзпроданных вычислительных устройств, способных в рэальпэч, а чаще з значительно опере.-лвдем масштабе времени имитирерзть процессы, происходящие в сетях.

Рассматривается задачи управления потоками на сетях сгяаи -коррекция плана распределения каналов первичной сети при изменении ситуации на атл и распределение потокоз по ветвям сети, которое -егт югак^альзуй среднюю задерлку сообщения.

Для реген/а используются метод поочередного ЕЫбора и занятия кра???йгжг по длые путей неяцу парами ус-лов, имегет.Я вкчксл;ггзль-нуа с.'с^лость при решении на ПОВС 0(пг(п+<1)), и метод распределения каналов с организацией пучков по единичным каналам с трудозя-•г ст с о: 0 ( с т г С и -1- ^.)).

Пригк огэритч реслш для параллельного метода распрэдог г>№п (. сочетающий в себе простоту метода чо-

очередкего гкбо-^ч со-;::оеть, близкую к точнее:-:«, «.»"одса гсгейногс.

Д:,: класса Фольги.--. и сбалаксироганн;:/ сетей существует

г.ий алгзркгм оть'^-лниа потоков, аъпразлпе^/к: ¿ккзкрэвшю-'-. процедурой кпртр/тоь, но требами/ прилшелга методов нели-

нейного. прегра^.ерсван/л дзз оптимизации нелинейной целг-во": Фучк-цки средней задс-р.^-кк. Ахгзритм реализуется на ШВС и состоит кя

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

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

Время'определения кратчайшего пути (с1+1)т/Гт, где Гт-гакто-Еая частота работы устройства.

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

Аппаратная поддержка реализует слесуицие функции: приостановление передачи и при-»& данных при запросах на моделирование пути, восстановление обмене. данным!! после завершения передачи управляющего пакета; ыоделироЕан;® задержки в линии пропорционально длине очереди; обеспечение прохождения упраьллссш: пакетоё по сети в прямом и обратном направлении.

Лля телефонной сети с коммутацией каналов предлагается ёолно-еой 'алгоритм установления соединений по кратчайеим среди исправных и свободных е данный момент'путей, причем каждый абонент может менять свое местоположение и включаться ь сеть ъ любом узле.

Задачи САПР информационных сетей могут быть эффективно решены с помощью специализированным вычислительных устройств, входящих в состав. ПОВС.

Показано, что проектирование сети более эффективно при использован»« интерактивного режима работы 1ЮВЗ. Ингсекер-проектироЕ-икк мопэт достаточно точно и бистро анализироватг топологические преобразования, произведенные ШШ, вводить изменения б топологию с выводом кагздоч итерации ьг- графический дисплей.

Рассматривает: с»: вопросы лонг/енепия НОВО при оптимизации топо-

.v. „еги методами перестановки ветвей, устранения вогнутых ре--ec, насыщения разрезов; алгоритмы контроля k-сгязности и дострое-нкя сети до к-связной.

¡'сследовано применение специализированных вычислительных устройств для контроля изделий РЭА.

Известные групповые методы контроля и диагностики электрического монтажа обеспечивают полноту контроля только при наличии возможности подключения через коммутационное оборудование устройства ко всем к проводникам электрического монтажа одновременно. В большинстве случаев подключение ко ьсем неводникам невозможно, например, при ограничении на мо^ссть, ;тст:^5ляему:о ют/-;утационнкм оборудованием. Для устранения г:сго лсстатка пр^лг^н логарифмически;'! по частя!.! способ контроля и диагностики рчгС'СГК'ШОСТИ прс-яодшктов электрического монтажа.

Разобьем множество к проводников с присвоенными им дзохчными номерам! на k/р частей б ссответствии со старшими log к/о разрядами двоичного номера проводников. Затем двоичные разряды log Ч/р сдвинем вправо на один разряд и произведем разбиение множества проводников в соответствии с этими номерами. Повторим разбиения до циклического переноса правого из log k/p разряда в старший разряд гада номера проводника. Обозначим граф, полученный в результате разбиения: Gj (j = 1,2,3... log k/p ).

Теорема 3. 3. Если хотя бы один из преобразованных графов G j не является пустым графом, то исходный граф Q также не пустой.

В каждой из частей производится проверка обычным логарифмическим способом по свободным от разбиения разрядам номеров проводников. Число проверок равно log р. Так как проверки каждой из час-гей разбиения повторяются k/p раз, а число разбиений равно числу здвигов вправо log k/p разрядов с циклическим переносом от общего числа разрядов log k/p и составляет log 2k/p, то общее число проверок раЕНО k( (log2k/p) log р)/р.

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

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

Расчеты показывают, что на одном печатном модуле размером 220*233,4 мм можно разместить 256 моделей дуг спецпроцессора П( На втором модуле такого размера можно разместить блоки управле! синхронизации и задания списков. Конструктивно она может быть встроена в микро-ЭВМ семейства СМ1810 или подключена через ста! дартный параллельный порт к персональному компьютеру типа IBM f

В заключении сформулированы основные результаты и выводы i сертационной работы.

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

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

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

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

5. Доказана высокая эффективность применения ПОВС на осное предложенных устройств для управления потоками, маршрутизацией установлением соединения в сетях электросвязи.

6. Предложены алгоритмы проектирования топологии и пропуск ных способностей сети с использованием ПОВС.

7. Предложены аппаратногпрограммные средства контроля злен рического монтажа, имеющие повышенную достоверность.

8. Проработаны вопросы конструкции специализированных вычис-?льных устройств. Доказана экономическая целесообразность прак-гской реализации ПОВС. с использованием' БМК

Материалы диссертационной работы нашли отражение в следующих шкациях:

1. Попков В. К , Репин В. К. Специализированная вычислительная тема для решения задач на графах и сетях // Прикладные задачи графах и сетях: Материалы Всесоюзного совещания 1981.- Новоси-:к, 1981. с. 87-116.

2. Репин В. К. Формирование топологии графа на модели // Тези-юкладов XXV областной научно-технической конференции. Секция шслительная техника и системный анализ" 1982. - Новосибирск,

!. с. 16,17.

3. Попков В. К. , Репин В. К. Специализированные вычислительные юйства для решения задач теории графов // Методы и программы >ния оптимизационных задач на графах и сетях: Тезисы докладов зсесоюного совещания 24-26 августа 1982.- Улан-Уде, 1982.

•ь 1. Алгоритмы, программы, применения, стр. 164,165.

4. Репин В. К Мультипроцессорная система для моделирования юв и сетей // Вычислительная техника и дискретная математика: юы докладов региональной конференции 1983. - Новосибирск, 1983. Ю-23.

5. Попков В. К., Репин В. К . Устройство для моделирования крат-мх путей на графах: Авт. св. СССР N 1051543. МКИ Q06F15/20.-

!. - БИ N 40.

6. Репин В. К. Моделирование информационных сетей с помощью тимикропроцессорной системы // Методы и программы решения оп-[зационных задач на графах и сетях: Тезисы докладов III Всесо-iro совещания 28-30 августа 1984.- Ташкент, 1984. Часть I. Ал-[тмы, программы, применения, с. 192,193.

7. Попков В. К. , Репин R К Устройство для моделирования экст-1льных путей на графе: Авт. св. СССР N 1129617. МКИ Q06F15/20.-

, - Бй N 46.

8. Репин В. К. Мультимикропроцессорная система для синтеза се// Надежность и качество функционирования информационных сетей

и их элемент.;:-, ".ез;:?-.: . ..'адов V Ьсчсоьило:: к c*4!io-T<?xhKV>cKOf. конференции и.с. .я I'j-.i.. - йовосиЭирек. IW8L 87.v.

9. ¡--'Пии Р. к. Применение однскрис: -»льних гикр^-ЬкЛ' для управления потоками информации на сети // }.-•■- : -.о сукчиксчироьзния к надежность систем аьтг.«аткч*екой комм;:.;.'.:;- сетей .'-¿.-ктрссвязи: Теэись! докладов облагт^го научно-пех;: семинара 1-3 июля -1988,- Новосибирск, J 98is. 22, ЯГ

1С. Репин В. К. Per-ei:'»' ■ оптимийсилошшх задач на моделирующем процессор»: // Уод<глк;х-ьани-? систем информатики: Тезиса докладов всесоюзной конфет.енц»>'.- сентябре 1986.- Новосибирск, 1988. с «

95,90.

И. 'и'опков Ь. К., Репин ЕК. Устройство для определения пара метров cer-л. Авт. or. СССР N 1488823. МКИ G06F15/20. - 1989. БИ N 2:-.

12. Репин л К. Модель вычислительной системы // Методы и программы решения оптимизационных задач на графах и сетях : Тезисы докладоь IV Всесоюзного совещания 17-19 октября 1989.- Новосибирск, Ч*гть 1. Алгоритмы, программы, применения, стр. 171,17/.

10. Репин В. К. Аппаратные- модели ь управлении информационным., сетями Проблемы функционирования информационных сетей: Мате от лы Уэждународной научно-технической конференции 2-6 сентябг* 1991,- Новосибирск, ' часТ1- с. 197-20С.

14. Попков В к. . Репин В. К 'Алгоритмы контроля монтажа Системно--.- моделир! ;£.*№.•:. coopkk'c научных трулов зц 00 РАН - Нова сибирок. 1994. с