Predictable execution adaptivity through embedding dynamic reconfigurability into static MPSoC schedules

ABSTRACT

Advances in semiconductor technologies have placed MPSoCs center stage as a standard architecture for embedded applications of ever increasing complexity. Because of real-time constraints, applications are usually statically parallelized and scheduled onto the target MPSoC so as to obtain predictable worst-case performance. However, both technology scaling trends and resource competition among applications have led to variations in the availability of resources during execution, thus questioning the dynamic viability of the initial static schedules. To eliminate this problem, in this paper we propose to statically generate a compact schedule with predictable response to various resource availability constraints. Such schedules are generated by adhering to a novel band structure, capable of spawning dynamically a regular reassignment upon resource variations. Through incorporating several soft constraints into the original scheduling heuristic, the proposed technique can furthermore exploit the inherent timing slack between dependent tasks, thus retaining the spatial and temporal locality of the original schedule. The efficacy of the proposed technique is confirmed by incorporating it into a widely adopted list scheduling heuristic, and experimentally verifying it in the context of single processor deallocations.

REFERENCES

• 1: Wayne Wolf, The future of multiprocessor systems-on-chips, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996753]
• 2: Santanu Dutta , Rune Jensen , Alf Rieckmann, Viper: A Multiprocessor SOC for Advanced Set-Top Box and Digital TV Systems, IEEE Design & Test, v.18 n.5, p.21-31, September 2001 [doi>10.1109/54.953269]
• 3: M. A. Gomaa, C. Scarbrough, T. N. Vijaykumar, and I. Pomeranz. Transient-fault recovery for chip multiprocessors. IEEE Micro, 23(6):76--83, Nov. 2003.
• 4: International Technology Roadmap for Semiconductors (ITRS), 2005 Edition. Process integration, devices, and structures. http://www.itrs.net/Links/2005ITRS/PIDS2005.pdf
• 5: Andrei Radulescu , Arjan J. C. van Gemund, Low-Cost Task Scheduling for Distributed-Memory Machines, IEEE Transactions on Parallel and Distributed Systems, v.13 n.6, p.648-658, June 2002 [doi>10.1109/TPDS.2002.1011417]
• 6: Karsten Albers , Frank Slomka, Efficient Feasibility Analysis for Real-Time Systems with EDF Scheduling, Proceedings of the conference on Design, Automation and Test in Europe, p.492-497, March 07-11, 2005 [doi>10.1109/DATE.2005.128]
• 7: Youngchul Cho , Sungjoo Yoo , Kiyoung Choi , Nacer-Eddine Zergainoh , Ahmed Amine Jerraya, Scheduler implementation in MP SoC design, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120793]
• 8: Chun Gong , Rami Melhem , Rajiv Gupta, Loop Transformations for Fault Detection in Regular Loops on Massively Parallel Systems, IEEE Transactions on Parallel and Distributed Systems, v.7 n.12, p.1238-1249, December 1996 [doi>10.1109/71.553273]
• 9: M. Chean , J. A. B. Fortes, The Full-Use-of-Suitable-Spares (FUSS) Approach to Hardware Reconfiguration for Fault-Tolerant Processor Arrays, IEEE Transactions on Computers, v.39 n.4, p.564-571, April 1990 [doi>10.1109/12.54851]
• 10: S. Chabridon , E. Gelenbe, Failure detection algorithms for a reliable execution of parallel programs, Proceedings of the 14TH Symposium on Reliable Distributed Systems, p.229, September 13-15, 1995
• 11: Parthasarathy Ranganathan , Sarita Adve , Norman P. Jouppi, Performance of image and video processing with general-purpose processors and media ISA extensions, Proceedings of the 26th annual international symposium on Computer architecture, p.124-135, May 01-04, 1999, Atlanta, Georgia, United States
• 12: C. Panis, U. Hirnschrott, A. Krall, G. Laure, W. Lazian, and J. Nurmi. FSEL -- selective predicated execution for a configurable DSP core. In Proc. ISVLSI'04, pages 317--320, Feb. 2004.
• 13: D. F. Zucker, R. B. Lee, and M. J. Flynn. Hardware and software cache prefetching techniques for MPEG benchmarks. IEEE Trans on Circuits and Systems for Video Technology, 10(5):782--796, Aug. 2000.
• 14: Kelvin K. Yue , David J. Lilja, An Effective Processor Allocation Strategy for Multiprogrammed Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.8 n.12, p.1246-1258, December 1997 [doi>10.1109/71.640017]
• 15: Yu-Kwong Kwok , Ishfaq Ahmad, Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.506-521, May 1996 [doi>10.1109/71.503776]
• 16: (R) FAST: A Low-Complexity Algorithm for Efficient Scheduling of DAGs on Parallel Processors, Proceedings of the Proceedings of the 1996 International Conference on Parallel Processing, p.150, August 12-16, 1996
• 17: Robert P. Dick , David L. Rhodes , Wayne Wolf, TGFF: task graphs for free, Proceedings of the 6th international workshop on Hardware/software codesign, p.97-101, March 15-18, 1998, Seattle, Washington, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

General Terms:
Reliability

Keywords:
adaptive execution, multiprocessor task schedulihng, reconfiguration