In this work, we analyze the e ciency of atomic operations compare-and-swap (CAS), fetch-and-add (FAA), swap (SWP), load and store on modern multicore processors. These operations implemented in hardware as processor instructions are highly demanded in multithreaded programming (design of thread locks and non-blocking data structures). In this article we study the in uence of cache coherence protocol, size and locality of the data on the latency of the operations. We developed a benchmark for analyzing the dependencies of throughput and latency on these parameters. We present the results of the evaluation of the e ciency of atomic operations on modern x86-64 processors and give recommendations for the optimizations. Particularly we found atomic operations, which have minimum (load), maximum (\successful CAS", store) and comparable (\unsuccessful CAS", FAA, SWP) latency. We showed that the choice of a processor core to perform the operation and the state of cache-line impact on the latency at average 1.5 and 1.3 times respectively. The suboptimal choice of the parameters may increase the throughput of atomic operations from 1.1 to 7.2 times. Our evidences may be used in the design of new and optimization of existing concurrent data structures and synchronization primitives.
1.1
Multicore shared-memory computer systems (CS) include desktop and server systems as well as computer nodes within distributed CS (cluster systems, massively parallel systems, supercomputers). Such systems may include tens and hundreds of processor of processor cores. For example, a computer node of Summit supercomputer ( rst place in TOP500 supercomputer ranking, more than 2 million processor cores, 4608 nodes) include two 24-core universal processor IBM Power9 and six graphical accelerators NVIDIA Tesla V100 (640 cores). Sunway TaihuLight (more than 10 million processor cores, third place in TOP500) is equipped with 40960 Sunway SW26010 processors with 260 cores. Processor cores in such systems are connected via processor interconnects (Intel QPI, AMD HyperTransport) according to the NUMA architecture. Notice, that cache memory in such systems is organized in very complicated ways, including di erent policies (inclusive, exclusive cache) and coherence protocols (MESI, MOESI, MESIF, MOWESI, MERSI, Dragon).
One of the most relevant tasks in parallel programming is the design of e cient tools for parallel thread synchronization. The main synchronization methods are locks, non-blocking (lock-free, wait-free, obstruction-free) concurrent (thread-safe) data structures and transactional memory [1{8]. Atomic operations (atomic) are used for implementation of all synchronization methods. The operation is atomic, if it's performed in one undividable step relative to other threads. In other words, no thread can observe this operation as \partially completed". If two or more threads perform operations with a shared variable and at least one of them writes (stores) to it, then the threads must use atomic operations to avoid data races.
The most common atomic operations are compare-and-swap (CAS), fetchand-add (FAA), swap (SWP), load (read), store (write). Load(m; r) reads the variable's value from the memory address m to the processor register r. Store(m; r) writes the value of the variable from the processor register r to the memory address m. FAA(m; r1; r2) increments (or decrements) by register's value r1 the value of variable in memory address m and returns the previous value in the register r2. SWP(m; r) exchanges the values of the memory address m and register r. CAS(m; r1; r2) compares the memory value m with the register r1; if the values are equal, modify memory m to a new value r2. Designing parallel programs, we should consider the impact to the atomic operation e ciency such aspects as cache coherence protocol, bu er size, thread number, data locality.
Despite the widespread use, the e ciency of atomic operations has not been
adequately analyzed at the current moment. For example, some works still claim
that CAS is slower than FAA [
In this work we consider operations CAS, FAA, SWP, load, store, wherein the conditions of the experiments are as close as possible to the real conditions of parallel program execution. In particular, the core frequency is not xed, huge pages are disabled, and cache prefetching is enabled. We evaluate the e ciency of atomic operations for modern x86-64 processor architectures depending on the cache line state (in cache coherence protocol), bu er size and its locality (relative to the core, executed the operations). Besides, we consider di erent variants of CAS operation (successful and unsuccessful). 2
As a metrics we used latency l of atomic operation execution and throughput b. Throughput b = n=t, where n is the number of executed operations of sequential access to the bu er's cells in time t.
To measure the execution time, we used the instruction set RDTSCP. To avoid reordering while executing operations we used full memory barriers.
We investigated the in uence of cache line state (within the cache coherence protocol: M, E, S, O, I, F) to the atomic operation e ciency. De ne the basic states of cache lines. M (Modi ed) { cache-line is modi ed and contains actual data. O (Owned) { cache line contains actual data and is the only owner of this data. E (Exclusive) { cache-line contains actual data, which is equal to the memory state. S (Shared) { cache-line contains actual data and other processor cores have actual copies of this data at the same time. F (Forwarded) { cacheline contains the most actual correct data and other cores may have copies of this data in shared state. I (Invalid) { cache-line contains invalid data.
We designed a benchmark. In this benchmark we allocate integer bu er q of size s = 128 MiB. The data is placed in the cache-memory and cache-lines are translated to a given state of the cache coherence protocol. Notice, that we don't use virtual memory. All the data was unaligned. To set state M for cache-lines we write arbitrary values to the bu er's cells. To set state E we write arbitrary values to the bu er's cells and then perform cl ush instruction to set the state of cache-lines to I followed by reading the bu er's cells. To set the state S a processor core reads bu er's cells from the cache-lines with state E of another core. To set the state O a processor reads from the cache-lines with state M of another core's cache-memory (cache-lines are switched from M to O).
For the CAS operation we performed two experiments: for successful and unsuccessful operation. Unsuccessful CAS is such CAS, when m 6= r1 (the memory is not changed). The deliberately unsuccessful execution of CAS is achieved by comparing the address of the pointer with the data on that pointer. For successful CAS m = r1 (the memory is changed).
We conducted experiments with the next processors: AMD Athlon II X4
640 (microarchitecture K10), AMD A10-4600M (microarchitecture Piledriver)
(cache coherence protocol MOESI [
(a) Piledriver
Next, we describe the main steps of the algorithm for measuring the execution time of atomic operations for state E ( g. 2a). Auxiliary function DoOper executes de ned atomic operation for all the elements of the bu er. The main algorithm is performed until the bu er size reach the maximum value (line 1). Used range of test array testSizeBuf f er in the experiments is varied from 6 KiB (minimal size L1 cache) to 128 MiB (larger than L3 cache). Each experiment is executed nruns times (line 2). Then we store arbitrary values to the bu er's cells to set cache-lines of the core c0 to the state M (for the other cores the state is changed to I) (line 3). After that, we invalidate cache-lines (line 8) followed by the reading to set cache-lines of the core c0 to the state E (line 5). On the next step for each variable we perform atomic operation (line 7). In the end we compute the operation execution time and total execution time (line 9), compute the latency (line 11), throughput (line 12) and increase the current bu er size by step = Lx=8, where Lx is the cache memory size for levels x = 1; 2; 3 (line 13).
Here are the main steps of the algorithm for time measurement of atomic operation execution by the core c0 for cache-lines in state S ( g. 2b). This algorithm is performed in two threads, a ned to the cores c0 and c2. Synchronization is implemented by means of atomic ags. The rst thread on the core c0 writes arbitrary data to the bu er, set the state of cache-lines to M (at the same time for the other cores the state of these cache-lines is changed to I) (line 4). Then we clean cache-lines (set to I) (line 5) and read data for changing the state of cache-lines of c0 to the E (line 6). The second thread (core c2) reads the data, changes the cache-line state of c0 to c2 cores to S (line 8). Then the rst thread on core c0 implements atomic operation with the elements of a bu er (line 11). After that we get the time for operation execution and the metrics (lines 15-17). Function DoExpExlusive(oper) 1 while d testSizeBuffer do 2 for i = 0 to nruns do 3 DoOper(store(1), buf) 4 CLFlush(buffer; d) 5 DoOper(load, buf) 6 start= GetTime() 7 DoOper(oper; buf)) 8 end = GetTime() 9 sumT ime = sumT ime + (end{start) 10 end for 11 latency = sumT ime=nruns=d 12 bandwidth = (d=sumT ime=nruns) 109=220 13 d = d + step 14 end while (a) Exclusive state
Function DoExpShared(oper) 1 while d testSizeBuffer do 2 for i = 0 to nruns do 3 . First thread on c0 4 DoOper(store(1), buf) 5 CLFlush(buffer; d) 6 DoOper(load, buf)
The following are the main steps of the algorithm for measurement of execution time of atomic operations for the cores c1 and c2 in state S ( g. 3b). The algorithm is performed in three threads, a ned to the cores c0, c1, c2. The rst thread (core c0) writes to the bu er to set the state of cache-line of c0 to M (for the rest of the cores the state is changed to I) (line 4). Then cache-line is invalidated to the state I (line 5) followed by the reading data to set the state of c0 to E (line 6). The second thread (core c1) reads the data (the state of cache-lines in c0 and c1 is changed to S) (line 8). On the next step the third thread (core c2) perform atomic operation with each element of the bu er (line 11). After that metrics are computed (lines 15-17).
For atomic operation latency measurement on the c1 we use the similar algorithm, in which the steps for c1 and c2 cores are changed places with each other.
The following are the main steps for the algorithm for measurement of execution time of atomic operations for cache-lines in state O on the core c0 ( g. 3a). The algorithm is performed in two threads, binded to the cores c0 and c2. The rst thread (core c0) arbitrary data is written into the bu er to set the state of cache-lines of the core c0 to M (for the rest cores the state is changed to I) (line 4). The second thread (core c2) reads the data to change the state of cache-lines of the local core c0 to O and cache-lines of the core c2 to S (line 8). On the next step the rst thread (core c0) perform atomic operation for each variable in the bu er (line 9). After that we compute atomic operation execution time and the metrics (lines 13-15). Function DoExpLocalityShared(oper) 1 while d testSizeBuffer do 2 for i = 0 to nruns do 3 . First thread on c0: 4 DoOper(store(1), buf) 5 CLFLush(buf; d) 6 DoOper(load, buf) 7 8 . Second thread on c1
DoOper(Load) 9 . Third thread on c2: 10 start =GetTime() 11 DoOper(oper; buf)) 12 end =GetTime() 13 sumT ime = sumT ime + (end{start) 14 end for 15 latency = sumT ime=nruns=d 16 bandwidth = (d=sumT ime=nruns) 109=220 17 d = d + step 18 end while (a) Exclusive state
Function DoExpLocalityOwned(oper) 1 while d testSizeBuffer do 2 for j = 0 to nruns do 3 . First thread on c0: 4 DoOper(store(1), buf) Fig. 4, 5 represent the experimental results for SWP operation. Latency on all processor except Nehalem-EP highly depends on the locality. Local core c0 provides minimal latency especially for bu er size less than L2 cache. In shared state (Fig. 5), the latency grows when bu er size exceeds L2 cache and in most cases the impact of locality is insigni cant on a large bu er size.
Figure 6 represents the latency of SWP operation on K10 processor for different cache-line states. It shows that state Modi ed gives minimal latency and Invalid state gives the maximum latency. Exclusive and Shared states are comparable with each other. Meanwhile, execution on local processor (c1) provide substantially lower latency, compared with remote ones (c2, c3). With increasing bu er size, the e ect of locality on latency decreases, because all the data is not cached and locates in main memory.
Fig. 7 depicts latency evaluations for di erent atomic operations in Shared state on K10 processor. As expected, Load has the minimal latency. Successful Compare-and-swap gives substantially larger latency compared with the other operations. Meanwhile, unsuccessful Compare-and-swap has the latency similar to FAA and SWP. Store operation also has larger latency. The similar results have been obtained for other processors.
Fig. 8 shows the results for the operation SWP, state O (Owned). The results are similar to the other states.
The tables 1 and 2 show suboptimal parameters of atomic operation execution on Westmere-EP and Nehalem-EP processors. Similar results have been obtained for the other processors. For example, on microarhictecures K10, NehalemEP, Westmere-EP operation load has the minimal latency for state S on the core (a) Piledriver c0 (from 1.14 to 1.81 ns), while for a Piledriver processor this operation has the lowest latency on c0 and c2 cores (from 1.8 to 2.4 ns).
Table 3 shows the ratio of maximum and minimum throughput. Operation Cache-line state Bu er size Core
Load Exclusive L2 c0, c1, c2 Store Modi ed RAM c0, c1, c2 FAA Invalid L1 c0, c1, c2 SWP Invalid, Modi ed RAM c0, c1, c2 unCAS Exclusive L1, L2 c0, c1, c2 CAS Invalid L2, L 3 c0, c1, c2
State of cache-lines is M. Metrics for atomic operations SWP, FAA, unCAS on the core c0 for Piledriver architecture slightly varies with bu er resizing, meanwhile for the cores c1 and c2 the increasing of the bu er more than L2 leads the latency reduction down to minimum value for the both cores. For K10 at bu er size exceeding L2 latency of operations SWP, FAA, unCAS di ers (a) Piledriver slightly. Latency of load, SWP, CAS for Nehalem-EP latency is comparable for all cores for bu er size more than L3. There are similar observations for load, SWP for Westmere-EP. For other operations (store, CAS, FAA, unCAS) latency is the minimum for the core c0 and doesn't depends on the bu er size.
State of cache-lines is E. Operations SWP, FAA, unCAS on Piledriver architectures and the bu er size more than L2 for c1 and c2 latency is comparable, for c0 core we obtained maximum values at the same time. For K10 architecture latency of operations SWP, FAA, unCAS is similar for all the cores for bu er size exceeding L2. For Nehalem-EP latency of SWP, load is similar on all the cores for bu er size more than L3. For Westmere-EP minimum latency for load, SWP, FAA, CAS operations was obtained on the core c0. For c1 and c2 and bu er size more than L3 latency varies slightly. State of cache-lines is S. Operations SWP, FAA on Piledriver architecture for bu er size L1 latency is maximum on the core c0. On K10 for bu er size L2 maximum latency was obtained on the core c0 for SWP, FAA, store operations. For Nehalem-EP and Westmere-EP for bu er size L2 latency of SWP, FAA is maximum on c1 and c2 cores.
State of cache-lines is I. Operations SWP, FAA, unCAS on Piledriver architecture bu er size the bu er size does not signi cantly a ect the runtime for all cores; the lowest latency was obtained on c1 and c2 cores. Load and SWP operations on K10 at bu er size more than L2 latency is minimal for c0 core. For Nehalem-EP latency of SWP, load is similar for all the cores at bu er size more (a) Modi ed (b) Exclusive (c) Shared (d) Invalid than L3. For operations load, SWP, FAA, CAS on Westmere-EP the minimal latency was obtained on the core c0.
State of cache-lines is O. Operations SWP, FAA on Piledriver at bu er size L1 the maximum latency was obtained on the c0 core. For the core c1 bu er size does not a ect to the operation latency. The maximal latency of operations SWP, FAA, store on K10 is obtained for bu er size L2 on c0 core.
If we compare all the operations among each other, \successful CAS" has the highest latency and load has the lowest latency. For example, for the K10, Westmere-EP cores minimal latency was obtained for the state S on the core c0 and equals from 12 to 24 ns; for Piledriver processor CAS has the minimal Operation Cache-line state Bu er size Core
Load Shared L2 c0, c1, c2 Store Shared L1, RAM c0, c1, c2 FAA Shared RAM c0, c1, c2 SWP Shared L2 c0, c1, c2 unCAS Exclusive L2, L3, RAM c1, c2 CAS Modi ed L3, RAM c0, c1 (a) Load (b) Store (c) Swap (SWP)
(d) Fetch-and-add (FAA) (e) Successful CAS (f) Unsuccessful CAS (unCAS) Fig. 7: Latency of atomic operations for K10 processor for Shared cache-line state value on cores c0 and c2 (from 42 to 44 ns); on Nehalem-EP in the state S CAS performs with minimal latency on the core c0 (from 22 to 46 ns), wherein the maximal latency (46 ns) was obtained for bu er size L2. For Piledriver architecture latency of load operation (1.76 ns) exceed the minimal latency of CAS (12.39 ns) by 7 times. For K10 architecture minimal latency of load (1.72 ns) exceeds minimal latency of CAS (22.38 ns) by 12 times. For Nehalem-EP the ration of minimum load latency (1.3 ns) to minimum CAS latency (9.86) is 7.5. For Westmere-EP architecture, the ratio of minimum load latency (1.1 ns) to minimum CAS latency (4.9 ns) is 4.5. Comparing the microarchitecture, we note (a) Piledriver that at average the lowest latency was obtained on the Westmere-EP processor (MESIF protocol), and the largest on the Piledriver (MOESI protocol). 4
In this work, we developed the algorithms and software tools and conducted experiments for e ciency analysis of atomic operations on modern multicore shared-memory systems depending on bu er size, cache line state and data locality. We experimentally show that operations \unsuccessful CAS", FAA and SWP has the minimum latency. Load operation has the minimum latency and operations \successful CAS" and store { maximum latency.
We analyzed the experimental results and gave the recommendations for increasing the throughput and minimizing the latency of atomic operation performance of modern processors. So, the application of our recommendations will increase the throughput of atomic operations on the Piledriver processors from 1.1 to 3.9 times, on the K10 processor - from 1.1 to 1.6 times, on the NehalemEP processor from 2.1 to 6, 1 time, on the Westmere-EP processor - from 1.1 to 7.2 times. Thus, the results show that the execution time of atomic operations can vary widely, depending on the conditions of their execution (cache line state, localization, and bu er size). These evidences should be considered for designing new concurrent data structures and synchronization primitives.