Построение специализированных схем

Два варианта быстрых схем

1). Аппаратное умножение

P_i+1 = P_i + A×2×b_i+1

См. Угрюмов «Элементы и узлы ЦЭВМ»

Если не хотим задержку для регистра, за каждой операцией умножения закрепляем сумматор.

t - задержка на каждом сумматоре

(2n-1)t - время на умножение двух n-разрядных чисел

в результате умножение происходит примерно в два раза медленнее, чем обычное сложение ( )

Для построения быстрого устройства умножения используется методика закрепления – за каждой операцией закрепляется свое устройство

2). Табличный способ

Аргумент линейно возрастает

Значение аргумента совпадает с номером строки – хорошая таблица

Аргумент – адрес

Значение функции – то значение, которое хранится по адресу

Такая организация каких-либо операций – это основа таблично-алгоритмических методов

Память (ЗУ) не является памятью автомата

ЗУ, которое в течение работы не меняет своего значения – это КС (комбинационная схема); если память меняет свое значение, то это память автомата.

Рассмотрим таблицу, в которой приводится объем памяти ЗУ для хранения результатов операции умножения двух чисел;

n – разрядность множимого и множителя

2n – разрядность произведения

№	n	V1	V2	V3
		64Kб ´ 16р	256 б ´ 16р	16 б ´ 8р
		4Гб ´ 32р	64 Кб ´ 32р	256 б ´ 16р
		234Гб ´ 64р	4 Гб ´ 64р	64 Кб ´ 32р

1 – перемножаются 8-ми разрядные числа

2 – перемножаются 16-ти разрядные числа

3 – перемножаются 32-х разрядные числа

V₁ – обычное умножение; имеется 2ⁿ множимых 2ⁿ множителей, в итоге количество результатов 2ⁿ ×2ⁿ×n

Например, умножаются два 16-ти разрядных числа

2¹⁶*2¹⁶ – количество результатов операции умножения

16 – разрядность результата

2¹⁶*2¹⁶*16 бит ´ 32р = 2³⁰*2² ´ 32р = 4 Гб ´ 32р будет занимать таблица результатов

Попытаемся уменьшить объем таблицы

V₂ рассмотрим вычисление меньшего объема

(A – B)² = A² + B² – 2·A·B квадрат разности

т.е. произведение двух чисел можно представить в виде

Умножение при наличии таблицы квадратов можно осуществить примерно за 6 тактов

Например, умножаются два 8-ми разрядных числа

2⁸ – возможное количество результатов операции умножения

2⁸*16р = 256 ´ 16р будет занимать таблица результатов

V₃ рассмотрим вычисление меньшего объема

Разобьем число на две части

A = A₁ + A₂ · 2^n/2

сдвиг вправо на n/2 разрядов

AB = (A₁+A₂·2^n/2)·( B₁+B₂·2^n/2) = A₁·B₁ + A₁·B₂·2^n/2 + A₂·B₁·2^n/2 + A₂·B₂·2ⁿ

Умножение двух чисел будем производить как в предыдущем случае

Например, умножаются два 8-ми разрядных числа

2⁴ – возможное количество результатов операции умножения

2⁴*4р = 256 ´ 8р будет занимать таблица результатов

Малорегистровая и многорегистровая структура автоматов. Варианты реализации аккумулятора.

Если n ³ 4 (n – число слов), то выгодно использовать РЗУ

Слова – известные программе или некоторые внутренние (собственные) слова алгоритма

Например, вспомним команду JSB (переход на подпрограмму) – под считанный адрес отводится внутренняя переменная

Микропрограммный аккумулятор – аккумулятор это одна из ячеек РЗУ, доступ к нему осуществляется как к одному из регистров; может быть обращение к аккумулятору по умолчанию

Рг_расш вводится для ускорения операций умножения, деления

Регистры собираются в РЗУ

Микрокоманда – совокупность УС (управляющих сигналов), вырабатываемых за 1 такт.