Top

International Journal of Parallel Programming

Published in:

11-05-2016

Scalable Loop Self-Scheduling Schemes for Large-Scale Clusters and Cloud Systems

Authors: Yiming Han, Anthony T. Chronopoulos

Published in: International Journal of Parallel Programming | Issue 3/2017

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

search-config

AI-assisted search

Off

Abstract

Cloud systems have demonstrated the powerful computation and storage capability in many scientific applications. In this paper, we propose a class of scalable distributed loop self-scheduling schemes to achieve good load balancing and scalability. We implemented these schemes on a large-scale cluster and on a heterogeneous cloud system. The schemes consider the distribution of the output data, which can help reduce communication overhead and improve scalability. We evaluated the schemes using four scientific computations: Mandelbrot set, adjoint convolution, matrix multiplication and quick sort. The results show that the new schemes achieve better load balancing, better scalability and better overall performance than standard distributed loop self-scheduling schemes.

previous article RT-CUDA: A Software Tool for CUDA Code Restructuring

next article Porting the PLASMA Numerical Library to the OpenMP Standard

Dont have a licence yet? Then find out more about our products and how to get one 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

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

Keahey, K: Cloud computing for science. In: Proceeding of 21st Scientific and Statistical Database Management Conference. vol. 5566, pp. 478–478 (2009)

Wang, L., Tao, J., Kunze, M., Castellanos, A., Kramer, D., Karl, W.: Scientific cloud computing: early definition and experience. In: 10th IEEE International Conference on High Performance Computing and Communications, HPCC’08, pp. 825–830 (2008)

Yeo, S., Lee, H.-H.: Using mathematical modeling in provisioning a heterogeneous cloud computing environment. Computer 44, 55–62 (2011)

Han, Y., Chronopoulos, A.: Distributed loop scheduling schemes for cloud systems. In: IEEE 27th International Parallel and Distributed Processing Symposium Workshops PhD Forum (IPDPSW), pp. 955–962 (2013)

Sonnek, J., Greensky, J., Reutiman, R., Chandra, A.: Starling: minimizing communication overhead in virtualized computing platforms using decentralized affinity-aware migration. In: 39th International Conference on Parallel Processing, ICPP’10, pp. 228–237 (2010)

Han, Y., Chronopoulos, A.: A hierarchical distributed loop self-scheduling scheme for cloud systems. In: 12th IEEE International Symposium on Network Computing and Applications (NCA), pp. 7–10 (2013)

Han, Y., Chronopoulos, A.: Scalable loop self-scheduling schemes implemented on large-scale clusters. In: IEEE 27th International Parallel and Distributed Processing Symposium Workshops PhD Forum (IPDPSW), pp. 1735–1742 (2013)

Joyent corporation. http://joyent.com/

Kejariwal, A., Nicolau, A., Polychronopoulos, C.: History-aware self-scheduling. In: International Conference on Parallel Processing Parallel Processing, ICPP’06, pp. 185–192 (2006)

10.

Chronopoulos, A.T., Penmatsa, S., Xu, J., Ali, S.: Distributed loop-scheduling schemes for heterogeneous computer systems. Concurr. Comput. Pract. Exp. 18, 771–785 (2006)CrossRef

11.

Banicescu, I., Velusamy, V., Devaprasad, J.: On the scalability of dynamic scheduling scientific applications with adaptive weighted factoring. Clust. Comput. 6, 215–226 (2003)CrossRef

12.

Chronopoulos, A.T., Penmatsa, S., Yu, N., Yu, D.: Scalable loop self-scheduling schemes for heterogeneous clusters. Int. J. Comput. Sci. Eng. 1, 110–117 (2005)CrossRef

13.

Li, P., Ji, Q., Zhang, Y., Zhu, Q.: An adaptive chunk self-scheduling scheme on service grid. In: IEEE Asia-Pacific Services Computing Conference, APSCC’08, pp. 39–44 (2008)

14.

Yang, K.-W.C., Chao-Tung, Li, K.-C.: An efficient parallel loop self-scheduling on grid environments. In: Network and Parallel Computing, pp. 92–100 (2004)

15.

Yang, C.-T., Chang, S.-C.: A parallel loop self-scheduling on extremely heterogeneous pc clusters. In: Proceedings of International Conference on Computational, Science, pp. 1079–1088 (2003)

16.

Cheng, K.-W., Yang, C.-T., Lai, C.-L., Chang, S.-C.: A parallel loop self-scheduling on grid computing environments. In: Proceedings of the 2004 International Symposium on Parallel Architectures, Algorithms and IEEE Networks, pp. 409–414 (2004)

17.

Andronikos, T., Ciorba, F.M., Riakiotakis, I., Papakonstantinou, G., Chronopoulos, A.T.: Studying the impact of synchronization frequency on scheduling tasks with dependencies in heterogeneous systems. Perform. Eval. 67(12), 1324–1339 (2010)CrossRef

18.

Ciorba, F., Andronikos, T., Riakiotakis, I., Chronopoulos, A., Papakonstantinou, G.: Dynamic multi phase scheduling for heterogeneous clusters. In: Proceedings of the 20th IEEE International Parallel Distributed Processing Symposium, IPDPS06, p. 10 (2006)

19.

Riakiotakis, I., Ciorba, F.M., Andronikos, T., Papakonstantinou, G., Chronopoulos, A.T.: Towards the optimal synchronization granularity for dynamic scheduling of pipelined computations on heterogeneous computing systems. Concurr. Comput. Pract. Exp. 24, 2302–2327 (2012)CrossRef

20.

Diaz, J., Reyes, S., Nino, A., Munoz-Caro, C.: Derivation of self-scheduling algorithms for heterogeneous distributed computer systems: application to internet-based grids of computers. Future Gener. Comput. Syst. 25, 617–626 (2009)CrossRef

21.

Wu, C.-C., Yang, C.-T., Lai, K.-C., Chiu, P.-H.: Designing parallel loop self-scheduling schemes using the hybrid MPI and openMP programming model for multi-core grid systems. J. Supercomput. 59, 42–60 (2012)CrossRef

22.

He, Y., Liu, J., Sun, H.: Scheduling functionally heterogeneous systems with utilization balancing. In: IEEE International Parallel Distributed Processing Symposium, IPDPS’11, pp. 1187–1198 (2011)

23.

Penmatsa, S., Chronopoulos, A., Karonis, N., Toonen, B.: Implementation of distributed loop scheduling schemes on the teragrid. IN: IEEE International Parallel and Distributed Processing Symposium, IPDPS’07, pp. 1–8 (2007)

24.

Kyriakopoulos, K., Chronopoulos, A., Ni, L.: An optimal scheduling scheme for tiling in distributed systems. In: IEEE International Conference on Cluster Computing, pp. 267–274 (2007)

25.

Chronopoulos, A., Ni, L., Penmatsa, S.: Multi-dimensional dynamic loop scheduling algorithms. In: IEEE International Conference on Cluster Computing, pp. 241–248 (2007)

26.

Hwang, K., Dongarra, J., Fox, G.C.: Distributed and cloud computing: from parallel processing to the internet of things. Morgan Kaufmann, (2011)

27.

Wen, G., Hong, J., Xu, C., Balaji, P., Feng, S., Jiang, P.: Energy-aware hierarchical scheduling of applications in large scale data centers. In: International Conference on Cloud and Service Computing, CSC’11, pp. 158–165 (2011)

28.

Iosup, A., Ostermann, S., Yigitbasi, M., Prodan, R., Fahringer, T., Epema, D.: Performance analysis of cloud computing services for many-tasks scientific computing. IEEE Trans. Parallel Distrib. Syst. 22, 931–945 (2011)CrossRef

29.

Ekanayake, J. Fox, G.: High performance parallel computing with clouds and cloud technologies. In: Proceedings of the First International Conference on Cloud Computing, pp. 20–38 (2010)

30.

Evangelinos, C., Hill, C.N.: Cloud computing for parallel scientific HPC applications: feasibility of running coupled atmosphere–ocean climate models on Amazon’s EC2. In: 5th International Conference on Computability and Complexity in Analysis, pp. 159–168 (2008)

31.

Shih, W.-C. Tseng, S.-S., Yang, C.-T.: Performance study of parallel programming on cloud computing environments using MapReduce. In: International Conference on Information Science and Applications, ICISA’10, pp. 1–8 (2010)

32.

Stress. http://www.hecticgeek.com/2012/11/stress-test-your-ubuntu-computer-with-stress/

Title: Scalable Loop Self-Scheduling Schemes for Large-Scale Clusters and Cloud Systems
Authors: Yiming Han
Anthony T. Chronopoulos
Publication date: 11-05-2016
Publisher: Springer US
Published in: International Journal of Parallel Programming / Issue 3/2017
Print ISSN: 0885-7458
Electronic ISSN: 1573-7640
DOI: https://doi.org/10.1007/s10766-016-0434-5

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+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2017

A Parallel Approach for the Generation of Unstructured Meshes with Billions of Elements on Distributed-Memory Supercomputers

A Wait-Free Hash Map

Restart Optimization for Transactional Memory with Lazy Conflict Detection

RT-CUDA: A Software Tool for CUDA Code Restructuring

Panda: A Compiler Framework for Concurrent CPUGPU Execution of 3D Stencil Computations on GPU-accelerated Supercomputers

Programming GPGPU Graph Applications with Linear Algebra Building Blocks

Premium Partner