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

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

Ватутин Эдуард Игоревич

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

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

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

Курск - 2009

ии3472ЭВЗ

003472863

Работа выполнена в ГОУ ВПО «Курский государственный технический университет: кафедре вычислительной техники в совместной научно-исследовательской лаборатор; Центра информационных технологий в проектировании РАН и Курского государстве ного технического университета: «Информационные распознающие телекоммуннкац онные интеллектуальные системы».

Научный руководитель:

доктор технических наук, профессор, заслуженный деятель наук РФ Титов Виталий Семенович

Официальные оппоненты.

доктор технических наук, профессор Бурмака Александр Александрович

кандидат технических наук Беляев Юрий Валентинович

Ведущая организация:

Белгородский государственный техночс гический университет им. ВТ. Шухове

Защита состоится 25 июня 2009 г. в 14-00 часов в конференц-зале на заседании согтта i защите докторских и кандидатских диссертаций Д 212.105.02 при ГОУ ВПО «Курск; государственный технический университет» по адресу: 305040, г. Курск, ул. 50 л. Октября, 94.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Курский государств ный технический университет» по адресу: г. Курск, ул. 50 лет Октября, 94.

Автореферат разослан 23 мая 2009 г.

Ученый секретарь совета по защите докторских и кандидатских диссертаций Д 212.105.02 _£ д Титенко

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

Актуальность работы. Системы логического управления (СЛУ) являются одним распространенных классов цифровых управляющих систем, проблемы анализа и син-за которых на протяжении многих лет остаются в центре внимания отечественных и рубежных ученых (С.И. Баранов, A.A. Баркалов, В.И. Варшавский, В.А. Горбатов, Д. Закревский, И.В. Зотов, В.Г. Лазарев, В.З. Магергут, Е.И. Пийль, E.H. Турута, С. Харченко, A.A. Шалыто, С.А. Юдицкий, Т. Agerwala, S. Husson, R. Puri и др.). Соименные СЛУ - параллельные многомодульные однородные системы, объединяющие тни и тысячи процессорных уалов. Как правило, это многофункциональные открытые [стемы, способные оперативно перестраиваться на новый алгоритм управления, выби-1емый из некоторого (часто заранее неизвестного) множества алгоритмов. Подобные тстемы могут выполнять комплексные управляющие алгоритмы теоретически неогра-«енной сложности при условии их предварительного разбиения (декомпозиции) на ча-ные алгоритмы (блоки), назначаемые на отдельные модули. При этом длительность эоцессов начальной настройки, отладки или последующей перенастройки системы, вы-злняемых обычно автоматизировано, во многом определяется временем поиска похо-ицего разбиения, сокращение которого ведет к повышению производительности труда увеличению коэффициента готовности СЛУ.

Разбиение параллельных алгоритмов осуществляется с учетом структурных и тех-элогических ограничений СЛУ, при этом выбор окончательного решения производится з ряду критериев качества (связность и интенсивность взаимодействия частных алго-ггмов, число избыточных частных алгоритмов, межблочное распределение микроопе-щий и логических условий), влияющих на основные функциональные характеристики [стемы (аппаратная сложность и производительность). Нахождение оптимального ре-ения задачи разбиения практически недостижимо для алгоритмов управления реальной южности (20 вершин и более) ввиду необходимости перебора и сопоставления очень хпьшого числа различных разбиений (ограниченного сверху числом Белла). В связи с им на практике распространены эвристические алгоритмы декомпозиции, обеспечи-нощие приближенное (субоптимальное) решение задачи за приемлемое время :.И. Баранов, A.A. Баркалов, В.А. Горбатов, B.C. Харченко). Однако известные эври-ические алгоритмы характеризуются низким качеством получаемых решений из-за по-¡едователыюго характера процедур обработки. Более высокое качество разбиений >еспечивает метод параллельно-последовательной декомпозиции (И.В. Зотов). В то же >емя он требует существенных затрат времени и памяти ЭВМ при программной реали-ции.

Потребность в построении разбиений высокого качества при ограниченных вре-гнных затратах на их получение приводит к необходимости переноса процедур обра->тки с программного уровня на аппаратный путем разработки специализированных тройств-акселераторов, жестко адаптированных к особенностям решаемой задачи. Из-стные устройства (В Л. Баранов, В.В. Васильев, А.Г. Додонов, В.В. Епихин, М. Глушань, В.А. Калашников, В.М. Курейчик, А.Н. Чаплиц, В.Н. Червяцов, И. Щербаков, В.И. Ян и др.) для решения схожих задач на графах характеризуются не->статочными функциональными возможностями или избыточной вычислительной ожностью.

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

Работа выполнена в рамках совместных НИР КурскГТУ и ОХП ОКБ «Авиаавт< матика» Курского ОАО «Прибор» (темы №1.121.03, №1.218.08П), а также в соответс вии с планом КНР Курского государственного технического университета по едином заказ-наряду Министерства образования РФ в 2003-2009 годах.

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

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

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

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

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

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

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

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

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

Научная новизна результатов работы заключается в следующем: 1. Сформулированы редукционные правила преобразования схем параллельных упра ляющих алгоритмов, основанные на представлении алгоритма, описанного системой J выражений, в виде дерева и позволяющие перенести оценку числовых характерней разбиений в процессе декомпозиции на аппаратный уровень. Выявлен и обоснован р) специфических свойств /^-выражений (не присущих графам и деревьям общего вид'

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

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

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

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

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

Практическая ценность результатов работы заключается в следующем: . Декомпозиция управляющих алгоритмов с использованием разработанных правил и роцедур позволяет получать разбиения более высокого качества с минимальным чис-ом блоков в 85-99% случаев, что обеспечивает создание более компактных (фактиче-ки, более дешевых) СЛУ с меньшей аппаратной сложностью (за счет уменьшения сред-его числа блоков до 13% и снижения сложности сети межблочных связей до 22%) и ольшим быстродействием (за счет снижения интенсивности межблочных взаимодейст-ий до 20%).

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

ние трудоемкости декомпозиции алгоритмов реальной размерности (более 1000 вершш в 2,7 раза, что весьма существенно при разработке или оперативной перенастройке СЛ ввиду повышения производительности труда и коэффициента готовности системы.

Реализация и внедрение. Результаты диссертационного исследования использую' ся в учебном процессе Курского государственного технического университета в рамка дисциплин «Программирование на языке высокого уровня», «Схемотехника ЭВМ) «Методы оптимизации», «Теория принятия решений», а также внедрены в ООО «Cai нер-Курск» (г. Курск) и ОАО «Прибор» (г. Курск), что подтверждается соответствуй щими актами.

Научные результаты, выносимые на защиту:

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

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

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

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

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

6. Зависимости степени приближения получаемых разбиений к оптимуму при испол зовании разработанных правил и процедур и известных методов декомпозиции от знач ний технологических ограничений и параметров обрабатываемых алгоритмов управл ния, демонстрирующие снижение среднего числа блоков разбиений до 13%, уменьшен! сложности сети межблочных связей до 22% и интенсивности межблочных взаимодейс вий до 20%. Оценки трудоемкости декомпозиции управляющих алгоритмов при пр граммной и аппаратной реализации.

Апробация работы. Основные положения диссертационной работы докладывали! и получили положительную оценку на региональных, российских и международнь конференциях: Параллельные вычисления и задачи управления «РАСО» (Москва, 200 2008); Information and Telecommunication Technologies in Intelligent Systems (Испаш 2004,-2005, 2007, Италия, 2006); Идентификация систем и задачи управления «SICPRr

(Москва, 2006,2008); Информационные технологии моделирования и управления (Воронеж, 2004); Интеллектуальные и информационные системы (Тула, 2004, 2005); Балтийская олимпиада по автоматическому управлению «ВОАС» (Санкт-Петербург, 2006, 2008); Информационно-математические технологии в экономике, технике и образовании (Екатеринбург, 2007); Образование, наука, производство (Белгород, 2004, 2006); Молодежь и XXI век (Курск, 2003, 2004, 2007, 2008); Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации «Распознавание - 2003» (Курск, 2003, 2005, 2008); Материалы и упрочняющие технологии (Курск, 2003); Современные инструментальные системы, информационные технологии и инновации (Курск, 2006); Перспективы развития систем управления оружием (Курск, 2007); а также на научных семинарах кафедры вычислительной техники Курск-ГТУ с 2003 по 2009 гг.

Публикации. По результатам диссертации опубликовано 39 печатных работ, среди которых 10 статей (из них 6 по перечню ВАК), 2 свидетельства о государственной регистрации программы для ЭВМ (№ 2005613091, № 2007613222) и 1 патент на изобретение (№ 2336556). Список основных публикаций приведен в конце автореферата.

Личный вклад автора. Все выносимые на защиту научные результаты получены соискателем лично. В работах по теме диссертации, опубликованных в соавторстве, лично соискателем выполнено следующее: в [1,7] сформулированы процедуры построения множества сечений параллельного алгоритма с использованием системы Л-выражений; в [3,8,9,12,13] разработаны процедуры модифицированной параллельно-последовательной декомпозиции; в [11,14] определены детали реализации алгоритмов вычисления значений критериев качества; в [15] предложена архитектура аппаратно-программного комплекса для автоматизированного построения разбиений и проведения вычислительных экспериментов; в [5,16,17,18,20,21] разработана методика проведения вычислительных экспериментов, а также проведено исследование экспериментальных результатов и влияния на них ряда модификаций методов декомпозиции; в [2,4,6,10,19] предложена схемотехническая реализация акселератора; в [22] синтезирован ряд коммутационных блоков, необходимых для аппаратной реализации процедур разбиения комплексных алгоритмов логического управления.

Объем и структура работы. Диссертационная работа состоит из введения, 4 глав, заключения, списка литературы из 128 источников и 1 приложения. Работа содержит 155 страниц основного текста, 64 рисунка и 16 таблиц.

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

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

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

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

Задача разбиения алгоритмов управления относится к классу Л7>-трудных, что н< позволяет находить ее оптимальное решение для управляющих алгоритмов реально} сложности (и = 1000 вершин и более) за приемлемое время. Оценка числа возможны) разбиений алгоритма с п вершинами, как известно, характеризуется числом Белла В„

(например, В20 & 5,17 • 1013). В связи с этим для решения задачи на практике используют ся эвристические методы разбиения.

По способу формирования решения выделяются последовательные методы разбиения (методы С.И. Баранова, А.Д. Закревского, В.Г. Лазарева, метод параллельно-последовательной декомпозиции И.В. Зотова), предусматривающие формирование един ственного решения с использованием ряда эвристик, и итерационные (метод случайной перебора, генетические алгоритмы, метод B.C. Харченко), подразумевающие перебо} вариантов решения и выбор наилучшего. Ряд этих методов ориентирован на разбиенш чисто последовательных алгоритмов управления, однако допускает простое расширен» на класс параллельных алгоритмов (метод С.И. Баранова). Некоторые из них предпола гают сведение задачи выбора разбиения к другим задачам (метод А.Д. Закревского - по иск минимальной раскраски графа). Наконец, известны методы, созданные для разбие ния параллельных алгоритмов управления с учетом их специфики (метод B.C. Харченкс метод параллельно-последовательной декомпозиции И.В. Зотова). Кроме того, имеете целый ряд задач, методы решения которых потенциально применимы при разбиени] управляющих алгоритмов. Это, например, задачи размещения элементов и трассировк: соединений при коммутационно-монтажном проектировании радиоэлектронной аппарг туры, проектирование топологии сетей Ethernet с максимизацией сетевого трафика в нут ри доменов коллизии и минимизацией между ними. Все эти задачи, в конечном счел также сводятся к разбиению графов на подграфы.

Для решения обозначенных выше задач на практике применяются эвристически алгоритмы, большинство из которых характеризуются асимптотической временно сложностью порядка <9(«2)-£?(я3). Однако даже полиномиальные алгоритмы, othoci

тельно быстро решающие небольшие (размерностью порядка п = 100 +1000) задачи, м( гут потребовать очень больших временных затрат при решении задач реальной разме| ности (трассировка межсоединений современных СБИС, насчитывающих до 2 млр, транзисторов, размещение функционально законченных фрагментов схем при их ПЛИС реализации, насчитывающих до 50 млн. вентилей и т.д.). В подобных случаях примеш мы два существенно различных подхода.

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

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

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

Таким образом, можно выделить целый ряд диктуемых практикой труднорешаемых адач. Возможно их точное решение (при малой размерности, п «10 + 15), приближен-юе решение с использованием универсальных, широко распространенных и относи-ельно дешевых вычислительных систем (при средней размерности, ««100 + 1000) или [риближенное решение с применением дорогих суперкомпьютеров или специализиро-анных акселераторов (задачи большой размерности, п «10000 и более).

Во второй главе дается формализованная постановка задачи разбиения параллель-[ых управляющих алгоритмов, приводится описание модифицированного метода парал-ельно-последовательной декомпозиции, выявляются и строго обосновываются специ-)ические свойства Я-выражений, позволяющие существенно снизить вычислительную ложность процедур декомпозиции, и формулируются аппаратные процедуры обработки f-выражений, представленных в виде деревьев, обеспечивающие возможность построе-:ия множества сечений алгоритма управления за полиномиальное время.

Опишем исходный алгоритм логического управления параллельной граф-схемой ПГарГСА) (В.И. Варшавский). ПарГСА Ga = {а°, V'3^ - взвешенный орграф с множест-

ом вершин А0 и множеством дуг У0. Вершинам ПарГСА ateAa, i = 1,/V припишем яд параметров: тип (начальная, конечная, операторная, условная, объединения альтер-ативных дуг, синхронизации), вес W (количество микрокоманд, занимаемых вершиной в памяти контроллера), множество микроопераций Y и логических условий X (B.C. Хар-ченко). В качестве параметров дуг v, е К0, / = 1, А/ выделим вероятность активации дуги а и среднее число передач управления 6 (И.В. Зотов). В дальнейшем ограничимся рас-

ю

смотрением подкласса параллельных граф-схем, удовлетворяющих свойствам безопасности, живости и устойчивости (С.И. Баранов, А.Д. Закревский).

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

/=1

е Ак, /^у, к = \,Н, |

где ш - символ отношения параллельности, при заданных технологических ограничениях базиса СЛУ на суммарный вес вершин блока ), общее число его логических условий (яду) и микроопераций (им0):

и4)|<"лу> \У(А)\<пмо, ¡=йн, где И7 (/),) = - суммарный вес вершин в составе /-го блока,

Х(4)= и -^(^у) - множество логических условий, входящих в вершины /-го блока,

У (Д) = ^(й,) - множество микроопераций /-го блока. При этом необходимо мини-

а,еА,

мизировать следующие критерии качества: число блоков 2„ = Н^Бер^А0^, сложность

н н

сети межблочных связей ^ ^ а(Ч>интенсивность межблочных взаимо-

(=1 ;=!,;»/

действий 2ъ = и степени дублирования логических условий

н н

2Х = и микроопераций 2У соответственно.

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

1. Произвести приведение исходной граф-схемы й" к ациклической граф-схеме С".

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

3. Ликвидировать «пустые» дуги граф-схемы С,л путем добавления в них фиктивных операторных вершин с целью получение граф-схемы С.

4. Построить матрицу отношений МК по граф-схеме <5.

5. Сформировать систему Л-выражений Е по граф-схеме <5.

6. Выделить базовое сечение Г2тах с использованием системы Е.

7. Построить множество смежных сечений К с использованием базового сечения и системы Е.

и

Сформировать скелетный граф С?5 по исходной граф-схеме С" . Получить искомое разбиение Бер^А0) с использованием всех построенных структур иных.

Основой метода является построение разбиения из множества сечений путем пре-5разования системы /^-выражений (конструктивных подмножеств вершин) Е с исполь-1ванием правил и- и ¿/-подстановки:

г.

у А*-+С"

=> г. Xя - Бй/,

хе А", В", В"', Ся, X" - некоторые Л-выражения, входящие в ее состав. При этом К-ьфажение задается в виде рекуррентного определения

(е «•» - обозначение отношения параллельности, а «] » - альтернативы.

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

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

31?, Щ, Ь^Щ А"Щв\

1е ¿;4 - 1-й набор листьев дерева А", (£, = ¿2) V(¿,, с 1г)у(Ьг с £,), [с] -

гношение /--изоморфизма деревьев (конструктивного включения ^-выражений), еобходимое условие 2 отсутствия г-изоморфизма:

»М-К^Ас^М^сД).

ледствие 1. ЗЦ,^, Ы у, и{ь^ = и{ьх^, где й(^) - функция, возвращающая эедка элемента дерева.

ледствие 2. ЧТ*, Т* = и(т*): /(^^/(г/), где Т? - /-Й узел дерева Xя, ¡(Т,*) -ш узла дерева.

емма 1. , Ь] : ¿f ПI] = 0, г * } ■

емма 2. 3е ^(а^.а, € =

еорема 1. : Ц[~Щ & ЗЬвк, Ц[~\Ьвк, к * у.

еорема 2. ЗА" [~]X", Xя С в": 3У" У" С В", X" ^ У", где [~] - отношение эк-'валентности (/--изоморфизма) деревьев.

Теорема 3. ЗТ" = и(т/1),1{т1в) = 1{тв): и(7;в) = Л£, где п(т») - номер позиции эл. мента дерева в табличном представлении, Итг - номер позиции в табличном представлю нии, в которую был скопирован корень дерева А" в результате выполнения подстановю

в)

а&^аыЫакзМабэ'абб'а&аез^ае^азб/анМ^ат/ап,))) В) Г~\То

№ Тип узла Ссылка на предка Множество вершин/ссылок

0(То) • ■ 1,2

ни) 1 0 99

2 (ТО 0 3, 4

3(1.,) Л 2 94, 95, 128

4(Тг) 2 5,6,7

5(1-2) Л 4 65, 66, 82, 83

6(Тз) 4 8

7(Т4) 4 9

8(Ц) £ 6 55, 56, 112

9(и) 1 7 59, 104, 111

№ Тип Ссылка на

узла предка

% 0(То) • -

1(Т,) / 0

Л 2(Гг) • 1

3(Тз) / 2

4(Т<) ! 3

№ Множество Ссылка на

0> вершин предка

а 0(То) 99 0

1(Т,) 94, 95, 128 1

2(Т.,) 65, 66, 82, 83 2

3(Т3) 55, 56, 112 3

4(Т<) 59, 104, 111 4

Рис. 1. Представление Я-выражения (а) в виде дерева (б) и различные способы его табличного описания (в, г)

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

управления составляют о[п?М + М)1^ и о[пп 1оцпк ■ (¿V + М)2| соответственно

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

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

Хранение /^-выражений осуществляется в табличном виде с использованием структуры из следующего набора полей: тип узла (ТУ), множество вершин (МВ), ссылка на

едка (СП), мощность узла (МУ), тип соответствия (ТС), номер соответствия (НС), уда-емый элемент (УЭ). Поля хранятся в однородной среде электронной модели дерева, ляющейся по своей организации ассоциативной многопортовой памятью.

В структуру акселератора рис. 2 входят схемы проверки принадлежности вершины :реву (СППВД), расчета ш-мощности дерева (СРМД), проверки отношения нестрогого лючения (СПОНВ), удаления поддерева (СУП), вставки поддерева (СВП), раскрытия :обок (СРС) и удаления пустых позиций (СУПП). Например, операция проверки г-юморфизма Д-выражений выполняется схемой, приведенной на рис. 3.

Рис. 2. Структурная схема акселератора для обработки Е-выражений

Помимо перечисленных выше схем акселератор (рис. 2) содержит контроллер ши PCI Express (КШ PCI-X), регистры РгННВ номера начальной и РгНКВ номера конеч* вершин соответственно; элементы памяти 4-7, хранящие /^-выражения, входящие в став пары обрабатываемых выражений системы Е; коммутаторы КХ-КА, обеспечивЕ щие модификацию трех /^-выражений А", В" и С" из четырех, загруженных в аксе. ратор, в зависимости от типа выполняемой подстановки (и- или d-) согласно двоичш значениям признаков <pu и ipd. После загрузки исходных значений управляющей мац ной по шине данных 1 в элементы 2-7 устройством управления активируются схемы 1 18, в результате чего производится расчет оо-мощностей загруженных Л-выражений. выходах, схем 8-11, 19, 20 формируются значения двоичных признак , , , ц , ш*, ш*, которые определяют возможность проведения одной из поде

новок, что идентифицируется единичным значением признака v, формируемого устрс ством управления 12. В случае если выполнение операции подстановки возможно, ус ройство управления поочередно активирует схемы 25-28, в результате чего на выход коммутаторов К\ и К2 формируется обновленная пара ^-выражений, соответствуют результату операции подстановки, и выставляется единичное значение признака готе ности 9. Обновленная пара Л-выражений выдается на шину данных 1.

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

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

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

Анализ качества разбиений был выполнен в разработанной автором визуальн! программной системе РАЕ. Первая серия вычислительных экспериментов была напрг лена на исследование поведения методов построения разбиений при наличии технолог ческих ограничений. Полученные зависимости качественно схожи; например, завис мость вероятности получения минимального числа блоков в разбиении от ограничен на емкость памяти контроллера СЛУ приведена на рис. 4. Их анализ показывает сущес венное преимущество модифицированного метода параллельно-последовательной i композиции по сравнению с известным методом С.И. Баранова.

0,8

0,6

0,4

0,24

3 10 20 30 40 Рис. 4. Зависимость вероятности построения разбиения с минимальным шелом блоков ря от ограничения на объем памяти микрокоманд контроллера \Упт (1 -модифицированный метод параллельно-последовательной декомпозиции, 2-метод С.И. Баранова)

Целью второй серии экспериментов являлось вьшенение того, как соотносятся значения критериев качества при разбиении алгоритмов управления с различным числом ¡1ершин. Полученные результаты (см. рис. 5) показывают, что модифицированный метод лараллельно-последовательной декомпозиции обеспечивает максимальную вероятность юстроения разбиений с минимальным числом блоков как в идеальном случае при отсутствии ограничений (наравне с методом С.И. Баранова), так и при наличии ограничений. Указанный на рис. 4 и 5 критерий качества 2Н является наиболее важным, его рост при-

I Рис. 5. Зависимости вероятности построения разбиения, с минимальным числом блоков ; рн от среднего размера алгоритма управления IV: без ограничений (а) и при наличии ог-1 раничений (б): 1 - модифицированный метод параллельно-последовательной декомпозиции, 2-метод С.И. Баранова, 3 - метод АД. Закревского

Также было проведено исследование зависимости времени построения разбиения среднего числа вершин в алгоритме управления для программной реализации процед преобразований, в результате чего с использованием метода наименьших квадратов б] ли получены следующие зависимости времени построения разбиеда = —1,064 + 9,698-10"2 д: для метода С.И. БараноЕ

г'(Аг) = -6,756 + 1,143х-4,524-Ю-2*2 +6,326-10""х3 для метода С.И. Закревского /(ЛГ) = -4,596 + 1,145л: - 4,005 • 10" V + 6,833• Ю-4*3 +1,417• 10~V для модифищ рованного метода параллельно-последовательной декомпозиции. С использование приведенных формул получены оценки времени, необходимого на отыскание ра; биений алгоритмов управления с различным числом вершин (см. табл.).

Таблиц

Зависимость среднего времени построения разбиения

от среднего размера алгоритма управления_

Метод Средний размер алгоритма управления

N = 100 N=1000 N = 10000

С.И. Баранова 0,4 с 0,8 ч 10,3 мес

А.Д. Закревского 0,29 с 9,8 мин 7,3 суш

Параллельно-последовательной декомпозиции 1,8 с 4,1 ч 4,5 года

Таким образом, получение разбиений высокого качества с использованием моди фицированного метода параллельно-последовательной декомпозиции требует сущест венных временных затрат. Использование разработанного акселератора позволяет сокрг тить время обработки /?-выражений в N раз, при этом время построения множества сече ний, составляющее 2,8 года при программной реализации для ТУ = 10000, сокращаете до 2,4 часа. Общее время синтеза разбиения сокращается в 2,7 раза.

Аппаратная сложность акселератора, выраженная числом эквивалентных вентиле: (ЭВ), выражается формулой

+474Л/.;;т + 250М/;т [1оё2 Л^], где ¿тах - максимальное число элементов в наборах листьев = А'), - макси мальное число элементов в табличном представлении деревьев. При N = 10 000 она со ставляет величину порядка 60 млн. ЭВ, что соответствует уровню развития современной микроэлектронной элементной базы.

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

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

ик преобразований с программного на аппаратный уровень. При этом получены сле-ующие результаты:

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

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

1. Проведено сравнение методов построения разбиений, в ходе которого подтверждено !Ысокое качество разбиений, получаемых модифицированным параллельно-юследовательным методом, выраженное минимальным числом блоков в 85-99% случаев, уменьшением среднего числа блоков до 13%, сложности сети межблочных связей до !2% и интенсивности межблочных взаимодействий до 20% по сравнению с известными залогами. Оценена асимптотическая временная сложность метода, получена практиче-:кая оценка его трудоемкости при построении разбиений алгоритмов размером 10000 ¡ершин и более, составляющая величину порядка нескольких лет. к С целью снижения временной сложности преобразований разработан акселератор, юзволяющий снизить время обработки /?-выражений за счет использования паралле-[изма как при действиях с множествами (наборами листьев деревьев), так и при выпол-1ении отдельных операций преобразования в N раз (с 2,8 года до 2,4 часа при ¥ = 10000).

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

). Получены оценки выигрыша в скорости обработки с использованием разработанного кселератора (составляющего по меньшей мере N раз при обработке Л-выражений) и его лпаратной сложности (порядка 60 млн. ЭВ), подтверждающие возможность практиче-:кого воплощения аппаратного разбиения алгоритмов на современной элементной базе. Использование акселератора в составе программно-аппаратного комплекса позволяется хжрахцение времени поиска разбиений в 2,7 раза.

СПИСОК ОСНОВНЫХ ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи в изданиях по перечню ВАК Минобрнауки РФ

1. Ватутин, Э.И. Построение множества сечений в задаче оптимального разбиения параллельных управляющих алгоритмов [Текст] / Э.И. Ватутин, И.В. Зотов, B.C. Титов // Известия ТулГУ. Вычислительная техника. Информационные технологии. Системы управления. Тула: ТулГУ, 2003. Т. 1. Вып. 2. С. 70-77.

2. Борзов, Д.Б. К задаче субоптимального разбиения параллельных алгоритмов [Текст] / Д.Б. Борзов, Э.И. Ватутин, И.В. Зотов, B.C. Титов // Известия вузов. Приборостроение. Вып. 12,2004. С. 34-39.

3. Ватутин, Э.И. Идентификация и разрыв последовательных Циклов в задаче субоптимального разбиения параллельных управляющих алгоритмов [Текст] / Э.И. Ватутин,

И.В. Зотов // Известия ТулГУ. Серия: Вычислительная техника. Информационные тех нологии. Системы управления. Т. 1. Вып. 3. Вычислительная техника. Тула: ТулГУ 2004. С. 51-55.

4. Ватутин, Э.И. Аппаратная модель для определения минимального числа блоков npi декомпозиции параллельных алгоритмов логического управления [Текст] / Э.И. Ватутин И.В. Зотов // Известия вузов. Приборостроение. 2008. Т. 51, № 2. С. 39-43.

5. Ватутин, Э.И. Анализ качества блочных разбиений при синтезе логических мульти контроллеров [Текст] / Э.И. Ватутин, И.В. Зотов // Информационно-измерительные i управляющие системы. № 10, Т. 6. М.: «Радиотехника», 2008. С. 32-38.

6. Ватутин, Э.И. Выявление изоморфных вхождений R-выражений при построений множества сечений параллельных алгоритмов логического управления [Текст] / Э.И Ватутин, И.В. Зотов И.В., B.C. Титов // Известия вузов. Приборостроение. 2009. Т 52, № 2. С. 37-45.

Статьи

7. Ватутин, Э.И. Поиск базового сечения в задаче разбиения параллельных алгоритмов [Текст] / Э.И. Ватутин, И.В. Зотов // Деп. в ВИНИТИ 24.11.03 № 2036-В2003.30 с.

8. Ватутин, Э.И. Построение матрицы отношений в задаче оптимального разбиения параллельных управляющих алгоритмов [Текст] / Э.И. Ватутин, И.В. Зотов // Известия КурскГТУ. Курск, 2004. № 2. С. 85-89.

9. Ватутин, Э.И. Параллельно-последовательный метод формирования субоптимальных разбиений [Текст] / Э.И. Ватутин, И.В. Зотов // Информационные технологии моделирования и управления. Воронеж: «Научная книга», 2004. Вып. 12. С. 64-71.

10. Ватутин, Э.И. Использование схемных формирователей и преобразователей двоичных последовательностей при построении комбинаторно-логических акселератороЕ [Текст] / Э.И. Ватутин, И.В. Зотов, B.C. Титов // Известия КурскГТУ, 2008. № 4 (25). С 32-39.

Тезисы докладов и материалы конференций

11. Ватутин, Э.И. Построение блоков разбиения в задаче декомпозиции параллельных управляющих алгоритмов [Текст] / Э.И. Ватутин, И.В. Зотов // Материалы и упрочняющие технологии - 2003. Курск: КурскГТУ, 2003. Т. 2. С. 38-42.

12. Ватутин, Э.И. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов [Текст] / Э.И. Ватутин, И.В. Зотов // Параллельные вычисления и задачи управления (РАСО'04). М.: ИПУ им. В.А. Трапезникова РАН, 2004. С. 884917.

13. Ватутин, Э.И. Объединение линейных участков в задаче нахождения субоптимальных разбиений параллельных управляющих алгоритмов [Текст] / Э.И. Ватутин // Молодежь и XXI век. Курск: изд-во КурскГТУ, 2004. Ч. 1. С. 22-23.

14. Ватутин, Э.И. Оценка качества разбиений параллельных управляющих алгоритмов на последовательные подалгоритмы с использованием весовой функции [Текст] / Э.И. Ватутин // Интеллектуальные и информационные системы (Интеллект - 2005). Тула: ТулГУ, 2005. С. 29-30.

15. Ватутин, Э.И. Программная система для построения разбиений параллельных управляющих алгоритмов [Текст] / Э.И. Ватутин, И.В. Зотов // Идентификация систем и задачи управления (SICPRO'06). М.: ИПУ им. В.А. Трапезникова РАН, 2006. С. 2239-2250.

. Vatutin, E.I. Constructing Random Sample Parallel Logic Control Algorithms [Текст] / i. Vatutin // 1 l'h International Student Olympiad on Automatic Control (Baltic Olympiad OAC'06). Saint-Petersburg: IFMO, 2006. PP. 162-166.

7. Vatutin, E.I. Comparison of Methods for Getting Separation of Parallel Logic Control Algo-thms [Текст] / E.I. Vatutin, J."N. Abdel-Jalil, M.H. Najajra, I.V. Zotov // Information and Tele-MYimunication Technologies in Intelligent Systems (ITT IS'06). Katania, Italy, 2006. PP. 92-l.

'?. Ватутин, Э.И. Комплексная сравнительная оценка методов выбора разбиений при роектировании логических мультиконтроллеров [Текст] / Э.И. Ватутин, C.B. Волобуев, ■ .13. Зотов // Идентификация систем и задачи управления (SICPRO'08). M.: ИПУ им. :.А. Трапезникова РАН, 2008. С. 1917-1940.

9. Ватутин, Э.И. Однородная среда электронной модели дерева для аппаратно-риентированной обработки Л-выражений [Текст] / Э.И. Ватутин // Оптико-электронные pvoopbi и устройства в системах распознавания образов, обработки изображений и сим-олчюй информации (Распознавание - 2008). Ч. 1. Курск: КурскГТУ, 2008. С. 90-92. С. Ватутин, Э.И. Повышение качества разбиения алгоритмов при синтезе логических '• льтиконтроллеров с использованием метода параллельно-последовательной декомпо-::цнн [Текст] / Э.И. Ватутин, И.В. Зотов // Перспективы развития систем управления ружием. М.: Изд-во «Бедретдинов и Ко», 2007. С. 84-92.

i Ватутин, Комплексный сравнительный анализ качества разбиений при синтезе логи-îcîchx мультиконтроллеров в условиях присутствия технологических ограничений Текст] / Э.И. Ватутин, C.B. Волобуев, И.В, Зотов // Параллельные вычисления и задачи правления (РАСО'08). М.: ИПУ им. В.А. Трапезникова РАН, 2008. С. 643-685.

Патент

Патент № 2336556. Российская федерация. Микроконтроллерная сеть [Текст] / Ватутин и др.; заявка 2007114559/09; опубл. 20.10.2008, бюл. № 29.

Свидетельства об официальной регистрации программ для ЭВМ

3. Свидетельство о регистрации программы для ЭВМ № 2005613091. Параллельно-оследавательный метод формирования субоптимальных разбиений параллельных '■равляющих алгоритмов [Текст] / Э.И. Ватутин, И.В. Зотов (РФ). М.: РосПатент; заяв-

03.10.05; дата регистрации 28.11.05.

4. Свидетельство о регистрации программы для ЭВМ №2007613222. Визуальная среда интгза разбиений параллельных алгоритмов логического управления [Текст] / Э.И. Ва-ут:ш, И.В. Зотов (РФ). М.: РосПатент; заявлено 04.06.07; дата регистрации 30.07.07.

Соискатель /Зк ^ Э.И. Ватутин

Подписано в печать <$С503__. Формат 60x84 1/16 .

Печатных листов 1,0. Тираж 100 экз. Заказ 5 ч Курский государственный технический университет. 305040, г. Курск, ул. 50 лет Октября, 94.

ВВЕДЕНИЕ.

1. ПОСТАНОВКА ЗАДАЧИ ПОИСКА ОПТИМАЛЬНЫХ РАЗБИЕНИЙ. ОБЗОР СХОЖИХ NP-ТРУДНЫХ ЗАДАЧ И МЕТОДОВ ИХ РЕШЕНИЯ.

1.1. Обзор существующих ТУР-трудных задач и подходов к уменьшению затрат вычислительного времени при их решении.

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

2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ РАЗБИЕНИЯ. АЛГОРИТМЫ ЭТАПОВ МЕТОДА ПАРАЛЛЕЛЬНО-ПОСЛЕДОВАТЕЛЬНОЙ ДЕКОМПОЗИЦИИ.

2.1. Формализованное описание алгоритма управления.

2.2. Постановка задачи выбора оптимального разбиения.

2.3. Приведение граф-схемы алгоритма к ациклической форме.

2.4. Классификация бинарных отношений между вершинами алгоритма.

2.5. Уменьшение размерности решаемой задачи путем введения обобщенных вершин.

2.6. Представление алгоритма управления в виде множества сечений.

2.7. Практическая реализация операций над R-выражениями и их свойства.

2.7.1. Представление ^-выражений в виде деревьев.

2.7.2. Операция проверки принадлежности вершины дереву.

2.7.3. Операция определения w-мощности дерева.

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

2.7.5. Операция удаления r-изоморфного поддерева.

2.7.6. Операция вставки поддерева.

2.7.7. Операция раскрытия скобок.

2.7.8. Операция удаления «пропусков».

2.8. Оценка интенсивности межблочных взаимодействий.

2.9. Синтез блоков разбиения с использованием множества сечений.

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

2.11. Оценка асимптотической временной и емкостной сложности алгоритмов этапов и метода параллельно-последовательной декомпозиции в целом.

3. СТРУКТУРНО-ФУНКЦИОНАЛЬНАЯ ОРГАНИЗАЦИЯ АКСЕЛЕРАТОРА ОПЕРАЦИЙ НАД R-ВЫРАЖЕНИЯМИ.

3.1. Особенности аппаратно-ориентированного табличного представления Л-выражений

3.2. Структурно-функциональная организация комбинаторно-логического акселератора

3.3. Однородная среда дня хранения электронной модели дерева.

3.4. Загрузка данных в ОСЭМД.

3.5. Комбинационные схемы формирования и преобразования битовых последовательностей

3.5.1. Схема подсчета бит (СПБ).

3.5.2. Схема маскировки неиспользуемых позиций (СМНП).

3.5.3. Схема сравнения битовых векторов (ССБВ).

3.5.4. Схемы выделения заданных граничных значений.

3.5.5. Схема определения типа соответствия предка (СОТСП).

3.6. Операция определения принадлежности вершины дереву.

3.7. Операция определения со-мощности дерева.

3.8. Операция проверки отношения нестрогого включения.

3.9. Операция удаления поддерева.

3.10. Операция вставки поддерева.

3.11. Операция раскрытия скобок.

3.12. Операция удаления пустых позиций («пропусков»).

4. ЭКСПЕРИМЕШАЛЬНЫЕ ИССЛЕДОВАНИЯ И ОЦЕНКИ.

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

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

4.3. Сравнение качества решений методов синтеза разбиений на выборках случайных алгоритмов.

4.4. Оценка аппаратной сложности акселератора.

4.5. Оценка быстродействия акселератора.

Актуальность работы. Системы логического управления (СЛУ) являются одним из распространенных классов цифровых управляющих систем, проблемы анализа и синтеза которых на протяжении многих лет остаются в центре внимания отечественных и зарубежных ученых (С.И.Баранов, А.А.Баркалов, В.И.Варшавский, В.А.Горбатов, А.Д. Закревский, И.В. Зотов, В.Г. Лазарев, В.З. Магергут, Е.И. Пийль, Е.Н. Турута, B.C. Харченко,

A.А. Шалыто, С.А. Юдицкий, Т. Agerwala, S. Husson, R. Puri и др.). Современные СЛУ - параллельные многомодульные однородные системы, объединяющие сотни и тысячи процессорных узлов. Как правило, это многофункциональные открытые системы, способные оперативно перестраиваться на новый алгоритм управления, выбираемый из некоторого (часто заранее неизвестного) множества алгоритмов. Подобные системы могут выполнять комплексные управляющие алгоритмы теоретически неограниченной сложности при условии их предварительного разбиения (декомпозиции) на частные алгоритмы (блоки), назначаемые на отдельные модули. При этом длительность процессов начальной настройки, отладки или последующей перенастройки системы, выполняемых обычно автоматизировано, во многом определяется временем поиска походящего разбиения, сокращение которого ведет к повышению производительности труда и увеличению коэффициента готовности СЛУ.

Разбиение параллельных алгоритмов осуществляется с учетом структурных и технологических ограничений СЛУ, при этом выбор окончательного решения производится по ряду критериев качества (связность и интенсивность взаимодействия частных алгоритмов, число избыточных частных алгоритмов, межблочное распределение микроопераций- и логических условий), влияющих на основные функциональные характеристики системы (аппаратная сложность и производительность). Нахождение оптимального решения задачи разбиения практически недостижимо для алгоритмов управления реальной сложности (20 вершин и более) ввиду необходимости перебора и сопоставления очень большого числа различных разбиений (ограниченного сверху числом Белла). В связи с этим на практике распространены эвристические алгоритмы декомпозиции, обеспечивающие приближенное (субоптимальное) решение задачи за приемлемое время (С.И.Баранов, А.А.Баркалов, В.А.Горбатов,

B.C. Харченко). Однако известные эвристические алгоритмы характеризуются низким качеством получаемых решений из-за последовательного характера процедур обработки. Более высокое качество разбиений обеспечивает метод параллельно-последовательной декомпозиции (И.В. Зотов). В то же время он требует существенных затрат времени и памяти ЭВМ при программной реализации.

Потребность в построении разбиений высокого качества при ограниченных временных затратах на их получение приводит к необходимости переноса процедур обработки с программного уровня на аппаратный путем разработки специализированных устройств-акселераторов, жестко адаптированных к особенностям решаемой задачи. Известные устройства (B.JL Баранов, В.В. Васильев, А.Г. Додонов, В.В. Епихин, В.М. Глушань, В.А. Калашников, В.М. Курейчик, А.Н. Чаплиц, В.Н. Червяцов, Л.И. Щербаков, В.И. Ян и др.) для решения схожих задач на графах характеризуются недостаточными функциональными возможностями или избыточной вычислительной сложностью.

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

Работа выполнена в рамках совместных НИР КурскГТУ и ОХП ОКБ «Авиаавтоматика» Курского ОАО «Прибор» (темы №1.121.03, №1.218.08П), а также в соответствии с планом НИР Курского государственного технического университета по единому заказ-наряду Министерства образования РФ в 2003-2009 годах.

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

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

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

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

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

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

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

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

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

Научная новизна результатов работы заключается в следующем:

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

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

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

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

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

Практическая ценность результатов работы заключается в следующем:

1. Декомпозиция управляющих алгоритмов с использованием разработанных правил и процедур позволяет получать разбиения более высокого качества с минимальным числом блоков в 85-99% случаев, что обеспечивает создание более компактных (фактически, более дешевых) СЛУ с меньшей аппаратной сложностью (за счет уменьшения среднего числа блоков до 13% и снижения сложности сети межблочных связей до 22%) и большим быстродействием (за счет снижения интенсивности межблочных взаимодействий до 20%).

2. Реализация разработанных правил и процедур в созданном акселераторе позволяет снизить время выполнения наиболее трудоемких преобразований (построение множества сечений) при декомпозиции управляющих алгоритмов в А'" раз, обеспечивая уменьшение трудоемкости декомпозиции алгоритмов реальной размерности (более 1000 вершин) в 2,7 раза, что весьма существенно при разработке или оперативной перенастройке СЛУ ввиду повышения производительности труда и коэффициента готовности системы.

Реализация и внедрение. Результаты диссертационного исследования используются в учебном процессе Курского государственного технического университета в рамках дисциплин «Программирование на языке высокого уровня», «Схемотехника ЭВМ», «Методы оптимизации», «Теория принятия решений», а также внедрены в ООО «Сайнер-Курск» (г. Курск) и ОАО «Прибор» (г. Курск), что подтверждается соответствующими актами.

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

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

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

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

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

6. Зависимости степени приближения получаемых разбиений к оптимуму при использовании разработанных правил и процедур и известных методов декомпозиции от значений технологических ограничений и параметров обрабатываемых алгоритмов управления, демонстрирующие снижение среднего числа блоков разбиений до 13%, уменьшение сложности сети межблочных связей до 22% и интенсивности межблочных взаимодействий до 20%. Оценки трудоемкости декомпозиции управляющих алгоритмов при программной и аппаратной реализации.

Апробация работы. Основные положения диссертационной работы докладывались и получили положительную оценку на региональных, российских и международных конференциях: Параллельные вычисления и задачи управления «РАСО» (Москва, 2004,2008); Information and Telecommunication Technologies in Intelligent Systems (Испания, 2004,2005, 2007, Италия, 2006); Идентификация систем и задачи управления «SICPRO» (Москва, 2006, 2008); Информационные технологии моделирования и управления (Воронеж, 2004); Интеллектуальные и информационные системы (Тула, 2004, 2005); Балтийская олимпиада по автоматическому управлению «ВОАС» (Санкт-Петербург, 2006, 2008); Информационно-математические технологии в экономике, технике и образовании (Екатеринбург, 2007); Образование, наука, производство (Белгород, 2004, 2006); Молодежь и XXI век (Курск, 2003,2004, 2007, 2008); Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации «Распознавание - 2003» (Курск, 2003, 2005, 2008); Материалы и упрочняющие технологии (Курск, 2003); Современные инструментальные системы, информационные технологии и инновации (Курск, 2006); Перспективы развития систем управления оружием (Курск, 2007); а также на научных семинарах кафедры вычислительной техники КурскГТУ с 2003 по 2009 гг.

Публикации. По результатам диссертации опубликовано 39 печатных работ, среди которых 10 статей (из них 6 по перечню ВАК), 2 свидетельства о государственной регистрации программы для ЭВМ (№ 2005613091, № 2007613222) и 1 патент на изобретение (№> 2336556). Список основных публикаций приведен в конце автореферата.

Личный вклад автора. Все выносимые на защиту научные результаты получены соискателем лично. В работах по теме диссертации, опубликованных в соавторстве, лично соискателем выполнено следующее: в [1,7] сформулированы процедуры построения множества сечений параллельного алгоритма с использованием системы ^-выражений; в [3,8,9,12,13] разработаны процедуры модифицированной параллельно-последовательной декомпозиции; в [11,14] определены детали реализации алгоритмов вычисления значений критериев качества; в [15] предложена архитектура аппаратно-программного комплекса для автоматизированного построения разбиений и проведения вычислительных экспериментов; в [5,16,17,18,20,21] разработана методика проведения вычислительных экспериментов, а также проведено исследование экспериментальных результатов и влияния на них ряда модификаций методов декомпозиции; в [2,4,6,10,19] предложена схемотехническая реализация акселератора; в [22] синтезирован ряд коммутационных блоков, необходимых для аппаратной реализации процедур разбиения комплексных алгоритмов логического управления.

Объем и структура работы. Диссертационная работа состоит из введения, 4 глав, заключения, списка литературы из 128 источников и 1 приложения. Работа содержит 155 страниц основного текста, 64 рисунка и 16 таблиц.

Выводы

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

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

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

4. Приведена оценка аппаратной сложности разработанного устройства-акселератора, позволяющая его реализацию на современной элементной базе в виде заказного или ПЛИС исполнения.

5. Приведена оценка быстродействия акселератора, показывающая как минимум N кратное снижение временной сложности операций над ^-выражениями.

ЗАКЛЮЧЕНИЕ

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

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

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

3. Проведено сравнение методов построения разбиений, в ходе которого подтверждено высокое качество разбиений, получаемых модифицированным параллельно-последовательным методом, выраженное минимальным числом блоков в 85-99% случаев, уменьшением среднего числа блоков до 13%, сложности сети межблочных связей до 22% и интенсивности межблочных взаимодействий до 20% по сравнению с известными аналогами. Оценена асимптотическая временная сложность метода, получена практическая оценка его трудоемкости при построении разбиений алгоритмов размером 10000 вершин и более, составляющая величину порядка нескольких лет.

4. С целью снижения временной сложности преобразований разработан акселератор, позволяющий снизить время обработки /^-выражений за счет использования параллелизма как при действиях с множествами (наборами листьев деревьев), так и при выполнении отдельных операций преобразования в ТУраз (с 2,8 года до 2,4 часа при N = 10000 ).

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

6. Получены оценки выигрыша в скорости обработки с использованием разработанного акселератора (составляющего по меньшей мере N раз при обработке ^-выражений) и его аппаратной сложности (порядка 60 млн. ЭВ), подтверждающие возможность практического воплощения аппаратного разбиения алгоритмов на современной элементной базе. Использование акселератора в составе программно-аппаратного комплекса позволяет сокращение времени поиска разбиений в 2,7 раза

1. Борзов, Д.Б. К задаче субоптимального разбиения параллельных алгоритмов Текст. / Д.Б. Борзов, Э.И. Ватутин, И.В. Зотов, B.C. Титов // Известия вузов. Приборостроение. Вып. 12,2004. С. 34-39.

2. Ватутин, Э.И. Аппаратная модель для определения минимального числа блоков при декомпозиции параллельных алгоритмов логического управления Текст. / Э.И. Ватутин, И.В. Зотов //Известия вузов. Приборостроение. 2008. Т. 51, № 2. С. 39-43.

3. Ватутин, Э.И. Анализ качества блочных разбиений при синтезе логических мультикон-троллеров Текст. / Э.И. Ватутин, И.В. Зотов // Информационно-измерительные и управляющие системы. № 10, Т. 6. М.: «Радиотехника», 2008. С. 32-38.

4. Ватутин, Э.И. Выявление изоморфных вхождений R-выражений при построении множества сечений параллельных алгоритмов логического управления Текст. / Э.И. Ватутин, И.В. Зотов И.В., B.C. Титов //Известия вузов. Приборостроение. 2009. Т. 52, № 2. С. 37-45.

5. Ватутин, Э.И. Поиск базового сечения в задаче разбиения параллельных алгоритмов Текст. / Э.И. Ватутин, И.В. Зотов // Деп. в ВИНИТИ 24.11.03 № 2036-В2003.30 с.

6. Ватутин, Э.И. Построение матрицы отношений в задаче оптимального разбиения параллельных управляющих алгоритмов Текст. / Э.И. Ватутин, И.В. Зотов // Известия Курск! I У. Курск, 2004. № 2. С. 85-89.

7. Ватутин, Э.И. Параллельно-последовательный метод формирования субоптимальных разбиений Текст. / Э.И. Ватутин, И.В. Зотов // Информационные технологии моделирования и управления. Воронеж: «Научная книга», 2004. Вып. 12. С. 64—71.

8. Ватутин, Э.И. Использование схемных формирователей и преобразователей двоичных последовательностей при построении комбинаторно-логических акселераторов Текст. / Э.И. Ватутин, И.В. Зотов, B.C. Титов //Известия КурскГТУ, 2008. № 4 (25). С. 32-39.

9. Ватутин, Э.И. Построение блоков разбиения в задаче декомпозиции параллельных управляющих алгоритмов Текст. / Э.И. Ватутин, И.В. Зотов // Материалы и упрочняющие техноло-пш—2003. Курск: КурскГТУ, 2003. Т. 2. С. 38-42.

10. Ватутин, Э.И. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов Текст. / Э.И. Ватутин, И.В. Зотов // Параллельные вычисления и задачи управления (РАСО'04). М.: ИПУ им. В.А. Трапезникова РАН, 2004. С. 884-917.

11. Ватутин, Э.И. Объединение линейных участков в задаче нахождения субоптимальных разбиений параллельных управляющих ал горитмов Текст. / Э.И. Ватутин // Молодежь и XXI век. Курск: изд-во КурскГТУ, 2004. Ч. 1. С. 22-23.

12. Ватутин, Э.И. Программная система для построения разбиений параллельных управляющих алгоритмов Текст. / Э.И. Ватутин, И.В. Зотов // Идентификация систем и задачи управления (SICPRO'06). М.: ИПУ им. В.А. Трапезникова РАН, 2006. С. 2239-2250.

13. Vatutin, E.I. Constructing Random Sample Parallel Logic Control Algorithms Текст. / E.I. Vatutin // 11th International Student Olympiad on Automatic Control (Baltic Olympiad BOAC'06). Saint-Petersburg: IFMO, 2006. PP. 162-166.

14. Патент № 2336556. Российская федерация. Микроконтроллерная сеть Текст. / Э.И. Ватутин и др.; заявка 2007114559/09; опубл. 20.10.2008, бюл. № 29.

15. Свидетельство о регистрации программы для ЭВМ № 2007613222. Визуальная среда синтеза разбиений параллельных алгоритмов логического управления Текст. / Э.И. Ватутин, И.В. Зотов (РФ). М.: РосПатент; заявлено 04.06.07; дата регистрации 30.07.07.

16. Курейчик, В.М. Комбинаторные аппаратные модели и алгоритмы в САПР Текст. / В.М. Курейчик, В.М. Глушань, Л.И. Щербаков. М.: «Радио и связь», 1990.216 с.

17. А.с. № 1086434, МКИ3 G06F 15/20. Устройство для разбиения графа на подграфы / В.М. Глушань, В.М. Курейчик, Л.И. Щербаков. Опубл. 1984, бюл. № 14.

18. А.с. № 1273941, МКИ3 G06F 15/20. Устройство для разбиения графа на подграфы / В.М. Глушань, Л.И. Щербаков, И.П. Левин. Опубл. 1986, бюл. № 44.

19. Число Белла Электронный ресурс. // http://m.wMpedia.or^wiki/4Haio Белла, 2008.

20. Rosen, К.Н. Handbook of discrete and combinatorial mathematics Text. / K.H. Rosen, J.G. Michaels, J.L. Gross, J.W. Grossman, D.R. Shier. New York: CRC Press, 2000.1183 p.

21. Число Стирлинга второго рода Электронный ресурс. // http://m.wikipedia.org/wiki/4HCfla Стирлингавторогорода, 2008.

22. Олифер, В. Компьютерные сети. Принципы, технологии, протоколы. Учебник для вузов Текст. / В. Олифер, Н. Олифер. СПб.: «Питер», 2008.960 с.

23. Microsoft Official Course 2277. Implementing, Managing, and Maintaining a Microsoft Windows Server 2003 Network Infrastructure: Network Services. Part number XI1-59430. Microsoft Press, 2005.357 p.

24. Lee, C.-H. Optimal task assignment in linear array networks Text. / C.-H. Lee, D. Lee, M. Kim //IEEETrans. Comput. 1992. Vol. 41, № 7. P. 877880.

25. Wu, S.S. Heuristic algorithms for task assignment and scheduling in a processor network Text. / S.S. Wu, D. Sweeting //Parallel Comput. 1994. № 20. P. 114.

26. Kim, J. Replicated process allocation for load distribution in fault-tolerant multi-computers Text. / Jong Kim; Heejo Lee; Sunggu Lee // IEEE Transactions on Computers. Volume 46, Issue 4,1997. P. 499-505.

27. Хопкрофт, Дж. Введение в теорию автоматов, языков и вычислений Текст. / Дж. Хоп-крофт, Р. Мотвани, Дж. Ульман. М.: «Вильяме», 2002.528 с.

28. Graham, R.L. Concrete Mathematics Text. / R.L. Graham, D.E. Knuth, O. Patashnic. Addison-Wesley, 1989.625 p.

29. Айгнер, M. Комбинаторная теория: пер. с англ. Текст. / М. Айгнер. М.: «Мир», 1982. 558 с.

30. Кристофидес, Н. Теория графов. Алгоритмический подход Текст. / Н. Кристофидес. М.: «Мир», 1978.432 с.

31. Зыков, А.А. Основы теории графов Текст. / А.А. Зыков. М.: «Наука», 1987.382 с.

32. Евстигнеев, В.А. Применение теории графов в программировании Текст. / В.А. Евстигнеев. М.: «Наука», 1983.354 с.

33. Берж, К. Теория графов и ее применения Текст. / К. Берж. М.: «Издательство иностранной литературы», 1962.320 с.

34. Асанов, М.О. Дискретная математика: графы, матроиды, алгоритмы Текст. / М.О. Аса-нов, В А. Баранский, В.В. Расин. Ижевск: НИЦ «РХД», 2001.288 стр.I

35. Свами, М. Графы, сети и алгоритмы Текст. / М. Свами, К. Тхуласираман. М.: «Мир», 1984.454 с.

36. Оре, О. Теория графов Текст. / О. Ope. М.: «Наука», 1980. 336 с.

37. Уилсон, Р. Введение в теорию графов Текст. / Р. Уилсон. М.: «Мир», 1977.208 с.

38. Татт, У. Теория графов Текст. / У. Татг. М.: «Мир», 1988.424 с.

39. Харари, Ф. Теория графов Текст. / Ф. Харари. М.: Мир, 1973.300 с.

40. Майника, Э. Алгоритмы оптимизации на сетях и графах Текст. / Э. Майника. М.: «Мир», 1981.324 с.

41. Зотов, И.В. Организация и синтез микропрограммных мультимикроконтроллеров Текст. / И.В. Зотов, ВА. Колосков, B.C. Титов, К.А. Сапронов, А.П. Волков. Курск: изд-во «Курск», 1999.368 с.

42. Процессор Intel Itanium Электронный ресурс. // http://www.intel.com/cd/products/services/emea/ms/processors/itamum/3736n 2008.

43. Матрицы Altera Stratix Ш стали основой самой большой платы для макетирования ASIC Электронный ресурс. // http://www.ixbt.com/news/all/index.shtml?! 1/30/11,2008.

44. Посыпкин, М.А. Комбинированный параллельный алгоритм решения задачи о ранце Текст. / М.А. Посыпкин, И.Х. Сигал // Параллельные вычисления и задачи управления (РАСО '2008). М.: ИПУ РАН, 2008. С. 177-189.

45. Пархоменко, В.П. Проблемы реализации и функционирования глобальной климатической модели на параллельных вычислительных системах Текст. / В.П. Пархоменко // Параллельные вычисления и задачи управления (РАСО '2008). М.: ИПУ РАН, 2008. С. 122-141.

46. Ахметзянов, А.В. Декомпозиция и распараллеливание вычислений при моделировании нелинейной фильтрации флюидов в пористых средах Текст. / А.В. Ахметзянов // Параллельные вычисления и задачи управления (РАСО '2008). М.: ИПУ РАН, 2008. С. 93-103.

47. Жучков, А.В. Грид-сервисы для организации и высокопроизводительной обработки данных маммогрфического архива в сети скиф-гриф Текст. / А.В. Жучков, Н.В. Твердохлеб // Параллельные вычисления и задачи управления (РАСО'08). М.: ИПУ РАН, 2008. С. 838-849.

48. ЦРУ и другие инвесторы вкладывают средства в разработку бионанотехнологий Электронный ресурс. // http://www.ixbt.com/news/all/index.shtml703/82/05,2005.

49. Исследователи из IBM и Гарвардского университета привлекут добровольцев к разработке солнечных батарей Электронный ресурс. // http://www.ixbt.com/news/all/index.shtml? 11/41/22,2008.

50. Большой адронный коллайдер Электронный ресурс. // http://www.collider.msk.ru/vikipedia.html, 2008.63. http://algolist.manual.ru.

51. Ватутин, Э.И. Оптимизация обработки множеств Текст. / Э.И. Ватутин // Медико-экологические информационные технологии 2005. Курск: изд-во КурскГТУ, 2005. С. 145-147.

52. Lewis, В. PThread Premier. A Guide for Multithreaded Programming Text. / B. Lewis, DJ. Berg. SunSoft Press, 1996.370 p.

53. Developing Multithreaded Applications: A Platform Consistent Approach Текст. Intel Press, 2003.106 p.

54. Threading Methodology: Principals and Practices Текст. Intel Press, 2004.64 p.

55. Intel 64 and IA-32 Architectures Software Developers Manual. Vol. 1. Basic Architecture Текст. Intel Press, 2006.468 p.

56. А.с. СССР № 304604, МКИ3 G06G 7/48. Устройство для определения характеристик связности вероятностного графа / А.Н. Чаплиц, В.В. Епихин, В.И. Ян. Опубл. 1971, бюл. № 17.о

57. А.с. СССР № 314214, МКИ G06G 7/48. Устройство для исследования вероятностных графов / В.В. Епихин, А.Н. Чаплиц, В.И. Ян. Опубл. 1971, бюл. 27.

58. А.с. СССР № 364939, МКИ3 G06F 15/34. Устройство для нахождения деревьев графа / Р.В. Дмигриншн. Опубл. 1972, бюл. № 5.

59. А.с. СССР № 433504, МКИ G06G 7/48. Устройство для определения характеристик связности вероятностного графа / Р.В. Тверицкий. Опубл. 1974, бюл. № 23.

60. А.с. СССР № 468244, МКИ G06F 15/20. Устройство для исследования связности вероятностного графа/В.В. Епихин. Опубл. 1975, бюл. № 15.

61. А.с. СССР № 637822, МКИ3 G06F 15/20. Устройстводля исследования связности вероятностного графа/В.В. Епихин. Опубл. 1978, бюл. № 46.л

62. А.с. СССР № 656073, МКИ G06F 15/36. Устройство для моделирования характеристик графа/В.Н. Червяцов. Опубл. 1979, бюл. № 13.

63. А.с. СССР № 1101834, МКИ3 G06F 15/20. Устройство для определения характеристик графа / В.М. Глушань, В.М. Курейчик, Л.И. Щербаков, Ю.Е. Шведенко, В.Н. Гуров. Опубл. 1984, бюл. №25.

64. А.с. СССР № 1304033, МКИ3 G06F 15/20. Устройство для исследования характеристик вероятностных графов /В.М. Глушань, И.Н. Сердюков. Опубл. 1987, бюл. № 14.

65. А.с. СССР № 305484, МКИ3 G06G 7/34. Устройство для моделирования экстремальных путей на графе / В.В. Васильев, А.Г. Додонов, А.И. Левина. Опубл. 1971, бюл. № 18

66. А.с. СССР № 805300, МКИ3 G06F 7/00. Ячейка однородной вычислительной структуры / В.В. Васильев, А.Г. Додонов, О.Н. Голованова, Я.Я. Фенюк, В.В. Хаджинов. Опубл. 1981, бюл. № 6.

67. А.с. СССР № 1377867, МКИ3 G06F 15/20. Устройство для моделирования графов / В.В. Васильев, В.Л. Баранов. Опубл. 1988, бюл. № 8.

68. А.с. СССР № 1418736, МКИ3 G06F 15/20. Устройство для анализа параметров графа / В.В. Васильев, В. Л. Баранов. Опубл. 1988, бюл. № 31.

69. А.с. СССР № 1658171, МКИ3 G06F 15/419. Устройство для решения задач на графах / В.В. Васильев, В. Л. Баранов. Опубл. 1991, бюл. № 23.

70. А.с. СССР № 1765832, МЕСИ3 G06F 15/419. Устройство для решения задач на графах / С.А. Ильин, С.В. Листровой, ВЛ. Певнев, В.Н. Мариян, В.И. Сова. Опубл. 1992, бюл. № 36.

71. А.с. СССР № 2100838, МКИ3 G06F 15/173. Устройство для решения задач на графах / В.М. Игнатьев, Н.Ю. Афанасьева, А.Н. Крючков. Опубл. 1997, бюл. № 32.

72. А.с. СССР № 596951, МКИ3 G06F 15/20. Устройство для определения изоморфизма графов /В.М. Курейчик, В.А. Калашников, А.Г. Королев. Опубл. 1978, бюл. № 9.

73. А.с. СССР №> 732879, МКИ3 G06F 15/20. Устройство для определения изоморфизма орграфов / А.Г. Королев, ВА. Калашников, В.М. Курейчик. Опубл. 1980, бюл. № 17.

74. Патент США №> 20070179760А1, МКИ3 G06F 17/10. Method of determining graph isomorphism in polynomial time / J.R. Smith. Опубл. 2007.

75. А.с. СССР № 877552, МКИ3 G06F 15/20. Устройство для исследования графов /А.П. Гер-манюк, В А. Калашников, В.А. Литвиненко, Е.А. Ралдугин, Н.В. Федотов. Опубл. 1981, бюл. №40.

76. А.с. СССР № 1059579, МКИ3 G06F 15/347. Устройство для решения комбинаторно-логических задач при проектировании печатных плат / Б.Н. Мороговский, Л.И. Раппопорт, С.А. Поливцев, В.М. Курейчик. Опубл. 1983, бюл. № 45.

77. Leica создаст процессор для новой цифровой зеркальной камеры совместно с Fujitsu Электронный ресурс. // http://www.ixbt.com/news/all/archive.shtml72008/Q925,2008.

78. FTRECODER Blu — возможность добавить HD-процессор Toshiba SpursEngine в настольный ПК Электронный ресурс. // http://www.ixbt.com/news/all/archive.shtml72008/1129,2008.

79. S1C33L19 — процессор приложений Seiko Epson для работы с n>EG Электронный ресурс. // http://www.ixbt.com/news/all/index.shtml? 11/69/30.2009.

80. Медиапроцессор TI TMS320DM365 поддерживает видео в различных форматах, включая 1080р Электронный ресурс. // http://www.ixbt.com/news/all/index.shtml? 11/71/21,2009.

81. Ускоритель NextEngine по производительности равен 550 процессорам Intel Хеоп, работающим на частоте 2,66 ГГц Электронный ресурс. // http://www.ixbt.com/news/all/archive.shtml72008/Q329,2008.

82. Makino, J. А 29.5 Tops simulation of planetesimals in Uranus-Neptune region on GRAPE-6 Text. / J. Makino, E. Kokubo, T. Fukushige // Proc. of SC-2002. IEEE Trans, 2002. P. 34-34.

83. Баранов, С.И. Обобщенный метод декомпозиции граф-схем алгоритмов Текст. / С.И. Баранов, Л.Н. Журавина, В.А. Песчанский // А и ВТ. 1982. №5. С. 43-51.

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

85. Вороновский, Г.К. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности Текст. / Г.К. Вороновский, К.В. Махотило, С.Н. Петрашев, С.А. Сергеев. Харьков: «Основа», 1997.107 с.

86. Glover, F. Handbook of Metaheuristics Text. / F. Glover, G.A. Kochenberger. Moscow. «Kluw-er academic publishers», 2003.560 p.

87. Закревский, А.Д. Декомпозиция параллельных алгоритмов логического управления по заданному разбиению множества предложений Текст. / А.Д. Закревский, Ю.В. Потгосин // А и ВТ. 1985. №4. С. 65-72.

88. Закревский, А.Д. Формальное описание алгоритмов логического управления при проектировании дискретных систем Текст. / А.Д. Закревский, В.К. Василенок // Электронное моделирование. 1984. Т. 6, № 4. С. 79-84.

89. Кёниг, Р. Декомпозиция сетей Петри при проектировании дискретных устройств на основе стандартных модулей Текст. / Р. Кёниг, Г.Ф. Фрицнович // А и ВТ. 1984. № 1. С. 82-91.

90. Харченко, B.C. Декомпозиция параллельных матричных схем алгоритмов в задачах синтеза микроконтроллерных сетей Текст. / B.C. Харченко, С.Б. Кальченко, А.Е. Сазонов // А и ВТ. 1990. №4. С. 81-89.

91. Баранов, С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы) Текст. / С.И. Баранов. Л.: Энергия, 1979.232 с.

92. Лазарев, В.Г. Синтез управляющих автоматов Текст. / В.Г. Лазарев, Е.И. Пийль. М.: Энергоатомиздат, 1989.328 с.

93. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах Текст. / Под ред. В.И. Варшавского. М.: Наука, 1986.400 с.

94. Ватутин, Э.И. Вспомогательные операции перебора сечений в задаче оптимального разбиения параллельного управляющего алгоритма Текст. / Э.И. Ватутин // Распознавание 2003. Курск: КурскГТУ, 2003. Т. 2. С. 238-239.

95. Ватутин, Э.И. Перебор сечений в задаче оптимального разбиения параллельного управляющего алгоритма Текст. / Э.И. Ватутин, И.В. Зотов // Распознавание — 2003. Курск: КурскГТУ, 2003. Т. 2. С. 235-237.

96. Ватутин, Э.И. Интересные свойства R-выражений в задаче синтеза разбиений параллельных алгоритмов управления Текст. / Э.И. Ватутин // Молодежь и XXI век. Ч. 1. Курск: изд-во КурскГТУ, 2008. С. 30-31.

97. Гордеев, А.В. Системное программное обеспечение Текст. / А.В. Гордеев, А.Ю. Молчанов. СПб.: «Питер», 2003.517 с.

98. Kelly, PJ. A congruence theorem for trees Text. / Paul J. Kelly // Pacific Journal of Mathematics. Vol. 7, № 1,1957. PP. 961-968.

99. Сортировка пузырьком Электронный ресурс. // http://algolist.manual.ru/sort/bubblesort.php, 2006.

100. Сортировка пузырьком Электронный ресурс. // http://ru.wikipedia.org/wiki/CopTHpoBKa пузырьком, 2009.

101. Software Optimization Guide for AMD64 Processors Text. / AMD, 2005. #25112.384 p.

102. Угрюмов, Е.П. Цифровая схемотехника: Учебное пособие для вузов Текст. / Е.П. Уг-рюмов. Спб.: БХВ-Петербург, 2004. 800 с.

103. Ватутин, Э.И. Программная система для нахождения разбиений параллельных алгоритмов логического управления Текст. / Э.И. Ватутин // Распознавание 2005. Курск: изд-во КурскГТУ, 2005. С. 174-177.

104. Елманова, Н. Delphi и технология СОМ Текст. / Н. Елманова, С. Трепалин, А. Тенцер. СПб.: Питер, 2003.698 с.

105. Ватутин, Э.И. Оптимизация обработки множеств Текст. / Э.И. Ватутин // Медико-экологические информационные технологии. Курск: изд-во КурскГТУ, 2005. С. 145-147.

106. Тарловский А.В., Зотов И.В. Библиотека функций для разбиения параллельных алгоритмов логического управления модифицированным методом Баранова // Свидетельство об официальной регистрации программы для ЭВМ № 2006612337 от 05.07.06.

107. Волобуев С.В., Евглевский К.О., Зотов И.В. Библиотека функций для разбиения параллельных управляющих алгоритмов методом Закревского // Свидетельство об официальной регистрации программы для ЭВМ № 2006613146 от 06.09.06.

108. Ватутин, Э.И. Анализ тенденций изменения значений критериев качества разбиений с ростом размера алгоритмов управления Текст. / Э.И. Ватутин, Е.Ю. Кобзарь // Распознавание -2008. Ч. 1. Курск: изд-во КурскГТУ, 2008. С. 89-90.

109. Первый взгляд на DDR3 Электронный ресурс. // http://www.ixbt.coin/mainboard/ddr3-rmma.shtml, 2007.

110. Chu, W.W. Task allocation in distributed data processing Text. / W.W. Chu at al. // IEEE Comput., 1980. № 11. PP. 57-69.

111. Intel 64 and IA-32 Architectures Optimization Reference Manual Text. / Intel Press, 2006. Order number 248966.490 p.

112. Ватутин, Э.И. Проблема оценки интенсивности межблочного взаимодействия в задаче нахождения субоптимальных разбиений параллельных управляющих алгоритмов Электронный ресурс. / ЭЛ. Ватутин // Образование, наука, производство. Белгород, 2006.

113. Волновой алгоритм Электронный ресурс. // http://algolist.manual ли.