Electrical computers and digital data processing systems: input/ – Input/output data processing – Flow controlling
Reexamination Certificate
1998-12-29
2001-11-06
Lee, Thomas (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Flow controlling
C701S102000, C358S001140, C358S001150
Reexamination Certificate
active
06314478
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to the field of queues or buffers as used in computing systems. More specifically, the present invention relates to those queues or buffers which behave or are intended to behave as circular queues or buffers. Particularly, the invention relates to those circular queues or buffers which are used for high speed communications between a first processor or system and a second processor or system.
BACKGROUND OF THE INVENTION
Typically, circular First In—First Out (FIFO) buffers or queues exist for numerous purposes including utilizing available memory resources effectively and repetitively, storing information where short term data transfer rates exceed the available temporary processing or transferring ability of the microprocessors or the like, and for temporary storage of data where the data size is limited but presently unknown or likely to be variable. FIFO buffers or queues can also be used for servicing hardware interrupts, cycling of software programs, for data shifting or manipulations, and for other purposes well known in the art. Circular FIFO buffers have likewise proven beneficial in the transfer of data both to and from communication devices and for other communication related applications. Typically, in certain communications applications or data transfer applications, the FIFO buffer or queue is first implemented in the hardware transmitting data or the hardware receiving data. Additional circular buffers or queues can be employed to move the received or transmitted data from or to the receiving or transmitting hardware.
Current FIFO buffers can be realized using one or more of many different mechanisms, including hardware implementation, software allocation, or a combination employing both hardware and software. A hardware implementation could include dedicated memory of a Central Processing Unit (CPU) using Dynamic Random Access Memories (DRAM), high speed memory, cache memory, or the like. Generally, at least two pointers are implemented in a circular FIFO buffer or queue. For example, the write pointer maintains the next or current available position in or for writing in the DRAM, memory, or storage space. The read pointer maintains the next or current position for retrieving data from the DRAM, memory, or storage space. It is customary to refer to the read pointer and write pointer as head pointer and tail pointer, or vice-versa, and therefore, herein they will be referred to specifically as ‘read pointer’ and ‘write pointer’ for clarity.
Additional types of control elements may be implemented in a circular queue or buffer. Optional pointers can exist for control in a circular FIFO buffer or system, including a data end pointer, one or more transfer pointers for execution of branching instructions, as well as others. Furthermore, one or more indexes or flags or the actual queue or buffer data can be used to implement queue or buffer control.
Optional control elements for the queue include buffer status indicators such as queue full, queue almost full, queue empty, queue almost empty, as well as other optional indicators such as data packet size, data size, transfer complete, data overrun, invalid request, free-count, used-count, a data loaded flag, and the like. These control elements have been added to circular queues to monitor or implement the ‘circular’ behavior of the queue, while actually implementing the circular queue using a linear physical addressing scheme or in a linear or matrixed (x by y addressing) memory array or data storage structure.
Referring briefly to
FIG. 2
a,
shown is a general overview of a prior art circular queue, or FIFO buffer, comprising numerous individual buffer storage elements
104
, a physical start address
117
which may be referenced by a logical start address
116
, a physical end address
121
which may be referenced by a logical end address
120
, a write address pointer
108
, and a read address pointer
112
. The ‘circular’ nature of this FIFO queue is shown by demonstrative return path
125
, whereby upon reaching logical end address
120
or physical end address
121
, the appropriate pointer resets to the logical start address
116
or physical start address
117
. In effect and by deliberate implementation, as physical end address
121
is reached, the incrementation of any particular logical or physical pointer referencing storage elements within the circular queue
200
, including either read address pointer
112
or write address pointer
108
, results in the pointer crossing the physical end address
121
to be reset to the logical or physical address at the physical start address
117
. For pointer addresses which exceed physical end address
121
, then to determine the appropriate pointer address within the circular queue, a multiplicative factor of physical end address
121
minus physical start address
117
is subtracted from the pointer address to reduce its value to an address value less than the physical end address
121
but greater than or equal to the physical start address
117
. In most present day systems, this is typically done by taking the modulus of the address divided by logical end address
120
when the logical start address
116
address is zero.
As demonstrated in
FIG. 2
a,
the buffer storage elements
104
are entirely empty. The write address pointer
108
points to the first available data storage element which is unused and available for data storage. The read address pointer
112
likewise points to the last used buffer storage elements
104
, or initialized (as shown therein) to the logical end address
120
. As data is written into the circular queue
200
, the buffer storage elements
104
fill as necessary to store data. As each portion or piece of data is written, a check is made to ensure write address pointer
108
has not exceeded logical end address
120
(or physical end address
121
) and read address pointer
112
. Thereafter, write address pointer
108
moves to point to the next available storage element address, as is shown in
FIG. 2
b
by the storage of Data Groups (
1
) through (
9
), Upon reaching logical end address
120
or physical end address
121
, the address of write address pointer
108
is reset to logical start address
116
or physical start address
117
. As shown in
FIG. 2
b,
no read process has yet occurred in the queue of
FIG. 2
b
as the read address pointer
112
remains at its initialized position.
As shown in
FIG. 2
c,
the operation of the circular queue
200
has completed data storage into each of the buffer storage elements
104
, and has begun the reading process as data groups less than Data Group (
24
) have been read, as indicated by the shift in position of read address pointer
112
. Also shown in
FIG. 2
c
is the write of Data Group (
31
) across physical end address
121
, resulting in a first data group portion being written (identified as Data Group (
31
A)) up to logical end address
120
, and a second portion being written (identified as Data Group (
31
B)) starting from logical start address
116
. Data Group (
31
A) in combination with Data Group (
31
B) is computationally or logically treated as a continuous single data group by the appropriate use of pointers, control functions, logic circuits and the like to effectively make a linear storage system of circular queue
200
appear or function ‘circular’.
Referring next to
FIG. 2
d,
shown is circular queue
200
where the queue is functionally full of data comprised of the Data Groups (
41
)-(
50
). The storage element wherein write address pointer
108
and read address pointer
112
both reside in the same storage element wherein no presently valid data exists. Typically, write address pointer
108
is not permitted to proceed to (or in certain designs pass) the exact position of read address pointer
112
. Likewise, read address pointer
112
is not permitted to proceed to (or in certain designs pass) the exact position of write address pointer
108
. However, contingent upon the particular circular q
Elamin Abdelmoniem
Lee Thomas
NEC America Inc.
Scully Scott Murphy & Presser
LandOfFree
System for accessing a space appended to a circular queue... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for accessing a space appended to a circular queue..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for accessing a space appended to a circular queue... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2579044