PDF de programación - Una implementación multithread de MPI para Linux

Una implementación multithread de MPI para Linux

Alejandro Calderón, Félix García, Jesús Carretero

Octubre de 1999

Resumen

En este artículo se presenta una implementación multithread de la interfaz estándar de paso de mensajes MPI,
que se está desarrollando en el Departamento de Arquitectura y Tecnología de Sistemas Informáticos (DATSI) de la
Universidad Politécnica de Madrid, denominada MiMPI. MiMPI ofrece una semántica multithread y utiliza operaciones
multithread para incrementar el rendimiento de ciertas operaciones, como por ejemplo las colectivas. MiMPI ejecuta
en estaciones de trabajo UNIX, Linux y en multicomputadores SP2. El artículo describe los principales objetivos de
diseño, la actual implementación de MiMPI y los resultados de su evaluación realizada sobre una red de estaciones de
trabaoj con Linux.

1 Introducción

MPI [7] es una interfaz estándar de paso de mensajes cuyos objetivos básicos son: la funcionalidad, la eficiencia y la
portabilidad. Aunque la semántica que especifica MPI para el paso de mensajes permite su utilización en aplicaciones y
entornos multithread, en la actualidad no existe ninguna implementación de este estándar que verdaderamente pueda ser
utilizada para desarrollar un programa MPI multithread.

El uso de threads en una aplicación que emplea paso de mensajes y la implementación de un sistema de paso de

mensajes utilizando threads puede ser muy útil por varias razones:

Los threads permiten una implementación natural de operaciones no bloqueantes, basta con crear un thread que

procese la operación no bloqueante.

El uso de threads puede incrementar la eficiencia de la implementación de operaciones colectivas.

Los threads ofrecen un modelo natural para implementar ciertas operaciones que requieren memoria compartida.
En general todo proceso que emplea paso de mensajes para comunicarse con otros, lleva a cabo dos tareas bien
diferenciadas, una de cómputo y otra de intercambio de mensajes. Estas tareas pueden implementarse de forma
eficiente utilizando threads dentro del mismo proceso.

Los threads se están convirtiendo en el mecanismo de programación paralela de los multiprocesadores de memoria

compartida, ya que permiten explotar el paralelismo de dichas arquitecturas de una forma eficiente.

Las ventajas anteriormente citadas junto con la falta de una implementación de MPI con soporte para la ejecución
de aplicaciones multithread en redes de estaciones de trabajo con Linux, motivó a los autores el desarrollo de MiMPI.
MiMPI [5] es una implementación de MPI que está desarrollándose en el Departamento de Arquitectura y Tecnología
de Sistemas Informáticos (DATSI) de la Universidad Politécnica de Madrid. MiMPI surgió con dos objetivos básicos:
ofrecer una implementación de MPI que pueda ser utilizada en programas multithread (MT-safe), y utilizar threads para
su implementación con el objetivo de mejorar el rendimiento de ciertas operaciones.

En la actualidad MiMPI implementa un subconjunto de todas las primitivas de MPI y ha sido utilizado con éxito en

ParFiSys [4] [9] un sistema de ficheros paralelo desarrollado en el DATSI.

El resto del trabajo está organizado como sigue: en la sección II se describe brevemente MPI. En la sección III se
presentan algunas de las implementaciones existentes de MPI. En la sección IV se realiza una descripción de MiMPI, sus
objetivos de diseño e implementaciones actuales. La evaluación de MiMPI se presenta en la sección V y los resultados
obtenidos de dicha evaluación se muestran en la sección VI. Estos resultados comparan el rendimiento de MiMPI con
el de MPICH (implementación de libre distribución) en una red de estaciones e trabajo con Linux. El trabajo finaliza
incluyendo algunas conclusiones y las líneas de trabajo futuras.

1

2 Breve descripción de MPI

MPI [7] [11] (message-passing interface) es la especificación de un interfaz estándar de paso de mensajes, cuyos prin-
cipales objetivos son: la funcionalidad, la eficiencia y la portabilidad. MPI incluye paso de mensajes punto a punto y
operaciones colectivas, todas ellas dentro del ámbito de un grupo de procesos especificado por el usuario. En MPI todos
los procesos pertenecen a grupos. Si un grupo contiene n procesos, éstos se identifican mediante enteros dentro del rango
0, n-1.

A continuación se describen algunas de las principales características que ofrece MPI:

Operaciones colectivas. Una operación colectiva es una operación ejecutada por todos los procesos que inter-
vienen en un cálculo o comunicación. En MPI existen dos tipos de operaciones colectivas: operaciones de
movimiento de datos y operaciones de cálculo colectivo. Las primeras se utilizan para intercambiar y reordenar
datos entre un conjunto de procesos. Un ejemplo típico de operación colectiva es la difusión (broadcast) de un
mensaje entre varios procesos. Las segundas permiten realizar cálculos colectivos como mínimo, máximo, suma,
OR lógico, etc, así como operaciones definidas por el usuario.

Topologías virtuales, ofrecen un mecanismo de alto nivel para manejar grupos de procesos sin tratar con ellos

directamente. MPI soporta grafos y redes de procesos.

Modos de comunicación. MPI soporta operaciones bloqueantes, no bloqueantes o asíncronas y síncronas. Una
operación de envío bloqueante bloquea al proceso que la ejecuta sólo hasta que el buffer pueda ser reutilizado
de nuevo. Una operación no bloqueante permite solapar el cálculo con las comunicaciones. En MPI es posible
esperar por la finalización de varias operaciones no bloqueantes. Un envío síncrono bloquea la operación hasta que
la correspondiente recepción tiene lugar. En este sentido, una operación bloqueante no tiene por que ser síncrona.

Soporte para redes heterogéneas. Los programas MPI están pensados para poder ejecutarse sobre redes de

máquinas heterogéneas con formatos y tamaños de los tipos de datos elementales totalmente diferentes.

Tipos de datos. MPI ofrece un amplio conjunto de tipos de datos predefinidos (caracteres, enteros, números en
coma flotante, etc.) y ofrece la posibilidad de definir tipos de datos derivados. Un tipo de datos derivado es un
objeto que se construye a partir de tipos de datos ya existentes. En general, un tipo de datos derivado se especifica
como una secuencia de tipos de datos ya existentes y desplazamientos (en bytes) de cada uno de estos tipos de
datos. Estos desplazamientos son relativos al buffer que describe el tipo de datos derivado.

Modos de programación. Con MPI se pueden desarrollar aplicaciones paralelas que sigan el modelo SPMD
o MPMP. Además el interfaz MPI tiene una semántica multithread (MT-safe), que le hace adecuado para ser
utilizado en programas MPI y entornos multithread.

En 1997 se añadieron algunas extensiones al estándar inicial, apareciendo MPI-2 [8]. Este nuevo estándar incluye,
entre otras características, funcionalidad para la gestión y creación de procesos, nuevas operaciones colectivas y opera-
ciones de E/S (MPI-IO).

3 Implementaciones existentes

A continuación se describen algunas de las implementaciones de MPI existentes en la actualidad:

LAM [3] es una implementación disponible en el centro de supercomputación de Ohio, que ejecuta sobre esta-

ciones de trabajo heterogéneas Sun, DEC, SGI, IBM y HP.

CHIMP-MPI [1] es una implementación desarrollada en el Centro de Computación Paralela de Edimburgo basada
en CHIMP [6]. Esta implementación ejecuta sobre estaciones de trabajo Sun, SGI, DEC, IBM y HP, y máquinas
Meiko y Fujitsu AP-1000.

MPICH [10] es una implementación desarrollada de forma conjunta por el Laboratorio Argonne y la Universidad
de Mississippi. Esta implementación ejecuta sobre diferentes plataformas, redes de estaciones de trabajo Sun,
SGI, RS6000, HP, DEC, Alpha, y multicomputadores como el IBM SP2, Meiko CS-2 y Ncube.

Unify [14], disponible en la Universidad del Estado de Mississippi, es una implementación que permite el uso de

llamadas MPI y PVM de forma simultanea dentro del mismo programa.

2

MPI-LITE [2] es una implementación multithread de MPI, que ofrece un núcleo para la creación, terminación y
planificación de threads de usuario. Esta implementación es la única conocida por los autores que ofrece un cierto
soporte para la ejecución de programas multithread. Sin embargo, el modelo que ofrece MPI-LITE es muy rígido,
puesto que los threads son de usuario, cada thread ejecuta una copia de un programa MPI, y además, el número
de threads en el programa es fijo y se especifica como un argumento de entrada a un programa MPI.

Ninguna de estas implementaciones, a excepción de MPI-LITE, puede ser utilizada para ejecutar programas MPI
multithread en estaciones de trabajo con Linx, y como se comentó anteriormente MPI-LITE ofrece un modelo muy poco
flexible que no puede emplearse en programas donde se creen y destruyan threads de forma dinámica.

4 Descripción de MiMPI

MiMPI es una nueva implementación de MPI cuyos objetivos de diseño son:

Ser una implementación de MPI adecuada para la ejecución de aplicaciones multithread, es decir, una imple-

mentación MT-safe.

Utilizar threads para su implementación con el objetivo de mejorar el rendimiento de ciertas operaciones, como

por ejemplo, las no bloqueantes y colectivas (ver figura 1).

Analizar la adecuación del uso de threads en diferentes estrategias a utilizar en la implementación de ciertas

operaciones de paso de mensajes.

Asegurar la portabilidad entre diferentes arquitecturas.

Ofrecer un entorno integrado de herramientas gráficas para el arranque de procesos, visualización y depuración de

la ejecución paralela de programas que utilicen MiMPI.

Figura 1: Implementación de operaciones colectivas en MiMPI

MiMPI se ha estructurado en tres niveles (ver figura 2):

Capa de servicios básicos independiente de la plataforma.

Micro-núcleo de comunicaciones, denominado XMP.

Capa de servicios que implementa la interfaz MPI.

La capa de servicios básicos pretende independizar de la pl