Диссертация (1150736), страница 13
Текст из файла (страница 13)
Задача аппроксимации не накладывает требований на гладкость, однако дополнительные ограничения позволяют уменьшить размер таблиц за счет переиспользования коэффициентов между сегментами.Рассмотрим аппроксимирующий квазисплайн степени −1 с 20 звеньями.Будем рассматривать двух- и четырехзвенные квазисплайны. Степени двойкииспользуются, поскольку в этом случае старшие биты аргумента используются как адрес в таблице коэффициентов, а младшие — как аргумент интерполяции, без необходимости вычислений по модулю. Двузвенный квазисплайнпозволяет переиспользовать все коэффициенты, не добавляя дополнительныхвычислений.
Квазисплайны с числом сегментов более 2 добавляют дополнительные сумматоры в вычислительный блок, таким образом, энергоэффективность переиспользования данных уменьшается за счет роста количества вычислений.70Требование гладкости является чрезмерно жестким, и его выполнение может приводить к увеличению количества сегментов кусочно-полиномиальнойинтерполяции и удвоению размера таблиц, что не компенсируется их последующим сокращением.
Для сохранения количества сегментов в узлах квазисплайна допускаются невязки, которые на практике равны 0 на большинствесегментов. Поскольку ограничения не являются жесткими, такая оптимизацияне приводит к уменьшению шага сетки по сравнению с задачей без ограничений.Поскольку часть коэффициентов обнуляется, предложенный метод можетсчитаться методом неравномерного табулирования, поскольку на сегментах,где функция имеет меньший модуль производной, для ее табулирования используется меньше данных. Для одного квазисплайна необходимо хранить коэффициентов полинома и (20 − 1) дополнительных значений невязок вовнутренних узлах квазисплайна.
Появление невязок приводит к необходимости дополнительных таблиц и дополнительных сумматоров для внесения поправок в коэффициенты.Такой алгоритм аппроксимации является обобщением гладкого двузвенного сплайна, рассматривавшегося Стролло и др. [3]. Использование болеедвух звеньев квазисплайна и ослабление требований гладкости позволяет существенно сократить размер таблиц.
Например, переход к четырехзвенномуквазисплайну по сравнению с двузвенным дает сокращение таблиц на болеечем 30%.Сформулируем оптимизационную задачу нахождения невязок для почтигладкого квазисплайна.2.4.3Оптимизационная задачаРассмотрим задачу аппроксимации функции многозвенным квазисплайном заданной степени с заданным количеством звеньев и с заданной точностью.
В этом разделе формулируется задача линейного программирования,нацеленная как на достижение точности аппроксимации, так и на сокращениедлины таблиц.71Для краткости обозначений будем считать, что длины всех сегментов полиномиальной интерполяции равны 1. Таким образом, границы сегментов полиномиальной интерполяции есть целые числа:0 ≤ < 20 , = ,где 20 — количество звеньев почти гладкого квазисплайна. Квазисплайн будем обозначать { ()}. Он определяется определяется коэффициентами своихполиномов, причём () - полином -го звена.В пределах каждого звена выберем сетку отсчётов ¯ = 2−2 при 0 ≤ <2−2 с шагом = 2−2 .Вводятся дополнительные ограничения на точность представления полиномов ∈ , где — множество двоичных дробей с дробной частью из цифр.Теорема 2 Пусть > 2, ∈ (, [0, 20 ]) и > 0 — заданная точностьаппроксимации.
Определим(︂¯ = −28( − 2)!)︂ (︂)︂−1 2 ,2 (0 )1+.2Пусть существует решение следующей смешанной целочисленной задачилинейного программирования относительно коэффициентов почти гладкогоквазисплайна { ()} на отрезке [0, 20 ] при ограничении на представление ∈ :⎧∑︀ ∑︀20 −1⎪=⎪=0=1 , |, |⎨ ≤ ¯⎪⎪⎩ * = min0 ,∈[0..2 −1]где =, =sup | ( + ¯ ) − ( + ¯ )|,0≤<22() ( )()0 ≤ < 20 ,0 < < 20 .− −1 ( ),Тогда квазисплайн { ()} обеспечивает заданную равномерную точностьаппроксимации функции :sup | () − ()| ≤ ,∈[0,20 ]72а количество ненулевых бит для коэффициентов в промежуточных узлах квазисплайна не превосходит≤02∑︁−1 −1∑︁max(0, 2 + ⌈ + log2 |, |⌉),=0 =0где - минимальная допустимая длина дробной части коэффициента полиномиальной аппроксимации в одном сегменте.Доказательство. По теореме 1(︂)︂−2()(−),2 0‖ − ‖ ≤ ¯ + 2+¯ .8( − 2)!2( − )2Подставим значения ¯, − = 1, = , тогда ‖ − ‖ ≤ .Рассмотрим случай , ̸= 0, тогда , имеет не более , ненулевых бит., = 2 + ⌈ + log2 |, |⌉Дополнительная единица в оценке отвечает за хранение знака.Если , = 0, то для его хранения требуется 0 бит, при этом , = −∞.Сначала перебором найдем минимальный , для которого существует базовый план.
Затем задача решается методом целочисленного смешанного линейного программирования аналогично предыдущей.Для решения задачи стандартными методами требуется привести задачу кканоническому виду.Теорема 3 Оптимизационную задачу из теоремы 2 можно свести к эквивалентной задаче линейного программирования в каноническом виде.⎛⎞⎛⎞¯ 0¯ + ¯⎜ ¯⎟⎜ ¯⎟⎜⎟⎜⎟−0−+¯⎟,⎜⎟min ˆ,ˆ ≤ ,=⎜=⎟⎜⎜ ¯ ⎠0⎟⎝⎝⎠¯ −⎛0⎞0...⎜ 0 .⎟⎟,..¯ = ⎜00⎝⎠0 .
. . 20 −10−1, = {( + ¯ ) }2=0,=073⎛10−100...⎜...........⎜.⎜⎜ −1−1 −10...⎜ 1⎜..¯ =⎜....00⎜⎜⎜0. . . 200 −1 −200 −1⎜........⎜....⎝0. . . 2−1−2−10 −10 −1⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠ = () ( )¯ = ( (0 ), (0 + ¯1 ), . . . , (20 ))ˆ = (00 , . . . , 0 , 01 , . . . , 20 −1 , 1,0 , . . . , 1, −1 , 2,0 , . . . , 20 −1, −1 ) = (0, . .
. , 1,0 , . . . , 1, −1 , 2,0 , . . . , 20 −1, −1 )Здесь - матрицы Вандермонда на сегментах, ¯ - вектор значений в узлахна всех сегментах.Доказательство. Выполним подстановку⎧⎛⎞⎛⎞¯¯⎪0+¯⎪⎪⎪⎟⎜ ¯⎜ ¯⎟⎪⎪⎟⎜⎜⎟−0−+¯⎪⎨⎜⎟ ˆ ≤ ⎜⎟⎟⎜ ⎜¯ ⎠0⎟⎝⎝⎠⎪⎪⎪¯ ⎪−0⎪⎪⎪⎩ * = min ˆ^ После упрощения получим неравенства из теоремы 2.Таблицы коэффициентов для функции включают коэффициенты для каждого квазисплайна.Таблицы могут синтезироваться как фиксированная логика, тогда площадьпропорциональна количеству ненулевых бит в представлении коэффициентов.Также может использоваться ПЗУ, тогда для коэффициента выбирается максимальная ширина по всем квазисплайнам.Для функций с монотонными производными на части сегментов в начале или конце таблицы поправочные коэффициенты равны нулю, посколькуфункция растет медленнее, чем на остальных сегментах, ошибка не успевает накопиться и не требует поправки. При синтезе таблиц из фиксированной74логики это приводит к уменьшению площади таблиц на полупроводниковомкристалле, поэтому обнуление части коэффициентов в начале или конце таблицы влияет на ее размер.Таким образом, при расчёте размера таблиц использовалось произведениеширины коэффициентов в битах на количество ненулевых коэффициентов.Также если коэффициент для всех квазисплайнов имеет один знак, то знаковый бит не учитывался в ширине таблицы для этого коэффициента.Такой алгоритм аппроксимации является обобщением гладкого двузвенного сплайна, рассматривавшегося Стролло и др.
[3]. Использование болеедвух звеньев квазисплайна и ослабление требований гладкости позволяет существенно сократить размер таблиц. Например, переход к четырехзвенномуквазисплайну по сравнению с двузвенным дает сокращение таблиц на болеечем 30%.2.5Результаты прототипированияБыли построены таблицы для квадратичной аппроксимации функций√sin, ln, 1/, в интервале точностей 24-32 бит. Уменьшение размера таблицдля двузвенного квазисплайна составляет более 40%, для четырехзвенного —более 60%.
Данные для двузвенного квазисплайна соответствуют результатамСтролло и др. [3]Рис. 2.1: Архитектура блока интерполяции функцийБыло проведено прототипирование интерполяционного блока с задержкойв один такт на основе предложенного алгоритма и синтез виртуальной тополо75гии для малопотребляющего процесса производства полупроводниковых кристаллов с геометрическими нормами 22 нм. Архитектура блока изображена нарисунке 2.1. Таблицы из-за небольшого размера были синтезированы как комбинационная схема.
Сравнение различных вариантов реализации по площадипоказано в таблице 2.1 и по задержке - в таблице 2.2. Данные представленыв относительной форме, поскольку абсолютные данные являются коммерческой тайной фирмы. Данные для кубической интерполяции приведены длясравнения с коммерческой библиотекой DesignWare [73] фирмы Synopsys.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
