More Web Proxy on the site http://driver.im/

research-article

WCET-aware hyper-block construction for clustered VLIW processors

Authors:

Jingling XueAuthors Info & Claims

LCTES 2019: Proceedings of the 20th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems

Pages 110 - 122

https://doi.org/10.1145/3316482.3326349

Published: 23 June 2019 Publication History

Abstract

Hyper-blocks can significantly improve instruction level parallelism on a wide range of super-scalar and VLIW processors. However, most hyper-block construction approaches aim at minimizing the average-case execution time of a program. In real-time embedded systems, minimizing the worst-case execution time (WCET) of a program is the primary goal of an optimizing compiler. We investigate the hyper-block construction problem for a program executed on a clustered VLIW processor such that the WCET of the program is minimized, and propose a novel heuristic approach considering tail duplications. Our approach is underpinned by a novel priority scheme and a precise tail duplication cost model for computing the WCET of a program. We have implemented our approach in Trimaran 4.0, and compared it with the state-of-the-art approach by using a set of 8 benchmark suites. The experimental results show that our approach achieves the maximum WCET improvement of 20.37% and the average WCET improvement of 11.59%, respectively.

References

[1]

Andreu Carminati, Renan Augusto Starke, and Rômulo Silva de Oliveira. 2017. Combining loop unrolling strategies and code predication to reduce the worst-case execution time of real-time software. Applied Computing and Informatics (2017).

[2]

Inc CEVA. 2017. CEVA-X DSP Cores for Multimedia and Communications. Copyright. Retrieved from http://www.ceva-dsp.com/product/ ceva-x2/ .

[3]

Lakshmi N Chakrapani, John Gyllenhaal, W Hwu Wen-mei, Scott A Mahlke, Krishna V Palem, and Rodric M Rabbah. 2004. Trimaran: An infrastructure for research in instruction-level parallelism. In International Workshop on Languages and Compilers for Parallel Computing. Springer, 32–41.

Digital Library

[4]

Pohua P Chang, Scott A Mahlke, and Wen-Mei W Hwu. 1991. Using profile information to assist classic code optimizations. Software: Practice and Experience 21, 12 (1991), 1301–1321.

Digital Library

[5]

Transmeta Corporation. 2001-2004. Transmeta Efficeon Processor. Copyright. Retrieved from http://datasheets.chipdb.org/Transmeta/ TM8600/efficeon_tm8600_prod_brief.pdf .

[6]

Heiko Falk. 2009. WCET-aware register allocation based on graph coloring. In Proceedings of the 46th Annual Design Automation Conference. ACM, 726–731.

Digital Library

[7]

Heiko Falk, Norman Schmitz, and Florian Schmoll. 2011. WCET-aware register allocation based on integer-linear programming. In Proceedings of the 2011 23rd Euromicro Conference on Real-Time Systems. IEEE Computer Society, 13–22.

Digital Library

[8]

Joseph A. Fisher. 1981. Trace scheduling: a technique for global microcode compaction. IEEE transactions on computers 30, 7 (1981), 478– 490.

Digital Library

[9]

Jan Gustafsson, Adam Betts, Andreas Ermedahl, and Björn Lisper. 2010. The Mälardalen WCET benchmarks: Past, present and future. In OASIcs-OpenAccess Series in Informatics, Vol. 15. Schloss DagstuhlLeibniz-Zentrum fuer Informatik.

[10]

Yazhi Huang, Liang Shi, Jianhua Li, Qingan Li, and Chun Jason Xue. 2014. WCET-aware re-scheduling register allocation for real-time embedded systems with clustered VLIW architecture. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 22, 1 (2014), 168–180.

Digital Library

[11]

Texas Instruments incorporated. 1995-2016. TI TMS320C64x DSPs Architecture. Copyright. Retrieved from http://www.ti.com .

[12]

Morteza Mohajjel Kafshdooz, Mohammadkazem Taram, Sepehr Assadi, and Alireza Ejlali. 2016. A compile-time optimization method for WCET reduction in real-time embedded systems through block formation. ACM Transactions on Architecture and Code Optimization (TACO) 12, 4 (2016), 66.

Digital Library

[13]

Björn Lisper. 2014. SWEET–a tool for WCET flow analysis. In International Symposium On Leveraging Applications of Formal Methods, Verification and Validation. Springer, 482–485.

[14]

Paul Lokuciejewski, Timon Kelter, and Peter Marwedel. 2010. Superblock-based source code optimizations for WCET reduction. In Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on. IEEE, 1918–1925.

Digital Library

[15]

Scott A Mahlke, David C Lin, William Y Chen, Richard E Hank, and Roger A Bringmann. 1992. Effective compiler support for predicated execution using the hyperblock. In ACM SIGMICRO Newsletter, Vol. 23. IEEE Computer Society Press, 45–54.

[16]

STMicroelectronics Group of Companies. 2000-2004. ST200 VLIW Series ST231 Core and Instruction Set Architecture Manual. Copyright. Retrieved from http://lipforge.ens-lyon.fr/docman/view.php/53/ 26/st231arch.pdf .

[17]

Joseph CH Park and Mike Schlansker. 1991. On predicated execution. Hewlett-Packard Laboratories Palo Alto, California.

[18]

Xuesong Su, Hui Wu, and Jingling Xue. 2017. An efficient WCET-aware instruction scheduling and register allocation approach for clustered VLIW processors. ACM Transactions on Embedded Computing Systems (TECS) 16, 5s (2017), 120.

Digital Library

[19]

Jun Yan and Wei Zhang. 2008. A time-predictable VLIW processor and its compiler support. Real-Time Systems 38, 1 (2008), 67–84.

Digital Library

[20]

Wankang Zhao, William Kreahling, David Whalley, Christopher Healy, and Frank Mueller. 2005. Improving WCET by optimizing worstcase paths. In 11th IEEE Real Time and Embedded Technology and Applications Symposium. IEEE, 138–147.

Digital Library

[21]

Wenguang Zheng and Hui Wu. 2017. Dynamic data-cache locking for minimizing the WCET of a single task. ACM Trans. Embed. Comput. Syst. 16, 2, Article 31 (Jan. 2017), 29 pages.

Digital Library

[22]

Wenguang Zheng, Hui Wu, and Qing Yang. 2017. WCET-aware dynamic I-cache locking for a single task. ACM Trans. Archit. Code Optim. 14, 1, Article 4 (March 2017), 26 pages.

Digital Library

Cited By

Maroun ESchoeberl MPuschner P(2024)Two-Step Register Allocation for Implementing Single-Path Code2024 IEEE 27th International Symposium on Real-Time Distributed Computing (ISORC)10.1109/ISORC61049.2024.10551362(1-12)Online publication date: 22-May-2024
https://doi.org/10.1109/ISORC61049.2024.10551362
Maroun ESchoeberl MPuschner P(2020)Towards Dual-Issue Single-Path Code2020 IEEE 23rd International Symposium on Real-Time Distributed Computing (ISORC)10.1109/ISORC49007.2020.00039(176-183)Online publication date: May-2020
https://doi.org/10.1109/ISORC49007.2020.00039

Index Terms

WCET-aware hyper-block construction for clustered VLIW processors
1. Computer systems organization
  1. Dependable and fault-tolerant systems and networks
    1. Redundancy
  2. Embedded and cyber-physical systems
    1. Embedded systems
    2. Robotics
2. Networks
  1. Network properties
    1. Network reliability

Recommendations

An Efficient WCET-Aware Instruction Scheduling and Register Allocation Approach for Clustered VLIW Processors
Special Issue ESWEEK 2017, CASES 2017, CODES + ISSS 2017 and EMSOFT 2017

In real-time embedded system design, one major goal is to construct a feasible schedule. Whether a feasible schedule exists depends on the Worst-Case Execution Time (WCET) of each task. Consequently, it is important to minimize the WCET of each task. We ...
Lifetime holes aware register allocation for clustered VLIW processors
DATE '14: Proceedings of the conference on Design, Automation & Test in Europe

This paper presents an on-the-fly register allocator which dynamically detects and utilises lifetime holes for clustered VLIW processors. A lifetime hole is an interval in which a variable does not contain a valid value. A register holding a lifetime ...
Register Allocation by Incremental Graph Colouring for Clustered VLIW Processors
TRUSTCOM '13: Proceedings of the 2013 12th IEEE International Conference on Trust, Security and Privacy in Computing and Communications

This paper presents an incremental register allocator based on graph colouring for clustered VLIW processor. This register allocator is integrated with an instruction scheduler which schedules all the basic blocks of a program in reverse postorder and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

LCTES 2019: Proceedings of the 20th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems

June 2019

218 pages

ISBN:9781450367240

DOI:10.1145/3316482

General Chair:
Jian-Jia Chen
TU Dortmund, Germany
,
Program Chair:
Aviral Shrivastava
Arizona State University, USA

Copyright © 2019 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 June 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

LCTES '19

Sponsor:

LCTES '19: 20th ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems

June 23, 2019

AZ, Phoenix, USA

Acceptance Rates

Overall Acceptance Rate 116 of 438 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
79
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Maroun ESchoeberl MPuschner P(2024)Two-Step Register Allocation for Implementing Single-Path Code2024 IEEE 27th International Symposium on Real-Time Distributed Computing (ISORC)10.1109/ISORC61049.2024.10551362(1-12)Online publication date: 22-May-2024
https://doi.org/10.1109/ISORC61049.2024.10551362
Maroun ESchoeberl MPuschner P(2020)Towards Dual-Issue Single-Path Code2020 IEEE 23rd International Symposium on Real-Time Distributed Computing (ISORC)10.1109/ISORC49007.2020.00039(176-183)Online publication date: May-2020
https://doi.org/10.1109/ISORC49007.2020.00039

View Options

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents