аппроксимация деления, почему не используется Опции

[alexkarnaukhov]

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

Почему никто не использует тупо полиномиальную аппроксимацию 1/х? Вот здесь всего навсего полином 3-й степени, 100 слайсов на 3-ем Спартане и при этом точность 11 бит. Мне так кажется, что я здесь что-то не понимаю, это же так просто, почему так не делают?
Еще и конкретно для моей задачи - даже при точности 11 бит, я мог бы получить приемлемый результат, забив на линейность нормировки.

Спасибо.

[Maverick]

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

Почему никто не использует тупо полиномиальную аппроксимацию 1/х? Вот здесь всего навсего полином 3-й степени, 100 слайсов на 3-ем Спартане и при этом точность 11 бит. Мне так кажется, что я здесь что-то не понимаю, это же так просто, почему так не делают?
Еще и конкретно для моей задачи - даже при точности 11 бит, я мог бы получить приемлемый результат, забив на линейность нормировки.

Спасибо.

Вот например целочисленное деление не подходит?
Какая частота съема пикселей? Разрядность пикселей? Какая плис?
PS в крайнем случае можно сделать pipeline деление...

[alexkarnaukhov]

Вот например целочисленное деление не подходит?
Какая частота съема пикселей? Разрядность пикселей? Какая плис?
PS в крайнем случае можно сделать pipeline деление...

Частота - 50МГц, 14бит, плис - 7я серия xilinx. На данный момент для деления использую корку DividerGenerator в режиме Radix-2. Хавает более 2000 FF... pipeline нужен обязательно, а вот latency роли не играет, хоть 1000 тактов пойдет. Ваш алгоритм, насколько я понимаю, несколько тактов на деление требует? Я боюсь, что если его конвейеризировать, то слайсов будет прилично занимать...
И все-таки в аппроксимации меня привлекает то, что результат-то можно получать гораздо большей разрядности, чем наихудшую точность (ну как в АЦП - есть разрядность, а есть нелинейность и в плохом АЦП может быть 16 эффективных разрядов, но линейными могут быть только 14). Т.е. можно получить монотонную 16-битную функцию на выходе, у которой только первые 11 бит будут всегда точно соответствовать 1/х, что вполне может сгодиться. Делением в столбик такого не получишь...

[Maverick]

Частота - 50МГц, 14бит, плис - 7я серия xilinx. На данный момент для деления использую корку DividerGenerator в режиме Radix-2. Хавает более 2000 FF... pipeline нужен обязательно, а вот latency роли не играет, хоть 1000 тактов пойдет. Ваш алгоритм, насколько я понимаю, несколько тактов на деление требует? Я боюсь, что если его конвейеризировать, то слайсов будет прилично занимать...
И все-таки в аппроксимации меня привлекает то, что результат-то можно получать гораздо большей разрядности, чем наихудшую точность (ну как в АЦП - есть разрядность, а есть нелинейность и в плохом АЦП может быть 16 эффективных разрядов, но линейными могут быть только 14). Т.е. можно получить монотонную 16-битную функцию на выходе, у которой только первые 11 бит будут всегда точно соответствовать 1/х, что вполне может сгодиться. Делением в столбик такого не получишь...

думаю будет меньше чем 2000 FF

upd

для 16 битных данных

Flow Status Successful - Thu May 14 14:49:58 2015
Quartus II 64-Bit Version 13.0.1 Build 232 06/12/2013 SP 1 SJ Full Version
Family Stratix IV
Logic utilization < 1 %
Combinational ALUTs 46 / 58,080 ( < 1 % )
Memory ALUTs 0 / 29,040 ( 0 % )
Dedicated logic registers 85 / 58,080 ( < 1 % )
Total registers 85
Total pins 67 / 584 ( 11 % )
Device EP4SGX70HF35C2
Timing Models Final

таймквет показывает частоту выше 300 МГц

Как вариант можно блок деления запустить на частоте эдак 300МГц.

300МГц/50МГц = 6

Ставим 3 (с запасом) модуля и переиспользуем ресурсы.
Таким образом, Вы получаете на 3 модулях pipeline на 3*6=18 тактов
Минимизация ресурсов налицо за счет временного мультиплексирования и переиспользования ресурса (модуля деления)...
------------------------------------------------------------------------------------------------------------------------------------------------------------
Даже если просто (для работы на одной тактовой частоте 50МГц)
85 регистров *16 = 1 360
то и здесь получается экономия

только что увидел у Вас не 16 бит а 14 бит данные, тогда еще больше экономии...