{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T16:09:09Z","timestamp":1761581349303,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,9,21]],"date-time":"2015-09-21T00:00:00Z","timestamp":1442793600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Korean government","award":["2012R1A2A2A06047297"],"award-info":[{"award-number":["2012R1A2A2A06047297"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. Emerg. Technol. Comput. Syst."],"published-print":{"date-parts":[[2015,9,21]]},"abstract":"<jats:p>\n            3D\n            <jats:italic>integrated circuits<\/jats:italic>\n            (3D ICs) using\n            <jats:italic>through-silicon vias<\/jats:italic>\n            (TSVs) allow to envision the stacking of dies with different functions and technologies, using as an interconnect backbone a 3D\n            <jats:italic>network-on-chip<\/jats:italic>\n            (NoC). However, partial vertical connection in 3D NoCs seems unavoidable because of the large overhead of TSV itself (e.g., large footprint, low fabrication yield, additional fabrication processes) as well as the heterogeneity in dimension. This article proposes an energy-efficient deadlock-free routing algorithm for 3D mesh topologies where vertical connections partially exist. By introducing some rules for selecting elevators (i.e., vertical links between dies), the routing algorithm can eliminate the dedicated virtual channel requirement. In this article, the rules themselves as well as the proof of deadlock freedom are given. By eliminating the virtual channels for deadlock avoidance, the proposed routing algorithm reduces the energy consumption by 38.9% compared to a conventional routing algorithm. When the virtual channel is used for reducing the head-of-line blocking, the proposed routing algorithm increases performance by up to 23.1% and 6.9% on average.\n          <\/jats:p>","DOI":"10.1145\/2751560","type":"journal-article","created":{"date-parts":[[2015,9,22]],"date-time":"2015-09-22T12:31:00Z","timestamp":1442925060000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["REDELF"],"prefix":"10.1145","volume":"12","author":[{"given":"Jinho","family":"Lee","sequence":"first","affiliation":[{"name":"Seoul National University, Seoul, South Korea"}]},{"given":"Kyungsu","family":"Kang","sequence":"additional","affiliation":[{"name":"Samsung, Gyeonggi-do, Korea"}]},{"given":"Kiyoung","family":"Choi","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, South Korea"}]}],"member":"320","published-online":{"date-parts":[[2015,9,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2039370.2039374"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISVLSI.2012.19"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1454115.1454128"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the International Conference on Supercomputing. 330--339","author":"Borkar Shekhar","year":"1988","unstructured":"Shekhar Borkar , Robert Cohn , George Cox , Sha Gleason , and Thomas Gross . 1988 . Warp: An integrated solution of high-speed parallel computing . In Proceedings of the International Conference on Supercomputing. 330--339 . Shekhar Borkar, Robert Cohn, George Cox, Sha Gleason, and Thomas Gross. 1988. Warp: An integrated solution of high-speed parallel computing. In Proceedings of the International Conference on Supercomputing. 330--339."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2401716.2401724"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676939"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISVLSI.2011.59"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2011.239"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/NOCS.2012.8"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2011.190"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2014.2323219"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2007.77"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1874620.1874721"},{"key":"e_1_2_1_14_1","article-title":"Cost-effective design of mesh-of-tree interconnect for multi-core clusters with 3-D stacked L2 scratchpad memory","author":"Kang Kyungsu","year":"2014","unstructured":"Kyungsu Kang , Luca Benini , and Giovanni De Micheli . 2014 . Cost-effective design of mesh-of-tree interconnect for multi-core clusters with 3-D stacked L2 scratchpad memory . IEEE Trans. VLSI Syst. (to appear). Kyungsu Kang, Luca Benini, and Giovanni De Micheli. 2014. Cost-effective design of mesh-of-tree interconnect for multi-core clusters with 3-D stacked L2 scratchpad memory. IEEE Trans. VLSI Syst. (to appear).","journal-title":"IEEE Trans. VLSI Syst. (to appear)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/VLSID.2012.81"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/605397.605420"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250662.1250680"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/645535.657007"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISVLSI.2011.74"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505011"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC'13)","author":"Lee Jinho","year":"2013","unstructured":"Jinho Lee , Dongwoo Lee , Sunwook Kim , and Kiyoung Choi . 2013 b. Deflection routing in 3D network-on-chip with TSV serialization . In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC'13) . 29--34. Jinho Lee, Dongwoo Lee, Sunwook Kim, and Kiyoung Choi. 2013b. Deflection routing in 3D network-on-chip with TSV serialization. In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC'13). 29--34."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2006.18"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1950815.1950892"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2008.15"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2065990"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2006.12"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2013.6509553"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1898953.1899038"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133429.2133529"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2008.13"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629911.1630061"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/VLSID.2012.82"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1999946.1999957"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the International Symposium on High Performance Computing (ISHPC'00)","author":"Sancho Jos\u00e9 Carlos","year":"2000","unstructured":"Jos\u00e9 Carlos Sancho , Antonio Robles , and Jos\u00e9 Duato . 2000 a. A flexible routing scheme for networks of workstations . In Proceedings of the International Symposium on High Performance Computing (ISHPC'00) . 260--267. Jos\u00e9 Carlos Sancho, Antonio Robles, and Jos\u00e9 Duato. 2000a. A flexible routing scheme for networks of workstations. In Proceedings of the International Symposium on High Performance Computing (ISHPC'00). 260--267."},{"volume-title":"Network-Based Parallel Computing. Communication, Architecture, and Applications","author":"Sancho Jos\u00e9 Carlos","key":"e_1_2_1_35_1","unstructured":"Jos\u00e9 Carlos Sancho , Antonio Robles , and Jos\u00e9 Duato . 2000b. A new methodology to compute deadlock free REDELF: An energy-efficient deadlock-free routing for 3-D NoCs with partial vertical connections 23routing tables for irregular networks . In Network-Based Parallel Computing. Communication, Architecture, and Applications . Springer , 45--60. Jos\u00e9 Carlos Sancho, Antonio Robles, and Jos\u00e9 Duato. 2000b. A new methodology to compute deadlock free REDELF: An energy-efficient deadlock-free routing for 3-D NoCs with partial vertical connections 23routing tables for irregular networks. In Network-Based Parallel Computing. Communication, Architecture, and Applications. Springer, 45--60."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.105178"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1874620.1874626"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/645610.661560"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1736530.1736544"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/NOCS.2012.31"},{"key":"e_1_2_1_41_1","unstructured":"Tilera. 2009. The TILE-GxTM processor family. http:\/\/www.tilera.com\/products\/processors.  Tilera. 2009. The TILE-GxTM processor family. http:\/\/www.tilera.com\/products\/processors."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the Design, Automation, and Test in Europe Conference (DATE'14)","author":"Wettin Paul","year":"2014","unstructured":"Paul Wettin , Jacob Murray , Ryan Kim , Xinmin Yu , Partha Pratim Pande , and Deukhyoun Heo . 2014 . Performance evaluation of wireless NoCs in presence of irregular network routing strategies . In Proceedings of the Design, Automation, and Test in Europe Conference (DATE'14) . 1--6. Paul Wettin, Jacob Murray, Ryan Kim, Xinmin Yu, Partha Pratim Pande, and Deukhyoun Heo. 2014. Performance evaluation of wireless NoCs in presence of irregular network routing strategies. In Proceedings of the Design, Automation, and Test in Europe Conference (DATE'14). 1--6."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/223982.223990"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the International Symposium on Computer Architecture (ISCA'99)","author":"Wu Jie","year":"1999","unstructured":"Jie Wu and Li Sheng . 1999 . Deadlock-free routing in irregular networks using prefix routing . In Proceedings of the International Symposium on Computer Architecture (ISCA'99) . 424--430. Jie Wu and Li Sheng. 1999. Deadlock-free routing in irregular networks using prefix routing. In Proceedings of the International Symposium on Computer Architecture (ISCA'99). 424--430."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICISE.2010.5691765"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the International Symposium on High Performance Computer Architecture (HPCA'09)","author":"Xu Yi","year":"2009","unstructured":"Yi Xu , Yu Du , Bo Zhao , Xiuyi Zhou , Youtao Zhang , and Jun Yang . 2009 . A low-radix and low-diameter 3D interconnection network design . In Proceedings of the International Symposium on High Performance Computer Architecture (HPCA'09) . 30--42. Yi Xu, Yu Du, Bo Zhao, Xiuyi Zhou, Youtao Zhang, and Jun Yang. 2009. A low-radix and low-diameter 3D interconnection network design. In Proceedings of the International Symposium on High Performance Computer Architecture (HPCA'09). 30--42."},{"volume-title":"Design of application-specific 3D networks-on-chip architectures. In 3D Integration for NoC-Based SoC Architectures","author":"Yan Shan","key":"e_1_2_1_47_1","unstructured":"Shan Yan and Bill Lin . 2011. Design of application-specific 3D networks-on-chip architectures. In 3D Integration for NoC-Based SoC Architectures . Springer , 167--191. Shan Yan and Bill Lin. 2011. Design of application-specific 3D networks-on-chip architectures. In 3D Integration for NoC-Based SoC Architectures. Springer, 167--191."},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the International Conference on VLSI and System-on-Chip (VLSI-SoC'12)","author":"Zhu Mingyang","year":"2012","unstructured":"Mingyang Zhu , Jinho Lee , and Kiyoung Choi . 2012 . An adaptive routing algorithm for 3D mesh NoC with limited vertical bandwidth . In Proceedings of the International Conference on VLSI and System-on-Chip (VLSI-SoC'12) . 18--23. Mingyang Zhu, Jinho Lee, and Kiyoung Choi. 2012. An adaptive routing algorithm for 3D mesh NoC with limited vertical bandwidth. In Proceedings of the International Conference on VLSI and System-on-Chip (VLSI-SoC'12). 18--23."}],"container-title":["ACM Journal on Emerging Technologies in Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2751560","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2751560","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:07Z","timestamp":1750225387000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2751560"}},"subtitle":["An Energy-Efficient Deadlock-Free Routing for 3D NoCs with Partial Vertical Connections"],"short-title":[],"issued":{"date-parts":[[2015,9,21]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,9,21]]}},"alternative-id":["10.1145\/2751560"],"URL":"https:\/\/doi.org\/10.1145\/2751560","relation":{},"ISSN":["1550-4832","1550-4840"],"issn-type":[{"type":"print","value":"1550-4832"},{"type":"electronic","value":"1550-4840"}],"subject":[],"published":{"date-parts":[[2015,9,21]]},"assertion":[{"value":"2014-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}