Paper Info
Title
Low-Cost Tuning of Two-Step Algorithms for Scheduling Mixed-Parallel Applications onto Homogeneous Clusters
Abstract
Due to the strong increase of processing units available to the end user, expressing parallelism of an algorithm is a major challenge for many researchers. Parallel applications are often expressed using a task-parallel model (task graphs), in which tasks can be executed concurrently unless they share a dependency. If these tasks can also be executed in a data-parallel fashion, e.g., by using MPI or OpenMP, then we call it a mixed-parallel programming model. Mixed-parallel applications are often modeled as directed a cyclic graphs (DAGs), where nodes represent the tasks and edges represent data dependencies. To execute a mixed-parallel application efficiently, a good scheduling strategy is required to map the tasks to the available processors. Several algorithms for the scheduling of mixed-parallel applications onto a homogeneous cluster have been proposed. MCPA (Modified CPA) has been shown to lead to efficient schedules. In the allocation phase, MCPA considers the total number of processors allocated to all potentially concurrently running tasks as well as the number of processors in the cluster. In this article, it is shown how MCPA can be extended to obtain a more balanced workload in situations where concurrently running tasks differ significantly in the number of operations. We also show how the allocation procedure can be tuned in order to deal not only with regular DAGs (FFT), but also with irregular ones. We also investigate the question whether additional optimizations of the mapping procedure, such as packing of allocations or backfilling, can reduce the make span of the schedules.
Year
DOI
Venue
2010
10.1109/CCGRID.2010.52
Cluster, Cloud and Grid Computing
Keywords
Field
DocType
scheduling mixed-parallel applications,total number,mixed-parallel programming model,homogeneous cluster,low-cost tuning,homogeneous clusters,allocation procedure,good scheduling strategy,mixed-parallel application,available processor,mapping procedure,two-step algorithms,allocation phase,regular dags,scheduling,scheduling algorithm,resource management,concurrency control,clustering algorithms,computer science,mathematical model,directed graphs,clusters,application software,parallel programming,grid computing,parallel programming model,schedules
Grid computing,Scheduling (computing),Computer science,Real-time computing,Cluster analysis,Application software,Distributed computing,Programming paradigm,Concurrency control,Parallel computing,Algorithm,Directed graph,Schedule
Conference
ISBN
Citations 
PageRank 
978-1-4244-6987-1
7
0.48
References 
Authors
14
1
Name
Order
Citations
PageRank
Sascha Hunold112120.11