Кольцевые буферы

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

- процесс вычислений одноразовый;

- вся входная информация уже имеется и хранится, например, в виде файла;

- практически отсутствуют требования на "время отклика системы", т.е. время выполнения того или иного действия программой может меняться от раза к разу и зависит от таких внешних для нее факторов, как, например, количество выполняемых в системе задач, загруженность процесора, объем доступной оперативной памяти, и частота обращения к странице виртуальной памяти, которой нет в данный момент в физическом ОЗУ и др.

В системе ЦОС обработка очередного отсчета (группы отсчетов) сигнала и переход к обработке следующего отсчета (группе отсчетов) должны происходить строго в соответствии с частотой дискретизации сигнала (периодом между поступлением отсчетов на входной порт процессора). Это значит, что несмотря на то, что какой-то отсчет или группа отсчетов в силу своих параметров и особенностей алгоритма может быть обработана быстрее (например, после проверки какого-либо условия выполнение алгоритма идет по "сокращенной" ветке вычислений), следующий отсчет должен быть "затребован" (прочитан из входного порта) не раньше ожидаемого времени его поступления во входной порт. То же самое можно сказать и о выводе сформированных/обработанных значений в выходной порт. Таким образом, систему ЦОС можно охарактеризовать как систему, выполняющую однотипные вычислительные операции над данными в "потоковом режиме", причем обработка каждого отсчета или группы отсчетов выполняется практически за один и то же интервал времени[6].

В большинстве приложений ЦОС обрабатываемый сигнал рассматривается как бесконечно продолжающийся во времени. Поэтому хранение такого сигнала в вычислительном устройстве, имеющем ограниченный размер памяти в принципе невозможно. К счастью, практически всегда для реализации алгоритма обработки сигнала достаточно иметь какое-то определенное количество последних входных отсчетов (например, нерекурсивный фильтр), а использование информации о предыстории обработки может храниться опосредованно (например, рекурсивный фильтр).

Как нельзя лучше для хранения последних отсчетов сигнала подходит такая структура данных, как кольцевой буфер, поддерживаемый аппаратными возможностями всех современных DSP-процессоров. Он позволяет эффективно организовать (рис.___):

- обновление буфера, при этом последний записываемый в буфер отсчет X(i) "затирает" отсчет X(i-N) (для буфера длиной N) и в буфере остаются N последних отсчетов;

- последовательное считывание последних N отсчетов в случае, если указатель на начало буфера (для чтения) Index_Read имеет значение на 1 больше, чем указатель на последний помещенный в буфер элемент Index_New. За счет кругового перемещения указателя Index_Read в цикле чтения буфера, первым прочитанным элементам будет самый "старый" из последних N отсчетов, а последним - только поступивший отсчет. Такой подход используется, если чтение элементов буфера необходимо выполнить в порядке их поступления, т.е. X(i-N+1), X(i-N+2),...,X(i). Реализовать вариант, когда чтение должно выполняться в порядке обратном поступлению отсчетов, т.е. от нового элемента к самому старому, также не составляет труда.

Рис.___. Варианты размещения указателей Index_New, Index_Read

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