The DOI matches its Crossref record; 8 of the 8 references it cites were found in a registry or an index.
Performance-effective and low-complexity task scheduling for heterogeneous computing
Open accessAbstract
Efficient application scheduling is critical for achieving high performance in heterogeneous computing environments. The application scheduling problem has been shown to be NP-complete in general cases as well as in several restricted cases. Because of its key importance, this problem has been extensively studied and various algorithms have been proposed in the literature which are mainly for systems with homogeneous processors. Although there are a few algorithms in the literature for heterogeneous processors, they usually require significantly high scheduling costs and they may not deliver good quality schedules with lower costs. In this paper, we present two novel scheduling algorithms for a bounded number of heterogeneous processors with an objective to simultaneously meet high performance and fast scheduling time, which are called the Heterogeneous Earliest-Finish-Time (HEFT) algorithm and the Critical-Path-on-a-Processor (CPOP) algorithm. The HEFT algorithm selects the task with the highest upward rank value at each step and assigns the selected task to the processor, which minimizes its earliest finish time with an insertion-based approach. On the other hand, the CPOP algorithm uses the summation of upward and downward rank values for prioritizing tasks. Another difference is in the processor selection phase, which schedules the critical tasks onto the processor that minimizes the total execution time of the critical tasks. In order to provide a robust and unbiased comparison with the related work, a parametric graph generator was designed to generate weighted directed acyclic graphs with various characteristics. The comparison study, based on both randomly generated graphs and the graphs of some real applications, shows that our scheduling algorithms significantly surpass previous approaches in terms of both quality and cost of schedules, which are mainly presented with schedule length ratio, speedup, frequency of best results, and average scheduling time metrics.
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
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
NP-complete scheduling problems
Ullman, J. D. (1975) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(75)80008-0 · Cited by 1,452
Kwok, Y.-K., & Ahmad, I. (1996) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/71.503776 · Cited by 812
A genetic algorithm for multiprocessor scheduling
Hou, E. S. H., Ansari, N., & Ren, H. (1994) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/71.265940 · Cited by 683
Wang, L., Siegel, H. J., Roychowdhury, V. P., & Maciejewski, A. A. (1997) · Journal of Parallel and Distributed Computing · doi:10.1006/jpdc.1997.1392 · Cited by 407
Braun, T. D., Siegal, H. J., Beck, N. B., Bölöni, L. L., Maheswaran, M., Reuther, A., Robertson, J. P., Theys, M. D., Yao, B., Hensgen, D. A., et al. (2003) · Heterogeneous Computing Workshop (HCW) · doi:10.1109/hcw.1999.765093 · Cited by 241
A dynamic matching and scheduling algorithm for heterogeneous computing systems
Maheswaran, M., & Siegel, H. J. (2002) · Heterogeneous Computing Workshop (HCW) · doi:10.1109/hcw.1998.666545 · Cited by 185
Cited by
StarPU: a unified platform for task scheduling on heterogeneous multicore architectures
Augonnet, C., Thibault, S., Namyst, R., & Wacrenier, P. (2011) · Concurrency and Computation: Practice and Experience · doi:10.1002/cpe.1631 · Cited by 1,275
Pegasus, a workflow management system for science automation
Deelman, E., Vahi, K., Juve, G., Rynge, M., Callaghan, S., Maechling, P. J., Mayani, R., Chen, W., Ferreira da Silva, R., Livny, M., et al. (2015) · Future Generation Computer Systems · doi:10.1016/j.future.2014.10.008 · Cited by 861
Workflows and e-Science: An overview of workflow system features and capabilities
Deelman, E., Gannon, D., Shields, M., & Taylor, I. (2009) · Future Generation Computer Systems · doi:10.1016/j.future.2008.06.012 · Cited by 831
List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table
Arabnejad, H., & Barbosa, J. G. (2014) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2013.57 · Cited by 653
Marwedel, P. (2021) · Embedded Systems · doi:10.1007/978-3-030-60910-8 · Cited by 605
Metadata
- Authors
- Topcuoglu, H., Hariri, S., & Wu, M.-Y.
- Venue
- IEEE Transactions on Parallel and Distributed Systems
- Published
- 2002-03
- Volume
- 13
- Issue
- 3
- Pages
- 260-274
- ISSN
- 1045-9219 (ISSN-L)
- OpenAlex
- W2149294210
- Cited by
- 3,475
- References
- 8
- FWCI
- 29.54
- Type
- journal article
- Language
- en
- Open access
- green
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.