User Tools

Site Tools


Sidebar

Master work

Thesis

Basic MPI-2

Work-Stealing with MPI-2

Implementation

Results

mestrado:start

About my Master Thesis

Title:

  • Scheduling Divide-and-Conquer programs by Work-Stealing with MPI-2
    • Escalonamento Work-Stealing de programas Divisão-e-Conquista com MPI-2


By Guilherme Peretti Pezzi

  • Advisor
    • Philippe Olivier Alexandre Navaux
  • Co-Advisor
    • Nicolas Maillard

Abstract

In order to be portable and efficient on modern HPC architectures, a parallel program must be adaptable. This work shows how to achieve this in MPI, by the dynamic creation of processes, coupled with Divide-and-Conquer programming and a Work Stealing strategy to balance the MPI processes, in a heterogeneous and/or dynamic environment, at runtime. The application of Divide and Conquer with MPI is explained, as well as the implementation of a Work Stealing strategy. Experimental results are provided, based on a synthetic application, the N-Queens computation. Both the adaptability of the code and its efficiency are validated. The results show that it is possible to use widely spread standards such as MPI, even in parallel HPC platforms that are not as homogeneous as a cluster.

Resumo

Com o objetivo de ser portável e eficiente em arquiteturas HPC atuais, um programa paralelo deve ser adaptável. Este trabalho mostra como isso pode ser atingido utilizando MPI, através de criação dinâmica de processos, integrada com programação Divisão-e-Conquista e uma estratégia Work Stealing para balancear os processos MPI, em ambientes heterogêneos e/ou dinâmicos, em tempo de execução. Este trabalho explica como implementar uma aplicação segundo o modelo de Divisão-e-Conquista com MPI, bem como a implementação de uma estratégia Work Stealing. São apresentados resultados experimentais baseados em uma aplicação sintética, o problema das N-Rainhas. Valida-se tanto a adptabilidade e a eficiência do código. Os resultados mostram que é possível utilizar um padrão amplamente difundido como o MPI, mesmo em plataformas de HPC não homogêneas, como um cluster.

Full Text

Dissertação de mestrado: Portuguese only

  1. PEZZI, G. P. ; CERA, Marcia C ; MATTHIAS, E. N. ; MAILLARD, Nicolas ; NAVAUX, P. O. A. On-Line Scheduling of MPI-2 Programs with Hierarchical Work Stealing. In: 19th International Symposium on Computer Architecture and High Performance Computing, 2007, Gramado, Brasil
  2. PEZZI, G., CERA, M., MATHIAS, E.N., MAILLARD, N., NAVAUX, P. Escalonamento Dinâmico de programas MPI-2 utilizando Divisão e Conquista. In: WORKSHOP EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO 2006 - WSCAD, 2006, Ouro Preto - MG. Proceedings, 2006.
  3. CERA, M., MATHIAS, E.N., PEZZI, G., MAILLARD, N., NAVAUX, P. Improving the Dynamic Creation of Processes in MPI-2. In: EuroPVM/ MPI’2006. European PVM/MPI Users’ Group Meetings , 2006, Bonn, Germany. Proceedings of EuroPVM/MPI 2006 and Spring LNCS series.
  4. CERA, Marcia C ; PEZZI, G. P. ; MATTHIAS, E. N. ; MAILLARD, Nicolas ; NAVAUX, P. O. A. . Scheduling Dynamically Spawned Processes in MPI-2.. In: 12TH WORKSHOP ON JOB SCHEDULING STRATEGIES FOR PARALLEL PROCESSING, 2006, Saint Malo. 12TH WORKSHOP ON JOB SCHEDULING STRATEGIES FOR PARALLEL PROCESSING - SIGMETRICS, 2006.

—-


Work-Stealing with MPI-2

Work-stealing is an efficient way to schedule divide-and-conquer applications in a parallel machine. It has been used in environments like Cilk and Satin, with very good results. This page presents implementations of a mechanism similar to these environments, but using MPI-2 and the new features provided by this norm.

As the primitives provided by MPI-2 are different from the other environments that implement Work-Stealing, it was needed to develop a new algorithm for performing Work-Stealing, which is called Hierarquical Work-Stealing.

Implementation

Results

Hierarchical Work-Stealing

mestrado/start.txt · Last modified: 2007/09/14 09:19 by pagode