SHARED STORAGE FOR MULTI-THREADED ORDERED QUEUES IN AN INTERCONNECT

• US 20080301708A1
• Filed: 06/01/2007
• Published: 12/04/2008
• 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.
• Granted Patent: US 7,814,243 B2
• Time in Patent Office: Days
• US Class Current: 719/314
• 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 payload of multiple threads between a plurality of cores of an integrated circuit by buffering the payload using a shared storage structure that includes a plurality of order queues and an index to track which thread is assigned to each queue;

guaranteeing each of the order queues 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

increasing, above said minimum, the number of buffer entries that make up any one of the queues for any of the multiple threads being received by the shared storage structure, by borrowing from a shared pool of unused buffer entries on a first-come, first-served basis.

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 order queue.

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

4. The method of claim 1 wherein each of the order queues has the same minimum number of buffer entries.

5. A machine-readable medium having data and instructions stored therein which, when executed by a machine, cause the machine to simulate the method of claim 1.

6. The machine-readable medium of claim 5 wherein the data and instructions are part of a stored electronic design automation (EDA) toolset for use in a system-on-a-chip (SoC) design process.

7. A system comprising:

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

an interconnect to which the data processing elements are coupled, the interconnect to route a plurality of requests and a plurality of responses between the elements,

wherein the interconnect implements a content addressable memory (CAM) structure that is shared storage for a plurality of logical, multi-thread ordered queues that make up entries in the CAM structure and buffer the requests from two or more threads, the responses from two or more threads, or both, wherein each thread has its own unique identifier.

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 first and second fields, the first field identifies a queue through the unique thread identifier, from among the plurality of 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 queue,

the data word containing a portion of a buffered request or response.

9. 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 queue and its associated thread, from among the plurality of queues, and the data word contains a portion of a buffered request or response in the associated thread, and

when the entry is output following a match with an input key, the entry is invalidated and becomes available for re-use by the associated queue or a different queue.

10. The system of claim 8 wherein the CAM entries are managed so that at most one of the plurality of entries matches any accessed key.

11. The system of claim 8 wherein the first field is static for the duration its entry is valid, the entry being invalidated in response to a) an accessed key matching the entry and b) its data word being output.

12. The system of claim 8 wherein the second field is dynamic and changes whenever an accessed key matches an entry that precedes the entry, in queue order, for the queue.

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

14. A machine-readable medium having data and instructions stored therein which, when executed by a machine, cause the machine to generate a representation of the system of claim 7.

15. The machine-readable medium of claim 14 wherein the data and instructions are part of a stored electronic design automation (EDA) toolset for use in a system-on-a-chip (SoC) design process that is to generate the representation of the system.

16. The system of claim 7 wherein the integrated circuit is a system-on-a-chip (SoC) and the interconnect is pipelined to store and move requests and responses in stages through the SoC.

17. An apparatus comprising:

an interconnect for an integrated circuit (IC), the interconnect to transfer payload of multiple threads between a plurality of Intellectual Property (IP) cores of the integrated circuit that are coupled to the interconnect, wherein the interconnect implements a content addressable memory (CAM) structure that is shared storage for a plurality of multiple thread buffers, the CAM structure stores requests that are from two or more threads and that come from an initiator IP core and that are to be routed to a target IP core in the integrated circuit.

18. The apparatus of claim 17 wherein the interconnect comprises an asynchronous multi-threaded ordered queue (MTOQ), the MTOQ being implemented as the combination of a single-threaded asynchronous ordered queue 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.

19. The apparatus of claim 18 wherein the asynchronous multi-threaded ordered queue is a multi-thread FIFO with non-blocking behavior.