Top

Cluster Computing

Published in:

01-09-2012

SEParAT: scheduling support environment for parallel application task graphs

Authors: Jörg Dümmler, Raphael Kunis, Gudula Rünger

Published in: Cluster Computing | Issue 3/2012

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

search-config

AI-assisted search

Off

Abstract

Programs using parallel tasks can be represented by task graphs so that scheduling algorithms can be used to find an efficient execution order of the parallel tasks. This article proposes a flexible, component-based and extensible scheduling framework called SEParAT that supports the scheduling of a parallel program in multiple ways. The article describes the functionality and the software architecture of SEParAT. The flexible interfaces enable the cooperation with other programming tools, e.g., tools exploiting a specification of the parallel task structure of an application. The core component of SEParAT is an extensible scheduling algorithm library that provides an infrastructure to determine efficient schedules for task graphs. Homogeneous as well as heterogeneous platforms can be handled. The article also includes detailed experimental results comprising the evaluation of SEParAT as well as the evaluation of a variety of scheduling algorithms.

previous article Performance analysis of virtual clusters in personal communication networks

next article Performance, reliability, and performability of a hybrid RAID array and a comparison with traditional RAID1 arrays

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

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

Ahmad, I., Kwok, Y.-K., Wu, M.-Y., Shu, W.: Casch: a tool for computer-aided scheduling. IEEE Concurrency 8, 21–33 (2000) CrossRef

Alexandrov, A., Ionescu, M.F., Schauser, K.E., Scheiman, C.: LogGP: incorporating long messages into the LogP model for parallel computation. Journ. of Parallel and Distr. Computing 44(1), 71–79 (1997) CrossRef

Baduel, L., Baude, F., Caromel, D., Contes, A., Huet, F., Morel, M., Quilici, R.: Grid Computing: Software Environments and Tools, Chapter: Programming, Deploying, Composing, for the Grid, pp. 205–229. Springer, Berlin (2006)

Banerjee, P., Chandy, J., Gupta, M., Hodge, E., Holm, J., Lain, A., Palermo, D., Ramaswamy, S., Su, E.: The paradigm compiler for distributed-memory multicomputers. IEEE Comp. 28(10), 37–47 (1995) CrossRef

Bansal, S., Kumar, P., Singh, K.: An improved two-step algorithm for task and data parallel scheduling in distributed memory machines. Parallel Computing 32(10), 759–774 (2006) MathSciNetCrossRef

Barker, K.J., Davis, K., Hoisie, A., Kerbyson, D.J., Lang, M., Pakin, S., Sancho, J.C.: Using performance modeling to design large-scale systems. IEEE Comput. 42(11), 42–49 (2009) CrossRef

Boudet, V., Desprez, F., Suter, F.: One-step algorithm for mixed data and task parallel scheduling without data replication. In: Proc. of 17th Int. Symp. on Parallel and Distr. Processing IPDPS’03:, p. 41.2. IEEE Comput. Soc., Los Alamitos (2003)

Cao, J., Chan, A.T., Sun, Y., Das, S.K., Guo, M.: A taxonomy of application scheduling tools for high performance cluster computing. Cluster Computing 9(3), 355–371 (2006) CrossRef

Casanova, H., Desprez, F., Suter, F.: From heterogeneous task scheduling to heterogeneous mixed parallel scheduling. In: Danelutto, M., Laforenza, D., Vanneschi, M. (eds.) Proc. of 10th Int. Euro-Par Conf. (Euro-Par’04), Pisa, Italy, August/September 2004. Lecture Notes in Computer Science, vol. 3149, pp. 230–237. Springer, Berlin (2004)

10.

Culler, D.E., Karp, R.M., Patterson, D.A., Sahay, A., Schauser, K.E., Santos, E., Subramonian, R., von Eicken, T.: LogP: towards a realistic model of parallel computation. In: Principles Practice of Parallel Programming, pp. 1–12 (1993)

11.

Du, J., Leung, J.Y.-T.: Complexity of scheduling parallel task systems. SIAM Journal on Discrete Mathematics 2(4), 473–487 (1989) MathSciNetMATHCrossRef

12.

Dümmler, J., Kunis, R., Rünger, G.: A comparison of scheduling algorithms for multiprocessortasks with precedence constraints. In: Proc. of the 2007 High Performance Computing & Simulation (HPCS’07) Conference, pp. 663–669 (2007). ECMS

13.

Dümmler, J., Kunis, R., Rünger, G.: A scheduling toolkit for multiprocessor-task programming with dependencies. In: Proc. of the 13th International Euro-Par Conference. Lecture Notes in Computer Science, vol. 4641, pp. 23–32. Springer, Berlin (2007)

14.

Dümmler, J., Kunis, R., Rünger, G.: Layer-based scheduling algorithms for multiprocessor-tasks with precedence constraints. In: Parallel Computing: Architectures, Algorithms and Applications: Proc. of the Int. Conf. ParCo 2007. Advances in Parallel Computing, vol. 15, pp. 321–328 (2007). IOS Press

15.

Dümmler, J., Rauber, T., Rünger, G.: A transformation framework for communicating multiprocessor-tasks. In: Proc. of the 16th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP’08), pp. 64–71. IEEE Press, New York (2008)

16.

Frachtenberg, E., Schiegelshohn, U.: New challenges of parallel job scheduling. In: Frachtenberg, E., Schwiegelshohn, U. (eds.) Proceedings of the 13th Job Scheduling Strategies for Parallel Processing. Lecture Notes in Computer Science, vol. 4942, pp. 1–23. Springer, Berlin (2008) CrossRef

17.

Hill, M., McColl, W., Skillicorn, D.: Questions and answers about BSP. Scientific Programming 6(3), 249–274 (1997)

18.

Kühnemann, M., Rauber, T., Rünger, G.: Performance modelling for task-parallel programs. In: Performance Analysis and Grid Computing, pp. 77–91. Kluwer, Norwell (2004) CrossRef

19.

Kunis, R., Rünger, G.: Optimizing layer-based scheduling algorithms for parallel tasks with dependencies. Concurrency and Computation: Practice and Experience 23(8), 827–849 (2011) CrossRef

20.

Kwon, O.-K., Hahm, J., Kim, S., Lee, J.R.: Grasp: a grid resource allocation system based on ogsa. In: 13th Int. Symp. on High-Performance Distr. Comp, pp. 278–279 (2004)

21.

Lepere, R., Mounie, G., Trystram, D.: An approximation algorithm for scheduling trees of malleable tasks. European Journ. of Operational Research 142, 242–249 (2002) MathSciNetMATHCrossRef

22.

Lepere, R., Trystram, D., Woeginger, G.J.: Approximation algorithms for scheduling malleable tasks under precedence constraints. Int. Journ. of Foundation of Comp. Sci. 13(4), 613–627 (2002) MathSciNetMATHCrossRef

23.

Lewis, T., El-Rewini, H.: Parallax: a tool for parallel program scheduling. IEEE Parallel Distr. Technol. 1(2), 62–72 (1993) CrossRef

24.

Ludwig, W., Tiwari, P.: Scheduling malleable and nonmalleable parallel tasks. In: Proc. of 5th Annual ACM-SIAM Symp. on Discrete Algorithms SODA’94, pp. 167–176. SIAM, Philadelphia (1994)

25.

Mounie, G., Rapine, C., Trystram, D.: Efficient approximation algorithms for scheduling malleable tasks. In: SPAA’99: Proc. of 11th Annual ACM Symp. on Parallel Algorithms and Architectures, pp. 23–32. ACM, New York (1999) CrossRef

26.

Mounie, G., Rapine, C., Trystram, D.: A \(\frac{3}{2}\)-approximation algorithm for scheduling independent monotonic malleable tasks. SIAM Journ. on Computing 37(2), 401–412 (2007) MathSciNetMATHCrossRef

27.

N’Takpe, T., Suter, F.: Critical path and area based scheduling of parallel task graphs on heterogeneous platforms. In: Proc. of 12th Int. Conf. on Parallel and Distr. Syst. (ICPADS06), Washington, DC, USA, pp. 3–10. IEEE Comput. Soc., Los Alamitos (2006)

28.

N’Takpe, T., Suter, F., Casanova, H.: A comparison of scheduling approaches for mixed-parallel applications on heterogeneous platforms. In: Proc. of 6th Int. Symp. on Parallel and Distr. Computing (ISPDC’07), pp. 35–42. IEEE Comput. Soc., Los Alamitos (2007) CrossRef

29.

Radulescu, A., Nicolescu, C., van Gemund, A.J.C., Jonker, P.: CPR: mixed task and data parallel scheduling for distributed systems. In: Proc. of 15th Int. Parallel & Distr. Processing Symp. (IPDPS01), pp. 39–48. IEEE Comput. Soc., Los Alamitos (2001)

30.

Radulescu, A., van Gemund, A.J.C.: A low-cost approach towards mixed task and data parallel scheduling. In: Proc. of 2001 Int. Conf. on Parallel Processing, pp. 69–76. IEEE Comput. Soc., Los Alamitos (2001) CrossRef

31.

Ramaswamy, S., Sapatnekar, S., Banerjee, P.: A framework for exploiting task and data parallelism on distributed memory multicomputers. IEEE Trans. Parallel Distr. Syst. 8(11), 1098–1116 (1997) CrossRef

32.

Rauber, T., Rünger, G.: Compiler support for task scheduling in hierarchical execution models. Journ. Syst. Archit. 45(6–7), 483–503 (1998)

33.

Rauber, T., Rünger, G.: Scheduling of data parallel modules for scientific computing. In: Proc. of 9th SIAM Conf. on Parallel Processing for Scientific Computing (PPSC). SIAM, Philadelphia (1999)

34.

Rauber, T., Rünger, G.: A transformation approach to derive efficient parallel implementations. IEEE Transactions on Software Engineering 26(4), 315–339 (2000) CrossRef

35.

Sips, H.J., van Reeuwijk, K.: An integrated annotation and compilation framework for task and data parallel programming in Java. In: Parallel Computing: Software Technology, Algorithms, Architectures and Applications (PARCO 2003), Dresden, Germany, pp. 111–118. Elsevier, Amsterdam (2003)

36.

Tannenbaum, T., Wright, D., Miller, K., Livny, M.: Condor—a distributed job scheduler. In: Sterling, T. (ed.) Beowulf Cluster Computing with Linux. MIT Press, Cambridge (2001)

37.

Topcuoglu, H., Hariri, S., Wu, M.-Y.: Task scheduling algorithms for heterogeneous processors. In: Proc. of 8th Heterogeneous Computing Workshop, HCW’99, Washington, DC, USA, p. 3. IEEE Comput. Soc., Los Alamitos (1999) CrossRef

38.

van Gemund, A.J.C.: Symbolic performance modeling of parallel systems. IEEE Trans. Parallel Distrib. Syst. 14(2), 154–165 (2003) CrossRef

39.

Wu, M.Y., Gajski, D.D.: Hypertool: a programming aid for message-passing systems. IEEE Trans. Parallel Distr. Syst. 1(3), 330–343 (1990) CrossRef

40.

Yang, T., Gerasoulis, A.: Pyrros: static task scheduling and code generation for message passing multiprocessors. In: 6th ACM Int. Conf. on Supercomputing, pp. 428–437 (1992)

Title: SEParAT: scheduling support environment for parallel application task graphs
Authors: Jörg Dümmler
Raphael Kunis
Gudula Rünger
Publication date: 01-09-2012
Publisher: Springer US
Published in: Cluster Computing / Issue 3/2012
Print ISSN: 1386-7857
Electronic ISSN: 1573-7543
DOI: https://doi.org/10.1007/s10586-012-0211-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+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2012

STACRP: a secure trusted auction oriented clustering based routing protocol for MANET

The impact of heterogeneous multi-core clusters on graph partitioning: an empirical study

Two-level parallelization of Ehrenfest force calculations in ab initio molecular dynamics simulation

A new approach to the job scheduling problem in computational grids

Modular implementation of dynamic algorithm switching in parallel simulations

A decentralized clustering scheme for transparent mode devices

Premium Partner