WEIGHED RANDOM SELECTION METHOD FOR CONSTRUCTION OF PARTITIONING OF PARALLEL ALGORITHMS FLOWGRAPHS FOR LOGIC MULTICONTROLLERS DESIGNING

The article describes the peculiarities of using weighted random selection method when solving a task of searching for sub-optimal partitions of parallel algorithms flowgraphs-that arises in designing systems of logical control in the basis of logical multicontrollers (LMC). A review of known methods of solving the problem is presented. Most of these methods are ‘greedy’ successive methods (except random selection method) and provide solutions of good quality in various areas of three-dimensional space formed by the dimensionality of problem N and technological limitations X_max, W_max of the LMC basis due to the presence of zone dependence. Combining the best aspects of ‘greedy’ and random approaches, it is possible to develop of a method that distributes the vertices in the blocks of the partition based on the weighting heuristics with aт adjustable degree of dispersion D relative to a greedy evaluation of the increment of solution quality. Special software was designed for this method; using this software a series of computational experiments has been carried out. In the course of matho-optimization, it was found that the optimal degree of dispersion D*=zero, which differs from the behaviour of the method in other problems of discrete combinatorial optimization and provides the iterative nature of the method only due to variation of the order of consideration of vertices. A computational experiment was carried out for the software implementation of the method using the indicated degree of dispersion. The experiment showed the advantage in terms of the quality of the output solutions for all quality parameters except for the intensity interblock interactions. At the same time, the working time of the method is 43 times more than that of the method of random selection and is limited by the time of evaluation of the quality of the generated partitioning.

дискретная комбинаторная оптимизация, граф-схемы параллельных алгоритмов, разбиения, взвешенный случайный перебор, 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.