A recursive technique for computing lower-bound performance of schedules

ABSTRACT

We present a fast recursive technique for estimating lower-bound performance of data path schedules. The method relies on the determination of an ASAPUC a(s Soon As Possible Under Constraint) time-step value for each node of the DFG (Data-Flow Graph) that is based on the ASAPUC values of its predecessor nodes. That is, the lower-bound estimation is applied to each subgraph permitting the derivation of a tight lower bound on the performance of the complete DFG. Applying the greedy lower-bound estimator of Rim and Jain [1994] to each subgraph improves the complete lower bound in more than 50% of the experiments reported in Rim and Jain [1994], and the CPU time is only about twice as long. The recursive methodology can be extended to exploit other lower-bound techniques, for example, considering other constraints such as the number of busses or registers.

REFERENCES

• 1: BENNOUR, I. AND ABOULHAMID, E. M. 1997. Lower-bounds on the iteration and initiation interval of functional pipelining and loop folding. Des. Autom. Embedded Syst. (to appear).
• 2: Raul Camposano , Jörg Wilberg, Embedded system design, Design Automation for Embedded Systems, v.1 n.1-2, p.5-50, Jan. 1996 [doi>10.1007/BF00134682]
• 3: DEWILDE, P., DEPRETTERE, E., AND NOUTA, R. 1985. Parallel and pipelined VLSI implementation of signal processing algorithms. In VLSI and Modern Signal Processing, S. Y. Kung, H. J. Whitehouse, T. Kailath, Eds., Prentice-Hall, Englewood Cliffs, NJ.
• 4: Daniel D. Gajski , Frank Vahid , Sanjiv Narayan , Jie Gong, Specification and design of embedded systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 5: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 6: 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]
• 7: HWANG, C.-T., LEE, J.-H., AND HSU, Y.-C. 1991. A formal approach to the scheduling problem in high level synthesis. IEEE Trans. CAD 10, 464-475.
• 8: Kai Hwang , Faye A. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill, Inc., New York, NY, 1990
• 9: R. Jain , K. Kücükcakar , M. J. Mlinar , A. C. Parker, Experience with ADAM synthesis system, Proceedings of the 26th ACM/IEEE conference on Design automation, p.56-61, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74393]
• 10: LANGEVIN, M., CERNY, E., WILBERG, J., AND VIERHAUS, H.-T. 1995. Local microcode generation in system design. In Code Generation for Embedded Processors, P. Marwedel and G. Goossens, Eds., Kluwer Academic, Boston, MA, Ch. 10, 171-187.
• 11: Michael C. McFarland , Alice C. Parker , Raul Camposano, Tutorial on high-level synthesis, Proceedings of the 25th ACM/IEEE conference on Design automation, p.330-336, June 12-15, 1988, Atlantic City, New Jersey, United States
• 12: PAPACHRISTOU, C. A. AND KONUK, H. 1989. A high-level synthesis technique based on linear programming. Tech. Rep., Computer Engineering and Science Dept., Case Western Reserve Univ., Nov.
• 13: PARK, N. AND PARKER, A.C. 1988. Sehwa: A software package for synthesis of pipelines from behavioral specifications. IEEE Trans. CAD 7, 356-370.
• 14: PAULIN, P. G. AND KNIGHT, J.P. 1989. Force-directed scheduling for the behavioral synthesis of ASIC's. IEEE Trans. CAD 8, 661-679.
• 15: RABAEY, g. M. AND POTKONJAK, M. 1994. Estimating implementation bounds for real time DSP application specific circuits. IEEE Trans. CAD 13, 669-683.
• 16: RIM, M. AND JAIN, R. 1994. Lower-bound performance estimation for high-level synthesis scheduling problem. IEEE Trans. CAD 13, 451-458.
• 17: SHARMA, A. AND JAIN, R. 1993. Estimating architectural resources and performance for high-level synthesis applications. IEEE Trans. VLSI Syst. 1.
• 18: Adwin H. Timmer , Jochen A. G. Jess, Execution interval analysis under resource constraints, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.454-459, November 07-11, 1993, Santa Clara, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Automatic synthesis

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Optimization

Keywords:
dataflow graph, lower-bound on performance, microcode optimization, resource constraints, scheduling