The Formal Study Of Board Level Routing Problem Of FPGA

The board-level routing problem(BLRP) of FPGAs is a significantissue in integrated circuit design. In IC designs, FPGAs are configured toperform a IC design,Along with scale of designs growth, an IC design have to be loaded in a plurality of FPGA chips. The BLRP is mainly to solve the routing problem of these FPGAs which are loadedpart of a large IC design by a lot of interconnection nets.How to solve the BLRP is a hotspot of IC research. In this paper, we propose a SMT based method to solve the BLRP bystudyingthe BLRP and SMT.This paper mainly obtains the following research results: proposed an effective modeling method of translating the BLRP into SMT formulas, and then,we could solve SMT formulas with a fast SMT solver at lost. After then we proposed amethod to reduce the scale of BLRP.Experimental results demonstrate the effectiveness of the SMT based method and the ability to deal with larger more scale of BLRP. The reducing method is an efficient way to improve the computational efficiency of SMT based method.