{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T12:14:26Z","timestamp":1777896866121,"version":"3.51.4"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2020,11,5]],"date-time":"2020-11-05T00:00:00Z","timestamp":1604534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,11,5]],"date-time":"2020-11-05T00:00:00Z","timestamp":1604534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s11227-020-03473-x","type":"journal-article","created":{"date-parts":[[2020,11,5]],"date-time":"2020-11-05T11:02:57Z","timestamp":1604574177000},"page":"5267-5288","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["An efficient parallel strategy for high-cost prefix operation"],"prefix":"10.1007","volume":"77","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9448-6168","authenticated-orcid":false,"given":"Hazem M.","family":"Bahig","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Khaled A.","family":"Fathy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,5]]},"reference":[{"key":"3473_CR1","volume-title":"Parallel computation: models and methods","author":"S Akl","year":"1997","unstructured":"Akl S (1997) Parallel computation: models and methods. Prentice Hall, Upper Saddle River, New Jersey"},{"key":"3473_CR2","doi-asserted-by":"crossref","unstructured":"Billeter M, Olsson O, Assarsson U (2009) Efficient stream compaction on wide SIMD many-core architectures. In: Proceedings of the Conference on High Performance Graphics August 01\u201303, pp 159\u2013166","DOI":"10.1145\/1572769.1572795"},{"key":"3473_CR3","doi-asserted-by":"publisher","unstructured":"Bahig H, Bahig H, Fathy K Fast and scalable algorithm for product large data on multicore system. In: Concurrency and computation: practice and expreience. https:\/\/doi.org\/10.1002\/cpe.5259","DOI":"10.1002\/cpe.5259"},{"key":"3473_CR4","unstructured":"Blelloch GE (1990) Prefix sums and their applications. Technical Report CMU-CS-90-190, School of Computer Science, Carnegie Mellon University. http:\/\/www.cs.cmu.edu\/~guyb\/papers\/Ble93.pdf"},{"key":"3473_CR5","first-page":"373","volume":"6586","author":"J Breitbart","year":"2010","unstructured":"Breitbart J (2010) Static GPU threads and an improved scan algorithm. LNCS 6586:373\u2013380","journal-title":"LNCS"},{"key":"3473_CR6","doi-asserted-by":"crossref","unstructured":"Capannini G (2011) Designing efficient parallel prefix sum algorithms for GPUs. In: 11th International Conference on Computer and Information Technology, pp 189\u2013196","DOI":"10.1109\/CIT.2011.11"},{"key":"3473_CR7","first-page":"334","volume":"4","author":"R Cole","year":"1989","unstructured":"Cole R, Vishkin U (1989) Faster optimal parallel prefix sum and list ranking. J Inf Control 4:334\u2013352","journal-title":"J Inf Control"},{"issue":"3","key":"3473_CR8","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1023\/B:SUPE.0000032783.66123.63","volume":"29","author":"A Datta","year":"2004","unstructured":"Datta A (2004) Multiple addition and prefix sum on a linear array with a reconfigurable pipelined bus system. J Supercomput 29(3):303\u2013317","journal-title":"J Supercomput"},{"key":"3473_CR9","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/978-3-319-46376-6_12","volume":"24","author":"F Dehne","year":"2017","unstructured":"Dehne F, Zaboli H (2017) Parallel Sorting for GPUs. Book Series titled Emergence, Complexity and Computation: Emergent Computation 24:293\u2013302","journal-title":"Book Series titled Emergence, Complexity and Computation: Emergent Computation"},{"key":"3473_CR10","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1080\/10637199308915441","volume":"1","author":"O Egecioglu","year":"1993","unstructured":"Egecioglu O, Srinivasan A (1993) Optimal parallel prefix on mesh architecture. Parallel Algorithms Appl 1:191\u2013209","journal-title":"Parallel Algorithms Appl"},{"key":"3473_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2017.07.025","volume":"700","author":"J Fuentes-Seplveda","year":"2017","unstructured":"Fuentes-Seplveda J, Ferres L, He M, Zeh N (2017) Parallel construction of succinct trees. Theor Comput Sci 700:1\u201322","journal-title":"Theor Comput Sci"},{"issue":"12","key":"3473_CR12","doi-asserted-by":"publisher","first-page":"2324","DOI":"10.1109\/TPDS.2012.336","volume":"24","author":"S Ha","year":"2013","unstructured":"Ha S, Han T (2013) A scalable work-efficient and depth-optimal parallel scan for the GPGPU environment. IEEE Trans Parallel Distrib Syst 24(12):2324\u20132333","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"3473_CR13","doi-asserted-by":"crossref","unstructured":"Han T, Carlson DD (1987) Fast area-efficient VLSI adders. Proceedings of the Ninth Annual Symposium on Computer Arithmetic, pp 49\u201356","DOI":"10.1109\/ARITH.1987.6158699"},{"issue":"8","key":"3473_CR14","doi-asserted-by":"publisher","first-page":"1602","DOI":"10.1109\/TPDS.2012.234","volume":"24","author":"K Kohlhoff","year":"2013","unstructured":"Kohlhoff K, Pande V, Altman R (2013) K-means for parallel architectures using all-prefix-sum sorting and updating steps. IEEE Trans Parallel Distrib Syst 24(8):1602\u20131612","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"6","key":"3473_CR15","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/S0020-0190(02)00317-4","volume":"84","author":"PK Jana","year":"2002","unstructured":"Jana PK, Naidu BD, Kumar S, Arora M, Sinha BP (2002) Parallel prefix computation on extended multi-mesh network. Inf Process Lett 84(6):295\u2013303","journal-title":"Inf Process Lett"},{"issue":"4","key":"3473_CR16","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1142\/S0129626406002757","volume":"16","author":"PK Jana","year":"2006","unstructured":"Jana PK, Sinha BP (2006) An improved parallel prefix algorithm on OTIS-mesh. Parallel Process Lett (World Sci) 16(4):429\u2013440","journal-title":"Parallel Process Lett (World Sci)"},{"key":"3473_CR17","doi-asserted-by":"publisher","first-page":"939","DOI":"10.1080\/02533839.2009.9671581","volume":"32","author":"Y Li","year":"2009","unstructured":"Li Y, Peng S, Chu W (2009) A new presentation of Metacubes for algorithmic design and case studies: Parallel prefix computation and parallel sorting. J Chin Inst Eng 32:939\u2013949","journal-title":"J Chin Inst Eng"},{"key":"3473_CR18","doi-asserted-by":"crossref","unstructured":"Li Y, Peng S, Chu W (2008) Prefix computation and sorting in dual-cube. In: Proceedings of the 37th International Conference on Parallel Processing, pp 389\u2013396","DOI":"10.1109\/ICPP.2008.18"},{"key":"3473_CR19","unstructured":"Lin YC, Lin CM (1996) Efficient parallel prefix algorithms on fully connected message passing computers. In: Proceedings of 3rd International Conference on High Performance Computing (HiPC), Trivandrum, India, pp 19\u201322"},{"issue":"1","key":"3473_CR20","first-page":"560","volume":"1","author":"KT Lucas","year":"2009","unstructured":"Lucas KT (2009) Parallel algorithm for prefix computation on OTIS $$k$$-Ary 3-cube parallel computers. Int J Recent Trends Eng 1(1):560\u2013562","journal-title":"Int J Recent Trends Eng"},{"key":"3473_CR21","unstructured":"Mallick DK, Jana PK (2008) Parallel prefix on mesh of trees and OTIS mesh of trees. In: Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA\u201908), pp 359\u2013364"},{"key":"3473_CR22","doi-asserted-by":"crossref","unstructured":"Maleki S, Burtscher M (2018) Automatic hierarchical parallelization of linear recurrences. In: The 23rd ACM International Conference on Architectural Support for Programming Languages and Operating Systems, March 24\u201328, USA, pp 128\u2013138","DOI":"10.1145\/3173162.3173168"},{"issue":"12","key":"3473_CR23","doi-asserted-by":"publisher","first-page":"2626","DOI":"10.1587\/transinf.E96.D.2626","volume":"E96D","author":"K Nakano","year":"2013","unstructured":"Nakano K (2013) Optimal parallel algorithms for computing the sum, the prefix-sums, and the summed area table on the memory machine models. IEICE Trans. Inf. Syst. E96D(12):2626\u20132634","journal-title":"IEICE Trans. Inf. Syst."},{"key":"3473_CR24","doi-asserted-by":"crossref","unstructured":"Nakano k, Ito Y (2015) Optimality of fundamental parallel algorithms on the hierarchical memory machine, with GPU implementation. In: 23rd Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP), pp 626\u2013634","DOI":"10.1109\/PDP.2015.46"},{"issue":"1","key":"3473_CR25","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s11227-007-0137-1","volume":"43","author":"JH Park","year":"2008","unstructured":"Park JH, Dai HK (2008) Reconfigurable hardware solution to parallel prefix computation. J Supercomput 43(1):43\u201358","journal-title":"J Supercomput"},{"issue":"1","key":"3473_CR26","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1049\/iet-ipr.2017.0161","volume":"12","author":"D Puchala","year":"2018","unstructured":"Puchala D, Stokfiszewski KK (2018) Numerical accuracy of integral images computation algorithms. IET Image Process 12(1):31\u201341","journal-title":"IET Image Process"},{"key":"3473_CR27","first-page":"237","volume-title":"Hypercube algorithms with applications to image processing and pattern recognition","author":"S Ranka","year":"1990","unstructured":"Ranka S, Sahni S (1990) Hypercube algorithms with applications to image processing and pattern recognition. Springer, New York, p 237"},{"key":"3473_CR28","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1006\/jpdc.2000.1698","volume":"62","author":"E Santos","year":"2002","unstructured":"Santos E (2002) Optimal and efficient algorithms for summing and prefix summing on parallel machines. J Parallel Distrib Comput 62:517\u2013543","journal-title":"J Parallel Distrib Comput"},{"key":"3473_CR29","doi-asserted-by":"crossref","unstructured":"Sinha BP, Bandyopadhyay S (2004) An optical interconnection system for parallel computing. In: Proceedings of International Conference on Computers and Devices for Communications","DOI":"10.1007\/978-3-540-27866-5_114"},{"key":"3473_CR30","doi-asserted-by":"crossref","unstructured":"Stine J, Babb C, Dave V (2005) Constant addition utilizing flagged prefix structures. In: IEEE International Symposium on Circuits and Systems, pp 668\u2013671","DOI":"10.1109\/ISCAS.2005.1464676"},{"key":"3473_CR31","doi-asserted-by":"crossref","unstructured":"Sudhanshu K (2013) An improved parallel prefix computation on 2D-mesh network. In: International conference on computational intelligence: modeling techniques and applications (CIMTA), pp 919\u2013926","DOI":"10.1016\/j.protcy.2013.12.438"},{"issue":"4","key":"3473_CR32","doi-asserted-by":"publisher","first-page":"1510","DOI":"10.1007\/s11227-018-2242-8","volume":"74","author":"H Tokura","year":"2018","unstructured":"Tokura H, Fujita T, Nakano K, Ito Y, Bordim J (2018) Almost optimal column-wise prefix-sum computation on the GPU. J Supercomput 74(4):1510\u20131521","journal-title":"J Supercomput"},{"issue":"12","key":"3473_CR33","doi-asserted-by":"publisher","first-page":"1226","DOI":"10.1109\/71.737698","volume":"9","author":"CF Wang","year":"1998","unstructured":"Wang CF, Sahni S (1998) Basic operations on the OTIS-Mesh optoelectronic computer. IEEE Trans Parallel Distrib Syst 9(12):1226\u20131998","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"3","key":"3473_CR34","doi-asserted-by":"publisher","first-page":"1296","DOI":"10.1109\/LRA.2017.2666544","volume":"2","author":"Y Yang","year":"2017","unstructured":"Yang Y, Wu Y, Pan J (2017) Parallel dynamics computation using prefix sum operations. IEEE Robot Automat Lett 2(3):1296\u20131303","journal-title":"IEEE Robot Automat Lett"},{"issue":"3","key":"3473_CR35","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1109\/TPDS.2011.174","volume":"23","author":"N Zhang","year":"2012","unstructured":"Zhang N (2012) A novel parallel scan for multicore processors and its application in sparse matrix-vector multiplication. IEEE Trans Parallel Distrib Syst 23(3):397\u2013404","journal-title":"IEEE Trans Parallel Distrib Syst"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-020-03473-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-020-03473-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-020-03473-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,11]],"date-time":"2021-05-11T22:05:20Z","timestamp":1620770720000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-020-03473-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,5]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["3473"],"URL":"https:\/\/doi.org\/10.1007\/s11227-020-03473-x","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,5]]},"assertion":[{"value":"19 October 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}