[alexkarnaukhov 0]

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

 

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

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

 

Спасибо.

[Lmx2315 2]

..я пользуюсь сдвигом вправо.

[Maverick_ 15]

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

 

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

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

 

Спасибо.

Вот например целочисленное деление не подходит?

Какая частота съема пикселей? Разрядность пикселей? Какая плис?

PS в крайнем случае можно сделать pipeline деление...

[des00 25]

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

собственно вот и ответ на ваш вопрос.

 

ЗЫ. деление в столбик будет делить точно, при конвейере будет 1 слово за такт. и для ваших 11 бит составит немногим больше 100 слайсов.

[alexkarnaukhov 0]

Вот например целочисленное деление не подходит?

Какая частота съема пикселей? Разрядность пикселей? Какая плис?

PS в крайнем случае можно сделать pipeline деление...

Частота - 50МГц, 14бит, плис - 7я серия xilinx. На данный момент для деления использую корку DividerGenerator в режиме Radix-2. Хавает более 2000 FF... pipeline нужен обязательно, а вот latency роли не играет, хоть 1000 тактов пойдет. Ваш алгоритм, насколько я понимаю, несколько тактов на деление требует? Я боюсь, что если его конвейеризировать, то слайсов будет прилично занимать...

И все-таки в аппроксимации меня привлекает то, что результат-то можно получать гораздо большей разрядности, чем наихудшую точность (ну как в АЦП - есть разрядность, а есть нелинейность и в плохом АЦП может быть 16 эффективных разрядов, но линейными могут быть только 14). Т.е. можно получить монотонную 16-битную функцию на выходе, у которой только первые 11 бит будут всегда точно соответствовать 1/х, что вполне может сгодиться. Делением в столбик такого не получишь...

[Maverick_ 15]

Частота - 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 бит данные, тогда еще больше экономии...

[_pv 52]

если в a/b делитель не так часто меняется, посчитайте как угодно медленно один раз с=(2^n)/b и потом множьте на него за такт и сдвигайте.

[alexkarnaukhov 0]

если в a/b делитель не так часто меняется, посчитайте как угодно медленно один раз с=(2^n)/b и потом множьте на него за такт и сдвигайте.

С нормировкой кадра такое прокатит, а вот когда множитель для каждого пикселя меняется (а такое тоже надо) - уже нет

[xvr 12]

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

Наверное потому, что x должно быть в пределах от 1 до 2х (в той же статье написано). Может не хватить диапазона.

 

 

[alexkarnaukhov 0]

Наверное потому, что x должно быть в пределах от 1 до 2х (в той же статье написано). Может не хватить диапазона.

 

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

[vladec 7]

Для вычисления 1/x есть еще итерационные алгоритмы, для них характерна очень быстрая сходимость, в том числе и на больших разрядностях

[Maverick_ 15]

Для вычисления 1/x есть еще итерационные алгоритмы, для них характерна очень быстрая сходимость, в том числе и на больших разрядностях

например? (хорошие по Вашему мнению - 32/64 бит)

[blackfin 16]

например? (хорошие по Вашему мнению - 32/64 бит)

Ну можно, наверное, методом Ньютона попробовать..

 

Главное - выбрать правильное начальное приближение.. ;)

 

Например, мы хотим найти частное от деления: A/B = D, где A = 555555, B = 11 и, соответственно, D = 50505.

 

Тогда:

 

A/B = [(A*2³²/B)>>32] = D.

 

Введем обозначение:

 

x = 2³²/B.

 

Это равносильно:

 

2³²/x = B.

 

Или:

 

f(x) == 2³²/x - B = 0.

 

Находим производную:

 

f'(x) = -2³²/x².

 

Теперь подставляем всё это в формулу Ньютона и находим:

 

x_n+1 = x_n - f(x_n)/f'(x_n), или

 

x_n+1 = x_n + [2³²/x_n - B]/[2³²/x_n²], или

 

x_n+1 = 2*x_n - B*x_n²/2³², или

 

x_n+1 = 2*x_n - [(B*x_n*x_n)>>32].

 

Начальное приближение для x₀ выбираем равным:

 

x₀ = 2^32-m, где m - максимальная степень двойки в двоичном представлении числа B..

 

То есть, для B = 11 это дает:

 

B = 11_d = 1011_b = 1*2³ + 0*2² + 1*2¹ + 1*2⁰.

 

Откуда находим, что m = 3, и:

 

x₀ = 2²⁹.

 

Тогда:

 

x₁ = 2³⁰ - 11*2²⁶ = 335544320;

 

x₂ = 2*335544320 - (11*335544320*335544320)>>32 = 382730240;

 

x₃ = 2*382730240 - (11*382730240*382730240)>>32 = 390298880;

 

x₄ = 2*390298880 - (11*390298880*390298880)>>32 = 390451513;

 

x₅ = 2*390451513 - (11*390451513*390451513)>>32 = 390451572;

 

x₆ = 2*390451572 - (11*390451572*390451572)>>32 = 390451572;

 

После чего находим:

 

A/B = [(A*x)>>32] = [(555555*390451572)>>32] = 50505 = D.

 

Но в целом, все эти "быстро сходящиеся итерации" не слишком то оптимальны для FPGA, КМК..

 

Как-то так..

 

[Maverick_ 15]

Ну можно, наверное, методом Ньютона попробовать..

 

Главное - выбрать правильное начальное приближение.. ;)

 

Например, мы хотим найти частное от деления: A/B = D, где A = 555555, B = 11 и, соответственно, D = 50505.

 

Тогда:

 

A/B = [(A*2³²/B)>>32] = D.

 

Введем обозначение:

 

x = 2³²/B.

 

Это равносильно:

 

2³²/x = B.

 

Или:

 

f(x) == 2³²/x - B = 0.

 

Находим производную:

 

f'(x) = -2³²/x².

 

Теперь подставляем всё это в формулу Ньютона и находим:

 

x_n+1 = x_n - f(x_n)/f'(x_n), или

 

x_n+1 = x_n + [2³²/x_n - B]/[2³²/x_n²], или

 

x_n+1 = 2*x_n - B*x_n²/2³², или

 

x_n+1 = 2*x_n - [(B*x_n*x_n)>>32].

 

Начальное приближение для x₀ выбираем равным:

 

x₀ = 2^32-m, где m - максимальная степень двойки в двоичном представлении числа B..

 

То есть, для B = 11 это дает:

 

B = 11_d = 1011_b = 1*2³ + 0*2² + 1*2¹ + 1*2⁰.

 

Откуда находим, что m = 3, и:

 

x₀ = 2²⁹.

 

Тогда:

 

x₁ = 2³⁰ - 11*2²⁶ = 335544320;

 

x₂ = 2*335544320 - (11*335544320*335544320)>>32 = 382730240;

 

x₃ = 2*382730240 - (11*382730240*382730240)>>32 = 390298880;

 

x₄ = 2*390298880 - (11*390298880*390298880)>>32 = 390451513;

 

x₅ = 2*390451513 - (11*390451513*390451513)>>32 = 390451572;

 

x₆ = 2*390451572 - (11*390451572*390451572)>>32 = 390451572;

 

После чего находим:

 

A/B = [(A*x)>>32] = [(555555*390451572)>>32] = 50505 = D.

 

Но в целом, все эти "быстро сходящиеся итерации" не слишком то оптимальны для FPGA, КМК..

 

Как-то так..

 

спасибо...

 

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

 

я думал, что есть уже какие-то модификации, которые лучше подходят для FPGA и менее итерационные...

[alexkarnaukhov 0]

Ну вообще Ньютон как раз может и быть интересен. По крайней мере в алгоритме быстрого вычисления обратного корня именно он и используется. Кстати интересно, есть ли готовые корки, реализующие быстрый инверсный корень?