Electronic digital logic circuitry – Clocking or synchronizing of logic stages or gates
Reexamination Certificate
2001-02-21
2002-05-07
Tokar, Michael (Department: 2819)
Electronic digital logic circuitry
Clocking or synchronizing of logic stages or gates
C326S040000, C326S046000
Reexamination Certificate
active
06384634
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to movement of data across asynchronous clock boundaries and, more particularly, to elastic storage operations. Further particularly, the invention relates to recovery and boundary verification for elastic storage operations.
BACKGROUND OF THE INVENTION
The purpose of an elastic store is to allow the movement of data across asynchronous clock boundaries. At a boundary between two clock domains, a clock associated with incoming data and a clock associated with outgoing data may have different periods. Alternatively, the two clocks may alternate from high to low at the same rate.
A FIFO (First In First Out) memory may be used as part of an elastic store between the two clock domains. This FIFO memory may be a dual port RAM (Random Access Memory) with independent address inputs and data ports for read and write. A true dual-port memory allows each port to operate independently. Each side (read and write) of the elastic store uses a continuously-running independent clock and data may be read or written to the elastic store after activating a read or write enable port.
A typical FIFO has many inputs and many outputs. The inputs are arranged to receive, for a write, a write address at a write address input, data to write at a write data input, a signal on a write enable port and a write clock. The inputs are arranged to receive, for a read, a read address at a read address input, a signal on a read enable port and a read clock. The output is arranged to transmit, for a read, the data that is read at the read address. In particular, while writing is enabled by the signal on the write line, a write operation is performed on the data received at the write data input at a write address received at the write address input. The write operation occurs as triggered by the write clock. Further, when a read is enabled by the signal on the read line, a read operation is performed on the data present at the read address received at the read address input. The read operation occurs as triggered by the read clock.
A well designed elastic store includes a write counter for providing a write address, at the write address input, for each write operation. Similarly, the elastic store includes a read counter for providing a read address, at the read address input, for each read operation. Following each write or read operation, the respective counter is incremented to the next value in a counter cycle. The write counter and read counter cycle through the same sequence of addresses.
In designing an elastic store, consideration must be given to avoidance of overflow or underflow conditions. Take, for example, an elastic store having a clock ratio (the ratio between the write clock and read clock periods) of 15:14 and 64 buffer addresses. In this case, the elastic store may perform 34 more write operations than read operations before the elastic store is full (overflow). Similarly, the elastic store may perform 30 more read operations than write operations before the elastic store is empty (underflow). With a ratio of 15 to 14, the worst case is that the elastic store will perform 16 more write operations (or read operations) than read operations (or write operations). This scenario assumes a write address of 0 and read address of 31 at the beginning (boot-up time or after several recoveries). Under ideal conditions then, the distance between the read address and the write address is not less than 15.
At boot-up time, i.e., when the elastic store is turned on, write and read clocks may not reach a steady functionality immediately. Unfortunately, the address supplied by the write counter and the address supplied by the read counter are unknown at boot-up time. Thus, the possibility exists that the read address and the write address are adjacent (i.e., if one counter is incremented, the value supplied by each counter may be equal). This is a potentially dangerous scenario. For example, if a slip occurs on one clock (jitter), the elastic store might go into an overflow condition (an attempt to write to a full—i.e., unread—memory address) or an underflow condition (an attempt to read from an empty memory address). The result of the elastic store having gone into an overflow or underflow condition, is that the elastic store can no longer handle data without corruption.
In one recovery scheme, an interrupt can be generated, as triggered by an overflow or underflow condition, and software can reset the elastic store. However, the elastic store in this recovery scheme can take a while to react. Furthermore, when the elastic store does react, the software may reset the elastic store at an inopportune time.
Clearly, there is a requirement for measures to avoid overflow or underflow. However, if overflow or underflow occurs despite the avoidance measures there is a requirement for a recovery method for returning the elastic store to a functional state.
SUMMARY OF THE INVENTION
A circuit is provided that attempts to avoid elastic store overflow or underflow through address boundary verifications. However, if the elastic store fails due to over flow or underflow, a method is provided for recovering elastic store functionality.
Advantageously, the elastic store can work alone, i.e., external assistance is not required to correct for failures. Further, the elastic store is fully programmable for flexibility.
In accordance with an aspect of the present invention there is provided a method of operating an elastic store, the elastic store including a First In First Out memory (FIFO) having a write address input and a read address input. The method includes determining a write address as supplied to the write address input, determining a read address as supplied to the read address input, detecting a state of the elastic store wherein the write address is adjacent to the read address and, responsive to the detecting the state, performing a recovery operation.
In accordance with another aspect of the present invention there is provided an elastic store including a First In First Out memory (FIFO) having a write address input and a read address input, a write counter for supplying a write address to the write address input of the FIFO, a read counter for supplying a read address to the read address input of the FIFO and a verification and recovery circuit for receiving a write address as supplied to the write address input, receiving a read address as supplied to the read address input, detecting a state of the elastic store wherein the write address is adjacent to the read address and, responsive to the detecting the state, performing a recovery operation.
Other aspects and features of the present invention will become apparent to those of ordinary skill in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.
REFERENCES:
patent: 5898893 (1999-04-01), Alfke
patent: 5994920 (1999-11-01), Narayana et al.
patent: 6191992 (2001-02-01), Komoto
Alfke, P., “Moving Data Across Asynchronous Clock Boundaries”, 2000, <http://www.isdmag.com/editorial/2000/design/0003.html>, pp. 1-6.
Brissette Patrice
Thomson Sandy W. A.
Tokar Michael
Tran Anh
LandOfFree
Elastic store: recovery and boundary verification does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Elastic store: recovery and boundary verification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Elastic store: recovery and boundary verification will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2861313