{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:27:51Z","timestamp":1763458071936,"version":"3.45.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,9,1]],"date-time":"2017-09-01T00:00:00Z","timestamp":1504224000000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"crossref","award":["W911NF-12-1-0373"],"award-info":[{"award-number":["W911NF-12-1-0373"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000015","name":"US DOE","doi-asserted-by":"crossref","award":["DE-SC-0006516"],"award-info":[{"award-number":["DE-SC-0006516"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["CCF-0845504, CCF-1514269 and CCF-1162202"],"award-info":[{"award-number":["CCF-0845504, CCF-1514269 and CCF-1162202"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p>With its applicability spanning numerous data-driven fields, the implementation of graph analytics on multicore platforms is gaining momentum. One of the most important components of a multicore chip is its communication backbone. Due to inherent irregularities in data movements manifested by graph-based applications, it is essential to design efficient on-chip interconnection architectures for multicore chips performing graph analytics. In this article, we present a detailed analysis of the traffic patterns generated by graph-based applications when mapped to multicore chips. Based on this analysis, we explore the design-space for the Network-on-Chip (NoC) architecture to enable an efficient implementation of graph analytics. We principally consider three types of NoC architectures, viz., traditional mesh, small-world, and high-radix networks. We demonstrate that the small-world-network-enabled wireless NoC (WiNoC) is the most suitable platform for executing the considered graph applications. The WiNoC achieves an average of 38% and 18% full-system Energy Delay Product savings compared to wireline-mesh and high-radix NoCs, respectively.<\/jats:p>","DOI":"10.1145\/2961027","type":"journal-article","created":{"date-parts":[[2016,9,1]],"date-time":"2016-09-01T14:24:38Z","timestamp":1472739878000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["High-Performance and Energy-Efficient Network-on-Chip Architectures for Graph Analytics"],"prefix":"10.1145","volume":"15","author":[{"given":"Karthi","family":"Duraisamy","sequence":"first","affiliation":[{"name":"Washington State University at Pullman, Pullman, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hao","family":"Lu","sequence":"additional","affiliation":[{"name":"Washington State University at Pullman, Pullman, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Partha Pratim","family":"Pande","sequence":"additional","affiliation":[{"name":"Washington State University at Pullman, Pullman, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ananth","family":"Kalyanaraman","sequence":"additional","affiliation":[{"name":"Washington State University at Pullman, Pullman, WA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2013.6522344"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2005.55"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2024716.2024718"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.027"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSTQE.2013.2295882"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/LED.2004.841461"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535753.2535757"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2012.07.001"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of HiPC 2014","author":"Chavarr\u00eda-Miranda D.","year":"2014","unstructured":"D. Chavarr\u00eda-Miranda, M. Halappanavar, and A. Kalyanaraman. 2014. Scaling graph community detection on the tilera manycore architecture. In Proceedings of HiPC 2014, Goa, India, 2014."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2388996.2389090"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676939"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2616606.2616725"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/JETCAS.2012.2193835"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2012.224"},{"volume-title":"The 10th DIMACS implementation challenge -- Graph partioning and clustering. URL: http:\/\/www.cc.gatech.edu\/dimacs10\/ (Last date accessed","year":"2016","key":"e_1_2_1_15_1","unstructured":"DIMACS10. 2016. The 10th DIMACS implementation challenge -- Graph partioning and clustering. URL: http:\/\/www.cc.gatech.edu\/dimacs10\/ (Last date accessed: May 2016)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"K. Duraisamy R. G. Kim and P. P. Pande. 2015. Enhancing performance of wireless NoCs with distributed MAC protocols. In Proceeedings of ISQED. 2015.","DOI":"10.1109\/ISQED.2015.7085460"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"D. Ediger. 2013. Analyzing Hybrid Architectures for Massively Parallel Graph Analysis. Ph.D. Dissertation Georgia Institute of Technology Atlanta Ga. (May 2013).","DOI":"10.1109\/IPDPSW.2013.172"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2014.11.002"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2388996.2389125"},{"volume-title":"Contemporary Mathematics","author":"Furmanczyk H.","key":"e_1_2_1_21_1","unstructured":"H. Furmanczyk. 2004. Equitable coloring of graphs. In Graph Colorings, M. Kubale (Ed.). Contemporary Mathematics, Vol. 352. American Mathematical Society, Providence, Rhode Island, 35--53."},{"key":"e_1_2_1_22_1","first-page":"1","article-title":"Adapteva: More flops, less watts: Epiphany offers floating-point accelerator for mobile processors","volume":"2","author":"Gwennup L.","year":"2011","unstructured":"L. Gwennup. 2011. Adapteva: More flops, less watts: Epiphany offers floating-point accelerator for mobile processors. Microprocess. Rep 2, 1--5.","journal-title":"Microprocess. Rep"},{"key":"e_1_2_1_23_1","unstructured":"T. R. Jensen and B. Toft. 1995. Graph Coloring Problems. Wiley Series in Discrete Mathematics and Optimization Wiley Interscience New York."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0914041"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/L-CA.2007.10"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/HOTI.2008.22"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2013.260"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2014.48"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2008.18"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.084.024"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1669112.1669172"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSSC.2007.900236"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2015.03.003"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2015.113"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.2010691"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601602103"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2006.878263"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2005.134"},{"key":"e_1_2_1_39_1","volume-title":"De Los Rios","author":"Petermann T.","year":"2005","unstructured":"T. Petermann and P. De Los Rios. 2005. Spatial small-world networks: A wiring cost perspective. arXiv: Condmat\/0501420v2."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","unstructured":"J. E. Riedy H. Meyerhenke D. Ediger and D. A. Bader. 2012. Parallel community detection for massive graphs. In Parallel Processing and Applied Mathematics. Springer Berlin 286--296. 10.1007\/978-3-642-31464-3_29","DOI":"10.1007\/978-3-642-31464-3_29"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/829576"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1038\/nrg2857"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of IEEE International Interconnect Technology Conference. 6--8, 120--122","author":"Seok E.","year":"2005","unstructured":"E. Seok and K. K. O. 2005. Design rules for improving predictability of on-chip antenna characteristics in the presence of other metal structures. In Proceedings of IEEE International Interconnect Technology Conference. 6--8, 120--122."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/JETCAS.2012.2193936"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2013.27"},{"key":"e_1_2_1_46_1","unstructured":"Tilera Corporation. 2015. TILE-Gx72 Processor Product Brief. http:\/\/www.tilera.com\/files\/drim__TILE-Gx8072_PB041-04_WEB_7683.pdf (Last Accessed: May. 2016)."},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"D. J. Watts and S. H. Strogatz. 1998. Collective dynamics of \u2018small-world\u2019 networks. Letters to Nature. 393.6684 440--442.","DOI":"10.1038\/30918"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2014.2351577"},{"volume-title":"Proceedings of 7th International Conference on Natural Computation (ICNC). 43--47","author":"Wu B.","key":"e_1_2_1_49_1","unstructured":"B. Wu, Y. Dong, Q. Ke, and Y. Cai. 2011. A parallel computing model for large graph mining with MapReduce. In Proceedings of 7th International Conference on Natural Computation (ICNC). 43--47."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAP.2007.905867"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2961027","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2961027","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2961027","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:16:52Z","timestamp":1763457412000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2961027"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1145\/2961027"],"URL":"https:\/\/doi.org\/10.1145\/2961027","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2016,9]]},"assertion":[{"value":"2015-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-09-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}