Coordinated parallelizing compiler optimizations and high-level synthesis

ABSTRACT

We present a high-level synthesis methodology that applies a coordinated set of coarse-grain and fine-grain parallelizing transformations. The transformations are applied both during a pre-synthesis phase and during scheduling, with the objective of optimizing the results of synthesis and reducing the impact of control flow constructs on the quality of results. We first apply a set of source level presynthesis transformations that include common sub-expression elimination (CSE), copy propagation, dead code elimination and loop-invariant code motion, along with more coarse-level code restructuring transformations such as loop unrolling. We then explore scheduling techniques that use a set of aggressive speculative code motions to maximally parallelize the design by re-ordering, speculating and sometimes even duplicating operations in the design. In particular, we present a new technique called "Dynamic CSE" that dynamically coordinates CSE and code motions such as speculation and conditional speculation during scheduling. We implemented our parallelizing high-level synthesis in the <i>SPARK</i> framework. This framework takes a behavioral description in ANSI-C as input and generates synthesizable register-transfer level VHDL. Our results from computationally expensive portions of three moderately complex design targets, namely, MPEG-1, MPEG-2 and the GIMP image processing tool, validate the utility of our approach to the behavioral synthesis of designs with complex control flows.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler transformations for high-performance computing, ACM Computing Surveys (CSUR), v.26 n.4, p.345-420, Dec. 1994 [doi>10.1145/197405.197406]
• 3: Reinaldo A. Bergamaschi, Behavioral network graph: unifying the domains of high-level and logic synthesis, Proceedings of the 36th ACM/IEEE conference on Design automation, p.213-218, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309916]
• 4: Brayton, R., Camposano, R., Micheli, G. D., Otten, R., and van Eijndhoven, J. 1988. The Yorktown Silicon Compiler System. Addison-Wesley, Chapter in Silicon Compilation.
• 5: Raul Camposano , Wayne H. Wolf, High-Level VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1991
• 6: Celoxica. Celoxica incorporated. DK Design Suite.
• 7: Chaiyakul, V., Gajski, D., and Ramachandran, L. 1992. Minimizing syntactic variance with assignment decision diagrams. Tech. Rep. ICS-TR-92-34, Department of Information and Computer Science, Univ. of California, Irvine.
• 8: Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill Higher Education, 1994
• 9: dos Santos, L. 1998. Exploiting instruction-level parallelism: a constructive approach. Ph.D. thesis, Electrical Engineering department, Eindhoven University of Technology.
• 10: 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]
• 11: Fisher, J. 1981. Trace scheduling: A technique for global microcode compaction. IEEE Trans. Comput. 30, 478--490.
• 12: Forte. Forte Design Systems. Behavioral Design Suite.
• 13: Daniel D. Gajski , Nikil D. Dutt , Allen C.-H. Wu , Steve Y.-L. Lin, High-level synthesis: introduction to chip and system design, Kluwer Academic Publishers, Norwell, MA, 1992
• 14: Get2Chip. Get2Chip Incorporated (acquired by Cadence). G2C Architectural Compiler.
• 15: Gimp website. GNU Image Manipulation Program. http://www.gimp.org.
• 16: M. Girkar , C. D. Polychronopoulos, Automatic Extraction of Functional Parallelism from Ordinary Programs, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.166-178, March 1992 [doi>10.1109/71.127258]
• 17: Sumit Gupta , Nikil Dutt , Rajesh Gupta , Alex Nicolau, SPARK: A High-Lev l Synthesis Framework For Applying Parallelizing Compiler Transformations, Proceedings of the 16th International Conference on VLSI Design, p.461, January 04-08, 2003
• 18: Gupta, S., Gupta, R., Dutt, N., and Nicolau, A. 2004. SPARK: A Parallelizing Approach to the High-Level Synthesis of Digital Circuits. Kluwer Academic.
• 19: Sumit Gupta , Nick Savoiu , Nikil Dutt , Rajesh Gupta , Alex Nicolau , Timothy Kam , Michael Kishinevsky , Shai Rotem, Coordinated transformations for high-level synthesis of high performance microprocessor blocks, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514140]
• 20: 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]
• 21: Sumit Gupta , Mehrdad Reshadi , Nick Savoiu , Nikil Dutt , Rajesh Gupta , Alex Nicolau, Dynamic common sub-expression elimination during scheduling in high-level synthesis, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan [doi>10.1145/581199.581256]
• 22: 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]
• 23: Gupta, S., Savoiu, N., Dutt, N., Gupta, R., and Nicolau, A. 2003b. Using global code motions to improve the quality of results for high-level synthesis. IEEE Trans. CAD 23, 2 (Feb.).
• 24: 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]
• 25: Steven Paul Haynal , Forrest D. Brewer, Automata-based symbolic scheduling, 2000
• 26: 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]
• 27: 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
• 28: 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]
• 29: Kountouris, A. and Wolinski, C. 1999. High level pre-synthesis optimization steps using hierarchical conditional dependency graphs. In Proceedings of the Euromicro Confernce. 1290--1294.
• 30: David Ku , Gionvanni De Micheli, Relative scheduling under timing constraints, Proceedings of the 27th ACM/IEEE conference on Design automation, p.59-64, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123227]
• 31: Lakshminarayana, G., Raghunathan, A., and Jha, N. 1999. Wavesched: A novel scheduling technique for control-flow intensive designs. IEEE Trans. CAD, 18, 505--523.
• 32: Jian Li , Rajesh K. Gupta, Decomposition of timed decision tables and its use in presynthesis optimizations, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.22-27, November 09-13, 1997, San Jose, California, United States
• 33: 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]
• 34: McFarland, M. C. 1978. The Value Trace: A database for automated digital design. Technical Report DRC-01-4-80, Carnegie-Mellon University, Design Research Center.
• 35: MediaBench. UCLA Mediabench benchmark suite. http://cares.icsl.ucla.edu/MediaBench/.
• 36: Miguel A. Miranda , Francky V. M. Catthoor , Martin Janssen , Hugo J. De Man, High-level address optimization and synthesis techniques for data-transfer-intensive applications, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.6 n.4, p.677-686, Dec. 1998 [doi>10.1109/92.736141]
• 37: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 38: Nicolau, A. 1985. A development environment for scientific parallel programs. Tech. Rep. TR 86-722, Department of Computer Science, Cornell University.
• 39: Nicolau, A. and Novack, S. 1993. Trailblazing: A hierarchical approach to Percolation Scheduling. In Proceedings of the International Conference on Parallel Processing. 87--96.
• 40: 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
• 41: Steven Novack , Alexandru Nicolau, An Efficient Global Resource-Directed Approach to Exploiting Instruction-Level Parallelism, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.87, October 20-23, 1996
• 42: Alex Orailoglu , Daniel D. Gajski, Flow graph representation, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.503-509, July 1986, Las Vegas, Nevada, United States
• 43: Park, S. and Choi, K. 2001. Performance-driven high-level synthesis with bit-level chaining and clock selection. IEEE Trans. CAD, 20, 2 (Feb.), 1999-212.
• 44: Pasko, R., Schaumont, P., Derudder, V., Vernalde, S., and Durackova, D. 1999. A new algorithm for elimination of common subexpressions. IEEE Trans. CAD, 18, 1 (Jan), 58--68.
• 45: Armita Peymandoust , Giovanni De Micheli, Symbolic algebra and timing driven data-flow synthesis, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 46: Potkonjak, M. and Rabaey, J. 1994. Optimizing resource utlization using tranformations. IEEE Trans. CAD, 13, 277--293.
• 47: Potkonjak, M., Srivastava, M., and Chandrakasan, A. 1996. Multiple constant multiplications: Efficient and versatile framework and algorithms for exploring common subexpression elimination. IEEE Trans. CAD, 15, 2 (Mar), 141--150.
• 48: Radivojevic, I. and Brewer, F. 1996. A new symbolic technique for control-dependent scheduling. IEEE Trans. CAD, 15, 45--57.
• 49: 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]
• 50: SPARK WEBSITE. SPARK parallelizing high-level synthesis framework website. http://mesl.ucsd.edu/spark.
• 51: 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
• 52: 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]
• 53: Kazutoshi Wakabayashi, C-based synthesis experiences with a behavior synthesizer, “cyber”, Proceedings of the conference on Design, automation and test in Europe, p.83-es, January 1999, Munich, Germany [doi>10.1145/307418.307530]
• 54: 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
• 55: Walker, R. and Thomas, D. 1989. Behavioral transformation for algorithmic level IC design. IEEE Trans. CAD, 8, 1115--1128.

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
Code motions, common subexpression elimination, dynamic CSE, embedded systems, high-level synthesis, parallelizing transformations, presynthesis