The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors
Abstract
In this paper, we propose a static scheduling algorithm for allocating task graphs to fully connected multiprocessors. We discuss six recently reported scheduling algorithms and show that they possess one drawback or the other which can lead to poor performance. The proposed algorithm, which is called the Dynamic Critical-Path (DCP) scheduling algorithm, is different from the previously proposed algorithms in a number of ways. First, it determines the critical path of the task graph and selects the next node to be scheduled in a dynamic fashion. Second, it rearranges the schedule on each processor dynamically in the sense that the positions of the nodes in the partial schedules are not fixed until all nodes have been considered. Third, it selects a suitable processor for a node by looking ahead the potential start times of the remaining nodes on that processor, and schedules relatively less important nodes to the processors already in use. A global as well as a pair-wise comparison is carried out for all seven algorithms under various scheduling conditions. The DCP algorithm outperforms the previous algorithms by a considerable margin. Despite having a number of new features, the DCP algorithm has admissible time complexity, is economical in terms of the number of processors used and is suitable for a wide range of graph structures.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)70356-x · Cited by 5,854
Computer and job-shop scheduling theory
Coffman, E. G., & Bruno, J. L. (1976) · Medical Entomology and Zoology · Cited by 1,107
Parallel Sequencing and Assembly Line Problems
Hu, T. C. (1961) · Operations Research · doi:10.1287/opre.9.6.841 · Cited by 898
Using dual approximation algorithms for scheduling problems theoretical and practical results
Hochbaum, D. S., & Shmoys, D. B. (1987) · Journal of the ACM · doi:10.1145/7531.7535 · Cited by 790
Scheduling independent tasks to reduce mean finishing time
Bruno, J., Coffman, E. G., & Sethi, R. (1974) · Communications of the ACM · doi:10.1145/361011.361064 · Cited by 504
Introduction to parallel computing
Najarian, J. (1993) · Control Engineering Practice · doi:10.1016/0967-0661(93)90237-l · Cited by 330
Deterministic Processor Scheduling
Gonzalez, M. J. (1977) · ACM Computing Surveys · doi:10.1145/356698.356700 · Cited by 216
Scheduling Graphs on Two Processors
Sethi, R. (1976) · SIAM Journal on Computing · doi:10.1137/0205005 · Cited by 78
Using random task graphs to investigate the potential benefits of heterogeneity in parallel systems
Almeida, V. A. F., Vasconcelos, I., Árabe, J. N. C., & Menascé, D. A. (2003) · ACM/IEEE Conference on Supercomputing (SC) · doi:10.1109/superc.1992.236634 · Cited by 55
Cited by
Performance-effective and low-complexity task scheduling for heterogeneous computing
Topcuoglu, H., Hariri, S., & Wu, M.-Y. (2002) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/71.993206 · Cited by 3,475
Static scheduling algorithms for allocating directed task graphs to multiprocessors
Kwok, Y.-K., & Ahmad, I. (1999) · ACM Computing Surveys · doi:10.1145/344588.344618 · Cited by 1,314
Self-citationRemote sensing big data computing: Challenges and opportunities
Ma, Y., Wu, H., Wang, L., Huang, B., Ranjan, R., Zomaya, A., & Jie, W. (2015) · Future Generation Computer Systems · doi:10.1016/j.future.2014.10.029 · Cited by 676
AI Models for Green Communications Towards 6G
Mao, B., Tang, F., Kawamoto, Y., & Kato, N. (2022) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2021.3130901 · Cited by 300
Yan, J., Bi, S., Zhang, Y. J., & Tao, M. (2020) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2019.2943563 · Cited by 280
HCOC: a cost optimization algorithm for workflow scheduling in hybrid clouds
Bittencourt, L. F., & Madeira, E. R. M. (2011) · Journal of Internet Services and Applications · doi:10.1007/s13174-011-0032-0 · Cited by 268
Workflow scheduling in cloud: a survey
Wu, F., Wu, Q., & Tan, Y. (2015) · The Journal of Supercomputing · doi:10.1007/s11227-015-1438-4 · Cited by 260
A hybrid multi-objective Particle Swarm Optimization for scientific workflow scheduling
Verma, A., & Kaushal, S. (2017) · Parallel Computing · doi:10.1016/j.parco.2017.01.002 · Cited by 258
Adaptive online scheduling in storm
Aniello, L., Baldoni, R., & Querzoni, L. (2013) · Proceedings of the 7th ACM international conference on Distributed event-based systems · doi:10.1145/2488222.2488267 · Cited by 245
“2 is known to be NP-complete [9, 18].”
Metadata
- Authors
- Kwok, Y.-K., & Ahmad, I.
- Venue
- IEEE Transactions on Parallel and Distributed Systems
- Published
- 1996-05
- Volume
- 7
- Issue
- 5
- Pages
- 506-521
- ISSN
- 1045-9219 (ISSN-L)
- OpenAlex
- W2023753260
- Cited by
- 812
- References
- 11
- FWCI
- 27.42
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.