{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T08:01:55Z","timestamp":1764403315354,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,11,8]],"date-time":"2023-11-08T00:00:00Z","timestamp":1699401600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,11,8]],"date-time":"2023-11-08T00:00:00Z","timestamp":1699401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"ISPS KAKENHI","award":["JP21K11806"],"award-info":[{"award-number":["JP21K11806"]}]},{"name":"JSPS Core-to-Core program","award":["JPJSCCB2023005"],"award-info":[{"award-number":["JPJSCCB2023005"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Netw Distrib Comput"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Binary search trees (BSTs) are one of the most important data structures in the field of computer science. We may easily write a parallel construction program of a BST by extending the sequential algorithm straightly. However, in such conventional approaches, the order of nodes inserted into a BST is determined dynamically, depending on the occasional state of the parallel thread execution. It results in a BST with a different structure (node position) generated on every execution of the parallel program. On the other hand, we have been developing parallel construction schemes of the BST with the same structure as a BST generated by the sequential algorithm. One is the speculatively parallel construction of a BST. And another is the purely (non-speculatively) parallel construction, but it was derived through the concept of thread-level speculation. This paper evaluates the performances of those construction schemes on several types of shared-memory multiprocessors. For the large enough size of BST, our new parallel programs can construct a BST with always the same structure on a little lower or sometimes higher performance than the program that makes a BST with a different structure on every execution. And in contrast with the general expectation that simply enlarging the size of parallel tasks increases misspeculation and damages the performance, we found that it sometimes enhances the performance of speculatively parallel execution.<\/jats:p>","DOI":"10.1007\/s44227-023-00013-w","type":"journal-article","created":{"date-parts":[[2023,11,8]],"date-time":"2023-11-08T10:02:41Z","timestamp":1699437761000},"page":"88-111","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Performance Evaluation on Parallel Speculation-Based Construction of a Binary Search Tree"],"prefix":"10.1007","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1382-4928","authenticated-orcid":false,"given":"Hiroaki","family":"Hirata","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1911-3075","authenticated-orcid":false,"given":"Atsushi","family":"Nunome","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,11,8]]},"reference":[{"key":"13_CR1","doi-asserted-by":"publisher","unstructured":"Hirata H, Nunome A (2021) Reducing the repairing penalty on misspeculation in thread-level speculation. In: Proceedings of the 8th international virtual conference on applied computing & information technology (ACIT 2021). ACM, pp 39\u201345. https:\/\/doi.org\/10.1145\/3468081.3471120","DOI":"10.1145\/3468081.3471120"},{"key":"13_CR2","doi-asserted-by":"publisher","unstructured":"Hirata H, Nunome A (2022) Parallel binary search tree construction inspired by thread-level speculation. In: Proceedings of the 23rd ACIS international summer virtual conference on software engineering, artificial intelligence, networking and parallel\/distributed computing (SNPD 2022-Summer). IEEE, pp 74\u201381. https:\/\/doi.org\/10.1109\/SNPD-Summer57817.2022.00021","DOI":"10.1109\/SNPD-Summer57817.2022.00021"},{"key":"13_CR3","doi-asserted-by":"publisher","unstructured":"Hirata H, Nunome A, Shibayama K (2016) Speculative memory: an architectural support for explicit speculations in multithreaded programming. In: Proceedings of the 15th international conference on computer and information science (ICIS 2016). IEEE, pp 715\u2013721. https:\/\/doi.org\/10.1109\/ICIS.2016.7550843","DOI":"10.1109\/ICIS.2016.7550843"},{"key":"13_CR4","doi-asserted-by":"publisher","unstructured":"Fujisawa K, Nunome A, Shibayama K, Hirata H (2017) A software implementation of speculative memory. In: Proceedings of the 18th international conference on software engineering, artificial intelligence, networking and parallel\/distributed computing (SNPD 2017). IEEE, pp 437\u2013443. https:\/\/doi.org\/10.1109\/SNPD.2017.8022759","DOI":"10.1109\/SNPD.2017.8022759"},{"key":"13_CR5","doi-asserted-by":"publisher","unstructured":"Matsunaga D, Nunome A, Hirata H (2019) Shelving a code block for thread-level speculation. In: Proceedings of the 20th international conference on software engineering, artificial intelligence, networking and parallel\/distributed computing (SNPD 2019). IEEE, pp 427\u2013434. https:\/\/doi.org\/10.1109\/SNPD.2019.8935751","DOI":"10.1109\/SNPD.2019.8935751"},{"issue":"3","key":"13_CR6","doi-asserted-by":"publisher","first-page":"19","DOI":"10.4018\/IJSI.2020070102","volume":"8","author":"H Hirata","year":"2020","unstructured":"Hirata H, Nunome A (2020) Decoupling computation and result write-back for thread-level parallelization. Int J Softw Innov (IJSI) 8(3):19\u201334. https:\/\/doi.org\/10.4018\/IJSI.2020070102","journal-title":"Int J Softw Innov (IJSI)"},{"issue":"1","key":"13_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4172\/2165-7866.1000103","volume":"1","author":"J Feng","year":"2011","unstructured":"Feng J, Naiman DQ, Cooper B (2011) A parallelized binary search tree. J Inf Technol Softw Eng 1(1):1\u20135. https:\/\/doi.org\/10.4172\/2165-7866.1000103","journal-title":"J Inf Technol Softw Eng"},{"key":"13_CR8","doi-asserted-by":"publisher","unstructured":"Howley SV, Jones J (2012) A non-blocking internal binary search tree. In: Proceedings of the 24th symposium on parallelism in algorithms and architectures. ACM, pp 161\u2013171. https:\/\/doi.org\/10.1145\/2312005.2312036","DOI":"10.1145\/2312005.2312036"},{"key":"13_CR9","unstructured":"McKenney PE (2010) Memory barriers: a hardware view for software hackers. Preprint at https:\/\/www.researchgate.net\/publication\/228824849_Memory_Barriers_a_Hardware_View_for_Software_Hackers. Accessed 25 Mar 2023"},{"issue":"7","key":"13_CR10","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1145\/1785414.1785443","volume":"53","author":"P Sewell","year":"2010","unstructured":"Sewell P, Sarkar S, Owens S, Nardelli FZ, Myreen MO (2010) x86-TSO: a rigorous and usable programmer\u2019s model for x86 multiprocessors. Commun ACM 53(7):89\u201397. https:\/\/doi.org\/10.1145\/1785414.1785443","journal-title":"Commun ACM"},{"key":"13_CR11","doi-asserted-by":"publisher","unstructured":"Adve SV, Hill MD (1990) Weak ordering: a new definition. In: Proceedings of the 17th international symposium on computer architecture (ISCA \u201917). ACM, pp 2\u201314. https:\/\/doi.org\/10.1145\/325096.325100","DOI":"10.1145\/325096.325100"},{"key":"13_CR12","doi-asserted-by":"publisher","unstructured":"Gharachorloo K, Lenoski D, Laudon J, Gibbons P, Gupta A, Hennessy J (1990) Memory consistency and event ordering in scalable shared-memory multiprocessors. In: Proceedings of the 17th international symposium on computer architecture (ISCA \u201917). ACM, pp 15\u201326. https:\/\/doi.org\/10.1145\/325096.325102","DOI":"10.1145\/325096.325102"},{"key":"13_CR13","doi-asserted-by":"publisher","unstructured":"Ellen F, Fatourou P, Ruppert E, Breugel F (2010) Non-blocking binary search trees. In: Proceedings of the 29th symposium on principles of distributed computing (PODC \u201910). ACM, pp 131\u2013140. https:\/\/doi.org\/10.1145\/1835698.1835736","DOI":"10.1145\/1835698.1835736"},{"key":"13_CR14","doi-asserted-by":"publisher","unstructured":"Natarajan A, Mittal N (2014) Fast concurrent lock-free binary search trees. In: Proceedings of the 19th ACM SIGPLAN symposium on principles and practice of parallel programming (PPoPP \u201914). ACM, pp 317\u2013328. https:\/\/doi.org\/10.1145\/2555243.2555256","DOI":"10.1145\/2555243.2555256"},{"key":"13_CR15","doi-asserted-by":"publisher","unstructured":"Fatourou P, Papavasileiou E, Ruppert E (2019) Persistent non-blocking binary search trees supporting wait-free range queries. In: Proceedings of the 31st symposium on parallelism in algorithms and architectures (SPAA \u201919). ACM, pp 275\u2013286. https:\/\/doi.org\/10.1145\/3323165.3323197","DOI":"10.1145\/3323165.3323197"},{"key":"13_CR16","doi-asserted-by":"publisher","unstructured":"Akkary H, Driscoll MA (1998) A dynamic multithreading processor. In: Proceedings of the 31st annual international symposium on microarchitecture (MICRO-31). IEEE, pp 226\u2013236. https:\/\/doi.org\/10.1109\/MICRO.1998.742784","DOI":"10.1109\/MICRO.1998.742784"},{"key":"13_CR17","doi-asserted-by":"publisher","unstructured":"Marcuello P, Gonz\u00e1lez A (1999) Clustered speculative multithreaded processors. In: Proceedings of the 13th international conference on supercomputing. ACM, pp 365\u2013372. https:\/\/doi.org\/10.1145\/305138.305214","DOI":"10.1145\/305138.305214"},{"issue":"2","key":"13_CR18","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1109\/40.848474","volume":"20","author":"L Hammond","year":"2000","unstructured":"Hammond L, Hubbert BA, Siu M, Prabhu MK, Chen M, Olukotun K (2000) The Stanford hydra CMP. IEEE Micro 20(2):71\u201384. https:\/\/doi.org\/10.1109\/40.848474","journal-title":"IEEE Micro"},{"issue":"12","key":"13_CR19","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1109\/71.970565","volume":"12","author":"TN Vijaykumar","year":"2001","unstructured":"Vijaykumar TN, Gopal S, Smith JE, Sohi G (2001) Speculative versioning cache. IEEE Trans Parallel Distrib Syst 12(12):1305\u20131317. https:\/\/doi.org\/10.1109\/71.970565","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"13_CR20","doi-asserted-by":"publisher","unstructured":"Cintra M, Torrellas J (2002) Eliminating squashes through learning cross-thread violations in speculative parallelization for multiprocessors. In: Proceedings of the 8th international symposium on high-performance computer architecture. IEEE, pp 43\u201354. https:\/\/doi.org\/10.1109\/HPCA.2002.995697","DOI":"10.1109\/HPCA.2002.995697"},{"key":"13_CR21","doi-asserted-by":"publisher","unstructured":"Steffan JG, Colohan CB, Zhai A, Mowry TC (2002) Improving value communication for thread-level speculation. In: Proceedings of the 8th international symposium on high-performance computer architecture. IEEE, pp 65\u201375. https:\/\/doi.org\/10.1109\/HPCA.2002.995699","DOI":"10.1109\/HPCA.2002.995699"},{"key":"13_CR22","doi-asserted-by":"publisher","unstructured":"Prabhu MK, Olukotun K (2003) Using thread-level speculation to simplify manual parallelization. In: Proceedings of the 9th ACM SIGPLAN symposium on principles and practice of parallel programming. ACM, pp 1\u201312. https:\/\/doi.org\/10.1145\/781498.781500","DOI":"10.1145\/781498.781500"},{"key":"13_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8987-1_12","author":"MJ Garzaran","year":"2004","unstructured":"Garzaran MJ, Prvulovic M, Llaberia JM, Vinals V, Rauchwerger L, Torrellas J (2004) Software logging under speculative parallelization. High Perform Mem Syst. https:\/\/doi.org\/10.1007\/978-1-4419-8987-1_12","journal-title":"High Perform Mem Syst"},{"issue":"3","key":"13_CR24","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1145\/1082469.1082471","volume":"23","author":"JG Steffan","year":"2005","unstructured":"Steffan JG, Colohan C, Zhai A, Mowry TC (2005) The STAMPede approach to thread-level speculation. ACM Trans Comput Syst 23(3):253\u2013300. https:\/\/doi.org\/10.1145\/1082469.1082471","journal-title":"ACM Trans Comput Syst"},{"key":"13_CR25","doi-asserted-by":"publisher","unstructured":"Ohsawa T, Takagi M, Kawahara S, Matsushita S (2005) Pinot: speculative multi-threading processor architecture exploiting parallelism over a wide range of granularities. In: Proceedings of the 38th annual international symposium on microarchitecture (MICRO-38). IEEE, pp 81\u201392. https:\/\/doi.org\/10.1109\/MICRO.2005.26","DOI":"10.1109\/MICRO.2005.26"},{"key":"13_CR26","doi-asserted-by":"publisher","unstructured":"Colohan CB, Ailamaki A, Steffan JG, Mowry TC (2006) Tolerating dependences between large speculative threads via sub-threads. In: Proceedings of the 33rd annual international symposium on computer architecture (ISCA \u201906). IEEE, pp 216\u2013226. https:\/\/doi.org\/10.1109\/ISCA.2006.43","DOI":"10.1109\/ISCA.2006.43"},{"key":"13_CR27","doi-asserted-by":"publisher","unstructured":"Praun C, Ceze L, Cascaval C (2007) Implicit parallelism with ordered transactions. In: Proceedings of the 12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP \u20197), pp. 79\u201389. https:\/\/doi.org\/10.1145\/1229428.1229443","DOI":"10.1145\/1229428.1229443"},{"key":"13_CR28","doi-asserted-by":"publisher","unstructured":"Tian C, Feng M, Nagarajan V, Gupta R (2008) Copy or discard execution model for speculative parallelization on multicores. In: Proceedings of the 41st IEEE\/ACM international symposium on microarchitecture (MICRO-41). IEEE, pp 330\u2013341. https:\/\/doi.org\/10.1109\/MICRO.2008.4771802","DOI":"10.1109\/MICRO.2008.4771802"},{"key":"13_CR29","doi-asserted-by":"publisher","unstructured":"Mehrara M, Hao J, Hsu P, Mahlke S (2009) Parallelizing sequential applications on commodity hardware using a low-cost software transactional memory. In: Proceedings of the 30th ACM SIGPLAN conference on programming language design and implementation. pp 166\u2013176. https:\/\/doi.org\/10.1145\/1543135.1542495","DOI":"10.1145\/1543135.1542495"},{"key":"13_CR30","doi-asserted-by":"publisher","unstructured":"Hertzberg B, Olukotun K (2011) Runtime automatic speculative parallelization. In: Proceedings of the 9th Annual IEEE\/ACM international symposium on code generation and optimization. IEEE, pp 64\u201373. https:\/\/doi.org\/10.1109\/CGO.2011.5764675","DOI":"10.1109\/CGO.2011.5764675"},{"key":"13_CR31","doi-asserted-by":"publisher","unstructured":"Odaira R, Nakaike T (2014) Thread-level speculation on off-the-shelf hardware transactional memory. In: Proceedings of the IEEE international symposium on workload characterization. pp 212\u2013221. https:\/\/doi.org\/10.1109\/IISWC.2014.6983060","DOI":"10.1109\/IISWC.2014.6983060"},{"key":"13_CR32","doi-asserted-by":"publisher","unstructured":"Shoji Y, Nunome A, Hirata H, Shibayama K (2015) A large-scale speculation for the thread-level parallelization. In: Proceedings of the 3rd international conference on applied computing and information technology (ACIT 2015). IEEE, pp 162\u2013168. https:\/\/doi.org\/10.1109\/ACIT-CSI.2015.39","DOI":"10.1109\/ACIT-CSI.2015.39"},{"key":"13_CR33","doi-asserted-by":"publisher","unstructured":"Salamanca J, Amaral JN, Araujo G (2016) Evaluating and improving thread-level speculation in hardware transactional memories. In: Proceedings of the IEEE international parallel and distributed processing symposium (IPDPS). IEEE, pp 586\u2013595. https:\/\/doi.org\/10.1109\/IPDPS.2016.84","DOI":"10.1109\/IPDPS.2016.84"},{"key":"13_CR34","doi-asserted-by":"publisher","unstructured":"Hirata H, Kimura K, Nagamine S, Mochizuki Y, Nishimura A, Nakase Y, Nishizawa T (1992) An elementary processor architecture with simultaneous instruction issuing from multiple threads. In: Proceedings of the 19th annual international symposium on computer architecture (ISCA \u201992). ACM, pp 136\u2013145. https:\/\/doi.org\/10.1145\/146628.139710","DOI":"10.1145\/146628.139710"},{"key":"13_CR35","doi-asserted-by":"publisher","unstructured":"Tullsen DM, Eggers SJ, Levy HM (1995) Simultaneous multithreading: maximizing on-chip parallelism. In: Proceedings of the 22nd annual international symposium on computer architecture (ISCA \u201995). ACM, pp 369\u2013380. https:\/\/doi.org\/10.1145\/225830.224449","DOI":"10.1145\/225830.224449"}],"container-title":["International Journal of Networked and Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s44227-023-00013-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s44227-023-00013-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s44227-023-00013-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,23]],"date-time":"2023-11-23T09:46:25Z","timestamp":1700732785000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s44227-023-00013-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,8]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["13"],"URL":"https:\/\/doi.org\/10.1007\/s44227-023-00013-w","relation":{},"ISSN":["2211-7938","2211-7946"],"issn-type":[{"type":"print","value":"2211-7938"},{"type":"electronic","value":"2211-7946"}],"subject":[],"published":{"date-parts":[[2023,11,8]]},"assertion":[{"value":"22 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 October 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 November 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflicts of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}