I.1.0. Introducci¢n El desarrollo de aplicaciones de ordenadores ha dependido siempre, en gran medida, de la velocidad de las unidades de procesamiento disponibles. Desde la construcci¢n del primer ordenador electr¢nico, la velocidad de operaci¢n se ha incrementado en un factor de diez cada d‚cada, lo que ha mejorado el rendimiento en las £ltimas d‚cadas. Esta mejora en el rendimiento se ha alcanzado, entre otras cosas, al hacer las componentes individuales de trabajo m s r pidas. Estos desarrollos comienzan a hacerse muy caros y algunas dificultades tecnol¢gicas empiezan a tener restricciones por limitaciones f¡sicas fundamentales, como es la velocidad de la luz. Las nuevas mejoras en la generaci¢n actual de circuitos integrados ofrecer n menores ganancias en t‚rminos del incremento de la velocidad. Los t¡picos ordenadores actuales poseen velocidades de procesamiento del orden de 1-10 Millones de Instrucciones Por Segundo (MIPs). En el futuro, VLSI ofrece el potencial de circuitos mucho m s complejos, pero sin sostener necesariamente el incremento en el rendimiento. Para satisfacer el software de la quinta generaci¢n se necesitar n velocidades del orden de 10.000-100.000 MIPs. Se han intentado t‚cnicas para conseguir estos incrementos, y futuros desarrollos, indudablemente alcanzar n algunos incrementos en las velocidades de los procesadores convencionales, sin embargo, un solo procesador no ser  capaz de ofrecer las velocidades requeridas. La perspectiva tradicional de m quinas basadas en la arquitectura de von Newman sostiene la idea de que procesar es costoso en comparaci¢n con la memoria. Una arquitectura von Newman t¡pica consiste en un procesador y un  rea de memoria. Datos y programas se almacenan en este  rea de memoria y as¡ el procesador necesita accesos constantes. Un contador de programa guarda la direcci¢n de la siguiente instrucci¢n y ‚ste se va modificando a medida que el programa se va ejecutando. Tales m quinas ejecutan una £nica instrucci¢n sobre un £nico ¡tem de datos, denotaremos estas m quinas como SISD (Single Instruction Single Data). Esto ha dado lugar a lo que se conoce como "cuello de botella" von Newman. Una estrategia obvia para mejorar el rendimiento es introducir alguna medida de paralelismo en el proceso ofreciendo procesadores adicionales. Un ordenador paralelo ideal es aquel en el que cada procesador tiene acceso a un  rea global de memoria compartida. Sin embargo a¤adir un procesador no implica necesariamente duplicar el poder de procesamiento. La introducci¢n de dos procesadores que comparten la misma memoria para comunicaciones significa que, deben usar un bus de memoria. Hay de esta forma un cuello de botella procesador-memoria y no se alcanza el rendimiento esperado. Esto nos lleva a un problema de contenci¢n. Por ejemplo, si ambos procesadores necesitan acceder a la misma zona de memoria en el mismo instante de tiempo debe haber alg£n tipo de sistema que permita decidir qu‚ procesador accede a la memoria y qu‚ procesador debe esperar a que el otro haya acabado. Tal esquema de arbitraje puede existir sin p‚rdidas significativas en el poder de procesamiento. A¤adir m s procesadores hace el problema de arbitraje m s dif¡cil, los incrementos del rendimiento no son lineales con respecto al n£mero de procesadores. Una importante tendencia actual es la producci¢n de ordenadores paralelos con costos relativamente bajos. Existen m quinas de procesamiento paralelo, que denotaremos como m quinas MIMD (Multiple Instrution Multiple Data), desde principios de 1950 cuando se introdujo el Univac 1. En un ordenador paralelo puede existir procesamiento paralelo en una gran variedad de formas, por ejemplo en el uso de "pipeline", "array processor", unidades funcionales y multiprocesadores. . El concepto de pipeline o canalizaci¢n hace referencia a una serie de elementos de procesamiento conectados en una canal a trav‚s del cual los datos fluyen. Los elementos de procesamiento se colocan de forma que el elemento siguiente desarrolla el siguiente estado del programa. Esto permite una medida de procesamiento paralelo mientras se retiene un £nico flujo de datos y un uso controlado de comunicaciones. Un ejemplo de uso de la t‚cnica pipeline es la m quina Cray y es una t‚cnica muy utilizada en dise¤os "bit-sliced" y en sistemas de microc¢digo. . En array processor, varios procesadores ejecutan la misma instrucci¢n pero sobre datos procedentes de la memoria asociada a cada procesador. Denotaremos estas m quinas como m quinas SIMD (Simple Instruction Multiple Data) . El paralelismo funcional permite que varias unidades funcionales como sumadores, booleanos l¢gicos, multiplicadores operen sobre diferentes datos. . El multiprocesamiento permite varios procesadores, cada uno de ellos ejecutando su propio flujo de instrucciones pero operando sobre datos que deben compartirse entre todos los procesadores. El multiprocesamiento resulta atractivo y se usa, por ejemplo, en el Cray XMP48. Pueden aparecer dificultades si no se usa la topolog¡a correcta para conectar los procesadores, entonces la red resultante del procesamiento puede ser tan lenta, que baje el rendimiento. Sin embargo, el multiprocesamiento a gran escala es ahora una posibilidad distinta, dado que el incremento funcional debido al incremento del n£mero de componentes en un solo chip aun no ha acabado. A pesar de los atractivos beneficios del procesamiento paralelo en t‚rminos de mejora del rendimiento, hay grandes problemas en lo que se refiere a comunicaci¢n, sincronizaci¢n y planificaci¢n de las tareas ("scheduling") entre los distintos procesadores. La comunicaci¢n se refiere a la toma correcta de datos en el tiempo correcto para su uso eficiente. Los procesadores necesitan comunicarse con otros y, de esta forma, compartir un bus com£n. Al incrementar el n£mero de procesadores, el sistema alcanza r pidamente el estado en el que los procesadores gastan la mayor parte del tiempo esperando para hacer uso del bus. El problema de dividir un programa entre varios procesadores es complejo, una situaci¢n t¡pica que se produce es aquella en la que los procesadores acaban sus tareas en tiempos distintos y unos deben esperar por los otros. Pueden aparecer problemas de sincronizaci¢n con el procesador que est  dedicado a controlar a los otros procesadores y detectar cuando han acabado sus tareas. Para resolver estos problemas se han desarrollado muchos algoritmos de planificaci¢n ("scheduling"). Un desarrollo en el  rea del procesamiento paralelo nos lo ofrece una nueva arquitectura de computadores desarrollada por Inmos Ltd en un microprocesador. Este nuevo procesador se llama TRANSPUTER (TRANSistor-comPUTER) y, adem s de los componentes de memoria y el procesador, ofrece canales o "links" (enlaces) para comunicarse con otros Transputers u otros dispositivos. Estos links y sus propiedades son una de las caracter¡sticas principales de esta nueva arquitectura. La comunicaci¢n entre estos links tiene lugar s¢lo si los emisores y receptores est n preparados, es decir, la comunicaci¢n es sincronizada. La sincronizaci¢n de sucesos fue uno de los mayores inconvenientes en los comienzos del procesamiento paralelo. Para cada Transputer hay cuatro de tales links lo que significa que pueden conectarse en un amplio espectro de configuraciones, de esta forma son muy convenientes para sistemas de multiprocesadores. La velocidad b sica del procesador Transputer est  en la regi¢n de los 10 MIPS, pero como los Transputers no comparten el mismo bus de comunicaci¢n el poder de comunicaci¢n total se incrementa linealmente con el n£mero de Transputers a¤adidos. Un array de, por ejemplo, 100 Transputers ofrecer¡a una velocidad en la regi¢n de los 1000 MIPS. En el caso de los procesadores convencionales, la mejora en la potencia empieza a disminuir con la inclusi¢n de alrededor de seis procesadores. La arquitectura Transputer utiliza los procesos como el bloque fundamental de construcci¢n de software y ofrece una implementaci¢n directa de un proceso en hardware. Un proceso es una computaci¢n independiente que puede comunicarse con otros procesos que se ejecutan al mismo tiempo. La comunicaci¢n entre procesos que se ejecutan en distintos Transputers se consigue utilizando canales expl¡citamente definidos. Un proceso puede consistir en un n£mero de subprocesos y el Transputer implementar estos subprocesos en tiempo compartido, con instrucciones especiales que soportan las comunicaciones. El Transputer ofrece un n£mero de links que soportan comunicaci¢n punto a punto entre Transputers, permitiendo de esta forma que los procesos se distribuyan sobre una red de Transputers. De esta forma, es posible programar sistemas que contienen m£ltiples Transputers interconectados en los que cada Transputer implementa un conjunto de procesos. Deber¡a notarse tambi‚n que un Transputer puede enviar un mensaje s¢lo a otro Transputer con el que est‚ directamente conectado. Un Transputer puede programarse en la mayor¡a de los lenguajes de alto nivel, sin embargo, se obtiene un mayor beneficio del sistema si se programa en el lenguaje concurrente Occam. Un sistema puede dise¤arse y programarse completamente en Occam desde la configuraci¢n del sistema hasta las entradas y salidas a bajo nivel e interrupciones en tiempo real. Occam permite que la concurrencia se defina expl¡citamente en el programa. Una caracter¡stica importante, tanto de Occam como del Transputer, es que unprograma escrito en Occam configurado para un sistema de varios Transputers, puede ejecutarse en un sistema de un solo Transputer haciendo muy pocas modificaciones, aunque m s lentamente. I.1.1. Arquitectura Transputer El Transputer es un procesador de alto rendimiento, dise¤ado b sicamente para facilitar las comunicaciones entre procesadores y entre procesos. Tiene caracter¡sticas hardware especiales que facilitan el proceso de planificaci¢n, tiene canales de comunicaci¢n y links seriales de comunicaci¢n externa. Estas caracter¡sticas est n todas dise¤adas de forma consistente y su desarrollo expresado en el contexto del lenguaje Occam. Occam es un lenguaje de programaci¢n con un fuerte soporte para el procesamiento paralelo y, el Transputer y Occam se desarrollaron juntos teni‚ndose en cuenta mutuamente. Consecuentemente, los programas Occam producen un c¢digo muy compacto y muy eficiente cuando el procesador es un Transputer. Como el Transputer se ha dise¤ado para ejecutar c¢digo eficientemente generado por el compilador Occam,se sigue que se obtendr  un rendimiento razonable con otros lenguajes de alto nivel, puesto que Occam tiene el mismo tipo de caracter¡sticas. La arquitectura Transputer define una familia de componentes VLSI programables con las siguientes caracter¡sticas: - Procesador RISC (Reduced Instruction Set Computer). - Memoria interna RAM (Random Access Memory) de alta velocidad. - Controlador de memoria externa. - Caracter¡sticas hardware "time-slicing". - Links seriales de alta velocidad (Inmos Links). La estructura b sica de un Transputer se corresponde con el diagrama de bloque de la figura-1. Aunque hay variantes en esta arquitectura, utilizaremos el T414 (un miembro de la familia Transputer) para describir las caracter¡sticas de esta arquitectura. El Transputer T414 integra un microprocesador con longitud de palabra de 32 bits, tiene 2 Kbytes de memoria interna (RAM) de alta velocidad (50ns) y 4 Gbytes de espacio direccionable con una interface de memoria de 25 Mbyte/s. Los cuatro Links (Inmos Links) en cada T414 ofrecen comunicaciones punto a punto y, pueden operar a velocidades de 5, 10 ¢ 20 Mbits/s en ambas direcciones al mismo tiempo. Una vez que un link ha iniciado una comunicaci¢n, procede aut¢nomamente y de esta forma el procesador puede ejecutar otro proceso (esto se consigue mediante t‚cnicas de acceso directo a memoria (DMA)). La memoria interna, 2 Kbytes para el T414, ofrece un promedio m ximo de datos de 80 Mbytes/s comparado con los 25 Mbytes/s de la memoria externa. Desde el punto de vista del programador no hay diferencias visibles entre las dos. Toda la RAM interna es asignada a la parte m s baja del espacio direccionable, y si la direcci¢n en un acceso a memoria est  en este rango entonces se accede a RAM interna, en otro caso el bus de direcci¢n de datos se activa. La provisi¢n de RAM interna tiene dos ventajas. En primer lugar, puede utilizarse para ubicar secciones cr¡ticas de c¢digo y datos, obteniendose un incremento significativo en la velocidad de ejecuci¢n del programa. En segundo lugar, permite que los Transputers se utilicen sin memoria externa si el programa y los datos no son demasiado largos. El T414 puede acceder directamente a un espacio de memoria direccionable linealmente de 4 Gbytes. La interface de memoria utiliza un bus de direcci¢n de datos de 32-bits y suministra datos a un promedio de 25 Mbytes/s. Un controlador de memoria configurable suministra todas las se¤ales de temporizaci¢n y control. Este controlador posee temporizadores (Timers) que soportan dos niveles de prioridad. Los procesos de alta prioridad se espera que se ejecuten en intervalos de tiempo cortos. Si uno o m s de tales procesos puede proceder, entonces se selecciona uno hasta que tenga que esperar en una comunicaci¢n, una entrada en un timer o hasta que el proceso se complete. Si no hay disponibles procesos de alta prioridad, se selecciona uno de baja prioridad. I.1.2. Inmos Links La arquitectura Transputer ofrece, comunicaciones mediante el uso de links llamados Inmos links. En el caso de T414 hay cuatro de tales links. Cada link ofrece dos canales Occam, uno en cada direcci¢n. La comunicaci¢n v¡a cualquier link puede ocurrir concurrentemente con comunicaciones en todos los otros links y con la ejecuci¢n de programas. La sincronizaci¢n de procesos en cada link es autom tica y no requiere programaci¢n expl¡cita. Los links se conectan uniendo un LinkOut a un LinkIn como se ilustra en la siguiente figura. Cada link consiste en una entrada y una salida serial, ambas se utilizan para llevar datos e informaci¢n de los links. Estos links permiten comunicaciones entre Transputers y de aqu¡ la conexi¢n de Transputers en arrays. Es posible una amplia variedad de configuraciones dependiendo en gran medida del n£mero de links utilizados: Se admite que dos procesadores interconectados dialogar n disponiendo del tiempo de uno o varios intermediarios que har n el papel de buz¢n. El caso l¡mite de conectar cada procesador a un "vecino" s¢lo podr¡a llevar directamente a embotellamientos, dado que las redes de Transputers que son apropiadas para solucionar un problema pueden no ser apropiadas para solucionar otros problemas. Por esto, es deseable, encontrar un r‚gimen de interconexi¢n que pueda aplicarse a muchos problemas. Una configuraci¢n altamente utilizada es la denominada hipercubo n-dimensional, dicha configuraci¢n pone en relaci¢n 2 procesadores -Transputers- de tal modo que cada uno est  conectado a n "vecinos" seg£n las n aristas que parten de cada v‚rtice de un hipercubo de dimensi¢n n. El orden (la dimensi¢n) de un hipercubo n, indica el n£mero de links que se necesitan en cada procesador del hipercubo. Las figuras siguientes muestran hipercubos para n = 0-4. El caso n = 0 se trata de un procesador sin interconexiones. Cuando n = 1 hay dos procesadores que est n conectados por un link. El mecanismo para progresar desde un hipercubo al siguiente en la secuencia consiste en duplicar la estrucura y unir mediante links los procesadores correspondientes. Esto es, cuando n = 2 hay dos ejemplos de n = 1 que est n conectados. Tambi‚n es una propiedad de un hipercubo que el orden n da el n£mero m ximo de procesadores entre un procesador y otro. Esto es, cuando n=2 el n£mero m ximo de links que han de atravesarse es 2. Esto ocurre entre los procesadores que est n en los extremos de las diagonales de los cuadrados. Para n = 3, se conectan dos hipercubos de orden dos y estos forman un cubo. Para n = 4, el hipercubo se forma uniendo dos hipercubos de orden 3. Estamos entonces en el l¡mite de lo que un Transputer puede ofrecer por s¡ mismo, ir m s all  supone multiplicar (o multiplexar) cada conexi¢n original con la ayuda de circuitos externos. Sustituyendo en un hipercubo cada uno de los v‚rtices por un conjunto de k procesadores c¡clicamente interconectados obtenemos una estructura, altamente modular, que se conoce como hipercubo conectado en ciclos. El n£mero de procesadores es k * 2 y, cada procesador tiene dos vecinos en el ciclo y uno de conexi¢n. I.1.3. La Familia Transputer El Transputer apareci¢ por primera vez en 1985. En aquel momento se anunci¢ como una revoluci¢n Occam. El primer procesador de la serie, el T414 se jactaba de una velocidad sin precedentes de 10 MIPS, junto con la capacidad de desarrollar multitarea en hardware. Adem s permit¡a la comunicaci¢n entre procesos que se ejecutar¡an en distintos Transputers. El T414 es un procesador de 32-bits con 2K de RAM interna y cuatro links interprocesadores, direccionando hasta 4Gbytes de memoria externa, utilizando direccionamiento multiplexado y links de datos. Desde entonces, se han anunciado otros miembros de la familia Transputer: - El T212, una versi¢n de 16-bits con 2K de RAM interna y un rango de direccionamiento de 64K, utilizando direccionamiento segmentado y buses de datos. - El M212, un T212 con 2 de los 4 links sustituidos por circuiter¡a controladora de disco. - El T800, esencialmente un T414 mejorado con un coprocesador de coma flotante integrado en el chip, instrucciones extra, links mejorados y la RAM interna duplicada a 4K. Este chip altamente extendido ha fijado la reputaci¢n de los Transputers, porque combina un alto rendimiento del procesamiento en coma flotante (1.5 MFLOPs) con la posibilidad de procesamiento paralelo. - El T222 un T212 mejorado con 4K de RAM interna. - El T801, un T800 con direccionamiento segmentado y buses de datos para accesos r pidos a memoria. - El T425 y T805 versiones superiores al T414 y el T800 con instrucciones extras a¤adidas para facilitar el seguimiento paso a paso y otras herramientas de depuraci¢n. I.1.4. Desarrollos futuros I.1.4.1. Arquitectura "supernode" Supernode es un proyecto francobrit nico; tiene como objetivo construir una familia de m quinas de conexionado reconfigurable din micamente por programa, utilizando los Transputers T800 dise¤ados por Inmos. La arquitectura supernode - empleamos deliberadamente las min£sculas para designar y subrayar el car cter gen‚rico y com£n de este tipo de arquitectura, que puede dar lugar a varias clases de m quinas (T-Nodes fabricados por Telmat en Francia o SN-1000, producidos por Parsys, filial de Thorn-EMI en Gran Breta¤a)-, es una soluci¢n atractiva de coste reducido; una alternativa a las topolog¡as actualmente desarrolladas. Se basa fundamentalmente en un m¢dulo con Transputers T800 (cuyos enlaces pueden ser conmutados mediante un componente especial), una estrategia de construcci¢n jer rquica y una metodolog¡a de programaci¢n elaborada sobre Occam. Este enfoque deber¡a desembocar en la construcci¢n de una familia de supernodes que ir¡a desde el puesto de trabajo individual potente hasta el supercomputador, pasando por m quinas dedicadas a una clase especial de aplicaciones. El supernode es una arquitectura que puede emplear un importante n£mero de Transputers y, a la vez, optimizar el coste de las comunicaciones en una m quina de tama¤o importante, que seguir¡a teniendo un coste de fabricaci¢n muy bajo en relaci¢n a los superordenadores existentes de potencia equiparable. El supernode b sico (que llamaremos "node" para evitar cualquier confusi¢n) est  constituido t¡picamente por un conjunto de dieciocho Transputers T800 (de ellos, diecis‚is acceden a una memoria masiva que almacena importantes cantidades de datos, o el control del conmutador). Estos elementos, fundamentalmente, est n interconectados mediante un conmutador programable. Podr¡amos designarlo como un configurador, funcionalmente parecido a una central telef¢nica, que realiza en dos microsegundos la conmutaci¢n de los kinks de los Transputers, sin importar cual de los links de un Transputer pueda, en un momento dado, ponerse en relaci¢n con uno cualquiera de los links de otro Transputer. Observemos, que esta configuraci¢n funciona tanto en modo MIMD como en modo SIMD. La arquitectura de un supernode es totalmente modular: los nodes pueden conectarse entre s¡ seg£n un principio similar a la conexi¢n de los Transputers ya descrita: el esquema precedente se aplica de nuevo, con la diferencia de que los procesadores no son ahora Transputers, sino nodes de Transputers. En este caso, la m quina es siempre reconfigurable: un conmutador electr¢nico internodes, bajo el control de un Transputer, permite modificar la topolog¡a entre estos nodes. En la configuraci¢n m s difundida, con el conmutador actual, se conectar  de este modo 64 nodes, es decir, 1204 Transputers dedicados al c lculo. Es perfectamente posible realizar topolog¡as fijas (pipelines,  rboles, hipercubos, ....) en los supernodes cuyo conexionado est  controlado por programa; su configuraci¢n puede efectuarse incluso durante la ejecuci¢n de una tarea. El lenguaje inicial de programaci¢n se ha elaborado en base a Occam pero actualmente existen otros tipos de lenguaje (C, Pascal, Fortran, Prolog, Lisp, Ada). I.1.4.2. El IMS T9000 Como resultado de un proceso de revisiones sucesivas a la arquitectura Transputer, se ha obtenido un nuevo componente de la familia, el IMS T9000 (anunciado como el H1). Est  destinado a ser un nuevo miembro de la familia Transputer que se caracteriza por un alto nivel de compatibilidad con sus predecesores y un rendimiento mucho m s alto. Las primeras caracter¡sticas del T9000 que ya hab¡a sido anunciado en 1990, fueron publicadas oficialmente por INMOS en Abril de 1991 y, los primeros modelos estar n disponibles a comienzos de 1992. El T9000 aporta el hardware necesario para una nueva concepci¢n del dise¤o de software paralelo. La idea fundamental es dejar a los dise¤adores de software libres de caracter¡sticas dependientes del tipo de m quina, tales como la topolog¡a de interconexi¢n de los procesadores. A un nivel de abstracci¢n alto, podemos decir, que la arquitectura T9000 CPU/FPU es exactamente la misma que la de la serie Transputer T800, con un incremento en la velocidad que permite alcanzar 200 MIPs, 25 MFLOPS. En el T9000, el multiplexado/demultiplexado de canales se lleva a cabo en un componente hardware llamado "Virtual Channel Processor" (VCP). El VCP es capaz de multiplexar cualquier n£mero de canales virtuales sobre un link f¡sico, utilizando un protocolo adecuado de comunicaciones con su socio VCP. Una importante caracter¡stica del VCP es que, cuando varios mensajes tienen que ser transmitidos concurrentemente sobre el mismo link, intercambia paquetes de diferentes mensajes de cara a optimizar el tiempo de entregas. Los Transputers T9000 pueden conectarse directamente, tal y como los modelos de Transputers anteriores. Adem s se dispone de VCPs que ofrecen cualquier n£mero de canales entre procesos asignados a Transputers vecinos. Sin embargo, puede utilizarse los VCPs para que los mensajes sean enviados (routing) a trav‚s de un sistema de comunicaciones que conecta todos (o varios) T9000 en el sistema. En otras palabras, es posible virtualizar las comunicaciones entre procesos asignados a T9000 que no est n directamente conectados mediante un link, marcando la ruta del mensaje por software. La capacidad de comunicaci¢n en redes amplias (network-wide) no est  implementada en el T9000, sino que necesita utilizar uno o m s dispositivos que canalicen los mensajes, tal y como muestra la figura siguiente: La posibilidad de utilizaci¢n de canales virtuales del chip T9000 permite que todos los mensajes se transmitan desde procesos remotos, a trav‚s de un £nico link. En principio, es suficiente conectar un link por Transputer a la red canalizadora (router), sin embargo, pueden conectarse varios links T9000 cuando se necesita un ancho de banda m s amplio. Otra posibilidad que aparece, es la de conectar los links no utilizados a otras redes canalizadoras (routers). El uso de varias redes en paralelo parece bastante interesante porque ofrece la posibilidad de aumentar el ancho de banda y crear planos separados de comunicaciones para diferentes tipos de mensajes de cara a mejorar el rendimiento.