Efficient, scalable and high performance mechanism for handling IO requests

• US 8,001,283 B2
• Filed: 03/12/2008
• Issued: 08/16/2011
• Est. Priority Date: 03/12/2008
• Status: Active Grant

• Current Assignee: ARM Finance Overseas Limited (SoftBank Group Corp.)
• Original Assignee: MIPS Technologies Incorporated (Wave Computing, Inc.)
• Inventors: Lee, William, Berg, Thomas Benjamin
• Primary Examiner(s): PEYTON, TAMMARA R
• Application Number:
  US12/047,257
• Publication Number:
  US 20090234987A1
• Time in Patent Office: 1,252 Days
• Field of Search: 710/5, 710/8, 710/46, 711/119, 711/141, 711/144, 711/146
• US Class Current: 710/5
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups

Abstract

A system, apparatus and method for managing input/output requests in a multi-processor system is disclosed. An IO coherence unit includes an IO request handler, a variable size transaction table, and an IO response handler. The size of the transaction table varies according to the number of pending IO requests. The IO request handler stores information about pending IO requests in the transaction table to establish an order among related requests and to permit out-of-order handling of unrelated requests. The IO response handler tracks responses to the IO requests and updates the information in the transaction table. The IO coherence unit returns responses to requesting devices in compliance with device ordering requirements.

Claims

1. An input/output (IO) coherence unit for use in a multiprocessor system, the IO coherence unit comprising:

an IO request handler configured to receive pending IO requests from a plurality of IO devices and to determine a next IO request for processing by the multiprocessor system;

a transaction table configured to store information about the pending IO requests such that the size of the transaction table varies according to the number of the pending IO requests,

wherein the IO request handler allocates entries in the transaction table and stores information about pending IO requests to establish an order among pending IO requests having a same identifier; and

an IO response handler configured to receive a response to a pending IO request and to update an entry in the transaction table corresponding to the response, the IO response handler configured to determine an order of responses in accordance with the information in the transaction table,

wherein the IO coherence unit returns the responses to the plurality of IO devices in the order determined by the IO response handler.

2. The input/output coherence unit of claim 1 wherein the IO request handler converts a pending IO request that is a multi-cacheline read request into a plurality of single cacheline read requests and allocates entries in the transaction table for each of the single cacheline read requests.

3. The input/output coherence unit of claim 2 wherein the IO request handler allocates buffers to store read data units corresponding to each single cacheline read request for which an entry is allocated in the transaction table.

4. The input/output coherence unit of claim 1 wherein the IO request handler converts a pending IO request that is a multi-cacheline write request into a plurality of single cacheline write requests and allocates a single entry in the transaction table for the multi-cacheline write request.

5. The input/output coherence unit of claim 1 wherein the IO request handler processes pending IO requests having different identifiers in a parallel fashion and processes IO requests having the same identifier in the order they are received.

6. The input/output coherence unit of claim 1 wherein the transaction table comprises a first transaction table and a second transaction table, and wherein the IO request handler determines a request type for each pending IO request and stores read requests in the first transaction table and write requests in the second transaction table.

7. The input/output coherence unit of claim 6 wherein each pending IO request includes a thread identifier, and wherein the IO request handler searches the first and second transaction tables for the thread identifier of a received IO request and associates the received IO request with IO requests in the first and second transaction tables using the thread identifier.

8. The input/output coherence unit of claim 7 wherein the first and second transaction tables comprise linked lists of pending IO requests and the IO request handler associates the received IO request with the pending IO requests by adding it to the tail of a linked list corresponding to its thread identifier.

9. The input/output coherence unit of claim 7 wherein IO response handler detects that a pending IO request is completed when a predetermined number of responses corresponding to the pending IO request are received.

10. The input/output coherence unit of claim 9 wherein the IO response handler returns a response to an IO device for a completed IO write request when the completed IO request becomes the head of its respective linked list.

11. The input/output coherence unit of claim 8 wherein the IO response handler returns data units corresponding to an IO read request to an IO device in the plurality of IO devices when the IO read request becomes the head of its respective linked list.

12. The input/output coherence unit of claim 9 wherein the IO response handler updates the linked list of pending IO requests when a completed 10 request becomes the head of the linked list and removes the entry for the completed 10 request from the first or second transaction table.

13. The input/output coherence unit of claim 1 wherein the pending IO requests include read requests and write requests, and wherein each pending write request comprises a number of acknowledgements and each pending read request comprises a number of data units.

14. The input/output coherence unit of claim 13 wherein the IO response handler updates the number of acknowledgments for a pending write request and the number of data units for a pending read request each time a response is received for the pending write request and the pending read request respectively.

15. The input/output coherence unit of claim 6, further comprising:

an allocation manager configured to allocate an entry for a received IO request in the first transaction table if the received request is a read request and to allocate an entry in the second transaction table if the received request is a write request,

wherein the IO request handler stalls processing of the received IO request if the allocation manager is unable to allocate an entry for the received request in its respective transaction table.

16. The input/output coherence unit of claim 1, further comprising:

a first input port coupled to the IO request handler for receiving a serialized stream of read and write requests from the plurality of IO devices;

a second input port for receiving data corresponding to write requests received at the first IO port,

wherein, if the next IO request is a write request, the IO request handler determines if write data corresponding to the next IO request is received at the second port and suspends the next IO request if it is determined that the write data is not received.

17. A method of maintaining coherence among input/output (JO) requests in a multiprocessor system, the method comprising:

receiving pending IO requests from a plurality of IO devices;

allocating entries in a transaction table for the pending IO requests such that a size of the transaction table varies according to the number of the pending IO requests;

storing information about the pending IO requests in the transaction table, including information for establishing an order among pending IO requests having a same identifier;

determining a next IO request for processing by the multiprocessor system from among the pending IO requests;

receiving a response to a pending IO request;

updating an entry in the transaction table corresponding to the response;

determining an order for returning responses to the plurality of IO devices in accordance with information stored in the transaction table; and

returning responses to the plurality of IO devices in the order determined from the transaction table.

18. The method of claim 17 wherein the transaction table includes a first transaction table and a second transaction table, the method further comprising:

detecting a request type for a pending IO request;

allocating an entry in the first transaction table if the pending IO request is detected as being a read request;

allocating an entry in the second transaction table if the pending IO request is detected as being a write request; and

storing information about the pending IO request in the entry allocated for that IO request.

19. The method of claim 17, further comprising:

converting a pending IO request that is a multi-cacheline read request into a plurality of single cacheline read requests;

allocating entries in the transaction table for each of the single cacheline read requests; and

storing information about the single cacheline read requests in the entries that are allocated.

20. The method of claim 19, further comprising allocating buffers to store read data units corresponding to each single cacheline read request for which an entry is allocated in the transaction table.

21. The method of claim 17, further comprising:

processing pending IO requests having different identifiers in a parallel fashion; and

processing pending IO requests having the same identifier in the order they are received.

22. The method of claim 18 wherein each pending IO request includes a thread identifier, the method further comprising:

searching the first and second transaction tables for the thread identifier of a received IO request; and

associating the received IO request with pending IO requests using the thread identifier.

23. The method of claim 22 wherein the first and second transaction tables comprise linked lists of pending IO requests, and wherein associating the received IO request with the pending IO requests comprises adding the received IO request to the tail of a linked list corresponding to its thread identifier.

24. The method of claim 22, further comprising:

detecting that a pending IO request is completed when a predetermined number of responses corresponding to the pending IO request are received.

25. The method of claim 24, further comprising:

returning a response to an IO device for a completed IO request when the completed IO request becomes the head of its respective linked list.

26. The method of claim 24, further comprising:

updating the linked list of pending IO requests when a completed IO request becomes the head of the linked list; and

removing the entry for the completed IO request from the first transaction table.

27. The method of claim 17 wherein the pending IO requests include read requests and write requests, and wherein each pending write request comprises a number of acknowledgements and each pending read request comprises a number of data units.

28. The method of claim 27, further comprising:

updating the number of acknowledgments for a pending read write request and updating the number of read units for a pending read request each time a response is received for the pending write request and the pending read request respectively.

29. The method of claim 17, further comprising:

stalling receipt of IO requests if an entry in the transaction table cannot be allocated for a pending IO request.

30. The method of claim 17, further comprising:

receiving write data corresponding to each pending IO request that is a write request; and

stalling processing of the next IO request if its corresponding write data is not received.

31. An input/output (JO) coherence unit for use in a multiprocessor system, the IO coherence unit comprising:

an IO request handler configured to receive pending IO requests from a plurality of IO devices and to determine a next IO request for processing by the multiprocessor system;

variable-size first and second transaction tables configured to store information about the pending IO requests, including one or more linked list data structures, such that the combined size of the transaction tables varies according to the number of the pending IO requests,

wherein the IO request handler detects a type of each pending IO request and allocates an entry in the first transaction table for a pending IO request that is detected as being a read request or the second transaction table for a pending IO request that is detected as being a write request; and

an IO response handler configured to receive a response to a pending IO request and to update the linked list data structure corresponding to the response, the IO response handler further configured to determine an order of responses in accordance with the information in the first and second transaction tables.