Top

The Journal of Supercomputing

Published in:

19-04-2017

Dynamic DAG scheduling for many-task computing of distributed eco-hydrological model

Authors: Shasha Yue, Yan Ma, Lajiao Chen, Yuzhu Wang, Weijing Song

Published in: The Journal of Supercomputing | Issue 2/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The computing of distributed hydrological model at large scale is increasingly characterized by data intensive and computation intensive, especially for the multi-process coupling model. Parallel computing is one effective approach to cope with this situation. The easily extensible fine-grained parallelization method can substantially improve the computing efficiency. Based on many-task computing, we proposed a parallel scheme that the whole computing of the distributed hydrological model is split into tremendous amount of small sub-tasks which are directly dispatched into the cluster nodes by the traditional local resource managers (LRMs). The task-splitting method, the single task model and the representation of dependencies between tasks are also proposed. In order to efficiently schedule so many tasks, a dynamic DAG scheduling method based on critical path and depth is provided. The management of intermediate file, the control strategy for LRMs and the fault recovery is also introduced to deal with the problems encountered in the actual parallel implementation process. The parallel scheme is tested with an optimality-based distributed eco-hydrological model (disVOM) in the Poyang Lake sub-basin. It is demonstrated that our approach provide efficient computing performance.

previous article Linear and dynamic programming algorithms for real-time task scheduling with task duplication

next article Prefetching-based metadata management in Advanced Multitenant Hadoop

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Wang L, Zhang J, Liu P, Choo K-KR, Huang F (2017) Spectralspatial multi-feature-based deep learning for hyperspectral remote sensing image classification. Soft Comput 21(1):213–221MATHCrossRef

Deng Z, Han W, Wang L, Ranjan R, Zomaya AY, Jie W (2017) An efficient online direction-preserving compression approach for trajectory streaming data. Future Gener Comput Syst 68:150–162CrossRef

Liu P, Choo K-KR, Wang L, Huang F (2016) SVM or deep learning? A comparative study on remote sensing image classification. Soft Comput 1–13

Wei J, Huang Y, Lu K, Wang L (2017) Fields of experts based multichannel compressed sensing. J Signal Process Syst 86(2):111–121CrossRef

Fan C, Wang L, Liu P, Lu K, Liu D (2016) Compressed sensing based remote sensing image reconstruction via employing similarities of reference images. Multimed Tools Appl 75(19):12201–12225CrossRef

Wei J, Huang Y, Lu K, Wang L (2016) Nonlocal low-rank-based compressed sensing for remote sensing image reconstruction. IEEE Geosci Remote Sens Lett 13(10):1557–1561CrossRef

Wang L, Geng H, Liu P, Lu K, Kolodziej J, Ranjan R, Zomaya AY (2015) Particle swarm optimization based dictionary learning for remote sensing big data. Knowl Based Syst 79:43–50CrossRef

Wang L, Lu K, Liu P (2015) Compressed sensing of a remote sensing image based on the priors of the reference image. IEEE Geosci Remote Sens Lett 12(4):736–740CrossRef

Chen L, Wang L, Ma Y, Zhu X (2013) Simulation of ecohydrolgocal process using an optimality based model. In: 2013 IEEE international geoscience and remote sensing symposium-IGARSS. IEEE, pp 4281–4284

10.

Bierkens MFP, Bell VA, Burek P, Chaney N, Condon LE, David CH, de Roo A, Döll P, Drost N, Famiglietti JS, Flörke M, Gochis DJ, Houser P, Hut R, Keune J, Kollet S, Maxwell RM, Reager JT, Samaniego L, Sudicky E, Sutanudjaja EH, van de Giesen N, Winsemius H, Wood EF (2015) Hyper-resolution global hydrological modelling: what is next? Hydrol Process 29(2):310–320CrossRef

11.

Borah DK, Bera M (2003) Watershed-scale hydrologic and nonpoint-source pollution models: review of mathematical bases. Trans Asae 46(6):1553–1566CrossRef

12.

Cunjak R, Linnansaari T, Caissie D (2013) The complex interaction of ecology and hydrology in a small catchment: a salmon’s perspective. Hydrol Process 27(5):741–749CrossRef

13.

Martínez-Murillo J, Nadal-Romero E, Regüés D, Cerdà A, Poesen J (2013) Soil erosion and hydrology of the western Mediterranean badlands throughout rainfall simulation experiments: a review. Catena 106:101–112CrossRef

14.

Shen ZY, Chen L, Liao Q, Liu RM, Huang Q (2013) A comprehensive study of the effect of GIS data on hydrology and non-point source pollution modeling. Agric Water Manag 118:93–102CrossRef

15.

Apostolopoulos TK, Georgakakos KP (1997) Parallel computation for streamflow prediction with distributed hydrologic models. J Hydrol 197(1–4):1–24CrossRef

16.

Li T, Wang G, Chen J, Wang H (2011) Dynamic parallelization of hydrological model simulations. Environ Model Softw 26(12):1736–1746CrossRef

17.

Wang H, Fu X, Wang G, Li T, Gao J (2011) A common parallel computing framework for modeling hydrological processes of river basins. Parallel Comput 37(6–7):302–315CrossRef

18.

Wang Y, Jiang J, Ye H, He J (2016) A distributed load balancing algorithm for climate big data processing over a multi-core CPU cluster. Concurr Comput Pract Exp 28(15):4144–4160CrossRef

19.

Wang Y, Jiang J, Zhang H, Dong X, Wang L, Ranjan R, Zomaya AY (2017) A scalable parallel algorithm for atmospheric general circulation models on a multi-core cluster. Future Gener Comput Syst 72:1–10CrossRef

20.

Liu J, Zhu AX, Qin C-Z (2013) Estimation of theoretical maximum speedup ratio for parallel computing of grid-based distributed hydrological models. Comput Geosci 60:58–62CrossRef

21.

Cui Z, Vieux BE, Neeman H, Moreda F (2005) Parallelisation of a distributed hydrologic model. Int J Comput Appl Technol 22(1):42CrossRef

22.

Cheng J, Hunter RM, Cheng H-P, Richards DR, Yeh G-T (2006) Parallelization of a watershed model phase III: coupled 1-dimensional channel, 2-dimensional overland, and 3-dimensional subsurface flows. Computational Methods in Water Resources XVI, Copenhagen, Denmark, CMWR CD-ROM, paper, vol 64. pp 19–22

23.

Kollet SJ, Maxwell RM (2006) Integrated surface-groundwater flow modeling: a free-surface overland flow boundary condition in a parallel groundwater flow model. Adv Water Resour 29(7):945–958CrossRef

24.

Chen L, Ma Y, Liu P, Xue W (2014) Parallelisation of a watershed distributed ecohydrological model with dynamic task scheduling. Int J Ad Hoc Ubiquitous Comput 17(2/3):110–121CrossRef

25.

Liu J, Zhu AX, Qin C-Z, Wu H, Jiang J (2016) A two-level parallelization method for distributed hydrological models. Environ Model Softw 80:175–184CrossRef

26.

Yalew S, van Griensven A, Ray N, Kokoszkiewicz L, Betrie GD (2013) Distributed computation of large scale SWAT models on the Grid. Environ Model Softw 41:223–230CrossRef

27.

Frey J (2002) Condor DAGMan: handling inter-job dependencies, University of Wisconsin, Dept of Computer Science, Tech Rep

28.

Wilde M, Hategan M, Wozniak JM, Clifford B, Katz DS, Foster I (2011) Swift: a language for distributed parallel scripting. Parallel Comput 37(9):633–652CrossRef

29.

Raicu I, Zhao Y, Dumitrescu C, Foster I, Wilde MF (2007) a fast and light-weight tasK executiON framework. In: Proceedings of the 2007 ACM/IEEE Conference on Supercomputing, 2007. SC ’07. pp 1–12

30.

Pordes R, Petravick D, Kramer B, Olson D, Livny M, Roy A, Avery P, Blackburn K, Wenaus T, Frank W (2007) The open science grid. In: Journal of Physics: Conference Series. vol 1. IOP Publishing, p 012057

31.

Catlett C, Allcock WE, Andrews P, Aydt R, Bair R, Balac N, Banister B, Barker T, Bartelt M, Beckman P, et al (2008) TeraGrid: analysis of organization, system architecture, and middleware enabling new types of applications. In: Grandinetti (ed) High performance computing and grids in action, vol 16. IOS Press, Amsterdam, 225–249

32.

Hategan M, Wozniak J, Maheshwari K (2011) Coasters: uniform resource provisioning and access for clouds and grids. In: Fourth IEEE International Conference on Utility and Cloud Computing. pp 114–121

33.

Wilde M, Foster I, Iskra K, Beckman P, Zhang Z, Espinosa A, Hategan M, Clifford B, Raicu I (2009) Parallel scripting for applications at the petascale and beyond. Computer 42(11):50–60CrossRef

34.

Stef-Praun T, Madeira G, Foster I, Townsend R (2007) Accelerating solution of a moral hazard problem with Swift. e-Soc Sci

35.

Fedorov A, Clifford B, Warfield SK, Kikinis R, Chrisochoides N (2009) Non-rigid registration for image-guided neurosurgery on the TeraGrid: a case study. Technical Report WM-CS-2009-05, College of William and Mary, Williamsburg

36.

Woitaszek M, Dennis JM, Sines TR (2011) Parallel high-resolution climate data analysis using swift. In: Proceedings of the 2011 ACM international workshop on Many task computing on grids and supercomputers. ACM, pp 5–14

37.

Kołodziej J, Khan SU, Wang L, Byrski A, Min-Allah N, Madani SA (2013) Hierarchical genetic-based grid scheduling with energy optimization. Cluster Comput 16(3):591–609CrossRef

38.

Wang L, von Laszewski G, Huang F, Dayal J, Frulani T, Fox G (2011) Task scheduling with ANN-based temperature prediction in a data center: a simulation-based study. Eng Comput 27(4):381–391CrossRef

39.

Wang L, Chen D, Zhao J, Tao J (2012) Resource management of distributed virtual machines. Int J Ad Hoc Ubiquitous Comput 10(2):96CrossRef

40.

Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H Freeman, New YorkMATH

41.

Kwok Y-K, Ahmad I (1999) Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Comput Surv (CSUR) 31(4):406–471CrossRef

42.

Chan-Ik P, Tae-Young C (2001) An optimal scheduling algorithm based on task duplication. In: Proceedings. Eighth International Conference on Parallel and Distributed Systems. ICPADS 2001. pp 9–14

43.

Shin K, Cha M, Jang M, Jung J, Yoon W, Choi S (2008) Task scheduling algorithm using minimized duplications in homogeneous systems. J Parallel Distrib Comput 68(8):1146–1156MATHCrossRef

44.

Park G-L, Shirazi B, Marquis J (1997) DFRN: a new approach for duplication based scheduling for distributed memory multiprocessor systems. In: Proceedings of the 11th international parallel processing symposium, 1997. IEEE, pp 157–166

45.

Ishfaq A, Yu-Kwong K (1998) On exploiting task duplication in parallel program scheduling. IEEE Trans Parallel Distrib Syst 9(9):872–892CrossRef

46.

Bansal S, Kumar P, Singh K (2003) An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems. IEEE Trans Parallel Distrib Syst 14(6):533–544CrossRef

47.

Song I, Yoon W, Jang E, Choi S (2011) Task scheduling algorithm with minimal redundant duplications in homogeneous multiprocessor system. Commun Comput Inf Sci 261:238–245

48.

Singh H, Youssef A (1996) Mapping and scheduling heterogeneous task graphs using genetic algorithms, 5th IEEE heterogeneous computing workshop (HCW ’96)

49.

Kaur K, Chhabra A, Singh G (2010) Improved genetic algorithm (IGA) for scheduling task graphs in multiprocessor systems. Digit Signal Process 2(5):33–40

50.

Xu Y, Li K, Khac TT, Qiu M (2012) A multiple priority queueing genetic algorithm for task scheduling on heterogeneous computing systems. In: 2012 IEEE 14th International Conference on High Performance Computing and Communication and 2012 IEEE 9th International Conference on Embedded Software and Systems. pp 639–646

51.

Xu Y, Li K, Hu J, Li K (2014) A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Inf Sci 270:255–287MathSciNetMATHCrossRef

52.

Nanda AK, DeGroot D, Stenger DL (1992) Scheduling directed task graphs on multiprocessors using simulated annealing. In: [1992] Proceedings of the 12th International Conference on Distributed Computing Systems. pp 20–27

53.

Cheng CH, Mak RWT, Tummala VMR, Feiring BR (1999) Task scheduling by guided simulated annealing. Prod Plan Control 10(6):530–541CrossRef

54.

Xiaohong K, Wenbo X (2006) Ant colony algorithm for scheduling parallel program based on DAG graph heuristics. In: 2006 6th world congress on intelligent control and automation. pp 3653–3657

55.

Jha MS, Mallik D, Suri R (2011) Balanced ant colony algorithm for scheduling DAG to grid heterogeneous system. Int J Sci Eng Res 2(6):184–193

56.

Sunil Kumar S, Deo PV (2015) Independent tasks scheduling using parallel PSO in multiprocessor systems. Int J Grid High Perform Comput 7(2):1–17CrossRef

57.

Topcuoglu H, Hariri S, Min-You W (2002) Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans Parallel Distrib Syst 13(3):260–274CrossRef

58.

Ilavarasan E, Thambidurai P, Mahilmannan R (2005) Performance effective task scheduling algorithm for heterogeneous computing system. In: The 4th international symposium on parallel and distributed computing (ISPDC’05). pp 28–38

59.

Kwok Y-K, Ahmad I (1999) Benchmarking and comparison of the task graph scheduling algorithms. J Parallel Distrib Comput 59(3):381–422MATHCrossRef

60.

Shaik N (2016) Dynamic job scheduling strategy for unreliable nodes in a volunteer desktop grid. Int J Grid High Perform Comput 8(4):21–33CrossRef

61.

Zhou A, Wang S, Hsu C-H, Sun Q, Yang F (2016) Task rescheduling optimization to minimize network resource consumption. Multimed Tools Appl 75(20):12901–12917CrossRef

62.

Chen L, Wang L, Ma Y, Liu P (2015) Overview of ecohydrological models and systems at the watershed scale. IEEE Syst J 9(3):1091–1099CrossRef

63.

Duan Q, Gupta VK, Sorooshian S (1993) Shuffled complex evolution approach for effective and efficient global minimization. J Optim Theory Appl 76(3):501–521MathSciNetMATHCrossRef

64.

Duan Q, Sorooshian S, Gupta VK (1994) Optimal use of the SCE-UA global optimization method for calibrating watershed models. J Hydrol 158(3):265–284CrossRef

65.

Raicu I, Foster IT, Zhao Y (2008) Many-task computing for grids and supercomputers. In: 2008 workshop on many-task computing on grids and supercomputers. IEEE, pp 1–11

66.

Laszewski GV, Hategan M (2005) Workflow concepts of the Java CoG Kit. J Grid Comput 3(3):239–258CrossRef

67.

Bode B, Halstead DM, Kendall R, Lei Z, Jackson D (2000) The portable batch scheduler and the maui scheduler on linux clusters. In: USENIX Extreme Linux Technical Conference

68.

Frey J, Tannenbaum T, Livny M, Foster I, Tuecke S (2002) Condor-G: a computation management agent for multi-institutional grids. Cluster Comput 5(3):237–246CrossRef

69.

Zhou S (1992) Lsf: load sharing in large heterogeneous distributed systems. In: I Workshop on cluster computing

70.

Johnston K, Ver Hoef JM, Krivoruchko K, Lucas N (2001) Using ArcGIS geostatistical analyst, vol 380. Esri Redlands, Redlands

Title: Dynamic DAG scheduling for many-task computing of distributed eco-hydrological model
Authors: Shasha Yue
Yan Ma
Lajiao Chen
Yuzhu Wang
Weijing Song
Publication date: 19-04-2017
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 2/2019
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-017-2047-1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 2/2019

WatCache: a workload-aware temporary cache on the compute side of HPC systems

Binary executable file similarity calculation using function matching

On the modelling of optimal coordinated checkpoint period in supercomputers

Fair multiple-workflow scheduling with different quality-of-service goals

An Otsu multi-thresholds segmentation algorithm based on improved ACO

An energy-efficient partition-based XYZ-planar routing algorithm for a wireless network-on-chip

Premium Partner