{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T22:40:09Z","timestamp":1751064009869,"version":"3.41.0"},"reference-count":34,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. & Syst."],"published-print":{"date-parts":[[2017]]},"DOI":"10.1587\/transinf.2017pap0019","type":"journal-article","created":{"date-parts":[[2017,11,30]],"date-time":"2017-11-30T22:26:45Z","timestamp":1512080805000},"page":"2796-2807","source":"Crossref","is-referenced-by-count":5,"title":["A Layout-Oriented Routing Method for Low-Latency HPC Networks"],"prefix":"10.1587","volume":"E100.D","author":[{"given":"Ryuta","family":"KAWANO","sequence":"first","affiliation":[{"name":"Dept. of ICS, Keio University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroshi","family":"NAKAHARA","sequence":"additional","affiliation":[{"name":"Dept. of ICS, Keio University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ikki","family":"FUJIWARA","sequence":"additional","affiliation":[{"name":"Universal Communication Research Institute, National Institute of Information and Communications Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroki","family":"MATSUTANI","sequence":"additional","affiliation":[{"name":"Dept. of ICS, Keio University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michihiro","family":"KOIBUCHI","sequence":"additional","affiliation":[{"name":"National Institute of Informatics"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hideharu","family":"AMANO","sequence":"additional","affiliation":[{"name":"Dept. of ICS, Keio University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","unstructured":"[1] K. Scott Hemmert et al, \u201cReport on Institute for Advanced Architectures and Algorithms, Interconnection Networks Workshop 2008,\u201d http:\/\/ft.ornl.gov\/doku\/_media\/iaaicw\/iaa-ic-2008-workshop-report-v09.pdf."},{"key":"2","unstructured":"[2] J. Tomkins, \u201cInterconnects: A Buyers Point of View,\u201d ACS Workshop, June 2007."},{"key":"3","doi-asserted-by":"crossref","unstructured":"[3] J.-Y. Shin, B. Wong, and E.G. Sirer, \u201cSmall-World Datacenters,\u201d Proc. of the Symposium on Cloud Computing (SoCC), pp.2:1-2:13, Oct. 2011. 10.1145\/2038916.2038918","DOI":"10.1145\/2038916.2038918"},{"key":"4","doi-asserted-by":"crossref","unstructured":"[4] M. Koibuchi, H. Matsutani, H. Amano, D.F. Hsu, and H. Casanova, \u201cA Case for Random Shortcut Topologies for HPC Interconnects,\u201d Proc. of the International Symposium on Computer Architecture (ISCA), pp.177-188, June 2012. 10.1109\/isca.2012.6237016","DOI":"10.1145\/2366231.2337179"},{"key":"5","unstructured":"[5] A. Singla, C.Y. Hong, L. Popa, and P.B. Godfrey, \u201cJellyfish: Networking Data Centers Randomly,\u201d Proc. of USENIX Symposium on Network Design and Implementation (NSDI), pp.225-238, April 2012."},{"key":"6","unstructured":"[6] S. Moh, C. Yu, H.Y. Youn, B. Lee, and D. Han, \u201cMapping Strategies for Switch-Based Cluster Systems of Irregular Topology,\u201d Proc. of the 8th International Conference on Parallel and Distributed Systems (ICPADS), pp.733-740, June 2001. 10.1109\/icpads.2001.934891"},{"key":"7","doi-asserted-by":"crossref","unstructured":"[7] H. Subramoni, S. Potluri, K. Kandalla, B. Barth, J. Vienne, J. Keasler, K. Tomko, K. Schulz, A. Moody, and D.K. Panda, \u201cDesign of a Scalable InfiniBand Topology Service to Enable Network-Topology-Aware Placement of Processes,\u201d Proc. of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pp.1-12, Nov. 2012. 10.1109\/sc.2012.47","DOI":"10.1109\/SC.2012.47"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] M. Koibuchi, I. Fujiwara, H. Matsutani, and H. Casanova, \u201cLayout-conscious Random Topologies for HPC Off-chip Interconnects,\u201d Proc. of the International Symposium on High Performance Computer Architecture (HPCA), pp.484-495, June 2013. 10.1109\/hpca.2013.6522343","DOI":"10.1109\/HPCA.2013.6522343"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] I. Fujiwara, M. Koibuchi, H. Matsutani, and H. Casanova, \u201cSwap-And-Randomize: A Method for Building Low-Latency HPC Interconnects,\u201d IEEE Trans. Parallel Distrib. Syst. (TPDS), vol.26, no.7, pp.2051-2060, July 2015. 10.1109\/tpds.2014.2340863","DOI":"10.1109\/TPDS.2014.2340863"},{"key":"10","doi-asserted-by":"publisher","unstructured":"[10] J. Flich, T. Skeie, A. Mejia, O. Lysne, P. Lopez, A. Robles, J. Duato, M. Koibuchi, T. Rokicki, and J.C. Sancho, \u201cA Survey and Evaluation of Topology-Agnostic Deterministic Routing Algorithms,\u201d IEEE Trans. Parallel Distrib. Syst. (TPDS), vol.23, no.3, pp.405-425, March 2012. 10.1109\/tpds.2011.190","DOI":"10.1109\/TPDS.2011.190"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[11] R. Kawano, H. Nakahara, I. Fujiwara, H. Matsutani, M. Koibuchi, and H. Amano, \u201cLOREN: A Scalable Routing Method for Layout-conscious Random Topologies,\u201d Proc. of the 4th International Symposium on Computing and Networking (CANDAR), pp.9-18, Nov. 2016. 10.1109\/candar.2016.0019","DOI":"10.1109\/CANDAR.2016.0019"},{"key":"12","doi-asserted-by":"crossref","unstructured":"[12] J. Kim, W.J. Dally, and D. Abts, \u201cFlattened Butterfly: a Cost-Efficient Topology for High-Radix Networks,\u201d Proc. of the International Symposium on Computer Architecture (ISCA), pp.126-137, June 2007. 10.1145\/1250662.1250679","DOI":"10.1145\/1273440.1250679"},{"key":"13","doi-asserted-by":"crossref","unstructured":"[13] J. Kim, W.J. Dally, S. Scott, and D. Abts, \u201cTechnology-Driven, Highly-Scalable Dragonfly Topology,\u201d Proc. of the International Symposium on Computer Architecture (ISCA), pp.77-88, June 2008. 10.1109\/isca.2008.19","DOI":"10.1145\/1394608.1382129"},{"key":"14","doi-asserted-by":"publisher","unstructured":"[14] M.R. Samatham and D.K. Pradhan, \u201cThe De Bruijn Multiprocessor Network: A Versatile Parallel Processing and Sorting Network for VLSI,\u201d IEEE Trans. Comput. (TC), vol.38, no.4, pp.567-581, April 1989. 10.1109\/12.21149","DOI":"10.1109\/12.21149"},{"key":"15","unstructured":"[15] S.B. Akers, B. Krishnamurthy, and D. Harel, \u201cThe Star Graph: An Attractive Alternative to the n-Cube,\u201d Proc. of the International Conference on Parallel Processing (ICPP), pp.393-400, Jan. 1987."},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] M. Miller and J. \u0160ir\u00e1\u0148, \u201cMoore Graphs and Beyond: A survey of the Degree\/Diameter Problem,\u201d Electronic Journal of Combinatorics, vol.20, no.2, pp.1-92, Nov. 2013.","DOI":"10.37236\/35"},{"key":"17","doi-asserted-by":"publisher","unstructured":"[17] P.R. Hafner, \u201cThe Hoffman-Singleton Graph and its Automorphisms,\u201d Journal of Algebraic Combinatorics, vol.18, no.1, pp.7-12, 2003. 10.1023\/a:1025136524481","DOI":"10.1023\/A:1025136524481"},{"key":"18","doi-asserted-by":"crossref","unstructured":"[18] W. Bao, B. Fu, M. Chen, and L. Zhang, \u201cA High-Performance and Cost-Efficient Interconnection Network for High-Density Servers,\u201d Proc. of the IEEE 10th International Conference on High Performance Computing and Communications & IEEE International Conference on Embedded and Ubiquitous Computing (HPCC_EUC), pp.1246-1253, Nov. 2013. 10.1109\/hpcc.and.euc.2013.177","DOI":"10.1109\/HPCC.and.EUC.2013.177"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[19] P.R. Hafner, \u201cGeometric realisation of the graphs of McKay-Miller-\u0160ir\u00e1\u0148,\u201d Journal of Combinatorial Theory, Series B, vol.90, no.2, pp.223-232, March 2004. 10.1016\/j.jctb.2003.07.002","DOI":"10.1016\/j.jctb.2003.07.002"},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] M. Besta and T. Hoefler, \u201cSlim Fly: A Cost Effective Low-Diameter Network Topology,\u201d Proc. of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pp.348-359, Nov. 2014. 10.1109\/sc.2014.34","DOI":"10.1109\/SC.2014.34"},{"key":"21","unstructured":"[21] \u201cThe degree diameter problem for general graphs,\u201d http:\/\/combinatoricswiki.org\/wiki\/The_Degree_Diameter_Problem_for_General_Graphs\/."},{"key":"22","unstructured":"[22] \u201cGraph golf: The order\/degree problem competition,\u201d http:\/\/research.nii.ac.jp\/graphgolf\/."},{"key":"23","doi-asserted-by":"publisher","unstructured":"[23] \u00dc.Y. Ogras and R. Marculescu, \u201c\u201cIt's a Small World After All\u201d: NoC Performance Optimization Via Long-Range Link Insertion,\u201d IEEE Transactions on Very Large Scale Integration Systems (TVLSI), vol.14, no.7, pp.693-706, July 2006. 10.1109\/tvlsi.2006.878263","DOI":"10.1109\/TVLSI.2006.878263"},{"key":"24","doi-asserted-by":"crossref","unstructured":"[24] A. Brady and L. Cowen, \u201cCompact Routing on Power Law Graphs with Additive Stretch,\u201d Proc. of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX), pp.119-128, Jan. 2006.","DOI":"10.1137\/1.9781611972863.12"},{"key":"25","doi-asserted-by":"publisher","unstructured":"[25] L.J. Cowen, \u201cCompact Routing with Minimum Stretch,\u201d Proc. of the ACM-SIAM Symposium on Discrete Algorithms (SODA), vol.38, no.1, pp.170-183, 2001. 10.1006\/jagm.2000.1134","DOI":"10.1006\/jagm.2000.1134"},{"key":"26","doi-asserted-by":"crossref","unstructured":"[26] M. Thorup and U. Zwick, \u201cCompact Routing Schemes,\u201d Proc. of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp.1-10, July 2001. 10.1145\/378580.378581","DOI":"10.1145\/378580.378581"},{"key":"27","doi-asserted-by":"crossref","unstructured":"[27] I. Fujiwara, M. Koibuchi, H. Matsutani, and H. Casanova, \u201cSkywalk: A Topology for HPC Networks with Low-Delay Switches,\u201d Proc. of the IEEE 28th International Parallel and Distributed Processing Symposium (IPDPS), pp.263-272, May 2014. 10.1109\/ipdps.2014.37","DOI":"10.1109\/IPDPS.2014.37"},{"key":"28","doi-asserted-by":"crossref","unstructured":"[28] N. Jiang, J. Balfour, D.U. Becker, B. Towles, W.J. Dally, G. Michelogiannakis, and J. Kim, \u201cA Detailed and Flexible Cycle-Accurate Network-on-Chip Simulator,\u201d Proc. of the IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pp.86-96, April 2013. 10.1109\/ispass.2013.6557149","DOI":"10.1109\/ISPASS.2013.6557149"},{"key":"29","doi-asserted-by":"crossref","unstructured":"[29] R. Kawano, H. Nakahara, S. Tade, I. Fujiwara, H. Matsutani, M. Koibuchi, and H. Amano, \u201cACRO: Assignment of Channels in Reverse Order to Make Arbitrary Routing Deadlock-free,\u201d Proc. of the 15th IEEE\/ACIS International Conference on Computer and Information Science (ICIS), pp.565-570, June 2016. 10.1109\/icis.2016.7550818","DOI":"10.1109\/ICIS.2016.7550818"},{"key":"30","doi-asserted-by":"crossref","unstructured":"[30] T. Skeie, O. Lysne, J. Flich, P. Lopez, A. Robles, and J. Duato, \u201cLASH-TOR: A Generic Transition-Oriented Routing Algorithm,\u201d Proc. of the 10th International Conference on Parallel and Distributed Systems (ICPADS), pp.595-604, July 2004. 10.1109\/icpads.2004.1316144","DOI":"10.1109\/ICPADS.2004.1316144"},{"key":"31","unstructured":"[31] W.J. Dally and B. Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann, 2004."},{"key":"32","doi-asserted-by":"crossref","unstructured":"[32] T. Hoefler, T. Schneider, and A. Lumsdaine, \u201cMultistage Switches are not Crossbars: Effects of Static Routing in High-Performance Networks,\u201d Proc. of the IEEE International Conference on Cluster Computing (CLUSTER), pp.116-125, Sept. 2008. 10.1109\/clustr.2008.4663762","DOI":"10.1109\/CLUSTR.2008.4663762"},{"key":"33","doi-asserted-by":"crossref","unstructured":"[33] X. Yuan, S. Mahapatra, M. Lang, and S. Pakin, \u201cLFTI: A New Performance Metric for Assessing Interconnect Designs for Extreme-Scale HPC Systems,\u201d Proc. of the IEEE 28th International Parallel and Distributed Processing Symposium (IPDPS), pp.273-282, May 2014. 10.1109\/ipdps.2014.38","DOI":"10.1109\/IPDPS.2014.38"},{"key":"34","doi-asserted-by":"crossref","unstructured":"[34] V. Latora and M. Marchiori, \u201cEfficient Behavior of Small-World Networks,\u201d Physical Review Letters, vol.87, no.19, pp.198701:1-198701:4, Oct. 2001. 10.1103\/physrevlett.87.198701","DOI":"10.1103\/PhysRevLett.87.198701"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E100.D\/12\/E100.D_2017PAP0019\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T22:17:53Z","timestamp":1751062673000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E100.D\/12\/E100.D_2017PAP0019\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"references-count":34,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2017]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2017pap0019","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"type":"print","value":"0916-8532"},{"type":"electronic","value":"1745-1361"}],"subject":[],"published":{"date-parts":[[2017]]}}}