Описание проекта
Системы логического управления (СЛУ) в последнее время получают все большее распространение в связи со все более широким использованием автоматизированных роботизированных сборочных линий, способных осуществлять необходимые операции практически без участия человека (либо сводя подобное участие к минимуму), с одной стороны, и успехами микроэлектроники, неуклонно следующей закону Мура, с другой. Основными сферами применения подобных систем являются:
- Управление в особо ответственных условиях, когда ошибка, вызванная человеческим фактором или какими-либо другими причинами, способна привести к серьезным последствиям техногенного, экономического или социального характера (управление АЭС, ракетами, спутниками и т.д.). К системам подобного класса предъявляются требования высокого быстродействия, отказоустойчивости и, по возможности, низкой аппаратной сложности (ввиду ее влияния на массогабаритные параметры) и стоимости.
- Управление электронными устройствами (процессорами, акселераторами, специализированными вычислителями и т.д.), частота работы которых может доходить до нескольких гигагерц. В этом свете к подобным управляющим системам в первую очередь предъявляются требования высокого быстродействия и низкой стоимости, частично являющейся следствием умеренной аппаратной сложности.
- Управление роботизированными конвейерными линиями или станками с числовым программным управлением, фактически сводящееся к управлению инерционными исполнительными механизмами, не требует высокого быстродействия: на первый план при этом выходят критерии низкой стоимости и возможности оперативной перенастройки СЛУ при изменении состава выполняемых операций (внедрении нового оборудования, изменении состава выпускаемой продукции и т.д.).
Рис. 1. Схематическое обозначение системы логического управления
Среди множества подходов к построению подобных систем управления нами взят за основу подход, ориентированный на использование логических мультиконтроллеров. Логический мультиконтоллер представляет собой множество однотипных программируемых логических контроллеров, совместно управляющих неким объектом (исполнительный механизм, электронное устройство и т.д.). Данный класс устройств сочетает в себе принципы однородности, модульности, отказоустойчивости, высокого быстродействия, умеренной аппаратной сложности и умеренной стоимости. Возможности одного контроллера (обычно выполняется в виде микросхемы) ограничены: он имеет конечное число  ножек (портов) для приема сигналов от датчиков объекта управления (каждый сигнал  является двоичным), конечное число  ножек (портов) для выдачи сигналов управляющих воздействий (так называемых микроопераций,  , также являющихся двоичными сигналами) на объект управления и ограниченную емкость памяти микропрограмм  . С целью упрощения внутренней структуры контроллера обычно (но не всегда) запрещено, чтобы в составе микропрограммы присутствовали параллельные ветви (аналогичным образом устроены и современные процессоры — ассемблерная программа, исполняемая одиночным процессором, является последовательной, а для параллельного исполнения на многоядерном процессоре, кластере или суперкомпьютере сложный параллельный алгоритм разбивается на последовательные фрагменты, каждый из которых выполняется одним процессором). При реализации сложного алгоритма управления (несколько сотен сигналов с датчиков, несколько сотен управляющих воздействий, несколько тысяч вершин в составе граф-схемы алгоритма управления) возможностей одного контроллера может быть недостаточно, поэтому они объединяются в логический мультиконтроллер. Современные мультиконтроллеры могут содержать от нескольких контроллеров, например, объединенных в кольцо, до матриц, гиперкубов или торов из десятков тысяч контроллеров. Проектирование СЛУ на базе подобного мультиконтроллера является нетривиальной задачей и требует решения целого ряда подзадач:
- Разбиение — представление исходной граф-схемы алгоритма в виде множества блоков, каждый из которых удовлетворяет технологическим (может быть выполнен любым контроллером без нарушения ограничений на число входных/выходных сигналов и емкости памяти) и функциональным (не содержит параллельных вершин) ограничениям контроллеров в составе СЛУ.
- Размещение — выбор соответствия между блоками разбиения и контроллерами СЛУ (какой блок исходного параллельного алгоритма попадет в какой контроллер).
- Отказоустойчивость — обеспечение работоспособности СЛУ при наличии некоторого числа неработоспособных контроллеров (например, если в составе системы из 10000 контроллеров нерабочими оказались несколько контроллеров, система должна продолжать работать, возможно с чуть меньшей эффективностью).
- Маршрутизация — обеспечение способности отказоустойчивого обмена данными между любыми контроллерами в системе (в том числе с учетом отказов, которые могут возникать непосредственно во время работы).
- и т.д.
В настоящее время в проекте Gerasim@home производится сравнение методов решения первой задачи. (В перспективе возможно будут добавлены вычислительные модули и для остальных задач.)
Каждую из указанных задач можно решить несколькими способами, причем число возможных решений обычно представляет собой астрономическое число. Например, число разбиений заданной граф-схемы алгоритма на блоки не превосходит числа Белла  (на самом деле в несколько раз меньше из-за того, что не все возможные разбиения корректны, т.е. удовлетворяют ограничениям). Например, при   . Если предположить, что время нахождения одного разбиения составляет 1 миллисекунду, то для построения всех разбиений потребуется  лет вычислительного времени. При  объем необходимого вычислительного времени превышает 100 миллионов лет. Реальные граф-схемы алгоритмов управления могут содержать до нескольких тысяч вершин. Построение множества всех решений производится с целью выбора наилучшего из них, а найденное решение называется оптимальным. Задачи, для которых невозможно получение оптимального решения за примелемое время, называются труднорешаемыми или NP-полными (задача выбора оптимального разбиения относится к этому классу). Для их решения на практике не применяют методы полного перебора всех решений, а ограничиваются рассмотрением лишь их части (итеративные методы) либо синтезом единственного "неплохого" решения (последовательные методы), которое обычно оказывается хуже оптимального не более чем на 1-2% (при использовании хорошего метода). Решения, полученные с использованием подобных эвристических методов, называются субоптимальными.
Различные решения необходимо сравнивать между собой, поэтому при постановке любой оптимизационной задачи вводится понятие критерия качества. Подобным критрием может служить минимальная стоимость, минимальная длина соединений или маршрутов, максимальная вероятность доставки сообщений и т.д. Для задачи разбиения алгоритма подобных критериев несколько, а сама задача является многокритериальной:
- Число блоков разбиения
 . Наиболее важный критерий, косвенно влияет на все остальные критерии. Определяет число контроллеров в системе управления (другими словами, ее аппаратную сложность), не может быть меньше степени параллелизма граф-схемы алгоритма управления [1, 2].
- Степень дублирования логических условий
 .
- Степень дублирования микроопераций
 . В совокупности с предыдущим критерием качества определяют избыточное число дорожек на печатной плате, которые необходимы для соединения выводов контроллеров с объектом управления (другими словами, влияют на сложность и себестоимость производства СЛУ).
- Сложность сети межблочных связей
 . Определяет число микрокоманд передачи управления между контроллерами системы, влияет на глубины очередей и разрядности полей управляющих слов (другими словами, на аппаратную сложность контроллеров).
- Интенсивность межблочных взаимодействий
 . Определяет среднее число передач управления между контроллерами за время выполнения алгоритма управления (межконтроллерный трафик передачи управления). Влияет на быстродействие СЛУ.
Возможны случаи, когда из нескольких решений сложно однозначно выбрать лучшее. Например, одно из решений характеризуется малыми степенями дублирования логических условий и микроопераций, а другое — сложностью сети межблочных связей и интенсивностью межблочных взаимодействий. Для этого числовое значение каждого критерия нормируется (приводится к диапазону  ), умножается на весовой коэффициент (значения коэффициентов выбираются экспертами), полученные значения складываются и образуют интегральный показатель качества  (многокритериальная задача сводится к однокритериальной) [3]:
 \right) = \frac{K_H}{\omega_{max} }H + \frac{K_X}{\left| X \left( A_l^0 \right) \right|} \left( \sum_{i=1}^H \left| X \left( A_i \right) \right| - \left| X \left( A_l^0 \right) \right| \right) + \frac{K_Y}{\left| Y \left( A_l^0 \right) \right|} \left( \sum_{i=1}^H \left| Y \left( A_i \right) \right| - \left| Y \left( A_l^0 \right) \right| \right) +)
 } \delta \left( Sep_{F_k} \left( A_l^0 \right) \right) + \frac{K_{\alpha}}{\omega_{max} \left( \omega_{max} - 1 \right)} \sum_{i=1}^H \sum_{j=1, j \neq i}^H \alpha \left( A_i, A_j \right) "\300dpi J\left( Sep_{F_k} \left( A_l^0 \right) \right) = \frac{K_H}{\omega_{max} }H + )\frac{K_X}{\left| X \left( A_l^0 \right) \right|} \left( \sum_{i=1}^H \left| X \left( A_i \right) \right| - \left| X \left( A_l^0 \right) \right| \right) + \frac{K_Y}{\left| Y \left( A_l^0 \right) \right|} \left( \sum_{i=1}^H \left| Y \left( A_i \right) \right| - \left| Y \left( A_l^0 \right) \right| \right) + \frac{K_{\delta}}{\delta \left( A_l^0 \right) } \delta \left( Sep_{F_k} \left( A_l^0 \right) \right) + \frac{K_{\alpha}}{\omega_{max} \left( \omega_{max} - 1 \right)} \sum_{i=1}^H \sum_{j=1, j \neq i}^H \alpha \left( A_i, A_j \right)")
Разбиение одного и того же алгоритма управления может быть получено различными методами:
- Метод С.И. Баранова (программная реализация Э.И. Ватутина, свидетельство о регистрации № 2010612902) — классический пример "жадного" алгоритма. Последовательный метод, строит разбиение путем включения наиболее подходящих вершин в первый блок пока это возможно, затем во второй и т.д. до тех пор, пока не будут рассмотрены все вершины. Оптимизируется только часть критериев качества.
- Метод А.Д. Закревского (программная реализация С.В. Волобуева, свидетельство о регистрации № 2006613146) — последовательный метод, сводит решение задачи разбиения к задаче раскраски специального графа. Оптимизируется только число блоков (хроматическое число специального графа на языке ПРАЛУ), метод не имеет поддержки технологических ограничений, что является его существенным недостатком.
- Метод параллельно-последовательной декомпозиции (программная реализация Э.И. Ватутина, свидетельство о регистрации № 2005613091) [4] — последовательный метод, разработан на кафедре вычислительной техники Курского государственного технического университета. Выполняет серию предварительных преобразований граф-схемы алгоритма (разрыв циклов [5], объединение линейных участков [6], построение матрицы отношений [7], построение множества сечений алгоритма [8, 9, 10, 11], построение скелетного графа, синтез разбиения [12, 13]), оптимизирует все критерии качества.
- Ряд других методов (полный перебор, ограниченный полный перебор, случайный перебор) и модификации приведенных выше методов.
Рис. 2. Схематическое обозначение предварительных преобразований граф-схем алгоритмов
Эффективность программных реализаций методов синтеза разбиений проанализорована с использованием профайлера, интегрированного в составе программной среды PAE (свидетельство о регистрации № 2007613222) [14]. Программные реализации методов значительно оптимизированы на алгоритмическом уровне, операции с множествами реализованы на ассемблере с оптимизацией под использование векторных расширений MMX и SSE системы команд процессора (свидетельство о регистрации № 2007614221).
Для объективного сравнения методов необходимо проведение ряда вычислительных экспериментов, изучающих особенности методов в различных условиях (при различном изменении размера алгоритма управления, при различных значениях ограничений, при различных значениях параметров методов и различном составе преобразований). Результаты предварительных экспериментов, полученные с использованием PAE, отражены в работах [15, 16, 17, 18, 19]. Целью данного проекта является проведение более подробного сравнения качества решений различных методов (требующего большей вычислительной мощности). Построение большего числа разбиений способно дать более точные "гладкие" графики (уменьшить доверительный интервал). В ходе вычислительных экспериментов планируется проведение более тщательного сравнения методов (переход от однопараметрических графиков к двухпараметрическим диаграммам).
В конечном счете это позволит создавать более эффективные системы логического управления, обладающие меньшей аппаратной сложностью, меньшей себестоимостью производства и большим быстродействием. Кроме того, разработанные алгоритмы преобразований граф-схем алгоритмов могут найти применение в задачах распараллеливания вычислений, при оптимизации программ современными оптимизирующими компиляторами, а также при решении ряда задач теории графов.
По тематике работы опубликовано более 40 научных работ, список наиболее значимых из которых приведен здесь. Результаты исследований использованы при разработке цифрового канала связи для системы управления запорной арматурой (разработчики Э.И. Ватутин, С.Ю. Мирошниченко по заказу ОАО "Прибор", г. Курск), при проектировании системы логического управления роботизированной ячейкой для сборки маломощных электродвигателей постоянного тока, при проектировании системы управления отопительным котлом "Котел-М2М" (разработчик И.В. Зотов по заказу ОАО "Прибор", г. Курск).
Рис. 3. Пример СЛУ: ячейка по сборке электродвигателей
Примеры разбиений алгоритма управления, значения критериев качества, схематичное изображение функциональных схем СЛУ и графа межблочных взаимодействий:
| Разбиение |
Критерии качества |
СЛУ |
 |
 |
 |
 |
 |
 |
 |
 |
 |
При получении расчетного задания (англ. Work Unit, WU) ваш компьютер, на котором установлен менеджер BOINC, строит разбиения выборки алгоритмов управления заданного объема и размера при указанных значениях технологических ограничений, производит оценку полученных результатов (критериев качества) и отправляет результат на сервер. Для каждого критерия качества на сервере расчитывается пара значений: среднее значение критерия качества для выборки алгоритмов заданного размера среди разбиений, полученных выбранным методом ) , и вероятность получения минимального значения критерия качества для выборки алгоритмов заданного размера выбранным методом ) . Среднее значение критериев должно быть по возможности минимальным, а вероятность — максимальной. Полученные значения отображаются в виде двухпараметрических диаграмм и используются для сравнения методов построения разбиений, для оценки влияния различных модификаций и т.д.
Дополнительная литература:
- Зотов И.В., Колосков В.А., Титов В.С. [и др.] Функционально-топологическая организация микропрограммных мультимикроконтроллеров группового логического управления. Тула: издательство ТулГУ, 1997. 226 с. ISBN: 5-7679-0122-8
- Зотов И.В., Титов В.С., Колосков В.А. [и др.] Организация и синтез микропрограммных мультимикроконтроллеров. Курск: изд-во «Курск», 1999. 368 с. ISBN 5-7277-0253-4
- Зотов И.В., Титов В.С., Штейнберг В.И., Стеценко Ю.П., Жданов В.С. Архитектура и синтез параллельных логических мультимикроконтроллеров (учебное пособие, в 2 частях). Курск: издательство Курск, 2006. 200 с. ISBN: 5-7681-0270-1
- Емельянов С.Г., Зотов И.В., Титов В.С. Архитектура параллельных логических мультиконтроллеров. М: Высшая школа, 2009. 233 с. ISBN: 978-5-06-006073-7
- Ватутин Э.И., Зотов И.В., Титов В.С. [и др.] Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управлени при проектировании логических мультиконтроллеров. Курск, изд-во КурскГТУ, 2010. 200 с. ISBN 978-5-7681-0523-5
|