Integer Programming Based Routing Algorithm for Hierarchical FPGAs

In order to avoid the unroutability caused by the bad net-routing sequence,this paper presents a routing algorithm for hierarchical FPGAs(HFPGAs) based on integer programming.It employs global optimization method to solve the routing problem.By analyzing the architecture of HFPGAs and the features of the integer programming,we get the corresponding relationship between the problem of the routing and the integer programming model.Then the process of conversions from the FPGA routing constraints to the modeling of the binary integer programming is discussed in detail.At this stage,it takes advantage of the architectural characteristics of HFPGAs to simplify the resulted model.At last the integer programming based FPGA routing algorithm is implemented,compared with the SAT algorithm by experiments.The experimental results show that the proposed routing algorithm has advantages of high speed,large scale and good quality.