HPC R+D: los sistemas xRH.

En un par de posts anteriores he comentado sobre la posibilidad de un sistema HPC basado en programas que utilicen sólo movimientos de datos por recorridos hamiltonianos (ver https://ireneses.wordpress.com/2010/12/23/parallel-computing-supercomputing-iv-industrial-organization/ y https://ireneses.wordpress.com/wp-admin/post.php?post=1600&action=edit).

Téngase en cuenta que en lo que sigue me interesa más explorar que componentes tendrían éste tipo de sistemas o máquinas, cómo se programarían y cómo se analizarían estos programas, que  obtener definiciones exactas o programas correctos y eficientes.

El objetivo de dichos sistemas es que cumplan con los requisitos de eficiencia energética, resistencia a fallos de sus elementos (nodos o procesadores; links) y facilidad de programación. En este post quiero concretar un poco más la idea, describiendo una familia de sistemas, que llamaré provisionalmente sistemas xRH (x=por; RH = recorridos hamiltonianos).

Cada miembre de la familia es un sistema multiprocesadores de memoria distribuida, con procesadores multicore, unidos por una red de interconexión con topología de Digrafo de Cayley (de momento no es necesario especificar el digrafo en concreto; cada sistema de la familia puede tener una topología basada en un digrafo diferente; otra posibilidad es diseñar un sistema con una topología universal, que pueda simular cualquier Digrafo de Cayley inferior a un determinado tamaño, sistema que podriamos llamar   xRHU).

Diversos RH disjuntos, tantos cómo  necesite la aplicación que se esté ejecutando, recorren la topología de manera simultánea y predecible;  utilizando estas rutas tipo RH se puede ir enviando instrucciones y datos a los procesadores desde cualquier procesador. En general cuantos más RH simultáneos permita una determinada topología, mejor.

Existe además una memoria principal adjunta al sistema dónde están los datos y las instrucciones que se irán inyectando al sistema.

Veamos cómo se realizaría una operación, trivial, de suma de dos números de  6 dígitos (numeración decimal) en un sistema concreto de la familia xRH. Para simplificar, en lo que sigue, de momento obviamos la propiedad multicore

INPUT: +; repetir ; 456897; 578129;

SISTEMA: 6 procesadores numerados con números naturales, desde 1 a 6; topología cualquiera que admita al menos 3 RH disjuntos simultáneos. Desde el inicio existen 3 RH preprogramados recorriendo de manera simúltanea el digrafo. Uno de los RH es un ciclo.

PROGRAMA:

El símbolo “C” denota carga de información en un RH, sean instrucciones o datos; los simbolos “<<” denotan que lo que esté entre ellos es la información que se carga en el RH correspondiente; “;” en el programa denota simultaneidad. La instrucción repetir significa que una vez que la operación, suma o cualquier otra, se haya cargado en el procesador, este deberá repetirla hasta nueva orden. En cada momento o tiempo el programa ejecuta una instrucción de movimiento (M) de datos /instrucciones, o una instrucción de proceso (P) de datos.

Inicio de programa.

Tiempo 1/M: desde la memoria principal adjunta a un nodo inicial,

–C <+< RH1 (se carga la instrucción suma en el RH ciclo que pasará por todos los procesadores o nodos y la cargará en cada uno de ellos); RH1 continua recorriendo el digrafo.

–C <número 1< RH2 (se cargan los dígitos del primer número en otro RH, y éste asignará cada dígito a cada procesador correspondiente; RH2 finaliza el recorrido del digrafo.

–C <número 2< RH3 (idem número 2). RH3 finaliza el recorrido del digrafo.

Tiempo 2/P: cada procesador ejecuta la suma de un par de dígitos y obtiene el resultado y un resto.

Tiempo 3/M: el resultado queda en cada procesador y el resto se envía al procesador siguiente utilizando el RH1, que es una permutación cíclica con respecto al orden numerico de los procesadores.

Tiempo 4/P: se repite la operación de suma, del resultado con el resto correspondiente, Bucle: se repiten las instrucciones del tiempo 3 y 4, hasta que el resto sea cero en todas las sumas  obteniendo un resultado final (1035026).

Tiempo X/M: C<+fin<RH1;   los digitos del resultado final se envian a la memoria principal utilizando el mismo RH1, desde dónde se puede leer el resultado;

Fin del programa.

La suma de n números de m dígitos se puede programar de manera equivalente y realizar en principio en el mismo tiempo o número de pasos: se necesitarian m procesadores de m núcleos y n+1 RH iniciales. Asumo que cada procesador puede sumar m dígitos en 1 paso (cosa que no tengo claro).

Queda claro que una parte importante de estos programas es, primero, diseñar RH capaces de ejecutar las instrucciones de movimiento de datos /instrucciones de manera conveniente y, segundo, coordinar las acciones de los diferentes RH. En principio toda la complejidad de la programación de estos sistemas se reduce a esto.

Además de los recursos  tiempo y espacio, el recurso consumo energético es un parámetro que actualmente se debe tener en cuenta en el análisis de complejidad de algoritmos (es posible que el recurso espacio se pueda reducir al recurso, pero pienso que tiempo y energía son independientes). En estos sistemas, el consumo de energía se realiza tanto  en las operaciones de movimiento cómo en las operaciones de proceso. Para las operaciones de movimiento, si mantener un RH recorriendo el digrafo una determinada cantidad de tiempo consume una determinada cantidad de energía, es fácil computar el consumo final de cada programa y comparar programas de acuerdo con su eficiencia energética.  En general en cada momento  solo estarán recorriendo el digrafo la cantidad de RH que sean necesarios, lo cual en principio puede suponer una mejora en la eficiencia energética.

Las operaciones básicas de suma, resta, multiplicación y división no parecen complicadas de programar en estos sistemas xRH, pero tengo que investigar que ocurre con otro tipo de operaciones más complejas (algebra lineal densa y dispersa, operaciones lógicas, grafos…). Ya iré publicando  en el blog avances: mi siguiente objetivo es diseñar un programa para un sistema xRH para multiplicación de matrices. También faltaría concretar más la ingeniería de los sistemas xRH: cómo garantizar la simultaneidad de la carga inicial etc…y analizar la resisencia a fallos.

l

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: