METHOD FOR ENABLING MULTI-PROCESSOR SYNCHRONIZATION

• US 20090193279A1
• Filed: 01/29/2009
• Published: 07/30/2009
• Est. Priority Date: 01/30/2008
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Sandbridge Technologies Incorporated (Qualcomm, Inc.)
• Inventors: Srikantiah, Umesh, Balzola, Pablo, Senthilvelan, Murugappan, Kalashnikov, Vitaly, Li, Tak-po, MOUDGILL, Mayan
• Granted Patent: US 8,539,188 B2
• Time in Patent Office: Days
• US Class Current: 713/375
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method for providing at least one sequence of values to a plurality of processors is described. In the method, a sequence generator from one or more sequence generators is associated with a memory location. The sequence generator is configured to generate the at least one sequence of values. One or more read accesses of the memory location are enabled by a processor from the plurality of processors. In response to enabling the read access, the sequence generator is executed so that it returns a first value from the sequence of values to the processor. After executing the sequence generator, the sequence generator is advanced so that the next access generates a second value from the sequence of values. The second value is sequentially subsequent to the first value.

Claims

1. A method for providing at least one sequence of values to a plurality of processors, comprising:

associating a sequence generator from one or more sequence generators with a memory location, the sequence generator being configured to generate the at least one sequence of values;

enabling one or more read accesses of the memory location by a processor from the plurality of processors;

in response to enabling the read access, executing the sequence generator to return a first value from the sequence of values to the processor; and

after executing the sequence generator, advancing the sequence generator so that the next access generates a second value from the sequence of values,

wherein the second value is sequentially subsequent to the first value.

2. The method of claim 1, wherein the sequence generator is an N-bit counter, the sequence of values encompasses {0, 1, . . . , 2^N−

1, 0, 1, . . . , 2<sup>N−

1</sup>, . . . }, and N is an integer.

3. The method of claim 1, further comprising:

enabling a write access of the memory location by a processor from the plurality of processors to store a write value; and

in response to enabling the write access, reconfiguring the sequence generator to advance from a different value of the sequence of values based on the write value.

4. The method of claim 3, wherein:

a read access following the write access returns the write value.

5. The method of claim 3, wherein:

a read access following the write access returns a value sequentially subsequent to the write value.

6. A method executed by a plurality of processors for a plurality of mutexes, comprising:

associating a sequence generator with each mutex, each sequence generator being adapted to generate a value from a sequence of values, starting from a first value;

associating a turn indicator with each mutex, wherein a first value of the turn indicator is initialized to the first value from the sequence of values;

when entering a critical section of code associated with the mutex,

accessing the associated sequence generator to read a second value from the sequence of values, and

waiting until the associated turn indicator equals the said second value from the sequence of values before accessing the critical section of code; and

when exiting the critical section, setting the turn indicator to a third value subsequent to the second value in the sequence of values.

7. The method of claim 6, wherein the turn indicator comprises a plurality of turn indicators, the method further comprising:

when entering the critical section of code, waiting on at least one of the plurality of turn indicators; and

when exiting the critical section of code, setting all of the plurality of turn indicators to the third value in the sequence of values.

8. The method of claim 7, wherein the number of the turn indicators equals the number of the processors.

9. The method of claim 8, wherein the first value is 0.

10. The method of claim 6, wherein:

the second value is greater than the first value by an integer equal to or greater than 1,

the second value is less than an integer, N, and

if the second value is equal to or greater than N, the second value is restarted to the first value.

11. The method of claim 10, wherein:

if the second value is equal to or greater than N, the second value is restarted to 0.

12. The method of claim 11, wherein:

the second value is greater than the first value by 1.

13. The method of claim 7, wherein the turn indicator that a processor accesses is located in memory positions local to the processor.

14. The method of claim 6, wherein each of the plurality of processors is initialized simultaneously.

15. The method of claim 14, wherein each of the plurality of processors operates disjunctively after initialization.

16. The method of claim 6, wherein all of the plurality of processors share common operating attributes.

17. The method of claim 6, wherein at least one of the plurality of processors has operating attributes that differ from operating attributes of others of the plurality of processors.

18. The method of claim 6, wherein the plurality of processors operate in parallel.

19. The method of claim 7, wherein the synchronization generator and the turn indicator have the same bit width.

20. The method of claim of claim 7, wherein all of the plurality of turn indicators are set to the third value simultaneously.