19335

УСКОРЕНИЕ ЦЕЛОЧИСЛЕННОГО ДЕЛЕНИЯ. АУ ДЛЯ ЧИСЕЛ С ПЛАВАЮЩЕЙ ЗАПЯТОЙ

Лекция

Информатика, кибернетика и программирование

АК ЛЕКЦИЯ № 12 УСКОРЕНИЕ ЦЕЛОЧИСЛЕННОГО ДЕЛЕНИЯ. АУ ДЛЯ ЧИСЕЛ С ПЛАВАЮЩЕЙ ЗАПЯТОЙ Ускорение целочисленного деления Следует отметить что операция деления предоставляет не слишком много путей для своей оптимизации по времени. Тем не менее определенные возможности ...

Русский

2013-07-11

82.5 KB

21 чел.

АК ЛЕКЦИЯ № 12 УСКОРЕНИЕ ЦЕЛОЧИСЛЕННОГО ДЕЛЕНИЯ. АУ ДЛЯ ЧИСЕЛ С ПЛАВАЮЩЕЙ ЗАПЯТОЙ

Ускорение целочисленного деления

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

- замена делителя обратной величиной, с последующим ее умножением на делимое;

- сокращение времени вычисления частичных остатков в традиционных методах деления (с восстановлением или без восстановления остатка) за счет ускорения операций суммирования (вычитания);

- сокращение времени вычисления за счет уменьшения количества операций суммирования (вычитания) при расчете Ч0;

- вычисление частного в избыточной системе счисления.

За исключением первого из перечисленных подходов все прочие фактически являются модификациями традиционного способа деления.

Замена деления умножением на обратную величину

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

.

В этом случае проблема сводится к эффективному вычислению 1/D. Обычно задача решается одним из двух методов: с помощью ряда Тейлора или метода Ньютона-Рафсона. В обоих случаях основное время расходуется на умножение, поэтому рассматриваемый метод ускорения деления имеет смысл при наличии быстрых схем умножения.

При реализации первого метода делитель D представляется в виде: D - 1 + X. Тогда для двоичного представления D можно записать:

Метод был использован в модели 91 вычислительной машины IBM 360 для вычисления 32-разрядной величины 1/D. Возможные значения сомножителей в правой части выражения извлекались из таблицы емкостью 28 байт, хранящейся в памяти. Операция вычисления 1/D требует шести умножений.

Вычисление величины 1/D методом Ньютона-Рафсона сводится к нахождению корня уравнения

то есть Х- 1/D. Решение может быть получено с привлечением рекуррентного соотношения: Xi+1 = Xi(2 – Xi*D). Количество итераций определяется требуемой точностью вычисления 1/D. Реализация метода для n-разрядных чисел требует 2 int(log2n) - 1 операций умножения.

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

Ускорение вычисления частичных остатков

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

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

Алгоритм SRT

В основе третьей группы методов ускорения операции деления, согласно приведенной выше классификации, лежит так называемый алгоритм SRT.

Свое название алгоритм получил по фамилиям авторов (Sweeney, Robertson, Tocher), разработавших его независимо друг от друга приблизительно в одно и то же время. Этот алгоритм представляет собой модификацию деления без восстановления остатка. В стандартной процедуре на каждом шаге помимо сдвига частичного остатка производится прибавление либо вычитание делителя. В SRT-алгоритме сдвиг Ч0 также имеется в каждой итерации, однако сложение или вычитание, в зависимости от получающегося Ч0, на отдельных шагах может не выполняться, что, естественно, позитивно влияет на быстродействие деления.

Алгоритм был ориентирован на операции над мантиссами чисел с плавающей запятой и опирается на то обстоятельство, что мантиссы в таких числах нормализованы. Впервые SRT-алгоритм был реализован в модели 91 вычислительной машины IBM 360. В настоящее время он широко применяется в блоках обработки чисел с плавающей запятой, в частности в микропроцессорах фирмы Intel.

Сначала рассмотрим алгоритм применительно к положительным целым числам. Делимое представляется (2n + 1)-разрядным числом, а делитель — n-разрядным. Процедура деления начинается с удаления в делителе всех нулей, предшествующих старшей единице, то есть с операции, аналогичной нормализации мантиссы в числах с плавающей запятой. По той же аналогии будем в дальнейшем условно называть эту операцию нормализацией. Исключение k предшествующих нулей реализуется за счет сдвига делителя влево на к разрядов. На аналогичное число разрядов влево сдвигается и делимое. Далее выполняются п итераций, в которых вычисляются цифры частного и частичные остатки. Действия, выполняемые на i-й итерации, можно описать следующим образом:

Обратим внимание на то, что частное представляется в системе счисления, отличной от двоичной. Это означает, что цифры частного могут иметь больше, чем два значения 0 и 1. В рассматриваемом случае—1,0,1.

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

Последний момент в алгоритме — преобразование частного из системы {-1,0,1} в систему {0,1}, то есть в обычную двоичную систему.

На практике это выливается в следующую процедуру (при объяснении будем ссылаться на схему деления без восстановления остатка, приведенную на рис. 7.50).

Делимое и делитель, представленные в дополнительном коде, размещаются в регистре делимого (РДМ) и делителя (РДТ) соответственно. Дальнейшие действия можно описать следующим образом.

1. Если в делителе D имеются k предшествующих нулей (при D > 0) или предшежимого РДМ и РДТ влево на k разрядов.

2. Для i от 0 до п - 1:

• если три старших цифры частичного остатка в РДМ совпадают, то qt = О и производится сдвиг содержимого РДМ на один разряд влево;

• если три старших цифры частичного остатка в РДМ не совпадают, а сам Ч0 отрицателен, то qi -1, делается сдвиг содержимого РДМ на один разряд влево и к Ч0 прибавляется делитель;

• если три старших цифры частичного остатка в РДМ не совпадают, а сам Ч0 положителен, то qt, - 1, выполняется сдвиг содержимого РДМ на разряд влево и из Ч0 вычитается делитель.

3. Если после завершения пункта 2 остаток отрицателен, то производится коррекция (к остатку прибавляется делитель, а из частного вычитается единица).

4. Остаток сдвигается вправо на k разрядов.

В стандартном алгоритме деления без восстановления остатка помимо сдвига в каждой итерации выполняется операция сложения или вычитания. В варианте SRT, в зависимости от кодов операндов в отдельных итерациях, достаточно только сдвига, что, безусловно, ускоряет процесс деления. Согласно статистическим данным, в среднем число сложений и вычитаний при использовании этого алгоритма сокращается в 2,67 раза.

Деление в избыточных системах счисления

Наиболее распространенные методы ускорения операции деления основаны на применении алгоритмов, где частное представляется в системе счисления, отличной от двоичной. Это означает, что цифры частного могут иметь больше, чем два значения, например {-1,0,1}, как это было в алгоритме умножения Бута, или {-2, -1,0,1,2}. В таких системах одно и то же число может быть записано несколькими способами, из-за чего системы называют избыточными. Очередная цифра частного в избыточной системе счисления, в зависимости от базы этой системы, соответствует двум или более цифрам в двоичном представлении частного, и для нужного количества двоичных цифр частного и остатка требуется меньше итераций. В то же время реализация такого подхода ведет к усложнению аппаратуры делителя, в частности надстраивается логика определения операции, выполняемой в очередной итерации. Для этой цели в состав устройства деления включается специальная память, хранящая таблицу, определяющую необходимые действия, в зависимости от текущей комбинации цифр в частичном остатке и делителе. Тем не менее выигрыш в быстродействии оказывается решающим моментом. Так, в микропроцессорах Pentium при делении мантисс чисел с плавающей запятой используется алгоритм SRT с базой 4, то есть частное сначала вычисляется с использованием цифр -2, - 1 , 0, 1, 2 с последующим преобразованием результата к стандартному двоичному представлению. В этом варианте выбор очередной цифры частного производится с помощью таблицы, состоящей из отдельных секций. Конкретную секцию определяют четыре старшие цифры делителя (после его нормализации). Входом в секцию служат шесть старших цифр частичного остатка. Ч0 в каждой итерации сдвигается не на один, а на два разряда, то есть число итераций сокращается вдвое. Известны варианты делителей, где берется еще большее основание системы счисления, в частности 8 и 16. В этом случае логика работы устройства существенно усложняется.

Операционные устройства с плавающей запятой ,

Операции над числами в формате с плавающей запятой (ПЗ) имеют существенные отличия от аналогичных операций целочисленной арифметики, поэтому их обычно реализуют с помощью самостоятельного операционного устройства. Как и целочисленное ОПУ, операционное устройство для чисел в формате ПЗ как минимум должно обеспечивать выполнение четырех арифметических действий: сложения, вычитания, умножения и деления.

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

Напомним основные положения записи чисел в стандарте IEEE 754. Мантиссы чисел М представляются в нормализованном виде, при этом действует прием скрытого разряда, когда старшая цифра мантиссы, всегда равная единице, в записи числа отсутствует, то есть в поле мантиссы старшей является вторая старшая цифра нормализованной мантиссы.

В отличие от общепринятого условия нормализации S - /М/ < 1, в стандарте IEEE 754 используется условие 1 - /М/ < 2.

Запись числа содержит смещённый порядок, то есть порядок, увеличенный на величину смещения, которое в стандарте IEEE 754 для одинарного формата равно 127, а для двойного — 1023.

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

где: XM, YM, ZM – нормализованные мантиссы операндов и результата; X , Y , Z  - смещённые порядки операндов и результата; О – знак арифметической операции.

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

Подготовительный этап

Первой особенностью операционных устройств для чисел с плавающей запятой является то, что в них операции над тремя составляющими чисел с ПЗ (знаками, мантиссами и порядками операндов) выполняются раздельно: блоком обработки знаков (БОЗ), блоком обработки порядков (БОП) и блоком обработки мантисс (БОМ). Для хранения операндов и результата в ОПУ предусмотрены соответствующие регистры. Хотя эти регистры могут быть физически реализованы в виде единых устройств, каждый из них логично рассматривать как совокупность трех регистров: знака, порядка и мантиссы. Таким образом, на этапе загрузки операндов в регистры ОПУ осуществляется «распаковка» чисел с ПЗ, их разбиение на три составляющие. В ходе такой распаковки в старшем разряде регистра мантиссы восстанавливается единица, которая в записи числа отсутствовала (была скрыта).

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

Заключительный этап

Действия на завершающем этапе выполнения любой арифметической операции идентичны и сводятся к выявлению нулевого значения мантиссы (потери значимости мантиссы), нормализации мантиссы, выявлению отрицательного переполнения порядка, "упаковке" составляющих результата.

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

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

В завершение мантисса результата округляется и, если это предусмотрено форматом ПЗ, из нее удаляется скрытый разряд.

В последней фазе осуществляется "упаковка" всех составляющих результата (знака, порядка и мантиссы), после чего сформированный результат заносится в выходной регистр ОПУ.

Сложение и вычитание

В арифметике с плавающей запятой сложение и вычитание — более сложные операции, чем умножение и деление. Обусловлено это необходимостью выравнивания порядков операндов. Алгоритм сложения и вычитания включает в себя следующие основные фазы:

1. Подготовительный этап.

2. Определение операнда, имеющего меньший порядок, и сдвиг его мантиссы вправо на число разрядов, равное разности порядков операндов.

3. Приравнивание порядка результата большему из порядков операндов.

4. Сложение или вычитание мантисс и определение знака результата.

5. Проверку на переполнение.

6. Заключительный этап.

Операции предшествует вышеописанный подготовительный этап, в ходе которого операнды «распаковываются» и помещаются в регистры ОПУ.

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

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

123 * 100 + 456 * 10-2.

Очевидно, что непосредственное сложение мантисс недопустимо, поскольку цифры мантисс, имеющие одинаковый вес, должны располагаться в эквивалентных позициях. Так, цифра 4 во втором числе должна суммироваться с цифрой 3 в первом. Этого можно добиться, если записать второе число так, чтобы порядки обоих чисел были равны:

123 * 100 + 456 * 10-2 = 123 * 100 + 4,56 * 100 = 127,56 * 100.

Выравнивания порядков можно достичь сдвигом мантиссы меньшего из чисел вправо, с одновременным увеличением порядка этого числа, либо сдвигом мантиссы большего из чисел влево и уменьшением его порядка. Оба варианта сопряжены с потерей цифр мантиссы, но выгоднее сдвигать меньшее из чисел, так как при этом теряются младшие разряды мантиссы. Таким образом, выравнивание порядков операндов реализуется путем сдвига мантиссы меньшего из чисел на один разряд вправо с одновременным увеличением порядка этого числа на единицу. Действия повторяются до совпадения порядков. Если в процессе сдвига мантисса обращается в 0, в качестве результата операции берется другой операнд.

Следующая фаза — сложение мантисс с учетом их знаков, что при одинаковых знаках мантисс может привести к переполнению. В последнем случае мантисса результата сдвигается вправо на один разряд, а порядок результата увеличивается на единицу. Это, в свою очередь, чревато переполнением поля порядка. Тогда операция прекращается и формируется признак переполнения, сопровождаемый соответствующим предупреждением (обычно в виде сигнала прерывания).

Далее выполняется описанный выше заключительный этап.

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

Умножение

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

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

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

Деление

Сначала также проводится проверка на 0. Если нулю равен делитель, в зависимости от реализации выдается сообщение о делении на 0, либо в качестве результата принимается бесконечность (для этого в некоторых форматах ПЗ имеется специальная кодовая комбинация). Когда нулю равно делимое, результат также принимается равным нулю.

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

Следующий шаг — деление мантисс, за которым идут нормализация, округление и компоновка числа из мантиссы и порядка.

Реализация логических операций

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

К базовым логическим операциям относятся: логическое отрицание (НЕ), логическое сложение (ИЛИ) и логическое умножение (И). Этот набор, как правило, дополняют операцией сложения по модулю 2 (исключающее ИЛИ).

Рис. 7.55. Структура операционного блока для выполнения логических операций

Булева переменная в ВМ представляется одним битом, однако на практике логические операции в ОПУ выполняются .сразу над совокупностью логических переменных, объединенных в рамках одного байта или машинного слова, причем над всеми битами этого слова выполняется одна и та же операция. Поскольку каждый бит совокупности логических переменных рассматривается как независимая переменная, никакие переносы между разрядами не формируются. Операционный блок (ОПБ) для выполнения логических операций обеспечивает реализацию всех перечисленных логических операций. Возможная структура подобного ОПБ показана на рис. 7.55.

Выбор нужной операции осуществляется с помощью двухразрядного управляющего кода L (/1/0). С учетом управляющего кода выходная функция Z может быть описана выражением:


 

А также другие работы, которые могут Вас заинтересовать

2610. Измерение скорости прецессии гироскопа 47.5 KB
  Измерение скорости прецессии гироскопа Цель работы: изучение основных закономерностей гироскопа; измерение скорости прецессии гироскопа, определение осевого момента инерции гироскопа. КРАТКАЯ ТЕОРИЯ Аксиально-симметричное тело (тело, обладающее цили...
2611. Электронный осциллограф 127.5 KB
  Изучение электронного осциллографа Цель работы: ознакомиться с устройством электронного осциллографа и применением его для простейших измерений. УСТРОЙСТВО ОСЦИЛЛОГРАФА Электронный осциллограф является одним из наиболее часто используемых в физических...
2612. Измерение моментов инерции параллелепипеда 84.5 KB
  Измерение моментов инерции параллелепипеда Цель работы: Измерить величины моментов инерции параллелепипеда относительно различных осей методом крутильных колебаний, провести сравнение полученных результатов с предсказанными теоретически...
2613. Грамматические значение и форма 52 KB
  Содержательная сторона слова представляет собой сложное образование, в котором сочетается информация разного типа. Например, в слове «чистый», с одной стороны, есть система значений...
2614. Розбудова Української незалежної держави. Національно-державне відродження українського народу (1991-2007 рр.) 136.5 KB
  Розбудова Української незалежної держави. Національно-державне відродження українського народу (1991-2007 рр.) Національно-державне відродження Українського народу. Соціально-політичний та економічний розвиток українського суспільства...
2615. Стратегії експериментального дослідження 73.5 KB
  Стратегії експериментального дослідження Основні питання Пояснювальна стратегія  Стратегія повторного дослідження.  Стратегія зіставлення  Формуюча стратегія. Біографічна стратегія Якось А.Ейнштейн, після того, як видатний...
2616. Поняття про програму та концепцію психологічного дослідження 57.5 KB
  Поняття про програму та концепцію психологічного дослідження Основні питання  Програма психологічного дослідження  Концепція психологічного дослідження Існування проблеми (проблемної ситуації) є вихідним моментом будь-якого наукового дослі...
2617. Минеральные ресурсы Волгоградской области 54.5 KB
  Минеральные ресурсы Волгоградской области Волгоградская земля содержит огромные запасы ценных ископаемых. В недрах области есть нефть и природный газ, бишофит, поваренные соли, фосфориты и сильвиниты, кварц, песок, известняки и мел, глины, железная...
2618. Физика и физические закономерности 138 KB
  Кольца Ньютона. Радиусы светлых и темных колец. Частым случаем полос равной толщины являются кольца Ньютона, которые наблюдаются в схеме, изображенной на рисунке. Плосковыпуклая линза с большим радиусом кривизны R выпуклой поверхностью лежит на...