Рациональный метод генерации сочетаний для параллельных вычислений в некоторых комбинаторных задачах

Abstract

Целью данной статьи являлась разработка нового способа нумерации сочетаний. Его особенностью является отсутствие в алгоритме циклов и ветвлений, что позволяет эффективно использовать его в многопоточном режиме. Для выполнения поставленной задачи были произведены разработка алгоритма, нахождение оптимального способа вычисления требуемых величин и оптимизация под многопоточные системы. По сравнению с классическими, данный метод показывает заметное увеличение производительности даже не в самых благоприятных условиях. Особенностью полученного алгоритма является независимое выполнение разных потоков вычисления, что очень важно при выполнении программы на процессорах SIMD архитектуры. Таким образом, разработанный способ нумерации имеет очевидные преимущества и может быть использован в задачах, решаемых методами комбинаторной оптимизации.

The purpose of this paper is development of a new method of numbering combinations. Its feature is the absence of loops and branches in the algorithm, which allows using it effectively multithreaded. For this purpose the following tasks have been produced: development of an algorithm, finding an optimal method for calculating the required values and optimization for multi-threaded system. Compared to classical ones, proposed method showed a significant performance increase even in adverse conditions. Thus, the developed algorithm of numbering has obvious advantages, and can be used in tasks, solved by methods of combinatorial optimization.