БЫСТРЫЙ ПОСЛЕДОВАТЕЛЬНЫЙ ЦЕЛОЧИСЛЕННЫЙ ДЕЛИТЕЛЬ ПО ОСНОВАНИЮ 4
А.С. Румянцев
УДК 004.315.5
БЫСТРЫЙ ПОСЛЕДОВАТЕЛЬНЫЙ ЦЕЛОЧИСЛЕННЫЙ ДЕЛИТЕЛЬ ПО ОСНОВАНИЮ 4
А.С. Румянцев
Разработан однотактовый блок нормализации делителя и делимого, занимающий немногим большую площадь по сравнению с последовательными (многотактовыми) блоками нормализации. Предложен метод определения ситуации переполнения при целочисленном знаковом и беззнаковом делении, позволяющий минимизировать площадь, занимаемую аппаратными ресурсами, и снизить их энергопотребление. Приведено сравнение различных архитектурных вариантов конвейеризации устройства делителя по основанию 4, которые используют разработанный однотактовый блок нормализации и предложенный метод определения ситуации переполнения. Ключевые слова: целочисленное деление по основанию 4, нормализация делителя и делимого, переполнение при целочисленном знаковом и беззнаковом делении.
Введение
Целочисленное деление является одной из наиболее затратных операций в современных процессорах, так как деление обладает самым длительным временем выполнения среди всех базовых целочисленных арифметических операций [1]. Хотя операция деления встречается не так часто, как операции сложения и умножения, есть множество важных областей, которые используют эту операцию: системы рендеринга, искусственный интеллект, алгоритмы сжатия данных и т.д. [2]. Наиболее часто используется деление на основе повторов [3], так как деление на основе последовательного приближения [4] в большинстве случаев предполагает использование однотактового умножителя или даже нескольких однотактовых умножителей. Использование большего основания при делении на основе повторов является очевидным способом ускорения операции деления [5], но этот подход увеличивает сложность аппаратной реализации и, как следствие, приводит к увеличению занимаемой площади, энергопотреблению и соотношения цена/производительность. На сегодняшний день представлено множество подходов к реализации деления на больших основаниях [6], но некоторые аспекты реализации все еще остаются не до конца исследованными, например, эффективный по площади и энергопотреблению метод определения ситуации переполнения при делении.
В настоящей работе разработан однотактовый блок нормализации делимого и делителя и предложен метод определения ситуации переполнения при делении для использования в каноническом устройстве делителя для 64/32-, 32/16- и 16/8-битных беззнаковых и знаковых целых чисел по основанию 4 (radix-4) [2, 3]. Разработанный блок нормализации позволяет выполнять нормализацию делимого и делителя за один такт, занимая при этом небольшую площадь в сравнении с последовательными блоками нормализации [7]. Предлагаемый метод определения ситуации переполнения при делении позволяет минимизировать площадь, занимаемую аппаратными ресурсами, и снизить их энергопотребление по сравнению с широко используемым на данный момент стандартным подходом [2, 6]. Кроме того, в работе приведено сравнение различных вариантов конвейеризации устройства делителя по основанию 4. Все рассмотренные варианты реализации устройства деления были верифицированы на корректность и синтезированы на библиотеку элементов TSMC LP120a 40 нм с использованием Synopsys DC и ICC.
Однотактовый блок нормализации делимого и делителя
Блок нормализации является одним из самых низкоскоростных блоков в критических путях устройств деления [3]. При использовании последовательных блоков нормализации среднее время нормализации будет значительным [7], но занимаемая площадь окажется минимальной. Разработанный блок нормализации является однотактовым, занимает небольшую площадь по сравнению с последовательным блоком нормализации и позволяет определить случай равенства делителя нулю.
Пусть x, d, q, rem обозначают делимое, делитель, частное и остаток от деления соответственно:
x q *d rem .
(1)
В формуле (1) и в последующих формулах знак «*» означает скалярное умножение, если не оговорено иное.
При реализации делителя на основе повторов с использованием таблицы выбора цифры частного необходимо, чтобы делимое и делитель были нормализованы [7]. Для нормализации произвольных делимых и делителей необходимо определить значение коэффициента нормализации ζ для получения нормализованного делителя (d*ζ). Тогда, после нормализации делителя и делимого, (1) приобретет вид
x* q*(d *) rem*, rem * d * .
(2)
Основными задачами блока нормализации являются:
нахождение позиции ведущей «1» в делителе;
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 6 (76)
81
БЫСТРЫЙ ПОСЛЕДОВАТЕЛЬНЫЙ ЦЕЛОЧИСЛЕННЫЙ ДЕЛИТЕЛЬ ПО ОСНОВАНИЮ 4
сдвиг делителя влево на определенную величину, чтобы ведущая «1» оказалась в позиции наибольшего значащего бита (2). Делимое сдвигается на соответствующую величину. Архитектура разработанного однотактового блока нормализации с определением равенства нулю
делителя показана на рис. 1 для 64-битного делимого и 32-битного делителя.
Рис. 1. Архитектура однотактового блока нормализации с определением равенства нулю делителя
Метод определения ситуации переполнения при делении
В рассматриваемом в работе делителе делимое (2N) больше частного (N) в два раза. При этом делитель обладает двумя режимами работы:
беззнаковое деление: 0 x 22n 1;0 d 2n 1;
знаковое деление: 22n1 x 22n1 1;2n1 d 2n1 1.
Довольно часто деление двух операндов, делимого и делителя, приводит к ситуации переполнения. В общем случае, с учетом беззнакового и знакового делений, переполнение происходит в следующих случаях.
1.Делитель d равен нулю. Заметим, что данная ситуация определяется в разработанном блоке нормализации делимого и делителя.
2.Частное q и/или остаток rem выходят за следующие диапазоны: – при беззнаковом делении
0 q 2n 1;
(3)
0 rem d 1; – при знаковом делении
2n1 q 2n1 1;
(4) (5)
d 1 rem d 1.
(6)
Воспользовавшись формулами (1), (3–6), можно перейти к стандартному принципу определения ситуации переполнения при делении беззнаковых и знаковых чисел [2, 6].
1. Делитель d равен нулю. 2. Не выполняются следующие условия:
– при беззнаковом делении x d *2n
– при знаковом делении
x d * 2n1, sign(x) sign(d);
x
d
* 2n1
d
, sign(x)
sign(d ).
82 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 6 (76)
А.С. Румянцев
Рассмотренный выше вариант определения ситуации переполнения при делении имеет серьезные недостатки, которые значительно увеличивают занимаемую аппаратными ресурсами площадь и критический путь устройства делителя:
необходимость получения модуля делимого x, который в разработанном устройстве деления может достигать размера в 64 бита;
сравнение абсолютного значения делимого по отношению к абсолютному значению сдвинутого делителя. В разработанном устройстве деления для этого потребуется использование полнофункционального 64-битного сумматора;
при несовпадении знаков делимого и делителя необходимо будет сравнить абсолютное значение делимого и суммы абсолютного значения сдвинутого делителя с его абсолютным значением. В некоторых ситуациях для этого потребуется использование полнофункционального 32-битного сумматора. В разработанном методе при делении используется иной подход к определению ситуации пере-
полнения, в котором отсутствуют приведенные недостатки. Делимое x разделяется на две части Y и Z, положение которых зависит от типа деления: беззнаковое или знаковое (рис. 2).
2n–1
Беззнаковое делимое (x
УДК 004.315.5
БЫСТРЫЙ ПОСЛЕДОВАТЕЛЬНЫЙ ЦЕЛОЧИСЛЕННЫЙ ДЕЛИТЕЛЬ ПО ОСНОВАНИЮ 4
А.С. Румянцев
Разработан однотактовый блок нормализации делителя и делимого, занимающий немногим большую площадь по сравнению с последовательными (многотактовыми) блоками нормализации. Предложен метод определения ситуации переполнения при целочисленном знаковом и беззнаковом делении, позволяющий минимизировать площадь, занимаемую аппаратными ресурсами, и снизить их энергопотребление. Приведено сравнение различных архитектурных вариантов конвейеризации устройства делителя по основанию 4, которые используют разработанный однотактовый блок нормализации и предложенный метод определения ситуации переполнения. Ключевые слова: целочисленное деление по основанию 4, нормализация делителя и делимого, переполнение при целочисленном знаковом и беззнаковом делении.
Введение
Целочисленное деление является одной из наиболее затратных операций в современных процессорах, так как деление обладает самым длительным временем выполнения среди всех базовых целочисленных арифметических операций [1]. Хотя операция деления встречается не так часто, как операции сложения и умножения, есть множество важных областей, которые используют эту операцию: системы рендеринга, искусственный интеллект, алгоритмы сжатия данных и т.д. [2]. Наиболее часто используется деление на основе повторов [3], так как деление на основе последовательного приближения [4] в большинстве случаев предполагает использование однотактового умножителя или даже нескольких однотактовых умножителей. Использование большего основания при делении на основе повторов является очевидным способом ускорения операции деления [5], но этот подход увеличивает сложность аппаратной реализации и, как следствие, приводит к увеличению занимаемой площади, энергопотреблению и соотношения цена/производительность. На сегодняшний день представлено множество подходов к реализации деления на больших основаниях [6], но некоторые аспекты реализации все еще остаются не до конца исследованными, например, эффективный по площади и энергопотреблению метод определения ситуации переполнения при делении.
В настоящей работе разработан однотактовый блок нормализации делимого и делителя и предложен метод определения ситуации переполнения при делении для использования в каноническом устройстве делителя для 64/32-, 32/16- и 16/8-битных беззнаковых и знаковых целых чисел по основанию 4 (radix-4) [2, 3]. Разработанный блок нормализации позволяет выполнять нормализацию делимого и делителя за один такт, занимая при этом небольшую площадь в сравнении с последовательными блоками нормализации [7]. Предлагаемый метод определения ситуации переполнения при делении позволяет минимизировать площадь, занимаемую аппаратными ресурсами, и снизить их энергопотребление по сравнению с широко используемым на данный момент стандартным подходом [2, 6]. Кроме того, в работе приведено сравнение различных вариантов конвейеризации устройства делителя по основанию 4. Все рассмотренные варианты реализации устройства деления были верифицированы на корректность и синтезированы на библиотеку элементов TSMC LP120a 40 нм с использованием Synopsys DC и ICC.
Однотактовый блок нормализации делимого и делителя
Блок нормализации является одним из самых низкоскоростных блоков в критических путях устройств деления [3]. При использовании последовательных блоков нормализации среднее время нормализации будет значительным [7], но занимаемая площадь окажется минимальной. Разработанный блок нормализации является однотактовым, занимает небольшую площадь по сравнению с последовательным блоком нормализации и позволяет определить случай равенства делителя нулю.
Пусть x, d, q, rem обозначают делимое, делитель, частное и остаток от деления соответственно:
x q *d rem .
(1)
В формуле (1) и в последующих формулах знак «*» означает скалярное умножение, если не оговорено иное.
При реализации делителя на основе повторов с использованием таблицы выбора цифры частного необходимо, чтобы делимое и делитель были нормализованы [7]. Для нормализации произвольных делимых и делителей необходимо определить значение коэффициента нормализации ζ для получения нормализованного делителя (d*ζ). Тогда, после нормализации делителя и делимого, (1) приобретет вид
x* q*(d *) rem*, rem * d * .
(2)
Основными задачами блока нормализации являются:
нахождение позиции ведущей «1» в делителе;
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 6 (76)
81
БЫСТРЫЙ ПОСЛЕДОВАТЕЛЬНЫЙ ЦЕЛОЧИСЛЕННЫЙ ДЕЛИТЕЛЬ ПО ОСНОВАНИЮ 4
сдвиг делителя влево на определенную величину, чтобы ведущая «1» оказалась в позиции наибольшего значащего бита (2). Делимое сдвигается на соответствующую величину. Архитектура разработанного однотактового блока нормализации с определением равенства нулю
делителя показана на рис. 1 для 64-битного делимого и 32-битного делителя.
Рис. 1. Архитектура однотактового блока нормализации с определением равенства нулю делителя
Метод определения ситуации переполнения при делении
В рассматриваемом в работе делителе делимое (2N) больше частного (N) в два раза. При этом делитель обладает двумя режимами работы:
беззнаковое деление: 0 x 22n 1;0 d 2n 1;
знаковое деление: 22n1 x 22n1 1;2n1 d 2n1 1.
Довольно часто деление двух операндов, делимого и делителя, приводит к ситуации переполнения. В общем случае, с учетом беззнакового и знакового делений, переполнение происходит в следующих случаях.
1.Делитель d равен нулю. Заметим, что данная ситуация определяется в разработанном блоке нормализации делимого и делителя.
2.Частное q и/или остаток rem выходят за следующие диапазоны: – при беззнаковом делении
0 q 2n 1;
(3)
0 rem d 1; – при знаковом делении
2n1 q 2n1 1;
(4) (5)
d 1 rem d 1.
(6)
Воспользовавшись формулами (1), (3–6), можно перейти к стандартному принципу определения ситуации переполнения при делении беззнаковых и знаковых чисел [2, 6].
1. Делитель d равен нулю. 2. Не выполняются следующие условия:
– при беззнаковом делении x d *2n
– при знаковом делении
x d * 2n1, sign(x) sign(d);
x
d
* 2n1
d
, sign(x)
sign(d ).
82 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 6 (76)
А.С. Румянцев
Рассмотренный выше вариант определения ситуации переполнения при делении имеет серьезные недостатки, которые значительно увеличивают занимаемую аппаратными ресурсами площадь и критический путь устройства делителя:
необходимость получения модуля делимого x, который в разработанном устройстве деления может достигать размера в 64 бита;
сравнение абсолютного значения делимого по отношению к абсолютному значению сдвинутого делителя. В разработанном устройстве деления для этого потребуется использование полнофункционального 64-битного сумматора;
при несовпадении знаков делимого и делителя необходимо будет сравнить абсолютное значение делимого и суммы абсолютного значения сдвинутого делителя с его абсолютным значением. В некоторых ситуациях для этого потребуется использование полнофункционального 32-битного сумматора. В разработанном методе при делении используется иной подход к определению ситуации пере-
полнения, в котором отсутствуют приведенные недостатки. Делимое x разделяется на две части Y и Z, положение которых зависит от типа деления: беззнаковое или знаковое (рис. 2).
2n–1
Беззнаковое делимое (x