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.