Due to the low cost and time, field-programmable gate arrays (FPGAs) have become the most popular tool for fast system prototyping. Unlike the routing problems of custom layouts such as standard cells and mask-programmed gate arrays in which wiring segments and vias can be drawn almost arbitrarily, the routing problem of FPGA is very restricted by the limited resources of the prefabricated wire segments and programmable switches. Thus general routing approaches for custom layouts may not be appropriate for FPGA routing.
This thesis proposes a new performance and routability-driven routing algorithm for symmetrical array-based FPGA. The routing problem has been studied by many researchers during the last decade but never truly accomplished. The contribution of our work is to overcome one of the most critical limitations of the previous routing algorithms: inaccurate estimations of routing density, which were too general for symmetrical FPGA. To this end, we devised new routing density measures that are directly linked to the structure (switch block) of symmetrical FPGA, and utilize them consistently in global and detailed routings.
With the use of the proposed accurate routing metrics, we developed a new routing algorithm called a reliable net decomposition-based routing. The proposed routing algorithm utilizes the routing resources effectively and, hence, increase the routability for the given connectivity limitation in symmetrical FPGA. The algorithm is very fast and yet produces excellent routing results in terms of net/path delays and routability. An extensive experiment was carried out to show the effectiveness of our algorithm based on the proposed cost metrics. The experimental results are compared to those obtained from previous routing algorithms for a given placement by adapting the same delay model of SEGA. To analyze the timing performance of the routed circuit, a static timing analyzer was implemented based on the breadth-first search. In summary, when compared to the best known results in the literature (TRACER-fpga_PR and SEGA), our algorithm has shown 31.9% shorter longest path delay and 23.0% shorter longest net delay even with about 9 times faster execution time.
