A parallel algorithm for generating combinatorial objects - combinations without repetition of the three elements was developed. The basis of the algorithm is the reverse lexicographic order of counting of combinations. The resulting algorithm does not contain conditional branches and loops, but uses a root function and the rounding. A perspective area of application of this algorithm is solving combinatorial problems on multiprocessor systems with SIMD architecture (in particular, on graphics cards). The developed algorithm has been tested on practical problems. During computing experiment there was a significant acceleration of the calculation of elements combinations from combination’s index relative to the classical methods. Multithreaded experiment showed that the performance of the algorithm scales, but the limiting factor is the overhead of the software environment. When using this method on the cards, you can expect further growth in productivity. ·
Translated title of the contributionMethod of generating combinations for parallel computing based on the reverse lexicographic order
Original languageRussian
Pages (from-to)40-46
Number of pages7
JournalВестник Санкт-Петербургского государственного университета технологии и дизайна. Серия 1: Естественные и технические науки
Issue number4
Publication statusPublished - 2015

    Level of Research Output

  • VAK List

    GRNTI

  • 27.45.00

ID: 1793262