Technique to perform concurrent updates to a shared data structure

• US 20070027870A1
• Filed: 08/01/2005
• Published: 02/01/2007
• Est. Priority Date: 08/01/2005
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Nguyen, Anthony, Kim, Daehyun, Smelyanskiy, Mikhail, Lee, Victor
• Granted Patent: US 7,350,036 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0806 Multiuser, multiprocessor or multiprocessing cache systems
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A technique to perform concurrent updates to a shared data structure. At least one embodiment of the invention concurrently stores copies of a data structure within a plurality of local caches, updates the local caches with a partial result of a computation distributed among a plurality of processing elements, and returns the partial results to combining logic in parallel, which combines the partial results into a final result.

Claims

1. An apparatus comprising:

a plurality of processing elements to compute a plurality of partial results;

a first logic to receive the plurality of partial results in parallel and combine the partial results into a final result.

2. The apparatus of claim 1 further comprising a plurality of local memories, each corresponding to one of the plurality of processing elements.

3. The apparatus of claim 2 further comprising a main memory to store a data structure in which the final result is to be stored.

4. The apparatus of claim 3, wherein each of the plurality of local memories are to store a copy of the data structure concurrently, in which one of the plurality of partial results is to be stored.

5. The apparatus of claim 1 wherein the first logic is within a memory controller to couple the plurality of processing elements to a main memory.

6. The apparatus of claim 1 wherein the first logic is within at least one of the plurality of processing elements.

7. The apparatus of claim 1 wherein the plurality of processing elements are processing cores within a multi-core processor.

8. The apparatus of claim 1 wherein the plurality of processing elements are each within a processor within a multi-processor computing system.

9. A system comprising:

a main memory to store an instruction to be performed by a plurality of processing elements;

a plurality of processing elements to generate a plurality of partial results of the instruction in parallel;

a first logic to receive the plurality of partial results in parallel and combine the plurality of partial results into a final result to be stored in the main memory;

10. The system of claim 9 further comprising a plurality of local memories corresponding to the plurality of processing elements to store a copy of the data structure concurrently.

11. The system of claim 10 further comprising a plurality of buffers to interface to couple local memories and the main memory.

12. The system of claim 11 wherein the first logic is to provide a copy of the data structure to each of the plurality of processing elements.

13. The system of claim 9 wherein the first logic is within at least one of the plurality of processing elements.

14. The system of claim 9 wherein the first logic is within a memory controller to couple the plurality of processing elements to the main memory.

15. The system of claim 9 wherein the plurality of processing elements are processing cores within a multi-core processor.

16. The system of claim 9 wherein the plurality of processing elements are each within a processor within a multi-processor computing system.

17. The system of claim 11 wherein the buffers each comprise a level 2 (L2) cache memory.

18. The system of claim 10 wherein the plurality of local memories each comprise a level 1 (L1) cache.

19. A method comprising:

detecting a task that will use multiple processing elements to compute a number of partial results to be reduced to a combined result;

concurrently storing a plurality of copies of a data structure within a plurality of local memories corresponding to the multiple processing elements;

updating the plurality of copies of the data structure with the plurality of partial results.

20. The method of claim 19 further comprising combining the updated plurality of copies of the data structure in parallel.

21. The method of claim 20 further comprising storing the combined result into a main memory.

22. The method of claim 21 wherein the task is indicated by an instruction type within a program to be executed.

23. The method of claim 22 wherein the task is indicated by an access to a range of memory addresses.

24. The method of claim 23, wherein the combining is performed by a memory controller coupled to the plurality of processing elements.

25. The method of claim 24, wherein the combining is performed by at least one of the processing elements.

26. A processor comprising:

a shared cache to store a data structure;

a plurality of local caches to concurrently store and update a plurality of copies of the data structure;

a memory controller to concurrently receive the updated plurality of copies of the data structure and to combine the updated plurality of copies of the data structure into a final result.

27. The processor of claim 26 further comprising a plurality of processing cores coupled to the plurality of local caches to generate a plurality of partial results in response to executing tasks in parallel associated with an instruction.

28. The processor of claim 27 further comprising detection logic to detect whether the instruction is to be performed by the plurality of processing elements in parallel.

29. The processor of claim 28 wherein the detection logic is to detect whether the instruction is a reduction instruction.

30. The processor of claim 29 wherein the detection logic is to detect the address range to be accessed by the instruction.