Shared storage for multi-threaded ordered queues in an interconnect

• US 8,166,214 B2
• Filed: 01/08/2010
• Issued: 04/24/2012
• Est. Priority Date: 06/01/2007
• Status: Active Grant

• Current Assignee: META Platforms Technologies LLC (Meta Platforms, Inc. (f/k/a Facebook, Inc.))
• Original Assignee: Sonics Incorporated (Meta Platforms, Inc. (f/k/a Facebook, Inc.))
• Inventors: Hamilton, Stephen W.
• Primary Examiner(s): Lee, Chun-Kuan
• Assistant Examiner(s): ABAD, FARLEY J
• Application Number:
  US12/684,627
• Publication Number:
  US 20100115196A1
• Time in Patent Office: 837 Days
• Field of Search: 710/52, 710/54, 710/57, 326/56, 709/234, 365/189.05, 711/118
• US Class Current: 710/52
• CPC Class Codes: G06F 13/4027 using bus bridges G06F13/4022 takes precedence
• CPC Class Codes: G06F 9/466 Transaction processing

Abstract

In one embodiment, payload of multiple threads between intellectual property (IP) cores of an integrated circuit are transferred, by buffering the payload using a number of order queues. Each of the queues is guaranteed access to a minimum number of buffer entries that make up the queue. Each queue is assigned to a respective thread. A number of buffer entries that make up any queue is increased, above the minimum, by borrowing from a shared pool of unused buffer entries on a first-come, first-served basis. In another embodiment, an interconnect implements a content addressable memory (CAM) structure that is shared storage for a number of logical, multi-thread ordered queues that buffer requests and/or responses that are being routed between data processing elements coupled to the interconnect. Other embodiments are also described and claimed.

Claims

1. A method for operating an interconnect, comprising:

transferring communication transaction traffic from multiple threads between a plurality of cores of an integrated circuit by buffering the communication transaction traffic using a shared storage structure in the interconnect that implements a plurality of ordered queues and an index to track which buffer entries are assigned to queues in the shared storage structure;

guaranteeing a minimum number of buffer entries to at least a first ordered queue of the ordered queues for use by a thread that is assigned to the first ordered queue; and

borrowing one or more buffer entries from a shared pool of uncommitted buffer entries on a first-come, first-served basis to increase a size of the first ordered queue above the guaranteed minimum number of buffer entries, and the buffer entries for at least the shared pool are tracked by the index.

2. The method of claim 1 wherein each entry in the shared pool of buffer entries is a memory block that is not statically allocated to a given ordered queue.

3. The method of claim 1 wherein the ordered queues are FIFOs.

4. A non-transitory machine-readable medium having data and instructions of an Electronic Design Automation (EDA) toolset used in a System-on-a-Chip design process stored thereon, which, when executed by a machine, cause the machine to perform the operations in claim 1.

5. The method of claim 1, wherein the shared storage structure implemented in the interconnect is a Content Addressable Memory (CAM) structure, and the interconnect includes at least one or more agent interfaces.

6. A system, comprising:

an integrated circuit having one or more data processing elements and one or more memory storage elements;

an interconnect to which the data processing elements are coupled, the interconnect to route communication transaction traffic between the data processing elements and the one or more memory storage elements;

a shared storage structure implemented by the interconnect that buffers the communication transaction traffic between the one or more data processing elements and the one or more memory storage elements and the shared storage structure includes a plurality of ordered queues and an index to track which buffer entries are assigned to queues in the shared storage structure, where each data processing element may contain one or more threads, and where one or more of the ordered queues is guaranteed access to a minimum number of buffer entries that make up the queue, for use by the thread that is assigned to the queue; and

wherein the minimum number of buffer entries that make up any one of the queues is increased above the minimum, for any of the multiple threads using the shared storage structure, by borrowing from a shared pool of unused buffer entries from one or more of the queues on a first-come, first-served basis, and the buffer entries for at least the shared pool are tracked by the index.

7. The system of claim 6, wherein the communication transaction traffic routed on the interconnect includes a plurality of requests and a plurality of responses routed between the data processing elements and the one or more memory storage elements;

and

the shared storage structure implemented in the interconnect is a Content Addressable Memory (CAM) structure that has the ordered queues with entries in the CAM structure and buffers at least the requests from two or more threads from the data processing elements, the responses from two or more threads from the memory storage elements, or both.

8. The system of claim 7, wherein the CAM structure comprises a plurality of CAM entries, each of the entries has a key and a data word:

the key having at least first and second fields, the first field identifies a first ordered queue through a unique thread identifier associated with a first thread, from among the plurality of ordered queues, to which its entry is currently assigned, and the second field represents how many other entries precede this entry, in queue order, for the first ordered queue; and

the data word contains a portion of a buffered request or response, wherein the CAM entries are managed so that at most one of the plurality of CAM entries matches any accessed key.

9. The system of claim 8, wherein the first field identifying the first ordered queue through the unique thread identifier is static for a duration of time its CAM entry is valid, and the CAM entry becomes invalidated in response to an accessed key matching the CAM entry and its data word being output.

10. The system of claim 8, wherein the second field representing how many other entries precede this CAM entry in queue order is dynamic and changes whenever an accessed key matches an entry that precedes this CAM entry, in queue order, for the first ordered queue.

11. The system of claim 7, wherein the CAM structure comprises a plurality of CAM entries, each of the entries has a key and a data word, the key identifies an associated ordered queue and its associated thread, from among the plurality of ordered queues, and the data word contains a portion of a buffered request or response in the associated thread, and when a first CAM entry is output following a match with an input key, the first CAM entry is invalidated and becomes available for reuse by the associated ordered queue or a different ordered queue.

12. The system of claim 7, wherein a thread number is assigned to the first field when its CAM entry is written, and does not change as long as the CAM entry is in use.

13. The system of claim 7, wherein the minimum number of buffer entries in the CAM structure is a fixed number of buffer entries for each thread that is assigned to the CAM structure, and the shared pool of unused buffer entries is used on the first-come, first-served basis by any of the threads assigned to the CAM after the allotted fixed number of buffer entries assigned for that thread has been exceeded.

14. A non-transitory machine-readable medium having data and instructions of an Electronic Design Automation (EDA) toolset used in a System-on-a-Chip design process stored thereon, which, when executed by a machine, cause the machine to generate a representation of the system of claim 6.

15. The system of claim 6, wherein the shared storage comprises an asynchronous Multi-Threaded Ordered Queue (MTOQ), the MTOQ being implemented as the combination of a single-threaded asynchronous ordered queues whose read port feeds a write port of a multi-threaded synchronous ordered queue in which the plurality of multiple thread buffers are implemented using the CAM.