Method and apparatus for reducing latency of inter-reference ordering in a multiprocessor system

• US 6,108,737 A
• Filed: 10/24/1997
• Issued: 08/22/2000
• Est. Priority Date: 10/24/1997
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Compaq Computer Corporation (HP Inc.)
• Inventors: Steely, Simon C. Jr., Van Doren, Stephen R., Gharachorloo, Kourosh, Sharma, Madhumitra
• Primary Examiner(s): Ray, Gopal C.
• Application Number:
  US08/957,097
• Time in Patent Office: 1,033 Days
• Field of Search: 395/287, 395/200.43, 395/281, 711/147, 711/100, 711/121, 710/107, 710/101, 710/111, 710/51, 710/52, 710/131, 710/113, 710/240, 709/213, 709/100, 709/106, 709/300, 712/214, 370/357, 370/462, 707/10
• US Class Current: 710/107
• CPC Class Codes: G06F 12/0828 with concurrent directory accessing, i.e. handling multiple concurrent coherency transactions
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30047 Prefetch instructions; cache control instructions
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3854 Instruction completion, e.g. retiring, committing or graduating
• CPC Class Codes: G06F 9/3856 Reordering of instructions, e.g. using queues or age tags

Abstract

A mechanism reduces the latency of inter-reference ordering between sets of memory reference operations in a multiprocessor system having a shared memory. The mechanism comprises a commit-signal that is generated by control logic of the multiprocessor system in response to an issued memory reference operation. The commit-signal facilitates inter-reference ordering; moreover, the commit signal indicates the apparent completion of the memory reference operation, rather than actual completion of the operation. The apparent completion of an operation occurs substantially sooner than the actual completion of an operation, thereby improving performance of the multiprocessor system.

Claims

1. Apparatus for reducing latency of inter-reference ordering between memory reference operations of a shared memory multiprocessor system having a consistency model, the system having a plurality of processors, each processor capable of issuing a memory reference operation to the system, the apparatus comprising:

a commit-signal structure generated by control logic of the multiprocessor system in response to each issued memory reference operation, the commit-signal generated substantially sooner than completion of the memory reference operation, the commit-signal indicating apparent completion of the memory reference operation rather than actual completion of the operation;

wherein each processor employs the commit signal to impose inter-reference ordering.

2. The apparatus of claim 1 wherein the consistency model is weak-ordering and wherein inter-reference ordering is imposed by a memory barrier (MB) instruction inserted between sets of the memory reference instructions of a program executed by the issuing processor, the sets of memory reference instructions issued to the system as pre-MB memory reference operations and post-MB memory reference operations.

3. The apparatus of claim 2 wherein ordering of an issued memory reference operation constitutes a commit-event for the issued operation and wherein the commit-signal is transmitted to the issuing processor upon the occurrence of, or after, the commit-event.

4. The apparatus of claim 3 wherein program execution is permitted to proceed past the MB instruction once commit signals for all pre-MB memory reference operations have been received by the issuing processor.

5. The apparatus of claim 4 further comprising a counter of the issuing processor, the processor (i) incrementing the counter upon the issuance of each pre-MB memory reference operation and (ii) decrementing the counter upon receipt of each commit-signal responsive to an issued pre-MB memory reference operation, such that when execution of the program reaches the MB instruction and a value of the counter is zero, program execution is permitted to proceed past the MB instruction.

6. The apparatus of claim 1 wherein the consistency model is sequential consistency and wherein inter-reference ordering is generally imposed by requiring completion of a current memory reference operation prior to issuing a next memory reference operation.

7. The apparatus of claim 6 wherein ordering of an issued memory reference operation constitutes a commit-event for the issued operation and wherein the commit-signal is transmitted to the issuing processor upon the occurrence of, or after, the commit-event.

8. The apparatus of claim 7 wherein receipt of the transmitted commit-signal by the issuing processor constitutes commitment of the issued memory reference operation and wherein the next memory reference operation is permitted to issue once commitment of the current memory reference operation has been received by the issuing processor.

9. Apparatus for reducing the latency of inter-reference ordering between memory reference operations issued by a processor to a symmetric multiprocessing (SMP) node having a shared memory that is distributed among a plurality of processors, each processor having a private cache and a programming interface to the distributed shared memory, the apparatus comprising:

a local switch of the SMP node, the local switch interconnecting the processors and shared memory;

an ordering point coupled to the local switch and configured to totally order the memory reference operations issued to the node; and

a commit-signal structure generated by the ordering point in response to each memory reference operation issued to the node, the commit-signal indicating the apparent completion of the memory reference operation to the processor issuing the operation.

10. The apparatus of claim 9 wherein the ordering point comprises:

an arbiter (Arb) bus coupled to the switch, the Arb bus functioning as a serialization point for the memory reference operations issued to the node; and

a coherence controller coupled to the Arb bus, the coherence controller generating memory reference probes in response to issued memory reference operations.

11. The apparatus of claim 10 wherein the local switch comprises:

a plurality of ports, each coupled to a respective processor via a full-duplex, bi-directional clock forwarded data link;

a plurality of input queues, each associated with a respective port, for receiving memory reference operations issued by its respective processor; and

a plurality of output queues, each associated with a respective port, for receiving the memory reference probes generated by the coherence controller, each of the output queues configured to receive the commit-signal generated by the ordering point, the output queues further configured to transmit the probes and commit-signal to the respective processors in first-in, first-out (FIFO) order.

12. The apparatus of claim 11 wherein the local switch further comprises an arbiter configured to implement an arbitration policy for arbitrating among the input queues to grant access to the Arb bus.

13. The apparatus of claim 12 wherein the arbitration policy is a round-robin algorithm.

14. Apparatus for reducing the latency of inter-reference ordering between memory reference operations issued by a processor to a symmetric multiprocessing (SMP) system comprising a plurality of SMP nodes, each node having a shared memory that is distributed among a plurality of processors, each processor having a private cache and a programming interface to the distributed shared memory, the apparatus comprising:

a hierarchical switch of the SMP system, the hierarchical switch interconnecting the plurality of SMP nodes;

an ordering point of the hierarchical switch configured to atomically multicast and totally order the memory reference operations issued to the system; and

a commit-signal structure generated by the ordering point in response to each memory reference operation issued to the system, the commit-signal comprising one of a plurality of commit-signal types, each type of commit-signal indicating the apparent completion of the memory reference operation to the processor issuing the operation.

15. The apparatus of claim 14 wherein the hierarchical switch comprises:

a plurality of input ports, each coupled to a respective node via a full-duplex, bi-directional clock forwarded link, for receiving memory reference operations issued by a processor of its respective node, the memory reference operations issued as commands by the processor;

a plurality of output ports, each coupled to the respective port via the bi-directional link, for forwarding the commands to at least one SMP node; and

a plurality of input buffers, each associated with a respective input port, for temporarily storing the received commands.

16. The apparatus of claim 15 wherein the hierarchical switch further comprises a plurality of multiplexer circuits having a plurality of inputs and an output, each of input of each multiplexer coupled to a respective input buffer of the hierarchical switch such that a command received from any of the input buffers may be forwarded in any order to any of the output ports.

17. The apparatus of claim 16 wherein the ordering point of the hierarchical switch comprises the input buffers and multiplexer circuits.

18. The apparatus of claim 17 wherein one of the commit-signal types generated by the ordering point of the hierarchical switch comprises a type 1 commit-signal corresponding to a global command issued by a processor to an address that is assigned to a SMP node other than the node on which the issuing processor resides.

19. The apparatus of claim 17 wherein one of the commit-signal types generated by the ordering point of the hierarchical switch comprises a type 2 commit-signal corresponding to a local command issued by a processor to an address that is assigned to the SMP node on which the issuing processor resides, the SMP node comprising a local ordering point for generating external memory reference probes to the address in response to the issued local command, the type 2 commit-signal characterized by generating the external probes and having outstanding probes.

20. The apparatus of claim 17 wherein one of the commit-signal types generated by the ordering point of the hierarchical switch comprises a type 3 commit-signal corresponding to a local command issued by a processor to an address that is assigned to the SMP node on which the issuing processor resides, the SMP node comprising a local ordering point for generating external memory reference probes to the address in response to the issued local command, the type 2 commit-signal characterized by having no generated external probes but having outstanding probes to the address.

21. Apparatus for reducing latency of inter-reference ordering between memory reference operations of a shared memory multiprocessor system having a consistency model, the system having a plurality of processors, each processor capable of issuing a memory reference operation to the system, the apparatus comprising:

a commit-signal structure generated by control logic of the multiprocessor system in response to each issued memory reference operation, the commit-signal generated substantially sooner than completion of the memory reference operation, the commit-signal indicating apparent completion of the memory reference operation rather than actual completion of the operation;

a memory barrier (MB) instruction inserted between sets of the memory reference instructions of a program executed by the issuing processor, the sets of memory reference instructions issued to the system as pre-MB memory reference operations and post-MB memory reference operations to impose inter-reference ordering in cooperation with said commit signal.