Graph-based detailed router for hierarchical field-programmable gate arrays

The paper presents a detailed routing algorithm for the hierarchical field-programmable gate arrays (HFPGAs). This algorithm is two phases. First performed in a multilevel transformed into a HFPGA is single-level HFPGA to find the initial routing results. The initial routing problem is reduced to the graph colouring and Steiner-tree problems. Two types of routing structure, disjointed and overlapped structures, are employed to specify different routing resources in order to improve the routing efficiency. In the second phase, the initial routing results are expanded to a multilevel HFPGA. Experimental results on a set of MCNC benchmark circuits show that the algorithm is very efficient. These results not only validate the claim on the performance of the algorithm but also facilitate the usage of the HFPGAs