A comprehensive estimation technique for high-level synthesis

ABSTRACT

Abstract: We present an integrated approach aimed at predicting layout area needed to implement a behavioral description for a given performance goal. Our approach is novel because: (1) it accounts for all types of RT level components (FUs, buses, registers), (2) it is highly flexible, allowing the designer to tradeoff one type of resource with another and considers dependencies between these different types, (3) it is vertically integrated to include provably accurate physical level estimators, and hence provides realistic accounting of layout effects, and (4) it uses a timing model with finer granularity, accounting for various delays in RTL datapaths. We demonstrate our technique on a variety of HLS benchmarks and show that efficient and effective design space exploration can be accomplished using this technique.

REFERENCES

• 1: C. Ramachandran , F. J. Kurdahi , D. D. Gajski , A. C.-H. Wu , V. Chaiyakul, Accurate layout area and delay modeling for system level design, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.355-361, November 1992, Santa Clara, California, United States
• 2: N. Dutt and C. Ramachandran,"Benchmarks for the 1992 High- Level Synthesis Workshop," Tech. Report #92-107, Information & Computer Science Department, UC Irvine, 1992.
• 3: Michael C. McFarland, Using bottom-up design techniques in the synthesis of digital hardware from abstract behavioral descriptions, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.474-480, July 1986, Las Vegas, Nevada, United States
• 4: S. Y. Ohm and C. S. Jhon, "A Branch and Bound Method for the Optimal Scheduling," Proc. CICC '92, May 1992.
• 5: R. Jain, A. C. Parker, and N. Park, "Predicting System-Level Area and Delay for Pipelined and Non-pipelined Designs," IEEE Trans. CAD, vol 11. no. 8, pp. 955-965, August 1992.
• 6: Y. Hu, A. Ghouse, and B. S. Carlson, "Lower Bounds on the Iteration Time and the Number of Resources for Functional Pipelined Data Flow Graphs,"Proc. ICCD '93, pp. 21-24, 1993.
• 7: A. H. Timmer, M. J. M. Heijligers, and J. A. G. Jess, "Fast System-Level Area-Delay Curve Prediction," Proc. 1st APCHDL, pp. 198-207, 1993.
• 8: Samit Chaudhuri , Robert A. Walker, Computing lower bounds on functional units before scheduling, Proceedings of the 7th international symposium on High-level synthesis, p.36-41, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
• 9: A. Sharma and R. Jain, "Estimating Architectural Resources and Performance for High-Level Synthesis Applications," IEEE Trans. VLSI Systems, vol 1. no. 2, pp. 175-190, June 1993.
• 10: Catherine H. Gebotys , Mohamed I. Elmasry, Simultaneous scheduling and allocation for cost constrained optimal architectural synthesis, Proceedings of the 28th conference on ACM/IEEE design automation, p.2-7, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127609]
• 11: Kayhan Ktigtikgakar, "System-Level Synthesis Techniques with Emphasis on Partitioning and Design planning," PhD Thesis, EE-systems Dept., USC, Sept. 1991.
• 12: Pravil Gupta , Alice C. Parker, SMASH: a program for scheduling memory-intensive application-specific hardware, Proceedings of the 7th international symposium on High-level synthesis, p.54-59, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
• 13: Seong Y. Ohm , Fadi J. Kurdahi , Nikil Dutt, Comprehensive lower bound estimation from behavioral descriptions, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.182-187, November 06-10, 1994, San Jose, California, United States
• 14: Alok Sharma , Rajiv Jain, InSyn: integrated scheduling for DSP applications, Proceedings of the 30th international conference on Design automation, p.349-354, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164926]
• 15: J. H. Lee, Y. C. Hsu and Y. L. Lin, "A New Integer Linear Programming Formulation for the Scheduling Problem in Data Path Synthesis," Proc. ICCAD-89, pp. 20-23, November 1989.
• 16: Samit Chaudhuri , Robert A. Walker , John E. Mitchell, Analyzing and exploiting the structure of the constraints in the ILP approach to the scheduling problem, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.2 n.4, p.456-471, Dec. 1994 [doi>10.1109/92.335014]
• 17: R Jha, C. Ramachandran, N. Dutt, and F. J. Kurdahi, "An Empirical Study on the Effects of Component Styles and Shapes on High-Level Synthesis," Proc. VLSI' 94, 1994.
• 18: J. R Weng and A. C. Parker, "3D scheduling: High-Level synthesis with Floorplanning," Proc. 5th International Workshop on High-Level Synthesis, Buhlerhohe, Germany, 1991.
• 19: S. Bakshi and D. Gajski, "A Strategy for Design Space Exploration," Tech.Report #93-10, Information & Computer Science Department, UC Irvine, 1993.
• 20: S. Y. Ohm, F. J. Kurdahi, and N. Dutt, "A Unified Methodology for Estimating Resource Requirements for Early Design Space Exploration," Tech. Report # 94-11-03 ,ECE Department, UC Irvine, March 1994.
• 21: R J. Jha and N. Dutt, "The GENUS User Manual and C Programming Library," Tech. Report #93-32, Information & Computer Science Department, UC Irvine, 1994.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Systems specification methodology

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

General Terms:
Algorithms, Performance, Reliability

Keywords:
HLS benchmarks, RT level components, RTL datapaths, behavioral description, buses, data flow graphs, delays, design space exploration, estimation technique, granularity, hardware description languages, high level synthesis, high-level synthesis, layout area, registers, system buses, timing, timing model