2010-05-11 11 views
10

Estoy impresionado con los bloques de creación de hilos de Intel. Me gusta cómo debo escribir tareas y no código de subprocesos y me gusta cómo funciona bajo el capó con mi comprensión limitada (las tareas están en un grupo, no habrá 100 subprocesos en 4 puntuaciones, no se garantiza que se ejecute una tarea porque no está activada su propio hilo y puede estar muy lejos en el conjunto. Pero puede ejecutarse con otra tarea relacionada, por lo que no puede hacer cosas malas como el código inseguro de hilo típico).¿Cómo escribo tareas? (código paralelo)

Quería saber más sobre la tarea de escritura. Me gusta el video 'Multitarea basado en tareas: cómo programar para 100 núcleos' aquí http://www.gdcvault.com/sponsor.php?sponsor_id=1 (actualmente segundo segundo enlace. ADVERTENCIA no es 'excelente'). Mi parte favorita fue 'resolver el laberinto es mejor hacerlo en paralelo', que es alrededor de la marca de 48 minutos (puede hacer clic en el enlace en el lado izquierdo. Esa parte es realmente todo lo que necesita para ver si hay alguno).

Sin embargo, me gustaría ver más ejemplos de código y algunas API sobre cómo escribir tareas. ¿Alguien tiene un buen recurso? No tengo idea de cómo una clase o partes de código pueden verse después de insertarlo en un grupo o qué tan extraño puede ser el código cuando necesitas hacer una copia de todo y cuánto de todo se inserta en un grupo.

Respuesta

7

Java tiene un marco de trabajo paralelo similar a los bloques de construcción de subprocesos: se lo denomina estructura de unión de horquilla. Es available para usar con el actual Java SE 6 y para ser incluido en el próximo Java SE 7.

Hay recursos disponibles para comenzar con el marco, además de la documentación de la clase javadoc. Desde jsr166 page, menciona que "También hay una wiki que contiene documentación adicional, notas, consejos, ejemplos, etc. para estas clases".

fork-join examples, como la multiplicación de matrices son un buen lugar para comenzar.

Utilicé el marco fork-join para resolver algunos de Intel's 2009 threading challenges. El marco es liviano y de bajo costo: el mío fue la única entrada de Java para el problema del Kight's Tour y superó a otras entradas en la competencia. Las fuentes de Java y la documentación están disponibles en el sitio del desafío para su descarga.

EDIT:

no tengo ni idea de cómo una clase o piezas de código puede cuidar empujándolo hacia una piscina [...]

Usted puede hacer su propia tarea mediante la subclasificación de una de las subclases ForKJoinTask, como RecursiveTask. A continuación se explica cómo calcular la secuencia de fibonacci en paralelo. (Tomado de la RecursiveTask javadocs - comentarios son mías.)

// declare a new task, that itself spawns subtasks. 
// The task returns an Integer result. 
class Fibonacci extends RecursiveTask<Integer> { 
    final int n;  // the n'th number in the fibonacci sequence to compute 
    Fibonnaci(int n) { this.n = n; } // constructor 
    Integer compute() { // this method is the main work of the task 
    if (n <= 1)   // 1 or 0, base case to end recursion 
     return n; 
    Fibonacci f1 = new Fibonacci(n - 1); // create a new task to compute n-1 
    f1.fork();       // schedule to run asynchronously 
    Fibonacci f2 = new Fibonacci(n - 2); // create a new task to compute n-2 
    return f2.invoke() + f1.join();  // wait for both tasks to compute. 
     // f2 is run as part of this task, f1 runs asynchronously. 
     // (you could create two separate tasks and wait for them both, but running 
     // f2 as part of this task is a little more efficient. 
    } 
} 

a continuación, ejecuta esta tarea y obtener el resultado

// default parallelism is number of cores 
ForkJoinPool pool = new ForkJoinPool(); 
Fibonacci f = new Fibonacci(100); 
int result = pool.invoke(f); 

Este es un ejemplo trivial para mantener las cosas simples. En la práctica, el rendimiento no sería tan bueno, ya que el trabajo ejecutado por la tarea es trivial en comparación con la sobrecarga del marco de tareas. Como regla general, una tarea debe realizar algunos cálculos significativos, suficientes para que la tara general del marco sea insignificante, pero no tanto que termine con un núcleo al final del problema ejecutando una tarea grande. Dividir tareas grandes en otras más pequeñas garantiza que no se deje mucho trabajo mientras que otros núcleos están inactivos; el uso de tareas más pequeñas mantiene ocupados más núcleos, pero no tan pequeños que la tarea no funciona realmente.

[...] o cómo el código puede parecer raro cuando que necesita para hacer una copia de todo y cuánto de todo lo que se empuja en una piscina.

Solo las tareas se envían a un grupo. Lo ideal es que no desee copiar nada: para evitar interferencias y la necesidad de bloqueo, lo que ralentizaría su programa, sus tareas deberían funcionar idealmente con datos independientes. Los datos de solo lectura se pueden compartir entre todas las tareas y no es necesario copiarlos. Si los hilos necesitan cooperar para construir una gran estructura de datos, lo mejor es que construyan las piezas por separado y luego las combinen al final. La combinación se puede hacer como una tarea separada, o cada tarea puede agregar su parte del rompecabezas a la solución general. Esto a menudo requiere alguna forma de bloqueo, pero no es un problema de rendimiento considerable si el trabajo de la tarea es mucho mayor que el trabajo que actualiza la solución. La solución My Knight's Tour utiliza este enfoque para actualizar un repositorio común de recorridos en el tablero.

Trabajar con tareas y concurrencia es un cambio bastante paradigmático de la programación regular de un solo hilo. A menudo, hay varios diseños posibles para resolver un problema determinado, pero solo algunos de ellos serán adecuados para una solución con rosca. Puede tomar algunos intentos obtener la sensación de cómo volver a resolver los problemas familiares de una manera multi-hilo. La mejor forma de aprender es mirar los ejemplos y luego probarlo por ti mismo. Siempre perfil, y meausre los efectos de variar el número de hilos. Puede establecer explícitamente el número de subprocesos (núcleos) para usar en el grupo en el constructor de grupo. Cuando las tareas se dividen linealmente, puede esperar una aceleración casi lineal a medida que aumenta el número de subprocesos.

0

Jugar con "frameworks" que pretenden resolver lo insoluble (la programación óptima de tareas es NP difícil) no va a ayudarlo en absoluto, leyendo libros y que los artículos sobre algoritmos concurrentes lo harán. Las llamadas "tareas" no son más que un nombre elegante para definir la separabilidad del problema (partes que se pueden calcular independientemente una de la otra). La clase de problemas separables es muy pequeña, y ya están cubiertos en libros antiguos.

Para los problemas que no se pueden separar, debe planificar las fases y las barreras de datos entre fases para intercambiar datos. La orquestación óptima de las barreras de datos para el intercambio simultáneo de datos no solo es difícil para NP sino que es imposible de resolver de una manera general -necesaria examinar la historia de todos los entrelazados posibles- es como la potencia del conjunto ya exponencial (como ir de N a R en matemáticas). La razón por la que menciono es dejar en claro que ningún software puede hacer esto por usted y que la forma de hacerlo depende intrínsecamente del algoritmo real y de determinar si la paralelización es factible (incluso si es teóricamente posible).

Cuando ingresa el alto paralelismo no puede mantener una cola, ni siquiera tiene un bus de memoria - imagínese 100 CPU-s tratando de sincronizarse en una sola int compartida o tratando de hacer un bus de memoria arbitraje. Tienes que pre-planificar y preconfigurar todo lo que se va a ejecutar y esencialmente probar la corrección en una pizarra blanca. Los bloques de construcción Threading de Intel son pequeños en ese mundo. Son para una pequeña cantidad de núcleos que aún pueden compartir un bus de memoria. Ejecutar problemas separables es una obviedad que puede hacer sin ningún "marco".

Ha vuelto a tener que leer tantos algoritmos paralelos diferentes como pueda. Normalmente, demora de 1 a 3 años en buscar un diseño de barrera de datos aproximadamente óptimo para un problema. Se convierte en diseño cuando busca 16 núcleos en un solo chip, ya que solo los primeros vecinos pueden intercambiar datos de manera eficiente (durante un ciclo de barrera de datos).Así que en realidad aprenderá mucho más al observar CUDA y sus documentos y resultados con la CPU experimental de 30 núcleos de IBM que con el lanzamiento de ventas de Intel o algún juguete de Java.

Tenga cuidado con los problemas de demostración para los cuales el tamaño de los recursos desperdiciados (número de núcleos y memoria) es mucho mayor que la aceleración que logran. Si se necesitan 4 núcleos y 4x RAM para resolver algo 2 veces más rápido, la solución no es escalable para la paralelización.

Cuestiones relacionadas