MOTIVACIÓN:
Existen diversidad de problemas que aparecen de manera natural en
diferentes áreas de la ciencia y la tecnología, los cuales se resuelven mediante
el planteamiento y solución de uno o varios sistemas de ecuaciones lineales
muy grandes. Ejemplos comunes de ellos son la simulación de yacimientos,
modelación de plantas químicas, simulación de circuitos de alta escala de
integración, análisis estructural, ecuaciones en derivadas parciales, etc.
Sin embargo, los métodos conocidos para la resolución de estos problemas
tienen, en general, un sobrecargo de procesamiento (por ejemplo, generando
y accesando estructuras de datos, calculando el ordenamiento adecuado,
etc.), y puede decirse que los algoritmos secuenciales han llegado a su límite
en cuanto a la reducción de su complejidad en tiempo. Incluso, también en la
implantación de estos algoritmos en un computador secuencial existen límites
físicos dados por la arquitectura, cada vez más cerca de alcanzarse con los
últimos avances de la tecnología.
Más aún, existe un sinfín de aplicaciones de otro tipo que demandan
computadores veloces para ejecutar muchos cálculos rápidamente o procesar
un gran conjunto de datos. Ningún computador actual produce la velocidad
de procesamiento requerida por estas aplicaciones, y el paralelismo parece
ser una vía para obtener mayor velocidad en el cálculo, pues con la ejecución
de varias operaciones simultáneamente, el tiempo de cálculo puede ser
reducido de manera significativa. Es así como el paralelismo ha revolucionado
al mundo científico, ya que promete grandes mejoras en tiempo con respecto
a la forma tradicional de hacer las cosas. Un algoritmo secuencial, entonces,
comienza a ser adaptado, o completamente desechado, en el diseño de
diferentes algoritmos paralelos equivalentes donde los tiempos de ejecución
puedan variar mucho dependiendo de la arquitectura en la que sean
implantados.
TAXONOMÍA DE FLYNN:
Cualquier computador, ya sea secuencial o paralelo, ejecuta instrucciones
sobre datos. Un flujo de instrucciones (el programa) le indica al computador
qué hacer en cada paso, y éstas instrucciones afectan a un flujo de datos
(las entradas del programa). De acuerdo a la forma según la cual el conjunto
de datos es afectado por el conjunto de instrucciones, pueden ser definidos
diferentes modelos de computadores, y es así como Flynn definió los
siguientes cuatro modelos, dependiendo de si existen uno o múltiples flujos de
instrucciones o datos, ejecutados u operados por un procesador:
b.) Múltiple flujo de Instrucciones - Simple flujo de Datos (MISD)
c.) Simple flujo de Instrucciones - Múltiple flujos de Datos (SIMD)
d.) Múltiple flujos de Instrucciones - Múltiple flujos de Datos (MIMD)
a) Computadores SISD
Un computador SISD consiste de una sola unidad de procesamiento
recibiendo una secuencia de instrucciones que opera sobre una secuencia de
datos. En cada paso, la unidad de control emite una instrucción que opera
sobre datos obtenido de la unidad de memoria. Este es el modelo Von
Neumann, al cual corresponden la mayoría de los computadores actuales,
no presenta ningún paralelismo.
En este modelo p procesadores (p>1), cada uno con su propia unidad de
control, comparten una unidad de memoria común donde residen los datos.
Existen p secuencias de instrucciones y una secuencia de datos. En cada paso,
un dato recibido desde la memoria es operado por todos los procesadores
simultáneamente, cada uno con las instrucciones que el procesador recibe de
su unidad de control. Así el paralelismo es alcanzado realizando diferentes
operaciones sobre el mismo dato. No existen computadores comerciales que
se ajusten a este modelo.
En este modelo un computador paralelo consiste de p procesadores idénticos
(p>1), cada uno operando con su propia memoria local. Todos los procesado
res operan bajo el control de una sola secuencia de instrucciones emitida por
una unidad de control central. Existen p secuencias de datos, una por
procesador, los cuales operan de manera síncrona. En cada paso, todos los
procesadores ejecutan la misma instrucción cada uno sobre un dato diferente.
En la mayoría de las aplicaciones interesantes que se quieran resolver sobre
este tipo de computadores, es deseable que los procesadores puedan
comunicarse entre sí durante el cálculo a fin de intercambiar datos o
resultados intermedios. Esto puede ser realizado de dos maneras diferentes,
a través de una memoria común (computadores SIMD a memoria compartida)
o a través de una red de interconexión (computadores SIMD a memoria
distribuida).
Esta clase de computadores es la más general y más poderosa en el
paradigma de la computación paralela que los clasifica de acuerdo a la
secuencia de datos y/o instrucciones. Este tipo de computadores poseen p
procesadores (p>1), conectados a la memoria por un conmutador de tipo
mariposa. Cada uno operando bajo el control de una secuencia de instrucciones
emitida por su propia unidad de control. Así los procesadores están
potencialmente todos ejecutando diferentes programas sobre datos diferentes
. Esto significa que los procesadores operan de manera asíncrona, sin
embargo, los algoritmos asíncronos son difíciles de diseñar, evaluar e
implantar.
a.) Arquitecturas MIMD a Memoria Compartida
Esta clase de computadores es también conocida como modelo de máquina
paralela de acceso aleatorio (PRAM). Aquí p procesadores (p>1) comparten
una memoria común. Cuando dos procesadores quieren comunicarse lo hacen
a través de esta memoria común. Si se desea transmitir un dato desde el
procesador Pi al procesador Pj , esto lo realiza en dos pasos, en el primero,
el procesador Pi escribe el dato en una dirección de memoria conocida por
el procesador Pj. En el segundo paso el procesador Pj lee esa localización.
El modelo básico permite a todos los procesadores acceder la memoria
compartida simultáneamente, si la posición de memoria que ellos están
tratando de escribir es diferente. Sin embargo, el tipo de memoria puede
dividir este modelo en cuatro subclases dependiendo de si dos o más
procesadores pueden acceder a la misma posición de memoria
simultáneamente [AKL-89], a saber:
1. Lectura-Exclusiva, Escritura-Exclusiva:
2. Lectura-Concurrente, Escritura-Exclusiva
3. Lectura-Exclusiva, Escritura-Concurrente
4. Lectura-Concurrente, Escritura-Concurrente
El permitir múltiples lecturas simultáneas sobre la misma posición de memoria
no debe ocasionar ningún problema. Conceptualmente, si cada procesador
requiere leer desde una misma posición de memoria copia el contenido de
esa posición y lo almacena en su memoria local. Sin embargo, si varios
procesadores requieren escribir simultáneamente diferentes datos sobre la
misma posición de memoria, debe existir una manera determinística de
especificar el contenido de esa posición de memoria una vez realizadas las
escrituras. En estos casos (subclases 3 y 4), los conflictos de escritura se
resuelven por hardware, mientras que para las subclases 1 y 2, es el sistema
operativo que los resuelve, dando como resultado que en diferentes ejecucion
es de un mismo programa pueden tener resultados distintos, dada la
aleatoriedad descrita.
b.) Arquitecturas MIMD a Memoria Distribuida
La otra forma de comunicación entre los procesadores es a través de una
red de interconexión. En este modelo la memoria es dividida entre el conjunto
de procesadores, para su acceso local. Además, cada procesador es
conectado con sus vecinos a través de una línea bidireccional de comunicación
, la cual le permite enviar o recibir datos en cualquier instante de tiempo,
habiéndose desarrollado una amplia variedad de topologías que permiten
abarcar una gran cantidad de problemas de manera eficiente, tales como:
el arreglo lineal, el anillo, la malla, el toroide, el árbol, el fat-tree, y el
hipercubo [RUK-94], que tienen una baja cantidad de enlaces entre
procesadores, de manera tal que cuando sea necesario comunicar un
mensaje entre dos procesadores que no tienen conexión directa, debe
encaminarse o enrutarse dicho mensaje por procesadores intermedios entre
éstos dos.
Generalmente, es el transputer 0 el considerado "raíz", por estar conectado al
computador anfitrión ó Host, pero, como se dijo, cualquier transputer puede
además estarlo, y ese hecho varía de una arquitectura a otra.
INTRODUCCION
El entorno de desarrollo que se entrega junto a los transputers es el TDS que
responde a las siglas Transputer Development System.
Se trata de un sistema de desarrollo de aplicaciones, basado en Occam, que
reúne herramientas como un editor, un compilador de Occam y un depurador.
EDITOR
Como el resto de este entorno de desarrollo, el interfase hacia el usuario es
poco agradable, fruto de un diseño típico de los ochenta, donde el usuario
era el que tenía que adaptarse al ordenador.
Este editor es muy incómodo pues requiere la utilización de una gran cantidad
de teclas para cada cosa.
Impone la utilización de folders, que son bloques de listado representados
por una sola línea, que se identifica al comenzar por tres puntos. El manejo
del TDS se basa en navegar entre folders. Para ello existen teclas para entrar
y salir de ellos, así como para moverlos, borrarlos, etc.
COMPILADOR
Existen cinco tipos de unidades o folders de compilación:
EXE: programa ejecutable desde TDS.
UTIL: programa con utilidades especiales a ser utilizadas por otros
programas.
PROGRAM: preparado para ejecutarse sobre un red de transputers.
Contiene información sobre la configuración que permite al sistema de
desarrollo cargar el programa sobre dicha red.
SC: unidad de compilación separada. Suele contener procedimientos y
funciones de Occam.
LIB: librerías. TDS ofrece una extensa gama de librerías para ser usadas por
el desarrollador de aplicaciones en Occam.
Habrían tres formas de ejecutar un programa en Occam:
Dentro de TDS para un transputer.
En el primer caso habría que realizar lo siguiente:
Chequeo de sintaxis.
En el segundo caso habría que comenzar realizando los pasos 1 y 2 también
sobre el PROGRAM en el que figuraría la descripción del reparto de tareas
entre los distintos transputers, así como el encaminamiento a seguir del flujo
de datos. Siempre, antes de ejecutar el programa, habrá que cargar la red,
es decir decirle a cada transputer qué tiene que hacer cuando se le diga que
comience con su tarea.
Un ejemplo PROGRAM para cargar un sistema de ocho nodos en pipeline,
siete de los cuales contienen el mismo programa:
{{{ PROGRAM pipeline
VAL last IS 7:
[last+1]CHAN OF INT32 links :
PLACED PAD
pipe.end (links[last], links[0], 0)
PLACED PAR i=1 FOR last
Obsérvese como para cada link se diferencia el canal de entrada y el de
salida de forma que la numeración es número de link para links de salida y
número de link más cuatro para links de entrada.
El compilador es muy poco tolerante a errores, lo cual significa que el
programador puede perder varias horas por culpa de una conversión de
tipos mal hecha.
DEPURADOR
Sólo permite realizar lo que podríamos denominar un análisis post-morten.
Analizando el fichero code dump donde se ha volcado el estado de las
variables del sistema en el instante del "cuelgue".
APLICACIONES TÍPICAS
El número de aplicaciones para máquinas de tal potencia es algo abierto a la
imaginación de los desarrolladores.
INMOS propone la siguiente lista de aplicaciones:
Aplicaciones científicas y matemáticas. Éstas requieren grandes cantidades de
cálculos antes reservadas a las grandes computadoras.
Sistemas multiprocesadores de alta velocidad.
Procesamiento gráfico de alto rendimiento. Con treinta y dos transputers se
conseguiría la misma potencia que la de los superordenadores vectoriales
usados para generar secuencias de animación para películas. Sirva de
ejemplo que con cuatro transputers se podrían generar animaciones a base
de polígonos, unos doscientos, de 17 imágenes por segundo.
Supercomputadores. Ya se comentó al principio que con cierto número
elevado de transputers se conseguiría alcanzar potencias comparables a la
un Cray. Conviene tener en cuenta el siguiente dato: el Cray 3, la máquina
más potente jamás construida da una potencia de cálculo de más de 16000
MIPS.
Estaciones de trabajo basadas en transputers.
Procesamiento digital de señales. Así se entra en competencia con los DSP,
debido a los canales de alta velocidad se pueden realizar adquisiciones de
señales a muy altas velocidades.
Bases de datos distribuidas.
Simulación de sistemas.
Telecomunicaciones.
Robótica. Usando los transputers como procesadores de los sistemas de
control.
Procesamiento de imágenes.
Reconocimiento de patrones. Permitiendo la implementación software de
sistemas de clasificación tales como redes neuronales.
Inteligencia artificial. De hecho algunos autores consideran Occam como un
lenguaje de la Quinta Generación.
ARQUITECTURAS SIMILARES
Se puede hablar de dos sistemas que ofrecen computación paralela a bajo
costo:
Hipercubos de Intel.
Las últimas generaciones de DSP.
Los hipercubos de Intel son estructuras basadas en 80386 con coprocesador,
memoria local de hasta 16 Mbytes, un interfase para añadir dispositivos al
nodo y un módulo de encaminamiento, DCM, que gestiona ocho canales serie,
de forma que al dedicar siete de éstos para las conexiones con otros nodos,
se obtiene un hipercubo de 128 elementos. Intel denomina a esta arquitectura
iPSC/2 (existió la iPSC/1 más antigua).
Su similitud con el transputer es alta; aunque aquí el tema del
encaminamiento y la gestión de los procesos la realiza un sistema operativo,
NX/2, que reside en cada nodo. La arquitectura del transputer es específica
para su conexión en paralelo, mientras que iPSC/2 consiste en poco más que
un circuito basado en un 80386 al que se le han añadido capacidad de
interconexión. Por último habría que comentar la diferencia en la potencia de
los dos micros: un transputer suele alcanzar los 30 MIPS, mientras que un
80386 apenas va a llegar a los 5 MIPS.
Los DSP están teniendo mucho éxito en los últimos años debido al desarrollo
de estos por algunas marcas como Texas Instruments, Zilog o SGS-Thomson.
La descripción más simple de un DSP es la de un microprocesador preparado
para capturar señales de muy diversos tipos y a altas velocidades.
Los C40 de Texas Instruments, que son DSP tienen cuatro canales
idireccionales de alta velocidad que podrían usarse como links. Aunque no
estén estos dispositivos preparados para el procesamiento en paralelo
internamente, su capacidad de interconectividad los hace muy indicados para
el desarrollo de sistemas concurrentes. Asimismo la capacidad de cálculo de
un DSP puede ser de unos 20 MIPS en el C40 y superior en modelos más
avanzados, así que sólo es cuestión que alguien se dedique ha formar redes
de DSP para procesamiento en paralelo.
FUTURO
Por último quedaría por platearse si los transputer tienen algún futuro. Ya en
la introducción se comentó las pocas intenciones por parte de INMOS de
continuar con el desarrollo de estas máquinas.
A principio de los noventa se habló mucho sobre el nuevo H1, sobre todo
porque solucionaba el problema del encaminamiento, el talón de Aquiles de
los transputers, a través de su C104 que estaba dedicado a dicho menester.
Cada C104 permite conectar hasta 32 H1 y ejecuta un algoritmo de
encaminamiento programable siendo la topología de la red.
Sin embargo, en los dos últimos años nadie parece querer hablar sobre ellos.
De todas formas, el hecho que aún haya quien utilice los transputers indica q
ue, al menos, fueron una buena idea.
a.) Simple flujo de Instrucciones - Simple flujo de Datos (SISD)
Dentro de una red de transputers.
Fuera de TDS.
Compilación, linkado y generación del código ejecutable, EXE.
Cargar el código en la red de transputers.
Ejecución propiamente dicha.
Si el programa ya había sido previamente compilado bastaría con realizar
los pasos 3 y 4.
{{{F source
... SC element (CHAN OF INT32 in, out, VAL INT board.no)
... SC element (CHAN OF INT32 in, out, VAL INT board.no)
VAL input.links IS [5, 7, 6, 7, 5, 7, 6, 7] :
VAL output.links IS [0, 2, 1, 1, 0, 2, 1, 1] :
PROCESSOR T4
PLACE links[last] AT input.links[0] :
PLACE links[0] AT output.links[0] :
VAL in IS i-1:
VAL out IS i:
PROCESSOR i T4
PLACE links[in] AT input.links[i] :
PLACE links[out] AT output.links[i] :
element (links[in], links[out], i)
}}}
}}}
