Устройство для вычисления скалярного произведения векторов с коррекцией ошибок на базе системы остаточных классов Авторы: Соловьев Р.А. (докладчик) Д.В. Тельпухов, Е.С. Балака Институт проблем проектирования в микроэлектронике ИППМ РАН

Скалярное произведение векторов (СПВ).

Ускорение вычислений СПВ. Схема конвейеризации умножителя

Модулярная арифметика. Позиционная система счисления Система счисления, в которой значение каждой цифры в записи числа зависит от его позиции. Система остаточных классов (СОК) Для системы взаимно простых чисел p 1, p 2, … p n, любое число X из диапазона [0; M), M = p 1 *p 2 *…*p n представимо в виде вектора (a 1, a 2, …, a n ), где a i = X mod p i. p 1, … p n – модули системы a 1, a 2, …, a n – остатки числа по заданной системе модулей. Параллелизм вычислений Низкая разрядность вычислений Простая реализация арифметических операций Возможность для коррекции ошибок Сложность сравнения чисел Сложность определения переполнения Необходимость в преобразователях в /из позиционной системы счисления

Обнаружение и коррекция ошибок в СОК p3p3 p1p1 p2p2 p u-1 pupu p u+1 p u+2 pnpn … Информационные модули … Контрольные модули Легитимный Диапазон [0;M-1] Нелегитимный Диапазон [M;M*K] M=p 1 p 2 … p u K=p u+1 p u+2 … p n Численный пример Информационные модули: 3, 5, 7 Контрольные модули: 8, 11 Легитимный диапазон: [0;105) 56 = (2,1,0,0,1) (2,3,0,0,1) Набор модулей Значения в СОКЗначение в позиционной записи (5,7,8,11)(3,0,0,1)1288 (3,7,8,11)(2,0,0,1)56 (3,5,8,11)(2,3,0,1)848 (3,5,7,11)(2,3,0,1)518 (3,5,7,8)(2,3,0,0)728

Выбор базисных оснований в СОК Что бы избежать затратной операции округления, можно выбрать динамический диапазон покрывающий все возможные значения результата скалярного произведения. Размерность элемента вектора в битах (k) Количество элементов вектора l Возможный базисMРазмерность максимального результата вычислений (бит) 816{5, 7, 11, 13, 17, 19} { 2, 3, 5, 7, 11, 13, 17, 19, 23 } {7, 11, 13, 17, 19, 23, 29, 31} {31, 37, 41, 43, 47, 53, 59, 61}

Прямой преобразователь в СОК 0 бит Х 1 бит 2 бит … k бит A0A0 A1A1 A2A2 AkAk Пирамида льный сумматор Блок финальной редукции S |Х|p|Х|p

Умножение и сложение по модулю в СОК 3 метода умножения по модулю 1)Обычное умножение с последующей коррекцией 2)Индексный метод 3)Метод разности квадратов IF (R P) O = R – P ELSE O = R + Схема индексного умножения Схема сложения по модулю Пример индексного умножения по модулю 5

Обратный преобразователь СОК Схема обратного преобразователя для системы из 4 модулей В конвейерных схемах обычно применяют преобразователи на базе полиадического кода из-за однородности их структуры. Основная операция для блоков ROM: Из-за малой размерности a и b, а также в силу того что константы p известны на этапе проектирования, эти блоки на критичных к скорости участках, могут быть заменены на таблицы.

Общая схема работы СПВ в СОК

Экспериментальные результаты

Преимущества подхода и нерешенные проблемы 1)Не уступает, а иногда и превосходит по скорости двоичную реализацию 2)Гибкий контроль набора модулей для исправления кратных ошибок 3)Не требует преобразователей в случае работы в модулярном представлении 1)Превосходит по площади двоичные аналоги 2)Более сложная структура 3)Массивный обратный преобразователь, вносящий потенциальные ошибки во время выбора правильного ответа Дальнейшее направление исследований: 1) Проверка эффективности устройства для исправления многократных ошибок 2) Использование улучшенных блоков модулярной арифметики с целью увеличения выигрыша по площади и скорости работы скалярного произведения