Научный журнал

Фундаментальные исследования

ISSN 1812-7339

"Перечень" ВАК

ИФ РИНЦ = 1,674

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Исупов К.С. 1 Князьков В.С. 1

---

1 ФГБОУ ВПО «Вятский государственный университет»

Проведен анализ классического и табличного методов прямого преобразования двоичных чисел в систему остаточных классов (СОК). Учитывалась временная и ёмкостная сложность параллельных алгоритмов, основанных на исследуемых методах. Выявлены основные недостатки исследуемых методов: классический метод имеет высокую временную сложность, ввиду экспоненциальной формы зависимости количества выполняемых операций вычитания от числа оснований (модулей) СОК pi, i=1,2,…,n; табличный метод прямого преобразования для оснований произвольного вида требует хранения подстановочных таблиц большого объема, в результате чего они не могут быть размещены в блоках КЭШ памяти первого уровня, а обращение к КЭШ памяти второго и последующего уровней приводит к существенному снижению скорости прямого преобразования. Предложен новый табличный метод преобразования двоичных чисел в систему остаточных классов с основаниями {pi=2^fi-1}, отличающийся тем, что в подстановочной таблице хранится не само значение остатка по основанию pi, а номер соответствующего бита унарного кода, который следует установить значением логической единицы для получения значения остатка по основанию pi. Это позволяет ускорить в 2.43 раза выполнение преобразования двоичных чисел в СОК относительно известного табличного метода для оснований произвольного вида, сократив при этом ёмкостную сложность алгоритма (размер подстановочной таблицы) приблизительно в k / ]log2k[ раз, где k – разрядность каждого основания pi, а ]log2k[ - округленный в бо́льшую сторону логарифм log2k.

Статья в формате PDF

1883 KB

подстановочные таблицы

прямое преобразование

система остаточных классов

1. Кнут Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы. Пер. с англ. – М.: Мир, 1977. – 728 с.

2. Обзор микроархитектур современных десктопных процессоров: Часть 3: организация кэшей данных, внешние интерфейсы процессора, эволюция и ближайшие перспективы развития. – Режим доступа: http://www.ixbt.com/cpu/cpu-microarchitecture-part-3.shtml. (дата доступа: 08.06.2012).

3. AMD Processors for Servers and Workstations: AMD Opteron™ Processor. Compare AMD Product Specs: AMD Phenom™, AMD Athlon™, AMD Opteron™, AMD Sempron™, AMD Turion™ 64 Processors Mobile Technology, ATI Radeon Graphics Cards, and AMD Powered Motherboards. – Режим доступа: http://products.amd.com/en-us/OpteronCPUDetail.aspx?id = 756. (date of access: 04.06.2012).

4. Intel® Core™ i7 Processor Family for the LGA-2011 Socket: Datasheet, Volume 1 of 2. Процессоры Intel для Ultrabook™, ноутбуков, ПК и серверов.– Режим доступа: http://www.intel.ru/content/dam/doc/datasheet/core-i7-lga-2011-datasheet-vol-1.pdf. (date of access: 04.06.2012).

5. Intel® Xeon® Processor E7-8800/4800/2800 Product Families: Datasheet, Volume 2 of 2. Процессоры Intel для Ultrabook™, ноутбуков, ПК и серверов. – Режим доступа: http://www.intel.ru/content/dam/www/public/us/en/documents/datasheets/xeon-e7-8800-4800-2800-families-vol-2-datasheet.pdf. (date of access : 03.06.2012).

6. Koren I. Computer arithmetic algorithms. 2nd ed. – Natick, MA: A K Peters, 2002. – 281 p.

7. Omondi A. Residue Number Systems theory and Implementation. – London : Imperial College Press, 2007. – 312 p.

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

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

Требуется преобразовать двоичное число  в СОК с попарно взаимно простыми основаниями , получив модулярное число  такое, что

где - i-я знакопозиция (модулярный разряд) модулярного числа ; - операция получения остатка от деления M′ на i-е основание p_i. Разрядная сетка вычислительных устройств, на которых выполняется преобразование, определяется значением k, а преобразуемое t-разрядное число  в общем случае выходит за ее пределы, т.е. t > k, при этом, если t = k·v, то t-разрядные арифметические операции представляются в виде v последовательно выполняемых k-разрядных операций.

Классический метод преобразования позиционного числа в систему остаточных классов сводится к нахождению значения каждой i-й знакопозиции (модулярного разряда) , i = 1, 2, ..., n, по формуле

(1)

где - наибольшее целое, не превышающее .

Другими словами, каждый модулярный разряд m_i представляет собой наименьший неотрицательный целочисленный остаток от деления исходного позиционного целого числа M′ на соответствующее целочисленное основание p_i.

Пусть t - разрядность преобразуемого двоичного числа , k - разрядность основания p_i. Условимся, что , а .

Диапазон изменения чисел  в системе остаточных классов с основаниями  определяется интервалом

,

а, с учетом условия , i = 1, 2, ..., n,

.

Тогда - максимальное число, представимое в системе остаточных классов с основаниями . Следовательно,

Для вычисления каждой знакопозиции m_i по формуле (1) потребуется  t-разрядных операций вычитания. Пусть T_sub(k) - время выполнения операции вычитания двоичных k-разрядных чисел. Операция t-разрядного вычитания, с учетом условия , сопоставима по времени с n последовательными операциями k-разрядного вычитания, т.е. . Следовательно, для параллельного вычисления всех знакопозиций потребуется время, приближенно равное

Получение модулярного числа  можно осуществить посредством использования подстановочной таблицы (Look-up Table) [6, с. 267]. Основная идея данного метода преобразования заключается в следующем. Пусть имеется - t-разрядное целое двоичное число, изменяющееся в пределах интервала . Величину данного числа можно выразить посредством взвешенной суммы

 (2)

где j = 1, 2, ..., t - позиции двоичных разрядов , в соответствии с которыми однозначно определяются веса этих разрядов в двоичной системе счисления (в данном случае номером младшего разряда является единица, а не ноль, вследствие чего истинный вес j-го разряда равен j - 1).

С учетом (2), выражение для получения i-й знакопозиции  будет иметь вид

(3)

Придерживаясь правил выполнения модулярной операции сложения, выражение (3) правомерно записать в виде

Так как , j = 1, 2, ..., t, то для нахождения модулярного числа  можно воспользоваться подстановочной таблицей (табл. 1), состоящей из n столбцов и t строк. Тогда процесс преобразования

сведется к выбору из подстановочной таблицы значений , i = 1, 2, ..., n (для разрядов d_j = 1), и их суммированию по модулю p_i.

Например, в табл. 2 приведены все значения , i = 1, ..., 4, j = 1, ..., 8, для оснований p₁ = 3, p₂ = 5, p₃ = 7, p₄ = 11 и разрядности двоичных слов до 8 бит.

Пример. Пусть имеется восьмибитное целое число M′ = 10001001₂ = 137₁₀. Необходимо определить модулярное число в системе остаточных классов с основаниями p₁ = 3, p₂ = 5, p₃ = 7, p₄ = 11.

1. Определяем позиции ненулевых бит в двоичном числе M′ = 10001001₂: j = 1, 4, 8, поэтому

2. Определяем знакопозиции m_i, i = 1, 2, 3, 4, модулярного числа , выполняя для каждого основания p_i выборку из подстановочной таблицы (табл. 2) и суммирование значений :

Получили

Таким образом, использование подстановочных таблиц позволяет получать модулярные представления чисел без необходимости вычисления выражения (1).

Оценка временных затрат. Пусть T_стр(t) - время выполнения битового анализа t-разрядного двоичного слова, T_L2(k) - время выборки из памяти ЭВМ k-разрядного двоичного слова (имеется ввиду время доступа к КЭШ памяти второго уровня), а T_add(k) - время выполнения операции сложения двух двоичных k-разрядных чисел. Пусть

,

Для получения каждой знакопозиции m_i на основании табличного метода необходимо выполнить одну операцию битового анализа t-разрядного двоичного числа для определения весов ненулевых разрядов, t обращений к подстановочной таблице за выборкой k-разрядных значений , соответствующих весам j ненулевых бит d_j, (t - 1) операций суммирования, выбранных из таблицы k-разрядных двоичных слов , и одну операцию получения остатка от деления суммы  на i-е основание p_i. В предельном случае сумма  состоит из t чисел, разрядность которых не превышает k, поэтому операцию получения остатка от деления  на i-е основание p_i можно представить в виде (t - 1) операции вычитания k-разрядных чисел из -разрядного числа, где - округленный до целого в бо?льшую сторону логарифм . Тогда, считая что

время параллельного преобразования двоичного t-разрядного числа в СОК табличным методом будет приближенно определяться выражением

а так как t≈k*n, то с учетом несложных преобразований получаем время

Недостатки. При большом количестве оснований подстановочные таблицы становятся большими, в результате чего не могут быть полностью записаны в модули памяти, располагающиеся непосредственно на вычислительном ядре (т.е. в КЭШ первого уровня L1), а доступ к КЭШ памяти второго уровня осуществляется значительно медленнее. Например, при использовании десяти 64-битных оснований для хранения общей подстановочной таблицы, содержащей значения  для двоичных слов вплоть до 2^64·10, потребуется 10·640·64/8 = 51200 байт памяти, в то время, как объем КЭШ памяти L1 современных универсальных процессоров на каждое ядро составляет в среднем 32-48 КБ [3-5]. Размещение подстановочных таблиц в КЭШ памяти второго и последующего уровней неизбежно приводит к тому, что время T_L2(k) выборки k-разрядного двоичного слова становится весьма большим относительно времени выполнения арифметических операций сложения, вычитания и умножения, которые работают либо с регистрами общего назначения, либо с КЭШ L1. В результате этого значительным образом снижается скорость преобразования

.

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

Согласно формуле (3), модулярное число можно выразить следующим образом:

(4)

где d_j € {0;1}- j-й бит двоичного числа

Выражение (4) можно модифицировать, используя известные результаты теории чисел, в частности, свойства чисел, имеющих форму 2^f - 1, где f ≥ 0 - натуральное число. Для чисел вида 2^f - 1 существует тождество [1, с. 307]

(5)

которое позволяет сформулировать утверждение о получении значения величины .

Утверждение 1. Зная позиционное значение неотрицательного целого показателя степени j, величину 2^j по положительному модулю p при условии, что p = 2^f - 1 и f ≥ 2, можно определить как . Другими словами, при выборе модуля p из множества чисел  справедливо тождественное равенство

где f ≥ 2, j ≥ 0 - натуральные числа,

Доказательство. Так как для любого целого f ≥ 2 справедливо сравнение , то соотношение  эквивалентно тождеству . Отсюда следует, что для любых целых f ≥ 2 и j ≥ 0 справедливо тождество

Если все основания , являющиеся модулями для определения модулярных чисел , выбирать из множества чисел вида 2^f - 1, где f - натуральное число, превышающее единицу, то, в силу Утверждения 1, выражение (4) примет вид

где

 ...,

при условии, что

 ...,

Введем обозначение:

 (6)

где d_j - j-й бит целого двоичного числа , i - номер знакопозиции m_i. Тогда

(7)

причем, в соответствии с Утверждением 1, для всех i и j справедливо неравенство .

Для ускорения процесса преобразования, по аналогии с рассмотренным табличным методом для оснований произвольного вида, предлагается использовать подстановочную таблицу (табл. 3), однако хранить в этой таблице следует не сами k-разрядные вычеты , а вычисленные заранее -разрядные значения для всех j = 1, 2, ..., t.

Таблица значений для перевода t-разрядных двоичных чисел в систему остаточных классов с n основаниями

В качестве примера, в табл. 4 приведены все значения для оснований p₁ = 3 = 2² - 1, p₂ = 7 = 2³ - 1, p₃ = 31 = 2⁵ - 1, p₄ = 127 = 2⁷ - 1 (f₁ = 2, f₂ = 3, f₃ = 5, f₄ = 7,) и разрядности t преобразуемых двоичных чисел до 8 бит.

Значения для перевода двоичных чисел разрядности вплоть до 8 бит в СОК с основаниями 3, 7, 31, 127

При использовании описанной подстановочной таблицы процесс прямого преобразования

будет заключаться в выборе из подстановочной таблицы значений , i = 1, 2, ..., n (только для разрядов d_j = 1 двоичного числа ), формировании на основе выбранных значений k-разрядных унарных двоичных кодов , соответствующих значениям , и суммированию полученных значений  по всем модулям p_i, в соответствии с выражением (7), для  при d_j = 1.

Таким образом, основная концепция предлагаемого метода прямого преобразования заключается в том, чтобы хранить в подстановочных таблицах не само значение остатка , а номер  соответствующего бита k-разрядного унарного кода, который следует установить значением логической единицы для получения значения остатка  в случае, если бит d_j в двоичном числе  ненулевой.

Рассмотрим на конкретном примере параллельный алгоритм приведения позиционного числа  к модулярному числу , построенный на базе предлагаемого метода.

Пример. Пусть имеется восьмибитное целое двоичное число M′ = 10001001₂ = 137₁₀. Необходимо определить модулярное число  в системе остаточных классов с основаниями p₁ = 3 = 2² - 1, p₂ = 7 = 2³ - 1, p₂ = 31 = 2⁵ - 1.

1. Определяем позиции ненулевых бит в двоичном числе M′ = 10001001₂: j = 1, 4, 8,

2. Выбираем из подстановочной таблицы (табл. 4) набор значений номеров соответствующих бит k-разрядных унарных кодов, которые следует установить значением логической единицы, для каждого основания p_i:

3. На основании определенных позиций ненулевых бит формируем 5-разрядные унарные двоичные коды, соответствующие значениям слагаемых  для каждого основания p_i (нулевое значение позиции соответствует унарному коду с единицей в младшем разряде, первое значение позиции соответствует коду с единицей в разряде, следующем за младшим и т.д.):

4. Находим модулярное число  в соответствии с выражением (7), определяя каждый модулярный разряд m_i как сумму полученных значений :

Получили .

Подобный метод прямого преобразования был представлен учеными A. Omondi и B. Premkumar в работе [7, с. 50]. Согласно этому методу, вычисление каждого остатка  выполняется следующим образом:

т.е. выполняется разложение величины 2^j-1 на сомножители: 2^q·f, остаток от деления на модуль 2^f - 1 которого дает единицу, и 2^r, остаток от деления на модуль которого дает искомое значение , т.е. показатель r, по существу, определяется выражением . Принципиальным отличием предлагаемого метода от метода, представленного в работе [7, с. 50], является использование подстановочной таблицы.

Предлагаемый метод преобразования позволяет, с одной стороны, избавиться от необходимости выполнения трудоемких операций получения остатка от деления исходного позиционного t-разрядного числа M′ на модули p_i, присущих классическому методу, а с другой - сократить размер подстановочных таблиц, тем самым обеспечивая возможность их распределения по модулям КЭШ памяти первого уровня (L1), в результате чего сокращается время доступа к ним. В предельном случае, при работе с k-разрядными основаниями p_i = 2^k - 1, i = 1, 2, ..., n, размер подстановочной таблицы для хранения -разрядных значений  для всех j = 1, 2, .., t будет определяться выражением , а не n·t·k, как при использовании табличного метода преобразования для оснований произвольного вида, предполагающего хранение в таблицах k-разрядных значений , т.е. ёмкостная сложность (размер подстановочной таблицы) сокращается приблизительно в раз, где - округленный до целого в бо?льшую сторону . Например, при использовании десяти 64-битных оснований для хранения общей подстановочной таблицы (табл. 3), содержащей значения  для двоичных слов вплоть до 2^64·10 потребуется

 байт памяти,

что в 10,67 раза меньше, чем при использовании табличного метода преобразования для модулей произвольного вида.

Оценка временных затрат. Пусть - время выборки из модуля КЭШ памяти первого уровня -разрядного двоичного числа, - время генерации k-разрядного унарного кода при известной позиции единичного бита, - время выполнения k-разрядной операции сложения (вычитания) пары двоичных чисел. Пусть p_i = 2^k - 1, i = 1, 2, ..., n, а M′ = 2^t - 1.

Для получения каждой знакопозиции m_i модулярного числа  на основании предлагаемого метода в предельном случае необходимо выполнить одну операцию битового анализа t-разрядного двоичного числа для определения весов ненулевых разрядов (для того, чтобы не выбирать из таблицы избыточные значения  когда d_j = 0 и не вычислять в явном виде выражение (6)), t обращений к подстановочной таблице за выборкой -разрядных значений , t операций генерации k-разрядного унарного кода, (t - 1) операций суммирования k-разрядных двоичных унарных кодов, соответствующих значениям b_i^j, и одну операцию получения остатка от деления  на модуль p_i, которую можно представить в виде (t - 1) операции вычитания k-разрядных чисел из -разрядного числа.

Следовательно, время параллельного вычисления всех знакопозиций m₁, m₂, ..., m_n составит

Так как по условиям t≈k*n, то после несложных преобразований получаем выражение времени преобразования:

В качестве базовой единицы времени для сопоставления полученных оценок временной сложности рассмотренных методов будем использовать время T такта вычислителя (далее просто - такт вычислителя), считая, что разрядная сетка имеет размер k, поэтому операции сложения, вычитания, битового анализа и формирования унарного кода в пределах k разрядов выполняются за 1 такт, т.е. T_add(k) = T_sub(k) = T_cmp(k) = T_unary(k) = T, а операции над числами, разрядность которых больше k, реализуются посредством выполнения набора k-разрядных операций. Условимся, что время T_L1(k) выборки не более k двоичных разрядов из КЭШ памяти первого уровня (L1) составляет 3 такта [2], а время T_L2(k) выборки из КЭШ памяти второго уровня (L2) - приблизительно 14 тактов (результаты тестирования показали, что на разных процессорах эта оценка изменяется от 8 тактов до 21 такта [2]). В табл. 5 представлены выраженные в тактах оценки временной сложности параллельных алгоритмов, основанных на рассматриваемых методах преобразования.

Оценки временной сложности параллельных алгоритмов преобразования

Таким образом, ценой ограничения допустимой формы оснований , удалось снизить временные затраты на преобразование двоичных чисел в систему остаточных классов приблизительно в

относительно табличного метода для оснований произвольного вида. Классический метод преобразования не рассчитан на большое число оснований и большую разрядность преобразуемых двоичных чисел, поэтому его временная сложность при больших значениях n и k во много раз превосходит временную сложность табличных методов.

Таким образом, предложен новый табличный метод параллельного преобразования позиционных двоичных чисел в систему остаточных классов с основаниями , отличающийся тем, что в качестве оснований выбираются попарно взаимно-простые числа вида , i = 1, 2, ..., n, а в подстановочной таблице хранится не само значение остатка , а номер  соответствующего бита k-разрядного унарного кода, который следует установить значением логической единицы для получения значения остатка

,

что позволяет ускорить приблизительно в 2,43 раза выполнение процедуры преобразования двоичных чисел в систему остаточных классов относительно известного табличного метода для оснований произвольного вида, сократив при этом емкостную сложность алгоритма (размер подстановочной таблицы) приблизительно в  раз, где k - разрядность каждого основания p_i.

Ограничением предложенного метода является специальный вид модулей - 2^f - 1. Однако данных оснований в большинстве случаев оказывается достаточно для обеспечения необходимого диапазона представления чисел в СОК. Кроме этого, предложенный метод с небольшими изменениями может быть адаптирован для оснований вида 2^f + 1 [7, с. 52]. Использование в качестве оснований СОК чисел из набора

позволит существенно расширить допустимый диапазон представления чисел.

• Бутаев М.М., д.т.н., профессор, ученый секретарь научно-технического совета, ОАО «Научно-производственное предприятие «Рубин», г. Пенза;
• Частиков А.В., д.т.н., профессор, декан факультета прикладной математики и телекоммуникаций ФГБОУ ВПО «Вятский государственный университет», г. Киров.
• Антонов А.В., д.т.н., профессор, декан факультета кибернетики Обнинского института атомной энергетики Национального исследовательского ядерного университета МИФИ, г. Обнинск.

Работа поступила в редакцию 04.09.2012.

Библиографическая ссылка