ABSTRACT
Interconnection planning is becoming an important design issue for ASICs and large FPGAs. As the technology shrinks and the design density increases, proper planning of routing resources becomes all the more important to ensure rapid and feasible design convergence. One of the most important issues for planning interconnection is the ability to predict the routability of a given placed design. This paper provides insight into the workings of recently proposed method by Lou et. al.[Lou_Shankar] and compares it with our proposed methodology, fGREP[fGREP]. We have implemented the two methods for a generic FPGA architecture and compare the performance, accuracy and usability of their estimates. We use the well known FPGA physical design suite VPR[VPR], as a common comparison tool. Our experiments show that fGREP produces far better routing estimates but at larger execution times than Lou's method. Insight into what makes the methods work and where they falter are also discussed in detail.
- {1} H. B. Bakoglu. Circuit, Interconnections, and Packaging for VLSI. Addison Wesley, Reading, MA, 1990.Google Scholar
- {2} V. Betz and J. Rose. VPR: A New Packing, Placement and Routing Tool for FPGA research. In Field-Programmable Logic and Applications, pages 213-222. Springer-Verlag, Berlin, Sep. 1997. Google ScholarDigital Library
- {3} A. A. E. Gamal. Two-Dimensional Stochastic Model for Interconnections in Master Slice Integrated Circuits. IEEE Trans. CAS., Feb 1981.Google Scholar
- {4} M. Garey and D. Johnson. The Rectilinear Steiner Problem is NP-complete. SIAM Journal on Applied Mathematics , 32:826-834, 1977.Google ScholarCross Ref
- {5} J. Griffith, G. Robins, J. Salowe, and T. Zhang. Closing the Gap: Near Optimal Steiner Trees in Polynomial Time. IEEE Transactions on Computer-Aided Design, 13(11):1351-1365, November 1994.Google ScholarDigital Library
- {6} P. Kannan, S. Balachandran, and D. Bhatia. fGREP - Fast Generic Routing Demand Estimation for Placed FPGA Circuits. In Lecture Notes in Computer Science, Belfast, Northern Ireland, August 2001. 11th International Workshop on Field-Programmable Logic and Applications, FPL, Springer.Google Scholar
- {7} W. Li. Routability Prediction for Hierarchical FPGAs. In Proc. Great Lakes Symposium on VLSI, 1999. Google ScholarDigital Library
- {8} J. Lou, S. Krishnamoorthy, and H. Sheng. Estimating Routing Congestion using Probabilistic Analysis. In Proceedings of the 1999 International Symposium on Physical Design (ISPD), 2001. Google ScholarDigital Library
- {9} H. V. Marck, D. Stroobandt, and J. V. Campenhout. Toward an Extension of Rent's Rule for Describing Local Variations in Interconnection Complexity. In Proceedings of the 4th International Conference for Young Computer Scientists, pages 136-141, 1995.Google Scholar
- {10} L. McMurchie and C. Ebeling. PathFinder: A Negotiation-Based Performance-Driven Router for FPGAs. In ACM Symp. on FPGAs, FPGA95, pages 111-117. ACM, 1995. Google ScholarDigital Library
- {11} S. K. Nag and R. Rutenbar. Performance-driven Simultaneous Placement and Routing for FPGAs. IEEE Transactions on CAD, June 1998. Google ScholarDigital Library
- {12} G. Parthasarathy, M. Marek-Sadaowska, and A. Mukherjee. Interconnect Complexity-aware FPGA Placement Using Rent's Rule. In To appear in, Proc. Intl. Workshop on System Level Interconnect Prediction (SLIP), April 2001. Google ScholarDigital Library
- {13} S. Sastry and A. Parker. Stochastic Models for Wireability Analysis of Gate Arrays. IEEE Trans. on CAD, Jan 1986.Google Scholar
- {14} S. Brown, J. Rose, and Z. G. Vranesic. A Stochastic Model to Predict the Routability of Field Programmable Gate Arrays. IEEE Transactions on CAD, pages 1827-1838, Dec 1993.Google Scholar
- {15} M. Wang and M. Sarrafzadeh. Congestion Minimization During Placement. In Proceedings of the 1999 International Symposiumon Physical Design (ISPD), 1999. Google ScholarDigital Library
- {16} R. Wood and R. Rutenbar. FPGA Routing and Routability Estimation via Boolean Satisfiability. In ACM International Symposium on FPGAs FPGA98. ACM, June 1998. Google ScholarDigital Library
Recommendations
Routing-architecture-aware analytical placement for heterogeneous FPGAs
DAC '15: Proceedings of the 52nd Annual Design Automation ConferencePlacement is a crucial stage for FPGA implementation. Most FPGA placers optimize their placement results by minimizing half-perimeter wirelength (HPWL). Due to the segmented routing architecture in FPGAs, however, the HPWL function cannot model routed ...
Fast and accurate routing demand estimation for efficient routability-driven placement
DATE '07: Proceedings of the conference on Design, automation and test in EuropeThis paper presents a fast and accurate routing demand estimation called RUDY and its efficient integration in a force-directed quadratic placer to optimize placements for routability.
RUDY is based on a Rectangular Uniform wire DensitY per net and ...
Comments