On-demand expansion of synchronization primitives

Patent metadata

Field	Value
Publication number	US-2016110283-A1
Application number	US-201414518995-A
Country	US
Kind code	A1
Filing date	Oct 20, 2014
Priority date	Oct 20, 2014
Publication date	Apr 21, 2016
Grant date	—

Abstract

Disclosed are techniques and systems for providing on-demand expansion of a non-cache-aware synchronization primitive to a cache-aware form. The expansion may occur on-demand when it becomes necessary to do so for performance and throughput purposes. Expansion of the synchronization primitive may be based at least in part on a level of cache-line contention resulting from operations on the non-cache-aware synchronization primitive. The synchronization primitive in the expanded (cache-aware) form may be represented by a data structure that allocates individual cache lines to respective processors of a multiprocessor system in which the synchronization primitive is implemented. Once expanded, the cache-aware synchronization primitive may be contracted to its non-cache-aware form.

First claim

What is claimed is:

1 . A method comprising:
providing a non-cache-aware synchronization primitive in a multiprocessor computer system having a shared memory; determining a level of cache-line contention resulting from operations on the non-cache-aware synchronization primitive; and in response to determining that the level of cache-line contention meets or exceeds a threshold, changing the non-cache-aware synchronization primitive to a cache-aware synchronization primitive that allocates individual cache lines of the shared memory to respective processors of the multiprocessor computer system.

2 . The method of claim 1 , wherein the determining the level of cache-line contention comprises measuring a parameter during performance of the operations, the parameter including at least one of a cycle count, a number of InterlockedCompareExchange retries, or a frequency of the operations.

3 . The method of claim 1 , wherein the determining the level of cache-line contention comprises:
collecting statistics for the non-cache-aware synchronization primitive, the statistics comprising measurements of a parameter that are taken during performance of the operations on the non-cache-aware synchronization primitive over a period of time; and calculating a statistical value of the parameter based at least in part on the collected statistics, and wherein the determining that the level of cache-line contention meets or exceeds the threshold comprises comparing the statistical value of the parameter to a baseline value of the parameter that represents a value of the parameter when the operations are performed without the cache-line contention.

4 . The method of claim 3 , wherein the baseline value of the parameter is at least one of: (i) computed by measuring the parameter during performance of one or more of the operations at boot time of the multiprocessor computer system, (ii) statically hard-coded within the multiprocessor computer system; or (iii) configured by an administrator of the multiprocessor computer system.

5 . The method of claim 3 , wherein the statistics further comprise:
a number of exclusive acquires or a number of exclusive releases of the non-cache-aware synchronization primitive over the period of time; and a number of shared acquires or a number of shared releases of the non-cache-aware synchronization primitive over the period of time, wherein the expanding is conditioned on a ratio of the number of exclusive acquires or releases to the number of shared acquires or releases being below a threshold ratio.

6 . The method of claim 1 , wherein the non-cache-aware synchronization primitive is a lock.

7 . The method of claim 1 , wherein the operations comprise interlocked operations associated with acquires or releases of the non-cache-aware synchronization primitive.

8 . The method of claim 1 , wherein the expanding comprises:
setting a transitioning state of the non-cache-aware synchronization primitive; allocating the individual cache lines of the shared memory to the respective processors of the multiprocessor computer system; and changing the transitioning state to an expansion state of the non-cache-aware synchronization primitive.

9 . The method of claim 8 , wherein the setting the transitioning state occurs while at least one thread is holding the non-cache-aware synchronization primitive based on a shared acquire from the at least one thread.

10 . A computer-readable memory executable by one or more of a plurality of processors of a multiprocessor system, the computer-readable memory storing a data structure of a non-cache-aware synchronization primitive and computer-executable instructions that, when executed by at least one of the one or more processors of the multiprocessor system, perform the following acts:
determining a level of cache-line contention resulting from operations on the non-cache-aware synchronization primitive; and in response to determining that the level of cache-line contention meets or exceeds a threshold, changing the non-cache-aware synchronization primitive to a cache-aware synchronization primitive that allocates individual cache lines of the shared memory to respective processors of the multiprocessor computer system.

11 . The computer-readable memory of claim 10 , the acts further comprising contracting the cache-aware synchronization primitive to revert to the non-cache-aware synchronization primitive after a period of time has lapsed since the expanding.

12 . The computer-readable memory of claim 11 , the acts further comprising waiting to free the shared memory of the allocated cache lines until there are no threads holding the cache-aware synchronization primitive.

13 . The computer-readable memory of claim 12 , the acts further comprising:
performing an operating system interrupt on a plurality of processors of the multiprocessor computer system; and checking whether there are any threads holding the cache-aware synchronization primitive.

14 . The computer-readable memory of claim 11 , the acts further comprising:
determining whether any threads are pending acquisition of an allocated cache line of the cache-aware synchronization primitive, the determining being based at least in part on (i) checking a list of in-progress lock acquires for individual ones of the threads, or (ii) checking whether a thread-local bit is set for individual ones of the threads; and refraining from contracting if the determining indicates that there is at least one thread that is about to acquire the allocated cache line of the cache-aware synchronization primitive.

15 . The computer-readable memory of claim 11 , wherein the contracting is further conditioned on a number of cache-aware synchronization primitives on the multiprocessor computer system exceeding a threshold number of cache-aware synchronization primitives.

16 . The computer-readable memory of claim 11 , the acts further comprising, before the contracting, collecting statistics for the cache-aware synchronization primitive, the statistics comprising:
a number of exclusive acquires or a number of exclusive releases of the cache-aware synchronization primitive over the period of time; and a number of shared acquires or a number of shared releases of the cache-aware synchronization primitive over the period of time, wherein the contracting is further conditioned on a ratio of the number of shared acquires or releases to the number of exclusive acquires or releases being below a threshold ratio.

17 . The computer-readable memory of claim 16 , wherein the number of shared acquires or shared releases of the cache-aware synchronization primitive is maintained per cache line of the cache-aware synchronization primitive.

18 . A multiprocessor system comprising:
a plurality of processors; and a shared memory comprising a plurality of cache lines accessible by the plurality of processors, the shared memory storing an operating system and a data structure of a non-cache-aware synchronization primitive, wherein the operating system includes logic to perform the following acts:
determine a level of cache-line contention resulting from operations on the non-cache-aware synchronization primitive; and
in response to determining that the level of cache-line contention meets or exceeds a threshold, change the non-cache-aware synchronization primitive to a cache-aware synchronization primitive that allocates individual ones of the cache lines of the shared memory to respective processors of the plurality of processors.

Assignees

• Microsoft Corp

Inventors

• Iyigun Mehmet
• Bak Yevgeniy
• Kleynhans Christopher Peter
• Raza Syed Aunn Hasan
• Ootjers Thomas James
• Singh Neeraj Kumar

Classifications

• G06F12/0871 Primary

  Allocation or management of cache space · CPC title

• G06F12/0842

  for multiprocessing or multitasking · CPC title

• G06F12/084 Primary

  with a shared cache · CPC title

• G06F2212/281

  Single cache · CPC title

• G06F12/0893

  Caches characterised by their organisation or structure · CPC title