FIFO buffer with full/empty detection by comparing respective registers in read and write circular shift registers

In a computer system, a method for generating empty and full signals for a First In First Out (FIFO) device, said method comprising the steps of:

• a) setting a read shift register and a write shift register, each having a plurality of register positions, to have a single logical one value in a corresponding register position;
• b) for each write operation to the FIFO, shifting said single logical one value to a next register position and toggling a write toggle value;
• c) for each read operation from the FIFO, shifting said logical one value to a next register position and toggling a read toggle value;
• d) after each write or read operation, identifying a boundary condition by comparing the corresponding register positions of said read shift register and said write shift register and determining if any corresponding pair of register positions both have a logical one value;
• e) asserting said full signal if said boundary condition exists and said read toggle value and write toggle value have a first set of predetermined values;
• and
• f) asserting said empty signal if said boundary condition exists and said read toggle value and write toggle value have a second set of predetermined values.

A circuit for generating almost full and almost empty signals for a First In First Out (FIFO) controller, said FIFO controller for controlling a FIFO with X storage locations, said circuit comprising:

• a) a write shift register having X register positions, said write shift register for tracking write operations of data into said memory device, said write shift register coupled to and triggered by a write clock;
• b) a read shift register having X register positions, said read shift register for tracking read operations of data from said memory device, said read shift register coupled to and triggered by a read clock;
• c) a read offset shift register having X register positions, said read offset shift register for tracking read operations from said memory device relative to said write shift register, said read offset shift register coupled to and triggered by said read clock;
• d) a write offset shift register having X register positions, said write offset shift register for tracking write operations from said memory device relative to said read shift register, said write offset shift register coupled to and triggered by said write clock;
• e) means for determining that corresponding register positions in said write shift register and said read offset shift registers both have a logical one value and asserting said almost full signal;
• and
• f) means for determining that corresponding register positions in said read shift register and said write shift registers both have a logical one value and asserting said almost empty signal.

A computer system comprising:

• a plurality of computing nodes, each of said computing nodes coupled to a routing element;
• a plurality of routing elements coupled to other of said plurality of routing elements, said plurality of routing elements for interconnecting each of said plurality of computing nodes;
• and
• each of said plurality of computing nodes comprised of a processor element and a buffer element, said processor element for processing data and said buffer element for managing the transfer of data between said processor element and said routing element;
• said buffer element comprised of:
• a memory means for storing data messages, said memory means having X locations for storing data messages;
• a read shift register having X register positions, said read shift register for identifying the location in said memory means from which a next data message is to be read
• a write shift register having X register positions, said read shift register for identifying the location in said memory means into which a next data message is to be written;
• flag signal generation means coupled to said read shift register and said write shift register, said flag signal generation means for generating a flag signal which indicates whether a boundary condition is occurring in said memory device;
• a read toggle responsive to a read clock for indicating whether an even or odd number of boundary conditions in said memory device have occurred;
• a write toggle responsive to a write clock for indicating whether an even or odd number of boundary conditions in said memory device have occurred;
• full signal generation means coupled to said flag signal generation means, said read toggle and said write toggle, said full signal generation means for generating a signal that said memory means is full;
• and
• empty signal generation means coupled to said flag signal generation means said read toggle and said write toggle, said empty signal generation means for generating a signal that said memory means is empty.

A circuit for generating flag signals for a First In First Out (FIFO) controller, said FIFO controller for controlling a FIFO with X storage locations, said circuit comprising::

• a) a read shift register coupled to and triggered by a read clock, said read shift register having X registers, said read shift register for identifying locations in said memory means from which data messages are read;
• c) a write shift register coupled to and triggered by a write clock, said write shift register having X registers, said write shift register for identifying locations in said memory means into which data messages are to be written;
• d) a first flag signal generation means coupled to said read shift register and said write shift register, said first flag signal generation means for generating an empty signal which indicates said FIFO is empty on a rising edge of said read clock and is not empty on a falling edge of said write clock;
• and
• e) a second flag signal generation means coupled to said read shift register and said write shift register, said second flag signal generation means for generating a full signal which indicates said FIFO is full on a rising edge of said write clock and is not full on a falling edge of said read clock.