Not necessarily more switches more routability [sic.]

TitleNot necessarily more switches more routability [sic.]
Publication TypeConference Paper
Year of Publication1997
AuthorsWu, Y-L, Chang, D, Marek-Sadowska, M, Tsukiyama, S
Conference NameDesign Automation Conference 1997. Proceedings of the ASP-DAC '97. Asia and South Pacific
Date Publishedjan
Keywords2D array, computational complexity, field programmable gate arrays, FPGA routing architecture, FPGA structures, global to detailed routing mapping, greedy routing architectures, H-tree, locally optimal switch box routing, mapping properties, network routing, NP-complete problem, optimal entire-chip routing, routability, switch number, switches, switches per switch box, switching circuits, switching theory, track number
AbstractIt has been observed experimentally that the mapping of global to detailed routing in a conventional FPGA routing architecture (2D array) yields unpredictable results. A different class of FPGA structures called greedy routing architectures (GRAs), where a locally optimal switch box routing can be extended to an optimal entire-chip routing, were investigated by Wu et al. (1994), Takashima et al. (1996) and Wu et al. (1996). It was shown that GRAs have good mapping properties. An H-tree GRA with W2+2W switches per switch box (SpSB) and a 2D array GRA with 4W2+2W SpSB were proposed by those authors (W is the number of tracks in each switch box). We continue this work by introducing an H-tree GRA with W2/2+2W SpSB and a 2D array GRA with 3.5 W2+2 W SpSB. These new GRAs have the same good mapping properties but use fewer switches. We also show a class of FPGA architectures in which the mapping problem remains NP-complete, even with 6(W-1)2+6W2 SpSB (this is close to the maximum number of SpSB, which is 6W2). Thus, more switches do not necessarily result in more routability
DOI10.1109/ASPDAC.1997.600339