Title :
Optimal MST-based graph algorithm on FPGA segmentation design
Author :
Zhou, Catherine L. ; Wu, Yu-Liang
Author_Institution :
Dept. of Comput. Sci. & Eng., Chinese Univ. of Hong Kong, China
Abstract :
The FPGA is currently widely used in digital systems. Its routability has a close relationship with the physical architecture. The application of switches improves the flexibility of the nets to be routed. Too many switches, however, bring a great performance penalty because of their high resistance and capacitance. To balance routing flexibility and performance constraints, the graph matching-based algorithm was proposed to construct good segmentation designs (Y.-W. Chang et al., Proc. IEEE/ACM Int. Conf. on CAD, p.34-9, 1998; J.-M. Lin et al., Proc. ASP-DAC 2003, p.851-4, 2003). It attempts to maximize routability under performance constraints. During the execution of the algorithm, the paring scheme affects the outcome, so that the solution may not be optimal. We enhance the algorithm and present the MST-based graph algorithm. It is optimal for both row-based FPGAs and array-based FPGAs. The results are independent of the net merging order. We conducted experiments on ten sets of routing instances. The results show 4.31% reduction of net length from the matching-based algorithm to the MST-based algorithm.
Keywords :
circuit layout CAD; field programmable gate arrays; integrated circuit layout; logic CAD; network routing; trees (mathematics); FPGA segmentation design; array-based FPGA; graph matching-based algorithm; maximum spanning tree based graph algorithm; net length; net merging order; paring scheme; performance constraints; routability; routing flexibility; row-based FPGA; Algorithm design and analysis; Capacitance; Computer architecture; Computer science; Design engineering; Digital systems; Field programmable gate arrays; Routing; Switches; Tree graphs;
Conference_Titel :
Communications, Circuits and Systems, 2004. ICCCAS 2004. 2004 International Conference on
Print_ISBN :
0-7803-8647-7
DOI :
10.1109/ICCCAS.2004.1346409