Control flow optimization in loops using interval analysis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Control flow optimization in loops using interval analysis

Full text

Pdf (978 KB)

Source

International Conference on Compilers, Architecture and Synthesis for Embedded Systems archive
Proceedings of the 2008 international conference on Compilers, architectures and synthesis for embedded systems table of contents

Atlanta, GA, USA

SESSION: Compilers table of contents

Pages 157-166

Year of Publication: 2008

ISBN:978-1-60558-469-0

Authors

Mohammad Ali Ghodrat	University of California, Irvine, Irvine, CA, USA
Tony Givargis	University of California, Irvine, Irvine, CA, USA
Alex Nicolau	University of California, Irvine, Irvine, CA, USA

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
ACM: Association for Computing Machinery
SIGBED: ACM Special Interest Group on Embedded Systems
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 126, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1450095.1450120 What is a DOI?

ABSTRACT

We present a novel loop transformation technique, particularly well suited for optimizing embedded compilers, where an increase in compilation time is acceptable in exchange for significant performance increase. The transformation technique optimizes loops containing nested conditional blocks. Specifically, the transformation takes advantage of the fact that the Boolean value of the conditional expression, determining the true/false paths, can be statically analyzed using a novel interval analysis technique that can evaluate conditional expressions in the general polynomial form. Results from interval analysis combined with loop dependency information is used to partition the iteration space of the nested loop. In such cases, the loop nest is decomposed such as to eliminate the conditional test, thus substantially reducing the execution time. Our technique completely eliminates the conditional from the loops (unlike previous techniques) thus further facilitating the application of other optimizations and improving the overall speedup. Applying the proposed transformation technique on loop kernels taken from Mediabench, SPEC-2000, mpeg4, qsdpcm and gimp, on average we measured a 175% (1.75X) improvement of execution time when running on a SPARC processor, a 336% (4.36X) improvement of execution time when running on an Intel Core Duo processor and a 198.9% (2.98X) improvement of execution time when running on a PowerPC G5 processor.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Standard Performance Evaluation Corporation. Spec cpu2000. Available as http://www.spec.org/cpu2000/.
	2	Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
	3	Heiko Falk , Peter Marwedel, Control Flow Driven Splitting of Loop Nests at the Source Code Level, Proceedings of the conference on Design, Automation and Test in Europe, p.10410, March 03-07, 2003
	4	Mohammad Ali Ghodrat , Tony Givargis , Alex Nicolau, Equivalence checking of arithmetic expressions using fast evaluation, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA [doi>10.1145/1086297.1086317]
	5	Ilya Issenin , Nikil Dutt, Data reuse driven energy-aware MPSoC co-synthesis of memory and communication architecture for streaming applications, Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176254.1176326]
	6	Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
	7	R.E. Moore. Interval analysis. Prentice-Hall, Englewood Cliffs, N.J., 1966.
	8	Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
	9	P. Stobach. A new technique in scene adaptive coding. In Proceedings of EUSIPCO, 1988.
	10	The GCC Team. Gnu compiler collection. Available as http://gcc.gnu.org/.
	11	The GIMP Team. Gnu image manipulation program. Available as http://www.gimp.org/.
	12	Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
	13	Michael Wolfe, How compilers and tools differ for embedded systems, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, p.1-1, September 24-27, 2005, San Francisco, California, USA [doi>10.1145/1086297.1086298]
	14	www.mp3tech.org. Iso mp3 sources. Available as http://www.mp3-tech.org/programmer /sources/dist10.tgz.