ОсобенностиАРИФМЕТИКО-ЛОГИЧЕСКИХУСТРОЙСТВ (АЛУ) с двоично-десятичнымикодами (ДДК) при вычислении операций умножения и деления и поиск путей ихускорения
Двоичные коды достаточногромоздкие и поэтому в качестве входной и выходной информации часто используютДДК. ДДК получают при преобразовании десятичного числа в двоичное путем заменыкаждой десятичной цифры числа ее двоичным эквивалентом, выделяя при этом подкаждую десятичную цифру 4 двоичных разряда. Очевидно, что такие преобразованияне соответствуют переводу числа из десятичного формата в двоичный. Однако такойспособ является весьма простым. Поэтому, при использовании ДДК чисел необходимовыполнять необходимые корректирующие действия, которые приводят полученноезначение к истинному результату.
Пример:
37=/>
АЛУ, построенное дляобработки ДДК базируется на традиционном двоичном сумматоре с выполнениемдополнительных корректирующих действий. Основная идея корректирующих механизмовзаключается в том, что при обработке десятичных разрядов переносы в смежныеразряды возникают при значениях, превышающих число 10, а при сложении ДДКперенос в смежный разряд возникает при превышении в разряде 16. Единицей данныхпри обработке ДДК является т. наз. тетрада, представляющая собой 4последовательных бита. Для компенсации искажений, возникающих при сложении ДДК,формируют операнд, каждая цифра которого имеет избыток, равный 6. В такомслучае:
z[i]=x[i]+y[i]+P[i]
Если при обработке i-тогоразряда десятичного кода при сложении i-того разряда первого операнда, i-тогоразряда второго операнда и входного переноса в i-тый разряд, значение превышает10, то в i-том разряде остается
z[i]=x[i]+y[i]+P[i]-10
P[i+1]=1
Формируется сигналпереноса в следующий разряд. Поэтому при сложении операндов с избытком в (х6)получаем:
zt=x6+Y
В таком случае в i-томразряде ztбудет такое значение:
/>
тогда zt$16. В таком случае в i-том разряде zr будет:
zr[i]=6+x[i]+y[i]+P[i]-16=x[i]+y[i]+P[i]-10=z[i]
P[i+1]=1 –перенос вследующий разряд
При получении псевдосуммыzt обнаруживается ситуация, когдаразряды (тетрады), из которых был перенос в старший разряд, содержат правильноезначение цифры этого разряда. Разряды, из которых не было переносов в старшийразряд, содержат цифру с избытком, равным 6. Поэтому полученное значениетребует корректировки. Она может быть проведена путем вычитания из разрядов, изкоторых не было переносов, значения 6. На практике, вместо вычитания к этимразрядам добавляют значение равное 10 и блокируют межтетрадные переносы:
/>
Упрощенная схема АЛУ
/>
Алгоритм сложения ДДК
РгВ принимает первыйоперанд, затем в РгА формируют числосо значением 6 в каждой тетраде.
В РгСм формируется код первогооперанда с избытком 6, который принимается в РгВ.
В РгА принимается второйоперанд. Сумматор формирует значение zr=x6+y. При этом тетрады, из которыхне возникли сигналы переноса, фиксируются.
В ргА формируетсяоперанд, в тетрадах которого размещено число 10, если в соответствующихтетрадах zr невозникал сигнал переноса. zr из РгСм передается в РгВ.
Корректировка zr путем добавления операнда с 10 в РгАс блокировкой межтетрадных переносов. Полученный результат передается навыходную шину данных.
Для вычитания ДДКпроизводятся такие действия:
Второй операнд Yпреобразуют в обратный код инвертированием каждого бита, при этом получаетсяобратный код с избытком 6, т.к. каждая тетрада является дополнением до 15.
Выполняется суммирование />. Если изстаршей тетрады zr при формировании был перенос, то получено положительноезначение результата. Если переноса не было из старшей тетрады, то результатявляется отрицательным в дополнительном коде. При этом дополнительный кодинвертируется и добавляется 1 к младшему разряду. Полученное значение требуеткорректировки. Если при получении zr из тетрады был перенос, то впоследствии к этой тетраде надо добавить 10 с блокировкой межтетрадныхпереносов.
Опции с ДДК со знакамисводятся к определению реальных опций, которые затем выполняются по приведеннымсхемам.
Умножение ДДК. Анализируется значение очереднойтетрады, начиная с младшей и к сумме частичных произведений добавляетсямножимиое столько раз, какому значению равно число в тетраде. Значение суммычастичных произведений сдвигается вправо на тетраду, чтобы уменьшить количествосложений. Отдельно формируется 8, 4 и 2 кратное множимое (8х, 4х, 2х, 1х).Данная процедура повторяется, пока все тетрады множителя не будут проанализированы.
Деление ДДК. Производится путем многократноговычитания делителя из текущего значения частичных разностей, которыепервоначально равны значению делимого, последовательным сдвигом частичныхразностей влево по разрядной сетке. Многократное вычитание выполняет дополучения отрицательного результата. Количество вычитаний до полученияотрицательного результата соответствует очередной цифре частного. В целом,опция похожа на традиционное деление «уголком».
Методы ускоренияоперации умножения.Аппаратурные методы ускорения требуют дополнительных затрат, пропорциональныхколичеству обратных разрядов. Как пример к аппартным методам операции (*) –включение дополнительных цепей сдвига возможно за 1 такт алгоритмасинхронизировать выполнение сдвига на нескольких разрядах.Другим методомявляется работы сумматоров, а также совмещение во времени сдвиговых операций иопераций суммирования
Логические методыускорения операции умножения требуют изменения центрального управления.Основным источником повышения эффективности является уменьшение кол-ва сложенийвыполняемых в процессе получения />S частных произведений. К логическим так же можноотнести методы позволяющие анализировать несколько разрядов множителейодновременно и выполнить соответствующие изменения суммы частных произведений.
Пример лог. метода
/>
0151413121100=26 –21;
k+1 k k-1 0
| | | |
0 1 1 1 0 1 1 1 …….
Вместо 2-Х вычитанийвыполняется одно.Если … 0 1к 0 в (к) выполняется только одно сложение
Формализация этогоподхода может быть сделана так :
di=(bi + bi-1)*di-1
Si = di *bi+1
bi –логическая переменнаяопределяющая необходимость выполнения арифметической операции для i-тогоразряда множителя
Si –определяет знаквыполнимой операции. Если Si =0, то выполняется сложение текущей суммычастного произведения и множимого. Если Si =1 то выполняется “-“ вычитаниемножимого из суммы частн. Произведений
Данное правило – правилоЛемана. Оно при самых неблагоприятных комбинациях разрядов множителей вдвоесокращает кол-во операций суммирования. Среднее значение ускорения *3.
На практике получилиприменение другие способы операции умножения с анализом нескольких разрядовмножителя .
При анализе 2-х разрядовмножителя можно предложить след последовательность действий :
Если два разряда 00. товыполняется только сдвиг Sчастного произведения (далее S ч.п.)вправо на 2 разряда
Если 01 то к S ч.п. добавляется множимое, а далеевыполняется сдвиг на два разряда
Если 10 то к S ч.п добовляется удвоеное множимое и S ч.п сдвигается вправо на дваразряда, если 11 то вычитаем множимое и на специальном триггере запоминаетсяситуация о необходимости коррекции при анализ след 2-х разрядов. Далее S ч.п сдвигается вправо на два разряда, след пара разряда множителя уже рассматривается как увел на 1.Значение разрядов Операция при знаке предыдущего разрядов =1000 0000 П(4)z П(4)(z+x) 0001 П(4)(z+x) П(4)(z+2x) 0010 П(4)(z+2x) П(4)(z+3x) 0011 П(4)(z+3x) П(4)(z+2x+2x) 0100 П(4)(z+2x+2x) П(4)(z+2x+3x) 0101 П(4)(z+2x+3x) П(4)(z+6x) 0110 П(4)(z+6x) П(4)(z+x+6x) 0111 П(4)(z+x+6x) П(4)(z+2x+6x) 1000 П(4)(z+2x+6x) П(4)(z-x-6x) 1001 П(4)(z-x-6x) П(4)(z-6x) 1010 П(4)(z-6x) П(4)(z-2x-3x) 1011 П(4)(z-2x-3x) П(4)(z-2x-2x) 1100 П(4)(z-2x-2x) П(4)(z-x-2x) 1101 П(4)(z-x-2x) П(4)(z-2x) 1110 П(4)(z-2x) П(4)(z-x) 1111 П(4)(z-x) П(4)z
Указанные значениясоответствуют кратным множимого, которые создаются и хранятся отдельно.Очевидно, можно получить похожую схему при анализе большего количестваразрядов. На практике используются также табличное умножение, которое с помощьюсоответствующих элементов памяти позволяет для определённых комбинаций двоичныхразрядов сразу получить соответствующее значение, которое прибавляют к текущемузначению суммы частичных произведений перед сдвигом её вправо на требуемоезначение разрядов.
Табличное умножениезначительно ускоряют операцию, используемую во всех моделях процессора Pentium.Целочисленное умножение является составной частью умножения чисел с плавающейточкой, поэтому эффективность данной операции существенно влияет наэффективность операции с плавающей точкой. Дополнительно для ускорениявыполнения операции умножения используется конвейерная форма организации, прикоторой сочетаются во времени различные фазы или элементы операции, выполняемыенад разными последовательностями операндов. Именно наличие последовательностейпозволяет поднять общую производительность операции.
АЛУ для реализацииоперации деления.Операция/ является обратной по отн к операции *, поэтому общая структура операциизаключается в последовательности вычитания значения делителя из делимого исдвигах.
Результат в виде текущегозначения частичных разностей. Цифры частного определяются как при положительномзначении частичных разностей и как нуль в противном случае.
Рассм. осн. требования:Частное Z как рез-т деления делимого X на делитель Y, Z=X/Y. Х представляется вформате двойного слова, т.е. занимает (2n-1) разрядов, Z и Y представлены вформате одинарного слова, т.е. занимают (n-1)разрядов. Поэтому |Z|
/>
Данная схема предполагаетиспользование двойной разрядности всех элементов. При этом делимое и послед.значение частичных разностей неподвижны, а сдвигаются вправо компонентыделителя. Начальное положение делителя старшие разряды регистра РгУ, а затемделитель à изрезультате каждой итерации. Частичные разности получаются с помощью сумматора,на один вход которого подается делимое, а на другой-обратный код делителя. Доп.код получается подсуммированием 1 к младшему разряду сумматора. Цифры частногоформируют по знаку полученных частичных разностей, т.е. по нулевому разряду сумматора.Цифры заносятся в младший разряд регистра РгZ, которые передаются со сдвигомвлево в регистр Z’, а далее прямо в регистр Z. Основным недостатком этой схемыявляется использование двойной разрядности всех компонентов. На практикеполучила распространение схема с неподвижным делителем и сдвигаемым влевозначением частичных разностей.(СХЕМА).
/>
В Рг1 размещаетсяделитель, а в РгВ и Рг2-делимое. В триггерах знака сохраняются знаки операндов.Регистр 3 используется для размещения цифр частного. Общая схема алгоритма:
1.Берутся модули отоперандов, которые размещаются в регистрах.
2.Делимое ß на 1 разряд, для этого регистр Аобнуляется и содержимое передается в регистр сумматора со сдвигом ß на один разряд.В освободившийсямладший разряд сумматора записывается младший разряд из регистра 2. После этогосодержимое регистра сумматора записывается в регистр В. одновременно разрядырегистра 2, кроме старшего, передаются в Рг2’ со сдвигом ß на 1 разряд и затем в регистр 2.
3.выполняется получениезначения частичных разностей путем сложения содержимого регистра В и обратногокода делителя из регистра А. Выполняется добавление 1 к младшему разрядусумматора для получения дополнительного кода делителя.
4.Если 0-й разрядрегистра сумматора>0, то цифра Zi, заносимая в младший разряд регистра 3’=1.Содержимое регистра 3’ передается в регистр 3. При очередном получениичастичных (текущих?)разностей содержимое регистра 3 передается в 3’ со сдвигом ß на 1 разряд.
Счетчик циклов содержитколичество цифровых разрядов частного. После получения очередной цифры частногозначение счетчика уменьшается на 1. При достижении 0 операция заканчивается.Если в процессе получения частичных разностей текущее значение в регистресумматора
В регистре В производитсясдвиг ß оставшейся части делимого дляпоследующих операций.
Рассмотренный алгоритмпредполагает при получении значения
1.Берутся модули отделимого и делителя.
2.Значение частичногоостатка полагается равным старшим разрядам делимого
3.Значение частичногоостатка удваивается путем сдвига ß на 1 разряд.
4.Из значения частичныхостатков вычитается делитель; если частичный остаток >0!!! то прибавляетсяделитель если
5.Цифра частногополагается =1, если после выполнения предыдущего шага частичные остатки >=0и 0 в противном случае.
6.Пункты 3,4,5выполняются до получения всех цифр частного.
7.Если в конце циклачастичный остаток
Знак частного =0, еслизнаки делимого и делителя совпадают, и 1 если они различны.
Содержание деления безвосстановления остатков заключается в том, что при сдвиге ß значение частичного остатка аудваивается 2а, поэтому вычитание делителя эквивалентно 2а-в=2(а-в)+в егодобавлению на следующем шаге.
Данный алгоритм можетприменяться и для деления целых операндов, представленных прямым кодом для положительныхчисел и дополнительным кодом для отрицательных. При этом необходимо производитьопределение цифр частного в зависимости от соотношений знаков частичныхостатков и делителя в соответствии со следующей таблицей:Частичные остатки Делитель Операция Цифра частного + + Вычитание Y 1 + - Добавление Y - + Добавление Y - - Вычитание Y 1
Если x>0,a y
Если x0 точастное следует увеличить на 1 в случае если остаток =0
Если x
Построение АЛУ длявыполнения операции умножения чисел с плавающей точкой
Правила умножения:
X=±qx*SPx
Y=±qy*SPy
Z=X*Y= ± qx* qy* SPx+Py = ± qz *SPz
T.o. qz= qx* qy; Pz= Px+Py ;
В соответствии с даннымивыражениями мантисса произведения равна произведению мантисс сомножителей.
Результат нормализуется.Знаку результата соответствует:
+ если мантиссысомножителей имеют одинаковые знаки;
— если мантиссысомножителей имеют разные знаки.
Учитывая то, что порядкисомножителей имеют смещение, то при прямом копировании приведенных действийпорядок результата должен быть уменьшен на 1 смещения. Поэтому, если присложении смещённых порядков старшие разряды суммы имеют нулевые значения, тоэто означает, что мы не можем извлечь смещение, т.к. значение 00 меньше чемизвлекаемое смещение. Поэтому в качестве результата операции принимается 0 т.к.мантисса не может быть размещена в разрядной сетке при таком значении порядка.
Р[0]=0; P[1]=0 в качестверезультата операции принимается 0
Р[0]=0; P[1]=1
Тогда производитсякоррекция, путём инвертирования этого разряда, т.о. получаем требуемыйсмещённый порядок.
Р[0]=1; P[1]=0
Мы получили отрицательноезначение суммы смещённых порядков и смещённый порядок суммы получается путёминвертирования.
Р[0]=1; P[1]=1
Мы получили отрицательноезначение суммы смещённых порядков, разрядная сетка переполняется, но переполнениеможет исчезнуть при выполнении нормализации мантисс. Эта ситуация отражается вспециальном триггере, который характеризует ситуацию возможного переполненияпорядков.
Общая схема АЛУ дляоперации умножения
/>
В Рг1 размещаетсямножимое, в Рг2-множитель. В начале для сложения смещённых порядков в РгА и РгВпередаются только биты смещённых порядков. Биты мантисс в РгА и РгВ обнуляются.Соответственно обнуляются и регистры знаков. Сами знаки пишутся в ТрЗн. Послеразмещения порядков в РгА и РгВ сумматор формирует код суммы смещённыхпорядков. Он размещается в соответствующем поле РгСм.
Производится анализ двухстарших разрядов в этом поле в соответствии с приведенными выше рассуждениями.В результате формируется смещённый порядок произведения с необходимымикорректировками кода, который помещается в Сч1.
После этого идётпроизведение мантисс. Для этого:
В РгА идёт код мантиссыХ(8-31 разр.). РгВ используется для хранения текущего значения суммы частичныхпроизведений. Идёт анализ младших разрядов мантиссы Y в Рг2 и добавление или недобавление к текущему значению суммы частичных произведений мантиссы Х.
Результат в виде суммычастичных произведений передаётся в РгСм со сдвигом вправо и последующейпередачей в РгВ.
Процесс идёт до получениятребуемого количества разрядов произведения мантисс.
Отличие данного умножениямантисс от умножения мантисс целых чисел в том, что мантисса произведения имееттот же размер, что и мантиссы сомножителей. После окончания умножения мантиссрезультат нормализуется (возможно изменяется значение Сч1). Результат Сч1 идётв поле для смещённого порядка.
/>