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

.ЖИСТЕРСТЗО ШСШЕГО И СРК/ЩЕГО СПЕЦИАЛЬНОГО 'ОБРАЗОВАНИЯ УСС?

ХАРЬКОВСКИЙ ОРДЕНА ТРУДОЕОГО КРАСНОГО ЗНАМЕН ШСТИТУТ РАДИОЭЛЕКТРОНИКИ Ж АКАДВМКА М.й. ЖВ&

УДК 681.3:519.688 На правах рукописи

АРУТЮНОВА ЛЕНОРА ЮРЬЕВНА .МЕТОДУ СИНТЕЗА АЛГОЕЖОВ ОТОБРАЯЕШН

яквшшвш форм шш задач з

БШйСЖТЕЗШНЫЕ СТРУКТУРЫ

Специальность: 05.13.13 - Вычислительные машины, комплексы,

системы и сети.

АВТОРЕФЕРАТ

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

Харьков 1992

Работа выполнена на кафвдрт^е^смтот^^и-хтатгап-»врыию-ского ордена Трудового Красного Знамени института радиоэлектроники имени академика М.К. Янгелк

Научный руководитель - доктор технических наук, профессор Мурашко А.Г.

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

■ Филиппенко И.Г,кандидат технических наук, сгаргшй

■ на7чннй сотрудник БерднкоЕ Т.К.

Ведущая организация - Институт проблем моделирования б энергетике АН УССР

; Защита состоится "__199_г.

в___часов на заседании Специализированного Совета К.068.37.0!

в Харьковском ордена Трудового Красного Знамени институте радио-; электроники имени академика М.К. Янгеля (310726, г.Харьков, проспект Ленина,14).

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

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

•Баш OT3KS на автореферат в 2-х экземплярах, заверенных печать», просим выслать по çapecy: 310726, г.Харьков,пр.Ленина,14

Ученый секретарь специализированного совета , к.т.н., доцент

Э.А. Сукесов

ОБЩАЯ ХМЖГ2РИСТИКА РАБОТН

Актуальность псо5.1й;д<. Программа интенсивного развития народного хозяйства' стран;! на основе уехорзния'-.-¡аучно-техннчесяого прогресса, иялозснла.-; з "Основных капгавлениях экономического и социального развитая '-ССР на 1966-1599 года и на перка до 2000 года' г;рздусматризает пирокое внедрение сВМ зо вез сферы производственной аеятельности, увеличение производства' средстз вычислительной техники з 2-.';,3 раза и существенное повышение эффективности использования

звм.

Существует ряд проблем и задач, которые предстоит решить на ¡ути совершенствования средств вычисления я управления. К взжнейзим »адачам относятся такие как:

- поиск новых принципов синтеза эффективных архитектур екчисли-'ольных систем и комплексов управления;

- поиск новых принципов синтеза эффективных структур систем рограммного обеспечения;

- разработка систем автоматизации программирования, создание овых эффективных языков программирования шеокого. уровня;

- поиск новых эффективных параллельных алгоритмов и вычислитеяь-лх методов решения исследозтельсккх, инженерных к экономических здач;

- разработка идей построения архитектур новых поколений вкчие-!тельных систем, комплексов и се''.:**;, увеличение гибкости, живучести кштеятуры систеш математическое; обеспечения и др.

Большой вклад з решение этих и других проблем и задач, возникает: в процессе развития средств и методов вычислительной телики и ории программирования, йнесли отечественные и зарубежные ученые А.Лебедев, 3.11. Гяуоков, А.П.Ерпюв, З.В. -Евреияов,- Г.Е. Пухоз, А. Поспелов, Г .И. Марчук, А.В. Каляев, а .Б. Ушаков, И.Ь.Смолоз,

ILM. Витекберг„ B.E. Котов, Дк.Маккорги, Г.А. .Кож, У.Д-.Кар-плвс, Дк.А. -Беки, Э. :Дейкстра к др., 'чьи фундаментальные .работы к исследования. ео многом способствовали интенсивно^' развитию новых прогрессивных средств к методов вычислительное техники.

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

Поэтому .очень важно знать не только потенциальные возможное^ аналоговых (АБС), • цифровых ,(ЦВС'), • иктегркруших (ЦЙС), однородных (ОВС), неоднородных (ЕВС), гибридных (ГЗС) или аналого-цифровых (АДВС) .вычислительных машин-и систем, не и; уметь грамотно-' ставить и -резать задачу выбора. От-.правильного решения "задачи выбора во шЬгсм зависит суммарный эффект применения вычислительной'техники в управлении, моделировании и результативности эксперимента и Енедрения.•

'- Настояааг работа посвящена. решению -.задач, связанных- с :автоматизацией процессов.' синтеза 'вычислительных и мо^елирупцкх структур по згуханноку математическому описанию • решаемых задач. Осуществляется автоматический машинный синтез структур, адаптивны к стратегия** проведения вычислительного, эксперимента по--критериях точности и быстродействия. -С целью, управления процессами синтеза вычислительных cvvyzT/p г работе разработаны к исследованы алгоритмические , программные, языковые и аппаратные, средства, -обеспечивание решение задсч синтеза 'еаакгиЕШх- структур в.'автоматического' режиме. 4

Цель работы. ■Основной целью диссертационной работы геляется развитие и совершенствование, теории - и', практики' • авто-'лтизаиш* процессов • синтеза вычислительных и модаяарущих струя- , ур по заданному матоматячёскогсу опасаниэ решаемых- задач.

Основные задачи исследования: -

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

- разработка концепции построения асинхронной параллельной налого-цифровой вычислительной-системы <АИ5С), относящейся к лаосу неоднородных. ЕС с переменной программируемой структурой

наделенной свойством адаптивности по точности и. быстродействию зависимости от класса решаемых задач и от заданных стратегий поведения вычислительного эксперимента;

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

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

- техническая реализация принципа регулирования;

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

Методы исследования. 3 процесса исследований и разработок этор опирался на работы сспотених » затубеяных ученых з области $орка вычислительных, упркзяятаах к модели оущих систем, екстем-:го анализа, имитационного модеднрзганил, .теории алгоритмов и >рмальных языков. Для теоретических иседедозгняй•в основном

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

научная новизна. В результате выполненных.научных иссле-

■ дований в диссертации соодана основы теории автоматического

■ синтеза вычислительных и моделируицих структур, наделенных свойствами адаптивное®!, переменности, гибкости и ярограьотрг?-емостк архитектуры. В рамках данной теории получены следуавие новые научные результаты:

- сформулирован приоип регулирования тонкости и быстродействия к разработаны-два'-'метода управления ¡.регулирования) точностью к временем решения задач; . ,

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

- разработаны ••принципы формального описания шчислительяах к моделирующих :ст£БГКтур и- создан язык внутренней интерпретации,. являвшийся входным -языком системы автоматической коммутации;

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

Практическая"ценность•■ .получанных результатов определяется

■ тем, что с ни. дают.. методологическую основу и программно-алгоритмический иксгрумеатарий автоматического синтеза -вычислительных к .модвлин^гх-'.структзф, ;.'дцаптивных.к стратегиям проведения вычислительного эксперимента. ,

Работа связана с общесоюзной целевой комплексной межвузовской программой "Микропроцессоры и микро-ЭВМ", научно-технической программой "Апродсп" Минвуза УССР.

Пракгаческг-? реглизапия. Результаты работа внедрены и пр:;-долглют .ледрлться в народное хозяйство.

Програыглно-аягсритмическое 'и'языковое обеспечение, связанное с созданием технологических средств для проектирования вычислительных структур и программного обеспечения, выполненных по постановлению ГКНТ СМ СССР, принято государственной комиссией я вошло в технологический комплекс по производству программных средств и систем кроссового математического обеспечения мульти-«икрспроцессорных систем (Центрспрограммскстем, г. Калинин).

Результаты работы используются в учебном процессе Харьковского института радиоэлектроники. , С^гларнкй годовой экономический эффект от внедрения результатов работы составляет 75 тыс. рублей.

Алроба-пия результатов работы. Основные результата работы доложены автором и обсуждены на слодуших научных конференциях: Всесоюзные конференции по аналоговой и аналого-цифровой вычислительной технике (1988, Москва), Всесоюзный симпозиум по' гибридным вычислениям (1987,Киев); Всесоюзные совещания по автоматизации программирования средств ABT (1985, Москва).Республиканский семинар научного совета АН УССР по проблеме " Теория и машинное проектирование электрических -электронных схем'Ч 1988,Киев); Всесоюзная научно-техническая конференция "Моделитюваше-85" (1955,Киев); научных конференциях по радиоэлектронике (1986-199I Харьков).

Публикации. По теме диссертации опубликовано б печатным работ, в том числе I монографик.

гч

/

Сттагктура и объем работы. Диссертация состоит из введения, четырех глав и заключения, содержит страниц текста, рисунка, таблиц, списка литературы из 6 / наименований

и приложения, состоящего из текстов машинных программ объемом .страниц.

СОДЕРЖАНИЕ РАБОТЫ.

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

Изучена эволюция архитектуры АЦВС, выделены наиболее важные эволюционные моменты теории . вычислительной техники и рассмотрены основные нововведения, положенные в основу проектирования вычислительных систем будущего: параллелизм, повышение уровня интеллекта внутренних языков, модульность архитектуры, перестраиваемость архитектуры, иерархичность структуры, асйнхронность'системы, прогрессивные режимы работы и др. ! ,

Сформулирована концепция синтеза архитектуры АЦВС, характеризующейся наличием следующих взаимосвязанных и взаимодействующих -компонентов: аналоговой вычислительной машины (системы)- АВМ(с), асинхронной параллельной.вычислительной системы - АПВС, согласутацзй системы - СС, системы автоматической коммутации - САК, интерфейса с входныш и выходными каналами, поля операционных элементов - ПОЭ, поля элементарных процессоров - НЭП, оперативной памяти ■— ОП и про-цессоро-памяти - Пр-П.

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

е-

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

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

Машина-диспетчер (М-Д) представляет собой ЦВМ, основным назначением которой является управление.математическим обеспечением АЦВС.

Устройство сопряжения и связи (УСС) содержит преобразователи информации типа аналог-код" и "код-аналог", а также специализированные преобразователи, работавшие с приращениями цифровых и аналоговых величин.

Система автоматической коммутации (САК) является специфическим устройством описываемой АЦВС, в которой реализован принцип ^ - кратной коммутации.

В лесвой главе также поставлены основные задачи исслэдова-. ния: -

- разработка языка для описания объекта моделирования, па-

*

раметров задач и служебной информации;.

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

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

- выбор стратегий проведения эксперимента по точностным 1! временным параметрам и синтез схемы решения, удовлетвотэяшей заданной стратегии;

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

о

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

Пусть дана акалого-цифтвая вычислительная система В, содержащая множество .аналоговых А и цифровых С вычислительных блоков: • , & \ л __—— ■ « -

в -Л (/с, ~ [ &/}:, Л ^ 'Л. / ^

где - число типов , -• число .¿^^¿^го типа, наст-

роенных на -ый алгоритм Функционирования, а - число

алгоритмов функционирования ДЗЛЗ £ -го типа.

¿Г

Обшеэ число АВБ - ^ ^^ ' __

■ /

где (Л-, ^А/С у ' Ж- / ' имеют, аналогичный смысл

толы-л для цифровых вычислительных блоков (ЦВБ). ,

О ^ 2 ^ -

Общее число ЦВь ¡(-С

Имеется множество алгоритмов решения некоторого класса задач

Для реализации алгоритма

посредством вычислительной системы. В . необходимо выделить подмножество И £ & вы-числительннх блоков и задать-оператор-сопряжения т1 , который определяет ,зид сети связей. Оператор ~/7 и подмножество М образуют структурную схему для реализации алгоритма ' .

■ ■■■" Каждому алгоритму (¿р С & можно поставить в соответствие миояествс структурных. схем &Я. ^, ^Ж»

1и

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

Требуется иг множеств?, выбрать такую структурную схему реализации алгоритма на множестве В,

которая давала бы решение, удовльтворянщеэ одной из следующих стратегий: • ;

2)' #и/г при ?

3) ^ при ^ Р

4) Г; ^ -

где Т^ - заданное время, а заданная погрешность решения

^ - ой задачи.

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

- для заданного множества алгоритмов £_/ и структуры вычислительной системы $ —/Р/У¿^требуется построить коммутирующую матрицу Ь , содержащую минимальное число элементов;

- решить задачу построения рациональных вычислительных структур для вычислительной системы /3^^^^; задача & ___

может быть разбита на операторы

0= /, где - число типов операторов, -тлело операторов -го типа. Операторы X можно реализовать

на множествах^ или С, либо нр множестве 3 ^. Каждому элементу £ /} и С^ / С- поставлены в соответствие весовые коэффициенты: по времени - /{? и по погрешности - & Тогда время решения задачи на структурной

с

схеме будет функцией масштаба Бремени Л/Г и

коэффициента Кх т.е. = ^ ( Мт , }-(т ), а погрешность

Требуется выбрать структурную схему - ^ , для которой

и удовлетворяли бы заданной стратегии;

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

- решить задачу планирования загрузки;

- решить задачу.автоматического масштабирования г-гдр. Вторая глава посвящена разработке языков программирования

параллельных АЦВС. На основе принятой блочной концепции структуры системы автоматизации программирования АЦВС, данцая возможность построения открытой для расширения САП, входной язык первого уровня, т.е. язык формулировки.задач, разбит на следующие разделы: язык.; описания объекта моделирования (ШОМ); .'язык задания служебной информации (ЙСИ); ; язык, описания параметров модели объекта (ЯОП); ... . язык внутренней .интерпретации (ЯВИ). . . : В работе представлены все.указанные,языки,.сформулированы основные требования к языкам, произведена детальная разработка : всех языков и описаны основные свойства языков и границы их при! менимости, приведены основные правила написания текстов на введенных языках и рассмотрены характерные'примера с: введенными со: ответствущими ограничениями.

Здесь ...будут кратко представлены лишь некоторые хслючевые. фрагменты языкового обеспечения АЦВС.

/.Язык "Аналог", состоящий из.трех модулей ЯООМ, ЯСИ и ЯОП, ■относится к классу контекстно-свободных языков и описывается формально грамматикой & У, , ^ "Т^теркш^ль-

Я алфавит, « - нетерминальный алфавит, <5 - аксиома,

VI/ }f . Р = i di j - конечная

стема подстановок, o¿¿ Мс С. -T'/Vj- свободная полу-

уппа над объединенным алфавитом. ;■

Ключевые слова: начало, конец, начальные, дополнительные,

Терминальный алфавит

тлкьла

аялтл xkx.xz.bnж,зл%ал4ц. i

ШМ, k f' -At**; л« Ш, ил

Нетерминальный алфавит li^ = zZ - цифра, ¿2T - целое з знака, £ - целое число, - дробное вдело 73//, С. -др.ч - число, У - буква, Х- возм.воздействие, р -яроиззод-í, б - пара ч., S - список пар, c3f - таблица, -Р - функция, ,- идентификатор, У - завис, переменная, - перемен-s, \) - терм, - множитель, о~ - первич.выражение, Ь — флетическое выражение, ьО- обыкн.яиффер.уравнение, ¿г'- простое ;свапвание, - присваив.нач^5иовий, X - начусловия, у -¡условия, - экстрем.знач. J¡- простое экстр.значение, -(грамма J-r

Схема грамматики:Я— ¿С5~ — начало ü) ; X ; j? конец сало и) , X конец; | Допо^тельше^;^^^^^ rw^V-^/^начальные; tU¿¿M "¿Z¿ ^ £;

£ ¿)/'l)/c г о/г-ú/-,

/V; f-^p/j; s;

^/d ■ ¿'A / ■

/-/; /а.a ; Л -^¿ва.; P~>Dag; в yy/jr/s/a/f/j /У/z/S.../W/gi

Пример: ЗУ* ЯПЛУ+^М*

I %Утсл «у; г..

ур «Д; У*ии=2: ¿^г-^/-/ ' < '

Текст на ЯООМ: начало ■ фШ; =0- допусл

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

Раздел языка "Аналог" - ЯОП предназначен для задания исходных значений'параметров объекта моделирования и числовых значений: начальных условий, максимальных и минимальных значений переменных, масштабов, интервалов и шагов интегрт^ррвания, таб-. личных значений функций, пармметров службы времени и т.п.

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

Текст на ЯОП представляет собой последовательность операторов, 'начинающуюся.оператором "параметры".и .оканчивающуюся

оператором "/ щ ", например: I_» параметры операторы Я0П^>

/' * .

Конструкции оператора вне зависимости от его типа единая: оператор : : ~ <^тип оператор.^>^комментари^>:^информация к оператору^» :

Х4

^тип.опер^ :: = НАЧУСЛ /МАКС ЗН,/мШ.ЗН./МАШ. / ТШ. ¡...¡Ж ШТЕГ.1... <^инф. к опер^ :: =<ЧС>|<ИД>=(ЧС)|«ЧС>, <ЧС>)|(<-ВД>

оп.нач.усл^>:: = НАЧУСЛ. :<^1ШРЕ^==<^ф|<^ПР0ИЗВ^>= </чС^>... Ш:Х2-0, Р1 хЫ,5); (МАКС:2 14=9,7); ИНТ: 40;'ШАГ: 01;

Раздел языка "Аналог" - ЯСИ представляет собой набор опера-оров различного уровня и назначений, который по существу опреде-пет средства специализированной операционной системы ЩВС, Основ-ге категории этих операторов позволяют настраивать АДЕС на задач-1в конфигурации аппаратуры, выбирать средства для отладки и испол-?ния задач, управлять поиском, проверкой данных, организацией ужбы времени, обеспечивать ■ режимы мультипрограммной работы и зделения времени.

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

^Текст ЯСЙ^>: := ¡._, служебная ^операторы группы <^опе-

оры группы к ... кооператоры группы ?

^Операторы группы :: = ^конфигурация АЦВС^: ^информа-о связях^

^Операторы группы : = ^выбор системы программирования ачи^ : <^вид выполняемой работы)^: Добьем расчетных работ АВС^>; ....^Операторы группы :: =-^привязка ксзфф. к бло-АВС^У : ^ривязка коэффиц. к потенциометрам с ручной

•ройкой^ .

Фрагмент

<_1 служебная

,_, конфигурация ЦВМ: ЕС-45, АВМ:АВК+ 32(структура: стандартная).

связь: канал,-коммутация АВМ : задана

i—I план работ

система программирования: гибридная - первого уровня POlVTRA. Задание: трансляция, расчет ASM, подготовка АВМ

управление данными Ввод данных: ПК, вывод данных ЛД; печать АВМ: табличная; Объем памяти АВМ: стандартный; сохранить производные:

Генерация функций Табличная функция

аналитическая функция: Блокнел: Каталог ЙОГо'/З ^^Н^

■г

i__I Реализация коэффициентов

Механические коэффициенты: AI, А2, A3, £¡1, В5;

Электронные коэффициенты: 31, В2, С2 .

А

Практическая реализация ЯСИ накладывает некоторые ограничен связанные с тактико-техническими данными используемого оборудовг которые рассмотрены в работе.

Заключительный параграф второй главы посвящен разработке языка формального списания 30, являющийся входным языком систем] "автоматической коммутации. Язык позволяет.описать формально bci зсзмз-кные соединения, между- элементами структурной схемы посредс специально введенных указателей. Введены следуицие указатели, и

связанные с ними наименования-и признаки:

с1- указатель структура ^ - указатель-последовательности;

^- указатель; £ - указатель главного элемента; <£.- указатель

вспомогательного элемента; А - первоначальный" указатель; -

/ * '

указатель стандартной процедуры; - код элемента; ^ - номер элемента; И. - номер входа элемента; код процедуры; -номер процедуры;Р-? - наименование; 0 - признак главного элемента; I,- конец; ^-^- наименование; наименование; А' - у?/-наименование; /Я?- ^ - наименование и др.

Правила грамматики языка при введенных обозначениях мета-леременных имеют вид:

¿>; </»>// =</> '■> '¿У . <£><Г>Л'-<Г>]<£><#>

у > >/\)>/<~"><Л>;<р>

' <&>;<£/& >Г:*=<&>>'

4 -*""* ' *

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

5 том, что признак и указатель главного элемента указывай? зле-!ент, выход которого должен быть соединен со входом (или входами) сругих элементов, которое- задаются при помощи указателя вспомо-'ательного элемента. - ....

При использовании" принятой. з--работе системыкодирования ¡ормальное описание ВС задается в виде, ■ навпр.утаких"-строк: 1_,0,0301 010100 й—мП0Ю2а_-Г ... '■«—» 0,0101 *_» 030201 010200 ...

. . 1_I 0,0302 /__1020100 -

Расшифровка первой строки: - 0, - признак главного элемента, тип которого 03 (Интегратор), номер которого 01; строка читается: выход главного элемента (0,0301) соединить со входом 00 элемента 01 (потенциометра), номер кторого 01, и со входом 02 элемента II (индикатор), номер которого 01. Другие строки читаются аналогично I,- признак окончания схемы, как последовательности соединений,^ процесса. ком\угации.

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

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

Процесс синтеза вычислительных структур производится в неск ко этапов: на первом, который является подготовительным, осущест ется математическая постановка задачи на входном языке системы "Аналог"; на втором этапе с помощью машины-диспетчера осуществля ется лексический анализ, распознавание и трансляция математическ описания решаемой задачи с входного языка на внутренний язык интерпретации; третий этап реализует алгоритмическую поддержку, со данную для автоматического синтеза рациональных вычислительных структур, осуществляется расчет данных для контроля и настройки соответствующих структур; на сеть связей ВБ накладываются ограни чения £ - кратной коммутации, а схема решения упорядочивается по специальным алгоритмам так, чтобы построенная структура сооте ствовала возможностям систеш коммутации; машина-диспетчер преде ляет структурнюю схему на внутреннем формальном языке, и в коне*; счете кодированный текст формального описания поступает в систеь автоматической коммутации устройства сопряжения, где осуществля«

18 -

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

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

Для рациональной организации процессов сштрч' X и прохояде-:я задач в соответствии с заданной стратегией и-сома матемэтичес-зго обеспечения АДьС (машины-диспетчера)- снабжена спедаализирован->й операционной системой, которая является дополнением к стандарт-)й ОС. ■

Таким образом, концепция функционирования специализированной гстемы алгоритмов ОС-АЦЬС на ояисыгаекоы уровне состоит в синте-!, выборе, опенка и самонастройке определенной конфигурации сп&-:цконккх олементов, связанных в соответствии с алгоритмом решаемой дачи в цельную ВС, удовлетворящук заданной стратегий решения.

Представим кратко результаты синтеза алгоритмов спеииалнгиро-нной ОС-АЦВС.

Алгоритм формирования пакетов задач. Пусть тлеется структура

. i <&>, *Г~ , 4?- ^j . т ^

JOE В£>, количество'ВБ L -го типа, а общее число блоков

-Sc/SJ . Дано множество В= {.../^/независимых задач.

5ая задача а/'^ ¿> может, быть'декомпозирована ка операторы зее число операторов fy'= jsjl^

г решения любой задачи на структуре А необходимо, чтобы выполня-\ъ следующее условие: какуга бы г руту из ¿р операторов ш не ¡ли, .ролзно найтись, по крайней мере,, ^'вычислительных блоков.

каждый из которых.может реализовать один из операторов. ¿¡то_ условие названо условием возможности решения.

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

' .Поставленная задача комбинаторного'типа решается методами .дискретного программирования.- Введение переменных

[I, если ^ -я задача включена в пакет, О, в-противном случае, ^ =1,2,... , ,

к!

ц

позволяет задачу планирования загрузки сформулировать в виде:

<2. л

найти Л/ при условиях ^ /и ^¿^<=¿2, —

Iпри ,гае<7^'-коли-

чество элементов ¿, -го типа , в структуре А, - число НВ £- -го типа, использутацихся в ^ -ой задаче, С^ - число ВБ, необходимые для решения -ой задачи. '

Решение задачи возможно получить разными известными методами. Выл использован метод случайного поиска.

Оптимизация задачи заменяется решением системы (Г±2 неравен с /2 булевыми переменными: ^

■Система решается методом итерации. Допустим, на К- ом шаге полгчек

набор ~ / Лу\ ♦ • (начальный

вольно). Затем.вычисляются величины:

а, };

I ¿ъ? J (

г Я £ 7

А/ ш^И*' ¿7;

с -

Независимо друг от друга случайным образом изменяем компоненты вектора X с одинаковой вероятностью ?=ГГМ1 /Ч по./с А ¿X

К.1 4

<9 ¿2-<¿-'1 и находим новый вектор X . . Процесс решения систем, закончен, когда все обратились в С.

Так как в работе при синтезе САК использован введенный здесь ¡ринпип С - кратной коммутации, то алгоритм формирования пакета ■

1адач несколько усложняется. Дополнительными данными при этом явля-

■ матрица связей для

тся: - матрица связей ЗБ - Ц /

адачи /У-/

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

Следующий этап состоит в ток, что полученное решение проверя~ гея на соответствие возможностям коммутирующей матрицы .

Постановка общей задачи автоматического синтеза ВС по математи-;скйм описаниям исходных задач требует решения задачи выбора и ■ ?енки по точностным и. временным параметрам. С этой целью в работе 1зработаны метод и алгоритмы выбора и оценки ВС по параметрам "2" .

СТ.

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

Требуется из элементов множества выбрать такуи структуру £ ^ , чтобы она позволяла регить задачу С^¡'бЭи

.удовлетворяла заданной стратегии (1,2,3,4;.

Введено понятие матриц весовых коэффициентов по погрешности и времени: . :

- матрицей весовых коэффициентов по времени называется матрица , именаая строк и столбцов, каждый элемент которой определяет, какую временную занерглсу вносит в решение задачи & вычислительный блок ¿?-го типа с алгоритмом функционирования /^у !

•-'аналогично определяется матрица погрешности-/У-^/^Яг$_

введена переменная ■ '

если вычислительный блок ¿"-го типа используется при решении ¿--ой"задачи , ^- .

(_ 0, в противном случае.

/О ,

Тогда задача выбора структурной схемы ^ для каждой

стратегии формулируется сл едущим образом:

Стратегия I. Найти ^¿-¿г <-£Г > для которой

/ ^ -¡с? /

Стратегия 2. Найти

* д/ ^ » '

при р

Аналогично для стратегии 3 и 4. Поставленные задачи откосятся к задачам комбинаторного типа и решены в работе методом ветвей и границ. В работе построены алгоритмы для -каждой стратегии эксперимента (1,2,3,4), операторные схемы алгоритмов имеют вид (на приме стратегии 4):

. Введены операторы: : £ =1, /4: выбор ^-'_ой строки;

Ру :/: - Ъъг ; ^

A(i: заполнить j -ю строку в r ; есть запись в я ; ^-.Use^Hcj ч-'АКс-;

[3 перебор всех вариантов двух строк: J ~ ой строки к Я -, п -сверка выполнения условия Ifoj -А Яг ¿МтсЛ ¡(^ Н^е;

:ть ли решения, удор~->--орякп:пв ftQ-Afe^&reA /чф'АКг&Лее ? ; У£ : печать решения, останов.

Операторная схема алгои:тг.:а выбора ЗС по стратеги;: -1 имеет ¡д (аналогичг.ые алгоритмы'для стратегий осмерг.атся ь -ра-

Третья глаза диссертации зг.зерлаетея разделом, в котором 1едлс.тена одна частная нетс-дикз интегральной оценки погрешности шекйя задач ira 'аналоговой части ДЦВС. Поставлена и решена задача родеяения параметров интегральной погрешности■вопроизьедения есккя го порядка, т.е.- определенно математического о;-.н-

нкя ÛlAjfj (~k) и сро.пке-квадраткческого отклонения & .¿l^/i^) ■ основании прогсденкых стзтистичсскго: испытаний методики, еде-, к вывод о применимости'предложенного-способа априорной :;нтс-аяьноП оценки погрешности диалоговых репеяа8, т.к. имеется рантия, что "плохая" схема ке будет оценена высоко.

В четвертой главе предложен и разработан метод непосредстден-1 прямой трансляции (отображения)' уравнений, опискваекнх задач;/, зччисяимаднне структуры, который реализован s виде библиотеки ;тных алгоритмов отображения, коирая входит как составная часть >бщую схему САП.

Задача состояла в построении таких алгоритмов отображения запеляц!®)'языка математических формул на язык структурных схем :окмутационных отношений между операх^гонными элементами.

Язык внутренней интерпретации (ЯЗЯ), введенный оо второй главе позволил формализовать процессы 'построения- и-, коммутации структурных схем.. -

Автоматический синтез ВС методом непосредственного отображения выполняется'- тохгз 'с использованием введенного языка- Основная идел'состоит. в • следующем: при'- отображении-,.- напр. .ОДУ; И -го лорллка („)у. '

.-f ----

n аналоговую вычислительную-.структуру, .-работа' алгоритма полностью определяется числами fi -ACCtifr Так -называемыми базисными структурами, которые для какого г/ла уравнений (линейное, нелинейное, однородное, неоднородное, с..постоянным/переменными коэффициен- ■ •гам» и 'т.д.) создаются заранее и - находятся -в. памяти машины-диспетчера. При этом выполняется два основных действия: составление цепи понижения порядка производной, 'образование .-обратных связей в схеме с цепями инвертирования сигналов или без такового, что оп- ' ределяется по признакам ©¿¿г

Базисные структуры при прлиятой. системе кодирования имеют

ВИН \

■ ' " _ ' ''

ill: 0,031 01 I 00 ОССООО П2: 0,01/ 0316 tD 01 000000 -

ПП1 : 0,03/ 01 (/7 */ +К -I) 00 01 L ОС iiii : 0,01 (г- tJ+£ -I) 03 01 j 000000

nniil : .0,03 i- 000 oi/oo'

¡* - номер интегратор.:;, /2 -» порядок-урашепид. ^ - цом-зч зходз первого интегратора,- К » кс^ер kksqotoes, П1, Ш1, 11ПП1 р * тип структуры и номер строки.

Метод непосредственного отображения частных форм математического описания решаемых.задач позволяет получить экономичные; транслирующие программы для большинства - типов дифференциальных, интегральных и' ПЯТегро-дифференпиальнкх-ур'авнений. В работе создана библиотека частных алгоритмов построения аналоговых, пифрокгх кнтегрирупсих и аналоро-цишрових структур. в которую включены • 22 программы отображения.

Испытания программ проведены на различных ОДУ и СОД}', порядок которых изменялся от 2 до ЮО. Определен практически линейный закон нарастания времени трансляции' г. зависимости от порядка уравнения ^ . Метод непосредственной" трансляции высоко эффективен по временным затратам (для сравнения: уравнение,24 порядка; время трансляции - универсальным транслятором ^ 12 сек.,.методом прямой трансляции ~ 550 МО). . -'

Введенный формальный .язык предусматривает возможность любых соединений мекпу элементам. Такая коммутация называется полной. В работе введен принцип - ¿Г -кратной кэмкутации, который позволяет существенно сократить число комг^тирртцих (КЭ) элементов; проведен анализ возможных ограничений, получены эмпирические зависимости для определения числа КЭ при ¿'-кратной коммутации.

Общее число КЭ при -кратной' коммутации определяется с учетом типа'схемы и типов'элементов, составляющих ее,-по формулам

Г: ■■ ,

-.Г., '

где--^ = 1,2,3,...,. С -число инверторов, ^-..число интеграторов, {Г~число входов, А - число интегросум-маторов. С увеличением зисла -типов и--количества блоков £ -пргтная1 коммутация датт ощути-^экономию КЭ. Так, при

где - потенциометры, - функциональные преобразователи, Р~ Iтюлсительно-делительняе блоки, С - стандартные процедуры и число На при полной коммутации Нп = 15Щ2, а при ¿"-кратной К& '

Г гпва четное завершается построением алгоритмов синтеза гзцкокалышх систем коммутации. Сформулирована и решена задача ■_-г:он:!я о.-.раничений на сеть связей разнотипных операционных о."("а;;тов для ЕС с программируемой конфигурацией, исследованы г^.злпчпке фор;® представления структурных схем и разработаны г.л?орит:.гы перехода от схем решения, заданных в графическом гл~е или в виде формального описания, к условным матрицам, которое позволяют компактно записывать информации о ВС в памяти 1!£:-а2а1-д:1спетчира. Алгоритмы автоматического построения САК реализованы на кабинах серии ЕС; например, при исследовании 22 вычислительных структур была получена матрица и ,. -содержащая • 250 1-:о'.".<утиг^тдих элементов; время, затраченное на получение обобщенной матрицы, равно 1,7 мин при быстродействии 20 т.опер/сек. ■

Полученные

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

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

В пг.гло-знип приводятся тексты' машинных программ на языка прогрз:,:.™.роваакя "Паскаль".

26

основные результаты к выводы работы

1. Анализ состояния проблем повышения эффективности вычисли-, гельных систем и систем математического обеспечения, изучение и сравнение черт различных средств ВТ с жесткой структурой позволил ¡формулировать задачи синтеза архитектуры АЦВС, основанной на флнципиально новой концепции.

2. Сформулирован принцип регулирования точноеи быстродействия и разработаны два метода управления точное- ъг и временем ' ешения задач, один из которых реализуется в процессе автоматического синтеза ВС, а другой - динамике процессов вычисления и модели-ования.

3. Создано языковое обеспечение для исследуемого класса парал-эльных аналого-цифровых ВС.

4. Разработка система программного обеспечения АЦВС, скстеиа зтомагазации программирования, предложен и разработан метод кело-зздетвешого отображения математических списаний в вычислительные' ■руктуры, на базе которого создана библиотека частных алгоритмов •ображения для большинства типов дифференциальных, интегральных и тегро-диффоренциальных уравнений.

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

6. Разработан и исследован комплекс моделей и алгоритмов для эспечення алгоритмической педдеряги принципа регулирования.

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

:а возможность получить экономический эффект 75 тыс .руб.

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

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

ПУЕШТКАПЖ ПО ТЕМЕ ДИССЕРТАЦИИ

I. Арутюнова 1.2., Цурапжо А.Г., Снвденко Г .И. Нормальное опясанзе вычяслвтельннх структур. - Харьков^ 1990. -

С8 с. - Лэп. в УкрКИИНТИ, Л 2 (232), б/о 465.

Арутшова Л.О., Мурашко А.Г., Оншеахо Г.И. Язык формального спясаапя структур. - Электронное моделирование, 1952, гпнь.

3. Арутажога Л.Ю., Мурашко А.Г., Онвшенко Г.И. Прятотн отойра"гн:;я математического описавгя в Бнтаслательные структуры. -

Электронное моделирование, 1992, июяь.

■4. Арутааова Л.Ю., Мурашко А.Т.,.Онзщенко Г.И. Пришит» построения систем автоматической коммутация ■вычислительных структур. - Управляющие свстемн и мгтпнн, 1592, июль.

5. Арутлноза Л.Ю., Ыурашко А.Г., Онищенко Г.И. Алгоритмы поотроэнзя рациональных систем коммутации..- Управлязше системы :: г.-а^яы. 1352, июль.

с. Арутансва Л.Ю. Алгоритмическая поддержка принципа рзгужроваЕгя вычислительных процессов в АЦВС'по временным я точ-тстн-м параметром. - Харьков, 1992. - 36 с. Деп. в УкрНЭШТИ, 3 (243), б/о 3£5.

ПолплСс:ко печати 25.II.92г. Зорыет бум.60x84 1/16 1,0 п.л. Спссг?.печ.удкый оосет. Зак.190 Тиозж ТОП. Бясплэтно-ОСП Ари.СХй ул.Теряна, 74