Probabilistic design of multimedia embedded systems

ABSTRACT

In this paper, we propose the novel concept of probabilistic design for multimedia embedded systems, which is motivated by the challenge of how to design, but not overdesign, such systems while systematically incorporating performance requirements of multimedia application, uncertainties in execution time, and tolerance for reasonable execution failures. Unlike most present techniques that are based on either worst- or average-case execution times of application tasks, where the former guarantees the completion of each execution, but often leads to overdesigned systems, and the latter fails to provide any completion guarantees, the proposed probabilistic design method takes advantage of unique features mentioned above of multimedia systems to relax the rigid hardware requirements for software implementation and avoid overdesigning the system. In essence, this relaxation expands the design space and we further develop an off-line on-line minimum effort algorithm for quick exploration of the enlarged design space at early design stages. This is the first step toward our goal of bridging the gap between real-time analysis and embedded software implementation for rapid and economic multimedia system design. It is our belief that the proposed method has great potential in reducing system resource while meeting performance requirements. The experimental results confirm this as we achieve significant saving in system's energy consumption to provide a statistical completion ratio guarantee (i.e., the expected number of completions over a large number of iterations is greater than a given value).

REFERENCES

• 1: Mayez A. Al-Mouhamed, Lower Bound on the Number of Processors and Time for Scheduling Precedence Graphs with Communication Costs, IEEE Transactions on Software Engineering, v.16 n.12, p.1390-1401, December 1990 [doi>10.1109/32.62447 ]
• 2: Bolot, J. and Vega-Garcia, A. 1996. Control mechanisms for packet audio in the internet. Proceedings of IEEE Infocom.
• 3: Burd, T. D., Pering, T., Stratakos, A., and Brodersen, R. 2000. A dynamic voltage-scaled microprocessor system. IEEE International Solid-State Circuits Conference. 294--295, 466.
• 4: K. S. Chatha , R. Vemuri, Performance Evaluation Tool for Rapid Prototyping of Hardware-Software Codesigns, Proceedings of the Ninth IEEE International Workshop on Rapid System Prototyping, p.218, June 03-05, 1998
• 5: Chunhong Chen , Majid Sarrafzadeh, Provably good algorithm for low power consumption with dual supply voltages, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.76-79, November 07-11, 1999, San Jose, California, United States
• 6: 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
• 7: H. -J. Eikerling , W. Hardt , J. Gerlach , W. Rosenstiel, A Methodology for Rapid Analysis and Optimization of Embedded Systems, Proceedings of the IEEE Symposium and Workshop on Engineering of Computer Based Systems, p.252, March 11-15, 1996
• 8: Rolf Ernst, Codesign of Embedded Systems: Status and Trends, IEEE Design & Test, v.15 n.2, p.45-54, April 1998 [doi>10.1109/54.679207 ]
• 9: Henkel, J. and Ernst, R. 1998. High-level estimation techniques for usage in hardware/software co-design. Asia and South Pacific Automation Conference (Feb.). 353--360.
• 10: Inki Hong , Darko Kirovski , Gang Qu , Miodrag Potkonjak , Mani B. Srivastava, Power optimization of variable voltage core-based systems, Proceedings of the 35th annual conference on Design automation, p.176-181, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277088]
• 11: 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]
• 12: Harry Hsieh , Felice Balarin , Luciano Lavagno , Alberto Sangiovanni-Vincentelli, Efficient methods for embedded system design space exploration, Proceedings of the 37th conference on Design automation, p.607-612, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337593]
• 13: Xiaobo Sharon Hu , Tao Zhou , Edwin H.-M. Sha, Estimating probabilistic timing performance for real-time embedded systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.6, p.833-844, 12/1/2001 [doi>10.1109/92.974897 ]
• 14: Shaoxiong Hua , Gang Qu, Approaching the Maximum Energy Saving on Embedded Systems with Multiple Voltages, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.26, November 09-13, 2003 [doi>10.1109/ICCAD.2003.34]
• 15: Tohru Ishihara , Hiroto Yasuura, Voltage scheduling problem for dynamically variable voltage processors, Proceedings of the 1998 international symposium on Low power electronics and design, p.197-202, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280894]
• 16: Johnson, M. C. and Roy, K. 1997. Scheduling and optimal voltage selection for low power multi-voltage dsp datapaths. In Proceedings of 1997 IEEE International Symposium on Circuits and Systems. 2152--2155.
• 17: Asawaree Kalavade , Pratyush Moghé, A tool for performance estimation of networked embedded end-systems, Proceedings of the 35th annual conference on Design automation, p.257-262, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277116]
• 18: Karam, M. J. and Tobagi, F. A. 2001. Analysis of the delay and jitter of voice traffic over the internet. Infocom.
• 19: Madsen, J., Grode, J., Knudsen, P. V., Petersen, M. E. and Haxthausen, A. E. 1997. LYCOS: The lyngby co-synthesis system. Journal for Design Automation of Embedded Systems 2, 2 (Mar.). 195--235.
• 20: Sharad Malik , Margaret Martonosi , Yau-Tsun Steven Li, Static timing analysis of embedded software, Proceedings of the 34th annual conference on Design automation, p.147-152, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266052]
• 21: Radu Marculescu , Amit Nandi , Luciano Lavagno , Alberto Sangiovanni-Vincentelli, System-level power/performance analysis of portable multimedia systems communicating over wireless channels, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 22: Carolyn McCreary , A. A. Khan , J. J. Thompson , M. E. McArdle, A Comparison of Heuristics for Scheduling DAGs on Multiprocessors, Proceedings of the 8th International Symposium on Parallel Processing, p.446-451, April 01, 1994
• 23: Gang Qu, What is the limit of energy saving by dynamic voltage scaling?, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 24: Gang Qu , Naoyuki Kawabe , Kimiyoshi Usami , Miodrag Potkonjak, Function-level power estimation methodology for microprocessors, Proceedings of the 37th conference on Design automation, p.810-813, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337786]
• 25: Gang Quan , Xiaobo Hu, Energy efficient fixed-priority scheduling for real-time systems on variable voltage processors, Proceedings of the 38th conference on Design automation, p.828-833, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379074]
• 26: Salil Raje , Majid Sarrafzadeh, Variable voltage scheduling, Proceedings of the 1995 international symposium on Low power design, p.9-14, April 23-26, 1995, Dana Point, California, United States [doi>10.1145/224081.224084]
• 27: Youngsoo Shin , Kiyoung Choi, Power conscious fixed priority scheduling for hard real-time systems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.134-139, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309901]
• 28: T.-S. Tia , Z. Deng , M. Shankar , M. Storch , J. Sun , L.-C. Wu , J. W.-S. Liu, Probabilistic performance guarantee for real-time tasks with varying computation times, Proceedings of the Real-Time Technology and Applications Symposium, p.164, May 15-17, 1995
• 29: M. Y. Wu , D. D. Gajski, Hypertool: A Programming Aid for Message-Passing Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.330-343, July 1990 [doi>10.1109/71.80160 ]
• 30: Peng Yang , Paul Marchal , Chun Wong , Stefaan Himpe , Francky Catthoor , Patrick David , Johan Vounckx , Rudy Lauwereins, Managing dynamic concurrent tasks in embedded real-time multimedia systems, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan [doi>10.1145/581199.581226]
• 31: T. Yang , A. Gerasoulis, DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.951-967, September 1994 [doi>10.1109/71.308533 ]
• 32: Wanghong Yuan , Klara Nahrstedt, Energy-efficient soft real-time CPU scheduling for mobile multimedia systems, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 33: Wanghong Yuan , Klara Nahrstedt, Practical voltage scaling for mobile multimedia devices, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027737]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Performance

Keywords:
Energy minimization, completion ratio, hardware/software codesign, multiple voltage, probabilistic design, soft real-time system