{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:14:18Z","timestamp":1763468058038,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CCF-0833122CCF-0925863CCF-0937907CNS-0720531OCI-0904534"],"award-info":[{"award-number":["CCF-0833122CCF-0925863CCF-0937907CNS-0720531OCI-0904534"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000105","name":"Office of Cyberinfrastructure","doi-asserted-by":"publisher","award":["CCF-0833122CCF-0925863CCF-0937907CNS-0720531OCI-0904534"],"award-info":[{"award-number":["CCF-0833122CCF-0925863CCF-0937907CNS-0720531OCI-0904534"]}],"id":[{"id":"10.13039\/100000105","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0833122CCF-0925863CCF-0937907CNS-0720531OCI-0904534"],"award-info":[{"award-number":["CCF-0833122CCF-0925863CCF-0937907CNS-0720531OCI-0904534"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>Advanced many-core CPU chips already have a few hundreds of processing cores (e.g., 160 cores in an IBM Cyclops-64 chip) and more and more processing cores become available as computer architecture progresses. The underlying runtime systems of such architectures need to efficiently serve hundreds of processors at the same time, requiring all basic data structures within the runtime to maintain unprecedented throughput. In this paper, we analyze the throughput requirements that must be met by algorithms in runtime systems to be able to handle hundreds of simultaneous operations in real time.<\/jats:p>\n          <jats:p>\n            We reach a surprising conclusion: Many traditional algorithm techniques are poorly suited for highly parallel computing environments because of their low throughput. We reach the conclusion that the intrinsic throughput of a parallel program depends on both its algorithm and the processor architecture where the program runs. We provide theory to quantify the intrinsic throughput of algorithms, and we provide a few examples, where we describe the intrinsic throughput of existing, common algorithms. Then, we go on to explain how to follow a\n            <jats:italic>throughput-oriented<\/jats:italic>\n            approach to develop algorithms that have very high intrinsic throughput in many core architectures. We compare our throughput-oriented algorithms with other well known algorithms that provide the same functionality and we show that a throughput-oriented design produces algorithms with equal or faster performance in highly concurrent environments. We provide both theoretical and experimental evidence showing that our algorithms are excellent choices over other state of the art algorithms.\n          <\/jats:p>\n          <jats:p>The major contributions of this paper are (1) motivating examples that show the importance of throughput in concurrent algorithms; (2) a mathematical framework that uses queueing theory to describe the intrinsic throughput of algorithms; (3) two highly concurrent algorithms with very high intrinsic throughput that are useful for task management in runtime systems; and (4) extensive experimental and theoretical results that show that for highly parallel systems, our proposed algorithms allow greater or at least equal scalability and performance than other well-known similar state-of-the-art algorithms.<\/jats:p>","DOI":"10.1145\/2086696.2086728","type":"journal-article","created":{"date-parts":[[2012,1,24]],"date-time":"2012-01-24T16:47:14Z","timestamp":1327423634000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Toward high-throughput algorithms on many-core architectures"],"prefix":"10.1145","volume":"8","author":[{"given":"Daniel","family":"Orozco","sequence":"first","affiliation":[{"name":"University of Delaware"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elkin","family":"Garcia","sequence":"additional","affiliation":[{"name":"University of Delaware"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rishi","family":"Khan","sequence":"additional","affiliation":[{"name":"ET International"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kelly","family":"Livingston","sequence":"additional","affiliation":[{"name":"University of Delaware"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guang R.","family":"Gao","sequence":"additional","affiliation":[{"name":"University of Delaware"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,1,26]]},"reference":[{"volume":"48","volume-title":"Advances in Geophysics","author":"Baysal E.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/209936.209958"},{"volume-title":"Fast: A functionally accurate simulation toolset for the cyclops-64 cellular architecture. CAPSL Tech. memo 062","year":"2005","author":"del Cuvillo J.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCS.2006.48"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/285930.285991"},{"key":"e_1_2_1_6_1","unstructured":"ET International. http:\/\/www.etinternational.com.  ET International. http:\/\/www.etinternational.com."},{"key":"e_1_2_1_7_1","unstructured":"Garcia E. Khan R. Livingston K. Venetis I. and Gao G. 2010a. Dynamic percolation\u2014mapping dense matrix multiplication on a many-core architecture. CAPSL Tech. memo 098 University of Delaware.  Garcia E. Khan R. Livingston K. Venetis I. and Gao G. 2010a. Dynamic percolation\u2014mapping dense matrix multiplication on a many-core architecture. CAPSL Tech. memo 098 University of Delaware."},{"volume":"6272","volume-title":"Proceedings of the 16th International Conference on Parallel Computing (Euro-Par'10)","author":"Garcia E.","key":"e_1_2_1_8_1"},{"volume-title":"Theory","author":"Kleinrock L.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","unstructured":"Mellor-Crummey J. 1987. Concurrent queues: Practical fetch and phi algorithms. Tech. rep. 229 Department of Computer Science University of Rochester.  Mellor-Crummey J. 1987. Concurrent queues: Practical fetch and phi algorithms. Tech. rep. 229 Department of Computer Science University of Rochester."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/248052.248106"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1074013"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2010.2"},{"key":"e_1_2_1_14_1","unstructured":"Theobald K. 1999. Earth: An efficient architecture for running threads. Ph.D. thesis McGill University.   Theobald K. 1999. Earth: An efficient architecture for running threads. Ph.D. thesis McGill University."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378611"},{"volume-title":"Proceedings of the International Conference on Parallel and Distributed Computing and Networks. 13--19","author":"Zhang Y.","key":"e_1_2_1_16_1"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2086696.2086728","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2086696.2086728","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:43Z","timestamp":1750241203000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2086696.2086728"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1145\/2086696.2086728"],"URL":"https:\/\/doi.org\/10.1145\/2086696.2086728","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2012,1]]},"assertion":[{"value":"2011-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}