УМНОЖИТЕЛЬ С ФИКСИРОВАННОЙ ТОЧКОЙ С ПРЕДВАРИТЕЛЬНЫМ НАСЫЩЕНИЕМ Российский патент 2010 года по МПК G06F7/499 

Область техники, к которой относится изобретение

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

Уровень техники

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

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

Положительные числа с дополнением до двух представляются в простой бинарной форме, с нулевым знаковым разрядом. Следовательно, самое большое положительное число, которое может быть представлено в формате дополнения до двух, представляет собой 2^n-1-1, где n - количество разрядов цифрового представления. Отрицательные числа с дополнением до двух представлены в виде двоичного числа, которое при добавлении к положительному числу такой же величины равняется нулю. Отрицательные числа дополнения до двух имеют знаковый разряд, равный единице. Поскольку представление дополнения до двух отрицательных чисел может использовать все n двоичных разрядов цифрового представления, самое большое отрицательное число, которое может быть представлено в формате дополнения до двух, представляет собой 2^n-1, которое по величине больше, чем самое большое положительное число дополнения до двух. Таким образом, например, диапазон значений целого числа со знаком, который может быть представлен в 32-разрядном поле, составляет от -2³¹ (0x8000 0000) до +2³¹-1 (0x7FFF FFFF).

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

Дробные величины могут быть представлены в цифровой форме фиксированной длины, используя так называемую систему обозначений формата Q. В системе обозначений формата Qn.x двоичные разряды значения интерпретируются как: один знаковый разряд, n целочисленных разрядов и x дробных разрядов. Общий формат Q для обработки цифрового сигнала представляет собой Q0.x (или просто Q.x), показывающий, что имеется один знаковый разряд, никаких целочисленных разрядов и x дробных разрядов. Число в системе обозначений Q.31 может быть выражено в 32 двоичных разрядах и будет иметь значения в пределах от -1 (0x8000 0000) до 1-2^-31 (0x7FFF FFFF).

При умножении чисел в формате Q важно принимать во внимание бинарную точку. Например, умножение Q.15 на Q.15 даст результат Q2.30. Однако желательно сохранить значение в формате Q.x. Чтобы урегулировать это, операции перемножения включают в себя перемножение с коэффициентом 2 - которое является эквивалентным операции сдвига влево - чтобы произвести результат Q.31. Перемножение двух n-разрядных значений вместе всегда будет производить значение, которое может быть представлено в 2n двоичных разрядах. Удвоение этого произведения произведет значение, которое может быть представлено в 2n двоичных разрядах во всех случаях, кроме одного: случая максимального отрицательного значения. Максимальное отрицательное значение в дополнении до двух представляет собой знаковый разряд (MSB) единицы со всеми другими двоичными разрядами, равными нулю. Сдвиг этого значения влево приводит к переполнению.

Пример представляет собой следующее перемножение двух 16-разрядных компонентов операции, чтобы произвести 32-разрядное произведение. Каждый из компонентов операции представляет собой отрицательную величину (знаковый разряд единицы), а их произведение должно быть положительным числом.

0x8000 × 0x8000 = 0x4000 0000 Перемножение 0x4000 0000 × 0x2 = 0x8000 0000 Удвоение (неправильный результат; должен быть положительным) 0x8000 0000 - 1 = 0x7FFF FFFF Результат с насыщением (самое большое положительное значение)

В этом примере каждый из двух компонентов операции является самым большим отрицательным числом, которое может быть представлено в виде 16 двоичных разрядов в формате дополнения до двух. Их произведение должно дать большое положительное значение. Однако фактический результат команды удваивающего умножения представляет собой самое большое отрицательное значение. Следовательно, из этого значения должна быть вычтена '1', чтобы получить величину насыщения 0x7FFFFFFF - нулевой знаковый разряд со всеми единицами в других разрядных позициях.

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

Раскрытие изобретения

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

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

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

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

Краткое описание чертежей

Фиг. 1 - функциональная блок-схема умножителя с предварительным насыщением в соответствии с одним вариантом осуществления.

Фиг. 2 - функциональная блок-схема умножителя с предварительным насыщением в соответствии с другим вариантом осуществления.

Фиг. 3 - блок-схема алгоритма для способа выполнения операции умножения с предварительным насыщением.

Осуществление изобретения

Умножитель обнаруживает компоненты операции для операции умножения, которые приведут к состоянию переполнения, если умножение будет выполнено. В ответ на это обнаружение умножитель выводит значение с насыщением. В одном варианте осуществления умножитель выводит значение с насыщением, изменяя компоненты операции таким образом, чтобы операция умножения привела к значению с насыщением в качестве произведения. Фиг. 1 изображает умножитель 40 с предварительным насыщением в соответствии с этим вариантом осуществления. Регистр 42 РОН (регистр общего назначения) содержит компоненты операции множителя (MR) и множимого (MD). Множитель вводится в устройство 44 перекодирования Бута.

Перекодирование Бута (иногда упоминаемое как модифицированное перекодирование Бута) представляет собой метод, предназначенный для снижения количества частичных произведений, которые будут добавляться при выполнении операции умножения. Вместо того чтобы рассматривать каждый двоичный разряд в множителе и производить соответствующее сдвигаемое частичное произведение, содержащее либо множимое, либо нуль, двоичные разряды множителя рассматриваются в группах, и добавляются сдвинутые частичные произведения, содержащие +/- кратные величины множимого. Этот метод снижает количество добавляемых частичных произведений. Например, в перекодировании Бута с основанием системы счисления, равным 4, двоичные разряды множителя рассматриваются в группах по два, наряду с MSB предыдущей группы (с нулем, добавленным к первой группе). Тогда частичные произведения производятся на основании значения групп двоичных разрядов, в соответствии со следующей таблицей:

Таблица
Перекодирование Бута с основанием системы счисления, равным 4 Группа двоичных разрядов Частичное произведение 000 0 001 1 × множимое 010 1 × множимое 011 2 × множимое 100 -2 × множимое 101 -1 × множимое 110 -1 × множимое 111 0

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

В этой реализации результаты вычислений устройства 44 перекодирования Бута выбирают частичные произведения для устройства 50 на основе дерева Уоллеса (или другого сумматора) через мультиплексоры 48 Бута. Мультиплексоры 48 Бута выбирают соответствующим образом модифицированное множимое от логического устройства 49 сдвигания/инвертирования, и каждый мультиплексор 48 выравнивается с позицией перекодированной группы двоичных разрядов в множителе. Логическое устройство 49 сдвигания/инвертирования производит модифицированные множимые, определяемые в таблице, следующим образом:

• 0 замещает все нули для двоичных разрядов множимых;

• ×1 прямо передает двоичные разряды множимых;

• ×2 сдвигает влево двоичные разряды множимых на одну позицию двоичного разряда; и

• взятие с обратным знаком выполняет поразрядное инвертирование (дополнение до единицы) на множимом, сдвинутом множимом или нулевом значении.

Следует отметить, что взятие с обратным знаком не завершено до тех пор, пока '1' не добавляется в LSB (самый младший двоичный разряд) к частичным произведениям в устройстве 50 на основе дерева Уоллеса (по правилу дополнения до двух для взятия с обратным знаком: дополнение до единицы + 1). Устройство 50 на основе дерева Уоллеса суммирует частичные произведения, выводя сумму и перенос, которые добавляются в сумматоре 52 распространения переноса, и произведение фиксируется в блоке 54. Специалистам в данной области техники должно быть понятно, что результат вычислений устройства перекодирования Бута и результаты вычислений мультиплексоров 48 Бута (или значение множимого) можно фиксировать, чтобы обеспечивать возможность конвейерной обработки.

Схема 56 обнаружения переполнения осуществляет контроль множителя и множимого в начале каждой операции умножения, выявляя значения компонентов операции, которые приведут к переполнению, требующему насыщения. Когда обнаружено ожидаемое переполнение, схема 56 обнаружения переполнения подает сигнал устройству 44 перекодирования Бута, чтобы изменить перекодирование двоичных разрядов множителя, и подает сигнал устройству 50 на основе дерева Уоллеса, чтобы изменить суммирование частичных произведений таким образом, чтобы операция умножения привела к значению с насыщением для произведения. Это является выполнимым, потому что переполнение могут вызывать ограниченное количество компонентов операции и эти компоненты операции известны заранее.

В частности, в одном варианте осуществления только случай, когда и множитель, и множимое содержат самое большое отрицательное значение, может вызвать переполнение, требующее насыщения. Когда обнаружено это состояние, схема 56 обнаружения переполнения направляет сигнал в устройство 44 перекодирования Бута, чтобы изменить перекодирование Бута. В ответ устройство 44 перекодирования Бута модифицирует перекодированную группу самых младших двоичных разрядов Бута (который, имея значение 000, обычно выбирается равным нулю), чтобы выбрать отрицательный нуль. Логическое устройство 49 сдвигания/инвертирования обеспечивает дополнение до единицы нуля (то есть все единицы) и подает сигнал в устройство 50 на основе дерева Уоллеса, чтобы прибавить '1' к частичным произведениям. Схема 56 обнаружения переполнения дополнительно направляет сигнал подавления в устройство 50 на основе дерева Уоллеса, чтобы подавить добавление '1', связанное с взятием нуля с обратным знаком (следует отметить, что в реализации конвейерной обработки сигнал "подавления +1" может быть фиксированным). Соответственно, расширенное знаком дополнение до единицы для нуля (0xFFFF FFFF) добавляется как частичное произведение, но соответствующая '1' - нет, эффективно производя вычитание '1' из результата. Например:

0x8000 × 0x8000 = 0x40000000 Перемножение двух самых больших отрицательных значений 0x40000000 × 0x2 = 0x80000000 Удвоение 0x80000000 + 0xFFFFFFFF = 0x7FFFFFFF Результат с насыщением (эффективное вычитание '1')

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

Фиг. 2 изображает другой вариант осуществления умножителя 40 с предварительным насыщением, в котором соответствующие компоненты имеют соответствующие ссылочные позиции. В этом варианте осуществления схема 56 обнаружения переполнения осуществляет контроль множителя и множимого, выявляя известные компоненты операции, которые приведут к переполнению, требующему насыщения. Когда эти компоненты операции обнаружены, схема 56 обнаружения переполнения выводит сигнал о том, что замещает результат с насыщением для результата вычислений произведения умножителя 40. Например, схема 56 обнаружения переполнения может выводить сигнал выбора мультиплексора, который заставляет мультиплексор 60 выбрать предварительно определенный результат вычислений с насыщением вместо результата вычислений сумматора 52 распространения переноса. Предварительно определенный результат вычислений с насыщением может содержать схемно-реализованное значение (то есть с разрядными позициями, связанными с шинами высокого или низкого напряжения) или, в качестве альтернативы, может содержать результат вычислений в виде адреса ячейки запоминающего устройства, такого как регистр. В варианте осуществления, где множество компонентов операции могут вызывать переполнение, требующее различных значений насыщения, схема 56 обнаружения переполнения может выводить многоразрядный сигнал выбора мультиплексора, который выбирает между множеством предварительно определенных значений насыщения и результатом вычислений сумматора 52. Результат вычислений схемы 56 обнаружения переполнения может быть фиксированным в реализации с конвейерной обработкой.

В этом варианте осуществления операция умножения может быть подавлена (то есть устройство перекодирования 44 Бута, логический блок 49, устройство 50 на основе дерева Уоллеса, сумматор 52 распространения переноса и другие схемы умножителя могут быть заблокированы), чтобы снизить потребляемую мощность. В качестве альтернативы, перемножению компонентов операции может быть дозволено производиться через умножитель 40, а результат может просто отвергаться, поскольку вместо этого в блоке 54 фиксируется результат с насыщением. В этом варианте осуществления задержка мультиплексора 60 добавляется к каждой операции умножения, выполняемой умножителем 40, хотя эта задержка может быть смягчена посредством использования неиспользованного участка существующего мультиплексора, использования фиксирования мультиплексора или с помощью других методов, известных в технике. Состояние переполнения определяется очень рано, и решение выбрать значение с насыщением не является частью критического пути.

Фиг. 3 изображает способ выполнения операции умножения с фиксированной точкой насыщения, для которой, по меньшей мере, один известный набор компонентов операции может вызвать переполнение, требующее насыщения. Первоначально (то есть до выполнения какого-либо перемножения) компоненты операции обследуются (на этапе 70). Компоненты операции сравниваются с известными значениями, которые могут вызвать переполнение (на этапе 72). Например, в некоторых случаях, если оба компонента операции содержат самое большое отрицательное значение, которое может быть представлено в пределах поля двоичных разрядов компонентов операции, может последовать переполнение. Если умножение компонентов операции не вызовет переполнение (на этапе 72), выполняется перемножение, и выводятся результаты (на этапе 74). Если умножение компонентов операции приведет к переполнению, требующему насыщения (на этапе 72), то в соответствии с одним или больше вариантами осуществления результат с насыщением выводится без перемножения первоначальных компонентов операции (на этапе 76).

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

В обоих вариантах осуществления (то есть вариантах осуществления, изображенных на Фиг. 1 и 2) компоненты операции, которые могут вызвать переполнение, обнаруживаются рано, и умножитель 40 непосредственно выводит результат с насыщением. Это представляет существенное улучшение рабочих характеристик и экономию энергии по сравнению с обычной методологией, заключающейся только в обнаружении переполнения посредством обследования произведения и замены впоследствии произведения значением с насыщением. Умножитель 40 в соответствии с одним или больше вариантами осуществления, раскрытыми в данном описании, особенно хорошо подходит для быстродействующих процессоров и/или процессоров, в которых низкая потребляемая мощность представляет собой критический фактор, например для портативных электронных устройств с батарейным питанием.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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