Semana 1: Reporte - Ordenamiento por mezcla

Introducción.

Anteriormente, los diseñadores que hacían algoritmos asumían que una computadora solamente tenía un elemento a procesar, este tipo de algoritmos que se diseñan con este propósito son llamados secuenciales, ya que hacen una secuencia particular siguiendo ciertos pasos. 

Pero ahora, una computadora sencilla o incluso laptops, actualmente tienen múltiples procesadores, también existen clusters de computadoras los cuales por ejemplo, en el departamento de defensa de los Estados Unidos simulan una explosión nuclear y Google procesa sus búsquedas en ese tipo de computadoras. Por ejemplo, para el año pasado (2011), la Fujitsu K es considerada la supercomputadora más rápida del mundo con 68544 CPUs.

Supongamos, que cuando estemos graduados y trabajemos en el mundo real, nos encontraremos con problemas que necesitamos resolver con un sistema multiprocesador, por ejemplo, si tuviéramos una matriz de enteros y queremos poner todos los números enteros negativos en la matriz, podemos dividir la matriz en segmentos de igual tamaño, un segmento por cada procesador y el procesador de cada uno puede mostrar todos los números enteros negativos de su segmento, el algoritmo que utilizaríamos secuencialmente tomaría Θ(n), si utilizáramos el algoritmo multiprocesador cada procesador se encarga de un segmento de la matriz con un máximo de n / p elementos, por lo que el procesamiento de toda la matriz toma Θ(n/p).

Pero existen problemas de los cuales es difícil imaginar y diseñar el uso de múltiples procesadores para acelerar el tiempo de procesamiento, un ejemplo de esto es el orden de búsqueda a profundidad de un grafo: cualquier algoritmo se verá obligado a procesar a un nodo hijo sólo después de su nodo padre, así que, si la altura de la grafo fuera como n / 2,  es necesariamente Θ(n), En esta liga puedes ver dónde se demuestra que este problema es intrínsecamente secuencial. 

Modelos paralelos y distribuidos.

Existen diferentes sistemas con múltiples procesadores, pero hay dos categorías básicas: las computadoras paralelas y las computadoras distribuidas, de las cuales estaremos hablando durante todo el curso y en mi caso profundizar conceptos algorítmicos para los sistemas y como pueden ayudarnos para resolver problemas en el futuro laborar, éstos dos términos se utilizan con algunas coincidencias, pero por lo general un sistema paralelo, es aquél en el que los procesadores están estrechamente relacionados, mientras  que un sistema distribuido tiene procesadores que son más independientes el uno del otro.

Análisis de un algoritmo de multiproceso.

Ahora, para mi aportación de esta semana haré un análisis de un algoritmo multiproceso, lo cual escogí el que se me facilitara en entender para en semanas mas adelantes, ir viendo algoritmos mas complejos.

Un algoritmo de divide y vencerás, divide el problema a resolver en subproblemas, que son más fáciles de resolver que el problema original, resuelve los subproblemas y se combina las soluciones a los subproblemas para construir una solución al problema original.

El paradigma de divide y vencerás mejora la modularidad del programa y lleva a menudo a algoritmos simples y eficientes, por ello se ha demostrado ser una poderosa herramienta para los diseñadores de algoritmos secuenciales.

Divide y vencerás juega un papel aún más importante en el diseño de algoritmos paralelos, debido a que los subproblemas creados en el primer paso son regularmente independientes, pueden ser resueltos de forma paralela, a menudo los subproblemas se resuelven de forma recursiva, a consecuencia de esto, incluso los algoritmos de dividir y vencerás que se han diseñado para las computadoras secuenciales suelen tener algún paralelismo inherente. 

Como ejemplo de algoritmo utilizando divide y vencerás, haré un análisis del algoritmo de ordenamiento por mezcla de forma secuencial, para luego verlo de una perspectiva paralela.

El ordenamiento por mezcla, produce una secuencia ordenada por la clasificación de sus dos mitades y su mezcla. 

Tiene un tiempo de complejidad de Θ(n log(n)) y la complejidad en el espacio es Θ(n).

En primer lugar, la secuencia a ordenar se descompone en dos partes (divide), cada mitad esta ordenada de forma independiente (conquista o vence), a continuación, las dos mitades se arreglan ordenadamente (mezcla).

Podemos ver que este algoritmo resalta la importancia de la operación de intercalación:

Mergesort(A[1, n])
Merge( MergeSort(A[1, ⌊n/2⌋]), MergeSort(A[⌊n/2⌋ + 1, n]) )

El caso base de la recursión, es cuando consta en ordenar a un solo elemento, por lo tanto no es posible la reorganización. 

Un seguimiento de la ejecución de la ordenación por mezcla.

Primero, se determina un índice intermedio entre alto y bajo, después va de bajo a medio, de medio más uno a alto recursivamente, luego las dos mitades se mezclan ordenados por un procedimiento de mezcla, la recursión termina, cuando bajo es igual a alto, esto quiere decir que solo hay un elemento.

ordenMezcla(int bajo, int alto){
    if (bajo<alto) {

        int medio = (bajo+alto) / 2;
        ordenMezcla(bajo, medio);
        ordenMezcla(medio+1, alto);
        mezcla(bajo, medio alto);
    }
}

La eficiencia de este algoritmo, depende de la eficiencia con que se mezclan las dos mitades ordenadas, en una sola lista ordenada, para esto existen diferentes métodos, el cual yo escribiré es el más óptimo.

La variante mas óptima de mezcla, no copia todo el arreglo a otro, por lo tanto solo utiliza la mitad de espacio de memoria y también solo la mitad del tiempo, para copiar elementos de un arreglo auxiliar, entonces cuando todos los elementos de la primera mitad se han copiado de nuevo a una, los elementos restantes ya no se necesitan mover porque están en sus lugares adecuados, esto es como si se creara un espacio auxiliar para realizar las operaciones.

mezcla(int bajo, int medio, int alto) {
    int i, j, k;
    i=0;    
    j=bajo;
    
   //Primero la primera mitad se copia en un array auxiliar 
    while (j<=medio)
        auxiliar[i++]=arreglo[j++];
    i=0; 
    k=bajo;
    
    // Se copia el próximo elemento a cada rato.
    while (k < j && j <= alto)
        if (auxiliar[i]<=arreglo[j])
            arreglo[k++] = auxiliar[i++];
        else
            arreglo[k++] = arreglo[j++];
    // copia los elementos de la primera mitad (si es que hay)
    while (k<j)
        arreglo[k++] = auxiliar[i++];
}

En esta variante eficiente, la función mezcla 1.5n pasos, o sea, n / 2 pasos para copiar la primera mitad al array auxiliar, n / 2 pasos para copiar de nuevo al arreglo y n / 2 pasos para la segunda mitad, esto produce un tiempo de ejecución de ordenación por mezcla de 1.5n log(n) pasos.

Un inconveniente es que necesita un espacio adicional de Θ(n) para el array auxiliar, pero como utilizamos el más eficiente, solo se necesita la mitad de este espacio, siendo más rápido y estable que otras variantes.

Por lo tanto el tiempo de ejecución puede ser especificado por la recurrencia:

Cuya solución es que el algoritmo tiene una complejidad en tiempo de Θ(n log(n)) es óptimo.

Ordenamiento mezcla en paralelo.

Ahora explicaré como paralelizar el algoritmo de ordenamiento por mezcla, como podemos ver por obvias razones, el paralelismo de este algoritmo depende directamente de como es la rutina de mezcla, la cual también puede ser paralela, aunque sea el algoritmo secuencial, este ya tiene un paralelismo inherente ya que permite realizar dos llamadas recursivas independientes.

La forma mas sencilla de poner en paralelo el algoritmo es como se muestra en el siguiente pseudocodigo:

ordenMezcla(int bajo, int alto){
    if (bajo<alto) {
        int medio = (bajo+alto) / 2;
        spawn ordenMezcla(bajo, medio);
        spawn ordenMezcla(medio+1, alto);
        sync;
        mezcla(bajo, medio, alto);
    }
}

Suponiendo, que la función mezcla es secuencial para que el trabajo y la profundidad de mezclar dos elementos ordenados de n / 2 sea Θ(n),  así que en ordenMezcla el trabajo y su profundidad esta dado por:

Obtuvimos como solución el mismo que el tiempo para el algoritmo secuencial Θ(n log(n)) para el trabajo, pero por el lado de la profundidad, la solución es D(n) = Θ(n) que es menor que el trabajo, por lo tanto el paralelismo de este algoritmo es Θ(log n), el problema aquí es que la etapa de mezcla sigue siendo secuencial.

Usando una combinación en paralelo de las dos secuencias ordenadas, se puede combinar con el trabajo Θ(n) y la profundidad Θ(log log n)

Para el uso de este algoritmo de mezcla, la recurrencia de profundidad sería:

cuya solución es D(n) = Θ(log n log log n), usando una técnica llamada "pipelined divde-and-conquer", la profundidad del ordenMezcla puede reducirse hasta Θ(log n).

Divide y vencerás ha demostrado ser, una de las técnicas más poderosas para la solución de problemas en paralelo, se pueden resolver problemas de geometría computacional, la clasificación de elementos, la realización rápida de las transformadas de Fourier, resolución de sistemas lineales para factorizar grandes números, etc...

Espero que haya quedado entendible, tardé en entender cada una de las cosas, espero y verifiquen lo que investigué y si algo no queda muy claro, les pongo los recursos de donde obtuve esta información.

The Algorithm Design Manual - Steven S. Skiena - Springer
Parallel Algorithms - Guy E. Blelloch - Carnegie Mellon University
Sequential and parallel sorting algorithms - Hans wener Lang - FH flensburg
A Minicourse on Dynamic Multithreaded Algorithms - Charles E. Leiserson - MIT

Animaciones aqui.

Videos del MIT "Introduction to Algorithms" Lecturas 20 y 21 hablan sobre algoritmos paralelos y hablan sobre el ordenamiento de mezcla en paralelo en el minuto 43:30 de la lectura 21.

 

Nominaciones: 

Esteban.

Aveldaño

Cecy