Universidad Nacional de San Agustín
Escuela Profesional de
Ciencia de la Computación
Programación Paralela
Parallel Odd-Even Sort
Docente: Integrantes:
Ing. Alvaro Lazo, Jesus
Salazar,Kevin
Guardia,Alfred
Tamo, Erika
April 23, 2019
1 ¿La Burbuja se puede paralelizar?
void Bubble s o r t (
int a [ ] ; /∗ in / out ∗/ ,
int n ; /∗ in ∗/ ) {
i n t l i s t length , i , temp ;
for ( l i s t length = n ; l i s t l e n g t h >= 2 ; l i s t
length )
for ( i = 0 ; i < l i s t length 1 ; i ++)
if (a[ i ] > a [ i +1]) {
temp = a [ i ] ;
a[ i ] = a[ i +1];
a [ i +1] = temp ;
}
No tiene mucho sentido intentar paralelizar este algoritmo de burbuja de-
bido al orden secuencial inherente de las comparaciones. A continuación se
explicará el algoritmo odd-even sort el cual, a final de cuentas, "burbujea" los
elementos.
2 Odd-even sort
Para iniciar la explicación de cómo funciona el programa tenemos la figura 1,
de la cual tenemos lo siguiente:
1. Digamos que los datos a ordenar están representados por variables que
guardan un orden entre sí, el la figura 1 estas variables son a,b,c,d,e,f,g,h.
2. Cada procesador trabajará con una variable, en la figura los procesadores
son representados por los números circunscritos.
3. A cada iteración del algoritmo se le llama "fase"; es decir, hace fase 0,
fase 1, fase 2, fase 3, etc, hasta que note que todas las variables están
1
Figure 1: Las variables.
ordenadas, se verá que en el peor caso la cantidad de fases es igual al
número de procesadores.
void S o r t ( . . . ) {
...
f o r ( phase = 0 ; phase <p ; phase + + ) {
Odd_even_iter ( . . . ) ;
// v e r i f i c a i n t e r c a m b i o s , puede l l e v a r a un
// break d e l f o r , se v e r ma’ s a d e l a n t e
}
...
}
4. Las agrupaciones (líneas de color rojo) que se ven arriba de las variables
representan la forma en la que las variables, a través de los procesadores,
toman sus parejas durante las fases pares y las que se ven abajo, las im-
pares. Notemos que, en el ejemplo, las fases impares no consideran las
variables a, h, por lo tanto los procesadores 0 y 7, en esta fase, no harán
actividades.
Si cada variable representa un número, entonces el odd-even sort hará lo sigu-
iente:
Fases:
2
Figure 2: Las variables como números.
0) 7, 8, 5, 6, 3, 4, 1, 2
1) 7, 5, 8, 3, 6, 1, 4, 2
2) 5, 7, 3, 8, 1, 6, 2, 4
3) 5, 3, 7, 1, 8, 2, 6, 4
4) 3, 5, 1, 7, 2, 8, 4, 6
5) 3, 1, 5, 2, 7, 4, 8, 6
6) 1, 3, 2, 5, 4, 7, 6, 8
7) 1, 2, 3, 4, 5, 6, 7, 8
Detalle: vemos como, por ejemplo, el número 2 y el 8 "burbujean" a su posi-
ción.
Notemos que nos hemos colocado en un peor caso, en el cual los números
tienen el orden inverso al que se busca establecer, entonces la cantidad de fases
máxima que odd-even sort puede llegar a iterar es igual a la cantidad de proce-
sadores. Pero hay que considerar que debemos parar cuando notemos que ya
se ha conseguido que todos los elementos están ordenados.
Veamos la figura 3.
¿Cómo realiza MPI la comparación entre dos variables? Apoyados en la
figura 3 decimos lo siguiente:
• Recordemos que un procesador está asociado a una variable, y que los
procesadores y su memoria son independientes unos de otros.
• Entonces si la variable a se quiere comparar con la variable b no pueden
referenciarse la una a la otra; en lugar de ello, la variable a debe recibir
una copia de b y b una copia de a. En la imagen la copia se representa
por el cuadrado rojo.
3
Figure 3: Las variables como listas.
• Ahora que cada procesador tiene ambas variables, puede compararlas y
decidir que la menor o la mayor, según convenga, asuma el lugar de su
variable original.
• El "según convenga" que se acaba de mencionar se rige por lo siguiente:
Nos apoyamos de la figura 1 para clarificarlo. Si el procesador
es par y estamos en una fase par, entonces él debe contener la variable
menor y el procesador que tiene por pareja debe contener la mayor para
que así se tengan ordenadas las variables en esa pareja.
• Ahora supongamos que las variables son listas, donde a representa "6,
8, 30" y b, "2, 5, 50", ambas listas están ordenadas pues se toma como
invariante que las variables tienen una estructura ordenada, si tomamos
la variable como un número como en el ejemplo1, este único número se
4
considera ordenado.
• Decíamos que "cada procesador tiene ambas variables", así cada proce-
sador tendrá ambas listas ("6, 8, 30" y "2, 5, 50"), "comparará las vari-
ables y sustituirá la suya con la que le convenga"; es decir, el procesador
comparará las listas y sustituirá la suya por la que tenga los elementos
menores/mayores a los de su compañero (para que la pareja a y b esté
ordenada), esto quiere decir que, como se ve en la figura 3, a tendrá "2,
5, 6" y b tendrá "8, 30, 50". Notemos que si a ha variado es porque se ha
dado un intercambio con b.
/∗−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
∗ Function : Odd_even_iter
∗ Purpose : One i t e r a t i o n o f Odd−even
transposition sort
∗ In a r g s : l o c a l _ n , phase , my_rank , p , comm
∗ In/out a r g s : l o c a l _ A
∗ Scratch : temp_B , temp_C
∗/
void Odd_even_iter ( i n t l o c a l _ A [ ] , i n t temp_B [ ] , i n t
temp_C [ ] ,
i n t l o c a l _ n , i n t phase , i n t even_partner , i n t
odd_partner ,
i n t my_rank , i n t p , MPI_Comm comm, i n t
&i n t e r c a m b i o s ) {
MPI_Status s t a t u s ;
i f ( phase % 2 == 0 ) {
i f ( e v e n _ p a r t n e r >= 0 ) {
MPI_Sendrecv ( local_A , l o c a l _ n , MPI_INT ,
even_partner , 0 ,
temp_B , l o c a l _ n , MPI_INT , even_partner , 0 ,
comm,
&s t a t u s ) ;
i f ( my_rank % 2 ! = 0 )
Merge_high ( local_A , temp_B , temp_C ,
local_n ) ;
else
Merge_low ( local_A , temp_B , temp_C ,
local_n , intercambios ) ;
}
} e l s e { /∗ odd phase ∗/
i f ( odd_partner >= 0 ) {
MPI_Sendrecv ( local_A , l o c a l _ n , MPI_INT ,
odd_partner , 0 ,
5
temp_B , l o c a l _ n , MPI_INT , odd_partner , 0 ,
comm,
&s t a t u s ) ;
i f ( my_rank % 2 ! = 0 )
Merge_low ( local_A , temp_B , temp_C ,
local_n , intercambios ) ;
else
Merge_high ( local_A , temp_B , temp_C ,
local_n ) ;
}
}
} /∗ Odd_even_iter ∗/
/∗−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
∗ Function : Merge_low
∗ Purpose : Merge t h e s m a l l e s t l o c a l _ n elements
i n my_keys
∗ and r e c v _ k e y s i n t o temp_keys . Then
copy temp_keys
∗ back i n t o my_keys .
∗ In a r g s : local_n , recv_keys
∗ In/out a r g s : my_keys
∗ Scratch : temp_keys
∗/
void Merge_low (
i n t my_keys [ ] , /∗ i n /out ∗/
i n t recv_keys [ ] , /∗ i n ∗/
i n t temp_keys [ ] , /∗ s c r a t c h ∗/
int local_n , /∗ = n/p , i n ∗/
i n t &i n t e r c a m b i o s ) {
i n t m_i , r _ i , t _ i ;
m_i = r _ i = t _ i = 0 ;
while ( t _ i < l o c a l _ n ) {
i f ( my_keys [ m_i ] <= r e c v _ k e y s [ r _ i ] ) {
temp_keys [ t _ i ] = my_keys [ m_i ] ;
t _ i ++; m_i ++;
} else {
temp_keys [ t _ i ] = r e c v _ k e y s [ r _ i ] ;
t _ i ++; r _ i ++;
i n t e r c a m b i o s ++;
}
}
6
memcpy( my_keys , temp_keys , l o c a l _ n ∗ s i z e o f ( i n t ) ) ;
} /∗ Merge_low ∗/
Ahora, sabiendo que las variables a, b, c, d, e, f, g, h pueden ser listas, surge
la pregunta de cuándo podemos asegurar que la lista global, formada por la
"concatenación" de todas, está ordenada y así salir de la iteración del algoritmo
antes de llegar a la fase máxima. En la figura 1 vemos que si en la fase 0 no
han existido intercambios es porque a<b, c<d, e<f, g<h, lo cual indica que las
parejas están ordenadas pero no indica que estén ordenadas entre ellas, si ver-
ificamos esto la lista global estará ordenada. La fase 1 verificará ello si no logra
hacer intercambios. Así, si tenemos parejas sueltas cuyo par están ordenados y
luego verificamos que las parejas están ordenadas unas con otras diremos que
la lista global está ordenada; en otras palabras, la lista global estará ordenada
si durante una fase, excepto la primera, no se ha dado intercambio alguno en
las parejas.
/∗−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
∗ Function : Sort
∗ Purpose : S o r t l o c a l l i s t , use odd−even s o r t
to so r t
∗ global l i s t .
∗ Input a r g s : l o c a l _ n , my_rank , p , comm
∗ In/out a r g s : l o c a l _ A
∗/
void S o r t ( i n t l o c a l _ A [ ] , i n t l o c a l _ n , i n t my_rank ,
i n t p , MPI_Comm comm) {
i n t phase ;
i n t ∗temp_B , ∗temp_C ;
i n t e v e n _ p a r t n e r ; /∗ phase i s even or
l e f t −l o o k i n g ∗/
i n t odd_partner ; /∗ phase i s odd or
r i g h t −l o o k i n g ∗/
/∗ Temporary s t o r a g e used i n merge− s p l i t ∗/
temp_B = ( i n t ∗ ) malloc ( l o c a l _ n ∗ s i z e o f ( i n t ) ) ;
temp_C = ( i n t ∗ ) malloc ( l o c a l _ n ∗ s i z e o f ( i n t ) ) ;
/∗ Find p a r t n e r s : n e g a t i v e rank => do nothing
during phase ∗/
i f ( my_rank % 2 ! = 0 ) {
e v e n _ p a r t n e r = my_rank − 1 ;
odd_partner = my_rank + 1 ;
i f ( odd_partner == p ) odd_partner =
MPI_PROC_NULL ; // I d l e during odd phase
} else {
7
e v e n _ p a r t n e r = my_rank + 1 ;
i f ( e v e n _ p a r t n e r == p ) e v e n _ p a r t n e r =
MPI_PROC_NULL ; // I d l e during even phase
odd_partner = my_rank − 1;
}
/∗ S o r t l o c a l l i s t using b u i l t −i n quick s o r t ∗/
q s o r t ( local_A , l o c a l _ n , s i z e o f ( i n t ) , Compare ) ;
# i f d e f DEBUG
p r i n t f ( " Proc %d > b e f o r e loop i n s o r t \n " , my_rank )
;
f f l u s h ( stdout ) ;
# endif
i n t intercambios = 0 ;
i n t f i n ;//suma de i n t e r c a m b i o s
f o r ( phase = 0 ; phase <p ; phase + + ) { // f i n ==0 y f a s e
// >0 , para
Odd_even_iter ( local_A , temp_B , temp_C , l o c a l _ n ,
phase ,
even_partner , odd_partner , my_rank , p ,
comm, i n t e r c a m b i o s ) ;
MPI_Reduce(& i n t e r c a m b i o s , &f i n , 1 , MPI_INT ,
MPI_SUM, 0 , MPI_COMM_WORLD) ;
i f ( my_rank = = 0 ) {
p r i n t f ( " I n t e r c a m b i o s en f a s e %d : %d\n " ,
phase , f i n ) ;
f o r ( i n t i = 0 ; i <p ; i + + ) {
MPI_Send(& f i n , 1 , MPI_INT , i ,0 ,
MPI_COMM_WORLD) ; / / 0 e n v a l a i n f o
de f i n a todos
}
MPI_Status s t a t u s ;
MPI_Recv(& f i n , 1 , MPI_INT , 0 , 0 , MPI_COMM_WORLD,
&s t a t u s ) ; //todos r e c i b e n l a i n f o de f i n
//para ver s i paran
i f ( f i n ==0 && phase > 0 ) {
i f ( my_rank = = 0 ) {
p r i n t f ("% s\n " , " No se l l e g a l peor caso ,
listas locales : " ) ;
8
}
P r i n t _ l o c a l _ l i s t s ( local_A , l o c a l _ n , my_rank ,
p , comm ) ;
break ;
}
intercambios = 0 ;
}
f r e e ( temp_B ) ;
f r e e ( temp_C ) ;
} /∗ S o r t ∗/
9
3 Ejecutando paso por paso el algoritmo
Figure 4: Ejecutando el algoritmo en una lista de tamaño 16 subdividida en
subarreglos de tamaño 4.
10
3.1 ¿Por qué el algoritmo usa 4 fases?
Supongamos que tenemos un arreglo de 16 y 4 procesadores entonces para
ordenarlo se divide el arreglo en subarreglo de tamaño 4 y se da cuenta que
despues del primera fase even el proceso 3 tiene los números minimos de todo
el arreglo entonces necesita 3 pasos para ir del proceso 3 al 0.
4 Resultados
Hicimos pruebas con dos computadoras:
• Con un computador i3 hp
• Con un computador i5 de 6ta generación Dell
Con la primera computadora se muestra el siguiente resultado.
Con la segunda computadora se muestra lo siguiente.
11