AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Journal of Computer Science and Technology Article
Article Link
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Regular Paper

Degree-of-Node Task Scheduling of Fine-Grained Parallel Programs on Heterogeneous Systems

School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, China
Show Author Information

Abstract

Processor specialization has become the development trend of modern processor industry. It is quite possible that this will still be the main-stream in the next decades of semiconductor era. As the diversity of heterogeneous systems grows, organizing computation efficiently on systems with multiple kinds of heterogeneous processors is a challenging problem and will be a normality. In this paper, we analyze some state-of-the-art task scheduling algorithms of heterogeneous computing systems and propose a Degree of Node First (DONF) algorithm for task scheduling of fine-grained parallel programs on heterogeneous systems. The major innovations of DONF include: 1) simplifying task priority calculation for directed acyclic graph (DAG) based fine-grained parallel programs which not only reduces the complexity of task selection but also enables the algorithm to solve the scheduling problem for dynamic DAGs; 2) building a novel communication model in the processor selection phase that makes the task scheduling much more efficient. They are achieved by exploring finegrained parallelism via a dataflow program execution model, and validated through experimental results with a selected set of benchmarks. The results on synthesized and real-world application DAGs show a very good performance. The proposed DONF algorithm significantly outperforms all the evaluated state-of-the-art heuristic algorithms in terms of scheduling length ratio (SLR) and efficiency.

Keywords

task schedulingheterogeneous systemperformanceparallel program

Electronic Supplementary Material

Download File(s)
jcst-34-5-1096-Highlights.pdf (273.3 KB)
jcst-34-5-1096_ESM.pdf (273.3 KB)

References

[1]
Suetterlein J. DARTS: A runtime based on the Codelet execution model [Master Thesis]. University of Delaware, 2014.
[2]

Qu P, Yan J, Zhang Y H, Gao G R. Parallel turing machine, a proposal. Journal of Computer Science and Technology, 2017, 32(2): 269-285.
Crossref Google Scholar
[3]

Valiant L G. A bridging model for parallel computation. Communications of the ACM, 1990, 33(8): 103-111.
Crossref Google Scholar
[4]
Zuckerman S, Suetterlein J, Knauerhase R, Gao G R. Using a “codelet” program execution model for exascale machines: Position paper. In Proc. the 1st International Workshop on Adaptive Self-Tuning Computing Systems for the Exaflop Era, June 2011, pp.64-69.
Crossref
[5]
Suettlerlein J, Zuckerman S, Gao G R. An implementation of the Codelet model. In Proc. the 19th Int. Conf. Parallel Processing, August 2013, pp.633-644.
Crossref
[6]

Ullman J D. NP-complete scheduling problems. Journal of Computer and System Sciences, 1975, 10(3): 384-393.
Crossref Google Scholar
[7]

Lenstra J K, Kan A H G R. Computational complexity of discrete optimization problems. Annals of Discrete Mathematics, 1979, 4: 121-140.
Crossref Google Scholar
[8]

Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness (1st edition). W.H. Freeman, 1979.
[9]

Arabnejad H, Barbosa J G. List scheduling algorithm for heterogeneous systems by an optimistic cost table. IEEE Trans. Parallel and Distributed Systems, 2014, 25(3): 682-694.
Crossref Google Scholar
[10]
Dennis J B, Fosseen J B, Linderman J P. Data flow schemas. In Proc. Int. Symp. Theoretical Programming, Aug. 1972, pp.187-216.
Crossref
[11]
Dennis J B. First version of a data flow procedure language. In Proc. Programming Symposium, April 1974, pp.362-376.
Crossref
[12]

Dennis J B. Data flow supercomputers. IEEE Computer, 1980, 13(11): 48-56.
Crossref Google Scholar
[13]

Arvind A, Gostelow K P, Plouffe W. Indeterminacy, monitors, and dataflow. ACM SIGOPS Operating Systems Review, 1977, 11(5): 159-169.
Crossref Google Scholar
[14]
Arvind A, Kathail V. A multiple processor data flow machine that supports generalized procedures. In Proc. the 8th Symp. Computer Architecture, May 1981, pp.291-302.
[15]

Watson I, Gurd J. A practical data flow computer. IEEE Computer, 1982, 15(2): 51-57.
Crossref Google Scholar
[16]
Hum H H J, Maquelin O, Theobald K B et al. A design study of the EARTH multiprocessor. In Proc. the IFIP WG10.3 Working Conf. Parallel Architectures and Compilation Techniques, June 1995, pp.59-68.
[17]
Farquhar W G, Evripidou P. DART: A data-driven processor architecture for real-time computing. In Proc. the IFIP WG10. 3. Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, January 1993, pp.141-152.
[18]
Evripidou P. Thread synchronization unit (TSU): A building block for high performance computers. In Proc. the 1997 Int. Symp. High Performance Computing, Nov. 1997, pp.107-118.
Crossref
[19]

Topcuouglu H, Hariri S, Wu M Y. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. Parallel Distrib. Syst., 2002, 13(3):260-274.
Crossref Google Scholar
[20]
Bittencourt L F, Sakellariou R, Madeira E R M. DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm. In Proc. the 18th Euromicro Int. Conf. Parallel, Distributed and Network-Based Processing, February 2010, pp.27-34.
Crossref
[21]
Munir E U, Mohsin S, Hussain A, Nisar M W, Ali S. SDBATS: A novel algorithm for task scheduling in heterogeneous computing systems. In Proc. the 27th Int. Symp. Parallel and Distributed Processing Symposium Workshops & PhD Forum, May 2013, pp.43-53.
Crossref
[22]

Wang G, Wang Y X, Liu H, Guo H. HSIP: A novel task scheduling algorithm for heterogeneous computing. Sci. Program., 2016, 2016: Article No. 3676149.
Crossref Google Scholar
[23]
Yelick K, Bonachea D, Chen W Y et al. Productivity and performance using partitioned global address space languages. In Proc. the 2007 International Workshop on Parallel Symbolic Computation, July 2007, pp.24-32.
Crossref
[24]
Murray D G, McSherry F, Isaacs R et al. Naiad: A timely dataflow system. In Proc. the 24th ACM SIGOPS Symp. Operating Systems Principles, Nov. 2013, pp.439-455.
Crossref
[25]

Daoud M I, Kharma N. A high performance algorithm for static task scheduling in heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing, 2008, 68(4): 399-409.
Crossref Google Scholar
[26]

Blumofe R D, Joerg C F, Kuszmaul B C et al. Cilk: An efficient multithreaded runtime system. Journal of Parallel and Distributed Computing, 1996, 37(1): 55-69.
Crossref Google Scholar
[27]
Blumofe R D, Frigo M, Joerg C F et al. DAG-consistent distributed shared memory. In Proc. the 10th International Parallel Processing Symposium, April 1996, pp.132-141.
[28]

Augonnet C, Thibault S, Namyst R, Wacrenier P A. StarPU: A unified platform for task scheduling on heterogeneous multicore architectures. Concurrency and Computation: Practice and Experience, 2011, 23(2): 187-198.
Crossref Google Scholar
[29]
Dongarra J, Heroux M A, Luszczek P. HPCG benchmark: A new metric for ranking high performance computing systems. Technical Report, Electrical Engineering and Computer Science Department, Knoxville, Tennessee, 2015. https://www.hpcg-benchmark.org/pubs/index.html, May 2019.
[30]
Su Z C, Chen J S, Lin H et al. A dataflow-based runtime support on a 100P actual system. In Proc. the 2017 IEEE Int. Symp. Parallel and Distributed Processing with Applications and the 2017 IEEE Int. Conf. Ubiquitous Computing and Communications, December 2017, pp.599-606.
Crossref
[31]
Simonyan K, Zisserman A. Very deep convolutional networks for large-scale image recognition. In Proc. the 3rd Int. Conf. Learning Representations, May 2015, Article No. 4.
[32]
Krizhevsky A, Sutskever I, Hinton G E. ImageNet classification with deep convolutional neural networks. In Proc. the 26th Annual Conference on Neural Information Processing Systems, December 2012, pp.1106-1114.
[33]
Sun Y, Liang D, Wang X G et al. DeepID3: Face recognition with very deep neural networks. arXiv: 1502.00873, 2015. https://arxiv.org/abs/1502.00873, May 2019.
[34]
Dai J F, He K M, Sun J. Convolutional feature masking for joint object and stuff segmentation. In Proc. the 2015 IEEE Conference on Computer Vision and Pattern Recognition, June 2015, pp.3992-4000.
Crossref
[35]
Long J, Shelhamer E, Darrell T. Fully convolutional networks for semantic segmentation. In Proc. the 2015 IEEE Conference on Computer Vision and Pattern Recognition, June 2015, pp.3431-3440.
Crossref
[36]
Ma C, Huang J B, Yang X K et al. Hierarchical convolutional features for visual tracking. In Proc. the 2015 IEEE Int. Conf. Computer Vision, December 2015, pp.3074-3082.
Crossref
Journal of Computer Science and Technology
Volume 34 Issue 5,
September 2019
Pages 1096-1108
DOI: 10.1007/s11390-019-1962-4
Cite this article:
Lin H, Li M-F, Jia C-F, et al. Degree-of-Node Task Scheduling of Fine-Grained Parallel Programs on Heterogeneous Systems. Journal of Computer Science and Technology, 2019, 34(5): 1096-1108. https://doi.org/10.1007/s11390-019-1962-4

363

Views

10

Crossref

N/A

Web of Science

11

Scopus

0

CSCD

Altmetrics
Received: 08 November 2018
Revised: 04 July 2019
Published: 06 September 2019
©2019 Springer Science + Business Media, LLC & Science Press, China
Return