More Web Proxy on the site http://driver.im/

research-article

Scheduling task dependence graphs with variable task execution times onto heterogeneous multiprocessors

Authors:

Nadathur R. Satish,

Kaushik Ravindran,

Kurt KeutzerAuthors Info & Claims

EMSOFT '08: Proceedings of the 8th ACM international conference on Embedded software

Pages 149 - 158

https://doi.org/10.1145/1450058.1450079

Published: 19 October 2008 Publication History

Abstract

We present a statistical optimization approach for scheduling a task dependence graph with variable task execution times onto a heterogeneous multiprocessor system. Scheduling methods in the presence of variations typically rely on worst-case timing estimates for hard real-time applications, or average-case analysis for other applications. However, a large class of soft real-time applications require only statistical guarantees on latency and throughput. We present a general statistical model that captures the probability distributions of task execution times as well as the correlations of execution times of different tasks. We use a Monte Carlo based technique to perform makespan analysis of different schedules based on this model. This approach can be used to analyze the variability present in a variety of soft real-time applications, including a H.264 video processing application.

We present two scheduling algorithms based on statistical makespan analysis. The first is a heuristic based on a critical path analysis of the task dependence graph. The other is a simulated annealing algorithm using incremental timing analysis. Both algorithms take as input the required statistical guarantee, and can thus be easily re-used for different required guarantees. We show that optimization methods based on statistical analysis show a 25-30% improvement in makespan over methods based on static worst-case analysis.

References

[1]

J. C. Beck and N. Wilson. Proactive Algorithms for Job Shop Scheduling with Probabilistic Durations. Journal of Artificial Intelligence Research, 28:183--232, 2007.

Digital Library

[2]

G. C. Buttazzo. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. Kluwer, 1997.

Digital Library

[3]

C. Chekuri. Approximation Algorithms for Scheduling Problems. PhD thesis, Computer Science Department, Stanford University, Aug 1998. CS-TR-98-1611.

Digital Library

[4]

W. Y. Chen, S. A. Mahlke, N. J. Warter, S. Anik, and W. mei W. Hwu. Profile-assisted instruction scheduling. Int. J. Parallel Program., 22(2):151--181, 1994.

Digital Library

[5]

J. Chong, N. R. Satish, B. Catanzaro, K. Ravindran, and K. Keutzer. Efficient Parallelization of H.264 Decoding with Macro Block Level Scheduling. In 2007 Intl. Conference on Multimedia and Expo, pages 1874--1877, July 2007.

[6]

T. Davidović and T. G. Crainic. Benchmark-Problem Instances for Static Scheduling of Task Graphs with Communication Delays on Homogeneous Multiprocessor Systems. Computers and OR, 33:2155--2177, 2006.

Digital Library

[7]

M. Drake, W. Thies, and S. Amarasinghe. MPEG Coding in StreamIt. http://www.cag.csail.mit.edu/streamit/mpeg/.

[8]

C. V. et al. First-Order Incremental Block-Based Statistical Timing Analysis. IEEE Trans. on Computer-Aided Design, 25(10):2170--2180, October 2006.

Digital Library

[9]

M. R. Garey and D. S. Johnson. Computers and Intractability: A guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.

Digital Library

[10]

H. Gautama and A. J. C. van Gemund. Static Performance prediction of data-dependent programs. In 2nd Intl. Work. on Software and Performance, pages 216--226, Sep 2000.

Digital Library

[11]

M. Gries. Methods for Evaluating and Covering the Design Space during Early Design Development. Integr. VLSI J., 38(2):131--183, 2004.

Digital Library

[12]

T. Hu. Parallel Sequencing and Assembly Line Problems. Oper. Res., 19(6):841--848, Nov 1961.

Digital Library

[13]

H. Kasahara and S. Narita. Practical Multiprocessor Scheduling Algorithms for Efficient Parallel Processing. IEEE Trans. on Computers, C-33(11), Nov 1984.

Digital Library

[14]

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by Simulated Annealing. Science, 220(4598):498--516, May 1983.

[15]

P. Koch. Strategies for Realistic and Efficient Static Scheduling of Data Ind. Algorithms onto Multiple Digital Signal Processors. PhD thesis, Aalborg University, 1995.

[16]

Y.-K. Kwok and I. Ahmad. Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors. ACM Comput. Surv., 31(4):406--471, 1999.

Digital Library

[17]

E. A. Lee and D. G. Messerschmitt. Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing. IEEE Trans. Comput., 36(1):24--35, 1987.

Digital Library

[18]

M. Mani and M. Orshansky. A New Statistical Optimization Algorithm for Gate Sizing. In Proc. of the IEEE Intl. Conf. on Comp. Design, pages 272--277, 2004.

Digital Library

[19]

S. Manolache, P. Eles, and Z. Peng. Real-Time Applications with Stochastic Task Execution Times Analysis and Optimisation. Springer Netherlands, 2007.

Digital Library

[20]

P. Moge and A. Kalavade. A Tool for Performance Estimation of Networked Embedded End-Systems. In DAC '98: 35th DAC conf., pages 257--262, 1998.

Digital Library

[21]

H. Orsila, T. Kangas, E. Salminen, and T. D. Hamalainen. Parameterizing Simulated Annealing for Distributing Task Graphs on Multiprocessor Socs. In Proc. of the Intl. Symposium on System-on-chip, pages 1--4, Nov 2006.

[22]

K. Ravindran. Task Allocation and Scheduling of Concurrent Applications to Multiprocessor Systems. PhD thesis, University of California, Berkeley, Nov 2007.

Digital Library

[23]

G. C. Sih and E. A. Lee. A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures. IEEE Trans. Parallel Distrib. Syst., 4(2):175--187, 1993.

Digital Library

[24]

A. Srivastava, D. Sylvester, and D. Blaauw. Statistical optimization of leakage power considering process variations using dual-Vth and sizing. In DAC '04: Proc. of the 41st conf. on Design automation, pages 773--778, 2004.

Digital Library

[25]

L. Thiele. Resource Constrained Scheduling of Uniform Algorithms. VLSI Signal Proc., 10(3):295--310, Aug 1995.

Digital Library

[26]

A. J. C. van Gemund. Performance Modeling of Parallel Systems. PhD thesis, Delft University of Technology, 1996.

Cited By

Jang JYang H(2023)A Runtime Switchable Multi-Phase Convolutional Neural Network for Resource-Constrained SystemsIEEE Access10.1109/ACCESS.2023.328799811(62449-62461)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3287998
Mandal SSarkar SMing WChattopadhyay AChakrabarti A(2019)Criticality Aware Soft Error Mitigation in the Configuration Memory of SRAM Based FPGA2019 32nd International Conference on VLSI Design and 2019 18th International Conference on Embedded Systems (VLSID)10.1109/VLSID.2019.00063(257-262)Online publication date: Jan-2019
https://doi.org/10.1109/VLSID.2019.00063
Jung HYang H(2019)Efficiently Switchable Context-Aware Dataflow Adaptation Technique for Low-Power Multi-Core Embedded SystemsIEEE Access10.1109/ACCESS.2019.29580457(177974-177987)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2958045
Show More Cited By

Index Terms

Scheduling task dependence graphs with variable task execution times onto heterogeneous multiprocessors

Recommendations

Mixed-Criticality Scheduling on Multiprocessors Using Task Grouping
ECRTS '15: Proceedings of the 2015 27th Euromicro Conference on Real-Time Systems

Real-time systems are increasingly running a mix of tasks with different criticality levels: for instance, unmanned aerial vehicle has multiple software functions with different safety criticality levels, but runs them on a single, shared computational ...
A unified analysis of global EDF and fixed-task-priority schedulability of sporadic task systems on multiprocessors

Fixed-task-priority (FTP) scheduling and earliest-deadline-first (EDF) scheduling policies are alike in fixing the priority of each job of a task at the time the job is released. This common feature of FTP and EDF scheduling permits a unified analysis ...
Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors

The scheduling of systems of periodic tasks upon multiprocessor platforms is considered. Utilization-based conditions are derived for determining whether a periodic task system meets all deadlines when scheduled using the earliest deadline first ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EMSOFT '08: Proceedings of the 8th ACM international conference on Embedded software

October 2008

284 pages

ISBN:9781605584683

DOI:10.1145/1450058

Program Chairs:
Luca de Alfaro
University of California, Santa Cruz
,
Jens Palsberg
University of California, Los Angeles

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 October 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ESWEEK 08

Sponsor:

ESWEEK 08: Fourth Embedded Systems Week

October 19 - 24, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 60 of 203 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
654
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jang JYang H(2023)A Runtime Switchable Multi-Phase Convolutional Neural Network for Resource-Constrained SystemsIEEE Access10.1109/ACCESS.2023.328799811(62449-62461)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3287998
Mandal SSarkar SMing WChattopadhyay AChakrabarti A(2019)Criticality Aware Soft Error Mitigation in the Configuration Memory of SRAM Based FPGA2019 32nd International Conference on VLSI Design and 2019 18th International Conference on Embedded Systems (VLSID)10.1109/VLSID.2019.00063(257-262)Online publication date: Jan-2019
https://doi.org/10.1109/VLSID.2019.00063
Jung HYang H(2019)Efficiently Switchable Context-Aware Dataflow Adaptation Technique for Low-Power Multi-Core Embedded SystemsIEEE Access10.1109/ACCESS.2019.29580457(177974-177987)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2958045
Jung HYang H(2018)Context-aware dataflow adaptation technique for low-power multi-core embedded systemsProceedings of the 55th Annual Design Automation Conference10.1145/3195970.3196015(1-6)Online publication date: 24-Jun-2018
https://dl.acm.org/doi/10.1145/3195970.3196015
Jung HYang H(2018)Context-Aware Dataflow Adaptation Technique for Low-Power Multi-Core Embedded Systems2018 55th ACM/ESDA/IEEE Design Automation Conference (DAC)10.1109/DAC.2018.8465771(1-6)Online publication date: Jun-2018
https://doi.org/10.1109/DAC.2018.8465771
Nogueira BMaciel PTavares ESilva RAndrade E(2017)Multi-objective optimization of multimedia embedded systems using genetic algorithms and stochastic simulationSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-016-2061-x21:14(4141-4158)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s00500-016-2061-x
Majumder ASaha SChakrabarti A(2017)Task Allocation Strategies for FPGA Based Heterogeneous System on ChipComputer Information Systems and Industrial Management10.1007/978-3-319-59105-6_29(341-353)Online publication date: 17-May-2017
https://doi.org/10.1007/978-3-319-59105-6_29
Alsheikhy AAmmar RElfouly RAlharthi MAlshegaifi A(2016)An efficient dynamic scheduling algorithm for periodic tasks in real-time systems using dynamic average estimation2016 IEEE Symposium on Computers and Communication (ISCC)10.1109/ISCC.2016.7543830(773-777)Online publication date: Jun-2016
https://doi.org/10.1109/ISCC.2016.7543830
Kim HYang H(2016)An Online Self-Adaptive System Management Technique for Multi-Core SystemsProcedia Computer Science10.1016/j.procs.2016.04.20483(417-424)Online publication date: 2016
https://doi.org/10.1016/j.procs.2016.04.204
Lattuada MPilato CFerrandi F(2016)Performance Estimation of Task Graphs Based on Path ProfilingInternational Journal of Parallel Programming10.1007/s10766-015-0372-744:4(735-771)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1007/s10766-015-0372-7
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents