СПОСОБ АДРЕСАЦИИ КОЛЬЦЕВОГО БУФЕРА В ПАМЯТИ МИКРОПРОЦЕССОРА
METHOD OF ADDRESSING A CIRCULAR BUFFER IN MICROPROCESSOR MEMORY

Изобретение относится к области выборки, адресации или распределению данных в системах или архитектурах памяти, а именно к адресации или местонахождению данных в памяти.
Во многих приложениях, например в вычислительных системах обработки информации с динамически изменяющимся темпом поступления данных, для промежуточного хранения данных широко используются кольцевые буферы.
В кольцевом буфере при чтении или записи данных осуществляется циклический возврат от конца буфера к его началу. При этом при нефиксированных размерах пакетов данных возникают ситуации, при которых пакет данных, к которому производится доступ, попадает на границы кольцевого буфера и для обработки разбивается на две части. Для исключения переполнения буфера или неправильной адресации считываемых данных возникает необходимость постоянно отслеживать границы и периодически производить коррекцию указателя данных, адресуемых в кольцевом буфере. Указанные операции в известных технических решениях зачастую выполняются программным путем с использованием ресурсов арифметико-логического устройства микропроцессора. При этом уменьшается быстродействие, отводимое на выполнение основной программы, и существенно усложняется обработка поступающих данных. Программа-обработчик в этом случае будет либо осуществлять обработку пакета по частям (в общем случае - переменной длины), либо потребуется дополнительный этап перезаписи частей пакета в область памяти, не связанную с кольцевым буфером, что также приводит к дополнительному расходованию вычислительных ресурсов и памяти, адресуемой микропроцессором.
При темпе поступления обрабатываемых данных, сопоставимом с быстродействием микропроцессора, экономия вычислительных ресурсов имеет существенное значение.
Для экономии ресурсов программе-обработчику необходимо обрабатывать однородные пакеты данных, при этом процесс обработки поддерживается аппаратными средствами, например при помощи систем прямого доступа к памяти.
Предлагаемое изобретение направлено на решение задачи повышения эффективности обработки пакетов данных переменной длины с использованием кольцевого буфера, а именно исключения дополнительных вычислительных операций микропроцессора, связанных с обработкой по частям неоднородных пакетов данных, попадающих на границу кольцевого буфера, организуемого в памяти, адресуемой микропроцессором, в чем заключается технический результат изобретения.
Решение поставленной задачи достигается при помощи такой адресации кольцевого буфера, размещенного в памяти микропроцессора, при которой адрес элемента кольцевого буфера с наименьшим местоположением является смежным с адресом элемента кольцевого буфера с наибольшим местоположением, т.е. элементов, расположенных в начале и конце области памяти, выделяемой под кольцевой буфер.
В результате при попадании пакета данных на границу кольцевого буфера первый будет адресоваться программой-обработчиком как однородный непрерывный блок памяти, в результате чего не требуются вычислительные операции и не затрачиваются дополнительные ресурсы микропроцессора, связанные с отслеживанием границ кольцевого буфера и обработкой по частям неоднородных пакетов данных, попадающих на границу кольцевого буфера, тем самым увеличивается общая производительность вычислительной системы.
Известны способ и система вычисления указателя для масштабируемого программируемого кольцевого буфера (патент РФ №2395835 от 20.10.2006 [1]), в одном из вариантов реализации содержащий этапы на которых: устанавливают длину упомянутого кольцевого буфера, причем упомянутая длина предназначена для ограничения адресуемого диапазона упомянутого кольцевого буфера; устанавливают начальный адрес для упомянутого кольцевого буфера; устанавливают конечный адрес для упомянутого кольцевого буфера; определяют местоположение текущего указателя для адреса в упомянутом кольцевом буфере, причем местоположение упомянутого текущего указателя находится между упомянутым начальным адресом и упомянутым конечным адресом; формируют базовую маску на основании значений начального и конечного адресов; инвертируют базовую маску для получения маски смещения; применяют операцию логического «И» для местоположения текущего указателя и маски смещения для получения базы указателя; применяют операцию логического И для местоположения текущего указателя и базовой маски для получения смещения указателя; определяют величину шага по индексу бит между упомянутым начальным адресом и упомянутым конечным адресом; получают сумму упомянутого смещения указателя и упомянутого шага по индексу; получают новое смещение указателя на основании мультиплексирования полученной суммы, а также длины кольцевого буфера; определяют местоположение нового указателя в упомянутом кольцевом буфере посредством логической операции ИЛИ базы указателя и нового смещения указателя.
В другом варианте реализации упомянутый способ дополнительно содержит этап, на котором устанавливают местоположение отрегулированного указателя в случае положительного шага по индексу: в случае, когда местоположение упомянутого нового указателя меньше, чем упомянутый конечный адрес, с помощью регулирования местоположения упомянутого отрегулированного указателя таким образом, что оно является местоположением нового указателя; и в случае, когда местоположение упомянутого нового указателя больше, чем упомянутый конечный адрес, с помощью регулирования упомянутого отрегулированного указателя с помощью вычитания упомянутой длины из местоположения упомянутого нового указателя.
В третьем варианте реализации упомянутый способ дополнительно содержит этап, на котором получают местоположение упомянутого отрегулированного указателя в случае положительного шага по индексу с помощью прибавления замаскированного адреса в качестве упомянутого текущего указателя к упомянутому положительному шагу по индексу в устройстве генерирования адреса и вычитания упомянутой длины из суммы в сумматоре арифметического логического устройства.
По схожести большинства признаков рассмотренный способ совместно с вариантами его реализации выбран в качестве прототипа.
Прототипу присущи следующие недостатки: способ прототипа применим только в случае, когда адресуемые пакеты данных не попадают на границы кольцевого буфера; не ставится и не решается задача адресации пакетов данных, попадающих на границы кольцевого буфера; вычисление адреса текущего указателя данных кольцевого буфера производится в арифметико-логическом устройстве микропроцессора, что имеет критическое значение при темпе поступления данных, сопоставимом с быстродействием микропроцессора.
Указанные недостатки преодолены в предлагаемом способе адресации кольцевого буфера в памяти микропроцессора, заключающемся в том, что в способ, содержащий этапы, присущие прототипу, на которых устанавливают длину упомянутого кольцевого буфера, причем упомянутая длина предназначена для ограничения адресуемого диапазона упомянутого кольцевого буфера, устанавливают начальный и конечный адреса для упомянутого кольцевого буфера в памяти микропроцессора, устанавливают начальное местоположение текущего указателя в памяти микропроцессора, устанавливают шаг по индексу в памяти микропроцессора, в арифметическом логическом устройстве микропроцессора определяют местоположение текущего указателя в памяти микропроцессора путем прибавления шага по индексу к начальному местоположению текущего указателя в памяти микропроцессора, дополнительно вводят новые признаки - указатель в кольцевом буфере и этапы - в устройстве генерирования адреса микропроцессора определяют местоположение указателя в кольцевом буфере так, что производят сравнение местоположения упомянутого текущего указателя в памяти микропроцессора с конечным адресом для упомянутого кольцевого буфера, и в случае, когда местоположение текущего указателя в памяти микропроцессора не превосходит конечного адреса упомянутого кольцевого буфера, устанавливают местоположение указателя в упомянутом кольцевом буфере, равным местоположению текущего указателя в памяти микропроцессора, и в случае, когда местоположение упомянутого текущего указателя в памяти микропроцессора больше, чем упомянутый конечный адрес кольцевого буфера, то устанавливают местоположение указателя в упомянутом кольцевом буфере путем вычитания упомянутой длины кольцевого буфера из местоположения упомянутого текущего указателя в памяти микропроцессора, причем начальный и конечный адреса для упомянутого кольцевого буфера в памяти микропроцессора являются постоянными, начальное местоположение указателя в кольцевом буфере соответствует начальному адресу для упомянутого кольцевого буфера в памяти микропроцессора.
Следовательно, предлагаемый способ удовлетворяет критерию «новизна».
Сравнение с другими техническими решениями показывает, что предлагаемый способ обладает признаками, позволяющими существенно снизить количество вычислительных операций арифметико-логического устройства микропроцессора, затрачиваемых на отслеживание границ кольцевого буфера и на обработку по частям неоднородных пакетов данных, попадающих на границу адресуемого кольцевого буфера, тем самым увеличить общую производительность вычислительной системы.
Изобретение поясняется следующими графическими материалами:
фиг. 1 - схема, поясняющая сущность предлагаемого способа адресации кольцевого буфера в памяти микропроцессора;
фиг. 2 - функциональная схема вычислительной системы, в которой реализуется предлагаемый способ адресации кольцевого буфера в памяти микропроцессора.
0
Способ адресации кольцевого буфера в памяти микропроцессора состоит в том, что на первом этапе устанавливают длину S (фиг. 1) упомянутого кольцевого буфера 1, причем упомянутая длина предназначена для ограничения адресуемого диапазона упомянутого кольцевого буфера 1, устанавливают начальный В и конечный (B+S-1) адреса для упомянутого кольцевого буфера 1 в памяти 2 микропроцессора, устанавливают начальное местоположение текущего указателя N в памяти 2 микропроцессора, устанавливают шаг по индексу D в памяти 2 микропроцессора, а также вводят указатель в кольцевом буфере N′, причем начальное местоположение указателя в кольцевом буфере 1 задается как N′=В.
0
0
На втором этапе в арифметическом логическом устройстве микропроцессора определяют местоположение текущего указателя N в памяти 2 микропроцессора путем прибавления шага по индексу D к начальному местоположению текущего указателя N в памяти 2 микропроцессора, так что N=N+D.
На третьем этапе в устройстве генерирования адреса микропроцессора определяют местоположение указателя N′  в кольцевом буфере 1 путем сравнения местоположения упомянутого текущего указателя N в памяти 2 микропроцессора с конечным адресом для упомянутого кольцевого буфера (B+S-1) и в случае, когда N≤В+S-1, устанавливают местоположение указателя в упомянутом кольцевом буфере N′=N. В случае, когда местоположение упомянутого текущего указателя в памяти 2 микропроцессора N>В+S-1, то устанавливают местоположение указателя в упомянутом кольцевом буфере N′=N-S. Начальный В и конечный (В+S-1) адреса для упомянутого кольцевого буфера 1 в памяти 2 микропроцессора являются постоянными.
Таким образом, начальный элемент в кольцевом буфере 1 концептуально, или логически, является смежным с конечным элементом кольцевого буфера, несмотря на то, что физически в памяти 2 микропроцессора они расположены на границах адресного пространства, выделенного под кольцевой буфер.
1
2
В результате кольцевой буфер 1 обладает двойной адресацией и занимает удвоенный диапазон логических адресов микропроцессора. Физически он расположен в области памяти 2, адресуемой микропроцессором, с начального адреса В до конечного адреса (В+S). В то же время начальный адрес кольцевого буфера 1 может быть доступен в памяти 2 микропроцессора по адресу N=В+S, в силу того, что при N=B+S, согласно изложенному алгоритму получаем: при N>B+S-1, N′=(В+S)-(S)=В, что совпадает с начальным адресом кольцевого буфера 1. Аналогично конечный адрес кольцевого буфера 1 может быть доступен в памяти 2 микропроцессора по адресу N=B+2S-1, в силу того, что при N=В+2S-1, согласно изложенному алгоритму получаем: при N>В+S-1, N′=(В+2S-1)-(S)=В+S-1, что совпадает с конечным адресом кольцевого буфера 1. Таким образом, упомянутый кольцевой буфер 1 также может быть доступен в памяти 2 микропроцессора в диапазоне адресов с (В+S) до (В+2S-1), а общая длина логического адресного пространства в памяти 2 микропроцессора, выделенного для адресации кольцевого буфера, равна (В+2S-1)-В+1=2S.
В результате пакет данных, попадающий на границу кольцевого буфера B+S-1 программой-обработчиком, функционирующей с использованием области логических адресов микропроцессора, может быть считан (записан) и обработан непрерывно.
Предлагаемый способ адресации кольцевого буфера в памяти 2 микропроцессора может быть реализован, например, в составе вычислительного устройства (фиг. 2), состоящего из микропроцессора 3, запоминающего устройства (памяти) 2, адресуемого микропроцессором, цифрового многоразрядного компаратора 4, цифрового многоразрядного вычитателя 5, многоразрядного мультиплексора 6, выводы шины данных микропроцессора 3 поразрядно соединены с соответствующими выводами данных запоминающего устройства 2, выход шины адреса микропроцессора 3 поразрядно соединен с входом для подачи данных цифрового многоразрядного компаратора 4, входом для подачи уменьшаемого цифрового многоразрядного вычитателя 5 и первым входом многоразрядного мультиплексора 6, выход цифрового многоразрядного компаратора 4 соединен с адресным входом многоразрядного мультиплексора 6, выход которого поразрядно соединен с соответствующим входом для подачи адреса запоминающего устройства 2, вход для подачи вычитаемого цифрового многоразрядного вычитателя 5 соединен с источником величины S, равной длине кольцевого буфера 1, вход для подачи опорной величины цифрового многоразрядного компаратора 4 соединен с источником величины В+S-1, а выход многоразрядного вычитателя 5 поразрядно соединен со вторым входом многоразрядного мультиплексора 6, причем на выходе цифрового многоразрядного компаратора 4 формируется сигнал логической "1", если многоразрядная величина на его входе для подачи данных не превосходит многоразрядного значения на его входе для подачи опорной величины, и сигнал логического "0" - в другом случае, если многоразрядный мультиплексор 6 передает на выход данные на его первом входе, когда сигнал на его входе для подачи адреса равен логической "1" и данные на его втором входе, когда сигнал на его входе для подачи адреса равен логическому "0", разрядности выводов: входа для подачи данных цифрового многоразрядного компаратора 4, входа для подачи уменьшаемого цифрового многоразрядного вычитателя 5, первого и второго входов многоразрядного мультиплексора 6, входа для подачи адреса запоминающего устройства 2, входа для подачи вычитаемого цифрового многоразрядного вычитателя 5, источника величины S, входа для подачи опорной величины цифрового многоразрядного компаратора 4, источника величины В+S-1, выхода многоразрядного вычитателя 5 равны между собой и равны разрядности выхода для подключения шины адреса микропроцессора 5, кольцевой буфер 1 размещен в запоминающем устройстве 2.
Вычислительное устройство функционирует следующим образом (фиг. 2).
При обращении к области памяти, содержащей кольцевой буфер 1, микропроцессор 3 на своем соответствующем выходе формирует адрес А, который одновременно поступает на вход для подачи данных цифрового многоразрядного компаратора 4, вход для подачи уменьшаемого цифрового многоразрядного вычитателя 5 и первый вход многоразрядного мультиплексора 6.
Многоразрядный цифровой компаратор производит сравнение адреса А с величиной, соответствующей границе кольцевого буфера В+S-1, подаваемой на его соответствующий вход. Если А<В+S-1, то на выходе многоразрядного цифрового компаратора формируется сигнал логической "1", который подается на адресный вход многоразрядного мультиплексора 6, который, в свою очередь, транслирует адрес А, присутствующий на его первом входе, на выход и далее - на вход для подачи адреса запоминающего устройства 2.
Запоминающее устройство 2 в соответствии с адресом А на входе на выводы данных выдает значение из кольцевого буфера, которое далее поступает на выводы шины данных микропроцессора 3. В этом случае микропроцессор работает с областью памяти А∈[B, В+S-1].
Если в многоразрядном цифровом компараторе не выполняется условие A≤B+S-1, то на его выходе формируется сигнал логический "0", который также подается на адресный вход многоразрядного мультиплексора 6, который, в свою очередь, транслирует величину A-S, формируемую на выходе многоразрядного вычитателя 5 и присутствующую на втором входе многоразрядного мультиплексора 6, на выход и далее - на вход для подачи адреса запоминающего устройства 2.
Запоминающее устройство 2 в соответствии с адресом A-S на входе, причем А>В+S-1, на выводы данных выдает значение из кольцевого буфера 1, которое далее поступает на выводы шины данных микропроцессора 3. В этом случае микропроцессор 3 работает с областью памяти A∈[B+S, В+2S-1]. Таким образом, кольцевой буфер 1 доступен в памяти 2 микропроцессора в диапазоне адресов с В до B+S- 1 и с В до B+S-1.
В результате пакет данных, попадающий на границу кольцевого буфера программой-обработчиком, функционирующей с использованием области логических адресов микропроцессора, может быть считан (записан) и обработан непрерывно; не расходуется производительность процессора на обработку по частям неоднородных пакетов данных, попадающих на границу адресуемого кольцевого буфера. Отслеживание границ кольцевого буфера в описанном вычислительном устройстве реализуется аппаратно, без привлечения ресурсов арифметико-логического устройства микропроцессора. В результате увеличивается общая производительность вычислительной системы.
Использованные источники
1. Патент РФ №2395835 от 20.10.2006 «Способ и система вычисления указателя для масштабируемого программируемого кольцевого буфера».