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

В статье приведено описание особенностей использования метода взвешенного случайного перебора в задаче поиска субоптимальных разбиений граф-схем параллельных алгоритмов, возникающей при проектировании систем логического управления в базисе логических мультиконтроллеров (ЛМК). Приведен обзор известных методов решения поставленной задачи, большинство из которых являются жадными последовательными методами (за исключением метода случайного перебора) и обеспечивают получение решений неплохого качества в различных областях трехмерного пространства, образованного размерно-стью задачи N и технологическими ограничениями X_max и W_max базиса ЛМК за счет наличия зонной зависимости. Комбинируя лучшие стороны жадного и случайного подходов, возможна разработка метода, производящего распределение вершин по блокам разбиения исходя из расчета взвешивающей эвристики с настраиваемой степенью разброса D относительно жадной оценки приращения качества решения. Для указанного метода разработана программная реализация, с использованием которой проведен ряд вычислительных экспериментов. В ходе метаоптимизации выяснено, что оптимальная степень разброса D*=0, что отличается от поведения метода в других задачах дискретной комбинаторной оптимизации и обеспечивает итерационный характер метода только за счет вариации порядка рассмотрения вершин. С указанной степенью разброса для программной реализации метода был реализован вычислительный эксперимент, который показал ее преимущество по качеству результирующих решений по всем показателям качества за исключением интенсивности межблочных взаимодействий. При этом время работы метода в 43 раза больше метода случайного перебора и лимитируется временем оценки качества формируемого разбиения.

дискретная комбинаторная оптимизация, граф-схемы параллельных алгоритмов, разбиения, взвешенный случайный перебор, discrete combinatorial optimization, parallel algorithms flowgraphs, partitioning, weighted random selection

1. Организация и синтез микропрограммных мультимикроконтроллеров / И.В. Зотов, В.А. Колосков, В.С. Титов [и др.]. Курск, 1999. 368 с.

2. Емельянов С.Г., Зотов И.В., Титов В.С. Архитектура параллельных логических мультиконтроллеров. М.: Высшая школа, 2009. 233 с.

3. Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управления при проектировании логических мультиконтроллеров / Э.И. Ватутин, И.В. Зотов, В.С. Титов [и др.]. Курск, 2010. 200 с.

4. Ватутин Э.И. Проектирование логических мультиконтроллеров. Синтез разбиений параллельных граф-схем алгоритмов. Saarbrücken: Lambert Academic Publishing, 2011. 292 с.

5. Ватутин Э.И., Титов В.С., Емельянов С.Г. Основы дискретной комбинаторной оптимизации. М.: Аргамак-Медиа, 2016. 270 с.

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

7. Ватутин Э.И., Леонов М.Е. Использование смежной окрестности при жадном последовательном формировании блоков разбиения граф-схем параллельных алгоритмов // Известия высших учеб-ных заведений. Приборостроение. 2013. Т. 56, № 6. С. 30-35.

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

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

10. Метод случайного перебора в задаче построения разбиений граф-схем параллельных алгоритмов / Э.И. Ватутин, Д.В. Колясников, И.А. Мартынов, В.С. Ти-тов // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов. Барнаул, 2014. С. 115-125.

11. Ватутин Э.И., Колясников Д.В., Титов В.С. Анализ результатов применения метода случайного перебора в задаче поиска разбиений граф-схем параллельных алгоритмов // Известия Южного федерального университета. Технические науки. 2014. № 12 (161). С. 102-110.

12. Ватутин Э.И., Волобуев С.В., Зотов И.В. Комплексная сравнительная оценка методов выбора разбиений при проектировании логических мультиконт-роллеров // Идентификация систем и задачи управления (SICPRO’08). М.: ИПУ РАН, 2008. С. 1917-1940.

13. Ватутин Э.И., Волобуев С.В., Зотов И.В. Комплексный сравнительный анализ качества разбиений при синтезе логических мультиконтроллеров в условиях присутствия технологических ограничений // Параллельные вычисления и задачи управления (PACO’08). М.: ИПУ РАН, 2008. С. 643-685.

14. Ватутин Э.И., Титов В.С. Сравнение методов синтеза разбиений параллельных алгоритмов логического управления с использованием двухпараметрических диаграмм // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание - 2012). Курск, 2012. С. 138-140.

15. Ватутин Э.И., Титов В.С. Сравнение методов синтеза разбиений граф-схем параллельных алгоритмов с использованием двумерных диаграмм // Известия Юго-Западного государственного университета. 2012. № 3 (42). С. 66-74.

16. Ватутин Э.И., Титов В.С. Использование добровольных распределенных вычислений на платформе BOINC для анализа качества разбиений граф-схем параллельных алгоритмов // Параллельные вычисления и задачи управления (PACO’12). М.: ИПУ РАН, 2012. С. 37-54.

17. Ватутин Э.И., Титов В.С. Анализ областей качественного превосходства последовательных эвристических методов синтеза разбиений при проектировании логических мультиконтроллеров // Известия высших учебных заведений. Приборостроение. 2015. Т. 58, № 2. С. 115-122.

18. Анализ вероятности получения субоптимальных решений при использовании смежной жадной стратегии синтеза разбиений / В.С. Титов, Э.И. Ватутин, С.Ю. Валяев, А.Л. Андреев // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание - 2015). Курск, 2015. С. 363-365.

19. Vatutin E.I., Valyaev S.Yu., Titov V.S. Comparison of Sequential Methods for Getting Separations of Parallel Logic Control Algorithms Using Volunteer Computing // CEUR Workshop Proceedings. Proceedings of the Second International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2015). Vol. 1502. Technical University of Aachen, Germany. 2015, pp. 37-51.

20. Ватутин Э.И., Валяев С.Ю., Титов В.С. Анализ результатов применения метода случайного перебора при построении разбиений граф-схем параллельных алгоритмов в зависимости от размерности задачи и силы ограничений // Перспективные информационные технологии (ПИТ 2016). Самара: изд-во Самарского научного центра РАН, 2016. С. 481-486.

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

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

23. Ватутин Э.И. Определение степени параллелизма параллельной граф-схемы алгоритма // Интеллектуальные и информационные системы (Интеллект-2009). Тула, 2009. С. 24-26.

24. Метод взвешенного случайного перебора для решения задач дискретной комбинаторной оптимизации / Э.И. Ватутин, Е.Н. Дремов, И.А. Мартынов, В.С. Ти-тов // Известия ВолГТУ. Серия: Электроника, измерительная техника, радиотехника и связь. 2014. № 10 (137). Вып. 9. С. 59-64.

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

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

27. Vatutin E.I. Constructing Random Sample Parallel Logic Control Algorithms // 11th International Student Olympiad on Automatic Control (Baltic Olympiad, BOAC’06). Saint-Petersburg, 2006, pp. 162-166.

28. Особенности использования взвешивающих эвристик в задаче поиска диагональных латинских квадратов / Э.И. Ватутин, А.Д. Журавлев, О.С. Заикин, В.С. Титов // Известия Юго-За-падного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2015. № 3 (16). С. 18-30.

29. Пшеничных А.О., Ватутин Э.И. Анализ качества решений метода взвешенного случайного перебора в задаче эвристической оценки хроматического числа графа // Интеллектуальные и информационные системы (Интеллект - 2017). Тула, 2017. С. 20-28.

30. Ватутин Э.И., Титов В.С. Анализ скорости сходимости качества решений эвристических методов в задаче поиска кратчайшего пути в графе // Информационно-измерительные диагностирующие и управляющие системы (Диагностика - 2016). Курск, 2016. С. 19-25.

31. Land A.H., Doig A.G. An Automatic Method of Solving Discrete Program-ming Problems // Econometrica. 1960. Vol. 28, pp. 497-520.