Как правильно в плис делить Опции

[sergey sva]

Как правильно в плис делить, очень медленная операция, на высокой частоте появляются слаки. Если сдвигом то можно поделить на 2 4 8 16.... а если нужно поделить на 9 или 5?

[Barktail]

Мне вот если делители известны заранее нравится умножать делимое на (2^n/делитель), а затем полученное число делить на 2^n. Можно даже составить таблицу соответствия делитель--множитель.

[Golikov A.]

Делить правильно делителем.
Видов делителей великое множество, надо реализовать один из них и все.

Самый простой реализует метод деления столбиком.
Делитель двигаете максимально вправо, сравниваете со старшей частью делимого, если оно больше 1 и вычитаете делитель, остаток сносите, если нет 0, и просто сносите остаток, сдвигаете делитель и так далее...

а можно так

Код

reg [15:0] A;
reg [15:0] B;
reg [15:0] C;

always...
C <= A/B;

и посмотреть вдруг то что придумает синтезатор вас устроит

[sergey sva]

Вариантов много, но нужно еще и быстрый.
То что синтезатор сделал по времени не проходит слаки появляются.

[dima32rus]

А что если задействовать аппаратный делитель? У Альтеры его можно конвейеризировать, устанавливая параметр pipeline. С Ксайлинксами не работал, но подозреваю, что там тоже есть что-то подобное. По идее, при увеличении ступеней максимальная частота тоже должна рости. Но это если Ваш алгоритм допускает конвейеризацию данных.

Вернее, не аппаратный, а библиотечный. Прошу прощения за неточность

[Maverick]

Как правильно в плис делить, очень медленная операция, на высокой частоте появляются слаки. Если сдвигом то можно поделить на 2 4 8 16.... а если нужно поделить на 9 или 5?

можете посмотреть это

[des00]

Вариантов много, но нужно еще и быстрый.
То что синтезатор сделал по времени не проходит слаки появляются.

берете деление столбиком и конвейризируете пока не надоест. я делал для сыклона 32 на 16 на 200МГц работает.

[sergey sva]

Сейчас попробую, у циклона 3 есть dsp, если их задействовать будет быстрее? квартус сам может их задействовать?

[Maverick]

Сейчас попробую, у циклона 3 есть dsp, если их задействовать будет быстрее? квартус сам может их задействовать?

зачем для реализации деления нужны умножители (DSP блоки)?

[sergey sva]

Если на нем сделать сдвиг, что бы сдвиг выполнился за один так. но это так мысли еще не подумал ).

[Maverick]

Если на нем сделать сдвиг, что бы сдвиг выполнился за один так. но это так мысли еще не подумал ).

а Вы не хотите для начала взять для начала за основу предложенный мной в сообщеннии 6 (через ссылку) реализацию/алгоритм?

[sergey sva]

Благодарю за информацию, ссылок много сейчас смотрю.

[Kuzmi4]

2 Maverick
я так понял, что человеку надо min latency и одновременно max FREQ, вы сделали всё что смогли

[sergey sva]

Да очень благодарен Maverick по ссылкам есть то что искал раньше.
Как оптимизировать что бы получить min latency max FREQ ?
Битовый сдвиг выполняется за одну операцию, или на каждый бит по такту?

[serjj]

И снова CORDIC
 cordic____.pdf ( 1.07 мегабайт ) Кол-во скачиваний: 199

стр 6 документа - умножение с накоплением и деление с накоплением, используются только сложения и сдвиги.

Преимущества
Можно получить fmax > 200 MHz при обработке потока порядка 32 бит и даже больше (конечный результат будет зависеть от ПЛИС)
Можно реализовать большим ресурсами так, что fs = fmax
При fs << fmax очень экономная корка, хотя обычный pipeline дулитель столбиком, про который упоминал des00 может занять меньше ресурсов

Недостатки
Latency = количество итераций * 1/fmax.
При fs = fmax получится довольно толстая корка

[Maverick]

быстрее алгритм Radix 4 division

CODE

#include <stdio.h>
#include <stdlib.h>

/* This code assumes that unsigned short is 16 bits, and unsigned int is 32 bits */

unsigned short radix4_division_u16(unsigned short divisor, unsigned short dividend)
{
unsigned short quotient = 0;
unsigned char i = 16; /* Number of bits to process */

if(dividend == 0)
{
printf("Divide by zero");
exit(0);
}

while(i > 0)
{
unsigned char j;
unsigned int d1,d2,d3;

i -= 2;

d1 = dividend << i;
d2 = dividend << (i+1);
d3 = d1+d2;

if(divisor < d1)
j = 0;
else if(divisor < d2) {
j = 1;
divisor -= d1;
} else if(divisor < d3) {
j = 2;
divisor -= d2;
} else {
j = 3;
divisor -= d3;
}
quotient = (quotient << 2)+j;
}
return quotient;
}

int main(int c, char *v[])
{
int i,j;
for(i = 0; i < 256*256; i++)
{
for(j = 1; j < 256*256; j++)
{
unsigned k = radix4_division_u16(i,j);
if(i/j != k)
{
printf("Error with %i/%i != %i\n",i,j,k);
exit(0);
}
}
if(i%650 == 0)
printf("%2.2f%% tested\n",i*100.0/256/256);
}
return 0;
}

алгоритм по шагам:

CODE

Each step

Inputs:

Existing quotient
Current dividend
Divisor
Clock signal
Bit offset of bits to generate

Constant (generic) information also needed:

Width of Divisor
Width of Quotient
Bit offset of bits to generate

Outputs:

updated quotient
updated dividend
Divisor

It is possible to reduce the length of comparisons - rather than comparing n2-2 bits only 4 bits need subtraction - the lowwer order bits can just be ORed together.

Equations for first step of a/b:

Comparing against divisor
x1 <= (0 & a(n-1 ... n-2)))
y1 <= (OR(b(n-1 ... 2)) & b(1 ... 0))
out1 <= (x-y)(1 ... 0) & a(n-3 ... 0)

Comparing against 2*divisor
x2 <= (0 & a(n-1))
y2 <= (OR(b(n-1 ... 1)) & b(0))
out2 <= (x-y)(0) & a(n-2 ... 0)

Comparing against 3*divisor
sum <= (0 & b(1 ... 0)) + (0 & b(0) & 0)
x3 <= (0 & a(n-1) & a(n-2))
y3 <= (OR(d(n-1 ... 1),sum(2)) & sum(1 ... 0))
out3 <= (x-y)(1 ... 0) & a(n-3 ... 0)

which 'out' is passed to the next stage is selected based on which of out1, out2 or out3 were positive (if any).

If you have n bits, you need 'n/2' stages, and if you number stages from (n/2-1) (dealing to the high bits) to 0 (dealing to bits 1 and 0) the equations become more generic:

For stage i (need to verify!):

Comparing against divisor
x1 <= (0 & a(n-1 ... 2i) )
y1 <= (OR(b(n-1 ... n-2i)) & b(n-2i ... 0))
out1 <= (x-y)(n/2-i-1 ... 0) & a(2i-1 ... 0)

Comparing against 2*divisor
x2 <= (0 & a(n-1 ... 2i+1) )
y2 <= (OR(b(n-1 ... n-2i+1)) & b(0))
out2 <= (x-y)(n/2-2i-2..0) & a(2i-1 ... 0)

Comparing against 3*divisor
sum <= (0 & b(n-2i-1 .. 0)) + (0 & b(n-2i-2 ... 0) & 0)
x3 <= (0 & a(n-1 ... 2i))
y3 <= (OR(d(n-1 ... n-2i),sum(2)) & sum(1 ... 0))
out3 <= (x-y)(n/2-i-1 ... 0) & a(2i-1 ... 0)

PS насчет скорости и кол-во ресурсов не знаю не реализовывал, но вроде считает раза в 2 быстрее (если не изменяет память) предложенного ранее реализации

PS PS есть Radix более высокого прядка , например Radix8

PS PS PS алгоритмы деления на константу - рекомендую к просмотру

[Fat Robot]

Метод Ньютона-Рафсона и его реализация: Goldschmidt division

The Goldschmidt method is used in AMD Athlon CPUs and later models.

[likeasm]

зачем для реализации деления нужны умножители (DSP блоки)?

Можно умножить делимое на число обратное делителю. c=a\b или c=a*(1\b). Алгоритм Кнута кажется.

[Kuzmi4]

Можно умножить делимое на число обратное делителю...

там выше 8-10 бит на средних С3 это дело просто нет смысла делать.. А довольно часто надо больше бит..

[D Mike]

если делимое не более 12 разрядов, делитель=константа и нужно после деления получить целое + остаток, то можно воспользоваться умножением + сдвиг.
например деление переменной(0..1512) на 35 сводится к умножению на 117 и сдвигу на 11. Работает очень быстро

[Golikov A.]

да правда быстро, особенно если знаешь сколько будет разделить 2^12 на 35....
любое деление можно свести к умножению на обратное число, так что в вашем случае деление на 35 сводиться к умножению на 1/35, и это так же быстро, потому что тоже самое

и да сдвигать надо на 12, а не 11,