Здравствуйте!

Кто-нибудь знает как можно оптимизировать сдвиг элементов массива на 1 (для Blackfin):
-------------------------------------------------------------------
void AddSample(short pBuffer[], short sValue, int nSize)
{
int i;
for (i = 1; i < nSize; i++)
{
pBuffer[nSize - i] = pBuffer[nSize - i - 1];
}
pBuffer[0] = sValue;
}
--------------------------------------------------------------------
Как-нибудь можно для этого использовать кольцевые буфферы или DMA память-память?

А может проще ничего не двигать, а лишь модифицировать указатель при обращении к массиву?

В этом процессоре (как и в любом приличном DSP) есть аппаратная поддержка кольцевых буферов, где требуемая функциональность реализуется аппаратно. Фтыкать доку на тему DAGs (Data Address Generators). Не уверен только, что требуемого результата можно добиться на ЯВУ, скорее всего придется реализовывать на асме.

На С можно, используя библиотечную ф-ю circptr. Цитата и хелпа VDSP++ :

The following operation performs a circular buffer increment of a pointer.

void *circptr(void *ptr, long incr ,
void * base, unsigned long buflen);

Both incr and buflen are specified in bytes, since the operation deals in void pointers.

The operation is equivalent to:

ptr += incr;

if (ptr < base)

ptr += buflen;

else if (ptr >= (base+buflen))

ptr -= buflen;

An example of this built-in function is:

#include <ccblkfn.h>

void func(int *array, int n, int incr, int len)

{

int i, idx = 0;

int *ptr = array;


// scale increment and length by size

// of item pointed to.

incr *= sizeof(*ptr);

len *= sizeof(*ptr);


for (i = 0; i < n; i++) {

*ptr += incr;

ptr = circptr(ptr, incr, array, len);

}

}





--------------------------------------------------------------------------------
VisualDSP++ 5.0 C/C++
Compiler and Library Manual
for Blackfin Processors
Revision 5.0, August 2007

не совсем понятно для чего так делать.
я думаю что проще всего - ничего не сдвигать, а написатьчтение из массива на асме с кольцевым буфером.
дма тут - изврат. хотя, смотря сколько данных.

Спасибо за ответы!

В help к VDSP++ написано, что можно использовать функцию circindex(), чтобы компилятор "сказал", что этот массив нужно поместить в кольцевой буффер, но как выяснилось такой код работает в почти в 1,5 раза медленнее, чем представленный ранее. С чем это может быть связано?
Ниже приведен код с функцией circindex().
--------------------------------------------------
void AddSampleA(short pBuffer[], short sValue, int nSize)
{
int i;
short nIndex = 0;

for (i = 0; i < nSize; i++)
{
pBuffer[nSize - nIndex] = pBuffer[nSize - nIndex - 1];
nIndex = circindex(nIndex, 1, FFT_SIZE);
}
pBuffer[0] = sValue;
}
--------------------------------------------------

А зачем вообще нужно сдвигать буфер? Почему нельзя его оставить как есть и для извлечения значений буфера ограничится всего лишь вызовом подобной функции?

Абсолютно согласен. Использовать "навороченные" программы для данной задачи явно лишнее. Лучше работать с указателями. Пусть N - длина массива, begin - его начало, тогда элемент будем брать по адресу (i+begin) mod N, т.е. то же что предложил rezident. Просто если длина массива является степенью двойки, то алгоритм rezident'а можно оптимизировать - использовать операцию логического &. Все работает шустро и очень даже красиво. Думаю понятно, что в этом случае сдвиг масиива на k элементов выглядит как begin += k.

Вообще-то линии задержки (для фильтрации и прочее) строятся не так. Никакого цикла для сдвига не должно быть. Положение последнего отсчёта в кольцевом буфере сдвигается при каждом обращении к "функции" и этот указатель возвращается (на самом деле для эффективности никакой функции не должно быть или она должна быть как минимум за-инлайнена). Вам не нужно сдвигать весь буфер в памяти, вместо этого сдвигается адрес начала (последнего во времени отсчёта) буфера

Для примера - fir фильтр делается как-то так

int16 BufBase[N];
int16 *BufPtr=BufBase;
static int16 FIR(int16 *H, int16 *BufBase, int N)
{
int i;
register int16 *bp = BufPtr;
register int16 *hp = H;
register int32 sumFIR;

sumFIR = 0;
for (i = 0; i < N; i++) {
sumFIR = L_mac(sumFIR,*bp,*hp++);
bp= (int16 *) circptr(bp, +2, BufBase, 2*N);
}
sumFIR = sature(sumFIR >> 16);
BufPtr = bp;
return sumFIR;
}


По циклу входных данных выполняется

*BufPtr = DataIn;
BufPtr=circptr(BufPtr, +2, BufBase, 2*N);
DataOut=FIR(H, BufBase, N);

Здесь нет двойного цикла, связанного со сдвигом буфера задержки. Единственный цикл выполняет фильтрацию. Аналогично и с circindex

Кроме того должна быть включена оптимизация, иначе кольцевые буферы не используются функциями circindex и circptr

На самом деле, сдвиг всех элементов массива это только часть задачи (извиняюсь, что не сказал об этом сразу). Вся задача выглядит так:
1. Добавить очередной отчет с АЦП в буффер (на место первого элемента буффера, при этом все остальные элементы сдвинуть на 1, и последний "вытолкнуть" из буффера)
2. Посчитать ДПФ для этого буффера

Относительно оптимизации, почему-то время выполнения остается тем же самым (+0.01%), даже если использовать функцию circptr() и включить оптимизацию.

Ещё раз, у Вас неверная парадигма. Т.е. Вы смотрите на сдвиг с неверной стороны.

Правильная парадигма состоит в том, что Вы не двигаете отсчёты в памяти, а двигете их в мозгу.
При этом, с точки зрения последующей обработки (ДПФ), буфер не начинается с первого элемента массива, а начинается с некоторого, смещающегося на 1 на каждом такте обработки. Буфер для последующей обработки тогда должен иметь кольцевую адресацию. Но за то Вы не тратите время на сдвиг

Для эффективной реализации этой парадигмы и существуют кольцевые буфера. ДПФ ничего не меняет, если Вы его реализуете сами.

Если же у Вас блочная процедура ДПФ готовая, например из стандартной библиотеки, то кольцевые буфера Вам не помогут - там (в чужой библиотечной процедуре) не реализована кольцевая адресация. Кроме того, если у Вас ДПФ не для одной частоты, то время сдвига всё равно очень мало по сравнению с временем выполнения ДПФ и можно делать тупо в лоб, сдвигая элементы в памяти. Но в этом случае никакие кольцевые буфера Вам не помогут

Большое спасибо за разъяснения! Действительно, мне сначала следовало разобраться для чего нужны кольцевые буфферы

Осталось добавить, что ДПФ сдвинутой по кольцу последовательности равен ДПФ несдвинутой умноженной на exp(-j*2*pi/N*n*k)
k - пробегает 0..N-1
n - величина сдвига
N - длина последовательности
:-)

Вы видимо ярый ненавистник ЯВУ...
На самом деле все что можно написать на ассемблере - можно написать и на любом ЯВУ причем совершенно необязательно с потерей эффективности, но зато намного структурнее и понятнее.



Вы незаметили что у товарища вовсе не сдвиг по кольцу,
а вот что:

и после каждого сдвига и добавления вся последовательность изменяется.

Сообщение отредактировал Николай Z - Jan 5 2008, 08:35

Сия фраза ясно указывает, что либо: 1) вы ничего про меня не знаете; 2) вы просто провокатор. Второе с вероятностью 0.99. Впрочем, все уже знают, что это у вас работа такая. Меня зацепить не удастся, т.ч. направляйте усилия на более наивных участников.


Написана очевидная глупость. На самом деле на некоторых ЯВУ (как правило С/C++) можно иногда написать без потери эффективности по сравнению с асмом, но достигается это в подавляющем большинстве случаев за счет специальных непереносимых расширений конкретного ЯВУ в части конкретной платформы. Могу с легостью привести пример для того же Blackfin'а, где асм даст преимущество ЯВУ, но не буду этого делать - вступать в спор с виртуалами куда бОльшая глупость, нежели вышеотквоченная фраза. Т.ч. цепляйте кого-нить другого. счастливо оставаться.

P.S. Можете и дальше (это уже второй случай) искать мои старые посты и пытаться меня вытащить на дискуссию, но сразу предупреждаю, этого вам не удастся. Меняйте тактику.