Variation-aware resource sharing and binding in behavioral synthesis

ABSTRACT

As technology scales, the delay uncertainty caused by process variations has become increasingly pronounced in deep submicron designs. In the presence of process variations, worst-case timing analysis may lead to overly conservative synthesis, and may end up using excess resources to guarantee design constraints. In this paper, we propose an efficient variation-aware resource sharing and binding algorithm in behavioral synthesis, which takes into account the performance variations for functional units. The performance yield, which is defined as the probability that the synthesized hardware meets the target performance constraints, is used to evaluate the synthesis result. An efficient metric called statistical performance improvement, is used to guide resource sharing and binding. The proposed algorithm is evaluated within a commercial synthesis framework that generates optimized RTL netlists from behavioral specifications. The effectiveness of the proposed algorithm is demonstrated with a set of industrial benchmark designs, which consist of blocks that are commonly used in wireless and image processing applications. The experimental results show that our method achieves an average 33% area reduction over traditional methods, which are based on the worst-case delay analysis, with an average 10% run time overhead.¹

REFERENCES

• 1: Anand Raghunathan , Niraj K. Jha , Sujit Dey, High-Level Power Analysis and Optimization, Kluwer Academic Publishers, Norwell, MA, 1998
• 2: Daniel D. Gajski , Nikil D. Dutt , Allen C.-H. Wu , Steve Y.-L. Lin, High-level synthesis: introduction to chip and system design, Kluwer Academic Publishers, Norwell, MA, 1992
• 3: Tohru Furuyama, Keynote address: Challenges of digital consumer and mobile SoC's: more Moore possible?, Proceedings of the conference on Design, automation and test in Europe, p.1-1, April 16-20, 2007, Nice, France
• 4: P. Hurat, Y.-T. Wang, and N. K. Verghese. Sub-90 nanometer variability is here to stay. EDA Tech Forum, November 2005.
• 5: Cheng-Tsung Hwang, Jiahn-Hurng Lee, and Yu-Chin Hsu. A formal approach to the scheduling problem in high level synthesis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, CAD-10(4):464--475, 1991.
• 6: E. F. Girczyc, R. J. Buhr, and J. P. Knight. Applicability of a subset of ada as an algorithmic hardware description language for graph based hardware compilation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, CAD-4(2):134--142, 1985.
• 7: B. M. Prangrle, A behavioral compiler for intelligent silicon compilation, University of Illinois, Department of Computer Science, Urbana, IL, 1987
• 8: P. Paulin and J. Knight. Force-directed scheduling for the behavioral synthesis of asic's. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pages 661--679, 1989.
• 9: Heinrich Krämer , Wolfgang Rosenstiel, System synthesis using behavioural descriptions, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
• 10: C. J. Tseng and D. P. Siewiorek. Automated synthesis of data paths in digital systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, CAD-5(3):379--395, July 1986.
• 11: F. J. Kurdahi , A. C. Parker, REAL: a program for REgister ALlocation, Proceedings of the 24th ACM/IEEE conference on Design automation, p.210-215, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37920]
• 12: Eren Kursun , Ankur Srivastava , Seda Ogrenci Memik , Majid Sarrafzadeh, Early evaluation techniques for low power binding, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566450]
• 13: Chun-Gi Lyuh , Taewhan Kim, High-level synthesis for low power based on network flow method, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.3, p.364-375, June 2003 [doi>10.1109/TVLSI.2003.810796]
• 14: Xiaoyong Tang , Hai Zhou , Prith Banerjee, Leakage power optimization with dual-V_th library in high-level synthesis, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065634]
• 15: Rajarshi Mukherjee , Seda Ogrenci Memik , Gokhan Memik, Temperature-aware resource allocation and binding in high-level synthesis, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065633]
• 16: C. Visweswariah , K. Ravindran , K. Kalafala , S. G. Walker , S. Narayan, First-order incremental block-based statistical timing analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996663]
• 17: Shekhar Borkar, Designing Reliable Systems from Unreliable Components: The Challenges of Transistor Variability and Degradation, IEEE Micro, v.25 n.6, p.10-16, November 2005 [doi>10.1109/MM.2005.110]
• 18: Nam Sung Kim , Taeho Kgil , K. Bowman , V. De , T. Mudge, Total power-optimal pipelining and parallel processing under process variations in nanometer technology, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.535-540, November 06-10, 2005, San Jose, CA
• 19: Diana Marculescu , Emil Talpes, Variability and energy awareness: a microarchitecture-level perspective, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065588]
• 20: X. Liang and D. Brooks. Performance optimal micro-architecture parameters selection under the impact of process variation. In International Conference on Computer Aided Design, 2006.
• 21: W.-L. Hung , Xiaoxia Wu , Yuan Xie, Guaranteeing performance yield in high-level synthesis, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233561]
• 22: Jongyoon Jung , Taewhan Kim, Timing variation-aware high-level synthesis, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 23: K. Bernstein , D. J. Frank , A. E. Gattiker , W. Haensch , B. L. Ji , S. R. Nassif , E. J. Nowak , D. J. Pearson , N. J. Rohrer, High-performance CMOS variability in the 65-nm regime and beyond, IBM Journal of Research and Development, v.50 n.4/5, p.433-449, July 2006
• 24: C. Clark. The greatest of a finite set of random variables. Operations Research, pages 145--162, 1961.
• 25: Sachin Sapatnekar, Timing, Springer-Verlag New York, Inc., Secaucus, NJ, 2004
• 26: Catapult C synthesis. Technical report, Mentor Graphics Corporation, Products Overview,.