{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:32:19Z","timestamp":1750221139196,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,4,18]],"date-time":"2019-04-18T00:00:00Z","timestamp":1555545600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100011698","name":"Junta de Comunidades de Castilla-La Mancha","doi-asserted-by":"crossref","award":["SBPLY\/17\/180501\/000498"],"award-info":[{"award-number":["SBPLY\/17\/180501\/000498"]}],"id":[{"id":"10.13039\/501100011698","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Excma"},{"name":"Diputacion de Albacete under the project DIPUAB18ESCUDEROSAHUQUIL"},{"name":"Spanish System of Science, Technology and Innovation"},{"name":"Spanish MINECO and European Commission","award":["TIN2015-66972-C5-2-R (MINECO\/FEDER)"],"award-info":[{"award-number":["TIN2015-66972-C5-2-R (MINECO\/FEDER)"]}]},{"DOI":"10.13039\/501100007480","name":"University of Castilla-La Mancha","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007480","id-type":"DOI","asserted-by":"crossref"}]},{"name":"UCLM research program"},{"name":"predoc","award":["BES-2013-063681"],"award-info":[{"award-number":["BES-2013-063681"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>\n            Hybrid and direct topologies are cost-efficient and scalable options to interconnect thousands of end nodes in high-performance computing (HPC) systems. They offer a rich path diversity, high bisection bandwidth, and a reduced diameter guaranteeing low latency. In these topologies, efficient deterministic routing algorithms can be used to balance smartly the traffic flows among the available routes. Unfortunately, congestion leads these networks to saturation, where the HoL blocking effect degrades their performance dramatically. Among the proposed solutions to deal with HoL blocking, the routing algorithms selecting alternative routes, such as adaptive and oblivious, can mitigate the congestion effects. Other techniques use queues to separate congested flows from non-congested ones, thus reducing the HoL blocking. In this article, we propose a new approach that reduces HoL blocking in hybrid and direct topologies using source-adaptive and oblivious routing. This approach also guarantees deadlock-freedom as it uses virtual networks to break potential cycles generated by the routing policy in the topology. Specifically, we propose two techniques, called\n            <jats:italic>Source-Adaptive Solution for Head-of-Line Blocking Avoidance<\/jats:italic>\n            (SASHA) and\n            <jats:italic>Oblivious Solution for Head-of-Line Blocking Avoidance<\/jats:italic>\n            (OSHA). Experiment results, carried out through simulations under different traffic scenarios, show that SASHA and OSHA can significantly reduce the HoL blocking.\n          <\/jats:p>","DOI":"10.1145\/3319805","type":"journal-article","created":{"date-parts":[[2019,4,19]],"date-time":"2019-04-19T16:56:23Z","timestamp":1555692983000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Combining Source-adaptive and Oblivious Routing with Congestion Control in High-performance Interconnects using Hybrid and Direct Topologies"],"prefix":"10.1145","volume":"16","author":[{"given":"Pedro","family":"Yebenes","sequence":"first","affiliation":[{"name":"University of Castilla-La Mancha, Spain"}]},{"given":"Jose","family":"Rocher-Gonzalez","sequence":"additional","affiliation":[{"name":"University of Castilla-La Mancha, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0835-8624","authenticated-orcid":false,"given":"Jesus","family":"Escudero-Sahuquillo","sequence":"additional","affiliation":[{"name":"University of Castilla-La Mancha, Spain"}]},{"given":"Pedro Javier","family":"Garcia","sequence":"additional","affiliation":[{"name":"University of Castilla-La Mancha, Spain"}]},{"given":"Francisco J.","family":"Alfaro","sequence":"additional","affiliation":[{"name":"University of Castilla-La Mancha, Spain"}]},{"given":"Francisco J.","family":"Quiles","sequence":"additional","affiliation":[{"name":"University of Castilla-La Mancha, Spain"}]},{"given":"Crisp\u00edn","family":"G\u00f3mez","sequence":"additional","affiliation":[{"name":"Technical University of Valencia, Valencia, Spain"}]},{"given":"Jose","family":"Duato","sequence":"additional","affiliation":[{"name":"Technical University of Valencia, Valencia, Spain"}]}],"member":"320","published-online":{"date-parts":[[2019,4,18]]},"reference":[{"volume-title":"SAND2013 - 4744","author":"Heroux M. A.","key":"e_1_2_1_1_1","unstructured":"M. A. Heroux and J. Dongarra . 2013. Toward a New Metric for Ranking High Performance Computing Systems . SAND2013 - 4744 . M. A. Heroux and J. Dongarra. 2013. Toward a New Metric for Ranking High Performance Computing Systems. SAND2013 - 4744."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2011.98"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/HOTI.2010.23"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/161541.161736"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-016-1757-0"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2014.34"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 18th Annual Joint Conference of the IEEE Computer and Communications Societies","volume":"1","author":"Breslau L.","unstructured":"L. Breslau , Pei Cao , Li Fan , G. Phillips , and S. Shenker . 1999. Web caching and Zipf-like distributions: Evidence and implications . In Proceedings of the 18th Annual Joint Conference of the IEEE Computer and Communications Societies , Vol. 1 . 126--134. L. Breslau, Pei Cao, Li Fan, G. Phillips, and S. Shenker. 1999. Web caching and Zipf-like distributions: Evidence and implications. In Proceedings of the 18th Annual Joint Conference of the IEEE Computer and Communications Societies, Vol. 1. 126--134."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2635640"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.127260"},{"volume-title":"Proceedings of the 6th IEEE Symposium on High-Performance Interconnects (Hot Interconnects\u201998)","author":"Dally W. J.","key":"e_1_2_1_10_1","unstructured":"W. J. Dally , P. Carvey , and L. Dennison . 1998. Architecture of the Avici terabit switch\/router . In Proceedings of the 6th IEEE Symposium on High-Performance Interconnects (Hot Interconnects\u201998) . 41--50. W. J. Dally, P. Carvey, and L. Dennison. 1998. Architecture of the Avici terabit switch\/router. In Proceedings of the 6th IEEE Symposium on High-Performance Interconnects (Hot Interconnects\u201998). 41--50."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2005.1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.09.002"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.303"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2014.2307851"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11587514_18"},{"volume-title":"Proceedings of the Communication Architecture for Clusters Workshop (CAC\u201907)","author":"Gomez C.","key":"e_1_2_1_16_1","unstructured":"C. Gomez , F. Gilabert , M. E. Gomez , P. Lopez , and J. Duato . 2007. Deterministic versus adaptive routing in fat-trees . In Proceedings of the Communication Architecture for Clusters Workshop (CAC\u201907) in Conjunction with the IEEE International Parallel 8 Distributed Processing Symposium (IPDPS\u201907). 235. C. Gomez, F. Gilabert, M. E. Gomez, P. Lopez, and J. Duato. 2007. Deterministic versus adaptive routing in fat-trees. In Proceedings of the Communication Architecture for Clusters Workshop (CAC\u201907) in Conjunction with the IEEE International Parallel 8 Distributed Processing Symposium (IPDPS\u201907). 235."},{"volume-title":"Proceedings of the IEEE International Symposium on Parallel Distributed Processing (IPDPS\u201910)","author":"Gran E. G.","key":"e_1_2_1_17_1","unstructured":"E. G. Gran , M. Eimot , S. Reinemo , T. Skeie , O. Lysne , L. P. Huse , and G. Shainer . 2010. First experiences with congestion control in InfiniBand hardware . In Proceedings of the IEEE International Symposium on Parallel Distributed Processing (IPDPS\u201910) . 1--12. E. G. Gran, M. Eimot, S. Reinemo, T. Skeie, O. Lysne, L. P. Huse, and G. Shainer. 2010. First experiences with congestion control in InfiniBand hardware. In Proceedings of the IEEE International Symposium on Parallel Distributed Processing (IPDPS\u201910). 1--12."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.28"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/CONECT.2005.14"},{"key":"e_1_2_1_20_1","article-title":"Phenomenon of higher order head-of-line blocking in multistage interconnection networks under nonuniform traffic patterns. IEICE","author":"Jurczyk M.","year":"1996","unstructured":"M. Jurczyk and T. Schwederski . 1996 . Phenomenon of higher order head-of-line blocking in multistage interconnection networks under nonuniform traffic patterns. IEICE Trans. Info. Syst. E79-D, 8 ( Aug. 1996), 1124--1129. M. Jurczyk and T. Schwederski. 1996. Phenomenon of higher order head-of-line blocking in multistage interconnection networks under nonuniform traffic patterns. IEICE Trans. Info. Syst. E79-D, 8 (Aug. 1996), 1124--1129.","journal-title":"Trans. Info. Syst. E79-D, 8"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1987.1096719"},{"volume-title":"Proceedings of the 4th International Symposium on High-Performance Computer Architecture. 47--56","author":"Katevenis M.","key":"e_1_2_1_22_1","unstructured":"M. Katevenis , D. Serpanos , and E. Spyridakis . 1998. Credit-flow-controlled ATM for MP interconnection: The ATLAS I single-chip ATM switch . In Proceedings of the 4th International Symposium on High-Performance Computer Architecture. 47--56 . M. Katevenis, D. Serpanos, and E. Spyridakis. 1998. Credit-flow-controlled ATM for MP interconnection: The ATLAS I single-chip ATM switch. In Proceedings of the 4th International Symposium on High-Performance Computer Architecture. 47--56."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1394608.1382129"},{"key":"e_1_2_1_24_1","first-page":"10","article-title":"Fat-trees: Universal networks for hardware-efficient supercomputing","volume":"34","author":"Leiserson C. E.","year":"1985","unstructured":"C. E. Leiserson . 1985 . Fat-trees: Universal networks for hardware-efficient supercomputing . IEEE Trans. Comput. 34 , 10 (Oct. 1985), 892--901. http:\/\/dl.acm.org\/citation.cfm?id&equals;4492.4495. C. E. Leiserson. 1985. Fat-trees: Universal networks for hardware-efficient supercomputing. IEEE Trans. Comput. 34, 10 (Oct. 1985), 892--901. http:\/\/dl.acm.org\/citation.cfm?id&equals;4492.4495.","journal-title":"IEEE Trans. Comput."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.1108"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2009.63"},{"key":"e_1_2_1_27_1","unstructured":"Ali Shafiee Naveen Muralimanohar and Vaishnav Srinivas. {n.d.}. CACTI v7.0\u2014A Tool to Model Caches\/Memories 3D stacking and off-chip IO. Retrieved from https:\/\/github.com\/HewlettPackard\/cacti.  Ali Shafiee Naveen Muralimanohar and Vaishnav Srinivas. {n.d.}. CACTI v7.0\u2014A Tool to Model Caches\/Memories 3D stacking and off-chip IO. Retrieved from https:\/\/github.com\/HewlettPackard\/cacti."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-016-1640-z"},{"volume-title":"Proceedings of the 25th IEEE HOTI. 65--72","author":"Rocher-Gonzalez J.","key":"e_1_2_1_29_1","unstructured":"J. Rocher-Gonzalez , J. Escudero-Sahuquillo , P. J. Garc\u00eda , and F. J. Quiles . 2017. On the impact of routing algorithms in the effectiveness of queuing schemes in high-performance interconnection networks . In Proceedings of the 25th IEEE HOTI. 65--72 . J. Rocher-Gonzalez, J. Escudero-Sahuquillo, P. J. Garc\u00eda, and F. J. Quiles. 2017. On the impact of routing algorithms in the effectiveness of queuing schemes in high-performance interconnection networks. In Proceedings of the 25th IEEE HOTI. 65--72."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"T. Schneider O. Bibartiu and T. Hoefler. 2016. Ensuring deadlock-freedom in low-diameter infiniband networks. In Hot Interconnects. IEEE Computer Society 1--8. Retrieved from http:\/\/dblp.uni-trier.de\/db\/conf\/hoti\/hoti2016.html#SchneiderBH16.  T. Schneider O. Bibartiu and T. Hoefler. 2016. Ensuring deadlock-freedom in low-diameter infiniband networks. In Hot Interconnects. IEEE Computer Society 1--8. Retrieved from http:\/\/dblp.uni-trier.de\/db\/conf\/hoti\/hoti2016.html#SchneiderBH16.","DOI":"10.1109\/HOTI.2016.015"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/HOTI.2016.021"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.144624"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/PDP.2013.36"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40047-6_70"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1712277.1712280"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3319805","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3319805","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:06Z","timestamp":1750208886000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3319805"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,18]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3319805"],"URL":"https:\/\/doi.org\/10.1145\/3319805","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2019,4,18]]},"assertion":[{"value":"2018-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}