Method and apparatus for dynamic buffer allocation in a bus bridge for pipelined reads

• US 5,802,055 A
• Filed: 04/22/1996
• Issued: 09/01/1998
• Est. Priority Date: 04/22/1996
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Kelly, James D., Krein, William Todd, Flaig, Charles M.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): PHILLIPS, MATTHEW
• Application Number:
  US08/635,646
• Time in Patent Office: 862 Days
• Field of Search: 370/402, 370/401, 370/403, 370/404, 370/405, 370/413, 370/412, 370/419, 395/292, 395/299, 395/305, 395/309, 395/310, 395/285, 395/308
• US Class Current: 370/402
• CPC Class Codes: G06F 13/4027 using bus bridges G06F13/4022 takes precedence
• CPC Class Codes: G06F 13/4059 where the synchronisation uses buffers, e.g. for speed matching between buses

Abstract

A bus bridge circuit employs a dynamic allocation scheme that allows read transactions to be pipelined without deadlock and without the need for permanently reserving multiple buffer slots for read response transactions. The bus bridge circuit associates input and output buffers with a node and includes a state machine to monitor the number and type of transaction packets currently in slots that make up the buffers. In particular, the state machine monitors the number of transaction packets loaded in the output buffer slots, the number of outstanding read transactions for the node, and the number of read response transactions currently loaded in the output buffer. The state machine then allows the node to load a READ or WRITE transaction only if the monitored data indicates at least one of the buffer slots will be available to service a READ RESPONSE subsequently loaded by the node. The state machine launches READs to the node only when an unallocated buffer slot is available to service the corresponding READ RESPONSE.

Claims

1. A bridge circuit for transmitting message packets between a first and second node in a system employing a packet switched, split transaction bus protocol, the bridge circuit comprising:

first and second buffers, each buffer having an input line, an output line and a number of buffer slots for temporarily storing message packets; and

a first state machine coupled to the first node, to the input line of the first buffer and to the output line of the second buffer, the first state machine including a first counter for monitoring outstanding read transactions launched to the first node, a second counter for monitoring read response transactions loaded into the first buffer by the first node, and a third counter for monitoring currently loaded buffer slots of the first buffer, the first state machine including logic for transferring transactions to and from the first node according to launch and load slot availability criteria determined from the first, second, and third counters; and

a second state machine coupled to the second node, to the input line of the second buffer, and to the output line of the second buffer, the second state machine including a first counter for monitoring outstanding read transactions launched to the second node, a second counter for monitoring read response transactions loaded into the second buffer by the second node, and a third counter for monitoring currently loaded buffer slots of the second buffer, the second state machine also including logic for transferring transactions to and from the second node according to launch and load slot availability criterion determined from the first, second, and third counters.

2. The bridge circuit of claim 1, wherein the load slot availability criterion is represented by a signal that is asserted when the number of buffer slots exceeds the sum of the first and third counters by at least two.

3. The bridge circuit of claim 2, wherein the load slot availability signal is also asserted when the number of buffer slots exceeds the sum of the first and third counters by one and the first counter is non-zero.

4. The bridge circuit of claim 2, wherein the load slot availability signal is also asserted when the number of buffer slots exceeds the sum of the first and third counters by one and the second counter is non-zero.

5. The bridge circuit of claim 2, wherein the load slot availability signal is also asserted when the number of buffer slots exceeds the sum of the first and third counters by one and either the first counter is non-zero or the second counter is non-zero.

6. The bridge circuit of claim 1, wherein the launch slot availability criteria is met when the number of buffer slots exceeds the sum of the first and third counters.

7. The bridge circuit of claim 1, wherein each of the first and second state machines includes logic for ensuring that read response transactions are launched before write and read transactions.

8. The bridge circuit of claim 1, further comprising a third state machine coupled to the first and second buffers and the first and second state machines, for transferring status information among the first and second buffers and the first and second state machines.

9. A state machine for regulating transfer of data packets between a node and associated input and output buffers, the state machine comprising:

a transmission line for receiving outbound data packet information from the node and sending a packet loading signal to the node;

a transmission line for receiving inbound data packet information from the input buffer and sending a packet launching signal to the input buffer;

a status memory location for tracking a data packet in a slot associated with the output buffer;

first and second transaction type memory locations for tracking outstanding read data packets and loaded read response data packets, respectively; and

control logic for transferring data packets to and from the node when the status and transaction type memory locations indicate that a slot availability criterion has been met.

10. The state machine of claim 9, wherein the control logic transfers packets to the node when a launch slot availability criterion is met and transfers packets from the node when a load slot availability criterion is met.

11. The state machine of claim 10, wherein the first and second type memory locations are first and second counters, the first counter being incremented when a read packet is launched to the node and decremented when a read response packet is loaded from the node, and the second counter being incremented when a read response packet is loaded from the node and decremented when a read response packet is launched from the output buffer.

12. The state machine of claim 11, wherein the status memory location comprises a status bit associated with each slot of the output buffer, the status bit of a slot being set when the associated slot holds a data packet.

13. The state machine of claim 10, wherein the load slot availability criterion is met when the number of buffer slots of the output buffer exceeds the sum of set status bits and the first counter by at least a first threshold.

14. The state machine of claim 13, wherein the first threshold is two.

15. The state machine of claim 10, wherein the load slot availability criterion is met when the number of buffer slots exceeds the sum of set status bits and the second counter by a second threshold and the first counter is non-zero.

16. The state machine of claim 15, wherein the second threshold is one.

17. The state machine of claim 11, wherein the load slot availability criterion is met when the number of buffer slots exceeds the sum of set status bits and the second counter by a second threshold and the second counter is non-zero.

18. The state machine of claim 17, wherein the second threshold is one.

19. The state machine of claim 10, wherein the load slot availability criterion is met when the number of buffer slots of the output buffer exceeds the sum of set status bits and the first counter by at least a first threshold or when the number of buffer slots exceeds the sum of set status bits and the second counter by a second threshold that is less than the first threshold and either the first or second counter is non-zero.

20. The state machine of claim 19, wherein the first threshold is two and the second threshold is one.

21. The state machine of claim 10, wherein the launch slot availability criterion is met when the number of buffer slots of the output buffer exceeds the sum of set status bits and the first counter.

22. In a packet transfer circuit comprising a plurality of output buffer slots for coupling transaction packets from a first node to a second node and a plurality of input buffer slots for coupling transaction packets from the second node to the first node, a method for dynamically allocating one of the plurality of output buffer slots for a transaction packet, the method comprising the steps of:

monitoring the plurality of output buffer slots to determine a first number of the output buffer slots that are loaded with transaction packets

determining a second number of the loaded transaction packets that are read response transactions;

monitoring the plurality of input buffer slots to determine a third number of outstanding read transactions that have been launched to the first node;

loading a transaction from the first node when the first, second, and third numbers satisfy a load slot availability criterion.

23. The method of claim 22, wherein the loading step comprises the substeps of:

determining a difference between the plurality of output buffer slots and a sum of the first and third numbers; and

indicating to the first node that the load slot availability criterion is satisfied when the difference is two or more.

24. The method of claim 23, comprising the additional substep of indicating to the first node that the load slot availability criterion is satisfied when the difference is one and the second number is non-zero.

25. The method of claim 22, comprising the additional substep of indicating to the first node that the load slot availability criterion is satisfied when the difference is one and the third number is non-zero.

26. The method of claim 22, comprising the additional substeps of:

determining a difference between the plurality of output buffer slots and a sum of the first and third numbers; and

indicating to the first node that the load slot availability criterion is satisfied when the difference is two or more, or when the difference is one and either the second number of the third number is non-zero.

27. The method of claim 22, comprising the additional substep of launching a transaction to the first node when the first and second numbers satisfy a launch slot availability criterion.

28. The method of claim 27, wherein the launching step comprises the substeps of:

determining a difference between the plurality of output buffer slots and a sum of the first and third numbers; and

launching a read transaction to the first node when the difference is one or more.

29. The method of claim 28, comprising the additional substep of indicating to the first node that the load slot availability criterion is satisfied when the difference is two or more, or when the difference is one and either the second number of the third number is non-zero.