Method and apparatus for implementing a relaxed ordering model in a computer system

• US 20030145136A1
• Filed: 01/31/2002
• Published: 07/31/2003
• Est. Priority Date: 01/31/2002
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Gibney, Thomas J., Van Doren, Stephen R., Tierney, Gregory E.
• Application Number:
  US10/066,534
• Publication Number:
  US 20030145136A1
• Time in Patent Office: Days
• US Class Current: 710/3
• CPC Class Codes: G06F 13/1663 Access to shared memory
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency

Abstract

An ordering engine is configured to implement a relaxed ordering consistency model for a stream of I/O transactions initiated in a computer system. The ordering engine examines the relaxed ordering attribute of the transactions in the stream to distinguish payload transactions, which may be processed out of order, from control transaction which must be processed in strict order. The engine preferably organizes the stream of transactions into epochs, where the receipt of a first relaxed order write operation in the stream constitutes the start of an epoch and the receipt of a first strict order operation in the stream constitutes the conclusion of the epoch. The engine is configured to delay the completion of the strict order operation constituting the conclusion of the epoch until all payload write operations issued during the epoch have committed.

Claims

1. An apparatus for imposing relaxed ordering on a stream of read and write transactions from an input/output (I/O) device, the transactions indicating whether relaxed or strict ordering is to be applied, the apparatus comprising:

means for assigning epochs to at least some of the transactions in the stream, such that the receipt of a first relaxed order write transaction in the stream constitutes the start of a given epoch and the receipt of one or more strict order transactions constitutes the conclusion of the given epoch;

means for determining when relaxed order write transactions have reached a commit state in accordance with a predefined consistency model; and

means, responsive to the determining means, for inhibiting retirement of a strict order transaction assigned to the given epoch until all of the relaxed order write transactions assigned to the given epoch have reached the commit state.

2. The apparatus of claim 1 further comprising means for inhibiting retirement of a strict order transaction assigned to a later epoch until all strict order transactions assigned to one or more earlier epochs have reached the commit state in accordance with the predefined consistency model.

3. The apparatus of claim 2 wherein the assigning means comprises:

a relaxed ordering controller; and

an epoch identifier (ID) generator operatively coupled to the relaxed ordering controller and configured to produce epoch ID values, and

upon the start of each epoch, the relaxed ordering controller directs the epoch ID generator to produce an epoch ID for assignment to the relaxed order write and strict order transactions of the respective epoch.

4. The apparatus of claim 3 wherein the assigning means further comprises:

an epoch state machine operatively coupled to the relaxed ordering controller and configured for transition between a last_was_payload state and a last_was_control state, and

the relaxed ordering controller

directs the epoch state machine to transition from the last_was_control state to the last_was_payload state in response to a first relaxed order write transaction in the stream, thereby signaling the start of an epoch, and

directs the epoch state machine to transition from the last_was_payload state to the last_was_control state in response to a first strict order transaction in the stream, thereby signaling the conclusion of an epoch.

5. The apparatus of claim 4 wherein

the inhibiting means comprises a plurality of payload commit pending counters operatively coupled to the relaxed order controller, and

the relaxed ordering controller

assigns a selected payload commit pending counter to each epoch,

increments the selected payload commit pending counter in response to each relaxed order write transaction issued during the respective epoch, and

decrements the selected payload commit pending counter in response to receiving a commit signal corresponding to a relaxed order write transaction issued during the respective epoch.

6. The apparatus of claim 5 wherein

the inhibiting means further comprises a retire queue operatively coupled to the relaxed ordering engine, the retire queue organized as a first-in-first-out (FIFO) queue structure having a head and configured to store transactions,

all strict ordered transactions are stored in the retire queue, and

only the transaction disposed at the head of the retire queue is eligible for retirement.

7. The apparatus of claim 5 further comprising:

means for detecting an insufficient resource condition for processing relaxed order transactions; and

means, responsive to the detecting means, for converting relaxed order transactions to strict order transactions during the insufficient resource condition.

8. The apparatus of claim 7 having a fixed number of payload commit pending counters wherein

the detecting means comprises an epoch counter,

the epoch counter is incremented at the start of each epoch and decremented at the conclusion of each epoch,

means for determining whether the epoch counter equals the fixed number of payload commit pending counters.

9. A system in communicating relationship with an I/O device and a computer memory system, the I/O device configured to issue a stream of memory reference operations, including read and write operations, and to specify the application of relaxed or strict ordering to the memory reference operations, the memory system having an ordering point configured to return commit signals to the system in response to memory reference operations becoming committed, the system comprising:

a relaxed ordering controller;

an epoch identifier (ID) generator operatively coupled to the relaxed ordering engine and configured to produce epoch ID values; and

one or more payload commit pending counters operatively coupled to the relaxed ordering engine, wherein,

the relaxed ordering engine

organizes the stream of memory reference operations from the I/O device into epochs, such that the receipt of a first relaxed order write operation in the stream constitutes the start of an epoch and the receipt of a first strict order operation in the stream constitutes the conclusion of the epoch,

upon the start of each epoch, directs the epoch ID generator to produce an epoch ID value for the respective epoch, and assigns a selected payload commit pending counter to the epoch ID value,

associates the respective epoch ID value with all relaxed order write operations issued during the epoch,

increments the selected payload commit pending counter in response to each relaxed order write operation issued during the epoch,

decrements the selected payload commit pending counter in response to receiving a commit signal corresponding to a relaxed order write operation associated with the respective epoch ID, and

delays completion of the strict order operation constituting the conclusion of the epoch until the selected payload commit pending counter reaches zero, thereby confirming that all relaxed order write operations issued during the epoch have committed.

10. The system of claim 9 wherein the relaxed ordering engine delays completion of a given strict order operation in the stream until commit signals have been received at the system for all earlier issued strict order operations in the stream.

11. The system of claim 10 wherein, for a read operation, completion corresponds to transfer of requested data to the I/O device and, for a write operation, completion corresponds to write-back of written data to the memory system.

12. The system of claim 10 further comprising:

an epoch state machine operatively coupled to the relaxed ordering controller and configured for transition between a last_was_payload state and a last_was_control state, wherein

the relaxed ordering controller

directs the epoch state machine to transition from the last_was_control state to the last_was_payload state in response to a first relaxed order write operation in the stream, thereby signaling the start of an epoch, and

directs the epoch state machine to transition from the last_was_payload state to the last_was_control state in response to a first strict order operation in the stream, thereby signaling the conclusion of an epoch.

13. The system of claim 12 further comprising:

a retire queue operatively coupled to the relaxed ordering engine, the retire queue organized as a first-in-first-out (FIFO) queue structure having a head and configured to store memory reference operations, wherein

all strict ordered memory reference operations are stored in the retire queue, and

only the operation disposed at the head of the retire queue is eligible for completion.

14. The system of claim 13 wherein, if the operation at the head of the retire queue is a control operation, the relaxed ordering controller pops the operation from the head of the retire queue provided that the operation is eligible for completion and the commit signal for the operation has been received.

15. The system of claim 10 further comprising:

an I/O cache having a plurality of cache entries for storing data relating to the memory reference operations issued by the I/O device; and

a prefetch controller coupled to the I/O cache, the prefetch controller configured to prefetch data into the cache without any ordering constraints.

16. The system of claim 15 wherein

relaxed ordering operations requiring prefetching are stored in the retire queue, and

if the operation the head of the retire queue is a relaxed ordering operation, the relaxed ordering engine pops the operation from the head of the retire queue provided that the prefetched data has been received.

17. The system of claim 10 wherein the ordering point generates a commit signal in response to total ordering of each issued memory reference operation at the ordering point such that the commit signal indicates apparent completion of the operation rather than actual completion of the operation.

18. The system of claim 10 wherein

the system is disposed in an input/output processor (IOP) that is part of a symmetrical multiprocessor (SMP) computer system, and

the memory system is a shared memory having a non-uniform memory access (NUMA) architecture.

19. The system of claim 18 wherein the IOP is implemented as an application specific integrated circuit (ASIC).

20. A method for imposing relaxed ordering on a stream of memory reference operations issued by an input/output (I/O) device, including read and write operations, the operations indicating whether relaxed or strict ordering is to be applied, a computer memory system having an ordering point issues commit signals in response to memory reference operations becoming committed, the method comprising the steps of:

organizing the stream of memory reference operations into epochs, such that the receipt of a first relaxed order write operation in the stream constitutes the start of an epoch and the receipt of a first strict order operation in the stream constitutes the conclusion of the epoch;

upon the start of each epoch, producing an epoch ID value for the respective epoch, and assigning a payload commit pending counter to the epoch ID value;

associating the respective epoch ID value with all relaxed order write operations issued during the epoch;

incrementing the payload commit pending counter in response to each relaxed order write operation issued during the epoch;

decrementing the payload commit pending counter in response to receiving a commit signal corresponding to a relaxed order write operation associated with the respective epoch ID; and

delaying completion of the strict order operation constituting the conclusion of the epoch until the selected payload commit pending counter reaches zero, thereby confirming that all relaxed order write operations issued during the epoch have committed.

21. The method of claim 20 wherein the step of delaying further requires receipt of commit signals for all earlier issued strict order operations in the stream.

22. The method of claim 21 further comprising the steps of:

providing a state machine configured to transition between a last_was_payload state and a last_was_control state;

transitioning the state machine from the last_was_control state to the last_was_payload state in response to a first relaxed order write operation in the stream, thereby signaling the start of an epoch; and

transitioning the state machine from the last_was_payload state to the last_was_control state in response to a first strict order operation in the stream, thereby signaling the conclusion of an epoch.

23. The method of claim 21 further comprising the steps of:

providing a retire queue that is organized as a first-in-first-out (FIFO) queue structure having a head;

buffering all strict ordered memory reference operations in the retire queue; and

popping the operation off the head of the retire queue where the operation is eligible for completion and the commit signal for the operation has been received.

24. The method of claim 21 further comprising the steps of:

buffering relaxed ordering operations that require prefetching of data at the retire queue; and

popping a relaxed order operation from the head of the retire queue provided that the prefetched data has been received.

25. The method of claim 20 performed at an I/O processor (IOP) that is part of a symmetrical multiprocessor computer system in which the memory system is a shared memory having a non-uniform memory access (NUMA) architecture.

26. The method of claim 25 wherein the IOP is implemented as an application specific integrated circuit (ASIC).