CeRA: a router for symmetrical FPGAs based on exact routing density evaluation

We present a new performance and routability driven routing algorithm for symmetrical array-based field-programmable gate arrays (FPGAs). A key contribution of our work is the overcoming of one essential limitation of the previous routing algorithms: inaccurate estimations of routing density that were too general for symmetrical FPGAs. To this end, we formulate an exact routing density calculation that is based on a precise analysis of the structure (switch block) of symmetrical FPGAs and utilize it consistently in global and detailed routings. With an introduction to the proposed accurate routing metrics, we describe a new routing algorithm, called cost-effective net-decomposition-based routing, which is fast and yet produces remarkable routing results in terms of both routability and net/path delays. We performed extensive experiments to show the effectiveness of our algorithm based on the proposed cost metrics.