Optimization method of remote core locking

The number of processor cores in shared memory computer systems is increasing nowadays. Therefore, the need of scalable parallel programs rises up. These programs must be efficient on large number of parallel threads. Among the perspective scalable approaches of multithreading programming, one can emphasize lock-free algorithms and data structures and software transactional memory. The main drawbacks of lock-free algorithms and data structures are their restrained area of applying and essential complexity of parallel programs development. Besides the throughput of those structures is comparable with lock-based structures. Current implementations of software transactional memory do not provide high performance of multithreading programs and have not common in real applications yet. Classical approach of lock-based critical sections in multithreading programs remains the most prevalent. Locks are easier than lock-free algorithms and data structures and ensures high level of productivity. Besides that, the most of present software is lock-based. Thus, development of scalable locks is substantial now. Locks scalability depends on access contention while accessing of parallel threads to share memory and space cache locality. Access contention takes place while simultaneous access of multiple thread to one critical section, protected by one synchronization object. This leads to cache become inefficiency. Cache locality is significant when the critical section contains the access to shared data, which was accessed previously on the other core. This circumstance leads to cache misses and severe critical section execution time increasing. The most efficient approaches of scalable locks implementation are CAS spinlocks, MCS-locks, Flat combining CC-Synch, DSM-Synch, Oyama lock. However, these methods cannot guarantee the minimum of critical section execution. The critical section execution time includes time of lock ownership transfer and critical section execution time. In this work, we consider the method of critical section execution on remote processor cores (Remote Core Locking, RCL). RCL minimizes the execution time of legacy multithreading programs by reduction critical section execution critical path. This method replaces critical sections in legacy programs by procedures remote calls. All critical sections protected by one lock are performed by server thread launched on remote core. Therefore, by execution of the critical section by the particular thread minimizes the overheads of lock ownership transfer. In the current implementation RCL, they do not consider the non-uniform access to memory in NUMA-systems. These systems are the compositions multicore processors connected with local area of global memory. Time of critical section execution in RCL depends on RCL-server latency while accessing to memory blocks within critical section. Thus, in these programs memory should be allocated on NUMA node with the RCL-server. This reduces time of memory accesses and minimizes of programs execution time. In this work, we propose the algorithm minimizing the memory access time in NUMA systems while RCL-programs execution. The algorithm optimizes the memory allocation on NUMA-systems. The essential of the algorithms is allocating on the NUMA-node, on which RCL-server is executing. The results of experiments show that the memory allocation algorithm increases the throughput of critical sections execution by reducing the time of RCL-server access to memory.

Keywords

Authors

References