Wirelength Optimization for Multilevel Hierachical FPGA

The traditional placement methods for the island-style FPGA suffer from the conflicts of the unique architecture of the multilevel hierachical FPGA and the increasing capacity of FPGA. In this paper, we present an improved partitioning-based placement algorithm with three heuristic strategies, partition granularity strategy, vacancy distribution strategy and edge-weight assignment strategy. The partition granularity strategy works by deciding the number of sub-regions used to place blocks, vacancy distribution strategy acts through keeping each sub-region in relative balance and the edge-weight assignment strategy guides the min-cut partitions by giving the different weight to each nets, has abilities to deal with the circuits containing macro-blocks. Experiments on MCNC benchmark circuits show that our algorithm implements the placement with an average gain of 16.7% decrease of the total wirelength compared to the basic partitioning-based algorithms, but without increase in runtime.