skip to main content
research-article

Interrupt modeling for efficient high-level scheduler design space exploration

Published: 06 February 2008 Publication History

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]
Balarin, F., Watanabe, Y., Hsieh, H., Lavagno, L., Passerone, C., and Sangiovanni-Vincentelli, A. 2003. Metropolis: An integrated electronic system design environment. Comput. 36, 4, 45--52.
[2]
Bobrek, A., Pieper, J. J., Nelson, J. E., Paul, J. M., and Thomas, D. E. 2004. Modeling shared resource contention using a hybrid simulation/analytical approach. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE'04). Washington, DC, IEEE Computer Society, 21144.
[3]
Bouchhima, A., Yoo, S., and Jeraya, A. 2004. Fast and accurate timed execution of high level embedded software using HW/SW interface simulation model. In Proceedings of the Conference on Asia South Pacific Design Automation. 469--474.
[4]
Cassidy, A. S., Paul, J. M., and Thomas, D. E. 2003. Layered, multi-threaded, high-level performance design. In Proceedings of the Conference on Design, Automation and Test in Europe. 10954.
[5]
Duda, K. J. and Cheriton, D. R. 1999. Borrowed-virtual-time (BVT) scheduling: supporting latency-sensitive threads in a general-purpose scheduler. In Proceedings of the ACM Symposium on Operating Systems Principles. 261--276.
[6]
Guthaus, M. R., Ringenberg, J. S., Ernst, D., Austin, T. M., Mudge, T., and Brown, R. B. 2001. MiBench: A free, commercially representative embedded benchmark suite. In Proceedings of the IEEE Workshop on Workload Characterization. 1--12.
[7]
Honda, S., Wakabayashi, T., Tomiyama, H., and Takada, H. 2004. RTOS-centric hardware/software cosimulator for embedded system design. In Proceedings of the International Conference on HW/SW Codesign and System Synthesis. 158--163.
[8]
Jones, M. B. and Regehr, J. 1999. The problems you're having may not be the problems you think you're having: Results from a latency study of windows nt. In Proceedings of the 5th IEEE Real-Time Technology and Applications Symposium. 287.
[9]
Kempf, T., Doerper, M., Leupers, R., Ascheid, G., Meyr, H., Kogel, T., and Vanthournout, B. 2005. A modular simulation framework for spatial and temporal task mapping onto multi-processor soc platforms. In Proceedings of the conference on Design, Automation and Test in Europe (DATE'05). Washington, DC, IEEE Computer Society, 876--881.
[10]
Kim, D., Yi, Y., and Ha, S. 2005. Trace-driven HW/SW cosimulation using virtual synchronization technique. In Proceedings of the Conference on Design Automation. 345--348.
[11]
Kumar, R. 2005. Heterogenous chip multiprocessors. IEEE Comput. 38, 32--38.
[12]
Kumar, R., Farkas, K. I., Jouppi, N. P., hy Ranganathan, P., and Tullsen, D. M. 2003. Single-isa heterogeneous multi-core architectures: The potential for processor power reduction. In Proceedings of the 36th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO'36). Washington, DC, IEEE Computer Society, 81.
[13]
Lavagno, L., Passerone, C., Shah, V., and Watanabe, Y. 2005. A time slice based scheduler model for system level design. In Proceedings of the Conference on Design, Automation and Test in Europe. 378--383.
[14]
Meyer, B. H., Pieper, J. J., Paul, J. M., Nelson, J. E., Pieper, S. M., and Rowe, A. G. 2005. Power-performance simulation and design strategies for single-chip heterogeneous multiprocessors. IEEE Trans. Comput. 54, 6, 684--697.
[15]
Milojicic, D. S., Douglis, F., Wheeler, R., and Zhou, S. 2000. Process migration. ACM Comput. Surv. 32, 3, 241--299.
[16]
Passerone, C., Lavagno, L., Chiodo, M., and Sangiovanni-Vincentelli, A. 1997. Fast hardware/software co-simulation for virtual prototyping and trade-off analysis. In Proceedings of the Conference on Design Automation. 389--394.
[17]
Paul, J. M., Bobrek, A., Nelson, J. E., Pieper, J. J., and Thomas, D. E. 2003. Schedulers as model-based design elements in programmable heterogeneous multiprocessors. In Proceedings of the 40th Conference on Design Automation. 408--411.
[18]
Paul, J. M., Thomas, D. E., and Bobrek, A. 2004. Benchmark-based design strategies for single chip heterogeneous multiprocessors. In Proceedings of the International Conference on HW/SW Codesign and System Synthesis. 54--59.
[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]
Paul, J. M., Thomas, D. E., and Cassidy, A. S. 2005. High-level modeling and simulation of single-chip programmable heterogeneous multiprocessors. ACM Trans. Des. Autom. Electron. Syst. 10, 3, 431--461.
[21]
Pham, D., Anderson, H.-W., Behnen, E., and et al., M. B. 2006. Key features of the design methodology enabling a multi-core SoC implementation of a first-generation cell processor. In Proceedings of the Conference on Asia South Pacific Design Automation. 871--878.
[22]
Philips. http://www.semiconductors.philips.com/products/nexperia/.
[23]
Regehr, J. and Duongsaa, U. 2005. Preventing interrupt overload. In Proceedings of the Conference on Languages, Compilers, and Tools for Embedded Systems. 50--58.
[24]
Rhodes, D. L. and Wolf, W. 1999. Overhead effects in real-time preemptive schedules. In Proceedings of the International Workshop on HW/SW Codesign. 193--197.
[25]
SystemC. http://www.systemc.org/.
[26]
TexasInstruments. http://focus.ti.com/omap/docs/omaphomepage.tsp.
[27]
Yi, Y., Kim, D., and Ha, S. 2003. Virtual synchronization technique with os modeling for fast and time-accurate cosimulation. In Proceedings of the International Conference on HW/SW Codesign and System Synthesis. 1--6.
[28]
Yu, H., Gerstlauer, A., and Gajski, D. 2003. RTOS scheduling in transaction level models. In Proceedings of the International Conference on HW/SW Codesign and System Synthesis. 31--36.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems
ACM Transactions on Design Automation of Electronic Systems  Volume 13, Issue 1
January 2008
496 pages
ISSN:1084-4309
EISSN:1557-7309
DOI:10.1145/1297666
Issue’s Table of Contents
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

Journal Family

Publication History

Published: 06 February 2008
Accepted: 01 September 2007
Revised: 01 June 2007
Received: 01 August 2006
Published in TODAES Volume 13, Issue 1

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Heterogeneous chip multiprocessors
  2. MESH
  3. scenario oriented design

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)1
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2015)Multiprocessor Capacity Metric and AnalysisIEEE Transactions on Computers10.1109/TC.2015.238983164:11(3181-3196)Online publication date: 1-Nov-2015
  • (2015)Chip-level programming of heterogeneous multiprocessors2015 10th International Design & Test Symposium (IDT)10.1109/IDT.2015.7396730(20-25)Online publication date: Dec-2015
  • (2014)iDolaProceedings of the 2014 Theoretical Aspects of Software Engineering Conference (tase 2014)10.1109/TASE.2014.33(193-200)Online publication date: 1-Sep-2014
  • (2011)Capacity metric for chip heterogeneous multiprocessorsProceedings of the seventh IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis10.1145/2039370.2039404(207-216)Online publication date: 9-Oct-2011
  • (2011)Workload Mode Identification for Chip Heterogeneous MultiprocessorsInternational Journal of Parallel Programming10.1007/s10766-011-0175-440:2(184-224)Online publication date: 22-Jun-2011
  • (2010)Military Weaponry and Tactical OperationsTerrorism and Public Safety Policing10.1201/9781439815816.ch4(125-157)Online publication date: 19-Feb-2010
  • (2010)BibliographyTerrorism and Public Safety Policing10.1201/9781439815816.bmatt(405-427)Online publication date: 19-Feb-2010
  • (2009)A modular fast simulation framework for stream-oriented MPSoC2009 IEEE International Symposium on Industrial Embedded Systems10.1109/SIES.2009.5196198(74-81)Online publication date: Jul-2009

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media