Как сдвинуть все элементы массива на 1, Оптимизация этого процесса Опции

[azh]

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

Кто-нибудь знает как можно оптимизировать сдвиг элементов массива на 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 память-память?

[rezident]

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

[dxp]

Кто-нибудь знает как можно оптимизировать сдвиг элементов массива на 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). Не уверен только, что требуемого результата можно добиться на ЯВУ, скорее всего придется реализовывать на асме.

[fontp]

В этом процессоре (как и в любом приличном 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

[dtsar]

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

Кто-нибудь знает как можно оптимизировать сдвиг элементов массива на 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 память-память?

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

[azh]

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

В 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;
}
--------------------------------------------------

[rezident]

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

Код

short GetBufVal(short *pBuffer, unsigned idx, unsigned nSize)
{ if (idx<nSize) return(*(short *)(pBuffer+idx));
  else return(*(short *)(pBuffer+(nSize-idx)));
}

[shasik]

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

Код

short GetBufVal(short *pBuffer, unsigned idx, unsigned nSize)
{ if (idx<nSize) return(*(short *)(pBuffer+idx));
  else return(*(short *)(pBuffer+(nSize-idx)));
}

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

[fontp]

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

В 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;
}


--------------------------------------------------

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

Для примера - 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

[azh]

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

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

[fontp]

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

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

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

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

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

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

[azh]

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

[vadkudr]

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

[Николай Z]

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

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

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

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

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

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

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

[dxp]

Вы видимо ярый ненавистник ЯВУ...

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

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

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

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

[Николай Z]

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

Да не нужны Вы мне ни для какой дискусии - это просто попутное замечание по сути сказанного Вами...
Не обольщайтесь...

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

[Edmundo]

Да не нужны Вы мне ни для какой дискусии - это просто попутное замечание по сути сказанного Вами...
Не обольщайтесь...

[Грубый пост-новогодний OFF]
Уважаемый Николай Z! Вы хотя бы в раздел про ЦОС не лезьте. Для вас есть Off topics, резвитесь там!

[fontp]

Если речь идёт о скользящем ДПФ для немногих гармоник, то можно использовать идею, лежащую в основе фильтрации скользящего среднего CIC фильтрами. А именно, целочисленное скользящее среднее величины X вычисляется рекуррентно как

S(n) = S(n-1) + X(n) - X(n-M), M длина блока усреднения

Вычисления на границе устойчивости (для действительных чисел могут быть проблемы медленной потери устойчивости), но для целых чисел источник вычислительного шума отсутствует и вычисления абсолютно точные. Выкидываем уходящий отсчёт, добавляем входящий... имеем скользящую оценку среднего.

Далее для ДПФ заданной частоты - делаем два скользящих средних для целочисленных значений X(n)*sin(w*n) и X(n)*cos(w*n). Sin и Сos табличные и результаты умножений сохраняем в целочисленные линии задержки (лучше циклически адресуемые) для последующих рекуррентных вычислений. Получится скользящий ДПФ с точностью до комплексного фазового множителя (который при желании тоже можно учесть, но в большинстве случаев нас он не интересует, а интересует нас энергия) вычислительная сложность которого всего немногим более чем в 2 раза сложнее прямого блочного ДПФ или Герцеля. Это фатастика :-)
Кто с ними сталкивался, узнает в этом сразу типа DDC, используемый для вычислений точных значений отсчётов ДПФ

[alexander55]

S(n) = S(n-1) + X(n) - X(n-M), M длина блока усреднения

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

[Guest_TSerg_*]

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

Кольцевой буфер как раз дает требуемую функциональность.
Замените "принять" новый и "вытолкнуть" старый элемент на "перезаписать старый новым и сместить указатель на новый" и все станет вполне очевидным.

[Николай Z]

Кольцевой буфер как раз дает требуемую функциональность.
Замените "принять" новый и "вытолкнуть" старый элемент на "перезаписать старый новым и сместить указатель на новый" и все станет вполне очевидным.

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

Сообщение отредактировал Николай Z - Jan 14 2008, 13:55