Concurrent Treaps and Impact of Locking Objects
Tóm tắt
We propose algorithms to perform operations concurrently on treaps in a shared memory multi-core environment. Concurrent treaps hold the advantage of using nodes’ priority for maintaining the height of the treaps. To achieve synchronization, concurrent treaps make use of fine-grained locking mechanism along with logical ordering and physical ordering of nodes’ keys. We initially study the throughput and performance-per-Watt (PPW) of our concurrent treap implementation and observe that it scales well, and performs better than the state-of-the-art implementations. We further continue studies to understand the impact of different locking objects on both throughput and PPW. Our experiments show that a concurrent treap implementation that uses AtomicInteger as the locking object provides better throughput and PPW, at the same time uses a low memory footprint. As part of the application study, we consider concurrent interval trees by choosing different underlying concurrent search tree implementations as the base. We observe that the concurrent interval tree implementation that uses concurrent treap as an underlying data structure provides better throughput.
Tài liệu tham khảo
Afek, Y., Kaplan, H., Korenfeld, B., Morrison, A., Tarjan, R.E.: Cbtree: a practical concurrent self-adjusting search tree. DISC 27(6), 393–417 (2014)
Alapati, P., Saranam, S., Mutyam, M.: Concurrent treaps. In: Alapati, P. (ed.) Algorithms and Architectures for Parallel Processing, pp. 776–790. Springer, Cham (2017)
Aragon, C.R., Seidel, R.G.: Randomized search trees. In: FOCS, pp. 450–454 (1989)
Bronson, N.G., Casper, J., Chafi, H., Olukotun, K.: A practical concurrent binary search tree. In: PPoPP, pp. 257–268 (2010)
Christopher, H., Costin, C., William, S., Antonio, W., Alexandr, Z.: The effect of numa tunings on cpu performance. In: CHEP, pp. 1–7 (2015)
Crain, T., Gramoli, V., Raynal, M.: A contention-friendly binary search tree. In: ICPP, pp. 229–240 (2013)
David, H., Gorbatov, E., Hanebutte, U.R., Khanna, R., Le, C.: Rapl: Memory power estimation and capping. In: Proceedings of the 16th ACM/IEEE International Symposium on Low Power Electronics and Design, pp. 189–194 (2010)
Drachsler, D., Vechev, M., Yahav, E.: Practical concurrent binary search trees via logical ordering. In: PPoPP, pp. 343–356 (2014)
Ellen, F., Fatourou, P., Ruppert, E., van Breugel, F.: Non-blocking binary search trees. In: PODC, pp. 131–140 (2010)
Fraser: Practical Lock Freedom. PhD thesis, University of Cambridge (2003)
Gramoli, V.: Synchrobench (2015). https://github.com/gramoli/synchrobench
Herlihy, M.P., Shavit, N.: The Art of Multiprocessor Programming. Morgan Kaufmann Publishers, Burlington (2008)
Herlihy, M.P., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. TOPLAS 12(3), 463–492 (1990)
Intel-xeon-e5-4610 v2. https://ark.intel.com
Lea, D.: Concurrent skip list. java.util.concurrent
Liu, K., Pinto, G., Liu, Y.D.: Data-Oriented Characterization of Application-Level Energy Optimization, pp. 316–331. Springer, Berlin (2015)
Martínez, C., Roura, S.: Randomized binary search trees. JACM 45(2), 288–323 (1998)
Natarajan, A., Mittal, N.: Fast concurrent lock-free binary search trees. In: PPoPP, pp. 317–328 (2014)
Perf: A profiling tool (2015). https://perf.wiki.kernel.org/index.php
Pugh, W.: Skip lists: a probabilistic alternative to balanced trees. CACM 33(6), 668–676 (1990)
Reentrant locks. http://docs.oracle.com/java7/api/
Reitbauer, A.: Java Enterprise Performance. Entwickler Press, Frankfurt (2011)
Seidel, R., Aragon, C.R.: Randomized search trees. Algorithmica 16(4), 464–497 (1996)
Shavit, N.: Data structures in the multicore age. CACM 54(3), 76–84 (2011)
Weiss, M.A.: Data Structures and Algorithm Analysis in C++, 3rd edn. Pearson Press, London (2009)