Dynamically resizable circular buffers

Patent metadata

Field	Value
Publication number	US-9824003-B2
Application number	US-201313964257-A
Country	US
Kind code	B2
Filing date	Aug 12, 2013
Priority date	Sep 12, 2012
Publication date	Nov 21, 2017
Grant date	Nov 21, 2017

Abstract

Methods and apparatus for dynamically resizing circular buffers are described wherein circular buffers are dynamically allocated arrays from a pool of arrays. The method comprises receiving either a request to add data to a circular buffer or to remove data from a circular buffer. If the request is an addition request and the circular buffer is full, an array from the pool is allocated to the circular buffer. If, however, the request is a removal request and removal of the data creates an empty array, an array is de-allocated from the circular buffer and returned to the pool. Any arrays that are not allocated to a circular buffer may be disabled to conserve power.

First claim

The invention claimed is:

1. A circular buffer structure comprising:
a plurality of arrays, wherein each array comprises at least two storage elements configured to store data;
one or more circular buffers; and
buffer control logic configured to:
receive at least one of (a) a request to add data to a particular circular buffer and (b) a request to remove data from a specific circular buffer;
if a request to add data to a particular circular buffer is received when the particular circular buffer is full, dynamically allocate an array to the particular circular buffer and add the new data to the dynamically allocated array; and
if a request to remove data from a specific circular buffer is received and removal of the data from the specific circular buffer creates an empty array, dynamically de-allocate the empty array from the specific circular buffer and disable the de-allocated array;

wherein the buffer control logic is configured to:
only dynamically allocate an array to the particular circular buffer if a number of arrays already allocated to the particular circular buffer is not equal to or greater than a maximum threshold,
increase the maximum threshold when the buffer control logic detects a situation in which speed is more important than power conservation, and
decrease the maximum threshold when the buffer control logic detects a situation in which power conservation is more important than speed.

2. The circular buffer structure according to claim 1 , wherein the circular buffer structure comprises a plurality of circular buffers and the plurality of arrays are shared between the plurality of circular buffers.

3. The circular buffer structure according to claim 1 , wherein each of the arrays comprise the same number of storage elements.

4. The circular buffer structure according to claim 1 , wherein at least two of the arrays comprise a different number of storage elements.

5. The circular buffer structure according to claim 4 , wherein:
each circular buffer comprises a tail element and a head element; and
the buffer control logic is further configured to select the array to be allocated to the particular circular buffer based on how quickly the tail element is catching up with the end of the array in which it is situated.

6. The circular buffer structure according to claim 5 , wherein the buffer control logic is configured to select an array with a larger number of storage elements when the tail element is catching up quickly with the end of the array and to select an array with a smaller number of storage elements when the tail element is catching up slowly with the end of the array.

7. The circular buffer structure according to claim 1 , wherein the maximum threshold is expressed as a percentage of the plurality of arrays.

8. The circular buffer structure according to claim 1 , wherein at least two of the circular buffers have different maximum thresholds.

9. The circular buffer structure according to claim 1 , wherein the buffer control logic is configured to only de-allocate an array from the specific circular buffer if the number of arrays allocated to the specific circular buffer is greater than a minimum threshold.

10. The circular buffer structure according to claim 9 , wherein at least two of the circular buffers have different minimum thresholds.

11. The circular buffer structure according to claim 1 , wherein disabling the de-allocated array comprises turning off the power to each storage element of the array.

12. The circular buffer structure according to claim 1 , wherein each storage element can be read from.

13. A processor comprising the circular buffer structure according to claim 1 .

14. The processor according to claim 13 , wherein the processor is an out-of-order processor and the one or more circular buffers comprise at least one of a re-order buffer and a reservation station.

15. A method of dynamically resizing one or more circular buffers in a processor, the method comprising:
providing a plurality of arrays, each array comprising at least two storage elements configured to store data;
receiving at buffer control logic at least one of (a) a request to add new data to a particular circular buffer and (b) a request to remove data from a specific circular buffer;
if a request to add new data to a particular circular buffer is received when the particular circular buffer is full, dynamically allocating using the buffer control logic an array to the particular circular buffer and adding the new data to the dynamically allocated array; and
if a request to remove data from a specific circular buffer is received and removal of the data from the specific circular buffer creates an empty array, dynamically de-allocating using the buffer control logic the empty array from the specific circular buffer and disabling the de-allocated array;
wherein an array is only dynamically allocated to the particular circular buffer if a number of arrays already allocated to the particular circular buffer is not equal to or greater than a dynamically determined maximum threshold;
the method further comprising using the buffer control logic to:
increase the maximum threshold when the buffer control logic detects a situation in which speed is more important than power conservation, and
decrease the maximum threshold when the buffer control logic detects a situation in which power conservation is more important than speed.

16. A non-transitory computer readable storage medium having encoded thereon computer readable program code for generating a processor configured to:
provide a plurality of arrays, each array comprising at least two storage elements configured to store data;
receive at buffer control logic at least one of (a) a request to add new data to a particular circular buffer and (b) a request to remove data from a specific circular buffer;
if a request to add new data is received at the buffer control logic when the particular circular buffer is full, dynamically allocate using the buffer control logic an array to the particular circular buffer and add the new data to the dynamically allocated array; and
if a request to remove data for a specific circular buffer is received at the buffer control logic and removal of the data from the specific circular buffer creates an empty array, dynamically de-allocate using the buffer control logic an array from the specific circular buffer and disable the de-allocated array;
wherein an array is only dynamically allocated to the particular circular buffer if a number of arrays already allocated to the particular circular buffer is not equal to or greater than a dynamically determined maximum threshold; and
the processor is further configured to use the buffer control logic to:
increase the maximum threshold when the buffer control logic detects a situation in which speed is more important than power conservation, and
decrease the maximum threshold when the buffer control logic detects a situation in which power conservation is more important than speed.

Assignees

• Imagination Tech Ltd

Inventors

• Sanders Daniel
• Jackson Hugh

Classifications

• G06F5/10 Primary

  having a sequence of storage locations each being individually accessible for both enqueue and dequeue operations, e.g. using random access memory {(G06F5/065 takes precedence)} · CPC title

• G06F2205/063

  Dynamically variable buffer size · CPC title

• G06F9/3836

  Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution · CPC title

• G06F1/3275

  Power saving in memory, e.g. RAM, cache · CPC title

• G06F12/02 Primary

  Addressing or allocation; Relocation (program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00) · CPC title