{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T04:09:23Z","timestamp":1752984563505,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2014,11,18]],"date-time":"2014-11-18T00:00:00Z","timestamp":1416268800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001868","name":"National Science Council Taiwan","doi-asserted-by":"publisher","award":["NSC 102-2220-E-009"],"award-info":[{"award-number":["NSC 102-2220-E-009"]}],"id":[{"id":"10.13039\/501100001868","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2014,11,18]]},"abstract":"<jats:p>Deploying the Shared Last-Level Cache (SLLC) is an effective way to alleviate the memory bottleneck in modern throughput processors, such as GPGPUs. A commonly used scheduling policy of throughput processors is to render the maximum possible thread-level parallelism. However, this greedy policy usually causes serious cache contention on the SLLC and significantly degrades the system performance. It is therefore a critical performance factor that the thread scheduling of a throughput processor performs a careful trade-off between the thread-level parallelism and cache contention. This article characterizes and analyzes the performance impact of cache contention in the SLLC of throughput processors. Based on the analyses and findings of cache contention and its performance pitfalls, this article formally formulates the aggregate working-set-size-constrained thread scheduling problem that constrains the aggregate working-set size on concurrent threads. With a proof to be NP-hard, this article has integrated a series of algorithms to minimize the cache contention and enhance the overall system performance on GPGPUs. The simulation results on NVIDIA's Fermi architecture have shown that the proposed thread scheduling scheme achieves up to 61.6% execution time enhancement over a widely used thread clustering scheme. When compared to the state-of-the-art technique that exploits the data reuse of applications, the improvement on execution time can reach 47.4%. Notably, the execution time improvement of the proposed thread scheduling scheme is only 2.6% from an exhaustive searching scheme.<\/jats:p>","DOI":"10.1145\/2676550","type":"journal-article","created":{"date-parts":[[2014,11,24]],"date-time":"2014-11-24T15:29:41Z","timestamp":1416842981000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Reducing Contention in Shared Last-Level Cache for Throughput Processors"],"prefix":"10.1145","volume":"20","author":[{"given":"Hsien-Kai","family":"Kuo","sequence":"first","affiliation":[{"name":"National Chiao-Tung University, Taiwan"}]},{"given":"Bo-Cheng Charles","family":"Lai","sequence":"additional","affiliation":[{"name":"National Chiao-Tung University, Taiwan"}]},{"given":"Jing-Yang","family":"Jou","sequence":"additional","affiliation":[{"name":"National Central University and National Chiao-Tung University, Taiwan"}]}],"member":"320","published-online":{"date-parts":[[2014,11,18]]},"reference":[{"volume-title":"Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS'09)","author":"Bakhoda Ali","key":"e_1_2_1_1_1","unstructured":"Ali Bakhoda , George L. Yuan , Wilson W. L. Fung , Henry Wong , and Tor M. Aamodt . 2009. Analyzing cuda workloads using a detailed GPU simulator . In Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS'09) . 163--174. Ali Bakhoda, George L. Yuan, Wilson W. L. Fung, Henry Wong, and Tor M. Aamodt. 2009. Analyzing cuda workloads using a detailed GPU simulator. In Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS'09). 163--174."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375527.1375562"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248396"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1994.1104"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1687399.1687501"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1854273.1854318"},{"volume-title":"To GPU synchronize or not GPU synchronize&quest","author":"Feng Wu-Chun","key":"e_1_2_1_7_1","unstructured":"Wu-Chun Feng and Shucai Xiao . 2010. To GPU synchronize or not GPU synchronize&quest ; In Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS '10). 3801--3804. Wu-Chun Feng and Shucai Xiao. 2010. To GPU synchronize or not GPU synchronize&quest; In Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS'10). 3801--3804."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/800152.804907"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1839676.1839694"},{"volume-title":"Proceedings of the Conference on Innovative Parallel Computing (InPar'12)","author":"Gupta Kshitij","key":"e_1_2_1_10_1","unstructured":"Kshitij Gupta , Jeff A. Stuart , and John D. Owens . 2012. A study of persistent threads style GPU programming for GPGPU workloads . In Proceedings of the Conference on Innovative Parallel Computing (InPar'12) . Kshitij Gupta, Jeff A. Stuart, and John D. Owens. 2012. A study of persistent threads style GPU programming for GPGPU workloads. In Proceedings of the Conference on Innovative Parallel Computing (InPar'12)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2006.88"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2451116.2451158"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2011.40"},{"key":"e_1_2_1_14_1","volume-title":"Das","author":"Kayiran Onur","year":"2012","unstructured":"Onur Kayiran , Adwait Jog , Mahmut T. Kandemir , and Chita R . Das . 2012 . Neither more nor less: Optimizing thread-level parallelism for GPGPUs . http:\/\/www.cse.psu.edu\/~oik5019\/docs\/pdf\/NMNL-PACT2013.pdf. Onur Kayiran, Adwait Jog, Mahmut T. Kandemir, and Chita R. Das. 2012. Neither more nor less: Optimizing thread-level parallelism for GPGPUs. http:\/\/www.cse.psu.edu\/~oik5019\/docs\/pdf\/NMNL-PACT2013.pdf."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2011.89"},{"key":"e_1_2_1_16_1","unstructured":"Khronos. 2011. The opencl specification version 1.1. http:\/\/www.khronos.org\/registry\/cl\/specs\/opencl-1.1.pdf.  Khronos. 2011. The opencl specification version 1.1. http:\/\/www.khronos.org\/registry\/cl\/specs\/opencl-1.1.pdf."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321917"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 17th Asia and South Pacific Design Automation Conference (ASP-DAC'12)","author":"Kuo Hsien-Kai","year":"2012","unstructured":"Hsien-Kai Kuo , Kuan-Ting Chen , Bo-Cheng Charles Lai , and Jing-Yang Jou . 2012 . Thread affinity mapping for irregular data access on shared cache GPGPU . In Proceedings of the 17th Asia and South Pacific Design Automation Conference (ASP-DAC'12) . 659--664. Hsien-Kai Kuo, Kuan-Ting Chen, Bo-Cheng Charles Lai, and Jing-Yang Jou. 2012. Thread affinity mapping for irregular data access on shared cache GPGPU. In Proceedings of the 17th Asia and South Pacific Design Automation Conference (ASP-DAC'12). 659--664."},{"key":"e_1_2_1_19_1","first-page":"1","article-title":"A cache hierarchy aware thread mapping methodology for GPGPUs","volume":"99","author":"Charles Lai Bo-Cheng","year":"2014","unstructured":"Bo-Cheng Charles Lai , Hsien-Kai Kuo , and Jing-Yang Jou . 2014 . A cache hierarchy aware thread mapping methodology for GPGPUs . IEEE Trans. Comput. PP , 99 , 1 -- 1 . Bo-Cheng Charles Lai, Hsien-Kai Kuo, and Jing-Yang Jou. 2014. A cache hierarchy aware thread mapping methodology for GPGPUs. IEEE Trans. Comput. PP, 99, 1--1.","journal-title":"IEEE Trans. Comput. PP"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2010.41"},{"key":"e_1_2_1_21_1","unstructured":"Nvidia. 2012a. NVIDIA kepler compute architecture whitepaper. http:\/\/www.nvidia.com\/object\/nvidia-kepler.html.  Nvidia. 2012a. NVIDIA kepler compute architecture whitepaper. http:\/\/www.nvidia.com\/object\/nvidia-kepler.html."},{"key":"e_1_2_1_22_1","unstructured":"Nvidia. 2012b. NVIDIA cuda C programming guide 4.1. https:\/\/developer.nvidia.com\/cuda-toolkit-41-archive\/.  Nvidia. 2012b. NVIDIA cuda C programming guide 4.1. https:\/\/developer.nvidia.com\/cuda-toolkit-41-archive\/."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2012.16"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2540708.2540718"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1356058.1356084"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISSCC.2010.5434030"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2011.24"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPASS.2010.5452013"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442523"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.51.5.759.16753"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806596.1806606"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1950365.1950408"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993744.1993748"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2011.130"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2676550","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2676550","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:16Z","timestamp":1750231696000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2676550"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,18]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,11,18]]}},"alternative-id":["10.1145\/2676550"],"URL":"https:\/\/doi.org\/10.1145\/2676550","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2014,11,18]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-11-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}