Apparatus and technique for maintaining order among requests issued over an external bus of an intermediate network node

• US 6,757,768 B1
• Filed: 05/17/2001
• Issued: 06/29/2004
• Est. Priority Date: 05/17/2001
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Garner, Trevor, Potter, Kenneth H.
• Primary Examiner(s): THAI, XUAN MARIAN
• Application Number:
  US09/859,707
• Time in Patent Office: 1,139 Days
• Field of Search: 710/1, 710/5, 710/6, 710/305-314, 710/100, 710/112, 710/36, 710/39, 710/52, 709/200, 370/412-414
• US Class Current: 710/112
• CPC Class Codes: G06F 13/36 for access to common bus or bus system

Abstract

An apparatus and technique off-loads responsibility for maintaining order among requests issued over a split transaction bus from a processor to a split transaction bus controller, thereby increasing the performance of the processor. A logic circuit enables the controller to defer issuing a subsequent (write) request directed to an address on the bus until all pending (read) requests complete. By off-loading responsibility for maintaining order among requests from the processor to the controller, the invention enhances performance of the processor since the processor may proceed with program execution without having to stall to ensure such ordering. The logic circuit maintains the order of the requests in an efficient manner that is transparent to the processor.

Claims

1. An ordering circuit configured to off-load responsibility for maintaining order among requests issued over a split transaction bus from a processor to a split transaction bus controller of an intermediate network node, the ordering circuit comprising:

a command table having a plurality of entries, each entry adapted to track a pending read request issued by the processor and destined for the split transaction bus;

conflict detection logic coupled to the command table, the conflict detection logic comparing an address of a write request issued by the processor with an address of a pending read request stored in each entry of the command table, the conflict detection logic asserting a conflict bit corresponding to an entry of the command table when the address of any pending read request stored in the entry matches the address of write request; and

a read-in-progress register having a plurality of bits, each bit corresponding to a pending read request sent over the bus,

wherein assertion of a bit of the read-in-progress register and the conflict bit causes the write request to wait until all pending read requests complete before being sent over the split transaction bus to thereby maintain order among read and write requests directed to the same address on the bus.

2. The ordering circuit of claim 1 wherein each entry of the command table comprises:

an address field for storing the address of the request;

a type field for storing a particular type of request; and

a state field for storing a state of the request.

3. The ordering circuit of claim 2 wherein each entry of the command table further comprises:

a source ID field for storing the identity of the source of the request.

4. The ordering circuit of claim 1 further comprising:

an input queue manager coupled between a system bus and the command table, the input queue manager receiving a request from the system bus and, in response, allocating an entry in the command table, the input queue manager further calculating a tag value associated with the allocated entry, and placing the type of request and address of the request in the allocated entry.

5. The ordering circuit of claim 4 wherein the input queue manager is further coupled to the conflict detection logic and a low priority FIFO, the input queue manager sending the address of the request to the conflict detection logic and, in response, receiving a match bit map from the conflict detection logic, the input queue manager loading the received match bit map and the tag value into an entry in the low priority FIFO.

6. The ordering circuit of claim 5 further comprising:

a response manager coupled to the low priority FIFO and a response queue, the response manager receiving a response associated with the pending read request from the response queue and deasserting an asserted match bit corresponding to the pending read request for each entry in the low priority FIFO.

7. The ordering circuit of claim 4 wherein the input queue manager is further coupled to the read-in-progress register, the input queue manager receiving a read request from the system bus and asserting a bit in the read-in-progress register that corresponds to the read request.

8. The ordering circuit of claim 1 wherein the conflict detection logic comprises:

comparator logic associated with each entry of the command table and configured to compare the address of the request stored in the command table entry with the address associated with the request.

9. The ordering circuit of claim 8 wherein the match bit is asserted if the compared addresses are the same and the type of command in the entry is a read request.

10. The ordering circuit of claim 1 further comprising:

an output queue manager coupled to a high priority FIFO and the low priority FIFO, the output queue manager servicing a request at the high priority FIFO before servicing a request at the low priority FIFO.

11. The ordering circuit of claim 10 wherein the output queue manager is further coupled to a read-in-progress register, the output queue manager receiving a read request from one of the high priority FIFO or the low priority FIFO and asserting a bit in the read-in-progress register that corresponds to the read request.

12. The ordering circuit of claim 1 further comprising:

a response manager coupled to the pending command table, the response manager receiving a response associated with the pending request and changing a state field in the command table entry associated with the pending request to indicate the entry is non-pending.

13. The ordering circuit of claim 1 further comprising:

a response manager coupled to the read-in-progress register, the response manager receiving a response associated with the pending request and deasserting a bit corresponding to the pending request in the read-in-progress register.

14. A method for maintaining order among read and write requests directed to a same address on a split transaction bus from a processor to a split transaction bus controller of an intermediate network node, the method comprising the steps of:

receiving a request at an ordering circuit of the controller, the request containing a type of the request and an address of the request;

storing the request into an entry in a command table and marking the request as pending;

if the type of the request is a write request, searching the command table and asserting a match bit for each pending read request entry whose request address stored in the entry matches the address of the write request;

if the request is a write request, loading the request in a low priority output queue;

if the request is a read request, loading the request in a high priority output queue and asserting a corresponding bit in a read-in-progress register unless the low priority queue contains either a read request or another request whose request address is the same as the request in which case the request is loaded into the low priority output queue;

when the request reaches the head of the output queue, determining if any match bit is asserted in any entry associated with the request and if the request is a write request, determining if any bit in the read-in-progress register is asserted;

if any match bit is asserted and if the request is write request any bit in the read-in-progress register is asserted, causing the request to wait at the head of the output queue until all match bits are deasserted and if the request is a write request until all bits in the read-in-progress register are deasserted; and

as each pending read request completes, marking the entry for the read request as non-pending, deasserting the match bit associated with the read request for all entries in the table and deasserting the bit associated with the read request in the read-in-progress register.

50. A computer readable media, comprising:

said computer readable media having instructions written thereon for execution on a processor for the practice of the method of claim 14 or claim 28.

51. Electromagnetic signals propagating on a computer network, comprising:

said electromagnetic signals carrying instructions for execution on a processor for the practice of the method of claim 14 or claim 28.

15. Apparatus for maintaining order among read and write requests directed to a same address on a split transaction bus from a processor to a split transaction bus controller of an intermediate network node, the apparatus comprising:

means for receiving a request at an ordering circuit of the controller, the request containing a type of the request and an address of the request;

means for storing the request into an entry in a command table and marking the request as pending;

if the type of the request is a write request, means for searching the command table and asserting a match bit for each pending read request entry whose request address stored in the entry matches the address of the write request;

if the request is a write request, means for loading the request in a low priority output queue;

if the request is a read request, means for loading the request in a high priority output queue and asserting a corresponding bit in a read-in-progress register unless the low priority queue contains either a read request or another request whose request address is the same as the request in which case the request is loaded into the low priority queue;

when the request reaches a head of the output queue, means for determining if match bit is asserted in any entry associated with the request and if the request is a write request, determining if any bit in the read-in-progress register is asserted;

if any match bit is asserted and if the request is a write request if any bit in the read-in-progress register is asserted, means for stalling the request at the head of the output queue until all match bits are deasserted and if the request is a write request all bits in the read-in-progress register are deasserted; and

as each pending read request completes, means for marking the entry for the read request as non-pending, deasserting the match bit associated with the read request for all entries in the table and deasserting the bit associated with the read request in the read-in-progress register.

16. A computer readable medium containing executable program instructions for maintaining order among read and write requests directed to a same address on a split transaction bus from a processor to a split transaction bus controller of an intermediate network node, the executable program instructions comprising program instructions for:

means for receiving a request at an ordering circuit of the controller, the request containing a type of the request and an address of the request;

storing the request into an entry in a command table and marking the request as pending;

if the type of the request is a write request, searching the command table and asserting a match bit for each pending read request entry whose request address stored in the entry matches the address of the write request;

if the request is a write request, loading the request in a low priority output queue;

if the request is a read request, loading the request in a high priority output queue and asserting a corresponding bit in a read-in-progress register unless the low priority queue contains either a read request or another request whose request address is the same as the request in which case the request is loaded into the low priority output queue;

when the request reaches the head of the output queue, determining if any match bit is asserted in any entry associated with the request and if the request is a write request, determining if any bit in the read-in-progress register is asserted;

if any match bit is asserted and if the request is write request any bit in the read-in-progress register is asserted, causing the request to wait at the head of the output queue until all match bits are deasserted and if the request is a write request until all bits in the read-in-progress register are deasserted; and

as each pending read request completes, marking the entry for the read request as non-pending, deasserting the match bit associated with the read request for all entries in the table and deasserting the bit associated with the read request in the read-in-progress register.

17. An ordering apparatus for maintaining order among requests issued over a split transaction bus from a processor to a split transaction bus controller, comprising:

a command table having a plurality of entries, each entry adapted to track a pending read request issued by the processor on the split transaction bus; and

conflict detection logic coupled to the command table, the conflict detection logic comparing an address of a write request issued by the processor with an address of each pending read request stored in the command table, and in the event that an address of the write request matches an address of a pending read request, causing the write request to wait until all pending read requests complete before the write request is sent over the split transaction bus, to maintain order among read and write requests on the split transaction bus without stalling the processor.

18. The apparatus as in claim 17, further comprising:

a read-in-progress register having a plurality of bits, each bit corresponding to a pending read request;

the conflict detection logic asserting a conflict bit when the address of any pending read request stored in the entry matches the address of the write request, and the write request waiting, in response to assertion of a bit of the read-in-progress register and the conflict bit, until all pending read requests complete before the write request is sent over the split transaction bus.

19. The apparatus of claim 18 further comprising:

a response manager to clear a bit in the read-in-progress register corresponding to a read instruction which is in progress, the bit being cleared in response to receiving a response to the corresponding read instruction.

20. The apparatus of claim 19 further comprising:

an output queue manager to send the pending write request over the split transaction bus in response to all bits in the read-in-progress register being cleared.

21. The apparatus of claim 17 further comprising:

a high priority queue and a low priority queue;

an input queue manager to place the write request into the low priority queue;

the input queue manager, in response to receiving a subsequent read request for an address matching an address of the pending write request, to write the subsequent read request into the low priority queue after the write request and to not set the bit corresponding to the subsequent read request in the read-in-progress register, because the subsequent read request cannot pass the pending write request and so cannot be executed before the pending write request;

the input queue manager, in response to receiving a different subsequent read request directed to an address different from the address of the pending write request, loading the different subsequent read request into the high priority queue and also setting the bit in the read-in-progress register corresponding to the different subsequent read request to cause the pending write request to wait for receipt of the response to the different subsequent write request.

22. The apparatus of claim 21, further comprising:

an output queue manager receiving a read request from the low priority queue and transmitting the read request over the split transaction bus, and also asserting a bit in the read-in-progress register that corresponds to the read request.

23. The apparatus of claim 17, further comprising:

a high priority queue and a low priority queue;

an input queue manager receiving a read request from the processor; and

the input queue manager coupled to the conflict detection logic and a low priority queue, the input queue manager sending the address of the request to the conflict detection logic, and in response to receiving a conflict bit from the conflict detection logic, loading the received conflict bit and a tag value identifying the read request into an entry in the low priority queue.

24. The apparatus of claim 23 further comprising:

the input queue manager is further coupled to the read-in-progress register and the high priority queue, the input queue manager receiving a read request from the processor and asserting a bit in the read-in-progress register that corresponds to the read request when the request is placed in the high priority queue.

25. The apparatus of claim 17 further comprising:

a response manager coupled to the read-in-progress register, the response manager receiving a response to a pending read request; and

the response manager, in response to receiving the response to a pending read request, deasserting a bit in the read-in-progress register corresponding to the pending read request.

26. The apparatus of claim 17, further comprising:

comparison logic to compare an address of a pending read request with the address of the write request;

the comparison logic, in response to the address of the write request matching the address of any pending read request, asserting a bit in a bit mask; and

an OR circuit, in response to any bit in the bit mask being asserted, asserting a conflict bit.

27. The apparatus of claim 17 further comprising:

a high priority queue and a low priority queue;

an output queue manager coupled to the high priority queue and the low priority queue, the output queue manager servicing a request at the high priority queue before servicing a request at the low priority queue.

28. A method for maintaining order among requests issued over a split transaction bus from a processor to a split transaction bus controller, comprising:

tracking a pending read request issued by the processor on the split transaction bus; and

comparing an address of a write request issued by the processor with an address of each pending read request, and in the event that an address of the write request matches an address of a pending read request, causing the write request to wait until all pending read requests complete before the write request is sent over the split transaction bus, to maintain order among read and write requests on the split transaction bus without stalling the processor.

29. The method as in claim 28, further comprising:

maintaining a read-in-progress register having a plurality of bits, each bit corresponding to a pending read request; and

asserting a conflict bit when the address of any pending read request matches the address of the write request, and the write request waiting, in response to assertion of a bit of the read-in-progress register and the conflict bit, until all pending read requests complete before the write request is sent over the split transaction bus.

30. The method of claim 29 further comprising:

clearing a bit in the read-in-progress register corresponding to a read instruction which is in progress, the bit being cleared in response to receiving a response to the corresponding read instruction.

31. The method of claim 30 further comprising:

sending the pending write request over the split transaction bus in response to all bits in the read-in-progress register being cleared.

32. The method of claim 28 further comprising:

maintaining a high priority queue and a low priority queue;

placing the write request into the low priority queue;

writing, in response to receiving a subsequent read request for an address matching an address of the pending write request, the subsequent read request into the low priority queue after the write request and not setting the bit corresponding to the subsequent read request in the read-in-progress register, because the subsequent read request cannot pass the pending write request and so cannot be executed before the pending write request; and

loading, in response to receiving a different subsequent read request directed to an address different from the address of the pending write request, the different subsequent read request into the high priority queue and also setting a bit in the read-in-progress register corresponding to the different subsequent read request to cause the pending write request to wait for receipt of the response to the different subsequent write request.

33. The method of claim 32, further comprising:

receiving a read request from the low priority queue and transmitting the read request over the split transaction bus, and also asserting a bit in the read-in-progress register that corresponds to the read request.

34. The method of claim 28, further comprising:

maintaining a high priority queue and a low priority queue;

receiving a read request from the processor, and in response allocating an entry in the command table; and

loading, in response to receiving a conflict bit from the conflict detection logic, the received conflict bit and a tag value identifying the read request into an entry in the low priority queue.

35. The method of claim 34 further comprising:

receiving a read request from the processor, placing the read request in the high priority queue, and asserting a bit in the read-in-progress register that corresponds to the read request.

36. The method of claim 28 further comprising:

receiving a response to a pending read request; and

deasserting, in response to receiving the response to a pending read request, a bit in the read-in-progress register corresponding to the pending read request.

37. The method of claim 28, further comprising:

comparing an address of a pending read request with the address of the write request;

asserting, in response to the address of the write request matching the address of any pending read request, a bit in a bit mask; and

asserting, in response to any bit in the bit mask being asserted, a conflict bit.

38. The method of claim 28 further comprising:

maintaining a high priority queue and a low priority queue;

servicing a request at the high priority queue before servicing a request at the low priority queue.

39. An apparatus to maintain order among requests issued over a split transaction bus from a processor to a split transaction bus controller, comprising:

means for tracking a pending read request issued by the processor on the split transaction bus; and

means for comparing an address of a write request issued by the processor with an address of each pending read request, and in the event that an address of the write request matches an address of a pending read request, causing the write request to wait until all pending read requests complete before the write request is sent over the split transaction bus, to maintain order among read and write requests on the split transaction bus without stalling the processor.

40. The apparatus as in claim 39, further comprising:

a read-in-progress register having a plurality of bits, each bit corresponding to a pending read request; and

means for asserting a conflict bit when the address of any pending read request matches the address of the write request, and the write request waiting, in response to assertion of a bit of the read-in-progress register and the conflict bit, until all pending read requests complete before the write request is sent over the split transaction bus.

41. The apparatus of claim 40 further comprising:

means for clearing a bit in the read-in-progress register corresponding to a read instruction which is in progress, the bit being cleared in response to receiving a response to the corresponding read instruction.

42. The apparatus of claim 41 further comprising:

means for sending the pending write request over the split transaction bus in response to all bits in the read-in-progress register being cleared.

43. The apparatus of claim 39 further comprising:

means for maintaining a high priority queue and a low priority queue;

means for placing the write request into the low priority queue;

means for writing, in response to receiving a subsequent read request for an address matching an address of the pending write request, the subsequent read request into the low priority queue after the write request and not setting the bit corresponding to the subsequent read request in the read-in-progress register, because the subsequent read request cannot pass the pending write request and so cannot be executed before the pending write request; and

means for loading, in response to receiving a different subsequent read request directed to an address different from the address of the pending write request, the different subsequent read request into the high priority queue and also setting a bit in the read-in-progress register corresponding to the different subsequent read request to cause the pending write request to wait for receipt of the response to the different subsequent write request.

44. The apparatus of claim 43, further comprising:

means for receiving a read request from the low priority queue and transmitting the read request over the split transaction bus, and also asserting a bit in the read-in-progress register that corresponds to the read request.

45. The apparatus of claim 39, further comprising:

means for maintaining a high priority queue and a low priority queue;

means for receiving a read request from the processor; and

means for loading, in response to receiving a conflict bit from the conflict detection logic, the received conflict bit and a tag value identifying the read request into an entry in the low priority queue.

46. The apparatus of claim 45 further comprising:

means for receiving a read request from the processor, placing the read request in the high priority queue, and asserting a bit in the read-in-progress register that corresponds to the read request.

47. The apparatus of claim 46 further comprising:

means for receiving a response to a pending read request; and

means for deasserting, in response to receiving the response to a pending read request, a bit in the read-in-progress register corresponding to the pending read request.

48. The apparatus of claim 47, further comprising:

means for comparing an address of a pending read request with the address of the write request;

means for asserting, in response to the address of the write request matching the address of any pending read request, a bit in a bit mask; and

means for asserting, in response to any bit in the bit mask being asserted, a conflict bit.

49. The apparatus of claim 39 further comprising:

means for maintaining a high priority queue and a low priority queue;

means for servicing a request at the high priority queue before servicing a request at the low priority queue.