article

Open access

Improving WCET by applying a WC code-positioning optimization

Authors:

Christopher Healy,

Frank MuellerAuthors Info & Claims

ACM Transactions on Architecture and Code Optimization (TACO), Volume 2, Issue 4

Pages 335 - 365

https://doi.org/10.1145/1113841.1113842

Published: 01 December 2005 Publication History

Abstract

Applications in embedded systems often need to meet specified timing constraints. It is advantageous to not only calculate the worst-case execution time (WCET) of an application, but to also perform transformation, which reduce the WCET, since an application with a lower WCET will be less likely to violate its timing constraints. Some processors incur a pipeline delay whenever an instruction transfers control to a target that is not the next sequential instruction. Code-positioning optimizations attempt to reduce these delays by positioning the basic blocks to minimize the number of unconditional jumps and taken conditional branches that occur. Traditional code-positioning algorithms use profile data to find the frequently executed edges between basic blocks, then minimize the transfers of control along these edges to reduce the average case execution time (ACET). This paper introduces a WCET code-positioning optimization, driven by the worst-case (WC) path information from a timing analyzer, to reduce the WCET instead of ACET. This WCET optimization changes the layout of the code in memory to reduce the branch penalties along the WC paths. Unlike the frequency of edges in traditional profile-driven code positioning, the WC path may change after code-positioning decisions are made. Thus, WCET code positioning is inherently more challenging than ACET code positioning. The experimental results show that this optimization typically finds the optimal layout of the basic blocks with the minimal WCET. The results show over a 7% reduction in WCET is achieved after code positioning is performed.

References

[1]

Arnold, R., Mueller, F., and Whalley, D. 1994. Bounding worst-case instruction cache performance. In Proceedings of the Fifteenth IEEE Real-time Systems Symposium, San Juan. IEEE Computer Society Press. 172--181.

[2]

Benitez, M. 1994. Retargetable register allocation. Ph.D. thesis, University of Virginia, Char-lottesville, VA.

[3]

Benitez, M. E. and Davidson, J. W. 1988. A portable global optimizer and linker. In Proceedings of the SIGPLAN'88 conference on Programming Language design and Implementation, Atlanta, GA. ACM Press, New York. 329--338.

[4]

Benitez, M. E. and Davidson, J. W. 1994. The advantages of machine-dependent global optimization. In Proceedings of the 1994 International Conference on Programming Languages and Architectures, 105--124.

[5]

Calder, B. and Grunwald, D. 1994. Reducing branch costs via branch alignment. In Proceeding of ASPLOS'94, San Jose, CA. ACM Press, New York. 242--251.

[6]

Engblom, J. and Ermedahl, A. 2000. Modeling complex flows for worst-case execution time analysis. In Proceedings of the 21st IEEE Real-time System Symposium, Orlando, FL. IEEE Computer Society Press, 875--889.

[7]

Eyre, J. and Bier, J. 1998. Dsp processors hit the mainsteam. IEEE Computer 31, 8 (Aug.), 51--59.

Digital Library

[8]

Harmon, M., Baker, T., and Whalley, D. 1994. A retargetable technique for prediction execution time of code segments. Real-Time Systems. 159--182.

[9]

Healy, C. and Whalley, D. 1999. Tighter timing predictions by automatic detection and exploitation of value-dependent constraints. In Proceedings of the IEEE Real-Time Technology and Applications Symposium, Vancouver. IEEE Computer Society Press. 79--99.

[10]

Healy, C. and Whalley, D. 2000. Automatic detection and exploitation of branch constraints for timing analysis. IEEE Transaction on Software Engineering 28, 8 (Aug.), 763--781.

[11]

Healy, C., Whalley, D., and Harmon, M. 1995. Integrating the timing analysis of pipelining and instruction caching. In Proceedings of the Sixteenth IEEE Real-Time Systems Symposium, Pisa. IEEE Computer Society Press. 288--297.

[12]

Healy, C., Arnold, R., Mueller, F., Whalley, D., and Harmon, M. 1999. Bounding pipeline and instruction cache performance. IEEE Transactions on Computers 48, 1 (Jan.), 53--70.

Digital Library

[13]

Healy, C., Sjodin, M., Rustagi, V., Whalley, D., and van engelen, R. 2000a. Supporting timing analysis by automatic bounding of loop iterations. Real-Time Systems 18, 2 (May), 121--148.

[14]

Healy, C., Whalley, D., and Van engelen, R. 2000b. A general approach for tight timing predictions of non-rectangular loops. In WIP Proceedings of the IEEE Real-Time Technology and Applications Symposium, Washington, DC. IEEE Computer Society Press. 11--14.

[15]

Hong, S. and Gerber, R. 1993. Compiling real-time programs into schedulable code. In Proceedings of the SIGPLAN'93, Albuquerque, NM. ACM Press, New York. 166--176.

[16]

Ko, L., Healy, C., Ratliff, E., Arnold, R., Whalley, D., and Harmon, M. 1996. Supporting the specification and analysis of timing constraints. In Proceeding of the IEEE Real-Time Technology and Application Symposium, Boston, MA. IEEE Computer Society Press. 170--178.

[17]

Ko, L., Al-Yaqoubi, N., Healy, C., Ratliff, E., Arnold, R., Whalley, D., and Harmon, M. 1999. Timing constraint specification and analysis. Software Practice & Experience 29, 1 (Jan.), 77--98.

[18]

Kulkarni, P., Zhao, W., Moon, H., Cho, K., Whalley, D., Davidson, J., Bailey, M., Paek, Y., and Gallivan, K. 2003. Finding effective optimization phase sequences. In ACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems, San Diego, CA. ACM Press, New York. 12--23.

[19]

Lee, S., Lee, J., Park, C., and Min, S. 2004. A flexible tradeoff between code size and wcet using a dual instruction set processor. In International Workshop on Software and Compilers for Embedded Systems, Amsterdam. Springer, New york. 244--258.

[20]

Li, Y., Malik, S., and Wolfe, A. 1995. Efficient microarchitecture modeling and path analysis for real-time software. In Proceedings of the Sixteenth IEEE Real-time Systems Symposium, Pisa. IEEE Computer Society Press. 298--307.

[21]

Lim, S., Bae, Y., Jang, G., Rhee, B., Min, S., Park, C., Shin, H., Park, K., and Kim, C. 1994. An accurate worst case timing analysis technique for risc processors. In Proceedings of the Fifteenth IEEE Real-Time Systems Symposium, San Juan. IEEE Computer Society Press. 875--889.

[22]

Lundqvist, T. and Stenstrom, P. 1998. Integrating path and timing analysis using instruction-level simulation techniques. In Proceedings of SIGPLAN Workshop on Languages, Compilers and Tools for Embedded Systems(LCTES'98), Montreal. IEEE Computer Society Press. 1--15.

[23]

Mcfarling, S. and Hennessy, J. 1986. Reducing the cost of branches. In 13th Annual International Symposium of Computer Architecture, Tokyo, Japan. 396--403.

[24]

Mueller, F. 1997. Timing predictions for multi-level caches. In ACM SIGPLAN Workshop on Language, Compiler and Tool Support for Real-time Systems, Las Vegas, NV. ACM Press, New York. 29--36.

[25]

Mueller, F. 2000. Timing analysis for instruction caches. Real-Time Systems 18, 2 (May), 209--239.

Digital Library

[26]

Pettis, K. and hansen, R. 1990. Profile guided code position. In Proceeding of the ACM SIGPLAN'90 Conference on Programming Language Design and Implementation, ACM Press, New York. 16--27.

[27]

Shaw, A. C. 1989. Reasoning about time in higher-level language software. IEEE Transactions on Software Engineering 15, 7, 875--889.

Digital Library

[28]

Star Core, I. 2001a. Sc100 simulator reference manual.

[29]

Star Core, I. 2001b. Sc110 dsp core reference manual.

[30]

T. Marlowe, S. M. 1992. Safe optimization for hard real-time programming. In Special Session on Real-Time Programming, Second International Conference on Systems Integration. 438--446.

[31]

Vivancos, E., Healy, C., Mueller, F., and Whalley, D. 2001. Parametric timing analysis. In Proceedings of the ACM SIGPLAN Workshop on Language, Compilers, and Tools for Embedded Systems, Snowbird, UT. ACM Press, New York. 83--93.

[32]

White, R. T., Mueller, F., Healy, C., Whalley, D., and Harmon, M. 1997. Timing analysis for data caches and set-associative caches. In Proceedings of the IEEE Real-Time Technology and Application Symposium, Montreal. IEEE Computer Society Press. 192--202.

[33]

White, R., Mueller, F., Healy, C., Whalley, D., and Harmon, M. 1999. Timing analysis for data caches and wrap-around-fill caches. Real-Time Systems 17, 1 (Nov.), 209--233.

[34]

Zhao, W., Cai, B., Whalley, D., Bailey, M., van Engelen, R., Yuan, X., Hiser, J., Davidson, J., Gallivan, K., and Jones, D. 2002. Vista: A system for interactive code improvement. In ACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems, Berlin. ACM Press, New York. 155--164.

Cited By

Zheng LLiao XJin H(2018)Efficient and Scalable Graph Parallel Processing With Symbolic ExecutionACM Transactions on Architecture and Code Optimization10.1145/317043415:1(1-25)Online publication date: 22-Mar-2018
https://dl.acm.org/doi/10.1145/3170434
Liu TLi MXue C(2018)Instruction Cache Locking for Embedded Systems using Probability ProfileJournal of Signal Processing Systems10.1007/s11265-011-0650-669:2(173-188)Online publication date: 27-Dec-2018
https://dl.acm.org/doi/10.1007/s11265-011-0650-6
Liu TLi MXue C(2018)Instruction cache locking for multi-task real-time embedded systemsReal-Time Systems10.1007/s11241-011-9139-448:2(166-197)Online publication date: 28-Dec-2018
https://dl.acm.org/doi/10.1007/s11241-011-9139-4
Show More Cited By

Index Terms

Improving WCET by applying a WC code-positioning optimization

Recommendations

Improving WCET by applying worst-case path optimizations

It is advantageous to perform compiler optimizations that attempt to lower the worst-case execution time (WCET) of an embedded application since tasks with lower WCETs are easier to schedule and more likely to meet their deadlines. Compiler writers in ...
WCET-driven branch prediction aware code positioning
CASES '11: Proceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems

In the past decades, embedded system designers moved from simple, predictable system designs towards complex systems equipped with caches, branch prediction units and speculative execution. This step was necessary in order to fulfill increasing ...
Multicore-aware hybrid code positioning to reduce worst-case execution time
INTERACT-14: Proceedings of the 2010 Workshop on Interaction between Compilers and Computer Architecture

Unlike general-purpose programs, it is important to reduce the worst-case performance rather than the average-case performance for real-time systems. In this paper, based on a dual-core processor with a shared L2 cache, we propose a code positioning ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Architecture and Code Optimization

ACM Transactions on Architecture and Code Optimization Volume 2, Issue 4

December 2005

116 pages

ISSN:1544-3566

EISSN:1544-3973

DOI:10.1145/1113841

Issue’s Table of Contents

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2005

Published in TACO Volume 2, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
903
Total Downloads

Downloads (Last 12 months)96
Downloads (Last 6 weeks)13

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zheng LLiao XJin H(2018)Efficient and Scalable Graph Parallel Processing With Symbolic ExecutionACM Transactions on Architecture and Code Optimization10.1145/317043415:1(1-25)Online publication date: 22-Mar-2018
https://dl.acm.org/doi/10.1145/3170434
Liu TLi MXue C(2018)Instruction Cache Locking for Embedded Systems using Probability ProfileJournal of Signal Processing Systems10.1007/s11265-011-0650-669:2(173-188)Online publication date: 27-Dec-2018
https://dl.acm.org/doi/10.1007/s11265-011-0650-6
Liu TLi MXue C(2018)Instruction cache locking for multi-task real-time embedded systemsReal-Time Systems10.1007/s11241-011-9139-448:2(166-197)Online publication date: 28-Dec-2018
https://dl.acm.org/doi/10.1007/s11241-011-9139-4
Zhao WKreahling WWhalley DHealy CMueller F(2018)Improving WCET by applying worst-case path optimizationsReal-Time Systems10.1007/s11241-006-8643-434:2(129-152)Online publication date: 27-Dec-2018
https://dl.acm.org/doi/10.1007/s11241-006-8643-4
Kafshdooz MTaram MAssadi SEjlali A(2016)A Compile-Time Optimization Method for WCET Reduction in Real-Time Embedded Systems through Block FormationACM Transactions on Architecture and Code Optimization10.1145/284508312:4(1-25)Online publication date: 4-Jan-2016
https://dl.acm.org/doi/10.1145/2845083
Anand KBarua R(2015)Instruction-Cache Locking for Improving Embedded Systems PerformanceACM Transactions on Embedded Computing Systems10.1145/270010014:3(1-25)Online publication date: 21-Apr-2015
https://dl.acm.org/doi/10.1145/2700100
Li FZhao MXue C(2015)C3Proceedings of the 2015 IEEE 21st International Conference on Embedded and Real-Time Computing Systems and Applications10.1109/RTCSA.2015.34(51-59)Online publication date: 19-Aug-2015
https://dl.acm.org/doi/10.1109/RTCSA.2015.34
Axer PErnst RFalk HGirault AGrund DGuan NJonsson BMarwedel PReineke JRochange CSebastian MHanxleden RWilhelm RYi W(2014)Building timing predictable embedded systemsACM Transactions on Embedded Computing Systems10.1145/256003313:4(1-37)Online publication date: 10-Mar-2014
https://dl.acm.org/doi/10.1145/2560033
Wu LZhang W(2013)Reducing worst-case execution time of hybrid SPM-caches2013 IEEE 32nd International Performance Computing and Communications Conference (IPCCC)10.1109/PCCC.2013.6742770(1-9)Online publication date: Dec-2013
https://doi.org/10.1109/PCCC.2013.6742770
Falk HKotthaus HGupta RMooney V(2011)WCET-driven cache-aware code positioningProceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems10.1145/2038698.2038722(145-154)Online publication date: 9-Oct-2011
https://dl.acm.org/doi/10.1145/2038698.2038722
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents