Satisfying real-time constraints with custom instructions

ABSTRACT

Instruction-set extensible processors allow an existing processor core to be extended with application-specific custom instructions. In this paper, we explore a novel application of instruction-set extensions to meet timing constraints in real-time embedded systems. In order to satisfy real-time constraints, the worst-case execution time (WCET) of a task should be reduced as opposed to its average-case execution time. Unfortunately, existing custom instruction selection techniques based on average-case profile information may not reduce a task's WCET. We first develop an Integer Linear Programming (ILP) formulation to choose optimal instruction-set extensions for reducing the WCET. However, ILP solutions for this problem are often too expensive to compute. Therefore, we also propose an efficient and scalable heuristic that obtains quite close to the optimal results. Experiment results indicate that suitable choice of custom instructions can reduce the WCET of our benchmark programs by as much as 42% (23.5% on an average).

REFERENCES

• 1: Altera. Nios embedded processor, 2003.
• 2: Marnix Arnold , Henk Corporaal, Designing domain-specific processors, Proceedings of the ninth international symposium on Hardware/software codesign, p.61-66, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371677]
• 3: Kubilay Atasu , Laura Pozzi , Paolo Ienne, Automatic application-specific instruction-set extensions under microarchitectural constraints, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775897]
• 4: Todd Austin , Eric Larson , Dan Ernst, SimpleScalar: An Infrastructure for Computer System Modeling, Computer, v.35 n.2, p.59-67, February 2002 [doi>10.1109/2.982917]
• 5: Newton Cheung , Sri Parameswaran , Jörg Henkel, INSIDE: INstruction Selection/Identification & Design Exploration for Extensible Processors, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.291, November 09-13, 2003 [doi>10.1109/ICCAD.2003.86]
• 6: Nathan Clark , Hongtao Zhong , Scott Mahlke, Processor Acceleration Through Automated Instruction Set Customization, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.129, December 03-05, 2003
• 7: Jason Cong , Yiping Fan , Guoling Han , Zhiru Zhang, Application-specific instruction generation for configurable processor architectures, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA [doi>10.1145/968280.968307]
• 8: Paolo Faraboschi , Geoffrey Brown , Joseph A. Fisher , Giuseppe Desoli , Fred Homewood, Lx: a technology platform for customizable VLIW embedded processing, Proceedings of the 27th annual international symposium on Computer architecture, p.203-213, June 2000, Vancouver, British Columbia, Canada
• 9: Ricardo E. Gonzalez, Xtensa: A Configurable and Extensible Processor, IEEE Micro, v.20 n.2, p.60-70, March 2000 [doi>10.1109/40.848473]
• 10: M. R. Guthaus et al. Mibench: A free, commercially representative embedded benchmark suite. In IEEE Annual Workshop on Workload Characterization, 2001.
• 11: R. Kastner , A. Kaplan , S. Ogrenci Memik , E. Bozorgzadeh, Instruction generation for hybrid reconfigurable systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.4, p.605-627, October 2002 [doi>10.1145/605440.605446]
• 12: 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
• 13: Jong-eun Lee , Kiyoung Choi , Nikil Dutt, Efficient instruction encoding for automatic instruction set design of configurable ASIPs, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.649-654, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774668]
• 14: S. Lee et al. A flexible tradeoff between code size and WCET using a dual instruction set processor. In SCOPES, 2004.
• 15: Chang Yun Park , Alan C. Shaw, Experiments with a Program Timing Tool Based on Source-Level Timing Schema, Computer, v.24 n.5, p.48-57, May 1991 [doi>10.1109/2.76286]
• 16: Gustav Pospischil , Peter Puschner , Alexander Vrchoticky , Ralph Zainlinger, Developing Real-Time Tasks With Predictable Timing, IEEE Software, v.9 n.5, p.35-44, September 1992 [doi>10.1109/52.156895]
• 17: F. Stappert. WCET benchmarks. Available from http://www.c-lab.de/home/en/download.html.
• 18: Stretch. S5000 software-configurable processors, 2004.
• 19: F. Sun, S. Ravi, A. Raghunathan, and N. K. Jha. Custom-instruction synthesis for extensible-processor platforms. IEEE TCAD, 23(2), 2004.
• 20: Pan Yu , Tulika Mitra, Characterizing embedded applications for instruction-set extensible processors, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996764]
• 21: Pan Yu , Tulika Mitra, Scalable custom instructions identification for instruction-set extensible processors, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023844]
• 22: W. Zhao et al. Tuning the WCET of embedded applications. In RTAS, 2004.
• 23: Wankang Zhao , David Whalley , Christopher Healy , Frank Mueller, WCET Code Positioning, Proceedings of the 25th IEEE International Real-Time Systems Symposium (RTSS'04), p.81-91, December 05-08, 2004 [doi>10.1109/REAL.2004.55]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Design, Performance

Keywords:
customizable processors, execution time, instruction-set extensions, real-time systems, worst-case