К. Хамахер, З. Вранешич, С. Заки - Организация ЭВМ - 5-е издание (2003) (1114649), страница 100
Текст из файла (страница 100)
Чем больше слагаемых, тем значительнее зкономия времени. Например, для сложения 32-разрядных чисел по методу с сохранением переноса (рис. 6.19) требуется только восемь уровней СБА (до последней операции сложения). В общем случае, чтобы свести я слагаемых к двум векторам, при сложении которых получается конечная сумма, необходимо около 1,7 !ойдо — 1,7 уровней СЯА (см. упражнение 6.23). Для сложения двух конечных векторов можно использовать 64-рззрядный сумматор с параллельным переносом.
Общую задержку при умножении 32 х 32 составляют: одна вентильная задержка в начальной группе вентилей И, на выходах которых получается 32 слагаемых; шестнадцать вентильных задержек для восьми уровней СЯА; двенадцать вентильных задержек для самого длинного пути (до заз) через 64-разрядный сумматор. Итого — двадцать вентильных задержек. Сравните: обычный матричный умножитель 32 х 32 генерирует последний бит произведения за сто восемьдесят пять вентильных задержек. 6.5. Быстрое умножение 427 1 0 1 1 0 1 х 1 1 1 1 1 ! 0 1 1 0 1 1 1 0 1 1 0 1 ~Я о о о 0 0 ~11 1 1 1 0 0 с, 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 0 !О) 1 1 О О ! ! ! ~1 О О 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 1 ! 0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0 0 0 0 с 1 0 1 1 0 0 0 1 0 0 1 1 Произведение Рис.
В.1В. Пример выполнения умножения с использованием операции сложения с сохранением переноса (Лля примера на рис. 6.17] Обсуждая алгоритм сложения с сохранением переноса, мы опустили некоторые существенные моменты. Прежде всего отметим, что на случай отрицательных слагаемых логика СБА должна предусматривать расширение знака (как в алгоритме Буга). Расширение знака до полной длины произведения (удвоенной двины операнда) не обязательно. На каждом уровне СБА достаточно расширить знак на несколько разрядов. Еще один момент. Мы предполагаем, что для сложения двух последних векторов 5 и С в выражении и х и нужен 2и-разрядный сумматор с параллельным переносом.
В процессе выполнения этой операции на самом деле складывается несколько меньшее количество разрядов, поскольку часть 428 Глава 6. Арифметика младших разрядов произведения к отому времени уже определена. Но это не играет решающей роли, и в целом произведенный анализ времени умножения остается правильным. Последнее: для выполнения операции умножения с использованием матрицы и х л необходимо и слагаемых.
Однако после перекодировки пар разрядов количество слагаемых уменьшается до п/2. В результате и число уровней СЯА сокращается с 1,7 1одэп — 1,7 до 1,7 1ойэтэ — 3,4. т Е П С В А Уровень 1 СБА С, Бэ С, Я! ! Уровень 2 СБА С Сэ $. Уровень 3 СБА с„ 34 Последнее сложение Произведение Рис. 6.19. Схематическое представление операций сложения(рис.
6.18) с сохранением переноса Ускоренное умножение:нтогн Вы многое узнали о технологии высокоскоростного умножения. Давайте подведем итоги. Перекодировка пар разрядов (результат развития идеи, заложенной в алгоритм Бута) позволяет вдвое сократить количество слагаемых. Количество этих слагаемых вы можете уменьшить до двух путем выполнения относительно небольшого количества операций сложения с сохранением переноса.
Результирующее произведение получается путем сложения этих двух слагаемых в сумматоре с параллельным переносом. Все три технологии — перекодировка пар разрядов множителя, сложение с сохранением переноса и сложение с параллельным переносом — повсеместно применяются конструкторами высокопроизводительных процессоров для сокращения времени выполнения умножения. 6.6. Целочисленное деление В разделе 6.4, изучая процедуру умножения положительных чисел, мы сравнивали процесс умножения вручную с процессом умножения с помощью логических схем.
Такой же подход будет избран и при описании операций целочисленного деления. Сначала мы обстоятельно рассмотрим деление положительных чисел, а затем поговорим об особенностях деления чисел со знаком. На рис. 6.20 приведены примеры деления одних и тех же чисел в десятичной и двоичной системах счисления. Начнем с десятичных чисел. Цифру 2 в частном получаем следующим образом. Сначала предпринимается попытка разделить 2 на 13 — не делится. Тогда мы делим 27 на 13. Результат — 2 (13 х 2 - 26) и 1 в остатке. К единице дописываем 4 из делимого и продолжаем процесс — делим 14 ва 6.6. Целочисленное деление 429 13, вследствие чего получаем 1 (переносим в частное) и 1 в остатке. Двоичное ум- ножение выполняется аналогичным образом, но является более простым, по- скольку в частном могут быть только единицы и нули.
10101 1101 Рис. 6.20. Примеры операции деления Алгоритм деления десятичных чисел реализуется следующим образом. Делитель располагается под старшими разрядами делимого, после чего выполняется вычитание. Если остаток положителен или равен нулю, в частное записывается 1, а остаток дополняется следующим разрядом делимого. Делитель перемещается в новую позицию, и вычитание повторяется.
Если же остаток отрицательный, в частное записывается О, делимое восстанавливается, для чего к нему прибавляется делитель, который смещается для проведения следующего вычитания. Рис. 6.21. Схема для двоичного деления 21 13 Г274 26 14 13 1 1101 10000 1101 1110 1101 1 430 Глава 6. Арифметика Деление с восстановлением На рис. 6.21 представлена схема, по которой реализуется деление с воссгаановлением (гезсог1пй Йпчз1оп). Обратите внимание на то, как она похожа на схему умно- жителя, приведенную на рис. 6.7. В начале операции н-разрядный положительный делитель загружается в регистр М, а п-разрядное положительное делимое— в регистр Я, Регистр А устанавливается в О.
По завершении операции деления и-разрядное частное находится в регистре Я, а остаток — в регистре А. Вычитание производится в соответствии с арифметикой дополнения до двух. В процессе вычитания лишние разряды с левого края регистров А и М заполняются значением знакового разряда. Алгоритм деления с восстановлением включает следующие шаги, которые повторяются л раз. 1.
Сдвиг А и Ц влево на одну двоичную позицию. 2. Вычитание М из А и помещение результата в А. 3. Если знак А равен 1, установка до в О и добавление М к А (то есть восстановление А); иначе до устанавливается в 1. На рис. 6.22 приведен пример деления с 4-разрядным делимым, реализуемый схемой, которая представлена на рис. 6.21. Деление без восстановления Алгоритм деления с восстановлением можно усовершенствовать таким образом, чтобы в случае неудачного вычитания не приходилось восстанавливать значение А. Вычитание считается неудачным, если его результат отрицателен.
Рассмотрим последовательность действий, совершаемых после операции вычитания в приведенном выше алгоритме. Если А положительно, мы сдвигаем его влево и вычитаем из него М, то есть выполняем операцию 2А — М. Если А отрицательно, мы восстанавливаем его с помощью операции А + М и сдвигаем влево, после чего вычитаем из него М, что равнозначно 2А + М. Впоследствии бит дв устанавливается в О или 1. На втой основе можно разработать следующий алгоритм деления без восстановления.
Шаг 1: Перечисленные ниже действия выполняются н раз. 1. Если знак А равен О, сдвинуть А и (1 на один разряд влево, а затем вы- честь М из А; иначе сдвинуть А и 9 влево и прибавить М к А. 2. Если знак А равен О, установить до в 1; иначе установить др в О. Шаг 2: Если знак А равен 1, прибавить М к А.
Шаг 2 необходим для того, чтобы по завершении н циклов шага 1 в А остался положительный остаток. Логическая схема, приведенная на рис. 6.21, подходит и для описываемого алгоритма. Обратите внимание на то, что выполнять операции восстановления больше не нужно и что на каждом шаге цикла производится одна операция сложения или вычитания. На рис.
6.23 показано, как выполнить пример, приведенный на рис. 6.22, с помощью алгоритма деления без восстановления. б.б. Целочисленное деление 431 Первоначально Сдвиг Вычитание Первый цикл Установка дв Восстановление 0 О О П Сдвиг Вычитание 0 0 О 1 0 1 1 1 0 1 Второй цикл Установка оа Восстановление 0 ДЯ(01Д Сдвиг Вычитание 0 0 1 О 0 1 1 1 0 1 Третий цикл Установка дз Сдвиг Вычитание 0 Установка ое Восстановление Четвертый цикл Остаток Частное Рис. В.22. Пример деления с восстановлением К сожалению, простого алгоритма для непосредственного деления операндов со знаком, подобного алгоритмам умножения, не существует.
Поэтому перед делением операнды со знаком должны быть преобразованы в положительные числа. После применения одного из описанных алгоритмов деления результат преобразуется в соответствующее значение со знаком. Разумеется, при этом учитываются знаки делимого и делителя. 10 !! Г!000 11 10 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 1 1 0 0 0 0 0 О~Д 432 Глава б. Арифметика Первый цикл Сдвиг Вычитание Установка ов 0 0 ДЯДЯ Второй цикл 1 1 1 0 0 0 0 0 1 1 0 ДЯДЯДЯ Третий цикл 1 1 1 1 0 0 0 0 1 1 ДЯДЯ!.!! ДО Четвертый цикл Сдвиг 0 0 0 1 0 Вычитание 1 1 1 0 1 Установка <ув Частное Восстановление остатка Сложение 1 1 1 1 1 0 0 0 1 1 0 0 0 1 0 Остаток Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
