Automatic Modeling and Grid Scheduling MPI Applications

Abstract. Most scheduling algorithms for computational grids rely on an ap-plication model represented by a directed acyclic graph (DAG). Tasks are then selected for execution according to their processing and communication weights. The obtainment of DAGs for real applications, however, is not a simple quest. Many MPI programs present a cyclic communication model among the master and the processing nodes. This behavior prevents most scheduling algorithms to be employed as they recursively traverse the graphs to prioritize the tasks. In this sense, this paper presents a mechanism for the automatic creation of DAGs for real MPI. Applications go through a monitored execution in a cluster and the collected data are used to identify dependencies. Existing cycles among the tasks are eliminated producing an appropriate DAG. 1