Вопрос 42. Аппаратные методы ускоренного умножения: умножители по схеме Уоллеса.

Теория от Попова

Умножение сводится к последовательному формированию частных произведений и их сложению.

По способу формирования частных произведений различают следующие виды умножения:

• умножение со старших разрядов множителя со сдвигом влево;

• умножение с младших разрядов множителя со сдвигом вправо.

По способу накопления частных произведений различают следующее виды умножителей:

• матричные умножители;

• древовидные умножители.

Способы ускорения работы устройств умножения:

• сокращение количества частных произведений;

• обработка нескольких разрядов множителя за такт;

• параллельное вычисление нескольких СЧП;

• конвейеризация умножителей.

Древовидные умножители. Схема Уоллеса.

Рисунок 42.1 – Схема Уоллеса

Теория из учебника

В наиболее общей формулировке дерево Уоллеса - это оператор с n входами и log₂n выходами, в котором код на выходе равен числу единиц во входном коде. Вес битов на входе совпадает с весом младшего разряда выходного кода. Простейшим деревом Уоллеса является полный сумматор (СМ). Используя такие сумматоры, а также полусумматоры, можно построить дерево Уоллеса для перемножения чисел любой разрядности, при этом количество сумматоров возрастает пропорционально величине log₂n. В такой же пропорции растет время выполнения операции умножения.

Согласно алгоритму Уоллеса, строки матрицы частичных произведений группируются по три. Полные сумматоры используются для сжатия столбцов с тремя битами, а полусумматоры - столбцов с двумя битами. Строки, не попавшие в набор из трех строк, учитываются в следующем каскаде редукции. Количество строк в матрице (ее высота) на j-й ступени определяется выражениями w_о = n и w_j+1=2[w_j3]+(V_j mod 3), пока w_j >=2.

В 32-разрядном умножителе на базе дерева Уоллеса высоты матриц частичных произведений последовательно уменьшаются в последовательности: 22,15, 10, 7, 5, 4, 3 и 2.

Краткое объяснение от Алекса:

На рисунке 42.1 показана схема ускоренного умножения Уоллеса. На этом рисунке закрашенные кружочки представляют собой частичные произведения, а не закрашенные пунктирные кружочки – дополнительные переносы, используемые в конечном суммировании для получения результата. Прямоугольники, включающие два кружочка, представляют собой – полусумматоры. А прямоугольники, включающие три кружочка, – полные сумматоры.

Слева показана четырех ступенчатая схема. Справа трёх ступенчатая. Схемы отличаются по применению полусумматоров и полных сумматоров. В остальном схемы подобны. Вероятно, отличаются по скорости умножения, так как каждая операция суммирования занимает дополнительное время. В таком случае более быстрой является схема, показанная справа.

Вопрос 43. Деление с восстановлением и без восстановления остатка. Структура арифметико-логического устройства для целочисленного деления.

Теория от Попова

Алгоритм:

1) ЧО = Делимое;

2) ЧО = ЧО*2;

3) ЧО = ЧО – Делитель * 2ⁿ;

4) Если ЧО<0 то

Ч<-0,

ЧО = ЧО + Делитель * 2ⁿ

иначе Ч<-1;

5) Если все цифры то конец

иначе пункт 2.

Рисунок 43.1 – Деление с восстановлением остатка

Рисунок 43.2 – Деление без восстановления остатка. Схема АЛУ для целочисленного деления

Теория из учебника

Деление с восстановлением остатка

Наиболее очевидный алгоритм носит название алгоритма деления с неподвижным делителем и восстановлением остатка. В учебнике он представлен в силу того, что очень похож на общепринятый способ деления столбиком. Данный алгоритм может быть описан следующим образом:

1. Исходное значение частичного остатка полагается равным старшим разрядам делимого.

2. Частичный остаток удваивается путем сдвига на один разряд влево. При этом в освобождающийся при сдвиге младший разряд частичного остатка заносится очередная цифра частного.

3. Из сдвинутого частичного остатка вычитается делитель и анализируется знак результата вычитания.

4. Очередная цифра модуля частного равна единице, когда результат вычитания положителен, и нулю, если отрицателен. В последнем случае значение остатка восстанавливается до того значения, которое было до вычитания.

5. Пункты 2-4 последовательно выполняются для получения всех цифр модуля частного.

Деление без восстановления остатка

Недостаток затронутого алгоритма заключается в необходимости выполнения на отдельных шагах дополнительных операций сложения для восстановления частичного остатка. Это увеличивает время выполнения деления, которое в этом случае может меняться в зависимости от конкретного сочетания кодов операндов. В силу указанных причин реальные делители строятся на основе алгоритма деления с неподвижным делителем без восстановления остатка. Приведем описание этого алгоритма.

1, Исходное значение частичного остатка полагается равным старшим разрядам делимого.

2, Частичный остаток удваивается путем сдвига на один разряд влево. При этом в освобождающийся при сдвиге младший разряд частичного остатка заносится очередная цифра частного.

3, Из сдвинутого частичного остатка вычитается делитель, если остаток положителен, и к сдвинутому частичному остатку прибавляется делитель, если остаток отрицательный.

4. Очередная цифра модуля частного равна единице, когда результат вычитания положителен, и нулю, если он отрицателен.

5. Пункты 2-4 последовательно выполняются для получения всех цифр модуля частного.

Как видим, пункты 1,2,5 полностью совпадают с соответствующими пунктами предыдущего алгоритма деления.

Арифметико-логическое устройство для целочисленного деления

Рассмотренный алгоритм деления без восстановления остатка может быть реализован с помощью устройства, схема которого приведена на рисунке 43.2.

Процедура начинается с занесения делимого в 2n-разрядный регистр делимого (регистр частного остатка) и делителя в n-разрядный регистр делителя. В счетчик цикла (на схеме не показан), служащий для подсчета количества полученных цифр частного, помещается исходное значение, равное n.

На каждом шаге содержимое регистра частного остатка и регистра частного сдвигается на один разряд влево. В зависимости от сочетания знаков частичного остатка и делителя определяется значение очередной цифры частного и требуемое действие: вычитание или прибавление делителя. Вычитание делителя производится посредством прибавления дополнительного кода делителя. Преобразование в дополнительный код осуществляется за счет передачи делителя на вход сумматора обратным (инверсным) кодом с последующим добавлением единицы к младшему разряду сумматора.

Описанная процедура повторяется до исчерпания всех цифр делимого, о чем свидетельствует нулевое содержимое счетчика циклов (содержимое счетчика циклов уменьшается на единицу после каждой итерации). По окончании операции деления частное располагается в регистре частного, а в регистре частного остатка будет остаток от деления.

На заключительном этапе, если это необходимо, производится корректировка полученного результата, как это предусматривает алгоритм деления чисел со знаком.

На практике для накопления и хранения частного вместо отдельного регистра используют освобождающиеся в процессе сдвигов младшие разряды регистра частного остатка.

Краткое объяснение от Алекса:

Суть методов деления базируется на операции сложения в дополнительном коде (то есть вычитании) и сдвигах влево (то есть операциях умножения на 2). Деление в двоичной системе «в столбик» соответствует делению в десятичной системе в столбик. Количество разрядов делимого должно быть в 2 раза больше количества разрядов делителя. Если меньше, то дополняется нулями слева до нужного числа разрядов. То есть у делимого 2n разрядов, а у делителя n разрядов.

Итак, на каждом шаге производится сравнение n разрядов делимого и делителя. Сравнение проводится операцией вычитания. Если результат оказывается положительным (делимое больше), то в частное добавляется 1, если же результат оказывается отрицательным (делитель больше), то в частное добавляется 0, делимое восстанавливается и сдвигается влево (если это метод с восстановлением остатка), или трактуется как отрицательное число и просто сдвигается влево (если это метод без восстановления остатка).

Количество итераций определяется разрядностью делителя. То есть всего n итераций. Как только счетчик циклов обнуляется, деление прекращается. Можно произвести корректировку результата, если нужно. В регистре частного будет храниться результат целочисленного деления. А в старших n разрядах регистра делимого (частного остатка) – остаток от целочисленного деления.