Cross-layer customization for rapid and low-cost task preemption in multitasked embedded systems

ABSTRACT

Preemptive multitasking is widely used in many low-cost and real-time embedded applications for its superior hardware utilization. The frequent and asynchronous context switches, however, require the preservation and restoration of the task state, thus resulting in a large number of memory transfer instructions. As a consequence, task responsiveness and application throughput can be significantly deteriorated. To address this problem we propose a cross-layer customization framework which through the close cooperation of compiler, OS, and hardware architecture achieves rapid and low-cost task switch. Application information extracted during compile-time regarding state liveness is exploited in order to preserve a minimal amount of task state on task preemption. We introduce two complementary techniques to implement the application-aware state preservation. The first technique utilizes compiler-generated custom routines which preserve/restore an extremely small live context at judiciously selected points in the application code. The second technique requires more sophisticated hardware support. It employs an OS-controlled register file mapping to achieve a rapid context switch. By mapping a small fraction of the register file in a single clock cycle, a context switch is achieved requiring no memory transfers for the majority of cases to preserve/restore the live state. The effect of aggressively replicated register files, where each task is given its own replica, is achieved with the hardware cost of only adding from 25% to 50% extra physical registers. Through the utilization of these novel mechanisms, a significant improvement on task response time is achieved as the context-switch cost is minimized.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Albrecht, C., Hagenau, R., and Doring, A. 2004. Cooperative software multithreading to enhance utilization of embedded processors for network applications. In Proceedings of the 12th Euromicro Workshop on Parallel, Distributed and Network-Based Processing (PDP'04), IEEE, Los Alamitos, CA, 300--307.
• 3: ARM Ltd. ARM920T technical reference manual. ARM Ltd.
• 4: Baker, T., Snyder, J., and Whalley, D. 1995. Fast context switches: Compiler and architectural support for preemptive scheduling. In Microprocessors and Microsystems, 35--42.
• 5: Volker Barthelmann, Inter-task register-allocation for static operating systems, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 6: Shah Bhatti , James Carlson , Hui Dai , Jing Deng , Jeff Rose , Anmol Sheth , Brian Shucker , Charles Gruenwald , Adam Torgerson , Richard Han, MANTIS OS: an embedded multithreaded operating system for wireless micro sensor platforms, Mobile Networks and Applications, v.10 n.4, p.563-579, August 2005 [doi>10.1145/1160162.1160178]
• 7: Daniel Bovet , Marco Cesati , Andy Oram, Understanding the Linux Kernel, Second Edition, O'Reilly & Associates, Inc., Sebastopol, CA, 2002
• 8: Gregory T. Byrd , Mark A. Holliday, Multithreaded processor architectures, IEEE Spectrum, v.32 n.8, p.38-46, Aug. 1995 [doi>10.1109/6.402166]
• 9: Abhishek Chandra , Micah Adler , Pawan Goyal , Prashant Shenoy, Surplus fair scheduling: a proportional-share CPU scheduling algorithm for symmetric multiprocessors, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.4-4, October 22-25, 2000, San Diego, California
• 10: Alexander Guimaraes Dean, Software thread integration for hardware to software migration, Carnegie Mellon University, Pittsburgh, PA, 2000
• 11: Alexander G. Dean, Software Thread Integration and Synthesis for Real-Time Applications, Proceedings of the conference on Design, Automation and Test in Europe, p.68-69, March 07-11, 2005 [doi>10.1109/DATE.2005.275]
• 12: 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
• 13: Fisher, J., Faraboschi, P., and Young, C. 2005. Embedded Computing: A VLIW Approach to Architecture, Compilers and Tools. Morgan Kaufman, New York, NY.
• 14: 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]
• 15: Hans Hansson , Harold Lawson , Olof Bridal , Christer Eriksson , Sven Larsson , Henrik Lön , Mikael Strömberg, BASEMENT: An Architecture and Methodology for Distributed Automotive Real-Time Systems, IEEE Transactions on Computers, v.46 n.9, p.1016-1027, September 1997 [doi>10.1109/12.620482]
• 16: Hill, J. and Culler, D. 2001. A wireless embedded sensor architecture for system-level optimization. Tech. rep. University of California, Berkeley.
• 17: Hinton, G., Sager, D., Upton, M., Boggs, D., Carmean, D., Kyker, A., and Roussel, P. 2001. The microarchitecture of the pentium 4 processor. Intel Tech. J.
• 18: Intel Corporation. Intel XScale Microarchitecture. Intel Corporation.
• 19: R. E. Kessler, The Alpha 21264 Microprocessor, IEEE Micro, v.19 n.2, p.24-36, March 1999 [doi>10.1109/40.755465]
• 20: 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
• 21: Levis, P., Madden, S., Polastre, J., Szewczyk, R., Whitehouse, K., Woo, A., Gay, D., Hill, J., Welsh, M., Brewer, E., and Culler, D. 2005. Tinyos: An operating system for wireless sensor networks. Ambient Intelligence, Springer-Verlag, Berlin, Germany.
• 22: Matthew C. Merten , Andrew R. Trick , Ronald D. Barnes, An Architectural Framework for Runtime Optimization, IEEE Transactions on Computers, v.50 n.6, p.567-589, June 2001 [doi>10.1109/12.931894]
• 23: Jason Nieh , Monica S. Lam, A SMART scheduler for multimedia applications, ACM Transactions on Computer Systems (TOCS), v.21 n.2, p.117-163, May 2003 [doi>10.1145/762483.762484]
• 24: David W. Oehmke , Nathan L. Binkert , Trevor Mudge , Steven K. Reinhardt, How to Fake 1000 Registers, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.7-18, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.21]
• 25: Joshua Redstone , Susan Eggers , Henry Levy, Mini-Threads: Increasing TLP on Small-Scale SMT Processors, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.19, February 08-12, 2003
• 26: David C. Sastry , Mettin Demirci, The QNX Operating System, Computer, v.28 n.11, p.75-77, November 1995
• 27: Timothy Sherwood , Erez Perelman , Greg Hamerly , Suleyman Sair , Brad Calder, Discovering and Exploiting Program Phases, IEEE Micro, v.23 n.6, p.84-93, November 2003 [doi>10.1109/MM.2003.1261391]
• 28: Siddhartha Shivshankar , Sunil Vangara , Alexander G. Dean, Balancing register pressure and context-switching delays in ASTI systems, 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.1086335]
• 29: WINDRIVER. VxWorks, http://www.windriver.com.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management

General Terms:
Algorithms, Design, Experimentation, Performance