Sistemas Multiprocesadores

Un multiprocesador puede verse como un computador paralelo compuesto por varios procesadores interconectados que comparten un mismo sistema de memoria.
Los sistemas multiprocesadores son arquitecturas MIMD con memoria compartida. Tienen un único espacio de direcciones para todos los procesadores y los mecanismos de comunicación se basan en el paso de mensajes desde el punto de vista del programador.
Dado que los multiprocesadores comparten diferentes módulos de memoria, pudiendo acceder a un mismo módulo varios procesadores, a los multiprocesadores también se les llama sistemas de memoria compartida.
Dependiendo de la forma en que los procesadores comparten la memoria, se clasifican en sistemas multiprocesador UMA, NUMA y COMA.

Multiproceso

Multiproceso es tradicionalmente conocido como el uso de múltiples procesos concurrentes en un sistema en lugar de un único proceso en un instante determinado. Como la multitarea que permite a múltiples procesos compartir una única CPU, múltiples CPUs pueden ser utilizados para ejecutar múltiples hilos dentro de un único proceso.
El multiproceso para tareas generales es, a menudo, bastante difícil de conseguir debido a que puede haber varios programas manejando datos internos (conocido como estado o contexto) a la vez. Los programas típicamente se escriben asumiendo que sus datos son incorruptibles. Sin embargo, si otra copia del programa se ejecuta en otro procesador, las dos copias pueden interferir entre sí intentando ambas leer o escribir su estado al mismo tiempo. Para evitar este problema se usa una variedad de técnicas de programación incluyendo semáforos y otras comprobaciones y bloqueos que permiten a una sola copia del programa cambiar de forma exclusiva ciertos valores.

Multitarea

Permite a múltiples procesos compartir una única CPU, múltiples CPUs pueden ser utilizados para ejecutar múltiples hilos dentro de un único proceso.

Cooperativa
Los procesos de usuario son quienes ceden la CPU al sistema operativo a intervalos regulares. Muy problemática, puesto que si el proceso de usuario se interrumpe y no cede la CPU al sistema operativo, todo el sistema estará trabado, es decir, sin poder hacer nada. Da lugar también a latencias muy irregulares, y la imposibilidad de tener en cuenta este esquema en sistemas operativos de tiempo real. Un ejemplo sería Windows hasta la versión 95. F.M.J.B. (L)(L)

Preferente
El sistema operativo es el encargado de administrar el/los procesador(es), repartiendo el tiempo de uso de este entre los procesos que estén esperando para utilizarlo. Cada proceso utiliza el procesador durante cortos períodos de tiempo, pero el resultado final es prácticamente igual que si estuviesen ejecutándose al mismo tiempo. Ejemplos de sistemas de este tipo serían Unix y sus derivados (FreeBSD, GNU/Linux), VMS y derivados, AmigaOS, Windows NT.

Real
Sólo se da en sistemas multiprocesador. Es aquella en la que varios procesos se ejecutan realmente al mismo tiempo, en distintos microprocesadores. Suele ser también preferente. Ejemplos de sistemas operativos con esa capacidad: variantes Unix, GNU/Linux, Windows NT, Mac OS X, etc.
En conclusión
Los sistemas operativos multitarea son capaces de dar servicio a más de un usuario a la vez, ya sea por medio de varias terminales conectadas a la computadora o por medio de sesiones remotas en una red de comunicaciones. No importa el número de procesadores en la máquina ni el número de procesos que cada usuario puede ejecutar simultáneamente. En esta categoría se encuentran todos los sistemas que cumplen simultáneamente las necesidades de dos o más usuarios, que comparten mismos recursos. Este tipo de sistemas se emplean especialmente en redes. En otras palabras consiste en el fraccionamiento del tiempo (timesharing).

Multihebra

Podemos definir la programación multihebra o multihilo como un estilo de ejecución en el que se conmuta entre distintas partes del código de un mismo programa durante la ejecución.
El concepto multihebra ("multithreading") es de tipo lógico. Significa que un programa puede tener varias vías de ejecución que "pueden" ser independientes. Por ejemplo: Un procesador de texto puede tener una hebra que es utilizada por el usuario para escribir y otra, que a periodos de tiempo determinados, salva a disco el contenido de la memoria, obteniendo así una copia de seguridad. Según hemos visto (Wheeler ), desde el punto de vista físico, lo que caracteriza a las diversas hebras de un proceso es que comparten ciertos recursos dentro del mismo; por ejemplo la memoria, los ficheros abiertos y las variables estáticas, mientras que mantienen independencia en los recursos que les permiten una ejecución independiente, por ejemplo su propia pila ("Stack" 2.2.6) y el estado de los registros del procesador, que es salvado y restituido cada vez que la hebra es desactivada o activada.

Paralelismo y procesamiento de vector

Procesadores vectoriales de registro vectorial
Si un procesador vectorial posee registros vectoriales, los elementos del vector que se van a procesar se cargan desde la memoria directamente en el registro vectorial utilizando una operación de carga vectorial. El vector que se obtiene a partir de una operación vectorial se introduce en un registro vectorial antes de que se pueda almacenar de nuevo en la memoria mediante una operación de almacenamiento vectorial. Esto permite que se pueda utilizar en otra operación sin necesidad de volver a leer el vector, y también permite que el almacenamiento se pueda solapar con otro tipo de operaciones. En este tipo de computadoras, todas las operaciones aritméticas ó lógicas vectoriales son operaciones registro a registro, es decir, sólo se realizan operaciones vectoriales sobre vectores que ya se encuentran almacenados en los registros vectoriales. Por este motivo, a estas computadoras se les conoce como procesadores vectoriales de registro vectorial. La figura 3 muestra la arquitectura de registros y pipelines de una computadora vectorial de registro vectorial. El número de etapas de cada pipeline se muestra entre paréntesis dentro de cada pipeline.
Procesadores vectoriales memoria a memoria
Otro tipo de procesadores vectoriales permite que las operaciones realizadas con vectores se alimenten directamente de datos procedentes de la memoria hasta los pipelines vectoriales y que los resultados se escriban directamente en la memoria. Este tipo de procesadores se conocen con el nombre de procesadores vectoriales memoria a memoria. Dado que los elementos del vector necesitan venir de la memoria en lugar de proceder de un registro, se requiere más tiempo para conseguir que la operación vectorial comience a realizarse. Esto es debido en parte al coste del acceso a la memoria. Un ejemplo de procesador vectorial memoria a memoria era el CDC Cyber 205.

Paralelismo Funcional

El paralelismo funcional divide las aplicaciones en funciones. Se podría ver como paralelismo de código. Por ejemplo puede dividirse en: entrada, preparación del problema, solución del problema, preparación de la salida, salida y mostrar la solución. Esto permite a todos los nodos producir una cadena. Esta aproximación es como la segmentación en funciones de un procesador.
Aquí se sigue la misma idea pero a nivel de software, se dividen los procesos formando una cadena y dependiendo uno del siguiente. Aunque al principio no se logre el paralelismo, una vez que se ponen todos los nodos a trabajar (i.e. cuando hayamos ejecutado N veces lo que estemos ejecutando, siendo N el número de pasos en los que hemos dividido la aplicación) se consiguen que todos los nodos estén trabajando a la vez si todas las funciones tardan el mismo tiempo en completarse. Sino, las demás funciones tienen que esperar a que se complete la función más lenta.La idea es exactamente la misma que trataremos en el tema Arquitecturas aunque allí se referencie con el término pipeline. Esta forma de paralelizar no es ampliamente usada puesto que es muy difícil dividir en funciones que tarden el mismo tiempo en ejecutarse. Sólo se usa en casos concretos donde se ve claramente que es una buena opción por ser fácilmente implementable.

Paralelismo de Datos

El paralelismo de datos se basa en dividir los datos que se tienen que procesar. Típicamente los procesos que están usando esos datos son idénticos entre sí y lo único que hacen es dividir la cantidad de información entre los nodos y procesarla en paralelo. Esta técnica es más usada debido a que es más sencillo realizar el paralelismo.
Ejemplos pueden ser los films Final Fantasy o El señor de los anillos que fueron renderizadas en un cluster de renderización con el software Maya y Renderman. Esta forma de renderizar se basa en dividir los frames (cuadros) que se deban renderizar en una escena en concreto o todos los frames de la película entre todos los ordenadores. Para ser más exactos, primero se divide el número de frames por el número de nodos y se envía el número resultante de frames a cada nodo (suponiendo que es un cluster donde todos los nodos tienen la misma capacidad de proceso). Esta es la fase de preparación y suele ser secuencial, puesto que es una pequeña parte de la producción. Una vez hecho esto, cada nodo renderiza los frames que le fueron asignados. Esta fase puede durar semanas. Una vez se tienen todos los frames se unen en un fichero único que tiene toda la película. En este caso en particular se usa paralelismo de datos, y aunque algunas imágenes tardan más en renderizarse que otras y por lo tanto algún nodo tardará menos en acabar su trabajo que otro, lo que se hace es no elegir imágenes de forma secuencial (de la 1 a la n al nodo 1) sino paralela (1 al nodo 1, 2 al nodo 2... n+1 al nodo n+1) esto suele compensar la carga entre los nodos por lo que más o menos todos los nodos se mantienen en el máximo rendimiento (si no se comprende esto, piense en lo poco que tardaría el nodo que renderize unos títulos de crédito simples).

Computadoras con multiprocesador

Las computadoras que tienen mas de un CPU son llamadas multiproceso. Un sistema operativo multiproceso coordina las operaciones de la computadoras multiprocesadoras. Ya que cada CPU en una computadora de multiproceso puede estar ejecutando una instrucci ón, el otro procesador queda liberado para procesar otras instrucciones simultáneamente. Al usar una computadora con capacidades de multiproceso incrementamos su velocidad de respuesta y procesos. Casi todas las computadoras que tienen capacidad de mu ltiproceso ofrecen una gran ventaja. Los primeros Sistemas Operativos Multiproceso realizaban lo que se conoce como: Multiproceso asimétrico: Una CPU principal retiene el control global de la computadora, así como el de los otros procesadores. Esto fue un primer paso hacia el multiproceso pero no fue la dirección ideal a seguir ya que la CPU principal podía conv ertirse en un cuello de botella. Multiproceso simétrico: En un sistema multiproceso simétrico, no existe una CPU controladora única. La barrera a vencer al implementar el multiproceso simétrico es que los SO tienen que ser rediseñados o diseñados desde el principio para trabajar en u n ambiente multiproceso. Las extensiones de Unix, que soportan multiproceso asimétrico ya están disponibles y las extensiones simétricas se están haciendo disponibles. Windows NT de Microsoft soporta multiproceso simétrico.

IBM DEEP BLUE

Deep Blue fue la primera computadora que venció a un Campeón del Mundo vigente, Garry Kasparov, con un ritmo de juego lento. Esto ocurrió el 10 de febrero de 1996, en una memorable partida. Sin embargo, Kasparov ganó 3 y empató 2 de las siguientes partidas, derrotando a Deep Blue por 4-2. El encuentro concluyó el 17 de febrero de 1996.
Deep Blue fue mejorando y jugó de nuevo contra Kasparov en mayo de 1997, ganando el encuentro a 6 partidas por 3'5-2'5, lo que lo convirtió en la primera computadora en derrotar a un campeón del mundo vigente, en un encuentro con ritmo de juego de torneo estándar. El encuentro concluyó el 11 de mayo. El sistema saca su fuerza de juego principalmente en la fuerza bruta que calcula el sistema central. Era una potencia paralela, de 30 nodos, RS/6000, SP-based el sistema informático realzado(mejorado) con 480 VLSI con el objetivo especial de jugar al ajedrez. Su programa de juego de ajedrez fue escrito en C y corrió bajo el sistema operativo AIX. Era capaz de calcular 200 millones de posiciones por segundo, dos veces más rápido que la versión de 1996. En junio de 1997, Deep Blue era el 259 superordenador más poderoso, capaz de calcular 11.38 gigaflops, aunque toda esta potencia no estaba pensada en realidad para jugar al ajedrez.

Supercomputador Cray

La empresa CRAY, fabricante de los supercomputadores CRAY X-1 ha renovado su acuerdo con AMD, por el que ésta será la encargada de seguir suministrando las CPUs para las gamas de supercomputadores CRAY XD1 y CRAY XT3. En concreto, la gama XT3 está diseñada enlazando entre sí varios chasis o "cabinets" que pueden contener, cada uno, más de 90 procesadores. El máximo número de cabinas alcanza la cifra de 320, con lo que se obtienen más de 30.000 (treinta mil) procesadores trabajando en conjunto. Opcionalmente se pueden montar CPUs Dual Opteron. La capacidad de proceso puede llegar hasta 159 TeraFlops (con núcleos Opteron de 2,6 GHz) Destaca también, la memoria RAM que puede llegar hasta los 239 TeraBytes. Con un ancho de banda de 196 TB/s. El sistema operativo para manejar estos aparatos es el UNICOS/Ic. Aunque la serie XD1 soporta LINUX. Como inconvenientes podemos citar (aparte de su elevado coste) el tamaño: 57 x 144 cm cada cabina; y su peso: más de 690 Kgs por cada cabina

Clasificación y caracteristicas de los multiprocesadores
Clasificación en función de la organización de la memoria

:::Uniform Memory Access (UMA)
–Espacio de direcciones de memoria compartido
–Tiempo de acceso uniforme para toda dirección
– Hardware bastante simple.
– El cuello de botella es el acceso a memoria principal, lo cual implica:
·Grandes cachés en cada procesador
·El número de procesadores no puede ser muy alto. Hoy en día N≤32.

Multiprocesadores muy populares hoy en día:
·Todos los SMP’s (Multiprocesadores simétricos con memoria compartida basado en bus común)
·bi, quad-Pentium
·Sun Enterprise 10000 (crossbar)
Problema de coherencia en UMA
El overhead por acceder a la memoria compartida es muy grande. Hay que usar cachés
Debemos asegurar la coherencia de los datos en dichos dispositivos
Cuando usamos un dato privado ⇒ traerlo a caché
Si accedemos a un dato compartido, hay que traerlo a caché, pero si otros procesadores también acceden al dato y se lo llevan a su caché, existirán varias copias distintas del mismo dato. Si algún procesador modifica el dato ⇒ Problema de coherencia.
Solución
Intentar evitar las incoherencias mediante hard
En UMA se usan protocolos de husmeo (snooping)
Se pueden utilizar gracias a tener un bus único y compartido de comunicación.
–Los controladores de cachés locales espían el bus para ver si circula algún dato de alguna línea que tenga almacenada en su caché
– Los cachés deben de estar provistos de 2 puertos de acceso (p.e. replicando la memoria de etiquetas)
·Uno para el acceso del procesador
·Otro para que el controlador pueda comparar las direcciones que aparecen por el bus

:::NonUuniform Memory Access (NUMA)

–Espacio de direcciones de memoria compartido
–Tiempo de acceso no uniforme para toda dirección.
Depende de si accedemos a memoria local (no a caché) o a remota.
–Debido al incremento de prestaciones del uniprocesador y del AB requerido, ésta es la única solución para sistemas con muchos procesadores
– tacc pequeño en accesos a memoria local
– Hard de la red es complejo, necesita redes de interconexión especiales. Existen distintas líneas de comunicación separadas ⇒ mayor AB
– El problema de la coherencia es más difícil de mantener en hard.
Estos multiprocesadores son escalables
Escalable: Si crece el número de procesadores N, entonces la memoria crece como orden(N). Esto es gracias a que cada procesador lleva su propia memoria.
Los procesadores UMA no son escalables, puesto que si aumentamos el número de procesadores, la memoria es la misma.
Programación y comunicación
Comunicación entre procesadores es mediante variables globales
Al tener espacio de direcciones de memoria compartida ⇒ Se adapta perfectamente a la programación multihilo (multi-thread)

·Debe existir cacheo de datos remotos en hard, aunque la coherencia sea compleja
·Debe existir soporte hard para el acceso remoto
– Ld local, provoca acceso a caché o memoria local
– Ld remoto, provoca interrupción I/O a la red
Si existe coherencia, el código NUMA es totalmente compatible con UMA. Esto supone una ventaja, puesto que los UMA están muy extendidos y hay muchas aplicaciones
desarrolladas. El programador debe tener cuidado con los accesos remotos
– Ejemplos: TC2000, KSR-1, Standford Dash, BBN Butterfly, Cray T3D

Solución al problema de coherencia en NUMA
– La solución hard es más compleja que en UMA
– Han existido máquinas con control de coherencia por software (máquinas NC, NonCoherent). CRAY T3D
– Los datos compartidos se declaran no cacheables
– Si el compilador/programador detecta que un dato compartido será leído muchas veces, y no escrito, realiza un cacheo por software
Copia el dato en una variable local privada
Trabaja con esta copia hasta que por software sepa que la copia es mala (otro procesador la modifica)

:::Message Passing Machines (MPM)

–Espacio de direcciones de memoria distribuido
–Son compatibles en hard a los NUMA
–Cada procesador es un computador independiente del resto
– Fácilmente escalable
El mecanismo de comunicación es a través de mensajes (igual que la comunicación entre procesos del S.O.). No necesita mecanismos hard ni para controlar la coherencia de cachés (pues son espacios distintos de direcciones), ni para implementar los accesos remotos
La red es la parte más compleja de escalar
Programación y comunicación
Programación orientada a multiprocesos
Comunicación se realiza por mensajes. Existen librerías estándar que:
– Realizan la mensajería
– Distribuyen los procesos por la máquinas declaradas del multicomputador
Comunicación explícita, lo cual tiene que ser tenido en cuenta por los programadores. Esto obliga a estar pendiente de ella e intentar ocultar la latencia
El overhead de comunicación es muy alto, luego interesa enviar datos grandes, p.e. Páginas

:::Emulación de Multiprocesadores

–Se puede emular un MPM en un NUMA o viceversa. El hard es muy parecido
–El MPM se emula fácilmente con un NUMA.
La emulación de paso de mensajes es sencilla si se tiene memoria compartida (escribir/leer en
una determinada dirección de memoria)
–El NUMA es más difícil de emular con un MPM
Cualquier Ld/St requiere un overhead tremendo
–Llamar al S.O. para traducir la dirección
–Comprobar protecciones
–Crear el mensaje
No tiene sentido enviar 1 solo byte o palabra, sino muchos datos de una sola vez, para ello podemos limitar la compartición de datos solo a páginas de memoria virtual ⇒ Tamaño de datos comunicados es muy grande y, por tanto, el overhead por byte es pequeño.

:::Mercado actual

Los UMA se han introducido con gran éxito en el mercado (memoria centralizada)
Fáciles de contruir
–Basados en bus común
–Hard especial para mantener la coherencia
Los microprocesadores comerciales estándar llevan soporte para UMA
Bien caracterizados y documentados
Se adaptan bien a sistemas multiusuario

Los NUMA son compatibles en soft con los UMA, luego puede aprovechar el soft ya desarrollado
–El único problema es que el hard para mantener la coherencia de los cachés es más complejo, pero en los nuevos procesadores (Alpha 21364) ya se incluye dicho hard.