{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:33:03Z","timestamp":1750307583881,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2008,3,16]],"date-time":"2008-03-16T00:00:00Z","timestamp":1205625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0829911CCF-0702434"],"award-info":[{"award-number":["CCF-0829911CCF-0702434"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. Emerg. Technol. Comput. Syst."],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>The integration of novel nanotechnologies onto silicon platforms is likely to increase fabrication defects compared with traditional CMOS technologies. Furthermore, the number of nodes connected with these networks makes acquiring a global defect map impractical. As a result, on-chip networks will provide defect tolerance by self-organizing into irregular topologies. In this scenario, simple static routing algorithms based on regular physical topologies, such as meshes, will be inadequate. Additionally, previous routing approaches for irregular networks assume abundant resources and do not apply to this domain of resource-constrained self-organizing nano-scale networks. Consequently, routing algorithms that work in irregular networks with limited resources are needed.<\/jats:p>\n          <jats:p>In this article, we explore routing for self-organizing nano-scale irregular networks in the context of a Self-Organizing SIMD Architecture (SOSA). Our approach trades configuration time and a small amount of storage for reduced communication latency. We augment an Euler path-based routing technique for trees to generate static shortest paths between certain pairs of nodes while remaining deadlock free. Simulations of several applications executing on SOSA show our proposed routing algorithm can reduce execution time by 8% to 30%.<\/jats:p>","DOI":"10.1145\/1721650.1721653","type":"journal-article","created":{"date-parts":[[2010,3,16]],"date-time":"2010-03-16T19:25:36Z","timestamp":1268767536000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Routing in self-organizing nano-scale irregular networks"],"prefix":"10.1145","volume":"6","author":[{"given":"Yang","family":"Liu","sequence":"first","affiliation":[{"name":"Duke University, Durham, NC"}]},{"given":"Chris","family":"Dwyer","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC"}]},{"given":"Alvin R.","family":"Lebeck","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC"}]}],"member":"320","published-online":{"date-parts":[[2008,3,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/165123.165162"},{"key":"e_1_2_1_2_1","unstructured":"Bolotin E. Cidon I. Ginosar R. and Kolodny A. 2005. Efficient routing in irregular topology NoCs. Tech. rep. Department of Electrical Engineering Technion Haita Israel.  Bolotin E. Cidon I. Ginosar R. and Kolodny A. 2005. Efficient routing in irregular topology NoCs. Tech. rep. Department of Electrical Engineering Technion Haita Israel."},{"volume-title":"Proceedings of the Conference on Design, Automation and Test in Europe (DATE'07)","author":"Bolotin E.","key":"e_1_2_1_3_1","unstructured":"Bolotin , E. , Cidon , I. , Ginosar , R. , and Kolodny , A . 2007. Routing table minimization for irregular mesh Nocs . In Proceedings of the Conference on Design, Automation and Test in Europe (DATE'07) . 942--947. Bolotin, E., Cidon, I., Ginosar, R., and Kolodny, A. 2007. Routing table minimization for irregular mesh Nocs. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE'07). 942--947."},{"volume-title":"Proceedings of the 11th Euromicro Conference on Parallel, Distributed and Network-based Processing.","author":"Chi H.","key":"e_1_2_1_4_1","unstructured":"Chi , H. and Wu , W . 2003. Routing tree construction for interconnection networks . In Proceedings of the 11th Euromicro Conference on Parallel, Distributed and Network-based Processing. Chi, H. and Wu, W. 2003. Routing tree construction for interconnection networks. In Proceedings of the 11th Euromicro Conference on Parallel, Distributed and Network-based Processing."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/359657.359665"},{"volume-title":"Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom).","author":"De Pallegrini F.","key":"e_1_2_1_6_1","unstructured":"De Pallegrini , F. , Starobinski , D. , Karpovsky , M. G. , and Levitin , L. B . 2004. Scalable cycle-breaking algorithms for gigabit ethernet backbones . In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom). De Pallegrini, F., Starobinski, D., Karpovsky, M. G., and Levitin, L. B. 2004. Scalable cycle-breaking algorithms for gigabit ethernet backbones. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.877816"},{"volume-title":"Proceedings of the Conference on IEEE Computer Communications Workshops (InfoCom).","author":"Ibanez G. A.","key":"e_1_2_1_8_1","unstructured":"Ibanez , G. A. , Garcia-Martinez , A. , Carral , J. A. , and Gonzalez , P. A . 2008. Hierarchical up\/down routing architecture for ethernet backbones and campus networks . In Proceedings of the Conference on IEEE Computer Communications Workshops (InfoCom). Ibanez, G. A., Garcia-Martinez, A., Carral, J. A., and Gonzalez, P. A. 2008. Hierarchical up\/down routing architecture for ethernet backbones and campus networks. In Proceedings of the Conference on IEEE Computer Communications Workshops (InfoCom)."},{"volume-title":"Proceedings of the IEEE Computer Society Annual Symposium on VLSI","author":"Kumar S.","key":"e_1_2_1_9_1","unstructured":"Kumar , S. , Jantsch , A. , Soininen , J. P. , Forsell , M. , Millberg , M. , Oberg , J. , Tiensyrja , K. , and Hemani , A . 2002. A network on chip architecture and design methodology . In Proceedings of the IEEE Computer Society Annual Symposium on VLSI Kumar, S., Jantsch, A., Soininen, J. P., Forsell, M., Millberg, M., Oberg, J., Tiensyrja, K., and Hemani, A. 2002. A network on chip architecture and design methodology. In Proceedings of the IEEE Computer Society Annual Symposium on VLSI"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2006.14"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11796435_38"},{"volume-title":"Proceedings of the Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices. 344--358","author":"Patwardhan J. P.","key":"e_1_2_1_12_1","unstructured":"Patwardhan , J. P. , Dwyer , C. , Lebeck , A. R. , and Sorin , D. J . 2004. Circuit and system architecture for DNA-guided self-assembly of nanoelectronics . In Proceedings of the Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices. 344--358 . Patwardhan, J. P., Dwyer, C., Lebeck, A. R., and Sorin, D. J. 2004. Circuit and system architecture for DNA-guided self-assembly of nanoelectronics. In Proceedings of the Conference on Foundations of Nanoscience: Self-Assembled Architectures and Devices. 344--358."},{"volume-title":"Proceedings of the 1st International Conference on Nano-Networks (NANONETS).","author":"Patwardhan J. P.","key":"e_1_2_1_13_1","unstructured":"Patwardhan , J. P. , Dwyer , C. , and Lebeck , A. R . 2006a. Self-assembled networks: Control vs. complexity . In Proceedings of the 1st International Conference on Nano-Networks (NANONETS). Patwardhan, J. P., Dwyer, C., and Lebeck, A. R. 2006a. Self-assembled networks: Control vs. complexity. In Proceedings of the 1st International Conference on Nano-Networks (NANONETS)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1126257.1126258"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168888"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2004.28"},{"volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design.","author":"Schafer M. K. F.","key":"e_1_2_1_17_1","unstructured":"Schafer , M. K. F. , Hollstein , T. , Zimmer , H. , and Glesner , M . 2005. Deadlock-Free routing and component placement for irregular mesh-based networks-on-chip . In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design. Schafer, M. K. F., Hollstein, T., Zimmer, H., and Glesner, M. 2005. Deadlock-Free routing and component placement for irregular mesh-based networks-on-chip. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design."},{"key":"e_1_2_1_18_1","volume-title":"Autonet: A high-speed, self-configuring local area network using point-to-point links","author":"Schroeder M. D.","year":"1991","unstructured":"Schroeder , M. D. , Birrell , A. D. , Burrows , M. , Murray , H. , Needham , R. M. , Rodeheffer , T. L. , Satterthwaite , E. H. , and Thacker , C. P . 1991 . Autonet: A high-speed, self-configuring local area network using point-to-point links . IEEE J. Select. Areas Comm . 9. Schroeder, M. D., Birrell, A. D., Burrows, M., Murray, H., Needham, R. M., Rodeheffer, T. L., Satterthwaite, E. H., and Thacker, C. P. 1991. Autonet: A high-speed, self-configuring local area network using point-to-point links. IEEE J. Select. Areas Comm. 9."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2002.997877"},{"volume-title":"Proceedings of the International Parallel and Distributed Processing Symposium.","author":"Wiklund D.","key":"e_1_2_1_20_1","unstructured":"Wiklund , D. , and Liu , D . 2003. SoCBUS: Switched network on chip for hard real time embedded systems . In Proceedings of the International Parallel and Distributed Processing Symposium. Wiklund, D., and Liu, D. 2003. SoCBUS: Switched network on chip for hard real time embedded systems. In Proceedings of the International Parallel and Distributed Processing Symposium."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1038\/28998"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1089389"}],"container-title":["ACM Journal on Emerging Technologies in Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1721650.1721653","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1721650.1721653","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:41:20Z","timestamp":1750250480000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1721650.1721653"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3,16]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["10.1145\/1721650.1721653"],"URL":"https:\/\/doi.org\/10.1145\/1721650.1721653","relation":{},"ISSN":["1550-4832","1550-4840"],"issn-type":[{"type":"print","value":"1550-4832"},{"type":"electronic","value":"1550-4840"}],"subject":[],"published":{"date-parts":[[2008,3,16]]},"assertion":[{"value":"2009-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-03-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}