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

М.В. Хачумов,
 н.с., к.ф.-м.н., khmike@inbox.ru

Л.В. Кочина,

инж.-исслед., kochinal@isa.ru

ФИЦ ИУ РАН, Москва

М.В.Шустова

асп., m.v.shustova@gmail.com,

ИПС им. А.К.Айламазяна РАН

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

 

The task of automatic planning of work schedules and choice of specialized computers structures of periodic information processing is considered. Designing of devices is performed by generation of options according to the rules of knowledge base and criteria of quality.

Введение

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

В системах автоматизированного проектирования (САПР) различного назначения все чаще находят применение методы и технологии искусственного интеллекта. Интеллектуализация охватывает все уровни иерархической процедуры проектирования, включая вопросы генерации вариантов проектируемого изделия, оценку и оптимизацию свойств проекта, диалог с пользователем [3,4].

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

Применение ИСАПР дает следующие преимущества:

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

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

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

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

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

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

ЕСЛИ аналог существует, ТО блоком решения производится настройка аналога на проектируемое изделие; результат анализируется на соответствие техническому заданию и проводится моделирование его функционирования;

ЕСЛИ аналог не найден в базе данных, ТО переходят к синтезу вариантов с последующим моделированием, оценкой свойств и выбором оптимального варианта;

 ЕСЛИ вариант не оптимален, ТО переходят к оптимизации и цепочка повторяется, ИНАЧЕ имеем оптимальный вариант.

Схема процесса синтеза представлена на рис.1. В настоящей работе предлагается метод синтеза структуры СВУ, основанный на операциях с алгоритмами функционирования. Генерация вариантов осуществляется на основе оптимизации закрепления процессорных элементов (ПЭ) за фазами алгоритма, отвечающего требованиям одного из видов параллелизма при многократной циклической реализации.

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

 

рис. 1 Схема процесса синтеза структуры вычислителя

2. Оптимизация структуры СВУ периодической обработки

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

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

Под показателем сложности реализации системы ЛА будем понимать общее количество ПЭ ,  используемых в СВУ для организации  требуемого вычислительного процесса (здесь и далее - означает комплекс отмеченных локальных алгоритмов, для которого выполнено закрепление ПЭ за операциями алгоритмов). Под быстродействием понимается среднее время однократной реализации системы ЛА  или время ее -кратной реализации в СВУ. Под показателем надежности  понимается вероятность безотказной работы СВУ при -кратной реализации системы ЛА.

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

            С учетом эвристического критерия качества задача нахождения оптимизированного варианта закрепления процессорных элементов за фазами выполнения последовательного ТП сводится к отысканию такого пути на ярусном орграфе (рис. 2), что:  Здесь  - запрещенное множество сдвигов фаз между одноименными приборами для -го варианта закрепления ПЭ за операциями -го типа, причем  .

Рис. 2  Граф задачи синтеза ТП

Основные положения технологии синтеза периодических ТП с совмещением циклов, основанной на эвристических критериях и правилах, достаточно подробно описаны в серии работ [5,6]. Далее рассмотрим расширение этой задачи на случай наличия нескольких локальных алгоритмов.

3. Синтез периодических расписаний для системы ЛА

Ограничимся рассмотрением задач синтеза СВУ, реализующего относительно простую ограниченную систему ЛА, ориентированную на параллелизм смежных операций и параллелизм независимых ветвей. При этом будем опираться на основные положения работ [5,6].         

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

1) входы  и  являются независимыми, а выходы служат входами ;

2) периодичность следования всех ЛА одинакова.

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

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

При этом результирующий вариант закрепления ПЭ формируется путем простого объединения решений для отдельных ЛА.  Далее задача решается обычным образом, определенным в работах [5,6].

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

. 

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

 .

Поскольку третий подход является общим и дает обычно наилучшие результаты, то остановимся на нем подробнее. Здесь наибольшие затруднения вызывает необходимость учета множества . Причем приходится перебирать допустимые значения сдвига  для каждой зафиксированной системы ОЛА.

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

            На первом этапе решается задача отыскания системы ОЛА с минимальным значением , где .

            На втором этапе осуществляется перебор вариантов упорядочения  ОЛА на основе допустимых сдвигов . Для каждой полученной отмеченной системы алгоритмов определяются значения параметров , на основании чего делается окончательный выбор. Подобный подход позволяет решать задачу с использованием алгоритмов максимального совмещения и оптимизации закрепления ПЭ, изложенных в работах [5,6].

Система ЛА отвечает требованиям параллелизма независимых ветвей, если выполняются следующие требования:

1.  каждая из ветвей представляет собой ЛА или их систему, информационно не связанную с ЛА других ветвей;

2.  выполняется хотя бы одно из условий: все ветви являются разными, т.е. отличаются составом или/и структурой ин­формационных связей; ветви выполняются циклически с разными периодами.

Для построения циклического расписания можно применить два основных подхода. Первый подход соответствует раздельной реализации ветвей, когда каждая из них выполняется на своем множестве ПЭ. При втором подходе имеет место совместная реализация на общем оборудовании. С учетом принятой в настоящей работе модели совмеще­ния циклов обработки, все множество вариантов мо­жет быть получено путем перебора способов объединения отдельных ЛА. При этом достаточно рассмотреть временной участок расписания, равный наименьшему общему кратному периодов.

Проводилась серия экспериментальных исследований, заключающаяся в поиске всевозможных вариантов ОЛА и определении значений критериев качества. Предложенные подходы в выполненной серии исследований подтвердили достаточно хорошее качество построения периодических расписаний и структур СВУ в рамках выбранных критериев качества.

Заключение

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

 

Работа выполнена в рамках проекта РФФИ 16-29-12839 офи_м.

Литература

1.  Фуругян М. Г. Построение периодических расписаний в многопроцессорных системах реального времени. – Материалы 7 международной конференции «Управление развитием крупномасштабных систем». – ИПУ РАН, Москва, 2013, с.444–446.

2.  Фуругян М.Г. Построение периодических расписаний в многопроцессорных АСУ реального времени. – Автоматика и телемеханика, №9, 2000, выпуск 9, с.169-172.

3.  Третьяков А. Автоматизация построения расписаний для периодических систем реального времени. – Труды Института системного программирования РАН, том 22, 2012, с.375-400. URL: http://www.ispras.ru/proceedings/docs/2012/22/isp_22_2012_375.pdf

4.  Семенов В.С., Золотов В.П. Системы автоматизации проектных работ. Курс лекций. / В.С. Семенов, В.П. Золотов.  Самара: Самар. гос. техн. ун-т, 2012. – 134 с.

5.  Хачумов В.М. Модели конвейерного медицинского технологического процесса. – Искусственный интеллект и принятие решений, №3, 2009, с.25-32.;

6.  Хачумов В.М. Основные принципы моделирования сложных систем и процессов (Учебное пособие). – М.: Изд-во Российского университета дружбы народов, 2013. – 141 с.