данный алгоритм на плис, из своего опыта подскажите на сколько быстро будет работать Опции

[toshas]

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

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

for( ; ; ) {
1. каждое число в массиве сдвигается на соседнее место M[i]->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]

N>1.000.000

только с использованием внешней памяти.
скорость вычисления одного среднего для k=1000 ~ 10мкс при частоте работы памяти ~ 100MHz, или ~ 5мкс для 32битной памяти.
Алгоритм можно и ускорить, если куски 0...k и M-k...M не очень большие и расположены во внутренней памяти.
В общем, скорость вычисления может быть и меньше...

[toshas]

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

[Gate]

Буду более оптимистичен, чем 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]

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


Можно еще проще - кольцевой буфер на N отсчетов
На каждом такте 2 чтения (M[N] и M[k]) и одна запись M[0].
Дальше также как и описал Gate. Вместо длинной операции деления использовать умножения на обратные величины. Итого - 3 такта на входной отсчет и задержка результата на 15 -20 тактов.

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

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

Успехов! Rob.

[toshas]

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