Routing in a New 2-Dimensional FPGA/FPIC Routing Architecture

This paper studies the routing problem for a new Field-Programmable Gate Array (FPGA) and Field-Programmable Interconnect Chip (FPIC) routing architecture which improves upon the one proposed in [9] by providing continuing switches along the horizontal and vertical wire segments. The addition of continuing switches leads to higher routability and better timing performance than that for the routing architecture in [9]. A two-phase routing algorithm for the new routing architecture is developed. Both the initial routing phase and the rip-up and reroute phase employ a dynamic programming technique. The rip-up and reroute phase can also be applied to the segmented channel routing problem for row-based FPGA routing structures. Experimental results show that routability is improved dramatically and the number of active programmable switches in connecting paths and the total number of programmable switches are reduced, when compared with the results in [9] and [3]. The running time of the algorithm is less than 7 seconds for each of five industrial circuits.