К. Хамахер, З. Вранешич, С. Заки - Организация ЭВМ - 5-е издание (2003) (1114649), страница 99
Текст из файла (страница 99)
Преобразование 011... 110 =з ч- 100... — 10 называется переходам через единицы, В атом термине отражен принцип действия алгоритма Буга, когда единицы множителя составляют несколько непрерывных блоков. Как видите, для формирования произведения нужно сложить всего несколько сдвинутых копий множимого, что значительно ускоряет процесс. В худшем случае, когда единицы в нули множителя чередуются, сложение приходится выполнять для каждого разряда множимого. В результате слагаемых получается даже болыпе, чем если бы не применялся алгоритм Буга.
На рис. 6.13 показаны три варианта расположения нулей и единиц в множителе: худший, обычный и лучший. 422 Глава 6. АриФметика У алгоритма Бута есть две хорошие стороны. Он одинаково обрабатывает положительные и отрицательные числа, а если множитель содержит несколько больших блоков единиц, значительно ускоряется операция умножения.
Ускорение за счет перехода через единицы зависит от значений данных. В среднем алгоритм Бута работает с той же скоростью, что и обычный алгоритм умножения. 6.5. Быстрое умножение Настоящий раздел посвящен способам ускорения операции умножения. При использовании первого способа гарантируется, что максимальное количество слагаемых (версий множимого) для п-разрядных операндов не превысит п/2.
Применение второго способа приводит к сокращению времени, затрачиваемого на операции сложения. 6.5.1. Перекодировка пар разрядов множителя Благодаря технологии, называемой перекодировкой пар разрядов, вдвое уменьшается количество слагаемых, используемых для получения произведения. Ее можно назвать продолжением развития алгоритма Бута. Сначала множитель преобразовывается в соответствии с алгоритмом Буга, после чего его разряды разбиваются на пары. Каждая пара (+1 — 1) эквивалентна паре (О +1). Таким образом, вместо того чтобы прибавлять произведение (-1 н М), сдвинутое на 1 разрядов, к произведению (+1 н М), сдвинутому на (т + 1) разрядов, можно получить тот же результат, поместив в разряд т значение (+1 н М).
Возможны и другие замены пар разрядов множителя. Например, пара (+1 О) эквивалентна паре (О +2), пара ( — 1 +1) эквивалентна паре (О -1) и т. д. Анализ разрядов множителя, преобразованного согласно алгоритму Бута, начиная справа, показывает, что их можно переписать таким образом, чтобы для каждой пары разрядов выполнялось не более одного сложения. На рис.
6.14, а приведен пример перекодировки пар разрядов множителя, который мы встречали на рис. 6.11, а на рис. 6.14, б воспроизведена таблица выбора версии множимого для каждого из возможных сочетаний разрядов множителя. На рис. 6.16 показано, как выполнить пример умножения, описанный на рис. 6.11, осуществляя перекодировку пар разрядов множителя. Расширение знака Подразумеваемый О справа от 1.ЯВ ~Я 1 1 О 1 О ДЯ О вЂ” 1 — 2 Рис. 6.14. Перекодировка пар разрядов множителя: после преобразования по алгоритму Буга [в); таблица выбора версий множимаго (б) 424 Глава 6. Арифметика 6.5.2. Сложение с сохранением переноса Умножение всегда выполняется путем сложения некоторого количества слагаемых. Этот процесс можно ускорить за счет сложения с сохранением переноса (Саггу Баче А66111оп, СЯА). Рассмотрим матрицу умножения двух 4-разрядных чисел (рис.
6.16, а). Эта матрица знакома нам по рис. 6.6. В ее первой строке содержатся вентили И, с помощью которых генерируются битовые произведения тздр, тя)е шИэ и тоЧо Вместо того чтобы последовательно распространять переносы вдоль строк матрицы сумматоров, можно «сохранять» их и переносить в соответствующие позиции следующей строки, как показано на рис, 6.16, 6.
В результате у ряда полных сумматоров матрицы освобождается по одному входу. В частности, в первой строке освобождаются входы трех крайних слева сумматоров. Эти входы исполь- зУютсЯ длЯ битовых пРоизведений тРетьего слагаемого: язв т1пз и те~Уз На два входа сумматоров во второй строке подаются выходные суммы и переносы из первой строки. Третий вход предназначается для битовых произведений гля)ь ш~(73 и та~уз четвертого слагаемого. Старшие битовые произведения та 71 и взчз третьего и четвертого слагаемых подаются на оставшиеся свободные входы с левого края второй и тре|ъей строк матрицы.
Сохраненные биты переноса и разряды суммы из второй строки добавляются в третью строку, вследствие чего образуется полный набор разрядов произведения. Полная задержка в матрице умножителя с сохранением переноса меньше, чеи в обычной матрице с распространением переноса. Ускорение достигается за счет того, что выходные векторы каждой строки 5 и С формируются параллельно на протяжении одной задержки в полном сумматоре. В упражнении 6.22 вам представится случай самим оценить выигрыш во времени.
Описываемый ниже метод позволяет еще больше сократить задержку. Рассмотрим операцию суммирования большого количества слагаемых, выполняемую при умножении длинных операндов. Можно разбить слагаемые на тройки и для каждой из них произвести сложение с сохранением переноса, вследствие чего на протяжении одной задержки в полном сумматоре будет сформирован набор векторов 5 и С. Далее эти векторы снова объединятся в тройки, для которых тоже будет произведено сложение с сохранением переноса. Этот процесс продолжается до тех пор, пока не останется два вектора. Их сложение посредством сумматора с последовательным или параллельным переносом и дает результирующее произведение.
Обратимся к примеру. Предположим, требуется осуществить сложение шести сдвигаемых значений множимого при умножении двух 6-разрядных беззнаковых чисел. Все шесть разрядов множителя содержат единицы (рис. 6.17). Шесть слагаемых, А, В ., Г, складываются множителем с сохранением переноса, как показано на рис. 6.18. Прямоугольники на этих двух рисунках выделяют соответствующие биты операндов, суммы и переноса. На рис.
6.19 схематически представлен трехуровневый процесс суммирования с сохранением переноса. Очевидно, что два последних вектора, 5» и Се формируются за три задержки в полном сумматоре после подачи шести входных слагаемых на уровне 1. Последняя операция сложения векторов 54 и С4, в результате выполнения которой получаем конечное произведение, может быть произведена сумматором с последовательным или параллельным переносом. 6.5. Быстрое умножение 425 1И44)О ШО4(а Мзз)а Рг РБ Р5 рг Рз р! Ра о Мза)а Шгз)а М44)а Маа)а Р! РБ Р5 Рз Рз Рг Р! ра Рис. 6.16. Матрицы для операции умножения 4-разрядных операндов М х 0 = Р: с последовательным распространением переноса (а); с сохранением переноса (б) 426 Глава 6.
Арифметика О ! ! О ! (45) М х 1 1 1 1 1 1 (63) Я О ! 1 О 1 А 1 1 О 1 1 О 1 1 О О 1 1 О 1 1 О 1 1 1 О 1 1 О 1 О 1 1 О О О 1 О О 1 1 (2,835) Произведение Рис. 6.17. Пример умножения с использованием операции сложения с сохранением переноса(для примера на рис. 8.18) Давайте вычислим общее время, необходимое для умножения двух 6-разрядных чисел (рис. 6.18 и 6.19). После одной задержки в вентиле И, используемом для выбора слагаемых на основе значений разрядов множителя, все шесть слагаемых подаются на входы первого уровня СЯА (сложения с сохранением переноса).
Выходные векторы 5а и Са третьего уровня СБА будут вычислены спустя шесть вентильных задержек (при двух вентильных задержках на каждом уровне СЯА). Последние два вектора слагаются за восемь вентильных задержек, если применяется сумматор с параллельным переносом, как на рис. 6.5. Итого — пятнадцать вентильных задержек. Общее время, необходимое для умножения с использованием матрицы и х и, подобной изображенной на рис. 6.6, равно 6 (п — 1) — 1, Таким образом, если применяется матрица 6 х 6, умножение выполняется за двадцать девять вентильных задержек. Как видите, в результате использования алгоритма сложения с сохранением переноса и сложения последних двух векторов с параллельным переносом продолжительность операции умножения сокращается вдвое.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
