Generic universal switch blocks

A switch block M with W terminals on each side is said to be universal if e very set of nets satisfying the dimension constraint (i.e., the number of n ets on each side of M is at most W) is simultaneously routable through M [2 ]. In this paper, we present an algorithm to construct N-sided universal sw itch blocks with W terminals on each side. Each of our universal switch blo cks has ((N)(2))W switches and switch-block flexibility N - 1 (i.e., FS = N - 1). We prove that no switch block with less than ((N)(2))W switches can be universal. We also compare our universal switch blocks with others of th e topology associated with Xilinx XC4000-type FPGAs. To explore the area pe rformance of the universal switch blocks, we develop a detailed router for hierarchical FPGAs (HFPGAs) with 5-sided switch blocks. Experimental result s demonstrate that our universal switch blocks improve routability at the c hip level. Based on extensive experiments, we also provide key insights int o the interactions between switch-block architectures and routing.