Esta sección tiene como objetivo presentar un estudio de los sistemas multiprocesadores desde el punto de vista del aumento de rendimiento (Speed-up) y del tiempo de ejecución según el número de procesadores y el tamaño de la caché, propiedades que se consideran críticas para hacer un sistema con una buena relación entre las prestaciones y el coste del mismo. Todo ello utilizando el simulador Limes con una serie de programas.
El análisis se centra en dos puntos muy importantes en los sistemas multiprocesador desde el punto de vista de la coherencia de los datos, el protocolo de caché y el método de sincronización. Con respecto al primero, los analizados se basan únicamente en sondeo (Snoopy), con dos ejemplos de invalidación (MESI y Berkeley) y uno de actualización (Dragón), del segundo se tratan dos ejemplos de algoritmos basados en barrera (Sense-Reversing y Arbol). Se intenta pues, llegar a conclusiones sobre las prestaciones y tiempos de ejecución de las configuraciones explicándolas coherentemente.
Además de estos aspectos se dedica una parte de la sección a un problema realmente importante en los sistemas multiprocesador basados en bus, la falsa compartición, que puede disminuir notablemente el rendimiento del mismo si no se hace una buena elección del protocolo de caché para un tamaño de caché y número determinado de procesadores.
Los apartados son:
- Estudio comparativo de protocolos de caché .
- Problema de la falsa compartición
- Acceso a variables compartidas, sincronización .
- Estudio comparativo de protocolos de caché. En esta sección se analizan los distintos protocolos de caché (MESI, Berkeley y Dragón) sobre variaciones de tamaño de caché y número de procesadores, llegando a conclusiones de las ventajas e inconvenientes de cada uno en cada una de estas configuraciones. Además, se obtienen resultados de las propiedades de aplicarlos sobre el sistema con inicialización y sin inicialización.
- Rendimiento según número de procesadores y caché de 8KB.
Analizando comparativamente ambas gráficas respecto a considerar la inicialización o no, en el segundo caso el sistema es más rápido, hasta un 37%, esto es debido a que el periodo de inicialización significa un tiempo extra en el proceso de ejecución en el que se realizan tareas poco paralelizables como repartir a los procesadores sus procesos, en consecuencia los tres protocolos tienen casi el mismo comportamiento puesto que no pueden sacar jugo de sus propiedades pensadas para la ejecución concurrente, que es lo que se puede observar en la gráfica del rendimiento.
Con respecto al t.ejecución según el protocolo y el número de procesadores, como se puede observar en ambas, hasta 8 procesadores se obtienen aproximadamente los mismos resultados, aproximadamente 100000 ciclos sin inicialización, pero en adelante el tiempo varía según el protocolo, con un aumento notable para MESI (150%), y Berkeley(50%) así como una disminución mínima para Dragón (40%).
Esto es debido a que los protocolos de invalidación cuando ocurre un fallo de escritura o de lectura tienen que invalidar todas las copias del resto de procesadores que la poseen, con lo cual estos en los siguientes ciclos tendrán que acceder a memoria a por la nueva copia después de haber fallado al intentar leer, lo cual significara un incremento del tráfico en el bus y por tanto se requerirá más tiempo para efectuar todas estas lecturas a memoria principal y continuar con la ejecución. Para pocos procesadores este proceso casi no significa perdida de tiempo pero a medida que aumenta el número puede ser importante y un problema.
En el caso del Berkeley la mejoría con respecto al MESI es debida a que en lugar de acceder a memoria todos a por el bloque invalidado acceden al que tiene el correcto que ejerce de esta tarea con lo cual aunque este pierda prestaciones el sistema en general es más rápido puesto que no todos acceden memoria a leer todas los bloques sino que todos hacen esta función con los bloques exclusivos.
Por el contrario, Dragón, al ser un protocolo de actualización cuando modifica su copia se modifica la del resto con lo cual cuando estos hagan lectura del bloque no fallaran y no harán todos lectura a memoria, eliminando todo el tiempo de acceso de todos a hacer lecturas para obtener las copias validadas, por esta razón para un número de procesadores alto no aumenta el tiempo de ejecución.
En las siguientes gráficas se puede observar los comentados en el aumento del rendimiento (Speed-up) y su comparación con el ideal.
El resultado directo de contabilizar la inicialización es la disminución del rendimiento, alejándolo desde 4 procesadores de las posibilidades ideales, es decir con una escalabilidad hasta 2 procesadores. Por el contrario sin contabilizar la inicialización la escalabilidad aumenta hasta 8 procesadores puesto que hasta este valor el speed-up real se acerca al ideal.
Con respecto a los protocolos, el rendimiento de todos a partir de 16 procesadores disminuye aunque es más importante en el caso de los de invalidación como se ha comentado anteriormente. A partir de 16 procesadores se observa además que se aleja de las posibilidades ideales con lo cual no seria recomendable para esta configuración no superar este número y no obtener una mala relación coste-rendimiento.
- Rendimiento comparativo según número procesadores en caché de 8KB y 256KB
En este apartado se intenta observar como influye el aumento del tamaño de la caché en el número de procesadores y el protocolo utilizado. De manera comparativa se eligen dos tamaños 8 y 256 KB que difieren bastante y de esta forma observar como se comporta aumentando suficientemente el tamaño.
En primer lugar se muestran las gráficas del tiempo de ejecución sin tener en cuenta la inicialización, puesto que de ese aspecto ya se ha hablado antes:
La principal diferencia entre ambas gráficas reside en el hecho de que el protocolo Dragon aumenta el tiempo de ejecución para 4, 8 y 16 procesadores hasta aproximadamente un 60% en 16 procesadores.
Además, en general, se observa una disminución del tiempo del tiempo de ejecución hasta 4 procesadores y un aumento en adelante.
El tamaño de caché esta directamente relacionado con el número de bloques que puede albergar, de forma que dado un tamaño fijo de bloque, albergara un mayor número cuanto mayor sea esta, con lo cual habrá más probabilidad que una caché lo contenga y que este más tiempo sin desalojar por haber más espacio, y por el contrario menos de que se produzca fallo por no encontrarse en caché, en consecuencia disminuye el número de accesos a memoria y las transacciones de bus, por eso en general se observa una disminución del tiempo de ejecución.
Al aumentar la probabilidad de que un procesador contenga un bloque determinado en su caché y que este más tiempo sin ser desalojado, si se trata de un protocolo de invalidación cuando un procesador realice una escritura de un dato, posiblemente tendrá que invalidar más copias, que no será significativo, pero que además si no se vuelven a utilizar probablemente sean desalojadas antes de producir un fallo por realizar una nueva lectura/escritura, es eso por lo que el comportamiento no varia entre tamaños de caché.
Para el protocolo Dragon, actualización, al haber más copias en más procesadores tiene que actualizarlas todas aunque estas no se utilicen, puesto que quizás fueron leídas en un cierto momento para una operación únicamente pero al haber más memoria aun no han sido desalojadas, con lo cual hace actualizaciones innecesarias de copias q no se utilizan que genera tráfico innecesario, mayor tiempo de ejecución y disminución del rendimiento.
Muy importante es además el hecho de que los desalojos de la caché y en consecuencia los resultados obtenidos también dependen de la utilización de las variables en el programa que es consecuencia de la implementación del mismo.
En los gráficos siguientes se observa los efectos de lo explicado sobre el Speed-up:
Se observa que la escalabilidad del sistema bajo el protocolo dragón disminuye de 8 a 4 como consecuencia de los efectos del aumento del tamaño de caché. Del MESI y Berkeley se mantienen en el mismo valor
- Rendimiento según tamaño de caché con 4 procesadores.
Este último último apartado trata de analizar como se comporta un sistema según el protocolo utilizado modificando el tamaño de caché utilizado bajo un número de procesadores fijo.
En primer lugar se muestran los resultados de los tiempos de ejecución obtenidos tanto sin considerar como considerando la inicialización:
Con respecto a la inicialización como se puede ver se producen dos resultados, en primer lugar que disminuye el tiempo de ejecución si no se considera y en segundo lugar que también disminuye la diferencia del protocolo dragon con el resto.
Entre ambas, la característica más importante es el aumento del tiempo de ejecución del protocolo dragon con respecto del resto a partir de un tamaño determinado, manteniéndose constante. Desde 156.000 ciclos en 32KB, aumenta un 12% y se mantienen hasta 512KB, el resto disminuyen hasta 6%. En consecuencia hasta 32KB no será muy importante el tipo de protocolo que se utilice puesto que tardaran aproximadamente lo mismo pero desde ese punto en adelante interesa uno de invalidación, aunque mejor el Berkeley por lo ya comentado en el punto anterior.
A medida que aumenta el tamaño, los protocolos de actualización necesitan actualizar mayor número de copias en mas procesadores innecesariamente con lo cual disminuye el tiempo de ejecución.
La disminución en el tiempo de ejecución de los protocolos de invalidación hasta 64KB es debida a que hasta este valor no hay demasiados bloques en el procesador por lo que aunque se invalidan y se pierde tiempo accediendo a obtenerlo de nuevo por el resto después del fallo este tiempo es menor que el tiempo ganado por la tasa aciertos de escritura/lectura que se obtiene de mayor memoria.
A partir de 64KB las tasas de aciertos por mayor memoria y de fallos por invalidación se equilibran con lo cual por mucho que se aumente la memoria no se obtiene beneficio.
- Problema de la falsa compartición En una caché, sea cual sea el tipo, los datos son almacenados en líneas de un tamaño determinado, de forma que cuando el procesador hace una lectura no lee un único dato sino que capta toda la línea para almacenarla en un buffer interno y trabajar con ella. Por otro lado, cuando se comparte una variable entre procesadores en un sistema como el que estamos tratando, según los protocolos de caché, cuando uno realiza una modificación en este dato tiene la obligación de invalidar o actualizar el resto de copias en los otros procesadores que la posean, aunque realmente el principal problema se produce, como ya se ha visto, cuando se invalidan muchas copias cuando hay bastantes procesadores. Puesto que como se ha comentado no se comparten realmente datos sino líneas formadas de varios datos, cuando se invalida una variable por haber modificado su contenido, lo que realmente se hace es invalidar la línea. Aunque un procesador A trabaje con variable distinta a otra que posea otro procesador B, si estas se encuentran en la misma línea de caché, cuando A realice una escritura se invalidará la línea y en consecuencia la del procesador B aunque sean diferentes variables. La consecuencia directa de este problema se encuentra en procesos que trabajan con datos continuos en memoria, por ejemplo vectores, lo que se observa que disminuyen mucho las prestaciones aunque cada procesador realice las operaciones sobre su propio subvector no compartido. En los próximos dos apartados se observa las consecuencias de este problema realizando dos tipos de reparto de datos de las líneas de caché a los procesadores.
- Reparto consecutivo.
Trabajando con vectores de n elementos (en este caso 10000) y con m procesadores, en potencias de 2 hasta 64, se subdivide el vector en n/m trozos, dándole a cada procesador cada uno. A partir de lo visto, se espera que cuando dos procesadores se encuentren en extremos contiguos parte de los datos estarán localizados dentro de una misma línea de caché con lo cual se producirán invalidaciones. Cuanto mayor sea el tamaño de la línea más elementos cabrán y en consecuencia más invalidaciones se producirán. Se ejecuta un proceso que realiza operaciones sobre un vector de n elementos repartiéndolo entre los procesadores existentes para que se hagan las operaciones concurrentemente en la medida de lo posible. Las siguientes gráficas muestran el T. ejecución y el aumento de rendimiento del mismo:
Con respecto al T. ejecución, manteniendo ambos parecidos tiempos hasta 4 procesadores, con los siguientes Dragon sufre una relentización importante, con casi un aumento del 100% y MESI mantiene tiempos bajos aumentando a partir de 16 hasta 64 un 75% aproximadamente.
Este incremento se produce por el hecho de haber más trozos y por tanto más líneas compartidas. Los efectos se observan en el aumento del rendimientos, con una escalabilidad muy baja de solo 8 en MESI y 4 en Dragon, aunque a partir de 16 es más importante la caída de rendimiento en MESI, de 8’5 a 4`5. Para este tipo de reparto se hace más eficiente MESI que dragon.
- Reparto entrelazado.
Con vectores de n elementos y m procesadores, ahora cada elemento es asignado a un procesador en función del índice, de forma que para i desde 0 a n-1 se asignará al procesador [i mod m]+1. Con este reparto habrán con mayor probabilidad más procesadores que compartan líneas por tener datos contiguos, con lo cual los efectos deberían ser mayores que con reparto anterior. Se realiza una ejecución sobre 10000 datos y n procesadores desde 2 a 64 en potencias de 2 y se obtienen los siguientes resultados de tiempo y rendimiento:
Analizando los tiempos de ejecución se argumenta los posibles efectos comentados, tanto MESI como Dragon tienen realizan una ejecución más lenta para todos los procesadores que en consecutivo. Con respecto a lo más importante destacar que se mantienen en unos tiempos casi constantes con MESI teniendo una ejecución más lenta a excepción con 2 procesadores que es este el q sufre un pico con un aumento significativo del tiempo y Dragon una disminución. Para este número de procesadores las invalidaciones retrasan el sistema en gran medida. En la variación de rendimiento es donde se verifica que este método es mucho peor que el anterior llegando a unas prestaciones muy pobres que se alejan de las ideales en ambos protocolos con una escalabilidad de 1.
- Acceso a variables compartidas, sincronización.
- Barrera Sense-Reversing.
Consisten en sincronizar todos los elementos antes de una tarea, haciendo que hasta que todos no alcancen la misma no se continúe. Esta variación de barrera evita el problema de un bloqueo total producido en el caso de que uno se quedase colgado, para ello la variable que se utiliza para salir de la barrera se cambia así no hay posibilidad que se produzca lo anterior.
Cada procesador ejecuta el siguiente proceso:
void Proceso(void) { int i,pr,local_sense=1; LOCK(PrIdLock); pr=PrId; /* Cada identificador de proceso debe ser unico */ PrId++; /* por eso se protege con un cerrojo */ UNLOCK(PrIdLock); for (i=0; i <4; i++ ) { if (i==0) matriz[0][pr-1] = pr; else{ local_sense = !local_sense; // Evita bloqueo global LOCK(counterlock); // Primero que llega la cierra counter++; UNLOCK(counterlock); if(counter == n_pro) { // Han llegado todos a la barrera counter = 0; release = local_sense; }else // No estan todos -> while(release != local_sense); matriz[i][pr-1] = matriz[i-1][(pr-2+n_pro)%n_pro]; } } } donde las variables globales son: int matriz[4][PROC_MAX]; int PrId; /* Identificador de proceso */ int n_pro; /* Numero de procesadores totales */ int release = 1; int counter; /* Numero de procesadores en la barrera */ LOCKDEC(PrIdLock); /* Cerrojo usado para la variable anterior */ LOCKDEC(counterlock);Ejecutando el programa se obtienen los siguientes tiempos:
Que demuestran lo esperado, en primer lugar que los protocolos de actualización (dragon) ofrecen mejores tiempos que los de invalidación (MESI) para el caso de variables de sincronización y segundo que a partir de 16 procesadores no ofrece buenos resultados.
- Barrera en árbol
A medida que aumentan el número de procesadores las prestaciones de la Barrera SR disminuyen puesto que todos quieren acceder a count que es compatida y aumenta el tráfico del bus haciendo muchas lecturas continuadas a memoria. Con el fin de resolver este problema y eliminar el acceso de todos los procesadores a una variable compartida al mismo tiempo aparecen las barreras distribuidas (en árbol), donde a modo de árbol binario se hace una liberación jerarquizada.
El árbol esta formado por nodos hoja que son los procesadores y nodos intermedios que son contadores, cuando llega un proceso a la barrera este sabe que nodo le toca por lo tanto incrementa su nodo padre, que si comprueba que han llegado todos los hijos hace release del padre y este sigue el mismo procedimiento incrementando su contador y comprobando. Cuando el nodo raíz comprueba que todos los hijos han llegado hace release global para reiniciar el proceso.
El programa que se utiliza es el siguiente:
void Proceso(void) { int i,pr; int num_hijos=0; LOCK(PrIdLock); pr=PrId; PrId++; UNLOCK(PrIdLock); matriz[0][pr-1]=pr; for(i=1;i<4;i++){ if((pr*2>PROC_MAX)&&(pr!=1)){ ALOCK(contalock,pr-1); contadores[pr/2 -1]++; AULOCK(contalock,pr-1); num_hijos=0; } if(pr*2<=PROC_MAX){ if(pr*2+1>PROC_MAX) num_hijos=1; else num_hijos=2; } while(num_hijos!=contadores[pr-1]); if ((pr!=1)&&(pr*2<=PROC_MAX)){ ALOCK(contalock,pr/2-1); contadores[pr/2-1]++; AULOCK(contalock,pr/2-1); } contadores[pr-1]=0; if (pr!=1) while(liberacion[pr-1]!=1); liberacion[pr-1]=0; if (pr*2+1<=PROC_MAX) liberacion[pr*2+1-1]=1; if (pr*2 <=PROC_MAX)liberacion[pr*2-1]=1; matriz[i][pr-1]=matriz[i-1][(pr-2+PROC_MAX)%PROC_MAX]; } } Las variables globales son: int PROC_MAX=1; int matriz[4][64]; #define LONGIT 10000 ALOCKDEC(contalock,64); LOCKDEC(PrIdLock); int liberacion[64]; int count=0, release=1; int PrId; int contadores[64]; unsigned int final,inicio;Cuyos resultados son:
Sobre las conclusiones, se sigue corroborando que el protocolo Dragon es más eficiente pero lo más importante es observar que a partir de 32 procesadores se disminuye el tiempo de ejecución que es lo que se deseaba, pasando de alrededor de casi 50.000 ciclos para la barrera S-R a 30.000 en 32 procesadores y de 150.000 a 8.000 en 64.
El apartado se divide en 3 fases, dos de las cuales donde el objetivo principal es ver como afecta el número de procesadores sobre un tamaño de caché fijo (8Kb y 256Kb) y un tercero cuyo fin es observar como se comporta sobre un número de procesadores fijo (4) la variación del tamaño de caché. De las características, solo nos centraremos en el aumento de rendimiento (Speed-up) y el tiempo de ejecución, siendo las más importantes.
Del Speed-up, se incluye en las gráficas el ideal, para poder comparar con los obtenidos en las ejecuciones.
Generalmente cuando se crean programas de procesamiento de datos para multiprocesadores con el fin de aprovechar su potencia de cálculo es necesaria cierta sincronización ya sea para compartir variables entre los procesadores o para controlar su ejecución sin que unos se adelanten a otros. Si estos mecanismos no se utilizaran la ejecución produciría datos incorrectos.
Los algoritmos que se utilizan están basados en cerrojos que bloquean a los procesos a la espera de cierto evento ya sea la llegada del resto o que la sección crítica sea abierta para trabajar con un dato determinado. Entre algunos de estos se encuentran los basados en barreras que son los que se plantean para analizar, aunque existen otros también importantes.
Las pruebas se realizan sobre una matriz de 4 x n, donde n es el número de procesadores, el objetivo es que en 4 iteraciones se modifiquen los valores de cada fila desplazándolos a la derecha, con lo cual cada procesador debe mover el dato en su fila a la siguiente y si esta al final pasarlo al principio. Esto hace necesario que el procesador i en la iteración m se tenga que esperar para copiar su dato al procesador i+1 mod n al procesador i-1 mod n que acabe de la iteración m-1.
Sin sincronización, los resultados son inconsistentes escribiendo 0 en las primeras posiciones por no disponer del dato correcto, por ello se hace necesario implementar algún tipo de sincronización haciendo que el acceso a los datos sea una sección crítica.