[toshas 0]

Добрый день!

хотелось бы сделать на них следующее:

 

массив из N 16битных чисел и константа D0

 

for( ; ; ) {

1. каждое число в массиве сдвигается на соседнее место M->M[i+1], M[N] при этом теряется, M[0] освобождается

2. записать извне (spi или паралл.) новое число на место M[0]

3. взять среднее от k чисел M[0],....,M[k] (M1) и M[N-k],.....,M[N] (M2)

4. вычислить (M2-M1)/(N-k)=D

5. сравнить D и D0

}

 

какова максимально возможная скорость реализации этого алгоритма ?

(так сказать вообще и на микросхемах стоимостью менее 100у.е.)

на сколько большими могут быть заданы числа N и k (хотелось бы N>1.000.000 k>1000)?

 

спасибо!

[vetal 0]

N>1.000.000

только с использованием внешней памяти.

скорость вычисления одного среднего для k=1000 ~ 10мкс при частоте работы памяти ~ 100MHz, или ~ 5мкс для 32битной памяти.

Алгоритм можно и ускорить, если куски 0...k и M-k...M не очень большие и расположены во внутренней памяти.

В общем, скорость вычисления может быть и меньше...

[toshas 0]

спасибо,

думал будет быстрее, придется видимо использовать только сравнение средним с константой и отказаться от приозводной (

[Gate 0]

Буду более оптимистичен, чем vetal.

чтобы посчитать сумму (что тоже самое, что и среднее) последовательно поступающих чисел, нет необходимости каждый раз суммировать весь массив, а можно на каждом такте считать новую сумму из предыдущей:

S(i) = S(i-1) + M[0] - M[N]

Т.о. надо иметь три очереди M[0]...M[k], M[k+1]...M[N-k-1], M[N-k]...M[N], с каждой очередью надо делать 2 операции - читать и записать, если вычисление средних, вычитание и сравнение сделать конвеером, то это 6 тактов. Очень похоже, что 1 и 3 можно хранить во внутренней памяти (если k ~ 1000-2000), тогда быстрее.

[RobFPGA 35]

Приветствую!

 

 

Можно еще проще - кольцевой буфер на N отсчетов

На каждом такте 2 чтения (M[N] и M[k]) и одна запись M[0].

Дальше также как и описал Gate. Вместо длинной операции деления использовать умножения на обратные величины. Итого - 3 такта на входной отсчет и задержка результата на 15 -20 тактов.

 

При грубом прикиде на Spartan3 (30$) с внешней статической памятью (200 MHz) можно обрабатывать входные отсчеты с чатотой ~60 MHz. Можно и больше если оптимизировать работу с памятью.

 

Правда это при условии что коэффициенты k,N в процессе работы алгоритма не изменяются.

 

Успехов! Rob.

[toshas 0]

спасибо, будем пробовать