research-article

ILP-based scheduling for malleable fork-join tasks

Authors:

Ittetsu Taniguchi,

Hiroyuki TomiyamaAuthors Info & Claims

ACM SIGBED Review, Volume 16, Issue 3

Pages 21 - 26

https://doi.org/10.1145/3373400.3373403

Published: 25 November 2019 Publication History

Abstract

This paper studies scheduling of malleable fork-join tasks. In our scheduling problem, each task can be partitioned into multiple sub-tasks, and the sub-tasks are scheduled independently. The optimal number of sub-tasks is determined during scheduling simultaneously. This paper formulates the scheduling problem as an integer linear programming problem.

References

[1]

H. Kasahara, S. Narita, "Practical multiprocessor scheduling algorithms for efficient parallel processing," IEEE Transactions on Computers, vol. C-33, pp. 1023--1029, 1984.

[2]

S. Fujita, "A branch-and-bound algorithm for solving the multiprocessor scheduling problem with improved lower bounding techniques," IEEE Transaction on Computers, vol. 60, pp. 1006--1016, 2010.

Digital Library

[3]

A.Z.S. Shahul, O. Sinnen, "Optimal scheduling of task graphs on parallel systems," International Conference on Parallel and Distributed Computing, Applications and Technologies, 2008.

[4]

Y.K. Kwok, I. Ahmad, "Static scheduling algorithms for allocating directed task graphs to multiprocessors," ACM Computing Surveys, vol. 31, pp. 406--471, 1999.

Digital Library

[5]

J.J. Hwang, Y.C. Chow, F.D. Anger, C.Y. Lee, "Scheduling precedence graph in systems with interprocessor communication times," SIAM Journal of Computing, vol. 18, pp. 244--257, 1989.

Digital Library

[6]

G.C. Sih, E.A. Lee, "Compile time scheduling heuristic for interconnection constrained heterogeneous processor architecture," IEEE Transactions on Parallel and Distributed Systems, vol. 4, pp. 175--187, 1993.

Digital Library

[7]

T. Hagras, J. Janecek, "A high performance, low complexity algorithm for compile-time job scheduling in homogeneous computing environment," International Conference on Parallel Processing Workshops, 2003.

[8]

A. Palmer and O. Sinnen, "Scheduling algorithm based on force directed clustering," International Conference Parallel and Distributed Computing, Applications and Technologies, pp. 311--318, 2008.

[9]

M. Drozdowski, "Scheduling multiprocessor tasks: An overview," European Journal of Operational Research, vol. 94, 1996.

[10]

Y. Liu, L. Meng, I. Taniguchi and H. Tomiyama, "Novel list scheduling strategies for data parallelism task graphs," International Journal on Networking and Computing, vol. 4, no. 2, 2014.

[11]

J. Turek, J.L. Wolf, and P.S. Yu, "Approximate algorithms scheduling parallelizable tasks," Annual ACM Symposium on Parallel Algorithms and Architectures, 1992.

[12]

H. Yang and S. Ha, "ILP based data parallel multi-task mapping/scheduling technique for MPSoC," International SoC Design Conference, 2008.

[13]

C. Chen and C. Chu, "A 3.42-approximation algorithm for scheduling malleable tasks under precedence constraints", IEEE Transactions on Parallel and Distributed Systems, vol. 24, no. 8, 2013.

[14]

K. Shimada, S. Kitano, I. Taniguchi, and H. Tomiyama, "ILP-based scheduling for parallelizable tasks," IEICE Transactions on Fundamentals, vol. E100-A, no. 7, 2017.

[15]

J. Kim, H. Kim, K. Lakshmanan, R. Rajkumar, "Parallel scheduling for cyber-physical systems: Analysis and case study on a self-driving car," International Conference on Cyber-Physical System, 2013.

[16]

R.P. Dick, D.L. Rhodes, W.H. Wolf, "TGFF: Task graph for free," International Workshop on Hardwere/Software Codesign, 1998.

[17]

IBM CPLEX Optimize, http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/ (Last accessed : July 16, 2017)

Cited By

NISHIKAWA HSHIMADA KTANIGUCHI ITOMIYAMA H(2022)Simultaneous Scheduling and Core-Type Optimization for Moldable Fork-Join Tasks on Heterogeneous MulticoresIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2021VLP0003E105.A:3(540-548)Online publication date: 1-Mar-2022
https://doi.org/10.1587/transfun.2021VLP0003
Gao YPoon S(2021)A Genetic Algorithm for Scheduling Splittable Tasks with Precedence Constraints2021 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC45853.2021.9504867(1808-1816)Online publication date: 28-Jun-2021
https://dl.acm.org/doi/10.1109/CEC45853.2021.9504867
Shimada KTaniguchi ITomiyama H(2019)Communication-Aware Scheduling of Data-Parallel Tasks on Multicore ArchitecturesIPSJ Transactions on System LSI Design Methodology10.2197/ipsjtsldm.12.6512(65-73)Online publication date: 2019
https://doi.org/10.2197/ipsjtsldm.12.65

Index Terms

ILP-based scheduling for malleable fork-join tasks
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Index terms have been assigned to the content through auto-classification.

Recommendations

Scheduling of moldable fork-join tasks with inter- and intra-task communications
SCOPES '20: Proceedings of the 23th International Workshop on Software and Compilers for Embedded Systems

This paper proposes scheduling techniques for moldable fork-join tasks on multicore architecture. The proposed techniques decide the number of cores and execution start time for each task during scheduling and mapping, with taking into account inter- and ...
Communication-aware scheduling of data-parallel tasks: work-in-progress
CASES '18: Proceedings of the International Conference on Compilers, Architecture and Synthesis for Embedded Systems

This paper studies scheduling of data-parallel tasks on multicore architectures. Unlike traditional task scheduling, this work allows individual tasks to run on multiple cores in a data-parallel fashion. Our scheduling method finds shortest schedules ...
Algorithms for scheduling malleable and nonmalleable parallel tasks

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGBED Review

ACM SIGBED Review Volume 16, Issue 3

Special Issue on Embedded Operating Systems Workshops (EWiLi'17 and EWiLi'18)

October 2019

73 pages

EISSN:1551-3688

DOI:10.1145/3373400

Editors:
Heechul Yun
University of Kansas
,
Sophie Quinton
INRIA Grenoble - Rhone-Alpes, France
,
Edoardo Patti
Politecnico di Torino, Italy
,
Laurent Pautet
Telecom ParisTech, France
,
John Kubiatowicz
University of California Berkeley
,
Giuseppe Lipari
University Lille, France

Issue’s Table of Contents

Copyright © 2019 Copyright is held by the owner/author(s).

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 November 2019

Published in SIGBED Volume 16, Issue 3

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
94
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)7

Reflects downloads up to 28 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

NISHIKAWA HSHIMADA KTANIGUCHI ITOMIYAMA H(2022)Simultaneous Scheduling and Core-Type Optimization for Moldable Fork-Join Tasks on Heterogeneous MulticoresIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.2021VLP0003E105.A:3(540-548)Online publication date: 1-Mar-2022
https://doi.org/10.1587/transfun.2021VLP0003
Gao YPoon S(2021)A Genetic Algorithm for Scheduling Splittable Tasks with Precedence Constraints2021 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC45853.2021.9504867(1808-1816)Online publication date: 28-Jun-2021
https://dl.acm.org/doi/10.1109/CEC45853.2021.9504867
Shimada KTaniguchi ITomiyama H(2019)Communication-Aware Scheduling of Data-Parallel Tasks on Multicore ArchitecturesIPSJ Transactions on System LSI Design Methodology10.2197/ipsjtsldm.12.6512(65-73)Online publication date: 2019
https://doi.org/10.2197/ipsjtsldm.12.65

View Options

Get Access

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 Issue’s Table of Contents