Multilevel Based Global Routing Algorithm for Hierarchical FPGA*

This paper presents an efficient global routing algorithm for a hierarchical inter-connection architecture of FPGA. What is different from the traditional FPGA rout-ing algorithm is that the proposed algo-rithm takes advantage of the hierarchical structure of this particular FPGA. We use a hierarchical tree as the routing resource representation of the corresponding inter-connection architecture. In the routing phase, the global routing problem for each net is represented as a sub-tree de-termination problem. As soon as the loca-tion of each Logic Block is fixed, we can use a tree-growth-like algorithm to de-termine the sub-tree on the corresponding routing resource tree. The algorithm is very efficient and fast since the sub-tree is determined once we determined the po-sition of each Logic Block. On the other hand, we can use this method to evaluate the routability of the corresponding placement results