Рекурсивная модулярная арифметика
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
Возьмем в качестве базисных модулей все взаимно простые трехбитные числа: 4, 5 и 7. В этом случае <math>Q=4\cdot 5\cdot 7=140</math>. | Возьмем в качестве базисных модулей все взаимно простые трехбитные числа: 4, 5 и 7. В этом случае <math>Q=4\cdot 5\cdot 7=140</math>. | ||
| + | |||
| + | Таким образом, выбираем <math> p_{i} = 11 </math> (ближайшее к 7 простое число). Далее совокупность рабочих модулей строится с помощью аналогичного расчета, пока не будет достигнут требуемый вычислительный диапазон. | ||
| + | |||
| + | Наконец рассмотрим реальный случай. Пусть нам нужно реализовать преобразователь Фурье для 24-битных аргументов при количестве точек 1024. | ||
| + | Для этого потребуется вычислять сумму 1024 произведений, т.е. обеспечить <math> 1024 \cdot max^2 < Q </math>. Здесь уже не обойтись системой только трехбитных базисных модулей. Добавим к ним четырехбитные: 5, 7, 8, 9, 11 и 13 (Q = 360360). | ||
| + | Для выбора ближайшего рабочего модуля необходимо <math>\frac{\sqrt Q}{1024}</math>. | ||
| + | |||
| + | Получаем <math>p_{i}-1 < 32 </math>. | ||
| + | Выбираем <math>p_{i} = 31 </math>. | ||
| + | Аналогичным расчетом реализуем рекурсивное дерево рабочих оснований целиком. | ||
| + | Чтобы сделать такое устройство, нужно спроектировать блок из 6 вычислителей (для каждого базисного модуля) и таких блоков нужно будет 16. Вот где работает регулярность. | ||
| + | Заметим, что все вычислители будут иметь высокую скорость модульных операций (суперраспараллеливание) и небольшие аппаратные затраты в силу малости базисных модулей или их близости к степеням двойки. | ||
| + | |||
Версия 19:31, 28 апреля 2014
Содержание |
Принцип рекурсивных модулярных вычислений
Рекурсивная модулярная арифметика основана на принципе глубокого распараллеливания модульных операций модулярной арифметики с основаниями 
посредством сведения модульных операций по каждому рабочему основанию 
, 
к модульным вычислениям по предшествующим рабочим основаниям 
, имеющим то или иное технологическое преимущество (например, малобитным), которые называются базисными основаниями. Такая редукция допустима только при выполнении так называемого условия согласования вычислительных диапазонов по каждому рабочему модулю с вычислительными диапазонами по соответствующим комплексам базисных оснований.
Принцип согласования гарантирует, во-первых, изоморфизм кольцевых операций по соответствующим им комплексам базисных оснований, и во-вторых, выполнимость обращения каждого шага рекурсии посредством перевода соответствующих модулярных кодов по базисным основаниям в позиционный код (например, на основе китайской теоремы об остатках, или переводом их в полиадический код).
Несмотря на ограничения, которые накладываются на систему модулей, предложенный метод обеспечивает выигрыш по скорости и может быть применен в параллельных высокоскоростных вычислительных устройствах.
Пример
Поясним процедуру рекурсивных преобразований на простом примере. Возьмем в качестве базисных модулей двухбитные простые числа 
. Очевидно, что вычетами по модулям 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) Столь малая разрядность базовых модулей позволяет эффективно реализовать модульные операции по базисным модулям в комбинационных схемах.
Однако имеется ряд ограничений, которые должны быть выполнены и которые приводят к усложнению устройств, созданных по данной методике. Рассмотрим эти ограничения.
Пусть есть система базисных модулей 
и необходимо представить вычеты по модулю 
через вычеты по этой системе базовых модулей. Очевидно, что максимальный вычет по модулю равен 
. Зная это значение и последовательность выполняемых операций, можно рассчитать максимальное значение 
результата арифметической операции. Очевидно, что для однозначного представления результата арифметических операций необходимо, чтобы 
, где 
. Для остальных модулей расчет производится аналогично.
Для примера с базовыми модулями 2 и 3 
. Наименьшее простое число (после 2 и 3) - это 5, следовательно, 
.
Нельзя выполнить ни операцию сложения, т.к. 
, ни, тем более, операцию умножения, т.к. 
.
Чтобы выполнять любую из арифметических операций (сложение или умножение) надо увеличить число 
(т.е. увеличить значения базисных модулей и/или их количество).
Возьмем в качестве базисных модулей все взаимно простые трехбитные числа: 4, 5 и 7. В этом случае 
.
Таким образом, выбираем 
(ближайшее к 7 простое число). Далее совокупность рабочих модулей строится с помощью аналогичного расчета, пока не будет достигнут требуемый вычислительный диапазон.
Наконец рассмотрим реальный случай. Пусть нам нужно реализовать преобразователь Фурье для 24-битных аргументов при количестве точек 1024.
Для этого потребуется вычислять сумму 1024 произведений, т.е. обеспечить 
. Здесь уже не обойтись системой только трехбитных базисных модулей. Добавим к ним четырехбитные: 5, 7, 8, 9, 11 и 13 (Q = 360360).
Для выбора ближайшего рабочего модуля необходимо 
.
Получаем 
.
Выбираем 
.
Аналогичным расчетом реализуем рекурсивное дерево рабочих оснований целиком.
Чтобы сделать такое устройство, нужно спроектировать блок из 6 вычислителей (для каждого базисного модуля) и таких блоков нужно будет 16. Вот где работает регулярность.
Заметим, что все вычислители будут иметь высокую скорость модульных операций (суперраспараллеливание) и небольшие аппаратные затраты в силу малости базисных модулей или их близости к степеням двойки.
