Analysis of the use of multithreaded computing technologies to factorize of numbers by a binary algorithm

Abstract

EN: Context. Providing high-speed computation by computer systems of factorization of number into prime factors requires the development of effective algorithmic methods using computational technologies. Fast computation of factorization of numbers is used in such applications as, protection of information data, in algorithms of discrete transforms for transition from one to multidimensional computations and others. Objective. The purpose of the work is to analyze the implementation of technologies of multithreaded computation of factorization of integer value by the binary algorithm of the method of trial divisions using computer systems with multi-core processors and graphics accelerators. Method. A binary algorithm of trial divisions that uses the remainders of each digit of the binary representation of a number to perform a divisibility check on prime factors of the canonical factorization of number in parallel. Results. The analysis and comparison of multithreaded computations of software implementations of factorization of number by binary algorithm using hyper-threading, AMP C++, CUDA technologies in computer systems with multi-core processors and graphics accelerators. The results of the process of number factorization for multithreaded computing technologies using the same parallel core function are analyzed. Conclusions. In the study of realizations of number factorization by the binary algorithm in the multithreaded mode, the technology of hyper-threading calculations using multicore processors is most effectively performed. Heterogeneous computing using AMP C++ or CUDA technologies on computer systems and graphics accelerators requires consideration of GPU microarchitecture features for parallel computing core functions. UK: Актуальність. Забезпечення високої швидкодії обчислення комп’ютерними системами розкладу цілочисельного значення на прості множники вимагає розробки ефективних алгоритмічних методів з використанням обчислювальних технологій. Швидке обчислення факторизації чисел використовується в таких застосуваннях, як захист інформаційних даних, в алгоритмах дискретних перетворень для переходу від одного до багатовимірних обчислень та інших. Метою роботи є аналіз впровадження технологій багатопотокового обчислення факторизації цілочисельного значення за бінарним алгоритмом методу пробних ділень з використанням комп’ютерних систем з багатоядерними процесорами та графічними прискорювачами. Метод. Бінарний алгоритм пробних ділень, що використовує залишки кожного розряду двійкового подання числа, для здійснення паралельної перевірки подільності на прості множники для канонічного розкладання числа. Результати. Проведено аналіз та порівняння програмних реалізацій багатопотокових обчислень факторизації числа за двійковим алгоритмом із використанням технологій гіперпоточності, AMP C++, CUDA в комп’ютерних системах з багатоядерними процесорами та графічними прискорювачами. Проаналізовано результати процесу факторизації чисел для багатопоточних обчислювальних технологій, що використовують однотиповий алгоритм для функції паралельного ядра. Висновки. При дослідженні реалізації розкладання чисел за бінарним алгоритмом у багатопотоковому режимі найбільш ефективно виконується технологія гіперпоточних обчислень із використанням багатоядерних процесорів. Гетерогенні обчислення за допомогою технологій AMP C++ або CUDA на комп’ютерних системах та графічних прискорювачах вимагають врахування особливостей мікроархітектури графічного процесора для паралельного виконання функцій ядра.