Accelerator for multi-processing system and method

• US 8,566,828 B2
• Filed: 10/15/2004
• Issued: 10/22/2013
• Est. Priority Date: 12/19/2003
• Status: Active Grant

• Current Assignee: STMicroelectronics Incorporated (STMicroelectronics NV)
• Original Assignee: STMicroelectronics Incorporated (STMicroelectronics NV)
• Inventors: Pilkington, Charles E.
• Primary Examiner(s): KAWSAR, ABDULLAH AL
• Application Number:
  US10/967,059
• Publication Number:
  US 20050149937A1
• Time in Patent Office: 3,294 Days
• Field of Search: 718/1, 718/100, 718/101, 718/102, 718/103, 718/104, 718/105, 718/106, 718/107, 718/108
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A processing system includes a plurality of processors capable of executing a plurality of threads and supporting at least one of hardware context switching and software context switching. The processing system also includes a hardware concurrency engine coupled to the plurality of processors. The concurrency engine is capable of managing a plurality of concurrency primitives that coordinate execution of the threads by the processors. The concurrency primitives could represent objects, and the processors may be capable of using the objects by reading from and/or writing to addresses in an address space associated with the concurrency engine. Each address may encode an object index identifying one of the objects, an object type identifying a type associated with the identified object, and an operation type identifying a requested operation involving the identified object.

Claims

1. A processing system comprising:

a plurality of processors configured to execute a plurality of threads and to support context switching; and

a hardware concurrency engine coupled to the plurality of processors, the concurrency engine configured to manage a plurality of concurrency primitives that coordinate execution of the threads by the plurality of processors,

wherein each of the plurality of concurrency primitives comprises a concurrency object used to support various coordination functions performed by the concurrency engine; and

wherein the plurality of processors are configured to use the concurrency primitives by reading from and writing to addresses in an address space associated with the concurrency engine, wherein each address encodes an object index identifying one of the concurrency objects, an object type identifying a type associated with the identified concurrency object, and an operation type identifying a requested operation involving the identified concurrency object using bit variables.

2. The processing system of claim 1, wherein the plurality of concurrency primitives comprises at least one of:

a semaphore, a queue, a counter, a timer, a monitor, a condition, a deferred condition, and a timeout condition.

3. The processing system of claim 1, wherein the plurality of processors are configured to use the concurrency primitives by at least using concurrency control instructions in an instruction set architecture of at least one of the plurality of processors.

4. The processing system of claim 1, wherein the concurrency engine comprises:

a command decoder configured to decode requests from the plurality of processors;

a request queue configured to store the decoded requests;

a command processor configured to execute operations associated with the decoded requests, the operations involving at least some of the concurrency objects;

a response queue configured to store results from the execution of the operations;

a response formatter configured to encode the results;

a message passing engine configured to receive the requests from the plurality of processors over a network and to communicate the results to the plurality of processors over the network; and

a memory configured to store information associated with the threads, the concurrency objects, and queues corresponding to the concurrency objects.

5. The processing system of claim 1, wherein the concurrency engine is further configured to schedule execution of the threads by the plurality of processors.

6. The processing system of claim 5, wherein the concurrency engine is configured to schedule execution of the threads by at least one of:

adjusting a thread priority for at least one of the threads;

enabling and disabling execution of at least one of the threads;

altering at least one of a power and a clock speed of at least one of the plurality of processors;

gating a clock signal of at least one of the plurality of processors;

providing control signals to a thread scheduler in at least one of the plurality of processors;

providing control signals to load/store logic in at least one of the plurality of processors;

stalling at least one of a read acknowledgement and a write acknowledgement destined for at least one of the plurality of processors; and

providing at least one of an interrupt and an exception to at least one of the plurality of processors.

7. The processing system of claim 6, wherein the concurrency engine is configured to enforce concurrency semantics when managing the concurrency primitives, the semantics associated with at least one of:

mutual exclusion, monitors, waiting and signaling conditions, timeout conditions, deferred conditions, priority elevation to avoid priority inversion in the monitors, priority queues, and operation ordering.

8. The processing system of claim 1, wherein the concurrency engine is further configured to maintain thread descriptors for the threads, maintaining thread parent/child trees, and performing thread fork and thread join operations.

9. The processing system of claim 1, further comprising:

at least one memory;

at least one programmable hardware processing engine;

at least one interface to an external device; and

a network coupling the plurality of processors, the concurrency engine, the memory, the hardware processing engine, and the interface.

10. The processing system of claim 9, wherein the plurality of processors, the concurrency engine, the memory, the hardware processing engine, the interface, and the network comprise a system on a chip.

11. The processing system of claim 1, wherein the plurality of processors comprises homogenous processors in a symmetric multi-processing arrangement.

12. A method comprising:

executing a plurality of threads using a plurality of processors that support context switching;

managing a plurality of concurrency primitives that coordinate execution of the threads by the plurality of processors using a hardware concurrency engine coupled to the plurality of processors; and

reading from and writing, the plurality of processors, to addresses in an address space associated with the concurrency engine to use the concurrency primitives,

wherein each of the plurality of concurrency primitives comprises a concurrency object used to support various coordination functions performed by the concurrency engine; and

wherein each address encodes an object index identifying one of the concurrency objects, an object type identifying a type associated with the identified concurrency object, and an operation type identifying a requested operation involving the identified concurrency object using bit variables.

13. The method of claim 12, wherein the plurality of concurrency primitives comprises at least one of:

a semaphore, a queue, a counter, a timer, a monitor, a condition, a deferred condition, and a timeout condition.

14. The method of claim 12, wherein managing the concurrency primitives comprises allowing the plurality of processors to use the concurrency primitives by at least using concurrency control instructions in an instruction set architecture of at least one of the plurality of processors.

15. The method of claim 14, wherein the concurrency engine comprises:

a command decoder configured to decode requests from the plurality of processors;

a request queue configured to store the decoded requests;

a command processor configured to execute operations associated with the decoded requests, the operations involving at least some of the concurrency objects;

a response queue configured to store results from the execution of the operations;

a response formatter configured to encode the results;

a message passing engine configured to receive the requests from the plurality of processors over a network and to communicate the results to the plurality of processors over the network; and

a memory configured to store information associated with the threads, the concurrency objects, and queues corresponding to the concurrency objects.

16. The method of claim 12, further comprising scheduling execution of the threads by the plurality of processors using the concurrency engine.

17. The method of claim 16, wherein scheduling execution of the threads comprises at least one of:

adjusting a thread priority for at least one of the threads;

enabling and disabling execution of at least one of the threads;

altering at least one of a power and a clock speed of at least one of the plurality of processors;

gating a clock signal of at least one of the plurality of processors;

providing control signals to a thread scheduler in at least one of the plurality of processors;

providing control signals to load/store logic in at least one of the plurality of processors;

stalling at least one of a read acknowledgement and a write acknowledgement destined for at least one of the plurality of processors; and

providing at least one of an interrupt and an exception to at least one of the plurality of processors.

18. The method of claim 12, further comprising maintaining thread descriptors for the threads, maintaining thread parent/child trees, and performing thread fork and thread join operations using the concurrency engine.

19. A hardware concurrency engine configured to manage a plurality of concurrency primitives that coordinate execution of threads by a plurality of processors, the concurrency engine comprising:

a command decoder configured to decode requests from the plurality of processors;

a command processor configured to execute operations associated with the decoded requests;

a response formatter configured to encode results from the execution of the operations; and

a memory configured to store information associated with a plurality of concurrency objects that represents the concurrency primitives and support various coordination functions performed by the concurrency engine, each operation executed by the command processor involving at least one of the concurrency objects, each request from the plurality of processors to use the concurrency primitives comprising at least one of a read operation and a write operation involving an address in an address space associated with the concurrency engine, the address encoding an object index identifying one of the concurrency objects, an object type identifying a type associated with the identified concurrency object, and an operation type identifying a requested operation involving the identified concurrency object using bit variables.

20. The concurrency engine of claim 19, further comprising:

a request queue Previously Presented configured to store the decoded requests before the decoded requests are provided to the command processor;

a response queue Previously Presented configured to store the results before the results are provided to the response formatter; and

a message passing engine Previously Presented configured to receive the requests from the plurality of processors over a network and Previously Presented-to communicate the encoded results to the plurality of processors over the network.

21. The concurrency engine of claim 20, wherein the command decoder, the command processor, the response formatter, the request queue, the response queue, and the message passing engine comprise at least one of:

an application-specific integrated circuit, a field programmable gate array, and a sea of gates.

22. An apparatus comprising:

at least one of;

an input device and an interface to the input device, the input device configured to provide input data;

at least one of;

an output device and an interface to the output device, the output device operable to receiving output data; and

a processing system configured to receive the input data and to generate the output data, the processing system comprising;

a plurality of processors configured to execute a plurality of threads; and

a hardware concurrency engine coupled to the plurality of processors, the concurrency engine configured to manage a plurality of concurrency primitives that coordinate execution of the threads by the plurality of processors,

wherein the concurrency engine comprises a memory configured to store information associated with a plurality of concurrency objects that represents the concurrency primitives and support various coordinating functions performed by the concurrency engine, each operation executed by the plurality of processors involving at least one of the concurrency objects, each request from the plurality of processors to use the concurrency primitives comprising at least one of a read operation and a write operation involving an address in an address space associated with the concurrency engine, the address encoding an object index identifying one of the concurrency objects, an object type identifying a type associated with the identified concurrency object, and an operation type identifying a requested operation involving the identified concurrency object using bit variables.

23. The apparatus of claim 22, wherein:

the apparatus comprises a mobile telephone;

the at least one of an input device and an interface to the input device comprises a keypad and a microphone; and

the at least one of an output device and an interface to the output device comprises a display and a speaker.

24. The apparatus of claim 22, further comprising:

an antenna configured to at least one of;

receive wireless signals and transmit wireless signals; and

a wireless interface configured to convert received signals into data suitable for processing and to convert data into signals suitable for transmission.

25. The apparatus of claim 22, wherein:

the apparatus is coupled to a network; and

the processing system is configured to perform at least one of packet forwarding and traffic management.

26. The apparatus of claim 22, wherein the concurrency engine comprises:

a command decoder configured to decode requests from the plurality of processors;

a command processor configured to execute operations associated with the decoded requests; and

a response formatter configured to encode results from the execution of the operations.

27. A processor comprising:

an instruction set supporting a plurality of instructions for execution;

an embedded memory configured to store instructions to be executed, the instructions to be executed implementing at least one thread; and

a hardware concurrency engine configured to manage a plurality of concurrency primitives that coordinate execution of a plurality of threads by the processor and at least one additional processor,

wherein each of the plurality of concurrency primitives comprises a concurrency object used to support various coordination functions performed by the concurrency engine; and

wherein the processor is configured to use the concurrency primitives by reading from and writing to addresses in an address space associated with the concurrency engine, each address encoding an object index identifying one of the concurrency objects, an object type identifying a type associated with the identified concurrency object, and an operation type identifying a requested operation involving the identified concurrency object using bit variables.

28. The processor of claim 27, wherein:

the processor is configured to use the concurrency primitives by at least using concurrency control instructions in the instruction set of the processor.