{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:40:48Z","timestamp":1750308048311,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>The increasing clock frequencies in high-end industrial circuits bring new routing challenges that cannot be handled by traditional algorithms. An important design automation problem for high-speed boards today is routing nets within tight minimum and maximum length bounds. In this article, we propose an algorithm for routing bus structures between components on two layers such that all length constraints are satisfied. This algorithm handles length extension simultaneously during the actual routing process so that maximum resource utilization is achieved during length extension. Our approach here is to process one track at a time, and choose the best subset of nets to be routed on each track. The algorithm we propose for single-track routing is guaranteed to find the optimal subset of nets together with the optimal solution with length extension on one track. The experimental comparison with a recently proposed technique shows the effectiveness of this algorithm both in terms of solution quality and run-time.<\/jats:p>","DOI":"10.1145\/1124713.1124726","type":"journal-article","created":{"date-parts":[[2006,5,8]],"date-time":"2006-05-08T16:09:20Z","timestamp":1147104560000},"page":"213-227","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Two-layer bus routing for high-speed printed circuit boards"],"prefix":"10.1145","volume":"11","author":[{"given":"Muhammet Mustafa","family":"Ozdal","sequence":"first","affiliation":[{"name":"Intel Corporation, Hillsboro, OR"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin D. F.","family":"Wong","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,1]]},"reference":[{"volume-title":"Proceedings of the 7th International Workshop on Field-Programmable Logic. 213--222","author":"Betz V.","key":"e_1_2_1_1_1","unstructured":"Betz , V. and Rose , J . 1997. VPr: A new packing, placement and routing tool for FPGA research . In Proceedings of the 7th International Workshop on Field-Programmable Logic. 213--222 . Betz, V. and Rose, J. 1997. VPr: A new packing, placement and routing tool for FPGA research. In Proceedings of the 7th International Workshop on Field-Programmable Logic. 213--222."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Blazewicz J. Ecker K. H. and Pesch E. 2001. Scheduling Computer and Manufacturing Processes. Springer-Verlog New York.   Blazewicz J. Ecker K. H. and Pesch E. 2001. Scheduling Computer and Manufacturing Processes. Springer-Verlog New York.","DOI":"10.1007\/978-3-662-04363-9"},{"volume-title":"Proceedings of the Asia--Pacific Conference Circuits and Systems.","author":"Boese K. D.","key":"e_1_2_1_3_1","unstructured":"Boese , K. D. , Cong , J. , Kahng , A. B. , Leung , K. S. , and Zhou , D . 1992. On highspeed VLSI interconnects: Analysis and design . In Proceedings of the Asia--Pacific Conference Circuits and Systems. Boese, K. D., Cong, J., Kahng, A. B., Leung, K. S., and Zhou, D. 1992. On highspeed VLSI interconnects: Analysis and design. In Proceedings of the Asia--Pacific Conference Circuits and Systems."},{"volume-title":"Proceedings of the IEEE\/ACM 20th Design Automation Conference. ACM","author":"Burstein M.","key":"e_1_2_1_4_1","unstructured":"Burstein , M. and Pelavin , R . 1983. Hierarchical channel router . In Proceedings of the IEEE\/ACM 20th Design Automation Conference. ACM , New York, 591--597. Burstein, M. and Pelavin, R. 1983. Hierarchical channel router. In Proceedings of the IEEE\/ACM 20th Design Automation Conference. ACM, New York, 591--597."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/293625.293628"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.137519"},{"key":"e_1_2_1_7_1","unstructured":"Cormen T. H. Leiserson C. E. and Rivest R. L. 1992. Introduction to Algorithms. MIT Press Cambridge MA.   Cormen T. H. Leiserson C. E. and Rivest R. L. 1992. Introduction to Algorithms. MIT Press Cambridge MA."},{"volume-title":"Proceedings of the Design Automation Conference. 133--136","author":"Dunlop A. E.","key":"e_1_2_1_8_1","unstructured":"Dunlop , A. E. , Agrawal , V. D. , Deutsch , D. N. , Jukl , M. F. , Kozak , P. , and Wiesel , M . 1984. Chip layout optimization using critical path weighting . In Proceedings of the Design Automation Conference. 133--136 . Dunlop, A. E., Agrawal, V. D., Deutsch, D. N., Jukl, M. F., Kozak, P., and Wiesel, M. 1984. Chip layout optimization using critical path weighting. In Proceedings of the Design Automation Conference. 133--136."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.475966"},{"volume-title":"Proceedings of the 29th ACM\/IEEE Design Automation Conference, ACM","author":"Fang S. C.","key":"e_1_2_1_10_1","unstructured":"Fang , S. C. , Feng , W. S. , and Lee , S. L . 1992. A new efficient approach to multilayer channel routing problem . In Proceedings of the 29th ACM\/IEEE Design Automation Conference, ACM , New York, 579--584. Fang, S. C., Feng, W. S., and Lee, S. L. 1992. A new efficient approach to multilayer channel routing problem. In Proceedings of the 29th ACM\/IEEE Design Automation Conference, ACM, New York, 579--584."},{"volume-title":"Proceedings of the of 8th IEEE Design Automation Workshop. IEEE Computer Society Press","author":"Hashimoto A.","key":"e_1_2_1_11_1","unstructured":"Hashimoto , A. and Stevens , J . 1971. Wire routing by optimizing channel assignment within large apertures . In Proceedings of the of 8th IEEE Design Automation Workshop. IEEE Computer Society Press , Los Alamitos, CA. 214--224. 10.1145\/800158.805069 Hashimoto, A. and Stevens, J. 1971. Wire routing by optimizing channel assignment within large apertures. In Proceedings of the of 8th IEEE Design Automation Workshop. IEEE Computer Society Press, Los Alamitos, CA. 214--224. 10.1145\/800158.805069"},{"volume-title":"Proceedings of the 32nd ACM\/IEEE Design Automation Conference, ACM","author":"Huang D. J.-H.","key":"e_1_2_1_12_1","unstructured":"Huang , D. J.-H. , Kahng , A. B. , and Tsao , C . -W. A. 1995. On the bounded-skew clock and steiner routing problems . In Proceedings of the 32nd ACM\/IEEE Design Automation Conference, ACM , New York, 508--513. 10.1145\/217474.217579 Huang, D. J.-H., Kahng, A. B., and Tsao, C.-W. A. 1995. On the bounded-skew clock and steiner routing problems. In Proceedings of the 32nd ACM\/IEEE Design Automation Conference, ACM, New York, 508--513. 10.1145\/217474.217579"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Kahng A. B. and Robins G. 1995. On Optimal Interconnections in VLSI. Kluwer Academic Publishers.  Kahng A. B. and Robins G. 1995. On Optimal Interconnections in VLSI. Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4757-2363-2"},{"volume-title":"Proceedings of the IEEE International Symposium on Circuits and Systems, IEEE Computer Society Press","author":"Kuh E.","key":"e_1_2_1_14_1","unstructured":"Kuh , E. , Jackson , M. A. B. , and Marek-Sadowska , M . 1987. Timing-driven routing for building block layout . In Proceedings of the IEEE International Symposium on Circuits and Systems, IEEE Computer Society Press , Los Alamitos, CA. 518--519. Kuh, E., Jackson, M. A. B., and Marek-Sadowska, M. 1987. Timing-driven routing for building block layout. In Proceedings of the IEEE International Symposium on Circuits and Systems, IEEE Computer Society Press, Los Alamitos, CA. 518--519."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.809645"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the of IEEE International Conference on Computer-Aided Design. IEEE Computer Society Press","author":"Ozdal M. M.","year":"2003","unstructured":"Ozdal , M. M. and Wong , M . 2003. Length matching routing for high-speed printed circuit boards . In Proceedings of the of IEEE International Conference on Computer-Aided Design. IEEE Computer Society Press , Los Alamitos, CA. 10.1109\/ICCAD. 2003 .92 Ozdal, M. M. and Wong, M. 2003. Length matching routing for high-speed printed circuit boards. In Proceedings of the of IEEE International Conference on Computer-Aided Design. IEEE Computer Society Press, Los Alamitos, CA. 10.1109\/ICCAD.2003.92"},{"volume-title":"Proceedings of the of IEEE International Conference on Computer-Aided Design. IEEE Computer Society Press","author":"Prastjutrakul S.","key":"e_1_2_1_18_1","unstructured":"Prastjutrakul , S. and Kubitz , W. J . 1990. A timing-driven global router for custom chip design . In Proceedings of the of IEEE International Conference on Computer-Aided Design. IEEE Computer Society Press , Los Alamitos, CA. 48--51. Prastjutrakul, S. and Kubitz, W. J. 1990. A timing-driven global router for custom chip design. In Proceedings of the of IEEE International Conference on Computer-Aided Design. IEEE Computer Society Press, Los Alamitos, CA. 48--51."},{"key":"e_1_2_1_19_1","volume-title":"Busses: What are they and how do they work? Printed Circuit Design Magazine.","author":"Ritchey L. W.","year":"2000","unstructured":"Ritchey , L. W. 2000 . Busses: What are they and how do they work? Printed Circuit Design Magazine. Ritchey, L. W. 2000. Busses: What are they and how do they work? Printed Circuit Design Magazine."},{"volume-title":"Proceedings of the of IEEE\/ACM 19th Design Automation Conference. IEEE Computer Society Press","author":"Rivest R. L.","key":"e_1_2_1_20_1","unstructured":"Rivest , R. L. and Fiduccia , C. M . 1982. A greedy channel router . In Proceedings of the of IEEE\/ACM 19th Design Automation Conference. IEEE Computer Society Press , Los Alamitos, CA. 418--424. Rivest, R. L. and Fiduccia, C. M. 1982. A greedy channel router. In Proceedings of the of IEEE\/ACM 19th Design Automation Conference. IEEE Computer Society Press, Los Alamitos, CA. 418--424."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1985.1270096"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/567270.567271"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1982.1269993"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1124713.1124726","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1124713.1124726","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:14:35Z","timestamp":1750259675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1124713.1124726"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1145\/1124713.1124726"],"URL":"https:\/\/doi.org\/10.1145\/1124713.1124726","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2006,1]]},"assertion":[{"value":"2006-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}