Выбор оптимальных оснований системы остаточных классов. Общая структура модулярного сумматора и умножителя, выбор их моделей. Алгоритмы функционирования управляющих устройств сумматора и умножителя. Методы повышения скорости и надежности вычислений.
Аннотация к работе
В настоящее время невозможно представить себе сложную автоматическую систему без того, чтобы ее центральную часть не составляли вычислительные машины, выполняющие функции обработки информации и управления. С другой стороны это - математико-алгоритмический уровень вычислений, и фундаментальными ограничивающими факторами здесь выступают, в числе прочих, необходимость последовательного вычисления, когда следующий этап (шаг) частично или полностью зависит от предыдущих шагов. Даже простейшие арифметические операции сложения и умножения (не говоря уже о делении) при реализации их вычислителями с архитектурой фон-Неймана осуществляются побитово, и вычисление каждого последующего бита зависит от результата операции над предыдущими битами.Если задан ряд положительных целых чисел p1, p2,..., pn, называемых в дальнейшем основаниями системы, то под системой счисления в остаточных классах принято понимать такую систему, в которой целое положительное число представляется в виде набора остатков (вычетов) по выбранным основаниям N = (a1, a2,..., an), причем образование цифр ai осуществляется следующим процессом ai = N - pi, (1.1) где i = 1, 2,..., n. Здесь в отличие от обобщенной позиционной системы образование цифры каждого разряда проводится независимо друг от друга. Цифра i-го разряда ai представляет собой наименьший положительный остаток от деления самого числа N, а не предыдущего частного, как это имело место в позиционной системе, на i-e основание pi. Здесь, как и в обобщенной позиционной системе, диапазон представимых чисел растет как произведение оснований, а разрядность чисел N растет как сумма разрядностей тех же оснований. Далее следует рассмотреть правила выполнения операций сложения и умножения в системе остаточных классов в случае, если оба числа и результат операции находятся в диапазоне [0, P).Поскольку желательно, чтобы P было как можно большим, проще всего принять p1 наибольшим нечетным числом, соответствующим машинному слову, в качестве p2 принять наибольшее нечетное число <p1, взаимно простое с p1, а в качестве p3 - наибольшее нечетное число <p2, взаимно простое как с p1, так и с p2, и т.д., пока не наберется столько pj, сколько будет достаточно для образования нужного P[1]. При работе на двоичных компьютерах иногда желательно выбирать модули pj иным образом: pj = 2ej - 1. Такой выбор значения модуля pj зачастую упрощает выполнение основных арифметических операций, т.к. выполнять вычисления с числами, представленными по модулю 2ej-1, несколько проще, чем с числами, представленными в обратном коде. После того, как значения модулей выбраны таким образом полезно несколько ослабить условие 0 ? ai<pj и потребовать только, чтобы 0 ? ai<2ej, (1.12) ai ? N (mod 2ej - 1), (1.13) Таким образом, значение pj = 2ej-1 принимается в качестве оптимального, поскольку это означает, что pj может быть любым ej-битовым двоичным числом[1].Основным достоинством СОК является то, что арифметические операции производятся в ней независимо по каждому из модулей, следовательно, они могут выполняться параллельно по L вычислительным каналам: Обобщенная структура устройств цифровой обработки сигналов в модулярной арифметике представлена на рисунке 1.1.В состав любого цифрового устройства входят операционный автомат и управляющий автомат. Операционный автомат имеет информационные входы I и входы z управления; информационные выходы D, а также выходы u, которые сигнализируют о результатах выполнения операций. Управляющий автомат вырабатывает символы z управления операционным автоматом по заданной программе с учетом значений внутренних u и внешних v логических условий, которые для него являются входными переменными. На выходах у управляющего автомата могут быть сформированы символы, несущие информацию для внешних устройств о состоянии цифрового устройства. Управляющий автомат определяет логику работы устройства, т.е. последовательность и тип операций, выполняемых операционным автоматом над исходными данными.Существует достаточно большое количество подходов к реализации сумматоров по модулю m. Далее будут рассмотрены наиболее типичные и простые схемы модулярного суммирования. Для больших модулей, память LUT была бы значительного размера и другие схемы для суммирования оказываются в этом случае более предпочтительными.Более того, существование обратного по умножению по модулю мдля 2 элемента,, гарантируется только в случае, если 2 не делит m (т.е. m - нечетно). Умножители, основанный на арифметике указателей [12, 13] является сравнимой альтернативой по сложности и скорости умножителям, основанным на законе квадратов. Их использование ограничено простыми модулями и основывается на осуществлении преобразования в степенную форму (так называемое степенное исчисление), в котором умножение может более быстро осуществляться посредством операции суммирования. Это свойство полей Галуа можно использовать для умножения в GF(mj)благодаря использованию изоморфизма между мультипликативной по модулю mj группой Q = {1,2,…,m-1}, и аддитивной по
План
Содержание
Введение
1. Обзор системы остаточных классов и основные теоретические сведения
1.1 Основные понятия системы остаточных классов
1.2 Выбор оптимальных оснований СОК
1.3 Модулярные вычисления
1.4 Общая структура цифровых устройств
2. Разработка сумматора и умножителя
2.1 Выбор модели сумматора по модулю m
2.2 Выбор модели умножителя по модулю m
3. Постановка задачи
4. Разработкасумматора по модулю m
4.1 Примеры функционирования сумматора по модулю m
4.2 Пример управляющего устройства сумматором по модулю m
5. Разработкаумножителя по модулю m
5.1 Примеры функционирования умножителя по модулю m
5.2 Пример управляющего устройства умножителем по модулю m
6. Тестирование сумматора и умножителя
7. Алгоритм функционирования
8. Выбор ПЛИС семейства CYCLONEIII
9. Структурная схема устройства
Заключение
Введение
В настоящее время невозможно представить себе сложную автоматическую систему без того, чтобы ее центральную часть не составляли вычислительные машины, выполняющие функции обработки информации и управления. Поэтому очевидна ценность исследований методов ускорения расчетов и повышения производительности вычислительных машин.
Задачу повышения скорости и надежности вычислений можно рассматривать с двух сторон. С одной стороны это аппаратный уровень, фундаментальными ограничениями на котором являются технические возможности создания элементной базы - уменьшение размеров кристаллов, увеличение частоты синхронизации (тактовой частоты), решение проблем теплоотвода и др. Во многом этот уровень определяется современным состоянием фундаментальных наук, прежде всего, физики. С другой стороны это - математико-алгоритмический уровень вычислений, и фундаментальными ограничивающими факторами здесь выступают, в числе прочих, необходимость последовательного вычисления, когда следующий этап (шаг) частично или полностью зависит от предыдущих шагов. Даже простейшие арифметические операции сложения и умножения (не говоря уже о делении) при реализации их вычислителями с архитектурой фон-Неймана осуществляются побитово, и вычисление каждого последующего бита зависит от результата операции над предыдущими битами. Существуют и другие вычислительные архитектуры, в которых акцент сделан на параллельность и массовость вычислений. Большую популярность сейчас имеют нейронные сети, которые, обладая алгоритмической универсальностью машины Тьюринга, уже доказали свое преимущество в слабо формализованных задачах, связанных с необходимостью обучения. Использование системы остаточных классов (СОК) и модулярных вычислений позволяет существенно увеличить скорость арифметических вычислений за счет параллельного выполнения операций над остатками.