В статье приведена постановка задачи получения диагональных латинских квадратов (ДЛК) заданного порядка N. Показано, что данная задача достаточно просто формулируется, однако для ее решения могут потребоваться как использование эвристических методов, так и ряд алгоритмических приемов, относящихся к алгоритмической и высокоуровневой оптимизации программных средств, учитывающих особенности решаемой задачи (формируемой комбинаторной структуры) и позволяющих повысить темп генерации диагональных латинских квадратов. К ним относятся: использование диагонального порядка заполнения элементов ДЛК; использование статических структур данных вместо размещения их в динамической памяти; учет числа возможных значений для еще не заполненных ячеек квадрата в совокупности с ранним внеочередным заполнением ячеек с и ранним отсечением неперспективных ветвей дерева комбинаторного перебора с ; применение вспомогательных структур данных (одномерных массивов) для быстрого заполнения множеств допустимых элементов ; отключение технологии Hyper-Threading при однопоточной генерации ДЛК в совокупности с ликвидацией фоновой нагрузки на ядра CPU, не используемые в процессе генерации ДЛК; выбор порядка заполнения ячеек квадрата по критерию , что уменьшает арность узлов дерева комбинаторного перебора; использование PGO-компиляции. Для каждой из оптимизаций даны конкретные цифры темпа генерации, измеренного для однопоточной программной реализации на современных процессорах. Показано, что наиболее эффективным является подход на базе метода полного перебора с ранним отсечением неперспективных решений, который при специализированной программной реализации с использованием вложенных циклов обеспечивает темп генерации до 340 000 квадратов в секунду.
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.
The authors declare that there are no conflicts of interest present.