Параллельно-последовательный акселератор для быстрого субоптимального разбиения параллельных алгоритмов логического управления тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат технических наук Ватутин, Эдуард Игоревич

• Ватутин, Эдуард Игоревич
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Ватутин, Эдуард Игоревич

ВВЕДЕНИЕ.

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 раза

Список литературы диссертационного исследования кандидат технических наук Ватутин, Эдуард Игоревич, 2009 год

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 ли.