Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

A PRODUCER-CONSUMER SYNCHRONIZATION SYSTEM

IP.com Disclosure Number: IPCOM000008289D
Original Publication Date: 1997-Sep-01
Included in the Prior Art Database: 2002-Jun-04
Document File: 2 page(s) / 134K

Publishing Venue

Motorola

Related People

Aviel Livay: AUTHOR [+3]

Abstract

This invention relates to a system on which hvo entities share a FIFO. One entity (the Producer) writes data to the FIFO while the other entity (the Consumer) reads data from that FIFO. Producer and Consumer operating frequencies can be different. The problem in implementing such a system is that the Producer shall not write to the FIFO when it is full and the Consumer shall not read from the FIFO when it is empty.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 48% of the total text.

Page 1 of 2

M-LA Technical Developments

@

A PRODUCER-CONSUMER SYNCHRONIZATION SYSTEM

by Aviel Livay, Marc Neustadter and Shtayer Ronen

PROBLEM DESCRIPTION

  This invention relates to a system on which hvo entities share a FIFO. One entity (the Producer) writes data to the FIFO while the other entity (the Consumer) reads data from that FIFO. Producer and Consumer operating frequencies can be different. The problem in implementing such a system is that the Producer shall not write to the FIFO when it is full and the Consumer shall not read from the FIFO when it is empty.

SOLUTION DESCRIPTION

  According to the present invention, the Producer maintains a Logical FIFO Write Pointer (LFWP) and the Consumer maintains a Logical FIFO Read Pointer (LFRP). The Producer com- pares its LFWP to the synchronized LFRP in order to determine whether logical FIFO is full. If the logical FIFO is not fnll then the Producer may write to it; otherwise it should wait until it is not full. The Consumer compares its LFRP to the synchronized LFWP in order to determine whether the logical FIFO is empty. If it is not empty then it may read from it. This solution is simple because each entity (either Producer or Consumer) knows the logical FIFO status by analyzing the current status of LFWP/LFRP without relying on events that were sampled in the past.

  This solution requires that LFWP be synchronized to the Consumer clock while LFRP is synchronized to the Producer clock. Pointers synchronization is not straight forward. For example, suppose that LFWP is synchronized to the Consumer clock at the same time at which it is incremented from 001 to 010. There is always a slight difference in the propagation delay of the bits constituting LFWP Therefore LFWP may be equal to011 forashortperiodoftime(001 ->Oll ->OlO) and it is possible that LFWP is sampled as part of

its synchronization to the Consumer clock at just that time. The result is that 011 is the value synchronized to the Consumer clock, which is wrong. In order to overcome this problem, the current invention encodes the pointers such that on every pointer transition only one bit changes. An example of a useful code is the gray code, i.e., 000 -> 001 -> 011 -> 010 -> 110 -> 111 -> 101 -> 100 -> 000. Note that on every transition only one bit is updated. This encoding scheme ensures that the synchronized pointer shall have one out of two legal values: the value before the transition and the value after the transition and no intermediate states are allowed.

  Let us denote the number of different values that a Logical FIFO pointer can have by M. Let us denote the logical FIFO size by N. According to the present invention, M should be greater than or equal to N. In the case where M = N, when LFWP = LFRP, there is no knowledge as to whether the logical FIFO is empty or full. Maintaining additional knowledge on the logical FIFO status (for example a full flag) is complex. A preferable solution requires M > N and has following defmi...