Interrupt modeling for efficient high-level scheduler design space exploration

ABSTRACT

Single Chip Heterogeneous Multiprocessors executing a wide variety of software are increasingly common in consumer electronics. Because of the mix of real-time and best effort software across the entire chip, a key design element of these systems is the choice of scheduling strategy. Without task migration, the benefits of single chip processing cannot be fully realized. Previously, high-level modeling environments have not been capable of modeling asynchronous events such as interrupts and preemptive scheduling while preserving the performance benefits of high level simulation. This paper shows how extensions to Modeling Environment for Software and Hardware (MESH) enable precise modeling of these asynchronous events while running more than 1000 faster than cycle-accurate simulation. We discuss how we achieved this and illustrate its use in modeling preemptive scheduling. We evaluate the potential of migrating running tasks between processors to improve performance in a multimedia cell phone example. We show that by allowing schedulers to rebalance processor loads as new tasks arrive significant performance gains can be achieved over statically partitioned and dynamic scheduling approaches. In our example, we show that system response time can be improved by as much as 1.96 times when a preemptive migratory scheduler is used, despite the overhead incurred by scheduling tasks across multiple processors and transferring state during the migration of running tasks. The contribution of this work is to provide a framework for evaluating preemptive scheduling policies and task migration in a high level simulator, by combining the new ability to model interrupts with dramatically increased efficiency in the high-level modeling of scheduling and commuincation MESH already provides.

REFERENCES

• 1: Felice Balarin , Yosinori Watanabe , Harry Hsieh , Luciano Lavagno , Claudio Passerone , Alberto Sangiovanni-Vincentelli, Metropolis: An Integrated Electronic System Design Environment, Computer, v.36 n.4, p.45-52, April 2003 [doi>10.1109/MC.2003.1193228]
• 2: Alex Bobrek , Joshua J. Pieper , Jeffrey E. Nelson , JoAnn M. Paul , Donald E. Thomas, Modeling Shared Resource Contention Using a Hybrid Simulation/Analytical Approach, Proceedings of the conference on Design, automation and test in Europe, p.21144, February 16-20, 2004
• 3: Aimen Bouchhima , Sungjoo Yoo , Ahmed Jeraya, Fast and accurate timed execution of high level embedded software using HW/SW interface simulation model, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, January 27-30, 2004, Yokohama, Japan
• 4: Andrew S. Cassidy , JoAnn M. Paul , Donald E. Thomas, Layered, Multi-Threaded, High-Level Performance Design, Proceedings of the conference on Design, Automation and Test in Europe, p.10954, March 03-07, 2003
• 5: Kenneth J. Duda , David R. Cheriton, Borrowed-virtual-time (BVT) scheduling: supporting latency-sensitive threads in a general-purpose scheduler, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.261-276, December 12-15, 1999, Charleston, South Carolina, United States
• 6: 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]
• 7: Shinya Honda , Takayuki Wakabayashi , Hiroyuki Tomiyama , Hiroaki Takada, RTOS-centric hardware/software cosimulator for embedded system design, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016760]
• 8: Michael B. Jones , John Regehr, The Problems You're Having May Not Be the Problems You Think You're Having: Results from a Latency Study of Windows NT, Proceedings of the Fifth IEEE Real-Time Technology and Applications Symposium, p.287, June 02-04, 1999
• 9: Torsten Kempf , Malte Doerper , R. Leupers , G. Ascheid , H. Meyr , Tim Kogel , Bart Vanthournout, A Modular Simulation Framework for Spatial and Temporal Task Mapping onto Multi-Processor SoC Platforms, Proceedings of the conference on Design, Automation and Test in Europe, p.876-881, March 07-11, 2005 [doi>10.1109/DATE.2005.21]
• 10: Dohyung Kim , Youngmin Yi , Soonhoi Ha, Trace-driven HW/SW cosimulation using virtual synchronization technique, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065669]
• 11: Rakesh Kumar , Dean M. Tullsen , Norman P. Jouppi , Parthasarathy Ranganathan, Heterogeneous Chip Multiprocessors, Computer, v.38 n.11, p.32-38, November 2005 [doi>10.1109/MC.2005.379]
• 12: Rakesh Kumar , Keith I. Farkas , Norman P. Jouppi , Parthasarathy Ranganathan , Dean M. Tullsen, Single-ISA Heterogeneous Multi-Core Architectures: The Potential for Processor Power Reduction, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.81, December 03-05, 2003
• 13: Luciano Lavagno , Claudio Passerone , Vishal Shah , Yosinori Watanabe, A Time Slice Based Scheduler Model for System Level Design, Proceedings of the conference on Design, Automation and Test in Europe, p.378-383, March 07-11, 2005 [doi>10.1109/DATE.2005.41]
• 14: Brett H. Meyer , Joshua J. Pieper , JoAnn M. Paul , Jeffrey E. Nelson , Sean M. Pieper , Anthony G. Rowe, Power-Performance Simulation and Design Strategies for Single-Chip Heterogeneous Multiprocessors, IEEE Transactions on Computers, v.54 n.6, p.684-697, June 2005 [doi>10.1109/TC.2005.103]
• 15: Dejan S. Milojičić , Fred Douglis , Yves Paindaveine , Richard Wheeler , Songnian Zhou, Process migration, ACM Computing Surveys (CSUR), v.32 n.3, p.241-299, Sept. 2000 [doi>10.1145/367701.367728]
• 16: Claudio Passerone , Luciano Lavagno , Massimiliano Chiodo , Alberto Sangiovanni-Vincentelli, Fast hardware/software co-simulation for virtual prototyping and trade-off analysis, Proceedings of the 34th annual conference on Design automation, p.389-394, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266177]
• 17: JoAnn M. Paul , Alex Bobrek , Jeffrey E. Nelson , Joshua J. Pieper , Donald E. Thomas, Schedulers as model-based design elements in programmable heterogeneous multiprocessors, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775938]
• 18: JoAnn M. Paul , Donald E. Thomas , Alex Bobrek, Benchmark-based design strategies for single chip heterogeneous multiprocessors, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016736]
• 19: Paul, J. M., Thomas, D. E., and Bobrek, A. 2006. Scenario-oriented design for single-chip heterogeneous multiprocessors. IEEE Trans. VLSI Syst. 14, 868--880.
• 20: Joann M. Paul , Donald E. Thomas , Andrew S. Cassidy, High-level modeling and simulation of single-chip programmable heterogeneous multiprocessors, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.3, p.431-461, July 2005 [doi>10.1145/1080334.1080335]
• 21: Dac Pham , Hans-Werner Anderson , Erwin Behnen , Mark Bolliger , Sanjay Gupta , Peter Hofstee , Paul Harvey , Charles Johns , Jim Kahle , Atsushi Kameyama , John Keaty , Bob Le , Sang Lee , Tuyen Nguyen , John Petrovick , Mydung Pham , Juergen Pille , Stephen Posluszny , Mack Riley , Joseph Verock , James Warnock , Steve Weitzel , Dieter Wendel, Key features of the design methodology enabling a multi-core SoC implementation of a first-generation CELL processor, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118497]
• 22: Philips. http://www.semiconductors.philips.com/products/nexperia/.
• 23: John Regehr , Usit Duongsaa, Preventing interrupt overload, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 24: David L. Rhodes , Wayne Wolf, Overhead effects in real-time preemptive schedules, Proceedings of the seventh international workshop on Hardware/software codesign, p.193-197, March 1999, Rome, Italy [doi>10.1145/301177.301529]
• 25: SystemC. http://www.systemc.org/.
• 26: TexasInstruments. http://focus.ti.com/omap/docs/omaphomepage.tsp.
• 27: Youngmin Yi , Dohyung Kim , Soonhoi Ha, Virtual synchronization technique with OS modeling for fast and time-accurate cosimulation, Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, October 01-03, 2003, Newport Beach, CA, USA [doi>10.1145/944645.944647]
• 28: Haobo Yu , Andreas Gerstlauer , Daniel Gajski, RTOS scheduling in transaction level models, Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, October 01-03, 2003, Newport Beach, CA, USA [doi>10.1145/944645.944653]

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Heterogeneous (hybrid) systems; Cellular architecture (e.g., mobile)
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Design, Performance

Keywords:
Heterogeneous chip multiprocessors, MESH, scenario oriented design