Розпаралелення обчислення канонічного розкладу числа на множники

Abstract

В статті розглянуто обчислення канонічного розкладу числа на множники з використанням модифікованого методу пробних ділень. Виконання операцій ділення числа розкладу на прості числа для перевірки на кратність вимагає відповідних часових затрат в сучасних комп’ютерних системах. Для їх зменшення використовується бінарне подання числа розкладу в процесі його аналізу на кратність. Для кожного розряду бінарного числа розкладу, що дорівнює одиниці, визначаються залишки його вагового коефіцієнта за модулем відповідного простого числа. Отримані значення залишків акумулюються і потім виконується перевірка накопленого значення на рівність з відповідним значенням з множини простих чисел. У випадку рівності отримуємо елемент кано-нічного розкладу і знову перевіряємо степені цього елемента розкладу на кратність. В протилежному випадку переходимо на наступне більше просте число для подальшої перевірки на кратність, обмежуючись значенням кореня квадратного числа розкладу. Незалежність підзавдань виконання перевірки бінарного подання числа на подільність простими числами дає можливість розпаралелювати виконання розкладу числа в багатоядерних мыкропроцесорах комп’ютерних систем. Серед рівнів паралельності можна послідовно виділити: визначення залишків вагових коефіцієнтів, акумулювання залишків для одиничних розрядів бінарного подання числа розкладу, перевірки на кратність сукупністю простих чисел. Паралельне обчислення розкладу числа досягається виконан-ня алгоритму в багатьох потоках. Програмна реалізація на мові С++, відповідно алгоритму, розподіляє обчислення між потоками, використовуючи пул потоків. В алгоритмі розпаралелення обчислень канонічного розкладу, в залежності від введеного значення числа розкладу, визначається відповідне значення кількості простих чисел та їхніх степенів і рівномірно розподіляється між потоками для виконання аналізу на подільність. В результаті визначено залежність часу обчислення канонічного розкладу числа від кількості потоків в багатоядерних мікропроцесорах лінійки Intel Core i3/i5/i7. Для кожної комп’ютерної системи, що має певну кількість обчислювальних ядер в мікропроцесорах, існує оптимальна кількість потоків, яка забезпечує мінімальний час канонічного розкладу числа на множники.

В статье рассмотрено вычисление канонического разложения числа на множители с использованием модифицировано-го метода пробных делений. Выполнение операций деления числа разложения на простые числа для проверки на кратность требует соответствующих временных потерь в современных компьютерных системах. Для их уменьшения используется бинарное пред-ставление числа разложения в процессе его анализа на кратность. Для каждого разряда бинарного числа разложения, что равняется единице, определяются остатки его весового коэффициента по модулю соответствующего простого числа. Полученные значения остатков аккумулируются и потом выполняется проверка накопленого значения на равенство с соответстующим значением из множества простых чисел. В случае равенства получаем элемент канонического разложения и снова проверяем степени єтого єле-мента розложения на кратность. В противном случае переходим на следующее большее простое число для дальнейшей проверки на кратность, ограничиваясь значеннием квадратного кореня числа разложения. Независимость подзадач выполнения проверки би-нарного представления числа на делимость простыми числами дает возможность распараллеливать выполнение разложения числа в многоядерных микропроцессорах компьютерных систем. Среди уровней параллельности можно последовательно выделить: определение остатков весовых коэффициентов, аккумулирование остатков для единичных разрядов бинарного представления чис-ла разложения, проверки на кратность наборам из простых чисел. Программная реализация на С++, соответственно алгоритму, распределяет вычисления во многих потоках, используя пул потоков. В алгоритме распаралеливания вычислений канонического разложения, в зависимости от введеного значения числа разложения, определяется соответствующее значение количества простых чисел с их степенями и равномерно распределяется между потоками для выполнения анализа на делимость. В результате определе-на зависимость времени вычисления канонического разложения числа от количества потоков в многоядерных микропроцессорах линейки Intel Core i3/i5/i7. Для каждой компьютерной системы, которая имеет определенное количество вычислительных ядер в микропроцессорах, существует оптимальное количество потоков, которое обеспечивает минимальное время канонического разло-жения числа на множители.

The cоmputation of the canonical factorization of a number using the modified trial divisions method has been considered. The performing operations of the division a number of factorization into prime numbers for the testing on a repetition factor demands a respective loss of the execute time in modern computer systems. To reduce them, the presentation of the number of factorization in the binary form is used for the process of analysis on repetition factors. The residuals of weighting coefficient are defined for each digit of the binary represen-tation the number of factorization, which is equal to one. The obtained values of the residuals are accumulated and then the accumulated value is checked for the equality with the corresponding value from the set of prime numbers. In case of equality, we obtain an element of canonical factorization and again check the degrees of this element for a repetition factor. Otherwise, we proceed to the next larger prime number for further checking for a repetition factor. The independence of the subtasks to perform the check of the binary representation of a number on divisibility by prime numbers makes it possible to parallelize the execution of the factorization of a number in multi-core micro-processors of computer systems. Among the levels of the parallelism can be consistently identified: the definition of residual weighting coef-ficients, the accumulation of residuals for bits equel to one of the binary representation of the number of factorization, the checking for a repetition factor from the sets of primes. Software implementation in C++, according to the algorithm, schedules the computations in multi-threads, using a pool of threads. In the algorithm for parallelizing the computations of the canonical factorization, depending on the entered value of the expansion number, the corresponding value of the number of primes with their powers is determined and is evenly distributed between the streams to perform an analysis of divisibility. As a result, the dependence of the run time the computation of the factorization of a number from the number of threads is defined in multi-core processors of Intel Core i3/i5/i7. For the each computer system exist the opti-mal number of the threads, which supports the minimal time of the canonical factorization of a number on the prime numbers.