CONSIDERATION OF ALGORITHMIC SPECIFIC FEATURES OF THE TASK WHEN GENERATING DIAGONAL LATIN SQUARES

The article describes the problem statement for generation of diagonal Latin squares (DLS) of preassigned order N. It is indicated that this problem is fairly simply specified. However, to solve this problem it is necessary to apply both heuristic methods and a number of algorithmic techniques related to software algorithmic and high-level optimization which take into account specific features of the current task (generated combinatorial structure) and allow increasing the rate of DLS generation. They include the use of the diagonal order of filling the elements of DLS; the use of static data structures instead of placing them in the heap memory; taking into account the number of possible values for square slots which have not been filled yet together with early out-of-sequence filling of slots with and early pruning of unpromising lines of combinatorial search with ; the use of auxiliary data structures (one-dimensional arrays) for the quick filling of the sets of admissible elements ; Hyper-Threading technology disabling in the single-threaded DLS generation together with the elimination of the background load on the CPU cores which are not used in the DLS generation; the choice of the order of filling the square slots according to the criterion of which reduces the arity of tree nodes of combinatorial search; application of PGO-compilation. For each of the optimizations specific numbers of generation rate measured for single-threaded software implementation in modern processors are given. It is indicated that the most effective approach is based on the exhaustive method of early pruning of unpromising solutions. It provides the rate of generation of 340,000 squares per second when specialized software using nested loops is implemented.

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