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

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

КУРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

; г л п На правах рукописи

• ' b 0/1

1S ¡m ш

ЗОТОВ Игорь Валерьевич

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

Специальность 05.13.05 "Элементы и устройства вычислительной техники и систем управления"

Автореферат диссертации на соискание ученой степени кандидата технических наук

Курск, 1998

Работа выполнена в Курском государственном техническом университете на кафедре вычислительной техники

Научные руководители: академик МАН ВШ, доктор технических наук, профессор ТИТОВ B.C. кандидат технических наук, доцент КОЛОСКОВ В. А.

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

ПЕРЕДЕЛЬСКИЙ Г. И. кандидат технических наук, доцент СУСИН В. Н.

Ведущее предприятие — в/ч 25714

Защита диссертации состоится "2Я 1998 г. в_часов

на заседании специализированного совета Д.064.50.02 при Курском государственном техническом университете (305039, г. Курск, ул. 50 лет Октября, 94, конференц-зал).

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

Отзывы на автореферат в двух экземплярах, заверенные печатью, просьба направлять по адресу: 305039, г. Курск, ул. 50 лет Октября, 94, ученому секретарю специализированного совета Д.064.50.02.

Автореферат разослан "М." М.&&. 1998 г.

Ученый секретарь к.т.н., доцент

В.М.Довгаль

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

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

Повышение сложности объектов логического управления, распарал-ливаннс управляющих Процессов выдвигают шпрокьй спектр качествен-| новых требований к УЛУ, в число которых входят наличие возможности [ератипноп перенастройки, обеспечение оперативной отказоустойчивости высокой живучести. Сказанное обусловливает невозможность построения 1сокоэффектнвных УЛУ только на основе традиционных архитектурных шеннй и элементной базы и вызывает необходимость поиска принцнпн-ьно новых способов реализации УЛУ.

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

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

Работа выполнена в соответствии с программой П.Т.614 "Много-юцсссорныс ЭВМ с параллельной структурой и системы виртуальной рс-H.HOCIH", приказ министерства общего и профессионального образования (572 от 2.03.98г.

Hc.ih работы заключается в создании комплех а аппаратных и алго-

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

Основными задачам диссертационной работы являются:

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

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

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

4. Теоретическое исследование вопроса оптимального размещени комплексных алгоритмов управления в МКС, создание метода и алгоритм субоптимального размещения сетей компонентных алгоритмов в микре контроллерных сетях с кольцевой организацией.

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

Основные научные положения, разработанные лично соискателе* и их новизна.

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

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

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

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

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

ые микроконтроллеры могут быть использованы при создании распреде-енных контроллеров тин и обработчиков прерывании в МПС. а МКС на х основе могут найги применение в качестве локальных контроллеров в эставе многоуровневых АСУ ТП. Предложенные в работе алгоритмы могут гать эффективной основой для создания средств автоматизации логико-опологического проектирования УЛУ.

В ходе выполнения диссертационной работы:

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

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

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

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

996 г.), па Всероссийской научно-технической конференции 'Электроника информатика — 97" (г. Зеленоград. 1997 г.). на 23-й Всероссийской моло-

ежной научной конференции "Гагаринские чтения" (г. Москва. 1997 г.), на >серосспйской научно-технической конференции "Современные проблемы парочной науки и техники" (г.Воронеж. 1997г.). на 3-й научно-техни-сской конференции "Вибрационные машины и технологии" (г. Курск.

997 г.). на 5-н научно-технической конференции "Упрочняющие матгчиа-ы и технологии" (г. Курск, 1997 г.).

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

Объем и структура работы. Диссертационная работ и состоит из вве-ення. чс1ырсх пит. заключения, списка литературы и приложений. Работа одержи г 144 страницы текста и поясняется 37 рисунками; список литера-уры включает 82 наименования: 5 приложений содержат 81 страницу.

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

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

В первой главе рассматриваются особенности организации мулы мнкроконтроллерных УЛУ, структура средств реализации параллелью алгоритмов в МКС, проводится анализ известных моделей межмикрокс троллерного взаимодействия, а также методов размещения сложных ал1 ритмов в мультимикропрограммных устройствах управления и даст обоснование необходимости их совершенствования.

Концептуальной основой мультнмикроконтроллерного УЛУ являет модель сосредоточенного управляющего коллектива вычислителей.

Базовой подсистемой УЛУ является сеть микроконтроллеров (МК< каждый модуль (микроконтроллер) которой представляется композита функционального (ФЭ) и коммуникационного (КЭ) элементов. Каждый С включает блок микропрограммного управления (БМУ), а также блок фу| цнонального расширения (БФР), реализующий функции, необходимые п исполнении параллельных алгоритмов. КЭ, объединенные в коммуникш онную сеть (КС), используются для организации межмодульного взаин действия. Модули МКС подключаются к объектам управления (ОУ) с i мощью устройств сопряжения и сети связи. Настройка, запуск и остаи УЛУ осуществляется устройством управления верхнего уровня (УУВУ).

Работа УЛУ начинается с момента поступления кода операции УУВУ и заключается в циклическом выполнении последовательных и i раллельных ветвей (участков) алгоритма, распределенных между мик] контроллерами (МК). При исполнении алгоритма микроконтроллеры i рабатывают последовательности сигналов, воздействующих на испол! тельные органы ОУ и инициирующих требуемые микрооперации (МО), г этом направление развития управляющих процессов в точках ветвления ал ритма определяется значениями сигналов логических условий (ЛУ), выра тываемых ОУ »raí отражающих результаты операций, производимых УУВ}

Основу для эффективной реализации алгоритмов управления в MI составляют аппаратные средства, а также методико-алгоритмичсскне ср ства оптимального распределения вершин алгоритмов между МК. Оси* аппаратных средств в силу алгоритмически распределенной организаг МКС составляют средства межмодульного взаимодействия, представл ные коммуникационным уровнем (совокупность КЭ и КС), а также урог.1 функционального расширения (совокупность БФР). в рамках которого i делаются средства организации межмодульных передач управления и с хроиизацин параллельных процессов. Средства первого уровня яиляю традиционными для устройств на основе модели коллектива вычислшс.

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

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

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

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

Модель передачи управления для полносвяшой МКС предусматривает обмен одноразрядными признаками инициализации. Адреса приема управления {Л,'| определяются номером реализуемого алгоритма л и порядковым номером обращения я к МК т, от МК тк, к = к , т.е. номером посгуиишпего признака/Логическая характеристика модели им ее г вид:

4 = У,И К.[и.....> = 1\!. =

где £),— множество адресов приема управления /-го МК: — ко;и чество обращении к /-му МК при реализации 5-го алгоритма. Модель обе печивает возможность повышения наращиваемости МКС и без снижен! гибкости позволяет строить сети, содержащие N-1(1-НЮ МК, что на пор док превосходит показатель, характерный для традиционных моделей.

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

приема управления {А',) сдаются совокупностью функций самонастрой! МКС {я;}, определенных на множестве порядковых номеров реализуем! участков.

Процедурные особенности модели состоят в следующем. При перед че управления подмножеству МК микроконтроллер формирует приза вида (И'Цп)шКиУ#АА^{п), где А4?(п)— код коррекции адреса прне> управления, определяемый значениями ЛУ, проверяемых А>м МК: п — н мер процесса передачи управления; #— символ конкатенации. Призн передается через шину МКС и сравнивается с признаками участк

МК ] = Если Я*(и) = Р/Сд,), то МК »^приступает к выпе

нению <7,-го участка с адреса Л4*(п)+/1/(7у), иначе состояние у-го V остается неизменным.

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

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

лнзующнх участки - {£{}, сходящиеся в вершине синхронизации аг т делкетса "ведущий" МК ; остальные МК получают статус "ведомый".

словие синхронизации пар;ш!ельных участков {/.{} имеет вид к

где у(Ц.()= МБ(ти .а,) V (Л/5(т(1 .а,.0). АЩт^.а,) — прнз-

1К стагуса модуля я» по отношению к вершине синхронизации а/.

./5(от,1,а/)=/, если модуль т^ — ведущий; ЛС(тч ,а; )=0, если модуль

^ — ведомый: — индикаторная функция участка Ц,: А(Ц,1)=1,

:ли участок в момент времени г завершен; А([/к,1)=0 иначе (моме!Ст ^ответствует началу процедуры синхронизации).

Процедурные особенности модели состоят в следующем. Модули 1КС после окончания соответствующих участков переходят в пассивное .»стояние, при этом ведущий МК да выдает на шину .ИКС идентификатор срншны синхронизации «у. Последний поступает на входы всех МК и пре-бразуекя в пришаки состояния. Признак состояния <тр(1) МК тр. р=!,М, бразуегся согласно следующему правилу: а-р(1)=у(1.'к./). если треМг где !к — параллельный участок. реализуемый МК тр, ор(1)=!, если тр€Мг [ризнаки состояния передаются на линию состояния и формируют обоб-(енный признак 7.^1) как результат операции "схемное И" над сигналами

г,,0). Р= 1.М ■ При /Г,(/)=0 ведущий МК да освобождает шину МКС и ере 1 промежуток времени Л инициирует повторный цикл опроса состоя-ия участков {/.(}. Как только признак + гЛ) (г— число циклов

проса) принимает единичное значение, микроконтроллер да воюбновля-

твыполнение алгоритма.

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

:холишкхся в вершине а) (количество ожидаемых событий). Число //Ц) акрепляегся за МК т1(, для которого Л/5(т1(,а7)=/. Логическая хараете-(истика модели имеет вид

Процедурные особенности модели состоят в с..едующем. Каждый МК я е Л/у независимо от стагуса по отношению к вершине а) при завершении

чютветствуюшего участка (А(/.{,/)>(!) вырабатывает команду— квитан-

цию К(т^), содержащую идентификатор вершины а) — /Ц). Квитанци

последовательно передаются ведущему МК. Последний подсчитывает чш ло поступивших квитанций и модифицирует текущее значение условия сш хронизации /}(а;), последовательно уменьшая его на единицу (исходнс значение = гу))- Параллельные участки считаются завершенным при £'(а,) = /}(ау)-/=0.

Синхронизация параллельных процессов в МКС с кольцевой стру| турой осуществляется на основе многократной ретрансляции микрокома! ды, содержащей число ожидаемых событий рЦ). и модификации этог числа транзитными МК по мере окончания закрепленных за ними пара, лельных участков. Логическая характеристика модели имеет вид:

Процедурные особенности модели состоят в следующем. МК т^ е М А45(т(1 после выполнения участка Ь[ вырабатывает микрокомащ

опроса где /Ц)— идентификатор вершины а/,

— символ конкатенации. Микрокоманда передается по кольцу и пос обработки всеми модулями треМ, р*1к, возвращается на вход ведуше МК. Поскольку одна и та же микрокоманда А'Ц) может многократно тра слироваться через одни и те же МК, каждому микроконтроллеру присва ваегся флаг/(а,), устанавливаемый в единичное состояние после обработ] микрокоманды А'Ц). Обработка микрокоманды А'Ц) модулем /и,, ^е {0,1 ....N-1}, определяется следующим алгоритмом.

1. Если то МК т, игнорирует микрокоманду, передавая ее сг дующему (смежному) модулю тз., л' = (л + 1)тос1 N.

2. Если /и,еЛ/>. то в зависимости от состояния реализуемого модул участка ¿^. д = ), выполняется одно нз следующих действий:

2.1. При модуль опрашивает состояние флагаДсф н:

2.1.1. ЕслиЛа;)=°- устанавливает 7.-=Хр].и передает мнкг команду А'Ц) модулю тг..

2.1.2. Еслн/Ц)=/ (в этом случае ш, ранее уже производил моднфш цию поля 2^), то микрокоманда А'Ц) без изменений передается МК тл..

2.2. При обработка осуществляется аналогично л.1. Участки считаются завершенными, если после появления мик] команды А'Ц) на входе МК т^ Т.^0. Иначе микрокоманда повторно об] батывается модулями г.^ с А/у, длз которых у(Ц,1') < /, здесь /,' — мом;

кончання предыдущего цикла обработки микрокоманды А'Ц).

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

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

Алгоритм (комплекс алгоритмов) управления, реализуемый МКС, редставляется в виде (объединенной) параллельной граф-схемы (ПарГСА) ; с множеством вершин A=\a&a¡,a2.....an-2.a¡^% множеством дуг í'c.lx.l, а »кже множествами ЛУ X={xt.x?....}, МО >'= jV/.ís.... ¡. микрокоманд D={Y¡. Yyp ), Y/qY, t = I.Qp , удовлетворяющей требованиям

езопасности, живости и устойчивости. Предполагается, что ПарГСА С не эдержит "пустых" ветвей и циклически замыкающих дуг и является иерар-ической с точки зрения вложенности условных ветвлений. На множестве ершин А ПарГСА G определены следующие бинарные отношения: )следованне (ij: = ).....(atf czU; 2) связь

р): ат<раясэ(ая='ап)\/(ат\'ая)у(аяуат). <fZD\^U\ 3) альтернатива , Щ » 3ареА (о,ш;)л(а;№;): ЧЦага,)*{(ap,ah );(ак/,ик;).....,а,)) =

iap• "к..,.a,}cA. Цага)= {(аp.at¡).(at¡,o,,).....(a,,;,a¡)}s

{ap,alrah.....al{ гау}сА, L(ap.a¡)r\L(ap.aJ)\{Op} =0; ^параллель-

ость («): a/üeij <z>\(ulifuj), (Ш№(|Л№0, где A¥cA — множество

словных вершин, ~\ — операция логического отрицания.

Задача разбиения ПарГСА на подалгорнтмы формулируется следующим образом. Получить разбиение множества вершин ПарГСА G Sep(A)=

н

{А^А^.^.А/,}. удовлетворяющее условию ((J4» = Д Л54®. =\0)л

k-i _

.(1(а,<да,) \/ак.а, бAh,k*lMW(Ah)ZW.\X(A;^niy , h, f = J~H ,h *f), де И'(Л-,), X(Ah) — число микрокоманд и множество ЛУ подалгорнтма Ah; . V— емкость памяти микропрограмм микроконтроллера; плу— число вы-одов на корпусе СБИС МК, используемых для приема сигналов логиче-кнх условий от ОУ, и обращающее в минимум функционал <XSep{A))=K,H+K¿.\K¿r+K£>,

где Z , Z" — соответственно сложность cení межблочных связей и уммарное число межблочных взаимодействий, порождаемые разбиением >ср(А); Z' — степень различия подалгорнтмов по сложности; К,, /=1,2.3,4 — :оэффицнснты значимости.

Идея предложенного метода разбиения заключается в носледователь-юм nq>e6ope групп попарно несвязанных вершин и их псездооднозремен-юм распределении п формируемых подалгор:гп.!ах.

Основу метода составляют следующие определения.

Определение 1. Сечением алгоритма называется всякое подмножество 1)с./ удов.тст норяющее условию

[( Л = /) V (Чак.а,с О, к *1:\ик<ри,))]л[Чат1 П За^еП: ат<р«ч\. Определение 2. Под го-мощностью сечения П, понимасгся максималыи число попарно параллельных вершин образующих Определение 3. Сечение С1т называется максимальным, если V/?, еУ1 ,(*п П,"' < Пт"', где !)? — семейство всевозможных сечений алг оритма. Онреоелеиие 4. Сечения Ц„ и /?„, т*п, считаются смежными {Ц„м\)П„), еслг

при лом Оп, напивается «-сечением а Ц, — (/-сечением (

Сущносп. метода состоит в следующем. Первоначально формируем одно И! максимальных сечений Ц„. коюрому присваинаск'я статус бают го сечения. Далее выполняется последовательный перебор смежных сечет ллгоршма, начиная с базового, и для вершин каждою из них онределяеп оптимальное размещение в \ОтГ блоках с учетом способа распределен! ранее рассмотренных вершин.

Для формирования базового сечения используется конструктивный / алгоритм, обеспечивающий сведение исходного алгоритма к гшклег ческому алгоршму, содержащему единственное максимальное сечение, п тем но! лощения групп попарно параллельных вершин исходя из соотнош ния их "¿мощностей. Для формализации поиска базоно! о сечения исходш ПарГСЛ ставится в соответствие система выражений вп,

.V - (г.-» /К), где К).- множества соответственно першкн-нрсдшсс кснникои и исршпн-нослсдошпслсн такие, что

/<;.(«,.«„ «ие /íЛA[V,/„G П\.(ак .ат )еГ/=> ик с КЦ

определяемые в следующей конструктивно!! форме

. к) = к, )•...•< я;.

я' = [а,.....а,, • Сл^Ля^Ь ..I/»;, V/, >... . ,

* — — \шар* где V, (£ - 1,И,1 - 1,рж) 10,федсяястся в форме, аналогичной Н\\

■ , о V

—— ____ |Б/7

г',* (к = 1.г,1 = 1,У„)\ г . • ,у р* — предик

1 * [определяется в форме, аналогичной К2.

условия перехода от вершин к вершинам ; и " 1" — констр} тивные разделители*, отображающие отношения го и ^у соответственно.

В основе Я-алгоритма лежат следующие формальные правила. 1равило и-поглощения.

Если 35,,5, е =\/ * к: Д,*^]/^,^ е Я2 ,|я/|" > .

то л 5," =(/:/?; ->[Л:\/?,1]> Як:).

де [с] — отношение нестрогого конструктивного включения (обладающее войствами отношения с, но определяемое с учетом иерархии скобочных гонструкции): "<-" — оператор присваивания; ">" интерпретируется как V , если имеет место Я/ »(Я, \ /?/), и как "|",если Я* [(Я', \ /?*). 7равило (/-поглощения.

Если 35, е £,г*к: Я;[с]Я/ ,а0 е/?;,|л;|"'

то =- =(*:[/?;\я>

1 ранило у-перегруппировки.

Если 35,,е.Е\/' * к: Я,4 с Я^ и Я'2 содержит конструктивное

юдмножество Я;, представимое в виде Я о{[аЧ''\...\а"']»...»[а™"\...\а"'']), де атр' с А, р=/.<7, тг=т„тя, причем Я' = а? . .»а"",

го .Г «-[^Ч^М^,}, где 5, =(/:Я;Яо[я;!Л"]).

я-= е{/......

гели (Я}\Я'2)• я;. -1если (Я^\Я^. Я-алгоритм включает следующие шаги.

1. Выбрать произвольные выражения 5/.54е£'. удовлетворяющие условию действия правила .те{н-поглошенне, ¿/-поглощение, ^перегруппировка}.

2. Преобразовать систему выражении £"в систему ¿Г по правилу я. х Положить Эз£~ и перейти к п.1.

13 результате сыполнення Я-алгоритма образуется система выражений £"' = {5';=(/:я0-+Я/), описывающая гипотетический алгоритм

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

Перебор смежных сечений сводится к последовательному построению !/- м ¿/-сечений для ранее полученных сечений и (/?" ^ П* а /?„). Переход от сечения к /2* (от к /?/) осуществляется путем выделения подмножества выражений Л= {5/(.....5, } с таких, что

п'/пП"., я 0. Ь=~П\> (л-={5,(.....) с таких, что /?'' пЛ?., *0,

X = /,/;), и реализации подстановки ендз

О" =

(л;'=

н

а

: R"':...: R7"

H,' : ... : я/« где R'2'[çzh=¡,¡> (/ii'[ç|/2;'(, я = правые части ш

ра женин (Л'^б/г); ÎO = /<? п/7/.,,S^eA.q = Ui (R"' = R'¡' n/7/.

Ра змещение вершин сечений Л" (£?/) в блоках прои зводи гея на осн ве построения таблиц, строкам и столбцам которых сопоставляются ма симальные по включению подмножества попарно непараллельных верни />/./ь.....i>,tcíJ'¡ о Л/ {iï'п, А/), 1де Д/c.-í — подмножество вершин, i

включенных ни в один иэ блоков разбиения. 5 = , и формируем!

блоки At¡.....Aj{. Элементы таблиц определяются следующим обра юм:

ocrai 3«терк,а„еАи: amaxi„, V, если (\/<i„ ерк.а„ сАч: 1(</тл*/„))л

л((1Г( Ач ) +■ 1Г( А ) > И') v(|.V( Л'(рк )| > n¡v )). О, если (Ví/ra epk,<in еА,: 1(«тол1„))л(рк ^Ф),

-Л'/|Л'(Л )\Х{А„ )¡-tKfM'(pk,Alt ) + К/:М:(рк.Ли ) + +К„ АН'(рк, A¡f )J в противном случае;

ША, ) - min{IV(A, )}, если W(pk ) > О,

I ' m--l.i

[о, если 1У(рк) = 0

hAHUW. <V(A)=U'V(aJ. ^'(PaA

«•«л ' © "««<'»

¿1Z' .,1, ) — приращения сложности сети межблочных связей и числа мс

блочных взаимодействий. порождаемые включением /\ в блок Ли ; Ф mi

жcciво фиктивных вершин: А.',1 ,К] ,К,Х ,K¡ , К„ ,K¡— коэффициенты.

Ныоор оптимальною распределения подмножеств в б.кн

ii¡u>ii ич>ди1С)1 iiy.icM последовшельпою выделения в строках таблиц м;

Kíh.A,)-

где AW(pk,A ) = •

(Л с/1

имальных элементов {/(¿>t,4; )*"-","+"}. Для устранения возможных кон-щиктов между подмножествами используется дополнительный критерий ^(Р*. А, ) = t(pk.Ah)- max{t{pk,Aim ) -> max.

При обработке алгоритмов управления с циклическими фрагментами сходная граф-схема G сводится к ПарГСА 6'\ где каждому циклическому >рагменту Си соответствует гипотетическое альтернативное ветвление С*.

еорема. ПарГСА G* является ¿»-эквивалентом исходной ПарГСА G. 1а основании теоремы отношение параллельности инвариантно относи-ельно преобразования G-*G\ Таким образом, задача разбиения алгорит-ia управления, заданного граф-схемой G, может быть сведена к разбиению 1арГСА G*. что упрощает решение исходной задачи для алгоритмов правления, содержащих циклические фрагменты.

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

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

МКС описывается топологической моделью в-виде простого контура ~(/=<Л/,£>, где M={ntl>mi....,mx-i} — множество МК; Е^Л/хЛ/ — множе-тво межмикроконтроллерных связей, причем (mhm^E<^j={i+l) mod N. Алгоритм (комплекс алгоритмов) управления представляется в влде множества подалгорнтмов (полученных на этапе разбиения), связи между кото-1ымн описываются графом межблочных взаимодействий Г=<ГА,ГЬ>. Граф " считается ориентированным: наличие дуги (AiPAj)sи у означает, что подалгоритмы А) и Aj связаны по управлению, при этом Л, является ннициа-ором взаимодействия. Каждой дуге г/у ставится в соответствие ннтененв-юсть взаимодействия иу. Все подалгоритмы считаются последовательны-. ш, при этом VAj.Ajer,. tej: {3apeAi.aqeAj: afcca4)vQVl + ]Vl > IF), где Ifi —

уммарное число микрокоманд подалгорнтма AK7li=T.j.

Поскольку различные подалгоритмы не могут назначаться на один шкрокошроллер, размещение множества подхтгоритмов (графа Г) в МКС задастся в виде биекцни /?. Г, -> ,\t. Задача размещения сети алгорит-юп в МКС представляется как поиск биекцни /2, обращающей в минимум функционал, определенный на множествебнекцнй Гд -» Л/},

ф(п')=к,( zWoWu,))^)^*Kjz^Tf-

^Al..^1нrv . J* г -1 Р.Ц--0 .N

Р'Я

де L(mr'>ij) ' расстояние между ;'-м и j-м МК, /нАзЛ(Л,); Лип — пнтспсип-

юсть взанмодейстии.ч МК тр с тг соответствующие размещению /?; v'/.A'.! — коэффициенты значимости.

Идея предложенного метода размещения заключается в сведении гр фа Г к графу (7/■=</',. Гг>. изоморфному топологической модели МКС Г I ipouecc сведения представляется в виде последовательности итерации, » каждой из которых осуществляется выбор и фиксация пары смежных вс] шин (душ) текущею графа Г = Г в смежных вершинах модели Ги. Определение 5. Дуга и,^(А,,Ау)еГ, ■ считается фиксированной, если усташ влено взаимно-однозначное соответсгвие г с областью определения {А,.А и обласгыо прибытия Л/ такое, что Цт(А,), ^Ау))=/.

Определение 6. Пусть г — некоторое взаимно-однозначное соответствие областью определения \A,,Aj\ и областью прибытия Л/, причем муеГ( 1.(т {A,),T(Aj))=ti,j>l. Тогда величина нашвается коэффициентом дефо мании, а величина л"(/=<$/»'(/ коэффициентом размещения дуги иц.

Фиксация дут и и„ с необходпмоегью приводит к невозможное! и фи сап'пп ли чп !лкн\. чю (/)-/)/(<///)у((/=/')а(/>?•-/), по>тому текущий граф после каждой терапии подпер!асгся преобразованию ¿1/(ну). в резулыа которого душ uN замешаются путями (и,гим) (или {ир,.ич))\ коэффициент деформации этих д\1 получают единичное приращение.

Критерии выбора фиксируемых дуг включает понятия А- и /-ра ложения граф;» относительно дуги в топологической модели МКС.

Определение 7. Пусть ну— дуга |рафа /'. ц- \ч,г,,.....• "г,,! •

и,,.....и, J — максимальные по включению пути такие, что Vi/^e«^

¡'г- ссли 4] * ^

и,., е. U , И — множество фиксированных дут ; к'= {

[/. ccjui = С

[/;. если с/ ? О, | I. если = 0;

л(/;/■/)}. Под ¿-разложением графа /'отиосшельно дуги ич понимается см соб размещения дуг i/(J/,e/''и/' it топологической модели ГХ1. который и рождает минимальное приращение коэффициентов чх деформации. Определение К /-разложением графа /'относительно душ i/,y называется i потстичсский способ размещения дуг, входящих в простые контуры длин p<N. содержащие дугу которым порождает минимальное приращен! коэффициентов размещения этих дуг.

Выбор дуги Ujj сЯтгастся наиболее целесообразным, если она нмо |1анбол!>11шй вес и ее фиксация обусловливает минимальное прирашеш козффициентов Л- и /-разложения.

Предложенный метол позволяет иопысить качество получаемых р шеннй. Поданным проведенных статистических исследовании средняя ст псш. улаленност решений от глобального оптимума составляет 13%, Ч1 на 5-15 ' о ниже традиционного показателя.

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

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

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

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

При решении поставленной задачи в диссертационной работе полу-:ны следующие результаты:

1. Разработан комплекс логико-процедурных моделей н технических зедств синхронизации параллельных процессов для МКС с шинной, коль-евой и матричной структурой, позволяющих расширить функциональные эзможности и область применення УЛУ;

2. Предложены модели и технические средства межмодульной переда-и управления для МКС с шинной и полносвязной структурой, обеспечи-дющие повышение быстродействия УЛУ и оперативности управления, а жже минимизацию конструктивной сложности межмодульного интерфейс 1 и увеличение предельной наращиваемости размерности устройства;

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

4. Предложен Я1етод субоптнмального размещения сетей компонент-ых ;шгоритмов в МКС с кольцевой структурой, отличающийся от из--естных подходов применением процедур гипотетической оценки качества окальных вариантов размещения и обеспечивающий более высокое каче-гво решений при невысокой трудоемкости их получения;

5. На основе предложенных методов созданы алгоритмы субоптн-1ального разбиения и размещения алгоритмов управления в МКС, обла-ающие полиномиальной временной сложчюстью;

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

соответствующим актом. Кроме того, результаты диссертационной работь были внедрены в учебный процесс в КГТУ.

Основные положения диссертации отражены в следующих работах:

1. Функционально-топологическая организация микропрог раммны мулы ^микроконтроллеров группового логического управления / Зотов П. 13. i др.; Гул. гос. ун-т, Тула, 1997. — 226 с.

2. Зотов И.В., Колосков В.Л., Титов B.C. Выбор оптимальны разбиений алгоритмов при проектировании микроконтроллерных сетей ; Автоматика и вычислительная техника. — 1997. — №5. — С. 51-62.

З.Зотов И.В., Колосков В.А. Синхронизация параллельных пронес сов в мпкроконтроллерных сетях // Известия Тульск. гос. ун-та, Том 1 "Вычислительная техника, автоматика, управление". Вып.!.— Тутш 1997. С. 33-36.

4. Ihiob B.C., Колосков В.А., Зотов П.В. Модель вкшмодействи управляющих процессов в мпкроконтроллерных сетях с шинной структур ной opiанизацней // Методы и средства систем обработки ннформацш Сборник научных статей. - КП'У. Курск, 1997. - С. 55-58.

5. Зотов И.В., Колосков В.А., Гитов B.C. Псендопараллсльный мето. декомпозиции параллельных алгоритмов лог ическою управления. -Курск, 1996. — 22 с. — Дсп. в ВИНИТИ 17.07.96; №2438-В9б!

6. Зотов И.В.. Колосков В.А., Титов B.C. Метод размещения алге ршмоп ;ю1 ического управления в мпкроконтроллерных сетях с кольцево структурой. • Курск! 1997. —26с. - Дсп. в ВИНИТИ 14.05.97;№ I599-B97

7. Зою» И.В.. Колосков В.А., Титов B.C. Псевдопараллельный сник разбиений алшрщмов в задачах проектирования in-рсгулярных унр; плякчцих cipyKiyp / II международная конференция "Новые ннформанпо! ныетехнологии п системы". Сборник материалов. Пенза, 1ПТУ, 1996. 4.1.;- С. 82-84.

8. Зотов И.В.. Колосков В.А., Титов B.C. Организация средств сш хронизацин параллельных процессов в мпкроконтроллерных се1ях / 2-Всероссийская научно-техническая конференция с международным уч;и тнем "Электроника и информатика — 97". Тезисы докладов.— Москв ■(Зеленоград). 1997. — 4.2.-е. 33.

9. Зотов И.В. Логико-процедурная модель межмодульного взаимс действия в мнкроконт{&ллсрных сетях с шинной структурой // 23-я Bccpoi спйская молодежная научная конференция "Гагариискис чтения". Тезис докладов.'— М., 1997. — Ч.З. — с. 28.

.Ю.Зотов И.В.. Колосков В.А., Титов B.C. Аппарашо-ориенпфс ванная модель синхронизации параллельных процессов и мнкроконфо: .u'piii.ix сеич с шинной стр\ктурой / Pnccitittкля научно-техническая koiii|h

нция "Современные проблемы сварочной науки и техники "Сварка-97". ¡орннк материалов. — Воронеж, 1997. — С. 95-96.

П.Зотов И.В., Колосков В \„ Титов B.C. Функционально-логи-:кая модель распределенных средств синхронизации параллельных про-:сов в микроконтроллерных сетях с кольцевой структурой / 3-я междуна-дная научно-техническая конференция "Вибрационные машины и техно-гии". Сборник научных докладов. — КГТУ, Курск, 1997. — С. 243-245.

12. Зотов И.В., Колосков В.А., Титов B.C. Минимизация конструк-вной сложности межмодульного интерфейса в микроконтроллерных се-t с полносвязной организацией // 5-я научно-техническая конференция с ждународным участием "Материалы и упрочняющие технологии — 97". зисы и материалы докладов. — Курск, 1997. — С. 206-208.

13. Зотов И.В., Колосков В.А., Титов B.C. Дискретная микрокон-эллерная сеть / Патент №2110827 Россия, кл. G 05 В 19/18, G 06 F 9/28, J8, БИ №13.

14. Зотов И.В., Колосков В.А., Титов B.C. Микропрограммное гройство управления / Патент №2111528 Россия, кл. G 06 F 9/22, 1998, I №14.

15. Зотов И.В., Колосков В.А., Титов B.C. Модуль мнкроконтроллер-й сети / Патент №2112272 Россия, кл. G 06 F 9/22, 9/28, 1998, БИ №15.

16. Зотов И.В., Колосков В.А., Титов B.C. Модульное устройство для ограммного управления / Патент №2112269 Россия, кл. G 05 В 19/18, >8,БИ№15.

17. Зотов И.В., Колосков В.А.. Титов B.C. Модуль мультимнкропро-1ммной системы/ Решение о выдаче патента по заявке №97102631,

G 06 F 9/22, от 5.01.98.

искатель

Зотов И.В.

Подписано к печати ЛУ^ПР . Формат 60x84 1/16. Печатных листов /.л . Тираж 100 экз. Заказ Sf .

Курский государственный технический уннвераггет. 305039, г. Курск, ул. 50 лет Октябре, 94.