WCET-driven, code-size critical procedure cloning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

WCET-driven, code-size critical procedure cloning

Full text

Pdf (423 KB)

Source

ACM International Conference Proceeding Series; Vol. 296 archive
Proceedings of the 11th international workshop on Software & compilers for embedded systems table of contents

Munich, Germany

SESSION: Optimization and code generation for embedded processors table of contents

Pages 21-30

Year of Publication: 2008

Authors

Paul Lokuciejewski	Dortmund University of Technology, Dortmund, Germany
Heiko Falk	Dortmund University of Technology, Dortmund, Germany
Peter Marwedel	Dortmund University of Technology, Dortmund, Germany
Henrik Theiling	AbsInt Angewandte Informatik GmbH, Saarbrücken

Sponsors

: Artist2 European NoE
EDAA : European Design and Automation Association
SIGBED: ACM Special Interest Group on Embedded Systems

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 27, 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

ABSTRACT

In the domain of the worst-case execution time (WCET) analysis, loops are an inherent source of unpredictability and loss of precision since the determination of tight and safe information on the number of loop iterations is a difficult task. In particular, data-dependent loops whose iteration counts depend on function parameters can not be precisely handled by a timing analysis. Procedure Cloning can be exploited to make these loops explicit within the source code allowing a highly precise WCET analysis.

In this paper we extend the standard Procedure Cloning optimization by WCET-aware concepts with the objective to improve the tightness of the WCET estimation. Our novel approach is driven by WCET information which successively eliminates code structures leading to overestimated timing results, thus making the code more suitable for the analysis. In addition, the code size increase during the optimization is monitored and large increases are avoided.

The effectiveness of our optimization is shown by tests on real-world benchmarks. After performing our optimization, the estimated WCET is reduced by up to 64.2% while the employed code transformations yield an additional code size increase of 22.6% on average. In contrast, the average-case performance being the original objective of Procedure Cloning showed a slight decrease.

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	AbsInt Angewandte Informatik GmbH. CRL Version 2. http://www.absint.com/artist2/doc/crl2, 2007.
	2	AbsInt Angewandte Informatik GmbH. Worst-Case Execution Time Analyzer aiT for TriCore. 2007.
	3	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]
	4	K. D. Cooper, M. W. Hall, and K. Kennedy. A Methodology for Procedure Cloning. Computer Languages, 19(2):105--117, 1993.
	5	H. Falk , P. Lokuciejewski , H. Theiling, Design of a WCET-Aware C Compiler, Proceedings of the 2006 IEEE/ACM/IFIP Workshop on Embedded Systems for Real Time Multimedia, p.121-126, October 26-27, 2006 [doi>10.1109/ESTMED.2006.321284]
	6	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
	7	H. Falk , M. Schwarzer, Loop Nest Splitting for WCET-Optimization and Predictability Improvement, Proceedings of the 2006 IEEE/ACM/IFIP Workshop on Embedded Systems for Real Time Multimedia, p.115-120, October 26-27, 2006 [doi>10.1109/ESTMED.2006.321283]
	8	Jan Gustafsson , Andreas Ermedahl , Christer Sandberg , Bjorn Lisper, Automatic Derivation of Loop Bounds and Infeasible Paths for WCET Analysis Using Abstract Execution, Proceedings of the 27th IEEE International Real-Time Systems Symposium, p.57-66, December 05-08, 2006 [doi>10.1109/RTSS.2006.12]
	9	M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
	10	Informatik Centrum Dortmund. ICD-C Compiler framework. http://www.icd.de/es/icd-c, 2007.
	11	ICD Low Level Intermediate Representation backend infrastructure (LLIR) -- Developer Manual. Informatik Centrum Dortmund, 2007.
	12	S. Lee, J. Lee, C. Y. Park, and S. L. Min. A Flexible Tradeoff between Code Size and WCET using a Dual Instruction Set Processor. In SCOPES '04: Proceedings of the 8th International Workshop on Software and Compilers for Embedded Systems, pages 244--258, Amsterdam, 2004.
	13	P. Lokuciejewski. A WCET-Aware Compiler. Design, Concepts and Realization. Vdm Verlag Dr. Müller, 2007.
	14	Paul Lokuciejewski , Heiko Falk , Martin Schwarzer , Peter Marwedel , Henrik Theiling, Influence of procedure cloning on WCET prediction, Proceedings of the 5th IEEE/ACM international conference on Hardware/software codesign and system synthesis, September 30-October 03, 2007, Salzburg, Austria [doi>10.1145/1289816.1289852]
	15	Gokhan Memik , William H. Mangione-Smith , Wendong Hu, NetBench: a benchmarking suite for network processors, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	16	Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
	17	Alan D Samples , Paul N. Hilfinger, Code Reorginazation for Instruction Caches, University of California at Berkeley, Berkeley, CA, 1988
	18	D. Schulte. Modeling and transformation of flow facts within a wcet optimizing compiler (in german). Master's thesis, Technical University of Dortmund, Dortmund, Germany, May 2007.
	19	S. Thesing. Safe and Precise WCET Determinations by Abstract Interpretation of Pipeline Models. PhD thesis, Saarland University, 2004.
	20	Hiroyuki Tomiyama , Hiroto Yasuura, Code placement techniques for cache miss rate reduction, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.4, p.410-429, Oct. 1997 [doi>10.1145/268424.268469]
	21	Tuning the WCET of Embedded Applications, Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium, p.472, May 25-28, 2004
	22	Wankang Zhao , David Whalley , Christopher Healy , Frank Mueller, Improving WCET by applying a WC code-positioning optimization, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.4, p.335-365, December 2005 [doi>10.1145/1113841.1113842]