Optimization of Remote Core Locking Synchronization in Multithreaded Programs for Multicore Computer Systems

Alexey Paznikov

Abstract


This paper proposes the algorithms for optimization of Remote Core Locking (RCL) synchronization method in multithreaded programs. The algorithm of initialization of RCL-locks and the algorithms for threads affinity optimization are developed. The algorithms consider the structures of hierarchical computer systems and non-uniform memory access (NUMA) to minimize execution time of RCLprograms. The experimental results on multi-core computer systems represented in the paper shows the reduction of RCLprograms execution time.

Keywords


remote core locking; RCL; synchronization; critical sections; scalability

References


Khoroshevsky V.G. “Distributed programmable structure computer systems”, Vestnik SibGUTI, 2010, no. 2, pp. 3-41.

Herlihy M., Shavit N. “The Art of Multiprocessor Programming”, Revised Reprint. Elsevier, 2012, 528 p.

Herlihy M., Moss J. E. B. “Transactional memory: Architectural support for lock-free data structures”, Proceedings of the 20th annual international symposium on computer architecture ACM. ACM, 1993, vol. 21, no. 2, pp. 289-300.

Shavit N. “Data Structures in the Multicore Age”, Communications of the ACM. ACM, 2011, NY, USA. vol. 54, no. 3, pp. 76-84.

Shavit N., Moir M. “Concurrent Data Structures” In “Handbook of Data Structures and Applications”, D. Metha and S.Sahni Editors, Chapman and Hall/CRC Press, Chapter 47, pp. 47-1 to 47-30, 2004.

Dechev D., Pirkelbauer P., Stroustrup B. “Understanding and effectively preventing the ABA problem in descriptor-based lock-free designs”, Object/Component/Service-Oriented Real-Time Distributed Computing (ISORC), 2010 13th IEEE International Symposium on. IEEE, 2010, pp. 185-192.

Michael M. M., Scott M. L. “Simple, fast, and practical non-blocking and blocking concurrent queue algorithms”, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing. ACM, 1996, pp. 267-275.

Anderson T. E. “The performance of spin lock alternatives for sharedmoney multi-processors”, IEEE Transactions on Parallel and Distributed Systems, 1990, vol. 1, no. 1, pp. 6-16.

Mellor-Crummey J. M., Scott M. L. “Algorithms for scalable synchronization on shared-memory multiprocessors”, ACM Transactions on Computer Systems (TOCS), 1991, vol. 9, no. 1, pp. 21-65.

Hendler D. et al. “Flat combining and the synchronization-parallelism tradeo”, Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures. ACM, 2010, pp. 355-364.

Fatourou P., Kallimanis N. D. “Revisiting the combining synchronization technique”, ACM SIGPLAN Notices. ACM, 2012, vol. 47, no. 8, pp. 257-266.

Y. Oyama, K. Taura, and A. Yonezawa. “Executing parallel programs with synchronization bottlenecks efficiently”, Proceedings of the International Workshop on Parallel and Distributed Computing for Symbolic and Irregular Applications, PDSIA 99, 1999, pp. 1-24.

Suleman M. A. et al. “Accelerating critical section execution with asymmetric multi-core architectures”, ACM SIGARCH Computer Architecture News. ACM, 2009, vol. 37, no. 1, pp. 253-264.

Metreveli Z., Zeldovich N., Kaashoek M. F. “Cphash: A cachepartitioned hash table”, ACM SIGPLAN Notices, ACM, 2012. vol. 47. no. 8, pp. 319-320.

Calciu I., Gottschlich J. E., Herlihy M. “Using elimination and delegation to implement a scalable NUMA-friendly stack”, Proc. Usenix Workshop on Hot Topics in Parallelism (HotPar), 2013, pp. 17.

Lozi J. P. et al. “Remote Core Locking: Migrating Critical-Section Execution to Improve the Performance of Multithreaded Applications”, USENIX Annual Technical Conference, 2012, pp. 6576.

Lozi J.P., Thomas G., Lawall J.L., Muller G. “Efficient locking for multicore architectures”, Research Report RR-7779, INRIA. 2011, pp. 1-30.


Full Text: PDF

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

IT in Innovation IT in Business IT in Engineering IT in Health IT in Science IT in Design IT in Fashion

IT in Industry @ (2012 - ) . http://www.it-in-industry.com . ISSN (Online): 2203-1731; ISSN (Print): 2204-0595