Скачиваний:   0
Пользователь:   andrey
Добавлен:   13.01.2015
Размер:   317.0 КБ
СКАЧАТЬ

2.5 Умножители

 

Пусть a=a[n-1:0] и b=b[m-1:0], тогда

 

2_5

 

Поэтому данное произведение может быть представлено через n+m бит.

 

(n,m)-Умножитель – это схема с n-битным входом  a=a[n-1:0], с m-битным входом

b=b[m-1:0] и n+m-битным выходом p=p[n+m-1:0], удовлетворяющая следующему условию: 2_5

 

2.5.1 Метод “Умножения столбиком”

 

Очевидно, что произведение 2_5 может быть представлено в виде суммы частичных произведений:

2_5

для которой

2_5

Поэтому все частичные произведения, входящие в сумму могут быть вычислены за цену, равную n*m*C& при задержке D&. Обозначим  сумму k частичных произведений в интервале от j до j+k-1 как Sj,k

 

2_5

 

Благодаря тому, что Sj,k  кратно 2j, его можно представить в виде двоичного числа  c j нулевыми  младшими разрядами. Так как Sj,k  меньше чем 2j+n+k , его можно представить в виде двоичного числа длиной n+j+k (см. рис 2.25). Таким образом, мы имеем

 

2_5

 

Последняя строчка из приведенных выше выражений предлагает нам очевидную конструкцию умножителя, состоящего из m-1 n-разрядных сумматоров.  Такая конструкция умножителя соответствует методу умножения натуральных чисел столбиком. Если используемые в схеме сумматоры представить в виде сумматоров c последовательным переносом, то цена и задержки для такой схемы могут быть ограничены следующими выражениями:

 

2_5

 

 

 

 

 

2_5

рис. 2.25    Sj,k  - сумма k частичных произведений в интервале от j до j+k-1

 

 

2.5.2 Сумматоры с сохраняемым переносом

 

Пусть x – натуральное число и пусть существуют два двоичных числа s[n-1:0] и t[n-1:0], такие что

 

2_5

 

Тогда s и t называют представлением x с сохраняемым переносом длиной n.

Важнейшим строительным блоком в схемах для ускорения сложения частичных произведений является n-разрядный сумматор с сохраняемым переносом. Такой сумматор представляет собой схему с входами a[n-1:0], b[n-1:0], c[n-1:0] и выходами s[n-1:0], t[n:0], такими что

 

2_5

 

т.е. выходы s и t являются представлениями с сохраняемым переносом для входов a, b и c.

Сумматоры с сохранением переноса, сжимающие сумму 3-х чисел в 2-а числа, имеющих такую же сумму, часто называют n-разрядными 3/2 сумматорами. Такие сумматоры реализуются в соответствии со схемой 2.26 простым параллельным включением n полных сумматоров. Такая схема будет работать правильно, потому что

 

2_5

 

Цена и задержка для такого сумматора может быть посчитана следующим образом:

 

2_5

 

Основным достоинством данной конструкции является полная независимость задержки сумматора от n.

 

 

 

 

 

 

 

 

 

 

2_5

 

рис. 2.26    Схема n-разрядного сумматора с сохранением переноса, т.е. схема n-разрядного 3/2 сумматора

 

 

2_5

 

рис. 2.27    Схема (n,m)-умножителя

 

 

 

 

2.5.3 Перемножающие матрицы

 

Суммирующее дерево для m-операнд представляет собой схему, принимающую на входе m двоичных чисел и выдающую на выходе их сумму с сохраняемым переносом.  Используя суммирующие деревья, можно конструировать (n,m)-умножители так, как это предложено на схеме 2.27. Первый блок будет генерировать бинарные представления для m частичных произведений  St,1, которые затем будут подаваться на суммирующее дерево для m операндов. Тогда на выходе дерева мы получим представленное в виде с сохранением переноса искомое произведение, которое нужно будет перевести в  двоичный вид для получения конечного результата. Последнюю операцию можно осуществить при помощи обычного сумматора.

Пользуясь схемой 2.28, сконструируем  простейшее семейство суммирующих деревьев. На рисунке 2.28(а) изображены представления частичных сумм S0,1, S1,1 и S2,1 , которые подаются на n-разрядный сумматор с сохранением переноса. Конечный результат – представление с сохранением переноса  S0,3 с длиной n+3. На рисунке 2.28(b) представление St-1,1 и представление с сохранением переноса  S0,t-1 подаются на вход n-разрядного сумматора с сохранением переноса. Результат - представление с сохранением переноса  S0,t с длиной n+t. При предлагаемом на схеме каскадном включении m-2 n-разрядных сумматоров с сохранением переноса, мы получим суммирующее дерево, часто называемое перемножающей матрицей из-за своей структуры.

Если последняя операция сложения выполняется при помощи сумматора с предварительным переносом, то цена и задержка для такой схемы вычисляются по формулам:

 

 

 

 

 

 

2_5

 

рис. 2.28      Генерация представления с сохранением переноса частичных сумм  S0,3 (а) и S0,t (b)

 

 

 

2_5

 

 

2.5.4   4/2 Деревья

 

Задержка для перемножающих массивов пропорциональна m. Очевидно, что следующий шаг – это балансировка суммирующих деревьев с уменьшением задержки до  O(logm). Мы будем использовать стандартную, широко распространенную схему, которую достаточно просто анализировать.

 n-разрядный 4/2 сумматор представляет собой схему со входами a[n-1:0], b[n-1:0], c[n-1:0], d[n-1:0] и выходами s[n-1:0], t[n-1:0], такими что

 

2_5

 

Самый очевидный вариант реализации n-разрядного 4/2 сумматора из двух n-разрядных 3/2 сумматоров показан на рис. 2.29. Цена и задержки для него

 

2_5

 

 

Законченные суммирующие деревья.

 С помощью 4/2 сумматоров становится возможным построение полностью сбалансированных суммирующих деревьев. Для этого можно воспользоваться рекурсивным построением, предложенным на схеме 2.30. Следует заметить, что мы пока не определили ширину операндов. Таким образом, схема 2.30 пока не является полностью законченной. Пусть 2_5 будет степенью двойки. Следуя данной конструкции,

 

 

 

 

 

 

 

 

 

2_5

 

рис 2.29     Схема n-разрядного 4/2 сумматора

 

 

2_5

 

рис 2.30     Полностью сбалансированное суммирующее дерево T(K) с 2K операндами S0,…,S2k-1, где K – степень двойки; a) Дерево T(2) b) Дерево T(K).

 

 

 

можно получить суммирующее дерево T(K) c 2K входами. Такое 4/2 дерево T(K) имеет задержку, равную

 

2_5

 

 

Незаконченные суммирующие деревья

 

Для того чтобы сконструировать отвечающий требованиям IEEE FPU, нам придется сконструировать (n,m)-умножитель, для которого m не является степенью двойки. Пусть

 

2_5

 

Т.о. M – наименьшая степень двойки при 2_5. Согласно стандарту IEEE для плавающей точки [Ins85] и алгоритму деления, используемому  в FPU, длина 2_5 операнда b[m-1:0],  и отсюда количество операндов суммирующего дерева, должны удовлетворять условию:

 

2_5

 

В таком случае, мы создаем суммирующее дерево T(m) c m операндами, как предложено на рис. 2.31. Дерево T(m) имеет глубину м. Нижняя часть дерева –

 

 

 

 

 

2_5

 

Рис 2.31    Схема 4/2 суммирующего дерева T(m), складывающего входы S0,…,Sm-1

 

 

полностью сбалансированное правильное 4/2 Дерево T(M/4) с M/4 парами входов и М/8 4/2 сумматорами в качестве листьев. На верхнем уровне a 4/2 сумматоров и M/4 – a 3/2 сумматоров. Здесь а – решение уравнения:

 

2_5

 

откуда

 

2_5

 

Заметьте, что для каждого i=0,1,…, частичные произведения Si,1  вводятся в дерево справа налево, и на верхнем уровне дерева 3/2 сумматоры располагаются слева от 4/2 сумматоров. Для такой схемы умножителя задержка будет следующей:

 

2_5

 

 

Цена суммирующих деревьев

Посчитать цену дерева – более сложная задача. Для этого необходимо посчитать цену для всех 3/2 и 4/2 сумматоров, участвующих в конструкции. Чтобы решить данную проблему, суммирующие деревья рассматриваются как полностью бинарные деревья T  с точки зрения теории графов. Каждый 3/2 или 4/2 сумматор рассматривается как узел v дерева,

3/2 или 4/2 сумматоры верхнего уровня дерева – как листья дерева T.

 

Цену листьев определить легко. Представления с сохранением переноса для сумм Si,3 считаются n-разрядными 3/2 сумматорами так, как показано на схеме 2.28 (а). Длина представления – n+3. Схема 2.32 показывает, что  представления с сохранением переноса для сумм Si,4 могут быть вычислены двумя n-разрядными 43/2 сумматорами.

 

 

 

 

 

 

 

 

 

 

 

2_5

 

рис. 2.32     Частичная компрессия Si,4

 

Длина представления – n+4. Т.о. мы имеем

 

2_5

 

для всех листьев v из T.

 

Пусть v – внутренний узел дерева, имеющий дочерние узлы L(v) и R(v) слева и справа соответственно. Тогда узел v вычисляет представление с сохранением переноса суммы

 

2_5

 

где R(v) дает представление с сохранением переноса Si,k и L(v) дает представление с сохранением переноса Si+k,h . Если длины представлений i+k и i+k+h соответственно, то согласно уравнению (2.4) мы находимся в ситуации, описанной на рис. 2.33. Т.о. узел v состоит из 2n+2h полных сумматоров.

Если все 3/2 сумматоры в дереве будут включать в себя n полных сумматоров, и если все 4/2 сумматоры в дереве будут включать в себя 2n  полных сумматоров, тогда цена дерева будет равна n(m-2). Т.о. остается лишь посчитать количество избыточных полных сумматоров в дереве.

 

 

Комбинаторная лемма

 

Пусть T  - законченное бинарное дерево с глубиной м. Пронумеруем уровни l от листьев до корня от 0 до м. Каждый лист имеет вес W(u). Для любого натурального числа k,  имеется 2_5 для всех листьев, и веса не уменьшаются слева направо.  Пусть m – сумма весов

 

 

 

 

 

 

 

 

 

2_5

рис. 2.33    Частичная компрессия Si,k+h

 

 

листьев. Пусть для каждой м = 4, m=53 и k=3, листья будут, предположим, весить 3333333333344444. Для каждого поддерева t в дереве T определяем

 

2_5

 

где u изменяется в пределах всех листьев t. Для каждого внутреннего узла v дерева T определяем L(v) и R(v) как вес поддерева, начинающегося в левом или правом дочернем узле v соответственно. Нам интересны суммы

 

2_5

 

где v изменяется в пределах всех узлов уровня l. Тогда цена H

 

2_5

 

Доказательство:

 

Разбивая дерево T на уровни, легко увидеть, что веса не уменьшаются слева направо для каждого отдельно взятого уровня и их сумма равна m. Т.о.

 

2_5

 

Это доказывает справедливость верхней границы.

 

Доказывая справедливость верхней границы мы заместили каждый вес L(v) арифметическим значением L(v) и R(v), переоценивая L(v) на

 

2_5

 

 

 

 

 

 

Заметьте, что все узлы уровня l , кроме возможно одного, имеют веса в диапазоне

2_5. Т.о. на каждом уровне l максимум один узел vl, у которого 2_5.

Для этого узла

 

2_5

 

Т.о., ошибка в значении верхней границы не превышает

 

2_5

 

Конец доказательства.

 

Теперь мы можем использовать эту лемму для вычисления количества избыточных полных сумматоров в суммирующем дереве T(m) для схемы 2.31. Для этого, обозначим каждый лист u дерева T(m) номером W(u) частичного произведения, которое он суммирует. Т.е. для 3/2 сумматора, u обозначено номером W(u)=3, а для 4/2 сумматора u обозначено номером W(u)=4. Согласно 2.31, имеем

 

2_5

 

и тогда количество избыточных полных сумматоров E ровняется

 

2_5

 

Тогда ошибка в этой границы не превышает

 

2_5

 

Очень хорошей верхней границей для цены 4/2 дерева будет

 

2_5

 

Хорошей верхней границей для  цены умножителя, построенного на 4/2 деревьях, будет

 

2_5

 

 

2.5.5  Умножители с кодированием Бута

 

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

 

 

 

 

 

 

2_5

 

рис 2.34     Структура (m,n) умножителя Бута с суммирующим деревом.

 

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

 

На рисунке 2.34 изображена структура 4/2 умножителя с кодированием Бута. Схема bgen генерирует m` закодированных методом Бута частичных произведений S`2j,2, которые потом подаются на суммирующее дерево Бута. Наконец, обычный сумматор получает конечный результат произведения в бинарном виде из представления с сохранением переноса. Т.о. цена и задержка для (n,m) умножителя с 4/2 деревом и кодированием Бута может быть посчитана как

 

2_5

 

 

кодирование Бута-2

 

В простейшем виде (такой вид называется Бут-2) умножитель b кодируется, как предложено на рис. 2.35. Для bm+1= bm= b-1=0 и m`=[(m+1)/2], справедливо

 

2_5

 

где

 

2_5

 

Числа 2_5 называют Бутовыми цифрами, а их знаковый бит определяется как

 

2_5

 

 

 

 

 

 

2_5

 

рис. 2.35  Бутовы цифры B2j

 

Для

 

2_5

 

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

 

2_5

 

Для того, чтобы избежать отрицательных значений C2j, нужно вместо этого суммировать положительный E2j

 

2_5

 

Рис. 2.36 иллюстрирует вышесказанное. Дополнительные термы прибавляются к

 

2_5

 

Так как 2*m`>m, эти термы соответствуют нулю по модулю 2n+m. Т.о.

 

2_5

 

Лемма 2.6: двоичное представление e2j от E2j может быть вычислено через:

 

2_5

 

 

 

 

 

 

2_5

 

рис. 2.36     Суммирование E2j

 

 

Доказательство:

 

Для каждого j>0 и s2j = 0, имеем

 

2_5

 

 

Для каждого j>0 и s2j = 2, имеем

 

2_5

 

Тогда для j=0 понятно, что

 

2_5

 

Конец доказательства.

 

Согласно лемме 2.6, вычисление чисел

 

2_5

 

производится очень просто, а именно

 

2_5

 

2_5

 

рис. 2.37    Схема частичных произведений S`2j,2

 

 

Вместо того, чтобы добавлять знаковые биты s2j к числам F2j, их объединяют по подходящим позициям в представление F2j+2, как это показано на рис. 2.37. Последний знаковый бит не создает проблем, потому что B2m`-2 всегда положительно. Допустим

 

2_5

 

тогда

 

2_5

 

И если s-2=s2m’-2=0, то произведение можно также записать в виде

 

2_5

 

Если

 

2_5

 

то

 

2_5

 

Отсюда вытекает

 

Лемма 2.7 : S`2j,2k кратно 22j-2 ограничено 2_5. По этому нужно как минимум n+4+2k не нулевых позиций для представления S`2j,2k в обеих - сохраняющей перенос и двоичной формах.

 

 

 

 

Доказательство:

 

Для k=1:

2_5

 

Для k>1: нам это известно из предположения , что 2_5 . Т.о.

 

2_5

 

Конец доказательства.

 

2.5.6 Цена и задержка умножителя Бута

 

Генерация частичных произведений.  Двоичное представление чисел S`2j,2 должно быть вычислено (см. рис. 2.37). Эти числа

 

2_5

 

сдвинуты на 2j-2 битовых позиций. 2_5 легко определяются через B2j и a из

 

2_5

 

Для данного расчета необходимы два сигнала, указывающие на | B2j | = 1 и |B2j| = 2 . Мы обозначим эти сигналы как

 

2_5

 

и вычислим их при помощи Бутовой декодирующей логики  BD (см. рис. 2.38(а)). Декодирующую логику BD можно взять из таблицы 2.6 . Она будет иметь следующую цену и задержку:

 

2_5

 

Выбирающая логика BSL (см. рис. 2.38 (b))  направляет один из битов: либо a[i], либо a[i+1] либо 0 на позицию i+1. После чего инверсия, в зависимости от знакового бита s2j, выдает бит g2j[i+3]. Выбирающая логика BSL имеет следующую цену и задержку:

 

2_5

 

 

Таблица 2.6    Представление Бутовых  цифр

 

2_5

 

 

 

2_5

 

рис. 2.38     Бутова декодирующая логика  BD (а) и Бутова выбирающая логика BSL (b)

 

 

Выбирающая логика BSL используется только для выборки битов g2j[n+2:2]; оставшиеся биты g2j[1:0] и g2j[n+5:n+3] фиксированы. Для этих битов вместо BSL используется обычный сигнал знакового бита, его инверсии, единицы или нуля. Т.о. для каждого из m` частичных произведений необходимо n+1 BSL. Общая цена всего препроцессора Бута равна

 

2_5

 

 

Добавочная информация по частичным произведениям

Пусть M`=2log(m`) будет меньшей степенью двойки, большей или равной m`=[(m+1)/2], и пусть м` = log(M/4).  Для любых 2_5 имеем

 

2_5

 

Рассмотрим конструкцию Бутового 4/2 суммирующего дерева Т`(m`) также как и в параграфе 2.5.4, однако остановимся только на тех деревьях, которые удовлетворяют поставленному выше условию.

Стандартная длина 3/2 сумматоров и 4/2 сумматоров теперь равна n`= n+5 бит. Операнды большей длины нуждаются в дополнительных полных сумматорах.  Пусть E` - число избыточных полных сумматоров. Рассматривая  суммы S` вместо S нетрудно заметить, что верхний уровень дерева не содержит избыточных полных сумматоров. Пусть H` -

 

 

 

 

 

 

 

сумма меток левых дочерних узлов в результирующем дереве. С кодированием Бута, успешные частичные произведения сдвинуты на 2 позиции. Т.о. имеем

 

2_5

 

Так как H` ограничено 2_5, имеем

 

2_5

 

Т.о., задержка и цена для умножителя из 4/2 деревьев с кодированием по Буту-2 будет равна

 

2_5

 

Пусть C` и D` обозначают цену и задержку для умножителя Бута, но не включающего в себя (n+m)-битный CLA сумматор, и пусть C и D обозначают соответственно задержку и цену для умножителя, не включающего в себя кодирование Бута. Тогда

 

2_5

 

Для n=m=58, имеем

 

2_5

 

И для n=m=27, имеем

 

2_5

 

 

Асимптотически, С`/C стремится к 12/16=0.75. До тех пор, пока m не является степенью двойки, имеем м=м`+1 и D-D`=7. Отсюда следует, что D`/D стремится к единице с ростом n. 1ё

Наверх страницы

Внимание! Не забудьте ознакомиться с остальными документами данного пользователя!

Соседние файлы в текущем каталоге:

На сайте уже 21970 файлов общим размером 9.9 ГБ.

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

Не нашли нужный документ? Воспользуйтесь поиском по содержимому всех файлов сайта:



Каждый день, проснувшись по утру, заходи на obmendoc.ru

Товарищ, не ленись - делись файлами и новому учись!

Яндекс.Метрика