BC/NW 2019 № 1 (34):9.3

УСКОРЕНИЕ ДЕЛЕНИЯ ЧИСЕЛ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ

Новичков М.Д., Орлов Д.А.

Система остаточных классов (СОК) является эффективным решением таких проблем организации вычислений как ускорение выполнения арифметических операций, высокоточные вычисления, контроль и коррекция результатов арифметических операций. Однако операции сравнения и деления в СОК являются вычислительно затратными. Поэтому поиск пути ускорения выполнения операции деления является актуальной задачей.

Среди методов деления в СОК был выбран метод, описанный в описании патента RU 2559771. Вычислительная сложность данного метода имеет асимптотику O(n), где n — разность порядков делителя и диапазона. Чем больше делитель, тем быстрее будет выполнено деление. Алгоритм включает два цикла, поэтому его оптимизация заключается в минимизации итераций в них. В базовом алгоритме назначение первого цикла заключается в поиске степени двойки w, умножив на которую делитель, получим число близкое к верхнему пределу диапазона СОК P, такой, что соблюдаться условие 2^(w+1)>P. И за одну итерацию происходит умножение на 2, проверка условия "меньше единицы" и инкремент счётчика итераций.

Был разработан модифицированный алгоритм, в котором введено параллельное вычисление n значений F(B) —умноженных на степени двойки относительных значений делителя, где n равно количеству используемых нитей программы. После умножения F(B) на заранее вычисленные константы 2^(r+1), где r — номер нити, имеет значение от нуля до n. Затем над всеми F(B), что меньше единицы, выполняется редукция поиска максимального. Если для найденного максимального r=n-1, то к значению степени w (по умолчанию w=0) прибавляется r+1, а над текущим максимальным F(B) будет выполнена следующая итерация цикла. Иначе старшая степень двойки найдена и будет сразу присвоена переменной w. Количество шагов редукции равно , округлённое с избытком.

Базовый и модифицированный алгоритм реализованы программно. Программы написаны на языке C++ с использованием OpenMP. В реализации модифицированного алгоритма было использовано 6 потоков. Получен коэффициент ускорения 1,41666.

Литература

1. Акушский  Н.Я.,  Юдицкий  Д.И.  Машинная  арифметика  в  остаточных классах,  М. “Советское радио”, 1968. – 440 с.

2. Бабенко М.Г., Червяков Н.И., Лавриненко И.Н., Ляхов П.А. Устройство для основного деления модулярных чисел. — патент RU 2559771, G06F 7/72.