{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:38:16Z","timestamp":1750307896942,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,4,1]],"date-time":"2007-04-01T00:00:00Z","timestamp":1175385600000},"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":[[2007,4]]},"abstract":"<jats:p>\n            A switch block of\n            <jats:italic>k<\/jats:italic>\n            sides\n            <jats:italic>W<\/jats:italic>\n            terminals on each side is said to be universal (a (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>W<\/jats:italic>\n            )-USB) if it is routable for every set of 2-pin nets of channel density at most\n            <jats:italic>W<\/jats:italic>\n            . The generic optimum universal switch block design problem is to design a (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>W<\/jats:italic>\n            )-USB with the minimum number of switches for every pair of (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>W<\/jats:italic>\n            ). This problem was first proposed and solved for\n            <jats:italic>k<\/jats:italic>\n            =4 in Chang et al. [1996], and then solved for even\n            <jats:italic>W<\/jats:italic>\n            or for\n            <jats:italic>k<\/jats:italic>\n            \u22646 in Shuy et al. [2000] and Fan et al. [2002b]. No optimum (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>W<\/jats:italic>\n            )-USB is known for\n            <jats:italic>k<\/jats:italic>\n            \u22657 and odd\n            <jats:italic>W<\/jats:italic>\n            \u22653. But it is already known that when\n            <jats:italic>W<\/jats:italic>\n            is a large odd number, a near-optimum (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>W<\/jats:italic>\n            )-USB can be obtained by a disjoint union of (\n            <jats:italic>W<\/jats:italic>\n            \u2212\n            <jats:italic>f<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            (\n            <jats:italic>k<\/jats:italic>\n            ))\/2 copies of the optimum (\n            <jats:italic>k<\/jats:italic>\n            , 2)-USB and a noncompound (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>f<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            (\n            <jats:italic>k<\/jats:italic>\n            ))-USB, where the value of\n            <jats:italic>f<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            (\n            <jats:italic>k<\/jats:italic>\n            ) is unknown for\n            <jats:italic>k<\/jats:italic>\n            \u22658. In this article, we show that\n            <jats:italic>f<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            (\n            <jats:italic>k<\/jats:italic>\n            ) =\n            <jats:italic>k<\/jats:italic>\n            +3\u2212\n            <jats:italic>i<\/jats:italic>\n            \/3, where 1\u2264\n            <jats:italic>i<\/jats:italic>\n            \u22646 and\n            <jats:italic>i<\/jats:italic>\n            \u2261\n            <jats:italic>k<\/jats:italic>\n            (mod 6), and present an explicit design for the noncompound (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>f<\/jats:italic>\n            <jats:sub>2<\/jats:sub>\n            (\n            <jats:italic>k<\/jats:italic>\n            ))-USB. Combining these two results we obtain the exact designs of (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>W<\/jats:italic>\n            )-USBs for all\n            <jats:italic>k<\/jats:italic>\n            \u22657 and odd\n            <jats:italic>W<\/jats:italic>\n            \u22653. The new (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>W<\/jats:italic>\n            )-USB designs also yield an efficient detailed routing algorithm.\n          <\/jats:p>","DOI":"10.1145\/1230800.1230811","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["The exact channel density and compound design for generic universal switch blocks"],"prefix":"10.1145","volume":"12","author":[{"given":"Hongbing","family":"Fan","sequence":"first","affiliation":[{"name":"Wilfrid Laurier University, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiping","family":"Liu","sequence":"additional","affiliation":[{"name":"University of Lethbridge, Lethbridge, AB, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yu-Liang","family":"Wu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shatin, NT, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chak-Chung","family":"Cheung","sequence":"additional","affiliation":[{"name":"Imperial College London, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,4]]},"reference":[{"volume-title":"Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications. 213--222","author":"Betz V.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Betz V. Rose J. and Morquardt A. 1999. Architecture and CAD for Deep-Submicron FPGAs. Kluwer Academic Boston MA.   Betz V. Rose J. and Morquardt A. 1999. Architecture and CAD for Deep-Submicron FPGAs. Kluwer Academic Boston MA.","DOI":"10.1007\/978-1-4615-5145-4"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Brown S; Francine R. J. Rose J. and Vranesic Z. G. 1992. Field-Programmable Gate Arrays. Kluwer Academic Boston MA.  Brown S; Francine R. J. Rose J. and Vranesic Z. G. 1992. Field-Programmable Gate Arrays. Kluwer Academic Boston MA.","DOI":"10.1007\/978-1-4615-3572-0"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/225871.225886"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11425-004-5192-y"},{"volume-title":"Proceedings of the IEEE International Conference on Computer-Aided Design (ICCAD) (Nov.). 93--98","author":"Fan H.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/378239.378464"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/605440.605443"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.980020"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Lemieux G. and Lewis D. 2003. Design of Interconnection Networks for Programmable Logic. Kluewer Academic Boston MA.   Lemieux G. and Lewis D. 2003. Design of Interconnection Networks for Programmable Logic. Kluewer Academic Boston MA.","DOI":"10.1007\/978-1-4757-4941-0"},{"key":"e_1_2_1_11_1","unstructured":"Lovasz L. and Pummer M. D. 1986. Matching Theory. Elsevier Science New York.  Lovasz L. and Pummer M. D. 1986. Matching Theory. Elsevier Science New York."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-9260(98)00011-X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/4.75006"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.844347"},{"key":"e_1_2_1_15_1","unstructured":"Wilton S. J. E. 1997. Architecture and algorithms for field-programmable gate arrays with embedded memory. Ph.D. thesis University of Toronto.   Wilton S. J. E. 1997. Architecture and algorithms for field-programmable gate arrays with embedded memory. Ph.D. thesis University of Toronto."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.486270"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1230800.1230811","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1230800.1230811","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:47:28Z","timestamp":1750258048000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1230800.1230811"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,4]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,4]]}},"alternative-id":["10.1145\/1230800.1230811"],"URL":"https:\/\/doi.org\/10.1145\/1230800.1230811","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2007,4]]},"assertion":[{"value":"2007-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}