Portada :: Tecnología y Sociedad :: Artículos de mleyton

Skandium: Programación Multi-core en Java

27/Jul/2009

Nota: artículo largo (1700 palabras, ~9 min).

Durante las últimas décadas, la industria de la informática ha sido un ciclo constante donde nuevo hardware, más rápido que el anterior, permite el desarrollo de software más complejo y con más requerimientos de recursos. Este nuevo software a su vez promueve el desarrollo de hardware aún más rápido. Para aumentar la velocidad de un software, la mejor estrategia ha sido comprar hardware más nuevo.

Este paradigma ha cambiado ahora que Intel introdujo en el 2006, por primera vez, un procesador nuevo más lento que los anteriores, pero con multiples cores (núcleos). Esto produjo la denominada crisis del multi-core: el software antiguo funciona mas lento en el hardware nuevo. Esta crisis significa que la única forma de aumentar la velocidad de un software con nuevo hardware, es escribir software paralelo.

Skandium es una biblioteca en Java para facilitar programación paralela de hardware multi-core. El objetivo de Skandium es proveer una abstracción de alto nivel usando patrones de paralelismo como: farm (maestro-esclavo), pipe, for, while, if, map, fork y d&c (dividir para reinar).

Skandium esta basado en tecnología de esqueletos algorítmicos (Algorithmic Skeletons), originalmente orientada a sistemas distribuídos como Clusters y Grids donde se utilizan cientos y miles de nodos de cálculo. Con la llegada de procesadores multi-core, pronto tendremos hardware barato con cientos y miles de cores en nuestros escritorios. Por ejemplo, Intel ya tiene un prototipo denominado Polaris con 80 cores que fue presentado el 2007. Por lo tanto, tiene sentido utilizar esta tecnología para facilitar la programación de sistemas multi-core.

Patrones o Esqueletos

Los esqueletos representan patrones de paralelismo que pueden ser compuestos (anidados), para construir patrones más complejos. Los siguientes dos ejemplos muestran como pueden ser combinados los patrones para las aplicaciones de las N-Reinas (de cuántas formas se pueden poner N reinas en un tablero de NxN), y una paralelización de BLAST (alineamiento de sequencias de proteinas y ADN):

El paralelismo para cada esqueleto es el siguiente:

  • Farm: representa la replicación de tareas, y también es conocido como maestro-esclavo. Patrones anidados dentro de farm son replicados para obtener paralelismo.
  • Pipe: representa computación por etapas. El paralelismo se obtiene al ejecutar distintas etapas simultaneamente para diferentes tareas.
  • If: provee ramificación condicional. Utilizando una función de condición, el flujo de ejecución es decidido entre dos sub-esqueletos de manera dinámica.
  • For: ejecuta un sub-esqueleto una cantidad fija de veces.
  • While: ejecuta un sub-esqueleto una cantidad dinámica de veces, mientras una función de condición sea verdadera.
  • Map: una tarea es subdivida en varias sub-tareas, para cada tarea se ejecuta un sub-esqueleto en paralelo, y finalmente se combinan los resultados.
  • Fork: es como Map pero para cada sub-tarea se ejecuta un sub-esqueleto diferente.
  • D&C: es como Map pero se ejecuta recursivamente mientras se cumpla una función de condición. Una tarea se subdivide en varias sub-tareas. Y para cada sub-tarea se decide, utilizando la función de condición, si se ejecuta el sub-esqueleto o se vuelve a sub-dividir.

Los Músculos

Para transformar un esqueleto en una aplicación, el programador debe rellenar el esqueleto con las funciones especificas de su aplicación. Las funciones se denominan músculos y vienen en cuatro tipos:

  • Ejecución: public R execute(P param); Toma un parámetro de entrada y entrega un resultado.
  • Partición: public R[] split(P param); Toma un parámetro de entrada y entrega una lista de resultados.
  • Reducción: public R reduction(P[] param); Toma una lista de parámetros de entrada y entrega un unico resultado.
  • Condición: public boolean condition(P param); Toma un parámetro y entrega verdadero o falso.

Los músculos son ejecutados en paralelo y de manera concurrente durante la ejecución de la aplicación. Los resultados de un músculo se convierten en los parámetros de otros y así sucesivamente. El orden de ejecución de los músculos es orquestrado dependiendo del patrón/esqueleto donde se apliquen.

Por lo tanto es muy importante programar con la suposición de que los músculos serán ejecutados concurrentemente.

Ejemplo: Pi

El ejemplo que mostramos a continuación es el cálculo de los primeros 3000 decimales de Pi. Para esto utilizaremos la fórmula de Bailey-Borwein-Plouffe que permite calcular los decimales en un rango específico, por ejemplo del 1000 al 2000, sin necesidad de calcular los 999 primeros.

Por lo tanto el patrón que mejor se adapta a este problema es Map que permite dividir un problema en sub-problemas, calcular cada sub-problema de manera independiente, y después reducir los resultados.

Cuatro pasos se requieren para usar la biblioteca:

  1. Inicializar un nuevo esqueleto con sus respectivos músculos. En este caso se trata de un esqueleto Map.
  2. Ingresar los datos a la biblioteca que corresponde a un Intervalo de decimales a calcular [0,3000]. Al ingresar el Intervalo se genera un Futuro que almacenará el resultado de la aplicación cuando esté listo. Multiples datos pueden ser ingresados, pero en este ejemplo solamente mostramos uno.
  3. Mientras el calculo toma lugar, el thread principal puede realizar otras actividades.
  4. Obtener los resultados a través del Futuro, o bloquear hasta que estos esten disponibles.

// 1. Define the skeleton program structure
Skeleton<Interval, BigDecimal> bbp = new Map<Interval, BigDecimal>(
        //number of parts to divide by
        new SplitInterval(Runtime.getRuntime().availableProcessors()*2),
        new PiComputer(),
        new MergeResults());

// 2. Input parameters
Future<BigDecimal> future = bbp.input(new Interval(0, 3000));

// 3. Do something else...
// ...

// 4. Block for the results
BigDecimal pi = future.get();
System.out.println(pi);

Partición

Un músculo de Partición es responsable de transformar un único elemento de datos en una lista de elementos. En este ejemplo dividimos un Interval en un numero predefinido de partes. El resultado es una lista de intervalos que representan el original. Esta implementación no tiene estado, por lo que no es necesario agregar synchornized en el método split(...).

public class SplitInterval implements Split<Interval,Interval> {

        int numParts; //The number of sub intervals to create from an Interval
       
        public SplitInterval(int numParts){
                this.numParts=numParts;
        }
       
        @Override
        public Interval[] split(Interval param) throws Exception {
               
                int size = (param.end - param.start)/numParts;
                Interval[] result = new Interval[numParts];
               
                for(int i=0; i< (numParts-1) ? param.start + size*(i+1)-1 : param.end;
                       
                        result[i] = new Interval(start, end);
                }
               
                return result;
        }
}

Ejecución

Un músculo de Ejecución transforma un elemento en otro elemento. En otras palabras, ejecturá la computación.

En este ejemplo mostramos como la fórmula de Bailey-Borwein-Plouffe es usada para calcular los decimales de Pi para un Intervalo. Al igual que el caso anterior, no es necesario agregar synchronized al método execute(...).

public class PiComputer implements Execute<Interval, BigDecimal>{

    private static final int ROUND_MODE = BigDecimal.ROUND_HALF_EVEN;
    private BigDecimal ZERO             = new BigDecimal("0");
    private BigDecimal ONE              = new BigDecimal("1");
    private BigDecimal OPPOSITE_ONE     = new BigDecimal("-1");
    private BigDecimal OPPOSITE_TWO     = new BigDecimal("-2");
    private BigDecimal FOUR             = new BigDecimal("4");
    private BigDecimal FIVE             = new BigDecimal("5");
    private BigDecimal SIX              = new BigDecimal("6");
    private BigDecimal EIGHT            = new BigDecimal("8");
    private BigInteger SIXTEEN          = new BigInteger("16");
   
    @Override
    public BigDecimal execute(Interval interval) {

        //scale trick to hold enough precision
        int scale = (int) Math.floor(interval.end*1.2);
        BigDecimal bd = ZERO.setScale(scale);
               
        BigDecimal ONE            = this.ONE.setScale(scale);
        BigDecimal OPPOSITE_ONE   = this.OPPOSITE_ONE.setScale(scale);
        BigDecimal OPPOSITE_TWO   = this.OPPOSITE_TWO.setScale(scale);
        BigDecimal FOUR           = this.FOUR.setScale(scale);
        BigDecimal FIVE           = this.FIVE.setScale(scale);
        BigDecimal SIX            = this.SIX.setScale(scale);
        BigDecimal EIGHT          = this.EIGHT.setScale(scale);

       
        // BBP formula for the given interval
        for (int k = interval.start; k <= interval.end; k++) {
            bd = bd.add(f(k, interval.end,
                          EIGHT, ONE, FOUR, FIVE, SIX, OPPOSITE_TWO, OPPOSITE_ONE));
        }
       
        return bd;
    }

    private BigDecimal f(int k, int scale,
          BigDecimal EIGHT, BigDecimal ONE, BigDecimal FOUR, BigDecimal FIVE,
          BigDecimal SIX, BigDecimal OPPOSITE_TWO, BigDecimal OPPOSITE_ONE) {
       
        BigDecimal K       =  new BigDecimal(k);
        BigDecimal EIGHT_K =  EIGHT.multiply(K);
        BigDecimal FIRST   =  ONE.divide(new BigDecimal(SIXTEEN.pow(k)), ROUND_MODE);
        BigDecimal SECOND  =  FOUR.divide(EIGHT_K.add(ONE), ROUND_MODE);
        BigDecimal THIRD   =  OPPOSITE_TWO.divide(EIGHT_K.add(FOUR), ROUND_MODE);
        BigDecimal FOURTH  =  OPPOSITE_ONE.divide(EIGHT_K.add(FIVE), ROUND_MODE);
        BigDecimal FIFTH   =  OPPOSITE_ONE.divide(EIGHT_K.add(SIX), ROUND_MODE);

        return FIRST.multiply(SECOND.add(THIRD.add(FOURTH.add(FIFTH))));
    }

}

Reducción

Un múscuclo de Reducción es responsable en transformar una lista de elementos en uno solo. En este ejemplo simplemente sumamos los decimales calculados para cada intervalo y retornamos la suma total. Al igual que los músculos anteriores, este músculo no tienen estado, asi que no hay necesidad de sincronizar la concurrencia en merge(...)

public class MergeResults implements Merge<BigDecimal, BigDecimal>{

        @Override
        public BigDecimal merge(BigDecimal[] param) throws Exception {
               
                BigDecimal total = new BigDecimal(0);

                for (int i = 0; i < param.length; i++) {
                        total = total.add(param[i]);
                }

                return total;
        }
}

Acerca de Skandium


Skandium es desarrollado en NICLabs, el laboratorio de investigación aplicada y transferencia tecnológica de NIC Chile, parte del Departamento de Ciencias de la Computación de la Universidad de Chile, del cual soy parte.

Actualmente Skandium es desarrollado en Java bajo la licencia GPL v3.

Tu voto: None Promedio: 3.8 (5 votos)
  • mleyton's blog
  • 1357 lecturas

Comentarios

Foto de Gucci watches

http://www.dearwatches.com

Enviado por Gucci watches (no verificado) el 13 Diciembre, 2009 - 13:53

Christian Louboutin
Christian Louboutin on sale
cheap Christian Louboutin Evening
discount Christian Louboutin Pumps
Christian Louboutin Slingbacks on sale
YSL Platform Pumps&Slingbacks on sale
replica breitling watches
luxury replica watches
Burberry watches replica
Ferrari replica

Foto de ChaTo

¿Generaliza map-reduce?

Enviado por ChaTo el 27 Julio, 2009 - 08:53

Hola, este paradigma es más general que map-reduce, ¿O sea se puede implementar map-reduce sobre Skandium?

Otra: esto está pensado exclusivamente para computación paralela en multi-core o también para algoritmos distribuídos en red (tal vez la pregunta es tonta, no sé mucho del tema).

—ChaTo

Foto de mleyton

Re: ¿Generaliza map-reduce?

Enviado por mleyton el 27 Julio, 2009 - 19:18

El comportamiento de "map-reduce" esta representado en el esqueleto "map" de la biblioteca. La ventaja adicional de los esqueletos es que se pueden combinar los patrones. Por ejemplo puedo tomar un pipe, y ejecutar un map en la primera etapa y un d&c en la segunda.

Los Esqueletos Algoritmicos fueron inventados para computacion distribuida, como es el caso de las implementaciones de: Calcium, Lithium, Muskel, QUAFF, etc. Estas implementaciones estan pensadas para ambientes distribuidos con cientos y miles de nodos. Con la aparicion de multi-core pronto tendremos cientos y miles de cores en nuestros notebooks. Por lo tanto, tiene sentido adaptar modelos de programacion distribuida para multi-core. Esto es lo que estamos tratando de hacer con Skandium.

Enviar un comentario

El contenido de este campo se mantiene como privado y no se muestra públicamente.
  • HTML permitido: <a> <em> <strong> <pre> <ul> <ol> <li> <img> <blockquote> <br> <div> <h2> <h3> <hr> <object> <embed>
  • Saltos automáticos de líneas y de párrafos.
  • Las direcciones de las páginas web y las de correo se convierten en enlaces automáticamente.

Más información sobre opciones de formato

Recomendados por los lectores de Manzana Mecánica