Версия 08:04, 29 апреля 2014

Содержание

1 Принцип рекурсивных модулярных вычислений
- 1.1 Пример
2 Представление данных и основные операции рекурсивной модулярной арифметики

Принцип рекурсивных модулярных вычислений

Рекурсивная модулярная арифметика основана на принципе глубокого распараллеливания модульных операций модулярной арифметики с основаниями $p_1,p_2,\ldots,p_n$ посредством сведения модульных операций по каждому рабочему основанию $p_j$ , $i<=j<=n$ к модульным вычислениям по предшествующим рабочим основаниям $p_1,p_2,\ldots,p_{i-1}$ , имеющим то или иное технологическое преимущество (например, малобитным), которые называются базисными основаниями. Такая редукция допустима только при выполнении так называемого условия согласования вычислительных диапазонов по каждому рабочему модулю $p_j$ с вычислительными диапазонами по соответствующим комплексам базисных оснований. Принцип согласования гарантирует, во-первых, изоморфизм кольцевых операций по соответствующим им комплексам базисных оснований, и во-вторых, выполнимость обращения каждого шага рекурсии посредством перевода соответствующих модулярных кодов по базисным основаниям в позиционный код (например, на основе китайской теоремы об остатках, или переводом их в полиадический код). Несмотря на ограничения, которые накладываются на систему модулей, предложенный метод обеспечивает выигрыш по скорости и может быть применен в параллельных высокоскоростных вычислительных устройствах.

Пример

Поясним процедуру рекурсивных преобразований на простом примере. Возьмем в качестве базисных модулей двухбитные простые числа $p_1=2, p_2=3$ . Очевидно, что вычетами по модулям 2 и 3 можно однозначно представить любой вычет по модулю 5. В то же время вычетами по модулям 2, 3 и 5, где вычеты по модулю 5 представимы по модулям 2 и 3, можно однозначно представить любой вычет по модулю 29. Вычетами по модулям 2, 3, 5 и 29 можно однозначно представить любой вычет по модулю 863. И так далее пока не получим нужный набор рабочих оснований: 2, 3, 5, 29, 863,… Данный пример наглядно иллюстрирует 4 факта:

1) Аппаратные и временные затраты на представление чисел по базовым модулям 2 и 3 примерно одинаковы (оба базисных модуля двухбитные);

2) Наблюдается более высокая степень распараллеливаемости;

3) Появляется регулярность (все вычисления проводятся по модулям 2 и 3);

4) Столь малая разрядность базовых модулей позволяет эффективно реализовать модульные операции по базисным модулям в комбинационных схемах.

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

Пусть есть система базисных модулей $p_1,p_2,\ldots,p_m$ и необходимо представить вычеты по модулю $p_{m+1}$ через вычеты по этой системе базовых модулей. Очевидно, что максимальный вычет по модулю $p_{m+1}$ равен $max=p_{m+1}-1$ . Зная это значение и последовательность выполняемых операций, можно рассчитать максимальное значение $MAX$ результата арифметической операции. Очевидно, что для однозначного представления результата арифметических операций необходимо, чтобы $MAX<Q$ , где $Q=p_1\cdot p_2\cdot \ldots \cdot p_m$ . Для остальных модулей расчет производится аналогично.

Для примера с базовыми модулями 2 и 3 $Q=2\cdot 3 = 6$ . Наименьшее простое число (после 2 и 3) - это 5, следовательно, $max=4$ . Нельзя выполнить ни операцию сложения, т.к. $2\cdot max > Q$ $(8 > 6)$ , ни, тем более, операцию умножения, т.к. $max^2 > Q$ $(16 > 6)$ . Чтобы выполнять любую из арифметических операций (сложение или умножение) надо увеличить число $Q$ (т.е. увеличить значения базисных модулей и/или их количество).

Возьмем в качестве базисных модулей все взаимно простые трехбитные числа: 4, 5 и 7. В этом случае $Q=4\cdot 5\cdot 7=140$ .

Таким образом, выбираем $p_{i} = 11$ (ближайшее к 7 простое число). Далее совокупность рабочих модулей строится с помощью аналогичного расчета, пока не будет достигнут требуемый вычислительный диапазон.

Наконец рассмотрим реальный случай. Пусть нам нужно реализовать преобразователь Фурье для 24-битных аргументов при количестве точек 1024. Для этого потребуется вычислять сумму 1024 произведений, т.е. обеспечить $1024 \cdot max^2 < Q$ . Здесь уже не обойтись системой только трехбитных базисных модулей. Добавим к ним четырехбитные: 5, 7, 8, 9, 11 и 13 (Q = 360360). Для выбора ближайшего рабочего модуля необходимо $\frac{\sqrt Q}{1024}$ .

Получаем $p_{i}-1 < 32$ . Выбираем $p_{i} = 31$ .

Аналогичным расчетом реализуем рекурсивное дерево рабочих оснований целиком. Чтобы сделать такое устройство, нужно спроектировать блок из 6 вычислителей (для каждого базисного модуля) и таких блоков нужно будет 16. Вот где работает регулярность. Заметим, что все вычислители будут иметь высокую скорость модульных операций (суперраспараллеливание) и небольшие аппаратные затраты в силу малости базисных модулей или их близости к степеням двойки.

Таким образом, предложенный аппарат рекурсивных модулярных вычислений дает следующие преимущества:

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

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

3. Появляется регулярность (большое количество одинаковых базисных модулей).

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

Представление данных и основные операции рекурсивной модулярной арифметики

Идея, на которой базируется рекурсивная модулярная арифметика: выразить систему модулей через систему субмодулей, имеющую меньшую размерность.

Пусть задана система модулей $p_1, p_2, \ldots, p_i, \ldots , p_n$ и задан некоторый вектор $A = (a_1, a_2, \ldots , a_n)$ . Выразим $a_i$ через систему субмодулей

$p_i = (p_{i,1}, p_{i,2}, \ldots , p_{i,k})$ , где $P_i = p_{i,1}, p_{i,2}, \ldots , p_{i,k}$ и $a_i < P_i$ : $a_i = (a_{i,1}, a_{i,2}, \ldots , a_{i,k})$ .

В этом случае вектор A можно представить в следующем виде:

$(a_1, a_2, \ldots , a_{i-1}, (a_{i,1}, a_{i,2}, \ldots , a_{i,k}), a_{i+1}, \ldots , a_n)$ , см. рис. 1.

Назовем систему из m младших модулей системой базовых модулей, а их произведение обозначим $Q = (p_1 \cdot p_2 \cdot \ldots \cdot p_m)$ .

Пусть $P_{i,1} = p_i, p_{i,2} = p_2, \ldots , p_{i,i-1} = p_{i-1}$ , а $k = i-1$ , тогда при $i = m+1, \ldots , n$ имеет место рекурсия. $a_i = (a_1, a_2, \ldots , a_m, a_{m+1}, \ldots , a_{i-1})$ по системе модулей $p_1, p_2, \ldots , p_m, p_{m+1}, \ldots , p_{i-1}$ или, раскрывая рекурсию: $a_i = (a_1, a_2, \ldots , a_m, (a_{m+1,1}, a_{m+1,2}, \ldots , a_{m+1,m} ), \ldots)$ . На рис.2 приведен частный случай разложения элемента $a_i$ для случая $n=6$ и $m=3$ .

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

Если в традиционной модулярной арифметике число элементов вектора равно числу элементов в системе модулей, то в рекурсивной модулярной арифметике количество элементов вектора увеличивается в зависимости от заданных $n$ и $m$ . Очевидно, что каждый из первых $m$ элементов представляется в виде одного числа. $(m+1)$ -й элемент содержит $m$ элементов, поскольку выражается через $m$ элементов системы субмодулей:

$a_{m+1} = (a_{m+1,1}, a_{m+1,2}, \ldots , a_{m+1,m})$ .

$(m+2)$ -й элемент содержит $2 \cdot m$ элементов, поскольку выражается через $m$ элементов системы субмодулей и $m$ элементов вектора $a_{m+1}$ . Таким образом, продолжая рассуждения, можно заключить, что число элементов $L_i$ для вектора $a_i$ может быть выражено следующей формулой:

$L_i = \begin{cases} 1, & \mbox{if } i \le m ; \\ 2^{i-m-1} \cdot m, & \mbox{if } m<i<n \end{cases}$

Общее же число элементов $L$ вектора $A$ можно рассчитать, воспользовавшись формулой суммы геометрической прогрессии:

$L = \sum_{i=1}^{n} L_i = m+m \cdot (2^0+2^1+ \ldots +2^{n-m+1}) = m \cdot (1+ \frac{2^{n-m}-1}{2-1}) = 2^{n-m} \cdot m$

@@ Строка 34: / Строка 34: @@
 Получаем <math>p_{i}-1 < 32 </math>.
 Выбираем <math>p_{i} = 31 </math>.
 Аналогичным расчетом реализуем рекурсивное дерево рабочих оснований целиком.
 Чтобы сделать такое устройство, нужно спроектировать блок из 6 вычислителей (для каждого базисного модуля) и таких блоков нужно будет 16. Вот где работает регулярность.
@@ Строка 50: / Строка 51: @@
 Идея, на которой базируется рекурсивная модулярная арифметика: выразить систему модулей через систему субмодулей, имеющую меньшую размерность.
-Пусть задана система модулей <math> (p_1, p_2, \ldots, p_i, \ldots , p_n) </math> и задан некоторый вектор <math> A = (a_1, a_2, \ldots , a_n) </math>. Выразим <math> a_i </math> через систему субмодулей <math> p_i = (p_{i,1}, p_{i,2}, \ldots , p_{i,k}) </math> , где <math> P_i = p_{i,1}, p_{i,2}, \ldots , p_{i,k} </math> и a_i < P_i </math> : <math> a_i = (a_{i,1}, a_{i,2}, \ldots , a_{i,k}) </math> . В этом случае вектор A можно представить в следующем виде : <math> (a_1, a_2, \ldots , a_{i-1}, (a_{i,1}, a_{i,2}, \ldots , a_{i,k}), a_{i+1}, \ldots , a_n) </math> , см. рис. 1.
+Пусть задана система модулей <math> p_1, p_2, \ldots, p_i, \ldots , p_n </math> и задан некоторый вектор <math> A = (a_1, a_2, \ldots , a_n) </math>. Выразим <math> a_i </math> через систему субмодулей
-Назовем систему из m младших модулей системой базовых модулей, а их произведение обозначим  <math> Q = (p_1 \cdot p_2 \cdot \ldots \cdot  p_m) </math> . Пусть <math> P_{i,1} = p_i, p_{i,2} = p_2, \ldots , p_{i,i-1} = p_{i-1} </math> , а <math> k = i-1 </math> , тогда при <math> i = m+1, \ldots , n  </math> имеет место рекурсия. <math> a_i = (a_1, a_2, \ldots , a_m, a_{m+1}, \ldots , a_{i-1}) </math> по системе модулей <math> p_1, p_2, \ldots , p_m, p_{m+1}, \ldots , p_{i-1}) </math> или, раскрывая рекурсию: <math> a_i = (a_1, a_2, \ldots , a_m, (a_{m+1,1}, a_{m+1,2}, \ldots , a_{m+1,m} ),  \ldots) </math> . На рис.2 приведен частный случай разложения элемента <math> a_i </math> для случая <math> n=6 </math> и <math> m=3 </math>.
+:<math> p_i = (p_{i,1}, p_{i,2}, \ldots , p_{i,k}) </math> , где <math> P_i = p_{i,1}, p_{i,2}, \ldots , p_{i,k} </math> и <math> a_i < P_i </math> : <math> a_i = (a_{i,1}, a_{i,2}, \ldots , a_{i,k}) </math> .
+В этом случае вектор A можно представить в следующем виде:
+:<math> (a_1, a_2, \ldots , a_{i-1}, (a_{i,1}, a_{i,2}, \ldots , a_{i,k}), a_{i+1}, \ldots , a_n) </math> , см. рис. 1.
+Назовем систему из m младших модулей системой базовых модулей, а их произведение обозначим  <math> Q = (p_1 \cdot p_2 \cdot \ldots \cdot  p_m) </math> .
+Пусть <math> P_{i,1} = p_i, p_{i,2} = p_2, \ldots , p_{i,i-1} = p_{i-1} </math> , а <math> k = i-1 </math> , тогда при <math> i = m+1, \ldots , n  </math> имеет место рекурсия. <math> a_i = (a_1, a_2, \ldots , a_m, a_{m+1}, \ldots , a_{i-1}) </math> по системе модулей <math> p_1, p_2, \ldots , p_m, p_{m+1}, \ldots , p_{i-1} </math> или, раскрывая рекурсию: <math> a_i = (a_1, a_2, \ldots , a_m, (a_{m+1,1}, a_{m+1,2}, \ldots , a_{m+1,m} ),  \ldots) </math> . На рис.2 приведен частный случай разложения элемента <math> a_i </math> для случая <math> n=6 </math> и <math> m=3 </math>.
@@ Строка 58: / Строка 67: @@
 Если в традиционной модулярной арифметике число элементов вектора равно числу элементов в системе модулей, то в рекурсивной модулярной арифметике количество элементов вектора увеличивается в зависимости от заданных <math>n</math> и <math>m</math> .
-Очевидно, что каждый из первых <math>m</math> элементов представляется в виде одного числа. <math>(m+1)</math>-й элемент содержит <math>m</math> элементов, поскольку выражается через <math>m</math> элементов системы субмодулей: <math> a_{m+1} = (a_{m+1,1}, a_{m+1,2}, \ldots , a_{m+1,m}) </math> . <math>(m+2)</math>-й элемент содержит <math>2 \cdot m</math> элементов, поскольку выражается через <math>m</math> элементов системы субмодулей и <math>m</math> элементов вектора<math> a_{m+1} </math> . Таким образом, продолжая рассуждения, можно заключить, что число элементов <math> L_i </math> для вектора <math> a_i </math> может быть выражено следующей формулой:
+Очевидно, что каждый из первых <math>m</math> элементов представляется в виде одного числа. <math>(m+1)</math>-й элемент содержит <math>m</math> элементов, поскольку выражается через <math>m</math> элементов системы субмодулей:
+:<math> a_{m+1} = (a_{m+1,1}, a_{m+1,2}, \ldots , a_{m+1,m}) </math>.
+<math>(m+2)</math>-й элемент содержит <math>2 \cdot m</math> элементов, поскольку выражается через <math>m</math> элементов системы субмодулей и <math>m</math> элементов вектора <math> a_{m+1} </math> . Таким образом, продолжая рассуждения, можно заключить, что число элементов <math> L_i </math> для вектора <math> a_i </math> может быть выражено следующей формулой:
-<math>L_i = \{ 1, i \le m ; 2^{i-m-1} \cdot m, m<i<n </math>
+:<math>L_i = \begin{cases}
+, & \mbox{if } i \le m ; \\
+^{i-m-1} \cdot m,  & \mbox{if } m<i<n
+\end{cases}
+</math>
 Общее же число элементов<math> L </math>вектора <math> A </math> можно рассчитать, воспользовавшись формулой суммы геометрической прогрессии:
-<math>L = \sum_{i=1}^{n} L_i = m+m \cdot (2^0+2^1+ \ldots +2^{n-m+1}) = m \cdot (1+ \frac{2^{n-m}-1}{2-1}) = 2^{n-m} \cdot m </math>
+:<math>L = \sum_{i=1}^{n} L_i = m+m \cdot (2^0+2^1+ \ldots +2^{n-m+1}) = m \cdot (1+ \frac{2^{n-m}-1}{2-1}) = 2^{n-m} \cdot m </math>
 == Ограничения на выбор базиса ==

Рекурсивная модулярная арифметика — различия между версиями

Версия 08:04, 29 апреля 2014

Содержание

Принцип рекурсивных модулярных вычислений

Пример

Представление данных и основные операции рекурсивной модулярной арифметики

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

Ограничения на выбор базиса

Обратное преобразование числа из рекурсивного представления в позиционное

Сложение и умножение в рекурсивной модулярной арифметике

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация

Инструменты