A regularity-driven fast gridless detailed router for high frequency datapath designs

ABSTRACT

We present a new detailed routing methodology specifically designed for datapath layouts. In typical state-of-the-art microprocessor designs, datapaths comprise about 70\% of the logic (excluding caches). Although research on datapath placement and global routing has been reported, very little research has been reported in the area of detailed routing for datapaths.Datapaths typically comprise regular {\em bit-slices} which are replicated. We define anet-cluster, which is collection of similarly structured nets present across different bit-slices. We introduce two clustering schemes (Footprint-driven clusteringandInstance-driven clustering) to extract such net-clusters. Then, we perform astrap-basedrouting on exactly one member net of each net-cluster (in a single representative bit-slice). Next, for each net, wepropagateits route to all other nets in its net-cluster. Our algorithm is unique in that it performs the detailed routing on asinglebit-slice, and infers the routing for all bit-slices using the notion of net clusters.We demonstrate at least 6$\times$ speed gains for industrial 32 and 64-bit datapath designs. The regularity of the routes across the bit-slices results in more predictable timing characteristics for the resulting datapath layout.

REFERENCES

• 1: Naveen Buddi , Malgorzata Chrzanowska-Jeske , Charles L. Saxe, Layout synthesis for datapath designs, Proceedings of the conference on European design automation, p.86-90, September 18-22, 1995, Brighton, England
• 2: Terry Tao Ye , Giovanni De Micheli, Data path placement with regularity, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 3: Jaewon Kim , S. M. Kang, A timing-driven data path layout synthesis with integer programming, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.716-719, November 05-09, 1995, San Jose, California, United States
• 4: Suresh Raman , Sachin S. Sapatnekar , Charles J. Alpert, Datapath routing based on a decongestion metric, Proceedings of the 2000 international symposium on Physical design, p.122-127, May 2000, San Diego, California, United States [doi>10.1145/332357.332387]
• 5: Srinivasa R. Arikati , Ravi Varadarajan, A signature based approach to regularity extraction, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.542-545, November 09-13, 1997, San Jose, California, United States
• 6: Soha Hassoun , Carolyn McCreary, Regularity extraction via clan-based structural circuit decomposition, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.414-419, November 07-11, 1999, San Jose, California, United States
• 7: C. Lee, "An algorithm for path connections and its applications," IRE Transactions on Electronic Computing, pp. 346-365, 1961.
• 8: L. Pugh, "An improvement in printed circuit board routability using a maze-running algorithm," Electronic Letters, vol. 14(1):8-9, Jan 1991.
• 9: J. Soukup and S. Fournier, "Pattern router," in Proceedings of the International Symposium on Circuits and Systems, pp. 486-489, 1979.
• 10: Tetsuo Asano, Parametric pattern router, Proceedings of the 19th conference on Design automation, p.411-417, January 1982

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Design, Experimentation, Theory