Asynchronous first-in-first-out register structure

• US 4,837,740 A
• Filed: 11/10/1987
• Issued: 06/06/1989
• Est. Priority Date: 01/04/1985
• Status: Expired due to Term

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Ivan F. Sutherland
• Inventors: Sutherland, Ivan F.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US07/118,997
• Time in Patent Office: 574 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 365/73, 365/77, 365/78, 365/221, 377/66, 377/77, 377/81
• US Class Current: 710/316
• CPC Class Codes: G06F 5/08 having a sequence of storage locations, the intermediate ones not being accessible for either enqueue or dequeue operations, e.g. using a shift register G06F5/065 takes precedence; shift registers per se G11C19/00
• CPC Class Codes: G11C 19/00 Digital stores in which the information is moved stepwise, e.g. shift registers

Abstract

An asynchronous FIFO incorporates a series of interconnected cells alternately oppositely inverted to provide forward and retrograde data paths, so as to selectively establish virtual flip flops as needed at interfaces between cells. Each cell combines an inverting amplifier for data, switch structure and a binary control for the switch structure to provide the data path. The controls are interconnected in a sequence along with logic to set the state of each control according to an instruction: copy the state of your predecessor in the sequence if the states of your predecessor and successor differ, otherwise hold your present state.

Claims

1. An apparatus for use with data signals as one of a plurality of like units in a sequence, as in a first-in-first-out register, said one of a plurality of like units for connection with a predecessor unit and a successor unit, said apparatus comprising:

means for registering a state to provide a control signal for said one unit;

means controlled by said predecessor and successor units for altering said registered state of said one unit to that of said predecessor unit upon detecting the state of said predecessor unit and said successor unit to be different;

data means for said one unit for providing a data signal to said predecessor and successor units; and

switch means for said data means for said one unit activated in accordance with said control signal of said one unit, selectively provide forward and retrograde data paths to said successor and predecessor units whereby to pass a said data signal and enable virtual storage between said one unit and said other of said plurality of like units.

2. An apparatus according to claim 1 wherein said switch means is symmetrical to accommodate forward and retrograde data paths.

3. An apparatus according to claim 2 wherein said means for registering a state comprises a binary device.

4. An apparatus according to claim 1 wherein said means for registering and said means for altering comprise electronic apparatus operating with electrical signals.

5. An apparatus according to claim 4 wherein said switch means is symmetrical to accommodate forward and retrograde data paths.

6. An apparatus according to claim 2 wherein said switch means includes an amplifier means enhancing signals in said data paths.

7. A plurality of apparatus in accordance with claim 6 wherein said means to provide a control signal for said one unit is coupled to the means for providing a control signal in said predecessor and successor units and wherein said switch means of said plural units are interconnected to provide a first-in-first-out registration capability.

8. An apparatus according to claim 1 wherein said means for altering said registered state is asynchronous.

9. An apparatus according to claim 8 wherein said switch means is symmetrical to accommodate forward and retrograde data paths.

10. An apparatus according to claim 9 wherein said switch means includes an amplifier means for enhancing signals passing through said data paths.

11. An apparatus according to claim 10 wherein said switch means is asynchronous.

12. An apparatus in the form of said one unit according to claim 1 further including a processor for said one unit coupled to said switch means to process data in a forward data path.

13. A plurality of apparatus in accordance with claim 11 wherein said means to provide a control signal for said one unit is coupled to similar control means in said predecessor and successor units and wherein said switch means of said plurality units are interconnected to provide a first-in-first-out registration capability.

14. An apparatus according to claim 13 wherein said means for registering a state to provide control signals and said switch means are sized progressively in said plurality of units to accommodate varying signal levels in said apparatus.

15. An apparatus according to claim 13 wherein each of said means for registering and said means to provide a control signal comprise electronic apparatus operating with electrical signals.

16. An apparatus according to claim 1 further including multiple switch means in said unit actuated in accordance with said control signal.

17. An apparatus according to claim 16 further including processor means coupled between said switch means of said one unit and a predecessor unit process data in a data path therebetween.

18. A first-in-first-out register system for storing received data and having an input and an output, comprising:

a plurality of amplifying data cells including at least three cells;

means for interconnecting said amplifying data cells in a sequence between said input and said output including switch means to pass data signals bidirectionally with reference to said input and output and whereby said amplifying data cells may be controlled to pass data toward said output or pass data toward said input thereby provide cooperative storage of data between two amplifying data cells; and

control means for setting said switch means to control said amplifying data cells in accordance with received data signals and a predetermined propagation pattern whereby to provide such data signals at said output.

19. A system according to claim 18 wherein said means for interconnecting said data cells passes data signals asynchronously in said sequence of data cells.

20. A system according to claim 18 wherein said data cells manifest data moving in said sequence by signal transitions.

21. A system according to claim 19 wherein said data cells are connected to said control means to receive binary complementary signals from said control means.

22. A system according to claim 21 comprising plural sequences of said data cells, said data cells of different sequences being controlled by said control means.

23. A compound system comprising a plurality of systems in accordance with claim 18 interconnected in a series-parallel-series configuration.

24. A first-in-first-out register for storing data represented by received data signals, comprising:

a plurality of amplifiers designated in a predetermined progressive sequence;

input means to said plurality of amplifiers in said sequence;

a plurality of switch means individually interconnecting said amplifiers in said sequence with adjacent of said amplifiers in said sequence whereby signals from said sequence and whereby pairs of said amplifiers are switched to establish a storage therebetween; and

control means for setting said switch means in accordance with received data signals and a propagation pattern in said register.