Supporting task migration in multi-processor systems-on-chip: a feasibility study

ABSTRACT

With the advent of multi-processor systems-on-chip, the interest in process migration is again on the rise both in research and in product development. New challenges associated with the new scenario include increased sensitivity to implementation complexity, tight power budgets, requirements on execution predictability, the lack of virtual memory support in many low-end MPSoCs. As a consequence, effectiveness and applicability of traditional transparent migration mechanisms are put in discussion in this context. Our paper proposes a task management software infrastructure that is well suited for the constraints of single chip multiprocessors with distributed operating systems. Load balancing in the system is maintained by means of intelligent initial placement and task migration. We propose a user-managed migration scheme based on code checkpointing and user-level middleware support as an effective solution for many MPSoC application domains. In order to prove the practical viability of this scheme, we also propose a characterization methodology for task migration overhead. We derive the minimum execution time following a task migration event during which the system configuration should be frozen to make up for the migration cost.

REFERENCES

• 1: Barak A., La'adan O. and Shiloh A., "'Scalable Cluster Computing with MOSIX for Linux,"' Proc. Linux Expo '99, pp. 95--100, 1999.
• 2: P. E. Chung , Y. Huang , S. Yajnik , G. Fowler , Kiem-Phong Vo , Yi-Min Wang, Checkpointing in CosMiC: A User-Level Process Migration Environment, Proceedings of the 1997 Pacific Rim International Symposium on Fault-Tolerant Systems, p.187, December 15-16, 1997
• 3: D. Pham et al. "The design and implementation of a first generation CELL processor". IEEE/ACM ISSCC, pp. 184--186, 2005. July 2003.
• 4: Fred Douglis , John Ousterhout, Transparent process migration: design alternatives and the sprite implementation, Software—Practice & Experience, v.21 n.8, p.757-785, Aug. 1991 [doi>10.1002/spe.4380210802]
• 5: S. Dharmasanam, "'Multiprocessing with real-time operating systems,"' http://www.embedded.com/story/OEG20030512S0080
• 6: Intel, "'MultiProcessor Specification,"' http://www.intel.com/design/pentium/datashts/242016.htm
• 7: Feihui Li , Mahmut Kandemir, Locality-conscious workload assignment for array-based computations in MPSOC architectures, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065609]
• 8: ARM Limited, "'MPCore Linux 2.6 SMP kernel and tools,"' www.arm.com/products/CPUs/linux2_6_smp.html
• 9: Mahmut Kandemir , Guilin Chen, Locality-Aware Process Scheduling for Embedded MPSoCs, Proceedings of the conference on Design, Automation and Test in Europe, p.870-875, March 07-11, 2005 [doi>10.1109/DATE.2005.198]
• 10: MPARM, http://www-micrel.deis.unibo.it/sitonew/research/mparm.html
• 11: V. Nollet , P. Avasare , J-Y. Mignolet , D. Verkest, Low Cost Task Migration Initiation in a Heterogeneous MP-SoC, Proceedings of the conference on Design, Automation and Test in Europe, p.252-253, March 07-11, 2005 [doi>10.1109/DATE.2005.201]
• 12: L. Friebe, H.-J. Stolberg, M. Berekovic, S. Moch, M. B. Kulaczewski, A. Dehnhardt, P. Pirsch, "HiBRID-SoC: A System-on-Chip Architecture with Two Multimedia DSPs and a RISC Core," IEEE International SOC Conference, September 2003, pp. 85--88.
• 13: Patrick Schaumont , Bo-Cheng Charles Lai , Wei Qin , Ingrid Verbauwhede, Cooperative multithreading on 3mbedded multiprocessor architectures enables energy-scalable design, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065591]
• 14: Randolph D. Nelson , Mark S. Squillante, Modeling and Analysis of Task Migration in Shared-Memory Multiprocessor Computer Systems, Proceedings of the 4th International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, p.258, February 01-04, 1996
• 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: uClinux, "'Embedded Linux Microcontroller Project,"' www.uclinux.org/
• 17: Pieter van der Wolf , Erwin de Kock , Tomas Henriksson , Wido Kruijtzer , Gerben Essink, Design and Programming of Embedded Multiprocessors: An Interface-Centric Approach, Proceedings of the International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS'04), p.206-217, September 08-10, 2004 [doi>10.1109/CODES+ISSS.2004.17]
• 18: E. Zayas, Attacking the process migration bottleneck, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.13-24, November 08-11, 1987, Austin, Texas, United States