1 Procesamiento Paralelo Curso 13/142, 3, 2 3, 2 Computadores Paralelos Programación basada en paso de mensajes Técnicas básicas de programación paralela Compulsiva, Divide y Vencerás, Pipeline, Síncrona, Equilibrado de carga y Terminación Programación basada en memoria común Algoritmos y aplicaciones Ordenación, …

2 Procesamiento Paralelo Temario ordenación-2Algoritmos de ordenación Introducción Comparar e intercambiar Burbuja y transposición par-impar Ordenación bidimensional Ordenación por Mezcla QuickSort Ordenación y Mezcla “bitonic” Counting, Radix y Sample

3 proPar Introducción ordenación-3¿Coste de ordenar (seg:mSeg)? Burbuja SelecDir InserDir quickSort 4:054 1:956 1:444 0:146 1976 Wirth Pascal CDC 6400 V[512] 42.000 3:400 0:745 0:368 0:004 84.000 13:530 2:972 1:477 0:013 54:064 11:844 5:865 0:025 Burbuja SelecDir InserDir quickSort proPar C Core 2 Quad Q6600 2007 -O3 ¿Ordenación externa? O(n2) O(nlogn) 6:084 12:588 ¿Conclusiones? quickSort más rápido y comparativamente mejor según aumenta V[] ¿Acelaración alcanzable? O(log n) con n procesadores ¡difícil!

4 proPar Introducción ordenación-4quickSort * 2.400↓ 512 QuadCore * Pentium D 29.000 Core i7 3ª generación 2012

5 proPar Introducción ordenación-5 Tesis: “Algoritmos de Ordenación Conscientes de la Arquitectura y las Características de los Datos Dani Jiménez González – UPC – Mayo 2004

6 proPar Introducción ordenación-6Rank Sort: Dificultad de alcanzar O(log n) con n procesadores Idea: Ubicar cada elemento de A[] en su hueco en B[] 10 15 4 33 8 25 40 2 A B 4 33 8 25 40 2 Restricciones: Necesario array auxiliar Falla si repetidos 10 15 for (i=0; i iDest = 0; for (j=0; j if (A[j] < A[i]) iDest++; B[iDest] = A[i]; } forall (i=0; i iDest = 0; for (j=0; j if (A[j] < A[i]) iDest++; B[iDest] = A[i]; } ¿Código paralelo? Sólo consigo O(n) con n Pi

7 proPar Introducción ordenación-7Rank Sort: ¿Alcanzable O(log n) con más de n procesadores? 10 15 4 33 8 25 40 2 A B 10 15 4 33 8 25 40 2 A iDest 3 iDest++ forall (i=0; i iDest = 0; for (j=0; j if (A[j] < A[i]) iDest++; B[iDest] = A[i]; } Conclusiones: ¿Paralelizable? Necesarios n(n-1) Pi  n2 O (3) PRAM CRCW ¿Viable?

8 proPar Introducción ordenación-8Rank Sort: Alcanzable O(log n) con n2 procesadores 10 15 4 33 8 25 40 1 2 0/1 0/1/2 0/1/2/3/4 ¡ Eficiencia por los suelos y modelo memoria común !

9 proPar Comparar e intercambiar ordenación-9Evita tener array auxiliar ¿Paralelizar con paso mensajes? if (A[i] > A[j]) { tmp = A[j]; A[j] = A[i]; A[i] = tmp; } Código básico 10 15 4 33 8 25 40 2 A i j 10 15 4 33 8 25 40 2 Supongamos número por Pi ¿Cómo sería el código básico? 10 4 8 40 4 10 8 40 4 15 10 33 8 25 40 2 A 4 10 8 40 15 33 2 25

10 proPar Comparar e intercambiar (dos versiones) ordenación-10Versión 1 A B Versión 2 > > env (Pb, &A); rec (Pb, &A); rec (Pa, &A); if (A > B) { env (Pa, &B); B = A; } else env (Pa, &A); env (Pb, &A); rec (Pb, &B); if (A>B) A = B; rec (Pa, &A); env (Pa, &B); if (A>B) B = A; ¿ (A>B) igual resultado en Pa y Pb?

11 proPar Comparar e intercambiar (agrupar) ordenación-11512 128 4 Cada Pi mantiene su grupo ordenado V[N] y P procesadores => N/P números por Pi Versión 1 88 50 28 25 98 80 43 42 Números originales ¿Necesidades de memoria? 98 88 80 50 43 42 28 25 Mezcla 88 50 28 25 43 42 28 25 Números finales Devolver los menores

12 proPar Comparar e intercambiar (agrupar) ordenación-12512 128 4 V[N] y P procesadores => N/P números por Pi Versión 2 88 50 28 25 98 80 43 42 Números originales 98 88 80 50 43 42 28 25 Mezcla 88 50 28 25 98 80 43 42 Guardar los mayores los menores

13 proPar Burbuja y ............... ordenación-13Idea: Pasadas y en cada una intercambios => Mayores colocándose 4 2 1 8 5 7 3 6 for (i=n-1; i>0; i--) for (j=0; j if (A[j] > A[j+1]) swap(A[j], A[j+1]); 2 4 1 8 5 7 3 6 2 1 4 8 5 7 3 6 2 1 4 8 5 7 3 6 2 1 4 5 8 7 3 6 En la primera pasada, el mayor en su sitio 1 2 4 5 7 3 6 8 Segunda pasada ¿ Paralelizable ?

14 proPar Burbuja y ............... ordenación-14Idea: Solapar pasadas  “pipeline” 4 2 1 8 5 7 3 6 Puedo iniciar pasada 2 1 2 2 4 1 8 5 7 3 6 2 1 4 8 5 7 3 6 1 2 4 8 5 7 3 6 ¿ Código paralelo ?

15 proPar Burbuja y Transposición par-impar ordenación-15Idea: Pasadas de dos fases (intercambio par + intercambio impar) Par Pi pares con Pi+1 (derecha) 4 2 1 8 5 7 3 6 P0 P1 P2 P3 P4 P5 P6 P7 Pasada 1 Impar Pi impares con Pi+1 (derecha) 2 4 1 8 5 7 3 6 2 1 4 5 8 3 7 6 1 2 4 5 3 8 6 7 Pasada 2 ¿Cuándo parar? n-1 caso peor O(n) ¿ Código paralelo ?

16 proPar Burbuja y Transposición par-impar ordenación-16// Fase Par recibir(Pder, vOtro); enviar (Pder, vMio ); mezclar(vMio, vOtro, vAux); menores(vAux, vMio); // Fase Impar if (yo > 0) recibir(Pizq, vOtro); enviar (Pizq, vMio ); mayores(vAux, vMio); } Proceso Par recibir(Pizq, vOtro ); if (Pder < numProcesos) enviar (Pder, vOtro); recibir(Pder, vMio ); Proceso Impar P0 => Reparte (scatter) vector, , recoge (gather) Pi => Ordena “burbuja” su trozo y transposición ..... ?

17 proPar Burbuja y Transposición par-impar ordenación-17¿Cuáles son los tiempos esperados? 42.000 3:400 84.000 13:530 54:064 burbuSec burbuPar 2 4 6 8 Eficiencia 1,97 3,94 5,79 7,53 ¿Cada vez mejor? ¿Truco? 0:856 3:421 0:865 0:407 13:693 3:434 1:557 0:235 0:897 0:224 0:113 0:074 0:004 0:013 0:025 quickSort Sin embargo

18 proPar Ordenación bidimensional ordenación-18Si disponemos de una malla 2D ¿Cómo ordenar? Como si fuese un array lineal “serpenteante” y con transposición par-impar O(n) No se aprovecha la malla ¿Límite inferior en ordenación malla 2D => n * n ? 2(n –1) => O(n) Scherson, Sen y Shamir (1986) “shearsort” esquilar n (log n + 1)

19 proPar Ordenación bidimensional “shearsort” ordenación-19Impares: 1,3,5,... => Por filas tipo “serpenteante” Pares: 2,4,6,... => Por columnas “menores arriba” Fases 1,2,3,4, ..., M log n + 1 2 4 8 16 13 10 1 5 7 14 3 15 12 11 9 6 “Filas” min max max min 2 “Cols” 1 4 7 5 8 12 11 9 3 6 14 16 13 10 15 min max 4 14 8 10 3 13 7 15 1 2 16 5 12 6 11 9 ¿ Código paralelo ? 1 3 4 8 6 5 9 11 12 7 2 14 16 15 13 10 “Filas” 1 2 3 8 7 6 9 10 11 4 5 12 16 15 14 13 “Filas” 1 3 4 8 6 5 9 11 12 2 7 10 16 15 13 14 “Cols”

20 proPar Ordenación bidimensional “shearsort” ordenación-20Impares: 1,3,5,... => Por filas tipo “serpenteante” Pares: 2,4,6,... => Por columnas “menores arriba” Fases 1,2,3,4, ..., M log n + 1 2 4 8 16 13 10 1 5 7 14 3 15 12 11 9 6 “Filas” min max max min 2 “Cols” 1 4 7 5 8 12 11 9 3 6 14 16 13 10 15 min max 4 14 8 10 3 13 7 15 1 2 16 5 12 6 11 9 1 3 4 8 6 5 9 11 12 7 2 14 16 15 13 10 “Filas” ¿Cuáles son los tiempos esperados? 42.025 [205x205] 3:410 84.100 [290x290] 13:610 [410x410] 54:250 burbuSec shearSec 0:286 0:670 1:886 0:006 0:013 0:022 quickSec

21 proPar Ordenación bidimensional “transponer” ordenación-21Idea: Haciendo transposición, podemos trabajar sólo por filas C F 2 4 8 16 13 10 1 5 7 14 3 15 12 11 9 6 T 2 16 1 4 13 5 8 10 7 12 11 9 14 3 15 6 T 1 2 12 4 5 11 7 8 9 16 13 10 3 6 14 15 Fc T F Fc Asignación de una fila por Procesador Transposición eficiente con MPI_ALL_TO_ALL

22 proPar Ordenación por Mezcla ordenación-22Idea: Dividir y mezclar las partes (Similar a divide y vencerás) 10 1 13 5 7 8 14 2 6 15 16 3 11 12 4 9 Muy ineficiente dividir 10 1 13 5 7 8 14 2 6 15 16 3 11 12 4 9 ¿ Código ? P0 P1 P3 P2 P5 P4 P7 P6 mezclar 13 5 12 11 10 1 14 2 8 7 16 3 15 6 9 4

23 proPar Ordenación por Mezcla ordenación-23Mejora: Dividir en trozos grandes y mezclar las partes Ordeno partes (rankSort) Proceso de mezcla ¿Paralelo? ¿Secuencial? ¿ Cómo afectará el número de trozos?

24 proPar Ordenación por Mezcla ordenación-24Medida de tiempos variando el número de trozos rankSec Trozos Tiempo 1 2 4 6 8 10 12 14 16 20 100 200 300 500 1000 2000 8:822 4:414 2:214 1:479 1:110 0:888 0:744 0:638 0:560 0:451 0:112 0:081 0:108 0:189 0:368 rankPar 2:209 0:561 0:261 0:159 0:107 0:082 0:067 0:061 0:046 quickSort en 0,013

25 proPar Quicksort Paralelo ordenación-25Divide y vencerás tipo Árbol pivote 4 P0 P4 P2 P6 P5 4 2 7 8 5 1 3 6 Componer las sublistas ordenadas 2 1 3 4 7 8 5 6 2 7 1 2 3 4 7 8 5 6 ¿Paralelización?

26 proPar Quicksort Paralelo ordenación-26Ubicando pivotes en su destino final 2 7 8 5 1 3 6 pivote 4 4 2 7 1 3 5 8 6 Puede que muy desequilibrado

27 proPar Quicksort Paralelo ordenación-27Reparto de trabajo modelo Granja de Procesadores ¿ Mejor con hipercubo ?

28 proPar Quicksort Paralelo ordenación-28Otra idea más adaptada a modelo cluster: El array repartido entre todos los nodos (antes y después) ¡ Repetir a las partes ! pivote P0 P1 P2 P3 P0 P1 P2 P3 Una fase quickSort P0 P1 P2 P3 Un intercambio ≤ > ≤ >

29 proPar Quicksort Paralelo ordenación-29Otra idea más adaptada a modelo cluster (Bis): El array repartido entre todos los nodos (antes y después) ¿ Sublistas equilibradas? ¡ Ordenar cada trozo ! P0 P1 P2 P3 > ≤ P0 P1 P2 P3 Una fase quickSort ≤ > P0 P1 P2 P3 Más grandes Un intercambio Mayores Menores pequeños

30 proPar Quicksort Paralelo ordenación-30Medida de tiempos variando #muestras para elegir el pivote [PC9] mpirun –np 8 quickPar #muestras #muestras Tiempo Ocupación Min .. Max % 10 1:417 51,6% 100 1:211 26,9% 1.000 1:026 6,9% 4.000 0:999 1,7% Escalabilidad: quickPar Cluster 6:027 3:235 1:981 1:995 1:558 1:360 1 2 4 8 16 32 Núcleos Tiempo Efici. 0,93 0,76 0,38 0,24 0,14 PC9 6:236 3:238 1:863 0:999 Tiempo Efici. 0,96 0,84 0,78

31 proPar Ordenación y Mezcla “bitonic” ordenación-31Secuencia bitónica estricta (dos sublistas: una crece y otra decrece) A = {a0, a1, a2, a3, ..., an-2, an-1} tal que: a0 < a1 < a2 < ... < ai-1 < ai > ai+1 > ai+2 > ... > an-2 > an-1 Ejemplo: 1 5 6 7 9 12 13 15 14 11 10 8 4 3 2 Compara y swap ai  ai+n/2 2 secuencias bitónicas 1 5 6 7 4 3 2 15 14 11 10 8 9 12 13 ¿Recursivo?

32 proPar Ordenación y Mezcla “bitonic” ordenación-32Ejemplos visuales:

33 proPar Ordenación y Mezcla “bitonic” ordenación-33Mezcla bitónica ejemplo completo 1 5 6 7 9 12 13 15 14 11 10 8 4 3 2 1 5 6 7 4 3 2 15 14 11 10 8 9 12 13 1 3 2 7 4 5 6 8 9 11 10 15 14 12 13 1 3 2 5 4 7 6 8 9 11 10 12 13 15 14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ¿Código paralelo?

34 proPar Ordenación y Mezcla “bitonic” ordenación-34Obtener secuencia bitónica a partir de secuencia desordenada SecBitónicas de 2 elementos ?

35 proPar Ordenación y Mezcla “bitonic” ordenación-35Construcción de secuencia bitónica a partir del desorden salto 1 7 1 6 13 9 12 5 15 8 3 10 2 11 4 14 1 7 13 6 9 12 5 8 15 10 3 2 11 14 4 sort 1 6 7 13 12 9 5 3 8 10 15 14 11 4 2 sort 2 1 1 5 6 7 9 12 13 15 14 11 10 8 4 3 2 sort 4 2 1

36 proPar Ordenación y Mezcla “bitonic” ordenación-36Código secuencial sin optimizar

37 proPar Ordenación y Mezcla “bitonic” ordenación-37Tiempos de ejecución Cardinalidad quickSort 0:031 0:129 1:170 5:048 bitonic 0:225 1:028 12:464 60:635 rankSec* 0:435 shearSec 3:883 5:420 160:891 60:014

38 proPar Counting sort (secuencial) ordenación-38Idea: Ranksort O(n2) puede convertirse en O(n) con ciertas condiciones A[] 1 7 2 5 3 4 6 31 0<=ai<2P 10 1 11 1 -- 19 16 22 3 4 2 ++ ¿Cuántas veces aparece cada número? C[] 7 3 5 8 4 2 20 17 12 4 32 29 27 23 Sumas prefijo C[] 20 17 12 3 32 29 27 23 Ubicar A[] en B[] 2 5 3 1 4 7 6 17 12 29 27 23 20 B[] 31 ¡Estable! O (n+p+n) ¿Código paralelo?

39 proPar Ordenación y Mezcla “bitonic” ordenación-39Tiempos de ejecución Cardinalidad quickSort 0:031 0:129 1:170 5:048 counting1 0:015 0:117 1:547 7:059 Counting1  Cardinalidad C[] = A[] counting2 0:007 0:034 0:456 2:061 Counting2  Cardinalidad C[] = A[] / 4 bitonic 0:225 1:028 12:464 60:635

40 proPar Radix sort ordenación-40Idea: Claves numéricas con una base => ordenar por dígitos 315 219 649 479 100 922 863 632 219 649 479 315 863 922 632 100 ¿Counting sort? 479 863 649 632 922 219 315 100 Counting sort 922 863 649 632 479 315 219 100 Counting sort Estabilidad fundamental Vector C[] pequeño

41 proPar Radix sort ordenación-41Jugar con más de un bit por pasada 101001 100001 111010 101011 011011 001101 101110 110011 011111 011010 110010 110111 110001 100101 100111 000101 101011 011011 110011 011111 110111 100111 111010 101110 011010 110010 101001 100001 001101 110001 100101 000101 011111 101110 001101 101011 011011 111010 011010 101001 110111 100111 100101 000101 110011 110010 100001 110001 111010 110111 110011 110010 110001 101110 101011 101001 100111 100101 100001 011111 011011 011010 001101 000101

42 proPar Sample sort ordenación-42Problemática de la ordenación mediante cubetas: 10.000 19.999 9.999 90.000 99.999 M-1 P0 P1 P9 Recolectar en mi cubeta Para todo Pi Ordenar mi cubeta Puede que muy desequilibrado Meter en cada cubeta ≈ misma cantidad de números ¡ Elegir 9 elementos frontera equiespaciados !

43 proPar Sample sort ordenación-43 10 100 Mezcla 1000 9

44 proPar Sample sort ordenación-44Datos antiguos FIN