Современное состояние развития инфокоммуникационных технологий в области обработки и передачи данных характеризуется интенсивным внедрением новых принципов и подходов к обработке информации. Результаты теоретических и практических разработок отечественных и зарубежных специалистов со всей определенностью указывают на то, что одним из перспективных многообещающих путей решения задач сокращения времени обработки данных и повышения надежности вычислительных средств является применение различных форм параллельной обработки данных, в том числе и на основе числовых систем с параллельной структурой. Одним из магистральных направлений среди современных подходов к созданию отказоустойчивых высокопроизводительных средств обработки данных является использование системы остаточных классов (СОК).
Арифметика СОК долгое время привлекала интерес только на теоретическом уровне из-за сложности архитектур, определяемых использованием представляемых данных. Однако быстрый рост технологий вычислительной базы делает СОК удобным для многих приложений цифровой обработки данных, криптографии, систем передачи данных, основанных на множественном доступе с кодовым разделением каналов и др.
Главным преимуществом СОК является разложение динамического диапазона на параллельные каналы с меньшими динамическими диапазонами, определяемыми выбором оснований СОК, которые приводят к операциям без переноса между каналами с различными основаниями и сокращению задержек сигналов.
В качестве недостатка СОК можно отметить трудность выполнения немодульных операций.
Система остаточных классов
Основной теоретико-числовой базой системы остаточных классов является теория сравнений. Полной системой вычетов по модулю p называется совокупность p целых чисел, содержащая точно по одному представителю из каждого класса вычетов по модулю p. Каждый класс вычетов по модулю p содержит в точности одно из чисел совокупности всех возможных остатков от деления на p: {0, 1, ..., p ? }. Множество {0, 1, ..., p ? } также называется полной системой наименьших неотрицательных вычетов по модулю p.
Один из методов выполнения арифметических операций над длинными целыми числами основан на простых положениях теории чисел. Представление чисел в СОК позволяет заменить операции с большими числами на операции с малыми числами, которые представлены в виде остатков от деления больших чисел на заранее выбранные взаимно-простые модули p1, p2, ..., pn. Пусть
Тогда целому числу A можно поставить в соответствие кортеж (α1, α2, ..., αn) наименьших неотрицательных вычетов по одному из соответствующих классов. Данное соответствие будет взаимно однозначным, пока A < p1, p2, ..., pn, в силу Китайской Теоремы об Остатках (КТО). Кортеж (α1, α2, ..., αn) можно рассматривать как один из способов представления целого числа A в ЭВМ - модулярное представление или представление в СОК.
Основным преимуществом такого представления является тот факт, что выполнение операций сложения, вычитания и умножения реализуется очень просто, по формулам:
?
Эти операции носят название модульных, так как для их выполнения в СОК достаточно одного такта обработки численных значений, причем эта обработка происходит параллельно и значения информации в каждом разряде не зависят от других разрядов.
Основной недостаток модулярного представления чисел состоит в том, что трудно упорядочить множество всех целочисленных кортежей длины n так, чтобы этот порядок соответствовал естественному порядку на множестве целых чисел. Как следствие этого факта, трудно установить, является ли кортеж (α1, α2, ..., αn) большим (меньшим), чем (β1, β2, ..., βn). Трудно также проверить, возникло ли переполнение допустимого диапазона чисел P = p1p2...pn в результате выполнения операций сложения или умножения, но еще труднее выполнить операцию деления. Эти и некоторые другие операции носят название немодульных, так как для их выполнения требуется знание о величине числа в целом, которое называется позиционной характеристикой числа.
Модель целочисленной модулярной арифметики можно задать следующей сигнатурой
,
где 
- полная система вычетов по модулю полного динамического диапазона;
- вычет чисел по модулю pi; МО - множество модульных операций, к которым относятся арифметические операции сложения, вычитания, умножения и деления нацело или умножение на обратный элемент, НО - множество немодульных операций, к которым относятся операции определения знаков чисел и переполнения динамического диапазона, сравнение, определение интервалов чисел, определение и локализация ошибочного разряда и др.
Немодульные операции обусловлены знанием числового значения модулярной величины, которая определенным образом связана со значениями компонент модулярного представления. Эти операции являются медленными, что снижает эффективность применения модулярной алгебры. Для реализации немодульных операций используются специальные функционалы, которые определяют количественные характеристики отношения порядка над множеством модулярных векторов. Одно из устоявшихся названий функционалов - позиционная характеристика (ПХ) модулярной величины или числовой величины в модулярном коде. В основе алгоритмов выполнения немодульных операций лежат методы вычисления ПХ, сложность которых непосредственно влияет на скорость выполнения немодульных операций в модулярной алгебре. Поиск эффективных и универсальных ПХ важен для теоретических основ модулярных вычислительных структур и вычислительных средств на их основе.
В настоящее время известны следующие методы определения позиционных характеристик модулярного представления чисел [1-3]:
-
метод ортогональных базисов;
-
метод интервальных оценок;
-
метод с использованием коэффициентов обобщенной позиционной системы счисления (ОПСС) и другие.
С целью повышения эффективности вычисления позиционной характеристики предлагается новый приближенный метод определения позиционной характеристики, который позволяет реализовать практически все немодульные процедуры модулярного кода.
Исторически так сложилось, что поиск некоторого компромисса в удовлетворении требований, предъявляемых к ПХ, привел исследователей к введению таких характеристик модулярной алгебры, как ранг, след, нормированный ранг, неточный ранг, ядро числа и другие [1, 2, 3, 6]. Анализ этих ПХ показал, что значение модулярной величины по ним определяется сложно и не всегда однозначно. Кроме того, при выполнении некоторых НО нет необходимости в точном их определении, а достаточно знать значения в пределах каких-то интервалов, то есть при определении этих характеристик появляется избыточная информация, которая не используется. Эта идея и подтолкнула к поиску такой позиционной характеристики, которая бы не содержала избыточной информации, на нахождение которой требуются дополнительные вычислительные ресурсы.
Приближенный метод вычисления позиционной характеристики числа на основе использования относительных величин
Анализ немодульных операций показал, что их можно представить точно или приближенно, поэтому методы вычисления позиционных характеристик можно разделить на две группы:
-
методы точного вычисления позиционных характеристик;
-
методы приближенного вычисления позиционных характеристик.
Методы точного вычисления позиционных характеристик рассмотрены в [1-3]. В данной работе исследуются приближенные методы вычисления позиционных характеристик, которые позволяют существенно сократить аппаратные и временные затраты, обусловленные операциями, выполняемыми над позиционными кодами уменьшенной разрядности. В связи с этим возникает задача использования приближенного метода при вычислении определенного ряда немодульных процедур: определения интервалов чисел, знака числа, сравнения чисел, в том случае когда не требуется знания точного значения, насколько одно число больше или меньше другого.
Суть приближенного метода вычисления позиционных характеристик основан на использовании относительных величин анализируемых чисел к полному диапазону
(4)
где A - исследуемое число; pi - модули СОК;
- мультипликативная инверсия Pi относительно pi;
- константы выбранной системы; αi - разряды числа, представленного в СОК, 
- означает дробную часть числа.
Приближенный метод вычисления позиционной характеристики описывается такой последовательностью действий [4, 5]:
1. Вычисление констант СОК 
с требуемой точностью.
2. Вычисление приближенных значений αiki и запись их в LUT-память вычислительной системы, где ki - константы, найденные в п. 1, 
. Адресами выборки значений αiki являются разряды СОК αi, где i = 1, ..., n.
3. Вычисление приближенного значения позиционной характеристики 
в интервале [0, 1). Конечный результат определяется после суммирования и отбрасывания целой части числа с сохранением дробной части суммы. Тогда позиционная характеристика определяется в виде относительного значения величины
4. Конструируются некоторые правила Ψi, i = 1, ..., 4 согласно которым вычисляется i-я немодульная операция (определение знака числа, сравнение чисел, обнаружение ошибки и переполнения, а также локализация ошибочного разряда).
Правило Ψ1. Определение знака числа, в случае, если p1 = 2:
- Если 
, то число положительное;
- Если 
, то число отрицательное.
Правило Ψ2. Сравнение модулярных чисел A и B:
- Если 
, то A = B;
- Если 
, то A > B;
- Если 
, то A < B.
Правило Ψ3. Обнаружение ошибки и переполнения динамического диапазона:
- Если 
, тогда ошибки нет, где 
- искаженное число;
-
избыточный диапазон при двух избыточных модулях pn+1 и pn+2;
- рабочий диапазон.
- Если 
, тогда есть ошибка и установлено переполнение динамического диапазона.
Правило Ψ4. Локализация неисправного канала:
- Если 
, то в разряде i нет ошибки;
- Если 
, то в разряде i есть ошибка, где
- проекция искаженного числа A‾;
- проекция рабочего диапазона.
Пример. Пусть дана система оснований p1 = 2 , p2 = 3 , p3 = 5 , p4 = 7 , объем диапазона P = 2•3•5•7 = 210. Допустим, что в заданной СОК будут представлены только положительные числа. Величины
Сравним два числа A1 = 25 и A2 = 30, представленные в СОК по основаниям p1, p2, p3, p4, так A1 = (1,1,0,4), A2 = (0,0,0,2). Для этого найдем константы 
:
?
?
?
?
По выражению (4) получим
?
?
Так как 
то есть 0,1428 > 0,1189, то A2 > A1, и действительно 30 > 25.
Проблема синтеза немодульных устройств на основе предложенного приближенного метода побуждает к разработке таких правил Ψi, которые бы минимизировали число операций и вместе с тем могли быть достаточно просто реализованы на современной элементной базе.
В зависимости от типа немодульной операции, применяются либо точные, либо приближенные методы, или их комбинация. При необходимости можно использовать приближенные методы и для точных вычислений. В первую очередь необходимо исследовать возможность использования данного приближенного метода для восстановления остаточно- го кода.
Заключение
-
Противоречие между вычислительной сложностью определения основных проблемных процедур в СОК и их быстродействием разрешена путем замены абсолютных величин их относительными значениями и простотой их вычисления, которая сохраняет адекватную связь числовых значений модулярных величин с их представлениям в СОК и позволяет повысить скорость выполнения немодульных операций. Благодаря этому, применение системы остаточных классов может дать значительные преимущества не только в тех приложениях, в которых основная доля вычислений приходится на точное умножение, возведение в степень больших чисел в сочетании со сложением и вычитанием, но и в которых часто появляется необходимость в делении либо сравнении и определении знака числа, а также при проверке не «выходят» ли результаты за пределы допустимых значений и другие.
-
Решена фундаментальная проблема реализации основных проблемных операций в СОК, которые ранее определяли наибольший вклад в алгоритмическую сложность и сдерживали широкое применение СОК при разработке новых классов вычислительных систем. Внедрение полученных результатов позволяет снять это ограничение и расширить область применения модулярной арифметики.
-
Разработанные методы и алгоритмы самых проблемных процедур, характеризующихся простотой и высокой скоростью выполнения операций, дополняют известный универсальный базис СОК на основе обобщенной позиционной системы счисления и позволяют разделить выполнения всех немодульных процедур на два класса: процедуры точного вычисления (вычисления остатка, округления числа, деления, масштабирования, расширения модулярной величины на дополнительные основания и коррекция ошибок) и процедуры приблизительного вычисления (сравнения модулярных чисел, вычисления ранга числа, определения знака числа и переполнения диапазона, обнаружение и локализация ошибок при кодировании помехоустойчивым кодом). Перечисленные классы процедур являются важнейшими для машинной модулярной обработки и требуют глубокого дальнейшего исследования для определения границ их эффективного применения.
-
Полученные новые результаты эффективного выполнения немодульных процедур являются развитием теории математических основ разработки и проектирования высокопроизводительных и надежных вычислительных систем, функционирующих в системе остаточных классов.
Работа выполнена при поддержке гранта РФФИ 12-07-00482-а.
Рецензенты:
-
Мочалов В.П., д.т.н., профессор, зав. кафедрой автоматизированных систем обработки информации и управления СевКавГТУ, г. Ставрополь;
-
Калмыков И.А., д.т.н., профессор, профессор кафедры защиты информатизации СевКавГТУ, г. Ставрополь.
Работа поступила в редакцию 13.04.2012.