Estimation of lower bounds in scheduling algorithms for high-level synthesis

ABSTRACT

To produce efficient design, a high-level synthesis system should be able to analyze a variety of cost-performance tradeoffs. The system can use lower-bound performance estimated methods to identify and puune inferior designs without producint complete designs. We present a lower-bound performance estimate method that is not only faster than existing methods, but also produces better lower bounds. In most cases, the lower bound produced by our algorithm is tight.Scheduling algorithms such as branch-and-bound need fast and effective lower-bound estimate methods, often for a large number of partially scheduled dataflow graphs, to reduce the search space. We extend our method to efficiently estimate completion time of partial schedules. This problem is not addressed by existing methods in the literature. Our lower-bound estimate is shown to by very effective in reducing the size of the search space when used in a branch-and-bound scheduling algorithm.Our methods can handle multicycle operations, pipelined functional units, and chaining of operations. We also present an extension to handle conditional branches. A salient feature of the extended method is its applicability to speculative execution as well as C-select implementation of conditional branches.

REFERENCES

• 1: CHUNG, M. J. AND TIRUVURI, G. 1995. Optimum dynamic programming scheduling under resource constraints. MSUCPS-TR95-44.
• 2: Mehmet Emin Dalkiliç , Vijay Pitchumani, A Multi-Schedule Approach to High-Level Synthesis, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.572-575, October 10-12, 1994
• 3: DAVIDSON, S., LANDSKOV, D., SHRIVER, B. D., AND MALLET, P.W. 1981. Some experiments in local microcode compaction for horizontal machines. IEEE Trans. Comput. C-30, 7 (July), 460-477.
• 4: Yaw Fann , Minjoong Rim , Rajiv Jain, Global scheduling for high-level synthesis applications, Proceedings of the 31st annual conference on Design automation, p.542-546, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196529]
• 5: FERNANDEZ, E. B. AND BUSSELL, B. 1973. Bounds on the number of processors and time for multiprocessor optimal schedules. IEEE Trans. Comput. C-22, 8 (Aug.), 745-751.
• 6: Hu, Y., GHOUSE, A., AND CARLSON, B. S. 1993. Lower bounds on the iteration time and the number of resources for functional pipelined data flow graphs. In Proceedings of the International Conference on Computer Design. 21-24.
• 7: S. H. Huang , Y. L. Jeang , C. T. Hwang , Y. C. Hsu , J. F. Wang, A tree-based scheduling algorithm for control-dominated circuits, Proceedings of the 30th international conference on Design automation, p.578-582, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165051]
• 8: 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]
• 9: JAIN, R., PARKER, A. C., AND PARK, N. 1992. Predicting system-level area and delay for pipelined and non-pipelined designs. IEEE Trans. Comput.-Aided Des. 12, 8 (Aug.).
• 10: KIM, T., LIU, J., AND LIU, C. 1991. A scheduling algorithm for conditional resource sharing. In Proceedings of the IEEE International Conference on Computer-Aided Design (ICCAD '91, Santa Clara, CA, Nov. 11-14). IEEE Computer Society Press, Los Alamitos, CA, 84-87.
• 11: LANGERIN, M. AND CERNY, E. 1993. A recursive technique for computing lower-bound performance of schedules. In Proceedings of the International Conference on Computer Design. 16-20.
• 12: David J. Mallon , Peter B. Denyer, A new approach to pipeline optimisation, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
• 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: OHM, S.Y. 1995. Personal Communication.
• 15: PANGRLE, B. M. AND GAJSKI, D. D. 1987. Slicer: A state synthesizer for intelligent silicon compiler. In Proceedings of the International Conference on Computer Design. 42-45.
• 16: PAPACHRISTOU, C. A. AND KONUK, H. 1989. A high level synthesis technique based on linear programming. Tech. Rep. CES-89-21. Case Western Reserve University, Cleveland, OH.
• 17: Alice C. Parker , Jorge T. Pizarro , Mitch Mlinar, MAHA: a program for datapath synthesis, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.461-466, July 1986, Las Vegas, Nevada, United States
• 18: PARK, N. AND PARKER, A. C. 1988. SEHWA: A software package for synthesis of pipelines from behavioral specifications. IEEE Trans. Comput.-Aided Des. Integr. Circuits 7, 3 (Mar.), 356 -368.
• 19: PAULIN, P. G. AND KNIGHT, J. P. 1989. Force-directed scheduling for the beavioral synthesis of ASICs. IEEE Trans. CAD 8, 6 (June), 661-679.
• 20: RABAEY, J. M. AND POTKONJAK, M. 1994. Estimating implementation bounds for real time DSP application specific circuits. IEEE Trans. CAD 13, 6 (June), 669-683.
• 21: RADIVOJEVIC, I. P. AND BREWER, F. 1996. A new symbolic technique for control-dependent scheduling. IEEE Trans. CAD (Jan.).
• 22: RIM, M. AND JAIN, R. 1994. Lower-bound performance estimation for the high-level synthesis scheduling problem. IEEE Trans. CAD 13, 4 (Apr.), 451-458.
• 23: Alok Sharma , Rajiv Jain, Estimation and design algorithms for the behavioral synthesis of asics, 1992
• 24: SHARMA, A. AND JAIN, R. 1993. Estimating architectural resources and performance for high-level synthesis applications. IEEE Trans. Very Large Scale Integr. Syst. 1, 2 (June).
• 25: Robert Sedgewick, Algorithms in C, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 26: WAKABAYASHI, K. AND YOSHIMURA, T. 1989. A resource sharing and control synthesis method for conditional branches. In Proceedings of the International Conference on Computer-Aided Design (ICCAD). 62-65.
• 27: K. Wakabayashi , H. Tanaka, Global scheduling independent of control dependencies based on condition vectors, Proceedings of the 29th ACM/IEEE conference on Design automation, p.112-115, June 08-12, 1992, Anaheim, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
  B.7 INTEGRATED CIRCUITS

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance

Keywords:
dynamic programming, high-level synthesis, lower-bound estimated, scheduling