ПОСТРОЕНИЕ РАЗБИЕНИЙ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ЛОГИЧЕСКОГО УПРАВЛЕНИЯ ПРИ СИНТЕЗЕ ПАРАЛЛЕЛЬНЫХ ЛОГИЧЕСКИХ МУЛЬТИКОНТРОЛЛЕРОВ Санкт-Петербург, 2009 Курский. - презентация

1 ПОСТРОЕНИЕ РАЗБИЕНИЙ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ЛОГИЧЕСКОГО УПРАВЛЕНИЯ ПРИ СИНТЕЗЕ ПАРАЛЛЕЛЬНЫХ ЛОГИЧЕСКИХ МУЛЬТИКОНТРОЛЛЕРОВ Санкт-Петербург, 2009 Курский государственный технический университет Кафедра вычислительной техники Ватутин Эдуард Игоревич 1 Стратегическое партнерство вузов и предприятий радиоэлектронной промышленности

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

3 Объект управления и система логического управления 3

4 Постановка задачи Задача многокритериальной оптимизации на дискретной структуре (графе), NP-трудная задача 4

5 Критерии качества разбиения ; Схожие задачи решались школой В.М. Курейчика (г. Таганрог) при трассировке печатных плат (аналогия: H – число слоев, Z 1 – число связей между слоями) 5

6 Пример разбиения: одно из возможных разбиений (получено с использованием программной системы PAE) 6

7 Программно-аппаратный комплекс PAE для синтеза разбиений 7 Объем исходного кода: более строк, 971 КБ.

8 Обзор методов синтеза разбиений Методы синтеза разбиений: полного перебора (NP-трудная задача); (взвешенного) случайного перебора (Монте-Карло); метод С.И. Баранова (жадный алгоритм); метод А.Д. Закревского (задача раскраски графа); параллельно-последовательный метод (специализированный метод); генетические алгоритмы. Качество синтезируемых разбиений, временные и емкостные сложности методов существенно различны. Методы получения числовых оценок: определение степени параллелизма алгоритма управления (нижняя оценка числа блоков в разбиении); оценка интенсивности межблочных взаимодействий. 8

9 Понятие сечений 9

10 Понятие системы R-выражений 10

11 Пример выделения базового сечения … 11

12 Построение множества смежных сечений 12

13 Представление R-выражения в виде дерева 13

14 Характеристики качества разбиений выборки из K алгоритмов 14

15 Эксперимент: влияние ограничений 1.Параллельно-последовательный метод позволяет получать разбиения лучшего качества в условиях присутствия технологических ограничений. 2. В случае необходимости более сильной оптимизации одного из критериев существует возможность изменения значения соответствующего весового коэффициента. Критерий Ограничения Очень сильные X max < 5 W max < 11–12 Сильные 5 < X max < 12–15 11–12 < W max < 32–36 Слабые 12–15 < X max 32–36 < W max HPSM PSM Bar (X) Bar (Y) BarPSM PSM PSM Bar fPSM Bar 15

16 Эксперимент: влияние размера алгоритмов на качество разбиений в условиях присутствия сильных ограничений Количество блоков H 16

17 Анализ временных затрат Временные затраты на синтез разбиения алгоритма из вершин (приблизительно): Метод С.И. Баранова – 0,97 с * Метод А.Д. Закревского – 7,3 дней Параллельно-последовательный метод – 1,1 месяца … 4,5 года * без учета временных затрат на синтез матрицы отношений! 17

18 Ячейка однородной среды электронной модели дерева Возможности однородной среды: прямое чтение данных; многопортовое чтение данных; запись данных; ассоциативная запись данных. 18

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

20 Операция проверки изоморфного вхождения R-выражений Уменьшение времени обработки – в N 2 /k раз 20

21 Структурно-функциональная организация акселератора 21 Уменьшение времени обработки R-выражений в 1000 – раз

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

23 Примеры практического использования: система управления отопительным котлом Котел-M2M 23 Серийно выпускается ОАО «Прибор» (г. Курск)

24 Примеры практического использования: система удаленного управления запорной арматурой 24 Ведется разработка в ОАО «Прибор» (г. Курск)

25 1. Ватутин Э.И. Программа поиска базового сечения параллельного управляющего алгоритма // Молодежь и XXI век: Тезисы докл. XXXI вузовской научноо.-техн. конф. студ-тов и аспир-ов в области научноо. иссл-ий / Курск. гос. техн. ун-т. Курск, Ч. 3. С. 85– Поиск базового сечения в задаче разбиения параллельных алгоритмов / Ватутин Э.И., Зотов И.В.; КГТУ. Курск, с. Рус. деп. в ВИНИТИ B Ватутин Э.И., Зотов И.В., Титов В.С. Построение множества сечений в задаче оптимального разбиения параллельных управляющих алгоритмов // Известия ТулГУ. Вычислительная техника. Информационные технологии. Системы управления. Тула: ТулГУ, Т. 1. Вып. 2. С. 70– Ватутин Э.И., Зотов И.В. Перебор сечений в задаче оптимального разбиения параллельного управляющего алгоритма // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: Тезисы докл. 6 международной конф. Распознавание КГТУ. Курск, Т. 2. С. 235– Ватутин Э.И. Вспомогательные операции перебора сечений в задаче оптимального разбиения параллельного управляющего алгоритма // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: Тезисы докл. 6 международной конф. Распознавание КГТУ. Курск, Т. 2. С. 238– Ватутин Э.И., Зотов И.В. Построение блоков разбиения в задаче декомпозиции параллельных управляющих алгоритмов / Сборник материалов РНТК «Материалы и упрочняющие технологии – 2003», Курск. гос. техн. ун-т. Курск, – Т. 2. С.38– Ватутин Э.И., Зотов И.В. Параллельно-последовательный метод формирования субоптимальных разбиений // Международный сборник научнооых трудов «Информационные технологии моделирования и управления». Воронеж: «Научная книга», Вып. 12. С. 64– Ватутин Э.И., Зотов И.В. Построение матрицы отношений в задаче оптимального разбиения параллельных управляющих алгоритмов // Известия курского государственного технического университета. Курск, С. 85– Ватутин Э.И., Зотов И.В. Параллельно-последовательный синтез разбиений параллельных управляющих алгоритмов // Образование, наука, производство: Сб. тез. докл. II Международного студенческого форума. Белгород: Изд-во БГТУ им. В.Г. Шухова, Ч. 6. С Публикации авторов по теме 25

26 10. E.I. Vatutin, J.N. Abdel-Galil, I.V. Zotov. Method for the separation of a class of parallel algorithms with inter-module traffic optimization // Information and Telecommunication Technologies in Intelligent Systems. Barselona, PP. 105– Ватутин Э.И., Зотов И.В. Идентификация и разрыв последовательных циклов в задаче субоптимального разбиения параллельных управляющих алгоритмов // Известия ТулГУ. Серия: Вычислительная техника. Информационные технологии. Системы управления. Т. 1. Вып. 3. Вычислительная техника. Тула: изд-во ТулГУ, С. 51– Ватутин Э.И., Зотов И.В. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Труды II международной конференции «Параллельные вычисления и задачи управления» PACO 04 памяти Е.Г. Сухова. М.: Институт проблем управления им. В.А. Трапезникова РАН, С. 884– Ватутин Э.И., Зотов И.В. Решение задачи субоптимального разбиения параллельных управляющих алгоритмов // Материалы межрегиональной научнооо-технической конференции «Интеллектуальные и информационные системы». Тула, изд-во ТулГУ, С. 62– Ватутин Э.И. Объединение линейных участков в задаче нахождения субоптимальных разбиений параллельных управляющих алгоритмов // Молодежь и XXI век: тезисы докладов XXXII вузовской научнооо-технической конференции студентов и аспирантов в области научнооых исследований. Курск: изд-во КурскГТУ, Ч. 1. С. 22– Ватутин Э.И. Программная система для нахождения разбиений параллельных алгоритмов логического управления // Распознавание 2005: сборник материалов 7-й международной конференции. Курск, изд-во КурскГТУ, С. 174– Ватутин Э.И., Зотов И.В. Параллельно-последовательный метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Свидетельство об официальной регистрации программы для ЭВМ от Волобуев С.В., Ватутин Э.И. Библиотека функций разбиения управляющих алгоритмов методом Закревского // Тезисы докладов XXXIII вузовской научнооо-технической конференции студентов и аспирантов в области научнооых исследований «Молодежь и XXI век». Ч. 1. Курск: изд-во КурскГТУ, С. 20– Ватутин Э.И., Евглевский К.О. Псевдослучайное разбиение параллельных управляющих алгоритмов // Тезисы докладов XXXIII вузовской научнооо-технической конференции студентов и аспирантов в области научнооых исследований «Молодежь и XXI век». Ч. 1. Курск: изд-во КурскГТУ, С. 24– Ватутин Э.И., Зотов И.В. Программная система для построения разбиений параллельных управляющих алгоритмов // Труды V международной конференции «Идентификация систем и задачи управления (SICPRO06)». М.: Институт проблем управления им. В.А. Трапезникова РАН, С. 2239–2250. Публикации авторов по теме 26

27 20. Vatutin E.I. Constructing Random Sample Parallel Logic Control Algorithms // 11 th International Student Olympiad on Automatic Control (Baltic Olympiad BOAC06). Saint-Petersburg, PP. 162– E.I. Vatutin, J.N. Abdel-Jalil, M.H. Najajra, I.V. Zotov. Comparison of Methods for Getting Separation of Parallel Logic Control Algorithms // Information and Telecommunication Technologies in Intelligent Systems (ITT IS06). Katania, Italy, PP. 92– Ватутин Э.И. Проблема оценки интенсивности межблочного взаимодействия в задаче нахождения субоптимальных разбиений параллельных управляющих алгоритмов [Электронный ресурс] / III международный студенческий фестиваль «Образование, наука, производство». Белгород, Ватутин Э.И. Оценка качества разбиений параллельных управляющих алгоритмов на последовательные под алгоритмы с использованием весовой функции // Материалы межрегиональной научнооо-технической конференции «Интеллектуальные и информационные системы» (Интеллект-2005). – Тула, С. 29– Борзов Д.Б., Ватутин Э.И., Зотов И.В., Титов В.С. К задаче субоптимального разбиения параллельных алгоритмов // Известия вузов. Приборостроение. Вып. 12, С. 34– Ватутин Э.И., Зотов И.В. Библиотека классов для имитационного моделирования коммуникационных сетей // Свидетельство об официальной регистрации программы для ЭВМ от Зотов И.В., Крикунов О.В., Наджаджра М.Х., Ватутин Э.И. Визуальная среда имитационного моделирования VisualQChart // Свидетельство об официальной регистрации программы для ЭВМ от Ватутин Э.И. Методология сравнительной оценки методов нахождения разбиений параллельных алгоритмов логического управления при синтезе логических мульти контроллеров // Информационно-математические технологии в экономике, технике и образовании. – Екатеринбург, С. 259– Ватутин Э.И. Сравнительная оценка методов нахождения разбиений параллельных алгоритмов логического управления в условиях присутствия технологических ограничений // Информационно-математические технологии в экономике, технике и образовании. – Екатеринбург, С. 261– Ватутин Э.И., Зотов И.В. Визуальная среда синтеза разбиений параллельных алгоритмов логического управления // Свидетельство об официальной регистрации программы для ЭВМ от Публикации авторов по теме 27

28 30. Ватутин Э.И., Волобуев С.В., Зотов И.В. Комплексная сравнительная оценка методов выбора разбиений при проектировании логических мульти контроллеров // Труды VII международной конференции «Идентификация систем и задачи управления» SICPRO08. М.: Институт проблем управления им. В.А. Трапезникова РАН, С. 1917– Ватутин Э.И., Зотов И.В. Аппаратная модель для определения минимального числа блоков при декомпозиции параллельных алгоритмов логического управления // Известия вузов. Приборостроение Т. 51, 2. С. 39– Ватутин Э.И., Кобзарь Е.Ю. Анализ тенденций изменения значений критериев качества разбиений с ростом размера алгоритмов управления // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание – 2008). Ч. 1. Курск: изд-во КурскГТУ, С. 89– Ватутин Э.И. Однородная среда электронной модели дерева для аппаратно-ориентированной обработки R- выражений // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание – 2008). Ч. 1. Курск: изд-во КурскГТУ, С. 90– Ватутин Э.И. Интересные свойства R-выражений в задаче синтеза разбиений параллельных алгоритмов управления // Тезисы докладов XXXVI межвузовской научнооо-технической конференции студентов и аспирантов в области научнооых исследований «Молодежь и XXI век». Ч. 1. Курск: изд-во КурскГТУ, С. 30– Силаев С.В., Ватутин Э.И. Оценка интенсивности межблочных взаимодействий с использованием дерева фрагментов в задаче синтеза разбиений алгоритмов управления // Тезисы докладов XXXVI межвузовской научнооо- технической конференции студентов и аспирантов в области научнооых исследований «Молодежь и XXI век». Ч. 1. Курск: изд-во КурскГТУ, С. 48– Шумаков В.А., Ватутин Э.И. Разбиение алгоритмов логического управления на блоки методом полного перебора // Тезисы докладов XXXVI межвузовской научнооо-технической конференции студентов и аспирантов в области научнооых исследований «Молодежь и XXI век». Ч. 1. Курск: изд-во КурскГТУ, С. 53– Ватутин Э.И. Оценка степени параллелизма алгоритма с использованием матрицы отношений // Материалы IV международной научнооо-технической конференции «Современные инструментальные системы, информационные технологии и инновации». Ч. 2. Курск: изд-во КурскГТУ, С. 135–139. Публикации авторов по теме 28

29 38. Ватутин Э.И., Зотов И.В. Повышение качества разбиения алгоритмов при синтезе логических мульти контроллеров с использованием метода параллельно-последовательной декомпозиции // Перспективы развития систем управления оружием: сборник докладов IV научнооо-практической конференции, Курск, сентября 2007 г. – М.: Изд-во «Бедретдинов и Ко», – С. 84– Vatutin E.I. Parallel Logic Control Algorithm Separation Quality Analysis in the Synthesis of Logic Multicontrollers // 12 th International Student Olympiad on Automatic Control (Baltic Olympiad, BOAC'08). Saint-Petersburg, PP. 95– Ватутин Э.И., Волобуев С.В., Зотов И.В. Комплексный сравнительный анализ качества разбиений при синтезе логических мульти контроллеров в условиях присутствия технологических ограничений // Труды четвертой международной конференции «Параллельные вычисления и задачи управления» PACO08. М.: Институт проблем управления им. В.А. Трапезникова РАН, С. 643– Ватутин Э.И., Зотов И.В., Титов В.С. Использование схемных формирователей и преобразователей двоичных последовательностей при построении комбинаторно-логических акселераторов // Известия КурскГТУ, (25). С. 32– Ватутин Э.И., Зотов И.В. Анализ качества блочных разбиений при синтезе логических мульти контроллеров // Программируемые инфокоммуникационные технологии. Сборник статей. М.: «Радиотехника», С. 32– Ватутин Э.И., Зотов И.В. Анализ качества блочных разбиений при синтезе логических мульти контроллеров // Информационно-измерительные и управляющие системы. 10, Т. 6. М.: «Радиотехника», С. 32– Ватутин Э.И., Зотов И.В., Титов В.С. Выявление изоморфных вхождений R-выражений при построении множества сечений параллельных алгоритмов логического управления // Известия вузов. Приборостроение Т. 52, 2. С. 37–45. Публикации авторов по теме 29 WWW: ICQ: