Grey relational clustering associated with CAPRI applied to FPGA placement

Abstract

Grey relational clustering is used to minimise wire length during field programmable gate arrays (FPGA) placement and routing. The proposed Grey Relational Clustering Apply to Placement (GRAP) algorithm combines grey relational clustering and convex assigned placement for regular ICs method to construct a placement netlist, which was successfully used to solve the problem of minimising wire length in an FPGA placement. Upon calculating the grey relational grade, GRAP can rank the sequence and analyse the minimal distance in configuration logic blocks based on the grey relational sequence and combined connection-based approaches. The experimental results demonstrate that the GRAP effectively compares the Hibert, Z and Snake with bounding box (BB) cost function in the space-filling curve. The GRAP improved BB cost by 0.753%, 0.324% and 0.096% for the Hilbert, Z and Snake, respectively. This study also compares the critical path with the space-filling curve. The GRAP approach improved the critical path for Snake by 1.3% in the space-filling curve; however, the GRAP increased critical path wire by 1.38% and 0.03% over that of the Hilbert and Z of space-filling curve, respectively.

Keywords:

• grey relational clustering
• FPGA
• minimal wire length
• routing
• GRAP
• CAPRI
• space-filling curve

Additional information

Funding

The authors would like to thank the National Science Council of the Republic of China, Taiwan, for financially supporting this research under contract [NSC 99-2221-E-237-003].