Task concurrency management methodology to schedule the MPEG4 IM1 player on a highly parallel processor platform

ABSTRACT

This paper addresses the concurrent task management of complex multi-media systems, like the MPEG4 IM1 player, with emphasis on how to derive energy-cost vs time-budget curves through task scheduling on a multi-processor platform. Starting from the original “standard” specification, we extract the concurrency originally hidden by implementation decisions in a “grey-box” model. Then we have applied two high-level transformations on this model to improve the task-level concurrency. Finally, by scheduling the transformed task-graph, we have derived energy-cost vs time-budget curves. These curves will be used to get globally optimized design decisions when combining subsystems into one complete system or to be used by a dynamic scheduler. The results on the MPEG4 IM1 player confirm the validity of our assumptions and the usefulness of our approach.

REFERENCES

• 1: Filip Thoen , Francky Catthoor, Modeling, Verification, and Exploration of Task-Level Concurrency of Real-Time Embedded Systems, Kluwer Academic Publishers, Norwell, MA, 2000
• 2: Aggeliki Prayati , Chun Wong , Paul Marchal , Francky Catthoor , Hugo de Man , Nathalie Cossement , Rudy Lauwereins , Diederik Verkest , Alexis Birbas, Task Concurrency Management Experiment for Power-Efficient Speed-Up of Embedded MPEG4 IM1 Player, Proceedings of the 2000 International Workshop on Parallel Processing, p.453, August 21-24, 2000
• 3: P. Maw.hal, C. Wong, A. Prayati et di, "Impact of task-level concurrency transformations on the MPEG4 IM 1 player for weakly parallel processor platforms", International Conference on Parallel Architectures and Compilation Techniques 2000, Philadelphia, October 2000.
• 4: ftp://ftp.ics.ele.tue.ni/pub'Ip_ solve
• 5: Peng Yang , Dirk Desmet , Francky Catthoor , Diederik Verkest, Dynamic scheduling of concurrent tasks with cost performance trade-off, Proceedings of the 2000 international conference on Compilers, architecture, and synthesis for embedded systems, p.103-109, November 17-19, 2000, San Jose, California, United States [doi>10.1145/354880.354895]
• 6: L. Sha , R. Rajkumar , J. P. Lehoczky, Priority Inheritance Protocols: An Approach to Real-Time Synchronization, IEEE Transactions on Computers, v.39 n.9, p.1175-1185, September 1990 [doi>10.1109/12.57058]
• 7: K. Ramamritham and J. A. Stankvic, "Scheduling Algorithms and Operation Systems Support for Real-Time Systems" Proceedings of the IEEE, 82(1), Jan. 1994, pp. 55-67.
• 8: Neil C. Audsley , Alan Burns , Robert I. Davis , Ken W. Tindell , Andy J. Wellings, Fixed priority pre-emptive scheduling: an historical perspective, Real-Time Systems, v.8 n.2-3, p.173-198, March/May 1995 [doi>10.1007/BF01094342]
• 9: Thomas Benner , Rolf Ernst, An Approach to Mixed Systems Co-Synthesis, Proceedings of the 5th International Workshop on Hardware/Software Co-Design, p.9, March 24-26, 1997
• 10: Felice Balarin , Massimiliano Chiodo , Paolo Giusto , Harry Hsieh , Attila Jurecska , Luciano Lavagno , Claudio Passerone , Alberto Sangiovanni-Vincentelli , Ellen Sentovich , Kei Suzuki , Bassam Tabbara, Hardware-software co-design of embedded systems: the POLIS approach, Kluwer Academic Publishers, Norwell, MA, 1997
• 11: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 12: J. T. Leung and J. Whitehead, "On the Complexity of Fixed-Priority Scheduling of Periodic Real-time Tasks" Performance Evaluation, 2, 1982, pp. 237-250.
• 13: H. Chetto , M. Silly , T. Bouchentouf, Dynamic scheduling of real-time tasks under precedence constraints, Real-Time Systems, v.2 n.3, p.181-194, Sep. 1990 [doi>10.1007/BF00365326]
• 14: B. Sprunt, L. Sha, and J. Lchnczky, "Aperiodic Task Scheduling for Hard-Real-Time Systems", Real-7"we Systems, 1, 1989, pp. 27-60.
• 15: L P. Lehnezky, L. Sha, and J. K. Strosuider, "Enhanced Aperiodic Responsiveness in Hard Real-Tune Environments", In Proceedings of the IEEE Real.Time System Symposium, 1987, pp. 261-270.
• 16: S. Ramos-Thuel and L P. Lehnezky. ''On-Line Scheduling of Hard Deadline Aperiodic Tasks in Fixed-Priority Systems", In Proceedings of the IEEE Real.Time System Symposium, 1993, pp. 160--171.
• 17: M. Spuri and G. C. Buttazzo, "Efficient Aperiodic Service under Earliest Deadline Scheduling", In Proceedings of the IEEE Real- 71me System Symposiur 1994, pp. 2-11.
• 18: M. Spud and G. C. Buttazzn" "Scheduling Aperiodic Tasks in Dynamic Priority Systems", Real-lime Systems, 10(2), 1996.
• 19: T. P. Baker, Stack-based scheduling for realtime processes, Real-Time Systems, v.3 n.1, p.67-99, March 1991 [doi>10.1007/BF00365393]
• 20: Hesham El-Rewini , Hesham H. Ali , Ted Lewis, Task Scheduling in Multiprocessing Systems, Computer, v.28 n.12, p.27-37, December 1995 [doi>10.1109/2.476197]
• 21: Chao-Ju Hou , Kang G. Shin, Allocation of Periodic Task Modules with Precedence and Deadline Constraints in Distributed Real-Time Systems, IEEE Transactions on Computers, v.46 n.12, p.1338-1356, December 1997 [doi>10.1109/12.641934]
• 22: P. D. Hoang and J. M. Rabaey, "Scheduling of DSP Programs onto Multiprocessors for Maximum Throughput", IEEE Transactions on Signal Processing, 41(6), June 1993, pp. 2225-2235.
• 23: Karsten Strehl , Lothar Thiele , Dirk Ziegenbein , Rolf Ernst , Jürgen Teich, Scheduling hardware/software systems using symbolic techniques, Proceedings of the seventh international workshop on Hardware/software codesign, p.173-177, March 1999, Rome, Italy [doi>10.1145/301177.301523]
• 24: Ti-Yen Yen , Wayne Wolf, Sensitivity-driven co-synthesis of distributed embedded systems, Proceedings of the 8th international symposium on System synthesis, p.4-9, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224488]
• 25: Ti-Yen Yen , Wayne Wolf, Communication synthesis for distributed embedded systems, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.288-294, November 05-09, 1995, San Jose, California, United States
• 26: F. Gmlan and K. Kuchcinsld, "Low-Energy Directed Architecture Selection and Task Scheduling", In EUROMICRO'99, 1999, pp. 296-302.
• 27: A. Chandrakasan , V. Gutnik , T. Xanthopoulos, Data driven signal processing: an approach for energy efficient computing, Proceedings of the 1996 international symposium on Low power electronics and design, p.347-352, August 12-14, 1996, Monterey, California, United States
• 28: Inki Hong , Miodrag Potkonjak , Mani B. Srivastava, On-line scheduling of hard real-time tasks on variable voltage processor, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.653-656, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289105]
• 29: Takanori Okuma , Tohru Ishihara , Hiroto Yasuura, Real-Time Task Scheduling for a Variable Voltage Processor, Proceedings of the 12th international symposium on System synthesis, p.24, November 01-04, 1999
• 30: Bharat P. Dave , Ganesh Lakshminarayana , Niraj K. Jha, COSYN: hardware-software co-synthesis of embedded systems, Proceedings of the 34th annual conference on Design automation, p.703-708, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266341]
• 31: B. P. Dave , N. K. Jha, CASPER: concurrent hardware-software co-synthesis of hard real-time aperiodic and periodic specifications of embedded system architectures, Proceedings of the conference on Design, automation and test in Europe, p.118-124, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 32: Jiong Luo , Niraj K. Jha, Power-conscious joint scheduling of periodic task graphs and aperiodic tasks in distributed real-time embedded systems, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 33: N. Cossemeot, R. Lauwereins, and E Catthoor, "DF*: An extension of synchronous dutalinw with data dependency and non-determinism", accepted for Forum on Design Languages (FDL), Tuebingen, Germany, Sep. 2000.
• 34: http://developer.intel.com/design/strong/datashts/
• 35: L. Nachtergaele , B. Vanhoof , M. Peón , G. Lafruit , J. Bormans , I. Bolsens, Implementation of a scalable MPEG-4 wavelet-based visual texture compression system, Proceedings of the 36th ACM/IEEE conference on Design automation, p.333-336, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309948]
• 36: C. Wong F. Thnen, E Catthoor, and D. Verkest, "A slack-bused static task scheduling heuristic for embedded systems", accepted by Journal of Systems Architectures

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Design, Experimentation, Management, Theory

Keywords:
MPEG-4, concurrency, cost-efficiency, embedded system, scheduling