Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/31010
Title: Рациональный метод генерации сочетаний для параллельных вычислений в некоторых комбинаторных задачах
Other Titles: Rational method of generation of combinations for parallel calculations in some combinatorial problems
Authors: Дубинин, И. С.
Арапов, С. Ю.
Тягунов, А. Г.
Dubinin, I.S.
Arapov, S. Y.
Tjagunov, A. G.
Issue Date: 2015
Publisher: Уральский федеральный университет
Citation: Дубинин И. С. Рациональный метод генерации сочетаний для параллельных вычислений в некоторых комбинаторных задачах / И. С. Дубинин, С. Ю. Арапов, А. Г. Тягунов // Международная конференция студентов, аспирантов и молодых ученых "Информационные технологии, телекоммуникации и системы управления" : сборник докладов. — Екатеринбург : [УрФУ], 2015. — С. 174-178.
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.
Keywords: СОЧЕТАНИЯ
КОМБИНАТОРНАЯ ОПТИМИЗАЦИЯ
ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ
ALGORITHM
COMBINATORIAL OPTIMIZATION
PARALLEL COMPUTING
URI: http://hdl.handle.net/10995/31010
Conference name: Международная конференция студентов, аспирантов и молодых ученых «Информационные технологии, телекоммуникации и системы управления»
Conference date: 15.12.2014
Origin: Международная конференция студентов, аспирантов и молодых ученых «Информационные технологии, телекоммуникации и системы управления». — Екатеринбург, 2015.
Appears in Collections:Конференции, семинары

Files in This Item:
File Description SizeFormat 
ittisu_2015_29.pdf530,6 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.