Статья

Название статьи АНАЛИЗ РЕЗУЛЬТАТОВ ПРИМЕНЕНИЯ МЕТОДА СЛУЧАЙНОГО ПЕРЕБОРА В ЗАДАЧЕ ПОИСКА РАЗБИЕНИЙ ГРАФ-СХЕМ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ
Автор Э.И. Ватутин, Д.В. Колясников, В.С. Титов
Рубрика РАЗДЕЛ II. МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ СУПЕРКОМПЬЮТЕРОВ
Месяц, год 12, 2014
Индекс УДК 681.3
DOI
Аннотация Приведено описание метода случайного перебора в задаче построения субоптимальных разбиений параллельных алгоритмов логического управления, возникающей при проектировании однородных многомодульных мультисистем (систем логического управления в базисе логических мультиконтроллеров). С использованием разработанной программной реализации, работающей в составе программной среды PAE, выполнен ряд вычислительных экспериментов, на базе которых произведена оценка скорости сходимости предложенного метода, приведены результаты сопоставления качества оптимизации частных показателей качества с известными эвристическими последовательными методами, показывающие, что при достаточном количестве итераций (1000–10 000) качество решений является приемлемым, однако затраты необходимого вычислительного времени на один-два порядка выше. Полученные результаты позволяют сделать вывод о том, что при ряде сочетаний размерности задачи и силы технологических ограничений предложенный метод имеет преимущество по ряду частных показателей качества, проигрывая по интегральному показателю. Отмечено, что метод случайного перебора является легко распараллеливаемым, что позволяет его исполнение на широком спектре современных параллельных вычислительных средств.

Скачать в PDF

Ключевые слова Дискретная комбинаторная оптимизация; эвристические методы; проектирование мультиконтроллеров; граф-схемы параллельных алгоритмов; разбиения.
Библиографический список 1. Зотов И.В. и др. Организация и синтез микропрограммных мультимикроконтроллеров. – Курск: Изд-во «Курск», 1999. – 368 с.
2. Емельянов С.Г., Зотов И.В., Титов В.С. Архитектура параллельных логических мультиконтроллеров. – М.: Высшая школа, 2009. – 233 с.
3. Ватутин Э.И., Зотов И.В., Титов В.С. и др. Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управления при проектировании логических мультиконтроллеров. – Курск: Изд-во ”Курск”, 2010. – 200 с.
4. Ватутин Э.И. Проектирование логических мультиконтроллеров. Синтез разбиений параллельных граф-схем алгоритмов. – Saarbrьcken: Lambert Academic Publishing, 2011.
– 292 с.
5. https://ru.wikipedia.org/wiki/Числа_Белла.
6. Баранов С.И., Журавина Л.Н., Песчанский В.А. Обобщенный метод декомпозиции граф-схем алгоритмов // А и ВТ. – 1982. – № 5. – С. 43-51.
7. Ватутин Э.И. Библиотека функций построения разбиений методом С.И. Баранова с жадным последовательным формированием блоков // Свидетельство о государственной
регистрации программы для ЭВМ № 2010612902 от 28.04.10.
8. Ватутин Э.И., Леонов М.Е. Использование смежной окрестности при жадном последовательном формировании блоков разбиения граф-схем параллельных алгоритмов // Известия высших учебных заведений. Приборостроение. – 2013. – Т. 56, № 6. – С. 30-35.
9. Ватутин Э.И., Титов В.С. Библиотека функций для построения разбиений с использованием смежной жадной стратегии и последовательным формированием блоков // Свидетельство о государственной регистрации программы для ЭВМ № 2013619395 от 03.10.13.
10. Ватутин Э.И., Зотов И.В. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Параллельные вычисления и задачи управления
(PACO’04). – М.: ИПУ РАН, 2004. – С. 884-917.
11. Ватутин Э.И., Зотов И.В. Параллельно-последовательный метод формирования субоптимальных разбиений параллельных управляющих алгоритмов // Свидетельство об официальной регистрации программы для ЭВМ № 2005613091 от 28.11.05.
12. Ватутин Э.И. Оценка качества разбиений параллельных управляющих алгоритмов на последовательные подалгоритмы с использованием весовой функции // Интеллектуальные и информационные системы (Интеллект-2005). – Тула, 2005. – С. 29-30.
13. Ватутин Э.И., Волобуев С.В., Зотов И.В. Комплексная сравнительная оценка методов выбора разбиений при проектировании логических мультиконтроллеров // Идентификация систем и задачи управления (SICPRO’08). – М.: ИПУ РАН, 2008. – С. 1917-1940.
14. Ватутин Э.И., Волобуев С.В., Зотов И.В. Комплексный сравнительный анализ качества разбиений при синтезе логических мультиконтроллеров в условиях присутствия технологических ограничений // Параллельные вычисления и задачи управления (PACO’08). – М.: ИПУ РАН, 2008. – С. 643-685.
15. Ватутин Э.И., Титов В.С. Сравнение методов синтеза разбиений параллельных алгоритмов логического управления с использованием двухпараметрических диаграмм // Распознавание. – 2012. – С. 138-140.
16. Ватутин Э.И., Титов В.С. Сравнение методов синтеза разбиений граф-схем параллельных алгоритмов с использованием двумерных диаграмм // Известия Юго-Западного государственного университета. – 2012. – № 3 (42). – С. 66-74.
17. Ватутин Э.И., Титов В.С. Использование добровольных распределенных вычислений на платформе BOINC для анализа качества разбиений граф-схем параллельных алгоритмов // Параллельные вычисления и задачи управления (PACO’12). – М.: ИПУ РАН, 2012. – Т. 2. – С. 37-54.
18. Ватутин Э.И., Дремов Е.Н., Мартынов И.А., Титов В.С. Метод взвешенного случайного перебора для решения задач дискретной комбинаторной оптимизации // Известия ВолГТУ. Серия: Электроника, измерительная техника, радиотехника и связь. – 2014. – № 10 (137). – Вып. 9. – С. 59-64.
19. Ватутин Э.И., Колясников Д.В., Мартынов И.А., Титов В.С. Метод случайного перебора в задаче построения разбиений граф-схем параллельных алгоритмов // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов. – Барнаул: Барнаул, 2014. – С. 115-125.
20. Ватутин Э.И., Зотов И.В. Программная система для построения разбиений параллельных управляющих алгоритмов // Труды V Международной конференции «Идентификация систем и задачи управления (SICPRO’06)». – М.: Институт проблем управления им.
В.А. Трапезникова РАН, 2006. – С. 2239-2250.
21. Ватутин Э.И., Зотов И.В. Визуальная среда синтеза разбиений параллельных алгоритмов логического управления // Свидетельство об официальной регистрации программы для ЭВМ № 2007613222 от 30.07.07.

Comments are closed.