автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Маршрутизация данных в параллельной памяти

o u>n

ЛЕНИНГРАДСКИЙ ОРДЕНА ЛЕНИНА И ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЩИИ ЭЛЕКТРОТШЗЖЖИЙ ИНСТИТУТ ИМЕНИ В.Н.УЛЬЯНОВА (ЛЕНИНА)

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

Стариков Адцрей Николаевич

МАРШРУТИЗАЦИЯ ДАННЫХ В ПАРАЛЛЕЛЬНО!! ПАШГИ

Специальность: CS. 13.13 - Ецчисшггельныв машины,

комплексы, системы и сети

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

Ошда-Щтсрбург - 1232

Работа выполнена в Ленинградском ордена Ленина и ордена Октябрьской Револщии электротехническом институте июни В.И.Ульянова (Ленина).

Научный руководитель доктор технических наук профессор Негладкий Б.А.

Официальные опшшнгш: доктор технических наук профессор Штатников А.В., кандидат технических, наук старший научный сотрудник Сергеев Ю.Ф.

Ведущая организация - Ленинградский институт точной . ' механики и оптики

Защита состоится " $ " 1ъУЛ.т. в -чао.

на заседании специализированного совета К 063.36.12 Ленинградского отдана Ленина и ордена Октябрьской Революции эпвкгротехничаского инотитута им.В.И.Ульягаза (Ленина) по адресу: 197376, Санкт-Петербург, ул.Проф.Попова, 5.

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

Автореферат разослан " О^^-Я^Ч

а

Ученый секретарь

сев циалюировэиного совета

Валакин В.Н.

-г <

| ОБЩАЯ ХДРАКТЕРЛПЖО. РАБОТЫ

Актуальность темы. Одной из нзиболее сложных проблем, стояпдех ред специалистами в области разработки злем-ронных вычислитель-х машин, является создание устройств повышенного быстродействия, а проблема порождена рядом причин- расширением круга задач, ре-емых с использованием ЭВМ, увеличением сСъ?ма информации, обра-тьшаемой прикладными.программами, стремлением адаптировать комп-кс "ЭВМ- программное обеспечение" к потребностям пользователя.

Разработка современных аппаратных'средств ведется в двух ос-вкых направлениях: в области совершенствования элементной Сазы и области поиска и разработки оптимальной архитектуры ЭВМ.

В настоящее время в архитектуре ЭВМ широкое применение нахо-т принципы конвейеризации, параллелизма, распределенной обработанных. В концепции памяти с параллельным й многоформатным дос-пом к данным (ПГЩ), явлйицейся объектом исследования, наиболее кое отражение нашел принцип параллелизма.

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

Преимущество параллельной памяти по сравнению с традиционными поминащики устройствами достигается .за счет организации запоми-пцей среды на базе N независимых модулей памяти, что позволяет гспечигь одновременный доступ к N элементам данных, составляющим тонченную информационную' подструктуру. При атом возникает' необ-[дамость в специальных 'аппаратных срэдсгйах: (коммутационных се-£), преобразупда внуг-реннее представление информации на уровне цельных модулей! памяти, в логически связанное представление дан--с в виде подструктур, -

В .диссертации рассматривался проблемы организации хоммута-. энных сетей (КС) на Сазе дзоичьых перестановочных сетей (ДПС) в иках теории сисгем параллельной памяти, разработанной, кодпекги-I специалистов во главе с профессором кафедры МО ЭВМ Л'ЭГИ ллицким Е.А. В большинстве работ, :шсвящешшг проблеме прсекти-иния ППВД, рассматривается случай, когда на ДО .реализуется

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

В диссертационной рзбатй пред&гаетая годаод, пря котором управление КО может быть адаптирэЕаш к стсобу организации вашми-нащей среда, а управллщая дел сегк вычисляется в т-

№кг иащпалязации паралд&шлй: та-дти. Крота •того, s работе исследуется проблема перехода к рэшаззаии КС я устройотв управления ел в виде комплекта микросгеыбоддеЯ стзпенй.' интеграции. .

Дельд диссертационной рзйеш Г-Шется разработка катодов и средств управления кскк/тащалглыж сзтйгй, аходадам в состав пзмяти с параллельным и 1Шои46р?вт«йМ доступом'к данш*.-

В соответствии о ц&шэ Сэрад&^уются;'и рззавгся сяэдущив задачи;

- формирозаакэ трБбоаашй ¡г гл&гэтзшакаЕ: сетям, входящим в состав ПГЩ, и выбор средств даз к.: ¿¿nnspEïistf! ре&шзаща;

- разработка квтодоя упрса^жы хаг^у-'ех^шы&ш сатями;

- сшетез устройств упразгзг^г. Екз^угвцшвньш сетями;

- разработка йдасобса сскрзЕЩ-м .затрат кп аппаратную реализации йкяса коммутации 1ЩЦ.

Прздазтом иссстдованш яаюгггсй процесс кзршрутизадаа данных в коодгташкшшг сетях, вм«яь$32 в ссатгз ЫС'Л, способы организации управлекгя гзао&тгштш&а тшш,

Матовы иесдедораниЯ оошгаз ш иагог&етзгиЕШ ашарата тео~ рай структур даггт, булевой сггэфн, т&зрйз иаззств, катодов проэктерозашя , '

Научная ютазна .

На осшккгкз ранге рсфаевтгйжЗ теория построения сссгвм параллельной пемятя sia tçiîopj сзтск:

: - разработаны катоды и аязяагз ¿злусткетсти перя-

• отаяоаоя прайс. реализаций-кз даожи^г шрисгагметчных сетях; ..

- разработаш катода фоа'^йрзшгэ кйтряйа $празявния кокму-, ■ тачдяшыкя сетгш гсри рзадзаадаи ггглгаг :: tspasa тркэнгухяргиз

пзрееггэд&зи, ' учкгикэдкз еазогфгку.' организаций пгйити с парзл-: л&шаая и шюго^орйт!^ доступом;

'• - а соответствия в 1феда5г£;ужз аггорашзкг' рззработаш структура устройств упраалекаа сстя;«$, оржжткро-

бзпшэ на реализации иикник трзангздарньк псрзстггетэзгс;

- вы я плены загаюкзрнеп-: организации парзотаюпок при выполнении операций чтения и зьпкеа, позволяпциз сократить затраты на' аппаратную реалшзцшэ бгсг;г. коизутации ШЩ.

Прантэтескузз цекшсл». р: *5ота ссоташшют;

- расрзботанныо за фук<;ц'*з:1аяьнои ■ уровна схемы управления дашчшми перзстлтЕочшки с/.гяма, входами э состав парзялзль-!!п!5 памяти;

- метод иостроеж'л дналннх пзрестаковочшх сетей болыизй размерности;

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

- вариант практической рэалшгции КО на йзза серийно выпускаемых КО малой стонет интегращз? и пэдэ 8-сети с коммутационными элементами' 4x4- * •

Реализация и ггадзегаэ результатов. Полученные результаты использовались пря ВЫПОЛНЭНИМ хоздоговорных ИЗ?, ПрОВО,ЦКМЫХ на гсз-федрв МО ЭВМ ЛЭИ1 кн.В.И.Ульяпопа (Лэшша).

Апробация работа. Натгрэдг, приведенные в работе, докладывались и обсуэдалксь на:

- научна- техническом'с^ктзр» "Роагровыэ вадзо- терминальный системы"; октябрь, .1989, Алма-Ата;

- Межрегиональном семинара "Сиотеяы цифровой обработки изоб-рааений" (СЦОИ-91), мая, 1391, рига.

Публикации. По материалам диссертации опубликованы 4 почат-Ш8 работы.

Структура и об-ьбм работу. Днссзртационная работа состоит из сведения, чатырах разделов, еекяячвпил, списка литературы, ишна-пцего 49 наимешваний, в приложения. Основная чаоть работы издшв-на на 126 страницах машинописного текста. Диссертация содержит 56 рисунков и 10 таблиц« . " '

: КРАТНОЕ ШДЕШШБ РАБОТЫ.

Во введении обосновывается актуальность тема, опрзделвна область исследования, цель днпсертацяошюй работы й основные по-

ложаккя, ылгосимые на защиту.

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

В первой часта определяется место ГШКД среди параллельных вы числительных систем. В соответствии с классификацией, предложение Флютом, параллельная память отюситсй к устройствам типа ОКВД.

Е этой части приведрны определения понятий структуры и под структуры длнньгх, яшшзщихея Сизовыми при реке) зга задачи органкэа ции параллельного и многоформэгшго доступа к' данным. В соста: ППМД входят: аапомииавдпя среда на Сазе М модулей памяти, , адресш; блок, коммугзционная сеть и устройстве управления.

Во второй части описанз С1руктура и принципы работы пзрал лелыгой измята.

Адресное пространство эатшнашд й среда мокет быть представ лено произведением 1£гА, где

У » < К | D í 8 í (#( }- ккокеегю мойлей памяти,

А *> { А. | О s A s ¡iíj- J- емкость модулей памяти.

В работе в качества стр-етуру данных рассматриваете»

двумерная точечная реявтка Пр1 а в качестве подструктур, к которым обеспешшртся доступ,- геометрические г1юрчагы (строка, столбец, фрагмент).

ОтоОра$енив эхекентоэ структура данных осуществляется посредством функция разкеискал • N,rV? .

klz Hpj, -,13, '», 2.....Е, ... |В|-П

и адресной фу1одк? '

.H.xWo .

Ad: ^ —> {U, % 2. ... , ййг, ... |/.|-1J.

Нз практике наиболее часто испол^зуптся законы размещения (ЗР), базирующиеся нз операциях *\яий»йнца г.дпиг" и сдаг". ЗР

первого тшз описываются выражением иида

Al - (5,'t + ог"3) iwd г.\

где N = !»(.

Р второго типа оспззгта га ппзрггса спгвтя по ггодаэ 2, пржэ-ом ггогст поолугить фушпвг

41 » i ô 3-

K« хНр»

Кгздзму аг'мгпту' рзгпзгсх Ep¿ - eí j в пашгисюспт от pro олзгэгтя нэ ::еордпнатЕСЙ. плоскости, задаваемого коорцштаташ i is , з ссотва- атаке станется опрзда'легаий гадула» тгатп и arpa с !1утрл его:

я - ЛШ, J) я

EdT - Ad (i, J).

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

Xipaitrep упорядочения огтятслг от тотарэг фггетротз:

- сахо:тэ роггипаим,

- сада rccrsiphscroro <-зркзтз era),

- пэд^зкн ГО пэ шзр&лптксЗ Х-ГСГГССТЛ, , .- ркгга сСрзг^пя в пст.'-ттл ■(nïcîns/scîCTb).

çacv^'.^a гкашгэ дгя' ^-ГА'гкгппл гзязг ежа рзгягеют. юрадгскс э дгтас яскэтсз 5гс-утагятю1 глзлгят опгрцда герэ-т.:хг.сп1. '

3 4atC5jt33 и язтоЗ 1Ü8TXC ¿.-^гса опрагг>Хйгэ ашсэ езрз-

V =« £ 7С, ... » ... ,

ЭДПЗС портез КС ПЭ КЗЗГ*ОГЕГ> Í?

œaras шртез .80: " ■

«L •

"3 прпзздэтея ocHsrTH'í сгягэй! стакгяг """"сипсгэт»:: тгб-гоЛ, яагштпгюксЗ и гг.;;».гдгетЗ. ••

3 гкгссзг пртго • алел,! згрзсяпзгзп ггкзт С'гъ яреазткетз гг'зкгя oToCpEt5sa ft., st î^ctïssttsî тетерл

етегз огсташ^стоз ■

"о Wi

7k ••• Vn-2 VN-1 Wk ••• KH-2

Для матривд коммутации выполняется условие:

V^ftlOi vk. Wk <" К. а для матрицы перестановки:

- &J О < Vp < N.

. Аналитический способ описания перестановки задает соответствие меаду множествами V и S посредством арифметических и булевых функций в виде выражения Я » f(VJ.

В тестой и седьмой частях первого раздала рассматривается проблема проектирования КС, которое включает в себя этап выбора архитектуры сети и эт.ап разработки устройства упрзвле;дая. Показано, что при использовании КС в составе ППМЯ описание перестановок, выполняемых при обрашели? к -измятл, М.таот граниться , в виде матриц коммутации (перестановки) в ЗУ сравнительно небольшого обгема (например, при N=16 и строка, столбец, фрагирнт- потребуется и 1Z Кбайт памяти), и что табличная форма описания имеет определенные преимущества по сравнению с ^'шшнмческой; В седьмой части излагаются общие требования к коммугйшйнным сетям, Предполагайте, в частности, их работу по принципу кой^утации подмножеств входов с поданоаествами выходов.

Bq втором рЗэдедр. состой!;«; из пяти частей, рассматривается проблема выбора архитектура lie.

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

елтея конвейерные соёд»одаг$ли, мзтрйчныё ко^утаторы и многоярус-ше сети.

Во второй части производится сравнение уклззшй-т типов сетей го быстродействий, сямсшсти злпйр-эткой реализации, сложности ор гзнизацйи управлений и шзчэкшеп:.реализашз» вишдняемых в параллельной памяти перестановок. На отипиии сфчюулирстапятх в первом. разделе требований, • а', т««ы» результатов^ прозе штого сравнения й качестве KOKtyTaiwore&ar сетей в иярздлолыпй памяти предложено Использовать много я рус и,-с- сощ.

•В третьей части .описываются рээшвккмеи« иг'чсирусгая сетей

! их архитектура. Четвертая часть полшстью посвящена ошюму из ¡вдов многоярусных сетей- доэичньм перестановочным сетям. ДПС яв-шются блокируемыми, поэтому ряд перестановок На них реализован 5ыть не может. Базовым элементом ДПС является коммутационный эле-ент (КЭ) 2-2, который в зависимости от значения сигнала управлв-шя (О/i) обеспечивает прямое ихи перекрестное соединение двух йодов с двумя выходами.

Двоичные сета имеет размерность n*N, где n- целая степень шел;) 2, и состоят из log^r) ярусов КЭ. Каждый ярус включает в себя 1/2 КЭ. Разнообразие двоичных сетей обеспечивается различными зпособами организаций связей мвзду ярусами КЭ. К числу наиболее гавестных относятся сер; типа Indirect Binary п-Cube network (C-зеть), Baseline network (В- сеть), 0 - nettork (О - сеть) и ряд ЗруГИХ.

• Перестановка, реализуемая ДПС, определяется бинарной матрицей управления размером -»г xlog^N , элементы которой задаЬт состояниё гоммутациошшх. элементов сети.

Процесс коммутации некоторого входного порта 7 с некоторым зыходным портом li1 может быть описан как последовательная поразряден трансформация Двоичного кода

V = уш-1 vm-2 vl v0

з двоичный код

91 = wm-1 wm-2 *•• W1 w0-

гда ni=logzN.

На некотором 1-м ярусе С-сета имеет место преобразование

годов - ■

уга-1 vfli-2 -• vi+1. wl-1 ••■ wl w0 wl- '

Физический смысл приведенной выше записи сводится к следующему: гри передаче- иг порта V к порту И на 1-м ярусе, данные, при!года&е ta Vj-й вход (vTH^1 ую_2 ... v1+1 ... w, wfl)-ro КЗ, должны поступить на его Wj-й йаход. Это достигается. шДЬчёй нё управлявший зход этого КЭ сигнала "

С = Vj О Wj.

В пятой часто обсуждаются свойства топологической и фушшдо-

ш-1 ш~

vl+1 "1-1

1 "о V1

калькой гквгватшпоста даапшг сотой, а ш^с- -.2 рпоЕ&згурир: кости, которые сипа пределы в работах Ш и Гьту. "¿сазащгиз сво.": ва позволит сделать дза пракшчзсмИ вшгд, г^да:

1) в состава йаш шюсгутада гщд кетг икиалогагься лабая домшш сетей;

2) деоичшо сзти сольсой разморшсго когут стронься кз <533э с2)

юншсй разкзршсти, шташашшх и евдэ отделит. устройств.

В третье?; разлита. содародм оавохгш и;® ргзумдан расоматршзаотся вариант раа&зацзд КО ва бгзо С-сзти.

Процесс упорядочения дввшх в ШЩ ю ограничивается нзх срадстдашю коггдутахпкй блоков пакзтл с айонзагом, а состоит кзсколысих этапов. В ойцем случае г:арлрутззац;:л нзчшштсл о и лаза возможности рггигазещгх тробуекой пврестзюлхси на данной се (т.б: ее дзпустзздсш). В взрвой к второй чаэтяг лрздлагаотся I кзтодрв анализа дапустцмэош лераегшэахи, продет; влонной в к; ричном виде. ,

Теоретической основой дат. нагучзшаи результатов поолуы теорема Реаае, согласно которой перестановка явдявзся допустим: если соотвотбгвие'юэд разрядам" кодов портов У и 17 тшт бк задано в виде систсш аналитических Е'фааениЙ гада:

= ¥1 ° у1+1"1-1 — и1«0>'

ВД О 4 1

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

Во второй часта рассматривается вопрос класскОикацпи допуст шх перестановок и вводятся понятия ишзкй триангулярной (НТП) вершей триангулярной (БТП) перестановок.

НТП полет бить представлена следусц^и оврагом:

"о "0®°

п, = v, ф г1(в0)

"и-1 = VI.® ••• V»

с е ш, и;

а В'Ш, соответственно:-

.. 72 у,")

■ ■ ч2)

' ^ •

С (О, г.

К ими:! три.ткгу.-. :"рйста!швягм относятся, з частности, шроот:.ш>ша, котор.-з г. г^з/г-- -.г&пзхь Еиде могут с'мть опнсзки охэ-

:7 « а«'/, :,' ■ л п Г,

=» г; : Г, ;» » П*У + Ь,

где а - сопя!;, Ь » ccr.it,

IV ^ М-1.

В работ? показано, к чяс.п !Ш1 относятся пэресташвки, рэага-зуемуе я ПШЩ с з^потаги базирует;:;"^ из операциях

линейною и дчасчого сдвигов.

часта 3-3 тю?г.т$:т пещ^-гч упп'.пгзпня С-с^тьэ. Грзгм часть касается вспроссз сргагюз.рц'гл уп?-г:"::-г:п дзоячкыщ псрестанопо'ши-ми сетями лра регляззцш вж-тгп ?>-!:-шгу.гяриых перзстсновох. Ег.э ранее, а ргСот.я. Кетлпцкого Е.Л. ". Каггсрзпеза В.П., Сало показано, что значительная часть пэрзст^явок, выполшегш параллельной помята с лшэЯнжи и диздк1»"' ?2т:онг?зи рас.'!Э!Ц2Ш1Я, требует группового управления КЗ. В дисссугз'ш этот факт получил теоретическое обоснованно. Доказано, что способ управления КС определяется видза функции-

а, точнее, ев аргументам!.

' При групповом способа управления, обеспзчкваадэм реализация НТП и ВГП, рргукэнтагяг фунащи X* являются коды и

7ш-1 7е-2" ' "71+1' соогЕэтстпенш. Эта ко® на каздзм ярусе идентифицируют группы КЗ, теегадаи одинаковое управление. Таким сйрззом, как это показано а четвертой часта, для форктрсгйнил матрицы управления достаточпо вычислить (Н-1 > бэ згекзнтоп. • -

В третьей' и пятой частя! прадвагаются- алгоритмы вычисления матриц управления С-сетьв при реализации ВГП и НТП, в которых в качестве исходных данныз испшапувтсй, соответственно, матрица перестановки и матрица коммутации. Достоинством алгоритмов является

то, что формирование матрицы управления производится путем вцделе ния определенных разрядов из элементов матриц l'y и Кц.

Восьмая часть содержит классификацию способов управления Описываются, поярусшй, групповой и поэлементный способы управле ния. Отмечено, чго при поярусном управлении фушция принимав шстояшюе значение (0/1), и при поэлементном упрганении аргумен том ij является (m-t)-разрядный код. Описанные опособи управлени обеспечивавт, соответственно: 2u,JeN, 2м"1 и 2м'а*1оч2ы перестзно вок.

В девятой части на базе ранее разработанных алгоритмов синте зировпна структура устройства управлешя С-сетью (при реализаци: НТП). Осноной устройстна является nawfltb состоя!1ий сети (ПСС) хранящая табличное описание перестановок (в виде матриц перестано вок). В работе предлагается дш варианта устройства ИСС. В nepaoi случае ПСС ориентирована на работу с жесткой организацией запоми-нащей среда и в ней хранится описание фиксированного множеств; перестановок. Во втором случае содержимое памяти вычисляется npi настройке ППЦЦ. Предлагаемы^ 'рёшеция тесно связаны с возможностями, предоставляемыми совреме'ийо?! аппаратной базой, и рассматриваются более подробно в четперёо# разделе. .

Блок коммутации в ППМЛ должен обеспечивать требуемую коммутацию шин памяти как при чтений, 'так и при записи. Десятая и одиннадцатая части посвящены прсйлемв сокращения аппаратных-затрат ш реализацию КС за счет:

- выполнения процессов ызЛрутизации, происходящих при операциях чтения и записи, lia одной С-сути; ' '

- упродения устройства упраапеник сетью, используемой при чтении, и сетью, используемой, при записи.

Первый путь связан о 'необходимостью мультиплексирования/демультиплексирования шин. блока коммутации. Введение в состав блока коммутаций двух сетей (С-сети для чтения 'и реверсивной С-сети для загаси) позволяет сократить объем ПСС вдвое.

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

В первой . ' Чайти описываемся . разработанный программный комплекс, даделируйдай работу ГВДД, в котором наиболее детально представлен блок коммутации данных на базе С-сети. Комплекс может

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

Комплекс позволяет Моделировать обращения к параллельной [амяги, состоящей из 16 модулей, ц форйэтэх "гшгвашая строка", 'плавающий столбец" и "плаваЫиЙ фрагмент". При-¿том запоминающая :реда может быть организована либо в соответствии с линейным (аконом размещения, где С, И 0-, задаются пользователем, либо в 'оогЕягстаии любым другим, входящим в состав библиотеки ЗР, зако-гом размещения. Библиотеки ЗР й ГФ могут быть расширены.

Вычисление Матриц коммутации производится го имепдимся )писаниям ГФ й ЗР на основания заданного вида доступа [чтение/запись) и координат, по которым производится обращение. Зычислеигаая матрица коммутации Ку служит для анализа обращения на бесконфликтность..

. На втором этапе работы системы формируется матрица управления :-сетыэ. Предусмотрена возможность вычисления матрицы управления, <ак для случая реализация НТЦ и ВТГ^ так и при выполнении троизвдльной перестановки. После.небольшой модификации данная система может быть использована. для йсслёДрвания ПГЗД с различными эргэкизацияМи ззпомйнзещиХ Ьред и процессов маршрутизации в них в талузвтоМатическЬм режиме. Кроме того, практически значимым результатом моделирования я шлется сюдвряияоё таблиц, хранящий множество матриц управления сетьй, которые обеспечивают выполнение гребуеий перестановок. _

Во второй части представлен фаекг коммутационного блока на Зазе З-сети (разновидность кногеяряойых сетей) размерностью 16«Г6 в коммутационными элементами 4«4. Раздел вклвчает ё себя описание архитектуры сети, алгоритмов упрзвлзкяя й принципов организации устройства управления.

рассматривался случай, когда Запоминавшая среда организована в соответствии с двумя законами размещений:

а.» «л + 41) юс11б, А1 - [з + 4[(1 «эсК + П тос14"|^ (во£14^,

которые позволяют организовать обрацегатс'в формата строки, столбца

и фрагмента.

Коимутацюяшй элемент предгсга;- "роалиэмияъ на базе сди-гзтеля данных К531 ЯР21. При лгетго авогзкгэ дадаз выпол-

нять цгдакескпа сдеяги 4-х ггз^гг^й нсслздша кьЕТ -¿ости вдввз (вправо) ка I, 2 и 3 гозицгш. Код уп.~оаш21я сдоагателам содержит два разряда, а матрица управгоч:-»« иуоьт ро^х-ршсть 4«2. Устройство упрзшкная сгтьв построена * ссотгетсташ с шпеданиьш аналитическим,! зависакостяги и в сзЗя лоппескиэ элемзи-

ты, зояоккнавдйс усгрсйстез к Тек кг.-:: корэстг.?,о«:ки, яв-

ляпдйооя результатом даш^як скхгсь, огаоолтек к дэпустьлг; (па отшакмвш 'к С-сети), --«о ш©о-:о сли^'лтсдк дапел ютаг бить ш-польоовгга и С-соть 4«4.

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

сталла. ■ • ■ (

Предлагается огропть О-сап; цхч'-чажк/*?. ка

0-сотей небольшой рссмэркостя, я отдйлыепг секс.

Такой подход окззшзгэтея вокгахи.» * 1>ют ряхкзйтурцин базовых сетей в ссогагтствлд о 'югодм,. грпЬ'ьхал*?« н Уецд. При этом опшшш язллогоя тот С£гс<г!< пз»;?? 1<з оопзг? а-срусюпс сетей строится сеть с касясстгом яр^шь в.

В третьей •части с.г..; устро£сгФ1 упрэаекгв 0-

сатьв: в одаом случае в ИЗО жр^Гкачи. •..-.• гргда ягазазюм, к другс:;-матрая коодутшки. УстроГ^тг;.. тклз бить, прикгшш

как при реализация ЕГО, *сх а г^п .-слсцеи пр-гззодькяе перэста-аш, но Щ5г 2тск '¿аашгев тейосг..' к требуют значи-

тельных обхеког. яс^лтя.

Устройства • святей . ?:-:г>г б^о г.-зггддьзовак»

дет учивезягя -габей вш^зогдиг» ир:: раквазв» ярс;а-

сзаких шрстспййас. Пр-хд гаи, юо излет быть шао-

рэдеягагю иотадьиазгез дгй. С-сог'^. рзыздозик ИГЛ

' (ВТП). В работе «рсаггагсь //.¿зм«»^ 1КС подобного типа

на бака мюгорггглгро^'О'03^' к ¡.¡эп'-згр д.;ег эодаш-

нэоть «ргаавозать р^бо-гу 0-(!&Г4-в пзплпг о шл-йадфуаюй орга-

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

В дополнение к ПСС было разработано устройство формировав матрицы управления (ФИГ) С-свтья для-случая реализации на С-сети произвольных допустимых перестановок, не принадлежащих к классу 1ГГП (ВТП). ФКУ представляет собой С-сеть, на вход которой подастся элементы второй строки матрицы коммутации. Проходя со входа на выгод, кода настраивают соотватствуппие КЗ СМУ и одноименные элемен-тн управляемой сети. Предполагается, что данное устройство также может бить выполнено в виде СЖС, приведет ориентировочные расчета аппаратных затрат.

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

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

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

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

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

3. Разработаны структуры устройств управления коммутационными сетями. ориентированные на реализации 'нияних и верхних триангуляр-М1Х перестановок, а гзк«е произвольных допустимых перестановок. Предложен метод построения ДПС. большой размерности.

. 4. Выявлены закономерности 'организации перестановок при выполнении операций чтепия и гзлиси, позволящке .сократить затрата

на аппаратную реализации Слога коммутации E5?f. .

Б. Разработан программный коишгсс &ол:;;:ровакш пама паршшэльным I! мшгоформэгным доступом о Еоза» засть рзконфш ции среда гранения. 8 рамках комплекса разрзсФтгва шдедь де ной сети, позволялся формировать содорашмоэ пгнзти соот свти, составил клрй ядро устройства управления йзоком кортах

6. Разработан йети коммутации на бага S-csrj,o K3 4*4, j ш вопросы организация управления блоком, предгз^вш способа партшй рэалшации уотройс-щз управления. .;.;.■.

ЩШЩЮЦЙЗ ПО 5ГШ2 ДВОСЕРЩРИ

1. Горячев Г.4., Стариков А.Н. Реализация трзоташвочнь той на базе оадаоинхрсишиг буферш оапошиаиад: устройств // стая ЛЭ1И,-1Б8Э.- Вып.415.- C.ID5-IQ9.

2. Стариков А.Н. Шапвшнгиов упрашюшо дакгшой пэрес вочной сетьв //Известил ЛЭТЙ.-1390.- Вып.423.- С.127-133.

3. Горлчав Г.А., Стариков Д.Н. Коммутация данных в автш зированшх системах обработки изображений /Ленингр. алектрот ин-г.- Л., IS39.- ?о.~ Дэп. в ВИНИТИ 27-01.89, Шв-В.

' 4. Стариков А.Н. царирутюация данных в памяти о парадле и шюгоформатиш ¿рступом •//Системы цифровой обработки шой ний: Теа.докд. Уезрггшнэлыин'о сгшшара, f-iaft 1991г.-Рита, I С.20-22.