Routability optimization for crossbar-switch structured ASIC design

• Published in: ACM transactions on design automation of electronic systems 2013-07, Vol.18 (3), p.1-28
• Main Authors: Tsai, Mei-Hsiang, Hsu, Po-Yang, Li, Hung-Yi, Hung, Yi-Huang, Liu, Yi-Yu
• Format: Article
• Language: English
• Subjects: Channels
• ISSN: 1084-4309; 1557-7309
• DOI: 10.1145/2491477.2491483

In the routing architecture of a structured application-specific integrated circuit (ASIC), the crossbar is one of the most area-efficient switch blocks. Nevertheless, a dangling wire occurs when there is a routing bend in a crossbar switch. Dangling wires incur longer wire lengths as well as a higher interconnection capacitance. In this article, we tackle dangling wire issues for structured ASIC routability optimization. We first propose a compact graph model for crossbar-switch routing. With our graph model, switch connectivity relations can be removed to keep the 2D structured ASIC routing graph efficient and to speed up the runtime of our routing algorithm. Furthermore, we propose a heuristic dangling-wire-avoidance routing framework containing deferred pin assignment, Steiner point reassignment, and anchor pair insertion in order to minimize dangling wires and channel width. Finally, in order to take routing bends and channel width into account simultaneously, we propose concurrent and sequential integer linear programming (ILP) formulations and ILP variable/constraint degeneration techniques. The experimental results demonstrate that our proposed heuristic routing framework reduces dangling wires by 19%, channel width by 38%, and wire length by 13% to VPR using the crossbar switch (VPR-C). In addition, our sequential ILP router reduces dangling wires by 38%, channel width by 40%, and wire length by 15% compared to VPR-C. Thus, the runtime efficiency of our sequential ILP router is attractive for crossbar-switch structured ASIC routing.