Push-assisted migration of real-time tasks in multi-core processors

ABSTRACT

Multicores are becoming ubiquitous, not only in general-purpose but also embedded computing. This trend is a reflexion of contemporary embedded applications posing steadily increasing demands in processing power. On such platforms, prediction of timing behavior to ensure that deadlines of real-time tasks can be met is becoming increasingly difficult. While real-time multicore scheduling approaches help to assure deadlines based on firm theoretical properties, their reliance on task migration poses a significant challenge to timing predictability in practice. Task migration actually (a) reduces timing predictability for contemporary multicores due to cache warm-up overheads while (b) increasing traffic on the network-on-chip (NoC) interconnect.

This paper puts forth a fundamentally new approach to increase the timing predictability of multicore architectures aimed at task migration in embedded environments. A task migration between two cores imposes cache warm-up overheads on the migration target, which can lead to missed deadlines for tight real-time schedules. We propose novel micro-architectural support to migrate cache lines. Our scheme shows dramatically increased predictability in the presence of cross-core migration.

Experimental results for schedules demonstrate that our scheme enables real-time tasks to meet their deadlines in the presence of task migration. Our results illustrate that increases in execution time due to migration is reduced by our scheme to levels that may prevent deadline misses of real-time tasks that would otherwise occur. Our mechanism imposes an overhead at a fraction of the task's execution time, yet this overhead can be steered to fill idle slots in the schedule, i.e., it does not contribute to the execution time of the migrated task. Overall, our novel migration scheme provides a unique mechanism capable of significantly increasing timing predictability in the wake of task migration.

REFERENCES

• 1: Tera-scale research prototype: Connecting 80 simple sores on a single test chip. ftp://download.intel.com/research/platform/terascale/terascaleresearchprototypebackgrounder.pdf.
• 2: Tilera processor family. http://www.tilera.com/products/processors.php.
• 3: Wcet project benchmarks, 2007. http://www.mrtc.mdh.se/projects/wcetbenchmarks.html.
• 4: Assessing task migration impact on embedded soft real-time streaming multimedia applications, EURASIP Journal on Embedded Systems, 2008, p.1-15, January 2008 [doi>10.1155/2008/518904]
• 5: James H. Anderson , John M. Calandrino , UmaMaheswari C. Devi, Real-Time Scheduling on Multicore Platforms, Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium, p.179-190, April 04-07, 2006 [doi>10.1109/RTAS.2006.35]
• 6: J. Anderson and A. Srinivasan. Early-release fair scheduling. In Euromicro Conference on Real-Time Systems, pages 35--43, June 2000.
• 7: James H. Anderson , Anand Srinivasan, Mixed Pfair/ERfair Scheduling of Asynchronous Periodic Tasks, Proceedings of the 13th Euromicro Conference on Real-Time Systems, p.76, June 13-15, 2001
• 8: R. Arnold, F. Mueller, D. B. Whalley, and M. Harmon. Bounding worst-case instruction cache performance. In IEEE Real-Time Systems Symposium, pages 172--181, Dec. 1994.
• 9: Sanjoy Baruah, Techniques for Multiprocessor Global Schedulability Analysis, Proceedings of the 28th IEEE International Real-Time Systems Symposium, p.119-128, December 03-06, 2007 [doi>10.1109/RTSS.2007.48]
• 10: S. Baruah, N. Cohen, C. Plaxton, and D. Varvel. Proportionate progress: A notion of fairness in resource allocation. Algorithmica, 15:600--625, 1996.
• 11: Stefano Bertozzi , Andrea Acquaviva , Davide Bertozzi , Antonio Poggiali, Supporting task migration in multi-processor systems-on-chip: a feasibility study, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 12: Jörg Liebeherr , Almut Burchard , Yingfeng Oh , Sang H. Son, New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems, IEEE Transactions on Computers, v.44 n.12, p.1429-1442, December 1995 [doi>10.1109/12.477248]
• 13: John M. Calandrino , James H. Anderson, Cache-Aware Real-Time Scheduling on Multicore Platforms: Heuristics and a Case Study, Proceedings of the 2008 Euromicro Conference on Real-Time Systems, p.299-308, July 02-04, 2008 [doi>10.1109/ECRTS.2008.10]
• 14: Dhruba Chandra , Fei Guo , Seongbeom Kim , Yan Solihin, Predicting Inter-Thread Cache Contention on a Chip Multi-Processor Architecture, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.340-351, February 12-16, 2005 [doi>10.1109/HPCA.2005.27]
• 15: Robit Chandra , Leonardo Dagum , Dave Kohr , Dror Maydan , Jeff McDonald , Ramesh Menon, Parallel programming in OpenMP, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 16: Jichuan Chang , Gurindar S. Sohi, Cooperative Caching for Chip Multiprocessors, Proceedings of the 33rd annual international symposium on Computer Architecture, p.264-276, June 17-21, 2006
• 17: Zeshan Chishti , Michael D. Powell , T. N. Vijaykumar, Optimizing Replication, Communication, and Capacity Allocation in CMPs, Proceedings of the 32nd annual international symposium on Computer Architecture, p.357-368, June 04-08, 2005
• 18: David Choffnes , Mark Astley , Michael J. Ward, Migration policies for multi-core fair-share scheduling, ACM SIGOPS Operating Systems Review, v.42 n.1, January 2008 [doi>10.1145/1341312.1341328]
• 19: S. Dhall and C. Liu. On a real-time scheduling problem. Operations Research, 26(1):127--140, 1978.
• 20: Noel Eisley , Li-Shiuan Peh , Li Shang, In-Network Cache Coherence, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.321-332, December 09-13, 2006 [doi>10.1109/MICRO.2006.27]
• 21: Noel Eisley , Li-Shiuan Peh , Li Shang, Leveraging on-chip networks for data cache migration in chip multiprocessors, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada [doi>10.1145/1454115.1454144]
• 22: A. Fedorova, M. Seltzer, and M. Smith. Cache-fair thread scheduling for multicore processors. Technical Report TR-17-06, Harvard University, Oct. 2006.
• 23: Jayanth Gummaraju , Mendel Rosenblum, Stream Programming on General-Purpose Processors, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.343-354, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.32]
• 24: Damien Hardy , Isabelle Puaut, WCET Analysis of Multi-level Non-inclusive Set-Associative Instruction Caches, Proceedings of the 2008 Real-Time Systems Symposium, p.456-466, November 30-December 03, 2008 [doi>10.1109/RTSS.2008.10]
• 25: Ravi Iyer, CQoS: a framework for enabling QoS in shared caches of CMP platforms, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006246]
• 26: Natalie D. Enright Jerger , Li-Shiuan Peh , Mikko H. Lipasti, Virtual tree coherence: Leveraging regions and in-network multicast trees for scalable cache coherence, Proceedings of the 2008 41st IEEE/ACM International Symposium on Microarchitecture, p.35-46, November 08-12, 2008 [doi>10.1109/MICRO.2008.4771777]
• 27: Seon Wook Kim , Michael Voss , Bob Kuhn , Hans-Christian Hoppe , Wolfgang Nagel, VGV: Supporting Performance Analysis of Object-Oriented Mixed MPI/OpenMP Parallel Applications, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.331, April 15-19, 2002
• 28: S. Lauzac, R. Melhem, and D. Mosse. Comparison of global and partitioning schemes for scheduling rate monotonic tasks on a multiprocessor. In Euromicro Workshop on Real-Time Systems, pages 188--195, 1998.
• 29: Chang-Gun Lee , J. Hahn , Sang Lyul Min , R. Ha , Seongsoo Hong , Chang Yun Park , Minsuk Lee , Chong Sang Kim, Analysis of cache-related preemption delay in fixed-priority preemptive scheduling, Proceedings of the 17th IEEE Real-Time Systems Symposium, p.264, December 04-06, 1996
• 30: Tong Li , Dan Baumberger , David A. Koufaty , Scott Hahn, Efficient operating system scheduling for performance-asymmetric multi-core architectures, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362694]
• 31: T. Li, P. Brett, B. Hohlt, R. Knauerhase, S. McElderry, and S. Hahn. Operating system support for shared-isa asymmetric multi-core architectures. In Workshop on the Interaction between Operating Systems and Computer Architecture, pages 19--26, June 2008.
• 32: J. Liu. Real-Time Systems. Prentice Hall, 2000.
• 33: Michael R. Marty , Jesse D. Bingham , Mark D. Hill , Alan J. Hu , Milo M. K. Martin , David A. Wood, Improving Multiple-CMP Systems Using Token Coherence, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.328-339, February 12-16, 2005 [doi>10.1109/HPCA.2005.17]
• 34: Michael R. Marty , Mark D. Hill, Virtual hierarchies to support server consolidation, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 35: Mark Moir , Srikanth Ramamurthy, Pfair Scheduling of Fixed and Migrating Periodic Tasks on Multiple Resources, Proceedings of the 20th IEEE Real-Time Systems Symposium, p.294, December 01-03, 1999
• 36: F. Mueller. Timing predictions for multi-level caches. In ACM SIGPLAN Workshop on Language, Compiler, and Tool Support for Real-Time Systems, pages 29--36, June 1997.
• 37: Frank Mueller, Timing Analysis for Instruction Caches, Real-Time Systems, v.18 n.2/3, p.217-247, May 2000 [doi>10.1023/A:1008145215849]
• 38: H. Ramaprasad and F. Mueller. Tightening the bounds on feasible preemptions. Transactions on Embedded Computing Systems, Mar. 2008 (accepted).
• 39: J. Renau, B. Fragela, J. Tuck, W. Liu, L. Ceze, S. Sarangi, P. Sack, and a. P. M. K. Strauss. Sesc simulator. http://sesc.sourceforge.net, Jan. 2005.
• 40: Shane Ryoo , Christopher I. Rodrigues , Sara S. Baghsorkhi , Sam S. Stone , David B. Kirk , Wen-mei W. Hwu, Optimization principles and application performance evaluation of a multithreaded GPU using CUDA, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345220]
• 41: Anand Srinivasan , James H. Anderson, Optimal rate-based scheduling on multiprocessors, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509938]
• 42: Jan Staschulat , Rolf Ernst, Multiple process execution in cache related preemption delay analysis, Proceedings of the 4th ACM international conference on Embedded software, September 27-29, 2004, Pisa, Italy [doi>10.1145/1017753.1017798]
• 43: Jan Staschulat , Simon Schliecker , Rolf Ernst, Scheduling Analysis of Real-Time Systems with Precise Modeling of Cache Related Preemption Delay, Proceedings of the 17th Euromicro Conference on Real-Time Systems, p.41-48, July 06-08, 2005 [doi>10.1109/ECRTS.2005.26]
• 44: Karin Strauss , Xiaowei Shen , Josep Torrellas, Uncorq: Unconstrained Snoop Request Delivery in Embedded-Ring Multiprocessors, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.327-342, December 01-05, 2007 [doi>10.1109/MICRO.2007.43]
• 45: William Thies , Michal Karczmarek , Saman P. Amarasinghe, StreamIt: A Language for Streaming Applications, Proceedings of the 11th International Conference on Compiler Construction, p.179-196, April 08-12, 2002
• 46: Joachim Wegener , Frank Mueller, A Comparison of Static Analysis and Evolutionary Testing for the Verification of Timing Constraints, Real-Time Systems, v.21 n.3, p.241-268, November 2001 [doi>10.1023/A:1011132221066]
• 47: Reinhard Wilhelm , Jakob Engblom , Andreas Ermedahl , Niklas Holsti , Stephan Thesing , David Whalley , Guillem Bernat , Christian Ferdinand , Reinhold Heckmann , Tulika Mitra , Frank Mueller , Isabelle Puaut , Peter Puschner , Jan Staschulat , Per Stenström, The worst-case execution-time problem—overview of methods and survey of tools, ACM Transactions on Embedded Computing Systems (TECS), v.7 n.3, p.1-53, April 2008 [doi>10.1145/1347375.1347389]
• 48: www.openmp.org. Official OpenMP Specification, May 2005.
• 49: J. Yan and W. Zhang. Time-predictable l2 caches for real-time multicore processors. In Work in Progress session of IEEE Real-Time Systems Symposium, Dec. 2007.
• 50: J. Yan and W. Zhang. Wcet analysis of multi-core processors. In Work in Progress session of IEEE Real-Time Systems Symposium, Dec. 2007.
• 51: Jun Yan , Wei Zhang, WCET Analysis for Multi-Core Processors with Shared L2 Instruction Caches, Proceedings of the 2008 IEEE Real-Time and Embedded Technology and Applications Symposium, p.80-89, April 22-24, 2008 [doi>10.1109/RTAS.2008.6]
• 52: M. Zhang and K. Asanovic. Victim migration: Dynamically adapting between private and shared cmp caches. TR 2005-064, MIT CSAIL, 2005.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

General Terms:
Design, Experimentation

Keywords:
multi-core architectures, real-time systems, task migration., timing analysis