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

¿кшт нш украины

йнстяту? проблей моделировши в энергетике

рГБ ОД

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

УДК 681.323

ГОНКАЛЬ Бпэаа ВладамдроЕна

ИССЛЕДОВАНИЕ II РАЗРАБОТКА СЖЩШСЗИРСШШЖ ШЧтШПЕЯЕЯ ДНЯ ЕОДШРОВАШИ СЕТЕВЫХ ЗАДАЧ

СпэцаальЕость 05.13.05. - Элогэяти п устройства ычдсдэтолыюЗ Техника 2 систем управлзпйя

АВТОРЕФЕРАТ лдссэртащп на созсказш) учэеоЗ степэш кщцзддата тохшгтеспп наук

Клев - 1994

ДассератацЕэй являемся рукопись

Работа вшкдазна в Отделении габрщдных иоделнрущах и управлящш систем в ввертя тике Института проблзы ыодэлнровашя в аЕэргетпке АН Украины

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

05Ецнаяьвые оппоненты

1. Доктор технические наук Катков Александр Федорович.

2. Кандидат технических. наук ГлоОа Лариса Сэргеевна.

Ведущая оргаянзацдя: Институт проблей рагастращш зшЮрслацда АН Украшш, 252113, г.Клав, ул. Шаха 2.

Защита состоится *_*_ 1994 г. в_часов

на заседания специализированного совета Д 016.61.01 Института проблеы шделировання в энергетике АН Украины, 262164, г.Каев, ул. Генерала Наумова, 15.

С диссертацией шкно ознакомиться в библиотеке ШШЭ АН Украины. Автореферат разослан_■

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

сшциалазированного совета г

кандидат технически наук —. — Сеыагнна Э.П

снздя хшшдошяш ршуш

АКТУАЛЬНОСТЬ ПРСВЯЕШ. В на стоящее вреыя значительно возрос интерес к исподьзовашт различных катодов ьщелнровашя для репэння ¡задач в сетевой постановке. Сетевые ш>деш используется при анализа сгшд различных систем - транспортных, юамунжационных, информационных л др. Крона того, она весьма удобны при анализа и синтезе логических сетей, сетей связи, задач классификации и распознавания образов, определения вероятностей слогных событий, расчета основных врэ;_*энных характеристик сетевых графиков а др. Прннцнп сетевого продставлэния тдвщрувжй задачи является наглядный, весьма прост а нэ вызывает никаких затруднений, - поэтому сетевые модели пртлэ-шются фактически во всех научных, социальных н экономических сферах деятельности.

В процессе репэнпя задач в сетевой постановке, приходятся ош-рпроззть с болкзпи числом переменных, анализировать шо^естзо воз-г.слтх вариантов получения результата и проводить выбор из много-ства репзний оптимального. Зто свидетельствует о тон, что сетевые задачи носят*комбинаторный п вероятностный характер. Реализация алгоритмов их решения на универсальных или персональных ЭВМ не всегда аффективна, а в ряде случаев невозмоана вследствие математических трудностей, ограничений на объем памяти и быстродействие для управления быстропротекащиш процессами при работе в реальном нас-птабэ времени. Создание многомашинных кстяексов такзэ является малоэффективным, т.к. требует разработки параллельных алгоритмов функционирования, а это является процессом довольно трудоемким и дорогостоящим из-за необходимости высокого профессионального уровня разработчиков. Кроме того, для обеспечения диалогового ренина работы необходима специальная подготовка оператора, что значительно сокращает круг пользователей. Все это приводит к необходимости исполь- • зования высокопроизводительных специализированных средств вычислительной техники.

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

- г -

аналогового иоделировашя в гибридны! вычислительных систем, разработанная в трудах академика АН Украины Пухова Г.Е.

Среда различных специализировавшее вычислителей больше распространение получили модели задач, основанные на методах анализа и синтеза сетей. Вопросы построения электронных моделей для решения задач об экстремальных путях в сетях, сетевых задач об оптимальных путях, задач сетевого планирования и управления и др. достаточно освещены в исследованиях, выполненных Васильевым В.В., Додоновым ¿.Г., Хадкшовш В.В., Федотовым В.В., Федотовы» Н.В, н другими.

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

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

1. Улучшение качественных характеристик специализированных вычислителей.

2. Совершенствование цифровых моделей за счет расширения класса решаемых задач и функциональных возыошостей.

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

„ЦЕЛЬ РАБОТЫ заключается в разработке высокопроизводительных специализированных вычислителей с параллельным принципом обработка информации н гибкими связями мэаду элементарными процессорами цифровой модели, а *ам2в в организации цроцасооз¡решения ка подобных вычислителях для задач в сетевой постановка.

В соответствии с поставленной целью было уделено внимание рассмотрению слэдувдих вопросов:

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

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

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

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

„МЕТОДЫ ИССЛЕДОВАНИЯ.В процессе выполнения работы использовались:

- аппарат теории сетей и графов;

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

- теория шогеств;

- различные метода моделирования весовых характеристик сетей;

- «этода оценки эффективности многопроцессорных вычислительных систем.

.НАУЧНАЯ НОВИЗНА.В диссертационной работе разработан и предложен новый метод организации вычислительного процесса при построении специализированных вычислителей для решения задач в сетевой постановке.

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

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

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

Оригинальность схеяша реиешЗ зацнщэна 7 авторские свидетельствами.

ПРАКТИЧЕСКАЯ ЦЕШЮСТЬ. Разработанные ыэтода организации вычислительного процесса позволяют создавать специализированные вычислители с болаэ высокой щшзводательностью н эффективностью. Предлогэннне кэтода н алгоритмы использовались в процессе выполнения научно-исследовательских работ ОПУСЭ Шститута проблей моделирования в энергетика Украшы по темам "Инвариант" к "Варан", в такае ряду хоздоговорных теы.

Результаты работы использована цри создании цифрового вычислительного устройства для исследования технологического процесса электроспекания, которое изготовлено и внедрено в Институте проблем материаловедения АН Украины для спекания дисперсных порозков и при разработке и нзготовлэейп специализированного вычислителя для унра-лешш ЕнутрзЕЕЕЛ .темюратурашм полем при исследовании электрофизических процессов в высокотешературных материалах, котор12 установлен в Отделении высокотемпературного преобразования энергии Института проблем энергосбережения АНУ.

ЛПР0БЩ1Я РЕЗУЛЬТАТОВ РАБОТЫ. Основные результаты работы докладывались и получила одобрение на:

г всесоюзном семинаре "Распрделенная обработка инфэрмаццн-1У" ( Новосибирск - Горно-Алтайск, август 1991 г.); ■

- всесоюзной научно-технической конференции "Перспектива развития и применения средств ВТ для моделирования и автоматизированного исследования " ( Иосква, октябрь 1991г. );

- научных .семинарах отдела N 21 ОГУУСЭ ИШЭ АН Украины ( 19391994 ).

ПУБЛИКАЦИИ. Материалы диссертации напли свое отображение в 14 печатных работах, из которых 2 выполнена лично автором, получено 7 авторских свидетельств СССР.

СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертация выполнена на 133 страницах, содержит 52 рисунка, две фотографии и состоит из введения, .четырех глав, заключения, списка лятзратуры, содержащего 83 наименований работ, и приложения.

«ЩЕЕШИЕ PAEQIU

Во ЕЕЕДЕНШ! пргЕО*^тса обоснованна с::туальпоога работы, формулируется ее цель а основана голопзпля, которые пшосятся на всцяту.

ПЕРВАЯ ГЛАВА гтосЕпг,эка псслэдовашкм областзЗ практического ПрГЗЕОПНЯ СЭТ8ЕНХ .'"ОДЭЛЭЙ, а ТЕКГЭ аншнзу ЕЗЕЭСТНЫХ ¡зтодоз, средств п подходов к органпзацгш процоссз ренэння задач з сотовой ПОСТ2НОвко на рззличпнх срэдствах шчеслзтэльесй тэхшш.

Разработан ряд прогрел для расчета различных сэтзшх задач па универсальна п пэрсозальннх SEM. Однако, з ряда сдучазз uz

Щ£МЭНвНЕ9 ЯВЛЯЭТСЯ КШ:ООф$ЗКТ2£Н25, НаПр^Эр, ЦСЛ УЦРЗЗДЗЕПЗ бНС-

тропротзкаи^пл процессия з рзэльнсм масштаба врэгазна из-за запаздывания !язду мс^энтсм ввода пп$ор*4цця л мкэнтсц получения оптимального ре-енля. Кро::э того, нагшлэ в настоящоэ sporn большого разнообразия аягоратстюсках языков тр-эбуот ehcokoü квакфзхащп специалистов, что значительно сокращает круг Еользоватэ.'геЗ.

Однородные вычислительные среды для реализации ксгГпгурацпл сета требуют проводить ряд предварительных опэрециЗ, .смоглость которых внзываэт Е9СбХ03И!,'.0СТЬ привлекать дополнительные вычислительные средства, что та:--9 ограничивает их пр-эдношэ.

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

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

где а - основание системы счисления; е ='Ig m ( m - число вершин в сети ) - количество разрядов в счетчике; - коэффициент разлога-

ния численного значения, который изменяется от 0 до 9, позволяет реализовать любые значения в параллельной форме, что сокращает время решения.

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

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

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

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

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

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

- т -

са задач к другому.

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

3. Цифровой аналог долеэн обеспечивать выделение экстремальных характеристик сети в реальном масштабе времени.

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

4. Уоделирущая структура должна обладать функциональной полнотой.

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

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

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

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

ВТОРАЯ ГЛАВА содержит результаты исследований и разработок в области методов организации вычислительных процессов при-реванш вадач определения путей с екстрзмальныыл сео2ств£^и в сетях и создания на их основе 1:оделэ2 элементарных процессоров.

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

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

В работе предложена алгоритма решения перечисленных задач о путях с экстремальными сво2стваш1. Основными шагами алгоритма для задачи о пути с наибольшей пропускной способностью являются: I. В сети 0(2,7),где X - множество вэраш, V - шоеэство ветвей сети, иайтн любой разрез В, раздэлягцяй начальную а и конечную г вер-шны.

Среди ветвей разреза определить ветвь (х^) с наибольшей пропускной способностью q1^ ( с максимальным значением весовой характеристики. "

3. Из всей сети выделать ветви, для которых

0 при 0=аах (х^е Н.

4. Ичключнть ЕыделзЕане вэтеп из дальнейшего рассмотрения путеы за-шаы пари Еврпяш ха я т.^ одной вердиной Для этой процедуры вге-д<?м тержн "закорачивание". Ира этом пршэы: ,

Г(Х1)=Г(Х1№ Г(х^) и Г !(х1)=Г"1(х1)и г'схр, где

Г(х )=Г(х )У Г(х ) - пр^сэ отобрггэнпэ ЕЭр=ПЯ Х1,Х1,Хл; Г'Чх )=Г~1и >У Г"1(х ) - обратное пх отобрггзнпэ.

Получим прэобразовашуа сэть С' (Х,7).

5. В преобразованной сети прогорать условие совпадения начальной а конечной верзил. Если оно выполняется, то перейти к сагу 6, в противно:! случае - к пагу I, прзнпиая сеть О* (1,7) за исходную.

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

Отличие алгоритмов задач о путях с нага'-эньпэй пропускной способность!), максимальной спринн и задачи о взаа;асвязазштх потоках незначительно и заключается в слэдущзм:

- при репэнии задачи о щтл с неиуэньпэй пропускной способпоста

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

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

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

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

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

В работе представлена модель элементарного процессора для р' пения задачи о путл с наибольшей (наименьшей) пропускной способ"

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

ТРЕТЬЯ ГЛАВА посвящена разработке методов решения потоковых задач и организации на их основе моделирующих структур с описанием их функционирования.

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

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

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

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

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

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

фигурации сети. Для определения параметра, характеризующего топологию сети, предлагается использовать отноненне длины сети 1, под которой понимается структурно длиннейший путь, к ее ширине Б (максимальное количество ветвей сети, одновременно участвухцих в процессе решения ). Очевидно, что при фиксированном числе ветвей т, £/8 характеризует изменение сета в терминах теория графов от нультиграфа до цепочечного.

Анализ, проведенный для решения задачи о максимальном потоке тремя методами, дал возможность получить следутадаэ зависимости времени решения Г и производительности Р от структур« сети Ъ/Б:

V- чЬ**™*«**

5

*иГ 2«1 ♦ ♦ д Ч

Юв^а ь

ркпа

1оя,а Ь ,

Рртт = ---( тт+аэт.-нэто+о

011 2(1/8 + гпя, + х2> ^ 1 22

1о&,а ГI

Рил» --- | -и- (2т1+тр)+2пгс1+,Ср|

т 2(Ь/в(11+г2)+12+т1 12 1 ■ 2л

где:

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

сп - определение максимального потока при помощи нахождения структурного пути;

р - определение максимального потока при помощи построения разрезов;

- время на воспроизведение кодаутнрупцей функции;

т2 - время воспроизведения весовых характеристик;

т2'~ время распространения единичного импульса по сети.

Эффективность предложенного метода моделирования сетевых залг

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

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

ЧЕТВЕРТАЯ ГЛАВА содержа? списавва спэцзашафовсттш вычислительных устройств, разработанных на основе рассмотренных в работе цс£?ОЕах моделей п методов решения сетевых задач, и р:азываэтся области ЕХ конкретного ПрПМЗНОЕНЯ В СОСТвЕЭ ШЧМСЛПТвЛЬНЭГО К0МПЛЗК-са.

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

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

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

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

которого щпнпмал участие автор. Устройство позволяет воспроизводить ТП в ускоренной, замедленном я реальном реппмах. Причем, ускоренные н замедленные рэгтт.и воспроизводятся толка? для анаял-за отдельных операций. Показали ф7Нкцэональшэ еозмогеостп устройства.

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

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

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

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

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

- и -

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

В ЗАКЛШЕННИ формулируются основные результаты работы.

В ПРИЛОЖЕНИИ приводятся акта внедрения результатов днссертацн онной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТ« И ВЫВОДЫ ПО РАБОТЕ

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

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

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

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

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

ных материалах, которые находятся □ опытной эксплуатации в ИШ АН Укранны н ОВПЭ АН Украннн.

Кроме того, была получены следулдиэ результаты:

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

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

- проведен сравнительный анализ ¡методов моделирования задачи о максимальном потоке в сети;

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Братин В.И., Кузьмук В.В., Тонкаль Е.В. Сети Петри и алгоритмы параллельных процессов // Гибридные вычислительные машины и комплексы.- 1985.- ff 8. - C.I9-24.

2. Буренков Г.Л., Истомина Т.И., Тонкаль Е.В., Федотов Н.В. Вычислительный комплекс для исследования технологических процессов электроспекания // Электронное моделирование.- 1992.- N4.- С.75-79.

3. Васильев В.В., Баранов В.Л., Тонкаль Е.В. Метод решения вариационных задач при их моделировании на решетчатом интеграторе

// Электронное моделирование.- 1987.- N5.-С.31-35.

4. Тонкаль Е.В. Организация параллельных вычислений для решения задачи о максимальном потоке // Распределенная обработка информации -1У: Тез. докл. Всесоюз. семинара 10 - 13 августа 1991.'-Горно-Алтайск, 1991. 0.31.

5. Тонкаль Е.В. Цифровой аналог для решения задач управления

оптимизации технологических процессов // Перспективы развития и применения средств ВТ для шдедирования и автоматизированного исследования : Тез. докл. Всесоюз. научно-технич. конф. 21 - 23 октября 1991. - Москва, 1991. С.

6. Федотов Н.В., Тонкаль Е.В. ВДровая модель сети для оптимизации взаимосвязанных штоков // Гнбридные вычислительные иа-ПИНЫ и кошшксы.- 1986.- Вып.12.- (770-73.

7. Федотов Н.В., Тонкаль Е.В. Цифровые иодела потоковых задач.- Киев, 1990.-26с.- ( Препр. /АН УССР. Ин-т проблэа шделированая в энергетике; & 90-31 ).

8. A.c. I4I87I0 СССР, ШШ С Об ? 15/20. Устройство программного управления / В.В.Васильев, И.А.Табушик, Е.В.Тошсаль я др. -Опубл. 1988, БИ Н 31.

4

9. A.c. 1474667 СССР, ШШ G 05 ? 15/20. Устройство для анализа параметров сети / В.В.Васильев, И.А.Табунщик, Е.В.Тонкаль, Н.В.Федотов. - Опубл. 1989, БИ Н 15.

4

10. A.c. 1606452 СССР, ОДСИ G 05 F 15/20. Устройство для моделирования сетей / И.А.Табунщик, Е.В.Тонкаль, Н.В.Федотов.-Опубл. Х989, Ш Н 33.

4

11. A.c. 1506451 СССР, ШШ G Об Р 15/20. Устройство для анализа параметров сета / В.В.Васильев, и.А.Табунщик, Е.в.Тонкаль, Н.В.Федотов. - Опубл. I9S9, БИ Н 33.

4

12. A.c. 1587633 ССОР, НКй G Об 1 15/20. Устройство для анализа парамотров соте / В.В.Васильев, И.А.Табунщик, Е.в.Тонкаль, Н.В.вэдотов. - Опубл. 1990, БИ Н 31.

13. А,с. 1709347 СССР, МНИ G Об Р 15/20. Устройство для анализа параметров сети / А.А.Мирошниченко. и.А.Табунщик, Е.в.Тонкаль Н.В.ФЭД0Т0В. - Опубл. 19», БИ N 4.

14. A.c. I78I67I СССР, МКИ G Об F 15/20. Устройство программного управления / А.А.Мирошниченко, И.А.Табунщик, Е.в.Тонкаль, . Н.В.Федотов. * Опубл. 1992, БИ Н 46. ^