Data validity measure for efficient implementation of...

Details Data validity measure for efficient implementation of... Data validity measure for efficient implementation of...

2000-11-15

2002-12-10

Gaffin, Jeffrey (Department: 2182)

Electrical computers and digital data processing systems: input/

Input/output data processing

Input/output data buffering

C710S053000, C710S055000, C710S057000, C710S033000, C710S035000, C709S213000, C709S216000

Reexamination Certificate

active

06493773

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of computer memories. More particularly, the present invention relates to the field of First-In-First-Out memories for multi-processor computer systems.
2. Description of the Related Art
First-In-First-Out memories (FIFOs)are commonly used in electronic systems. FIFOs are used to transfer data between two electronic devices or modules where the data source (data writer) produces data asynchronously to a data sink's (data reader's) need for the data. The data is written into the FIFO by the writer as it is produced, and then read from the FIFO by the reader as the data is needed.
A FIFO is typically composed of a buffer where the data elements are stored, and descriptors which contain control information about the FIFO such as pointers to the storage locations where the next read or write operations should occur. An important consideration in the design of a FIFO is to prevent FIFO overflow and underflow conditions. A FIFO overflow occurs when the FIFO is full (all the buffer locations are used) and the writer attempts to insert a new data element. A FIFO underflow occurs when the FIFO is empty (there are no elements in the buffer) and the reader attempts to retrieve an element from the buffer. FIFO buffers may be implemented in many ways including arrays, linked lists and dedicated hardware memories. Similarly, FIFO descriptors may be software data structures or dedicated hardware circuits.
In many systems with multiple processors communicating among each other, each processor may have part or all of its memory accessible by other processors. Such memory will be referred to as shared memory, while processor memory that is not accessible for other processors will be called private memory. A subsystem, which includes a processor together with its private and shared memory, is typically interconnected with other subsystems by a bus. An example of such a bus is the industry standard Peripheral Component Interconnect (PCI) bus.
FIG. 1
shows a typical system having two electronic subsystem modules, each module including a processor and associated memory. A first module
10
which reads from a FIFO, and a second module
20
which writes to the FIFO, are connected via bus
30
. Reader module
10
includes a processor
12
, bus interface logic
14
, private memory
16
, and shared memory
18
. Similarly, Writer module
20
includes a processor
22
, bus interface logic
24
, private memory
26
, and shared memory
28
. For each module, its shared memory is accessible by the other module. In such a system, only one subsystem may be the master of the bus at a given time. The master requests the bus, waits until the bus is granted, and then initiates a transaction resulting in data being transferred to one or more other subsystems. If another subsystem has data to transfer at the same time, that second subsystem has to wait until the current bus master terminates the transaction. The time elapsed between the bus request and the first element of data being transferred is called bus latency. The bus latency typically increases with the number of subsystems using the bus and the average length of a transaction.
The simplest implementation for a FIFO is to use dedicated hardware circuits. In this case, a write controller performs a write transaction to a fixed memory location. The hardware based FIFO manager stores the data in the order it was received and informs the writer when an overflow condition occurs via a discrete output from the FIFO. A read controller performs a read transaction from the FIFO mapped at a fixed memory location and the FIFO manager makes the data available at the FIFO output port from its internal storage, in the order it was put there by the writer. Examples of such FIFOs include fall-through FIFOs and RAM based FIFOs.
FIG. 2
illustrates a second way to implement a FIFO. In this implementation, both the FIFO buffer and the FIFO descriptor are implemented in shared memory. This implementation will be described further below.
In the discussion that follows the algorithms used to implement the FIFO will be described using the C programming language for illustration purposes. The actual implementation may employ a different language, assembly language, or a hardware FIFO manager. Similarly, the FIFO buffer will be described as a RAM-based array holding data elements, although other implementations are possible. In the example of
FIG. 2
, the FIFO is implemented in memory that is on-board to the writer electronic module. Alternatively, the FIFO could be implemented within shared memory on-board to the reader module, with appropriate changes to the read and write algorithms.
In a first conventional implementation A, the FIFO descriptor is composed of two pointers (a read pointer, RD, and a write pointer, WR) and two binary flags (a full flag and an empty flag). The corresponding C programming language type definition statement is:
IMPLEMENTATION A
1
typedef struct {
2
 int WR;
/*initialized to 0 */
3
 int RD;
/* initialized to 0 */
4
 int Full;
/* initialized to 0 */
5
 int Empty;
/* initlalized to 1 */
6
{ FifoDesc_t, *pFifoDesc_t;
7
8
Elem_t Fifo[SIZE];
In this implementation, an operation of retrieving an element from a FIFO may be implementing by the following GetFifo routine:
 9
GetFifo (pFifoDesc_t FifoDesc, pElem_t Elem)
10
{
11
 if (FifoDesc->Empty)
/* R(Empty) */
12
 return 0;
13
*Elem=Fifo[FifoDesc->RD];
/* R(RD) + */
/* R(Fifo[RD] */
14
if (++FifoDesc->RD == SIZE)
15
 FifoDesc->RD = 0;
/*W(RD)*/
16
if (FifoDesc->RD == FifoDesc->WR
 /* R(WR) */
17
 FifoDesc->Empty = 1;
/* W(Empty)*/
18
return 1;
19
}
The read and write operations across the bus are indicated by the comments to the code.
The above routine is called to retrieve an element from the FIFO. If the FIFO is empty, the routine returns failure code
0
. Otherwise, the data element is copied to the destination and the FIFO RD pointer is advanced. If the FIFO RD pointer comes to equal the FIFO WR pointer, the FIFO is empty. This FIFO read routine requires four read operations and two write operations across the bus.
To write an element into the FIFO, the routine PutFifo is called:
20
int PutFifo (pFifoDesc_t FifoDesc, Elem_t Elem)
21
{
22
if (FifoDesc->FUll)
23
 return 0;
24
Fifo[FifoDesc->WR] = Elem;
25
if (++FifoDesc->WR == SIZE)
26
 FifoDesc->WR = 0;
27
if (FifoDesc->WR == FifoDesc->RD)
28
 FifoDesc->Full = 1;
29
return 1;
30
}
The above routine first checks FIFO status and returns failure code
0
if the FIFO is full. Otherwise, the data element is copied to the FIFO buffer and the WR pointer is incremented. If the WR pointer equals the RD pointer, the FIFO has become full. The PutFifo routine does not require any bus transactions because the FIFO is on-board to the Writer module in this example.
FIGS. 3A through 3G
illustrate the writing of data to the FIFO and the reading of data from the FIFO, and the corresponding conditions of the Full and Empty flags.
FIGS. 3E and 3F
illustrate how the WR pointer, for example, wraps around from the end of the FIFO back to the beginning.
In a second implementation B of a shared memory FIFO, full and empty flags are not used. For this alternate implementation the type definition statement is:
IMPLEMENTATION B
1
typedef struct {
2
 int WR;
/* initialized to 0 */
3
 int RD;
/* initialized to 0 */
4
} FifoDes_t, *pFifoDesc_t;
5
6
Elem_t Fifo[SIZE];
In this implementation, an operation of retrieving an element from a FIFO may be implementing by the following GetFifo routine:
 7
int GetFifo (pFifoDesc_t FifoDesc, pElem_t Elem)
 8
{
 9
 if (FifoDesc->RD == FifoDesc->WR
/* R(RD + R(WR) *

Affiliated with

Also associated with

Rating

Data validity measure for efficient implementation of... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data validity measure for efficient implementation of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data validity measure for efficient implementation of... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2976676