Высокоскоростные модули целочисленного деления



Скачать 151.69 Kb.
Дата09.08.2019
Размер151.69 Kb.
ТипРешение

Высокоскоростные модули целочисленного деления

Н.Ю. Сорокин, Е.В. Вохмин

ГОУ ВПО Тихоокеанский государственный университет, nus@mail.kshtu.ru

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

Для упрощения проектируемых устройств чаще всего применяется целочисленная арифметика, так как использование модулей с плавающей точкой не всегда оправдано и приводит к значительному усложнению устройств. Однако существующие в настоящее время реализации алгоритмов целочисленного деления накладывают дополнительные ограничения в процессе разработки вычислительных модулей на базе программируемой логики. Такими ограничениями являются представления операндов и результата деления. Например, в стандартном программном обеспечении для Xilinx FPGA предлагается использовать блок целочисленного деления со следующими параметрами: 32-х битные операнды, 32-х битный частичный остаток от деления. Для решения задач повышения точности результата, этого модуля недостаточно. Еще одна особенность заключается в том, что данный модуль не является быстродействующим и занимает достаточно большое место на кристалле. Целью данной работы ставится разработка быстродействующих модулей целочисленного деления, получение неограниченной разрядности остатка от деления и оптимизация этих модулей для Xilinx FPGA.
Методы деления

Как известно, основу целочисленного деления составляет общепринятый способ деления с помощью операций вычитания или сложения и сдвига. Задача сводится к вычислению частного и остатка от деления на таких, что Q=int(Y/D) и S=Y-Q*D при . Деление выражается как последовательность вычитаний делителя сначала из делимого, а затем из образующихся в процессе деления частичных остатков.

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

, (1)

при , и.

После n итераций, на основании приведенных формул получаем:

. (2)

Частное от деления 2n-разрядного числа на n-разрядное может содержать более чем n разрядов. В этом случае возникает переполнение, из-за чего перед выполнением деления необходима проверка условия .


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

Алгоритм 1. Деление с восстановлением остатка



  1. Исходное значение частичного остатка (ЧО) полагается равным старшим разрядам делимого.

  1. ЧО удваивается путем сдвига на один разряд влево. При этом в освобождающийся при сдвиге младший разряд ЧО заносится очередная цифра частного.

  1. Из сдвинутого ЧО вычитается делитель и анализируется знак результата вычитания.

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

  1. Пункты 2-4 последовательно выполняются для получения всех цифр модуля частного.

Алгоритм 2. Деление без восстановления остатка

  1. Исходное значение ЧО полагается равным старшим разрядам делимого.

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

  1. Из сдвинутого ЧО вычитается делитель, если остаток положителен, и к сдвинутому частичному остатку прибавляется делитель, если остаток отрицательный.

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

  1. Пункты 2-4 последовательно выполняются для получения всех цифр модуля частного.

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

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



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

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

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

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

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

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


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


В основе третьей группы методов ускорения операции деления лежит так называемый алгоритм SRT, различные реализации которого описаны в работах [6-8]. Этот алгоритм представляет собой модификацию деления без восстановления остатка. В стандартной процедуре на каждом шаге помимо сдвига частичного остатка производится прибавление либо вычитание делителя. В SRT-алгоритме сдвиг частичного остатка также имеется в каждой итерации, однако сложение или вычитание, в зависимости от получающегося частного остатка, на отдельных шагах может не выполняться, что, безусловно, позитивно влияет на быстродействие деления.

Рассмотрим данный алгоритм применительно к положительным целым числам. Делимое представляется n-разрядным числом, а делитель — m-разрядным. Процедура деления начинается с удаления в делителе всех нулей, предшествующих старшей единице, реализуемой при помощи сдвига делителя влево на требуемое число разрядов. На аналогичное число разрядов влево сдвигается и делимое. Далее выполняются итерации, в которых вычисляются цифры частного и частичные остатки. Действия, выполняемые на i-ой итерации, можно описать следующим образом:



(3)

. (4)

В формуле (4) частное представляется в системе счисления, отличной от двоичной. Это означает, что цифры частного могут иметь больше, чем два значения {0,1}. В рассматриваемом случае – {-1,0,1}. По завершению всех итераций, если последний остаток отрицателен, выполняется коррекция этого остатка и полученного частного, для чего к остатку прибавляется делитель, а из частного вычитается единица с весом младшего разряда. Последний шаг в алгоритме — преобразование частного из системы {-1,0,1} в систему {0,1}.

Необходимо отметить, что представление чисел в избыточных системах исчисления, как, например, в алгоритме умножения Бута [3,5], является одним из самых эффективных методов повышения производительности. В то же время реализация такого подхода ведет к усложнению аппаратуры делителя, в частности надстраивается логика определения операции, выполняемой в очередной итерации. Для этой цели в состав устройства деления включается специальная память, хранящая таблицу, определяющую необходимые действия, в зависимости от текущей комбинации цифр в частичном остатке и делителе. Тем не менее, выигрыш в быстродействии оказывается решающим моментом, и данный метод широко используется в микропроцессорах.
Современные устройства целочисленного деления

К современным устройствам деления можно отнести стандартный модуль целочисленного деления IP Core Xilinx Divider v3.0. Данный модуль представляет собой параметризированное синхронное устройство, позволяющее делить n-разрядное делимое на m-разрядный делитель. Результат деления представляется в виде пары чисел: частное и остаток. Основные свойства модуля деления фирмы Xilinx:



  • использование в качестве модуля (IP core) для всех семейств Virtex™, Virtex-E, Virtex-II™,Virtex-II Pro™, Spartan™-II, Spartan-IIE, Spartan-3 и Virtex-4 FPGA;

  • разрядность делимого от 1 до 32 бит;

  • разрядность делителя от 3 до 32 бит;

  • разрядность дробного остатка (fractional remainder) от 3 до 32 бит.

В Таблице 1 представлены характеристики модуля целочисленного деления фирмы Xilinx. Этот модуль имеет два значительных недостатка. Во-первых, большое занимаемое место на кристалле, а во-вторых, достаточно ограниченные возможности использования – значения остатка от деления не более 32 бит, что не позволяет использовать этот модуль как универсальный во всех вычислительных задачах, решаемых на базе ПЛИС.


Таблица 1
Характеристики 32-х разрядного модуля Xilinx Divider 3.0

Характеристика

Разрядность остатка, бит


8

16

32

Количество секций (slices)

2247

2742

3843

Количество триггеров (Flip Flops)

4020

4904

6864

Количество таблиц (LUTs)

1400

1680

2240

Fmax, МГц

204,3

201,6

193,1



Реализация модулей целочисленного деления на FPGA

Для реализации на базе Xilinx FPGA были выбраны алгоритмы целочисленного деления с восстановлением и без восстановления остатка, а также модификация алгоритма SRT.

Все алгоритмы были закодированы с помощью языка VHDL без использования каких-либо специфических конструкций и блоков, например, сумматоров, умножителей Xilinx FPGA. Это позволяет использовать данные разработки (VHDL код) в дизайнах, ориентированных не только на микросхемы программируемой логики фирмы Xilinx, но и, например, на микросхемах фирмы Altera. При этом все характеристики модулей деления для сравнения были взяты только с дизайнов, выполненных на микросхемах Xilinx FPGA Virtex-II Pro™. Реализация дизайнов была выполнена с использованием САПР Xilinx ISE 6.3i.

Все разработанные модули целочисленного деления имеют одинаковый интерфейс, состоящий из входных шин операндов (n-разрядное делимое и m-разрядный делитель), выходной шины q-разрядного результата и шины управления, включающей в себя синхросигнал, сигналы сброса, запуска, готовности и ошибки. Значения разрядности каждой шины объявлены как параметры модуля (с помощью конструкции generic), что позволяет полностью параметризировать код модуля. При этом количество циклов, необходимых для вычисления q-разрядного частного, равно q плюс циклы инициализации для каждого разработанного модуля деления.

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

Помимо конвейеризации значительную роль в повышении быстродействия сыграла оптимизация с помощью временных ограничений (timing constraints) и ограничений по площади (area constraints) при расположении дизайнов на кристалле Xilinx FPGA. Наложение условий по времени на синхросигнал, а также на некоторые из внутренних сигналов позволили оптимизировать дизайн по быстродействию. Ограничения по площади были использованы также для увеличения быстродействия дизайнов, за счет расположения дизайнов вокруг некоторого набора аппаратных ресурсов – сумматоров и умножителей. Все модули были синтезированы с помощью САПР Xilinx ISE 6.3i. Везде в настройках указывалась высшая степень оптимизации с целью получения максимального быстродействия, что для модулей с разрядностью входных и выходных операндов более 64 бит приводило к значительному увеличению времени синтеза и размещения дизайна на кристалле ПЛИС.

Верификация реализованных модулей целочисленного деления была произведена с помощью симулятора ModelSIM XE 5.8. Для проверки модулей использовалась заранее сгенерированная последовательность из ста тестовых данных. Результаты симуляции дизайнов были сохранены в файл, после чего были сверены с тестовыми данными. Для отладки логики дизайнов симуляция производилась на этапе синтеза, для выявления и анализа реальных задержек дизайнов симулирование производилось после операции Place and Route САПР Xilinx ISE 6.3i.
Характеристики разработанных модулей

Целью работы являлось получение модулей целочисленного деления для ПЛИС, характеристики которых, например, разрядность входных и выходных операндов, превосходили бы стандартный модуль деления фирмы Xilinx. Параметризированные модули были спроектированы для разрядностей входных и выходных операндов от 8 до 128 бит, каждый из них был синтезирован и размещен на кристаллах микросхем семейства Virtex-II Pro™. В результате реализации модулей деления были получены данные о скорости и занимаемой площади на кристалле. Все характеристики были сняты для микросхем семейства Virtex-II Pro™. Среди фиксируемых характеристик были: максимальная частота работы дизайна, количество занимаемых секций (slices) на микросхеме, количество используемых триггеров, таблиц (LUTs). Вся эта информация собиралась для различных комбинаций разрядностей входных и выходных операндов.

Сравнительные характеристики для модулей с 32–разрядными входных данными представлены на Рисунках 1-3. Как видно из графиков, модуль деления без восстановления остатка значительно превосходит по скорости и значительно ниже по занимаемой площади, чем стандартный делитель фирмы Xilinx. Ввиду особенностей алгоритма при реализации была проведена значительная оптимизация вычислительной структуры, за счет чего и была получена высокая скорость вычислений. Делитель с восстановлением остатка отстает по временным параметрам, но практически не уступает по аппаратным затратам делителю без восстановления остатка.



Рис. 1. Зависимость тактовой частоты в модулях деления от разрядности остатка



Рис. 2. Зависимость количества секций в модулях деления от разрядности остатка



Рис. 3. Зависимость количества триггеров в модулях деления от разрядности остатка

Данные по характеристикам разработанных модулей для различных разрядностей входных операндов сведены в Таблицы 2-3. Из данных ясно видно, что алгоритм деления без восстановления остатка является единственно применимым алгоритмом для систем с повышенными требования по точности вычислений и скорости систем на кристалле. Стоит отметить, что при повышении точности результата деления для фиксированной разрядности входных операндов максимальная рабочая частота меняется незначительно.

Таблица 2

Скорость модулей деления (в МГц) при 32-х битных входных операндах

Модуль деления \ Разрядность остатка

8

16

32

64

128

Делитель Xilinx

204,3

201,6

193,1

-

-

Деление по алгоритму SRT

78,1

77,2

76,1

72,4

64,3

Деление с восстановлением остатка

126,6

120,9

108,8

89,1

81,2

Деление без восстановления остатка

248,6

247,4

244,9

193,1

180,3

Таблица 3


Скорость модулей деления (в МГц) при 64-х и 128-и разрядных операндах

Модуль деления \ Разрядность остатка

n=64, m =64

n=128, m =128

32

64

128

32

64

128

Делитель Xilinx

-

-

-

-

-

-

Деление по алгоритму SRT

62,5

61,8

60,5

47,9

47,1

46,2

Деление с восстановлением остатка

75,3

57,8

48,4

42,8

38,9

36,6

Деление без восстановления остатка

173,6

160,3

157,6

92,2

89,9

86,5


Заключение

Многие вычислительные задачи, реализуемые на базе программируемой матричной логики, используют операцию деления, причем часто требуется получение результата с высокой точностью. Стандартный модуль деления для ПЛИС фирмы Xilinx для не предоставляет возможность получения остатка от деления более чем 32 разряда, что значительно ограничивает точность вычислений. Детальная разработка и последующая оптимизация модулей целочисленного деления показала значительное превосходство по скорости модуля деления без восстановления остатка, причем данный модуль является более универсальным, чем стандартный модуль фирмы Xilinx. В работе описаны результаты реализации модулей целочисленного деления с повышенной разрядностью остатка, например, 64 и 128 бит, причем эти значения не являются граничными – по необходимости, возможно проектирование модулей деления с еще большей точностью. При этом максимальная частота модуля меняется незначительно. Полученные временные характеристики, например, частота 244,9 МГц для 32-х разрядного и 180,3 МГц для 128-х разрядного остатков, позволили заменить модули фирмы Xilinx в вычислительных задачах, решаемых на базе Xilinx FPGA, при этом значительно увеличив точность вычислений в реальном масштабе времени.



Литература

  1. Цилькер Б.Я., Орлов С.А. Организация ЭВМ и систем. – СПБ.:Питер, 2004. – 667 с.

  2. Hiasat A.A., Abdel-Aty-Zohdy H.S. Semi-Custom VLSI Design and Implementation of a New Efficient RNS Division Algorithm // The Computer Journal. – 1999. - № 3 (42). – P. 232-240.

  3. Mueller S.M., Paul W.J. Computer Architecture Complexity and Correctness. – Springer-Verlag, 2000. – P. 553.

  4. Parhami Behrooz Computer Arithmetic: Algorithms and Hardware Designs. – Oxford University Press, New York, 2000. – P. 489.

  5. Paul W. J., Seidel P.-M. To Booth or not to Booth // Integration, the VLSI journal. – 2002. - № 1-3(32). – P. 5-40.

  6. Harris D.L., Oberman S.F., Horowitz M.A. SRT Division Architectures and Implementations // Proceedings of 13th IEEE International Symposium on Computer Arithmetic. – 1997. – P. 18-25.

  7. Ercegovac M.D., Lang T. Division and Square-Root Algorithms: Digit-Recurrence Algorithms and Implementations. – Norwell, MA: Kluwer Academic Publishers, 1994. – P. 230.

  8. Oberman S. F., Flynn M. Division algorithms and implementations // IEEE Transactions on Computers. - 1997. - № 8(46). – P. 833–854.






Каталог: conf
conf -> «Google облака как виртуальное рабочее место»
conf -> Инновационная технология восстановления высокоточного многолезвийного инструмента
conf -> Ежегодно во всём мире приходят в негодность десятки миллионов машин
conf -> Проблемы устойчивой работы синхронных двигателей в
conf -> Проблемы устойчивой работы синхронных двигателей в
conf -> Энергетический подход к оценке функционирования агроэкосистемы как операционально замкнутой самоорганизующейся структуры
conf -> Региональная
conf -> Гибридный способ дедупликации для резервного копирования данных
conf -> «Warm-up activities» на уроках английского языка


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©vossta.ru 2019
обратиться к администрации

    Главная страница