A path-based technique for estimating hardware runtime in HW/SW-cosynthesis

ABSTRACT

Abstract: One of the key issues in hardware/software-cosynthesis is precise estimation. The usual local estimation techniques are inadequate for globally optimising compilers and synthesis tools. We present a path based estimation technique which allows a computation time/quality tradeoff. The results show acceptable computation times while revealing much more potential parallelism than local list scheduling.

REFERENCES

• BaRoXi94: Xun Xiong , Edna Barros , Wolfgang Rosenstiel, A method for partitioning UNITY language in hardware and software, Proceedings of the conference on European design automation, p.220-225, September 19-23, 1994, Grenoble, France
• Cam91: R. Camposano, Path-Based Scheduling for Synthesis, IEEE Transactions on Computer-Aided Design, Vol. 10, No.l, pp. 85-93, Jan. 1991.
• ErHeBe93: Rolf Ernst , Jorg Henkel , Thomas Benner, Hardware-Software Cosynthesis for Microcontrollers, IEEE Design & Test, v.10 n.4, p.64-75, October 1993 [doi>10.1109/54.245964]
• GuMi92: R.K. Gupta and G.D. Micheli, System-level Synthesis using Re-programmable Components, Proc. of EDAC'92, IEEE Comp. Soc. Press, pp. 2-7, 1992.
• HeErHo+94: Jörg Henkel , Rolf Ernst , Ullrich Holtmann , Thomas Benner, Adaptation of partitioning and high-level synthesis in hardware/software co-synthesis, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.96-100, November 06-10, 1994, San Jose, California, United States
• HeHeEr94: D. Herrmann , J. Henkel , R. Ernst, An approach to the adaptation of estimated cost parameters in the COSYMA system, Proceedings of the 3rd international workshop on Hardware/software co-design, September 22-24, 1994, Grenoble, France
• JaElOb+94: Axel Jantsch , Peeter Ellervee , Ahmed Hemani , Johnny Öberg , Hannu Tenhunen, Hardware/software partitioning and minimizing memory interface traffic, Proceedings of the conference on European design automation, p.226-231, September 19-23, 1994, Grenoble, France
• KaLe94: Asawaree Kalavade , Edward A. Lee, A global criticality/local phase driven algorithm for the constrained hardware/software partitioning problem, Proceedings of the 3rd international workshop on Hardware/software co-design, September 22-24, 1994, Grenoble, France
• Keu94: Kurt Keutzer, Hardware-software co-design and ESDA, Proceedings of the 31st annual conference on Design automation, p.435-436, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196454]
• ObRaJe93: K. O'Brien, M. Rahmouni, A. Jerraya, DLS: A Scheduling Algorithm For High-Level Synthesis in VHDL, Proc. of EDAC'93, pp. 393-397, 1993.
• OG89: R. H. J. M. Otten , L. P. P. P. van Ginneken, The annealing algorithm, Kluwer, B.V., Deventer, The Netherlands, 1989
• PeKu93: Z. Peng, K. Kuchcinski, An Algorithm for Partitioning of Application Specific System, Proc. of The European Conference on Design Automation 1993, pp. 316-321, 1993.
• TsSi86: C.J. Tseng, D.P. Siewiorek, Automated Synthesis of Data Paths in Digital Systems, IEEE Trans. on CAD, Vol. 5, No. 3, pp. 379-395, 1986.
• VaGaGo94: Frank Vahid , Daniel D. Gajski , Jie Gong, A binary-constraint search algorithm for minimizing hardware during hardware/software partitioning, Proceedings of the conference on European design automation, p.214-219, September 19-23, 1994, Grenoble, France

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Experimentation, Performance

Keywords:
circuit CAD, computation time, computational complexity, computer architecture, hardware runtime, hardware software cosynthesis, local estimation techniques, local list scheduling, optimising compilers, path-based technique, quality, scheduling, synthesis tools, systems analysis