Dynamic common sub-expression elimination during scheduling in high-level synthesis

ABSTRACT

We introduce a new approach, "Dynamic Common Sub-expression Elimination (CSE)", that dynamically eliminates common sub- expressions based on new opportunities created during scheduling of control-intensive designs. Classical CSE techniques fail to eliminate several common sub-expressions in control-intensive designs due to the presence of a complex mix of control and data-flow. Aggressive speculative code motions employed to schedule control-intensive designs often re-order, speculate and duplicate operations, hence changing the control flow between the operations with common sub-expressions. This leads to new opportunities for applying CSE dynamically. We have implemented dynamic CSE in a high-level synthesis framework called Spark and present results for experiments performed using various combinations of CSE and dynamic CSE. The benchmarks used consist of four functional blocks derived from two moderately complex industrial-strength applications, namely, MPEG-1 and the GIMP image processing tool. Our dynamic CSE techniques result in improvements of up to 22% in the controller size and up to 31% in performance; easily surpassing the improvements obtained by the traditional CSE approach. We also observe an unexpected (and significant) reduction in the number of registers using our approach.

REFERENCES

• 1: Luiz C. V. dos Santos , Jochen A. G. Jess, A reordering technique for efficient code motion, Proceedings of the 36th ACM/IEEE conference on Design automation, p.296-299, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309935]
• 2: Sumit Gupta , Nick Savoiu , Nikil Dutt , Rajesh Gupta , Alex Nicolau, Conditional speculation and its effects on performance and area for high-level snthesis, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500040]
• 3: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 4: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 5: Zia Iqbal , Miodrag Potkonjak , Sujit Dey , Alice Parker, Critical path minimization using retiming and algebraic speed-up, Proceedings of the 30th international conference on Design automation, p.573-577, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165046]
• 6: M. Potkonjak, M.B. Srivastava, and A. Chandrakasan. Multiple constant multiplications: Efficient and versatile framework and algorithms for exploring common subexpression elimination. IEEE Trans. on CAD, Mar 1996.
• 7: R. Pasko, P. Schaumont, V. Derudder, S. Vernalde, and D. Durackova. A new algorithm for elimination of common subexpressions. IEEE Trans. on CAD, Jan 1999.
• 8: Martin Janssen , Francky Catthoor , Hugo De Man, A specification invariant technique for operation cost minimisation in flow-graphs, Proceedings of the 7th international symposium on High-level synthesis, p.146-151, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
• 9: M.Miranda, F.Catthoor, M. Janssen, and H.De Man. High-level address optimisation and synthesis techniques for data-transfer intensive applications.
• 10: Donald A. Lobo , Barry M. Pangrle, Redundant operator creation: a scheduling optimization technique, Proceedings of the 28th conference on ACM/IEEE design automation, p.775-778, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127768]
• 11: Miodrag Potkonjak , Jan Rabaey, Maximally fast and arbitrarily fast implementation of linear computations, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.304-308, November 1992, Santa Clara, California, United States
• 12: Robert Kennedy , Sun Chan , Shin-Ming Liu , Raymond Lo , Peng Tu , Fred Chow, Partial redundancy elimination in SSA form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.3, p.627-676, May 1999 [doi>10.1145/319301.319348]
• 13: Sumit Gupta , Miguel Miranda , Francky Catthoor , Rajesh Gupta, Analysis of high-level address code transformations for programmable processors, Proceedings of the conference on Design, automation and test in Europe, p.9-13, March 27-30, 2000, Paris, France [doi>10.1145/343647.343683]
• 14: Steven Novack , Alexandru Nicolau, Mutation Scheduling: A Unified Approach to Compiling for Fine-Grain Parallelism, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.16-30, August 08-10, 1994
• 15: Vugranam C. Sreedhar , Guang R. Gao , Yong-Fong Lee, Incremental computation of dominator trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.2, p.239-252, March 1997 [doi>10.1145/244795.244799]
• 16: Vugranam C. Sreedhar , Guang R. Gao , Yong-Fong Lee, A new framework for exhaustive and incremental data flow analysis using DJ graphs, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.278-290, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 17: Sumit Gupta , Nick Savoiu , Sunwoo Kim , Nikil Dutt , Rajesh Gupta , Alex Nicolau, Speculation techniques for high level synthesis of control intensive designs, Proceedings of the 38th conference on Design automation, p.269-272, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378481]
• 18: 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]
• 19: A. Nicolau and S. Novack. Trailblazing: A hierarchical approach to percolation scheduling. In International Conference on Parallel Processing, 1993.
• 20: Spark Synthesis Benchmarks~FTP site. ftp://ftp.ics.uci.edu/pub/spark/benchmarks.
• 21: GNU Image~Manipulation Program. http://www.gimp.org.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design

General Terms:
Design, Performance

Keywords:
common sub-expression elimination, dynamic CSE, high-level synthesis, parallelizing transformations