A code-motion pruning technique for global scheduling

ABSTRACT

In the high-level synthesis of ASICs or in the code generation for ASIPs, the presence of conditionals in the behavioral description represents an obstacle to exploit parallelism. Most existing methods use greedy choices in such a way that the search space is limited by the applied heuristics. For example, they might miss opportunities to optimize across basic block boundaries when treating conditional execution. We propose a constructive method which allows generalized code motions. Scheduling and code motion are encoded in the form of a unified resource-constrained optimization problem. In our approach many alternative solutions are constructed and explored by a search algorithm, while optimal solutions are kept in the search space. Our method can cope with issues like speculative execution and code such duplication. Moreover, it can tackle constraints imposed by the advance choice of a controller, such as pipelined-control delay and limited branch capabilities. The underlying timing models support chaining and multicycling. As tasking code motion into account may lead to a larger search space, a code-motion pruning technique is presented. This pruning is proven to keep optimal solutions in the search space for cost functions in terms of schedule lengths.

REFERENCES

• 1: AMELLAL,S.AND KAMINSKA, B. 1994. Functional synthesis of digital systems with tass. IEEE Trans. Comput.-Aided Des. 13, 5 (May 1994), 537-552.
• 2: Reinaldo A. Bergamaschi , Salil Raje , Louise Trevillyan, Control-flow versus data-flow-based scheduling: combining both approaches in an adaptive scheduling system, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.1, p.82-100, March 1997 [doi>10.1109/92.555989]
• 3: Reinaldo A. Bergamaschi , Raul Camposano , Michael Payer, Area and performance optimizations in path-based scheduling, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
• 4: Michel Berkelaar , Lukas P. P. P. van Ginneken, Efficient orthonormality testing for synthesis with pass-transistor selectors, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.256-263, November 05-09, 1995, San Jose, California, United States
• 5: CAMPOSANO, R. 1991. Path-based scheduling for synthesis. IEEE Trans. Comput.-Aided Des. 10, 1 (Jan. 1991), 85-93.
• 6: 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]
• 7: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 8: Luiz C. V. dos Santos , M. J. M. Heijligers , C. A. J. Van Eijk , J. T. J. Van Eijndhoven , J. A. G. Jess, A Constructive Method for Exploiting Code Motion, Proceedings of the 9th international symposium on System synthesis, p.51, November 06-08, 1996
• 9: Kemal Ebcioglu , Alexandru Nicolau, A global resource-constrained parallelization technique, Proceedings of the 3rd international conference on Supercomputing, p.154-163, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318807]
• 10: FISHER, J. 1981. Trace scheduling: A technique for global microcode compaction. IEEE Trans. Comput. C-30, 7 (July), 478-490.
• 11: Rajiv Gupta , Mary Lou Soffa, Region Scheduling: An Approach for Detecting and Redistributing Parallelism, IEEE Transactions on Software Engineering, v.16 n.4, p.421-431, April 1990 [doi>10.1109/32.54294]
• 12: HEIJLIGERS, M. 1996. The Application of Genetic Algorithms to High-Level Synthesis. Ph.D. Dissertation. Department of Mathematics and Computing Science, Eindhoven University of Technology, Eindhoven, Netherlands.
• 13: HEIJLIGERS, M. 1994. Neat: an object oriented high level synthesis interface. In Proceedings of the IEEE International Symposium on Circuits and Systems 1233-1236.
• 14: Jörg Henkel , Rolf Ernst, A path-based technique for estimating hardware runtime in HW/SW-cosynthesis, Proceedings of the 8th international symposium on System synthesis, p.116-121, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224527]
• 15: 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]
• 16: KIFLI, A. 1996. Global Scheduling in High-Level Synthesis and Code Generation for Embedded Processors. Ph.D. Dissertation. Department of Electrical Engineering, Katho-lieke Universiteit Leuven, Leuven, Belgium.
• 17: A. Kifli , G. Goosens , H. De Man, A unified scheduling model for high-level synthesis and code generation, Proceedings of the 1995 European conference on Design and Test, p.234, March 06-09, 1995
• 18: KIM, T. 1994. A scheduling algorithm for conditional resource sharing: A hierarchical reduction approach. IEEE Trans. Comput.-Aided Des. 13, 4 (Apr. 1994), 425-438.
• 19: Monica S. Lam , Robert P. Wilson, Limits of control flow on parallelism, Proceedings of the 19th annual international symposium on Computer architecture, p.46-57, May 19-21, 1992, Queensland, Australia
• 20: Rainer Leupers , Peter Marwedel, Time-constrained code compaction for DSPs, Proceedings of the 8th international symposium on System synthesis, p.54-59, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224498]
• 21: Soo-Mook Moon , Kemal Ebcioğlu, An efficient resource-constrained global scheduling technique for superscalar and VLIW processors, Proceedings of the 25th annual international symposium on Microarchitecture, p.55-71, December 01-04, 1992, Portland, Oregon, United States
• 22: T. Nakatani , K. Ebcioglu, Making Compaction-Based Parallelization Affordable, IEEE Transactions on Parallel and Distributed Systems, v.4 n.9, p.1014-1029, September 1993 [doi>10.1109/71.243528]
• 23: NICOLAU, A. 1985. Uniform parallelism exploitation in ordinary programs. In Proceedings of the International Conference on Parallel Processing 614-618.
• 24: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 25: Roni Potasman , Joseph Lis , Alexandru Nicolau , Daniel Gajski, Percolation based synthesis, Proceedings of the 27th ACM/IEEE conference on Design automation, p.444-449, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123333]
• 26: RADIVOJEVIC,I.P.AND BREWER, F. 1996. A new symbolic technique for control-dependent scheduling. IEEE Trans. CAD 15, 1 (Jan.), 45-57.
• 27: Minjoong Rim , Yaw Fann , Rajiv Jain, Global scheduling with code-motions for high-level synthesis applications, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.3, p.379-392, Sept. 1995 [doi>10.1109/92.406996]
• 28: M. Rim , R. Jain, Representing conditional branches for high-level synthesis applications, Proceedings of the 29th ACM/IEEE conference on Design automation, p.106-111, June 08-12, 1992, Anaheim, California, United States
• 29: Michael D. Smith , Mark Horowitz , Monica S. Lam, Efficient superscalar performance through boosting, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.248-259, October 12-15, 1992, Boston, Massachusetts, United States
• 30: VAN EIJNDHOVEN,J.AND STOK, L. 1992. A data flow exchange standard. In Proceedings of the Conference on Design Automation (EURO-DAC '92, Congress Centrum Hamburg, Hamburg, Germany, Sept. 7-10, 1992), G. Musgrave, Ed. IEEE Computer Society Press, Los Alamitos, CA, 193-199.
• 31: 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, Nov.) 62-65.
• 32: 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:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Control design
      B.5.2 Design Aids
          Subjects: Optimization; Automatic synthesis

General Terms:
Algorithms, Design

Keywords:
code generation, code motion, global scheduling, high-level synthesis, speculative execution