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

В статье приведена постановка задачи получения диагональных латинских квадратов (ДЛК) заданного порядка N. Показано, что данная задача достаточно просто формулируется, однако для ее решения могут потребоваться как использование эвристических методов, так и ряд алгоритмических приемов, относящихся к алгоритмической и высокоуровневой оптимизации программных средств, учитывающих особенности решаемой задачи (формируемой комбинаторной структуры) и позволяющих повысить темп генерации диагональных латинских квадратов. К ним относятся: использование диагонального порядка заполнения элементов ДЛК; использование статических структур данных вместо размещения их в динамической памяти; учет числа возможных значений для еще не заполненных ячеек квадрата в совокупности с ранним внеочередным заполнением ячеек с и ранним отсечением неперспективных ветвей дерева комбинаторного перебора с ; применение вспомогательных структур данных (одномерных массивов) для быстрого заполнения множеств допустимых элементов ; отключение технологии Hyper-Threading при однопоточной генерации ДЛК в совокупности с ликвидацией фоновой нагрузки на ядра CPU, не используемые в процессе генерации ДЛК; выбор порядка заполнения ячеек квадрата по критерию , что уменьшает арность узлов дерева комбинаторного перебора; использование PGO-компиляции. Для каждой из оптимизаций даны конкретные цифры темпа генерации, измеренного для однопоточной программной реализации на современных процессорах. Показано, что наиболее эффективным является подход на базе метода полного перебора с ранним отсечением неперспективных решений, который при специализированной программной реализации с использованием вложенных циклов обеспечивает темп генерации до 340 000 квадратов в секунду.

латинские квадраты, дискретная комбинаторная оптимизация, эвристические методы, метод взвешенного случайного перебора, метод муравьиной колонии, задача о булевой выполнимости, алгоритмическая и высокоуровневая оптимизация, Latin squares, discrete combinatorial optimization, heuristic methods, method of weighted accidental exhaustive search, ant colony method, Boolean satisfiability problem, algorithmic and high-level optimization

1. Colbourn C.J., Dinitz J.H. Handbook of Combinatorial Designs. Second Edition. Chapman&Hall, 2006. -984 p.

2. Заикин О.С., Кочемазов С.Е. Поиск пар ортогональных диагональных латинских квадратов порядка 10 в проекте добровольных распределенных вычислений SAT@home // Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика. - 2015. - Т. 4, № 3. - С. 95-108.

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

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

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

6. Dorigo M. Optimization, Learning and Natural Algorithms // PhD thesis. Politecnico di Milano, Italie, 1992.

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

8. Ватутин Э.И., Титов В.С. Об одном подходе к использованию алгоритма муравьиной колонии при решении задач дискретной комбинаторной оптимизации // Интеллектуальные и информационные системы (Интеллект 2015). - Тула, 2015. - С. 8-13.

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

10. Применение высокопроизводительных вычислений для поиска троек взаимно частично ортогональных диагональных латинских квадратов порядка 10 / О.С. Заикин, Э.И. Ватутин, А.Д. Журавлев, М.О. Манзюк // Параллельные вычислительные технологии (ПаВТ'2016). - URL: https://ru.wikipedia.org/wiki/ Раскраска_графов

11. Ватутин Э.И., Зотов И.В. Построение блоков разбиения в задаче декомпозиции параллельных управляющих алгоритмов // Материалы и упрочняющие технологии - 2003. - Т. 2. - Курск, 2003. - С. 38-42.

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

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

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

15. Vatutin E.I., Titov V.S. Voluntary distributed computing for solving discrete combinatorial optimization problems using Gerasim@home project // Distributed computing and grid-technologies in science and education: book of abstracts of the 6th international conference. - Dubna: JINR, 2014. - P. 60-61.

16. Заикин О.С., Посыпкин М.А., Семёнов А.А., Храпов Н.П. Опыт организации добровольных вычислений на примере проектов OPTIMA@home и SAT@home // Вестник Нижегородского университета им. Н.И. Лобачевского. - 2012. - № 5-2. - С. 340-347.

17. Intel 64 and IA-32 Architectures Software Developer’s Manual. Combined Volumes: 1, 2A, 2B, 2C, 3A, 3B and 3C. Intel press, order number 325462-052US, 2014. - 3439 p.

18. Процедурно-модульное программирование на Delphi: учебное пособие / С.Г. Емельянов, Э.И. Ватутин, В.С. Панищев, В.С. Титов. - М.: Аргамак-Медиа, 2014. - 352 с.

19. Biere A., Heule V., van Maaren H., Walsh T. (eds.). Handbook of Satisfiability. IOS Press, 2009. - 980 p.

20. Soos M., Nohl K. Extending SAT Solvers to Cryptographic Problems // Proceedings of the 12th International Conference on Theory and Applications of Satisfiability Testing (SAT’09), 2009. - P. 244-257.