Optimization of permanent decomposition procedures using parallelization algorithm

Abstract

EN: Context. The problem of efficiently finding all permutations of a list of N elements is a key problem in many areas of computer science, such as combinatorics, optimization, cryptography, and machine learning. The object of the study was to analyze the procedure of permanent decomposition and propose an algorithm for its parallelization using modern features of working with threads in C#. Objective. The goal of the work is the creation of the algorithm for parallelizing the generation of permutations using permanent decomposition processes. Method. The main research method is the comparison of various algorithms with proposed parallelized algorithm, taking into account such criteria as accuracy and speed. Scientific works [10, 9, 17] present algorithms, including the regular permanent decomposition algorithm and the Johnson-Trotter algorithm. The Johnson-Trotter’s algorithm is one of the most effective, so it has been taken as some kind of benchmark. It is worth mentioning that each paralleling process has its own disadvantages, including additional resources needed fot data synchronization between threads. This can be minimized using both technical abilities of modern programming languages and optimization of the algorithm itself. Results. The developed parallelized algorithm have improved performance of the regular permanent decomposition algorithm for solving the problem of finding all permutations. Conclusions. The conducted experiments have confirmed the proposed parallelized algorithm’s version is better from a performance standpoint than the regular one. The prospects for further research may include the application of the parallelized version of the algorithm to some practical tasks and comparison of the results. UK: Актуальність. Задача ефективного знаходження всіх перестановок списку з N елементів є ключовою проблемою в багатьох областях комп’ютерних наук, таких як комбінаторика, оптимізація, криптографія та машинне навчання. Мета дослідження – проаналізувати процедуру перманентної декомпозиції та запропонувати алгоритм для її розпаралелювання з використанням сучасних можливостей роботи з потоками в мові C#. Мета роботи – метою роботи є створення алгоритму для розпаралелювання генерації перестановок з використанням перманентних процесів декомпозиції. Метод. Основним методом дослідження є порівняння різних алгоритмів із запропонованим розпаралелеленим алгоритмом з урахуванням таких критеріїв, як точність та швидкість. У наукових працях [10, 9, 17] представлено алгоритми, серед яких регулярний алгоритм перманентної декомпозиції та алгоритм Джонсона-Троттера. Алгоритм Джонсона-Троттера є одним з найефективніших, тому його було взято за певний еталон. Варто зазначити, що кожен процес розпаралелювання має свої недоліки, зокрема, додаткові ресурси, необхідні для синхронізації даних між потоками. Це можна мінімізувати, використовуючи як технічні можливості сучасних мов програмування, так і оптимізацію самого алгоритму. Результати. Розроблений розпаралелений алгоритм дозволив покращити продуктивність звичайного алгоритму перманентної декомпозиції для розв’язання задачі знаходження всіх перестановок. Висновки. Проведені експерименти підтвердили, що запропонована розпаралелена версія алгоритму є кращою з точки зору продуктивності, ніж звичайна. Перспективами подальших досліджень може бути застосування розпаралеленої версії алгоритму до деяких практичних задач та порівняння отриманих результатів.