Mejora de la localidad en operaciones de E/S colectivas no contiguas XVIII Jornadas de Paralelismo, JP’2007 Rosa Filgueira, David E. Singh, Florin Isaila,

Mejora de la localidad en operaciones de E/S colectivas no contiguas

XVIII Jornadas de Paralelismo, JP’2007

Rosa Filgueira, David E. Singh, Florin Isaila, Jesús Carretero, Antonio G.

Loureiro

Índice

• Descripción del problema.

• Objetivos principales.

• Escritura no contigua de la técnica TwoPhase I/O.

• Optimización de escritura no contigua de la técnica TwoPhase I/O.

• Caso de estudio: BIPS3D.

• Evaluación.

• Conclusiones.

Descripción del problema

• Optimización de la escritura no contigua en la técnica TwoPhase I/O en Romio:

– La técnica TwoPhase I/O se utiliza para la escritura/lectura colectiva de datos contiguos y no contiguos.

– En este trabajo, nos centramos en la escritura no contigua, y esta se realiza en dos fases:

• 1ª fase: Intercambio de datos entre los procesos que intervienen en la escritura.

• 2ª fase: Escritura colectiva de datos en disco.

Descripción del problema

• Antes de realizar estas dos fases:– Se divide el conjunto de datos a escribir en

disco en distintas porciones. (File Domain o FD) .

– Se asigna cada FD a un proceso. Y cada proceso se encarga de escribir a disco los datos pertenecientes a su FD.

• Problema: La asignación de FD a cada proceso es fija.

Fd0 Fd1 Fd2 Fd3

4 procesosVector datos

Distribución de los datos

Objetivos principales

• Modificar la asignación de FD de forma automática Dependiente de la distribución de datos en los procesos.

• Con esta modificación queremos disminuir :

– Volumen de datos a intercambiar entre procesos en la fase 1.

– Número de mensajes a enviar y recibir.

– Tiempo de escritura no contigua en la técnica TwoPhase I/O.

Escritura no contigua de la técnica TwoPhase I/O en ROMIO

• Vector P :vector de enteros escrito en disco por 4 procesos.

• Vector P0: distribución del vector P en los procesos.


• Cada proceso:– Analiza que partes del vector P tiene

almacenados creando una lista de comienzos (offsets) y otra de longitudes (lenghts):

• El proceso 0, tiene tres intervalos:– El del valor 1 (offset=0,lenght=4)– El del valor 6 y 7 (offset=20,lenght=8)– El del valor 11(offset=40,length=4)

– Calcula el primer y último byte que tiene almacenado del vector P:

• Para el proceso 0:– El primer byte es el 0– El último byte es el 43

– Comunica al resto al resto su inicio y final creándose dos listas globales ordenadas por ID de proceso:

• Lista de inicios global: 0,20,52,4• Lista de finales global: 43,47,63,31

– Máximo final global=63– Mínimo inicio global=0


• Dividir el fichero entre los procesos en porciones (File Domain o FD)

• El File Domain tiene 3 valores:– Tamaño de la porción de datos.– Primer byte de la porción de datos.– Ultimo byte de la porción de datos.

• Para asignar cada FD a su proceso :– Se calcula el tamaño total de datos

en bytes (máximo final global - mínimo inicio global) + 1 = 64 bytes.

– Se divide el tamaño entre número de procesos 16 bytes.

– Se crea dos listas con tantas posiciones como procesos y se aplica una distribución por bloques del fichero (FD_inicio y FD_fin)


• Fase 1: Cada proceso analiza que datos no tiene almacenados pertenecientes a su FD y a que proceso se los debe pedir.


• Fase 2: Intercambio de datos entre procesos y escritura colectiva en disco.

Optimización de escritura no contigua de la técnica TwoPhase I/O en ROMIO

• Cambiar la asignación del FD por una asignación dependiente de la distribución de datos en los procesos.

• A esta variante la llamamos: Locality-Aware Two Phase I/O (LA-TwoPhase I/O).


• Calcular el número de intervalos en los que podemos dividir el fichero:

– Dividir el tamaño de datos entre el tamaño del FD 64 / 16 = 4

• Crear una lista con tantas posiciones como intervalos existan.

• Cada posición de la lista representa el proceso que tiene más datos almacenados localmente para ese intervalo.


• Para obtener el resultado de esta lista se construye la siguiente matriz:

• Se recorre por columnas, asignando cada intervalo aquel proceso:– Tenga más elementos almacenados para ese

intervalo.– No haya sido asignado previamente.

• Lista de intervalos: 3, 0, 1, 2

Int/Proc 0 1 2 3

0 1 2 1 0

1 0 1 3 0

2 0 0 0 4

3 3 1 0 0


• Calculo del FD de cada proceso a partir de la lista de intervalos:– El tamaño del FD sigue siendo el anterior.

– El primer byte del FD será el primer byte de su intervalo.

– El último byte del FD será el último byte de su intervalo.


• Las siguientes fases de la técnica LA-TwoPhase I/O son iguales que la versión original.

• Se ha reducido el número de comunicaciones (de 28 datos a 8).


• Por último cada proceso escribe en disco un conjunto de datos consecutivos.

Caso de estudio: BIPS3D

• BIPS3D es un simulador paralelo de dispositivos semiconductores basado en elementos finitos.

• Parte de una malla que representa un transistor y de un conjunto de parámetros físicos.

• Esta malla es particionada (METIS) y distribuida (MPI) entre los procesadores.

• Cada proceso realiza el proceso de simulación .

• Cuando terminan se manda los datos a un fichero paralelo (PVFS) utilizando la técnica TwoPhase I/O para la escritura en disco.

Evaluación

• Se han realizado las pruebas en BIPS3D utilizando :

– Distintas mallas, volúmenes de datos y número de procesadores (4 y 8).

– El BIPS3D tiene asociada una estructura de datos a cada nodo de la malla, y son los datos a escribir a disco. El número de elementos de la estructura se llama Carga.

Malla 1 Malla 2 Malla 3 Malla 4

Nodos 47219 32888 73260 289650

Vertices 305120 210437 416950 2027885

Mallas

Tamaño MBMalla 1 Malla 2 Malla 3 Malla 4

Carga 100 18 12 28 110

Carga 200 36 25 56 221

Carga 500 90 63 140 552

Evaluación

• Las pruebas han sido realizadas en un cluster de 16 procesadores (PIII 800 MHz,256KB L2cache,1GB memoria) con una red Fast Ethernet.

• Se ha utilizado la distribución MpichGM 2.7.15NOGM:

– Para obtener las medidas de tiempos de la técnica original.

– Sobre esta distribución se ha hecho las modificaciones para obtener LA-TwoPhase I/O.

Evaluación

• El programa se ha ejecutado para cada configuración almacenando:

– El tiempo en disco.

– El volumen de datos transferidos.

– El número de comunicaciones que se realizan.

Evaluación

• Se observa que la técnica LA-TwoPhase I/O tiene mejores resultados que la original.

• Demuestra: Reducir el número de datos intercambiados, reduce el tiempo de escritura .

0,0

5,0

10,0

15,0

20,0

25,0

30,0

% M

ejo

ra e

n t

iem

po

de

escr

itu

ra 4

p

roce

sos

Mesh1 Mesh2 Mesh3 Mesh4

Carga 100 Carga 200 Carga 500

-10,0

-5,0

0,0

5,0

10,0

15,0

20,0

25,0

30,0

35,0

% M

ejo

ra e

n t

iem

po

de

escr

itu

ra 8

p

roc

eso

s

Mesh1 Mesh2 Mesh3 Mesh4

Carga 100 Carga 200Carga 500

Evaluación

• También se ha reducido el volumen de datos

transferidos: – LA-TwoPhase tiene más datos pertenecientes

a su FD almacenados en local y necesita realizar menos peticiones.

0,0

5,0

10,0

15,0

20,0

25,0

30,0

35,0

40,0

Mesh 1 Mesh 2 Mesh 3 Mesh 4

% M

ejo

ra d

el

Vo

lum

en D

ato

s

4 procesos 8 procesos

16 procesos 64 procesos

Evaluación

• Al reducirse el volumen de datos a transferir también se reduce el número de comunicaciones.

0,0

2,0

4,0

6,0

8,0

10,0

12,0

Mesh 1 Mesh 2 Mesh 3 Mesh 4

% M

ejo

ra C

om

un

icac

ion

es

4 procesos 8 procesos 16 procesos 64 procesos

Conclusiones

• Se ha presentado una nueva propuesta llamada Locality-Aware TwoPhase I/O para escrituras colectivas no contiguas que consigue:

– Asignar el FD dependiendo de la distribución inicial de los datos.

– Reducir las comunicaciones entre procesos.

– Reducir el volumen de datos transferidos entre procesos.

– Reducir el tiempo de escritura en disco.

Documents

Mejora de la localidad en operaciones de E/S colectivas no contiguas XVIII Jornadas de Paralelismo, JP’2007 Rosa Filgueira, David E. Singh, Florin Isaila,