Irrevocabilidad Relajada para Memoria Transaccional Hardware

Irrevocabilidad Relajada para Memoria Transaccional Hardware Ricardo Quislant, Eladio Guti´errez, Emilio L. Zapata y ´ Oscar Plata1 Resumen— Los sistemas comerciales que ofrecen memoria transaccional (TM) implementan un sistema hardware best-effort (BE-HTM) con limitaciones. Es necesario programar un fallback software basado en cerrojos para asegurar el progreso de la aplicaci´on, lo que a˜nade complejidad al paradigma. En este art´ıculo se propone un nuevo tipo de irrevocabilidad hardware (un modo transaccional que marca las transacciones como no abortables) para hacer frente a las limitaciones de los sistemas BEHTM de una manera m´as eficiente, y para liberar al usuario de tener que programar un fallback. Se basa en el concepto de suscripci´on relajada utilizada en el contexto de la programaci´on de fallbacks basada en cerrojos, donde la transacci´on se suscribe al cerrojo al final de la misma en lugar de al principio. El mecanismo de irrevocabilidad relajada hardware no involucra cambios en el protocolo de coherencia y se compara con su hom´ologo software, que proponemos como un fallback con suscripci´on relajada de espera escapada. Tambi´en proponemos la irrevocabilidad relajada con anticipaci´on, un mecanismo que no se puede implementar en software, y que mejora el rendimiento de las aplicaciones con m´ultiples reemplazos de bloques transaccionales de cach´e. La evaluaci´on de las propuestas se lleva a cabo con el simulador Simics/GEMS junto con la suite de benchmarks STAMP, y se obtiene una mejora de rendimiento sobre el fallback del 14% al 28% para algunos benchmarks. Palabras clave— Memoria Transaccional Hardware; Best-effort; Irrevocabilidad Relajada; Fallback I. Introducci´ on LA memoria transaccional (TM) es un paradigma de programaci´on cuyo prop´osito es facilitar la programaci´on concurrente y maximizar el paralelismo en multiprocesadores de memoria compartida. Despu´es de veinte a˜nos de su publicaci´on por Herlihy y Moss [1], la TM hardware (HTM) se incluye en los procesadores Intel Haswell [2] e IBM BlueGene/Q [3] en 2013. IBM tambi´en lanza dos sistemas HTM diferentes en sus procesadores System z [4] y Power 8 [5]. Estos sistemas son una forma best-effort de HTM (BE-HTM) donde las transacciones que no encuentran impedimentos se ejecutan en hardware, pero las que encuentran alguna limitaci´on, como fallos de capacidad, interrupciones o conflictos persistentes, tienen que ser ejecutadas por un fallback para asegurar el progreso de la aplicaci´on. El fallback de una transacci´on tiene que ser programado por el usuario en la mayor´ıa de estos sistemas, lo que va en contra del prop´osito principal del paradigma TM, la simplicidad. Sin embargo, BlueGene/Q elimina la necesidad de fallback por medio de un runtime software que implementa irrevocabilidad [6]. Siempre que una transacci´on no pueda fi1Dpto. de Arquitectura de Computadores, Univ. M´alaga, e-mail: {quislant, eladio, zapata, oplata}@uma.es. nalizar despu´es de un n´umero de reintentos se hace irrevocable para que no pueda ser abortada. En este modo, el sistema puede ser incapaz de mantener informaci´on transaccional de la transacci´on por lo que los dem´as hilos de ejecuci´on deben parar. En este art´ıculo se propone la irrevocabilidad relajada como un modo de irrevocabilidad mejorado basado en el concepto de suscripci´on relajada [7] que se usa en la programaci´on de fallbacks en sistemas BE-HTM [8]. En una implementaci´on de fallback simple con un solo cerrojo global las transacciones se suscriben al cerrojo ley´endolo al principio. La suscripci´on relajada se hace al final de la transacci´on permitiendo m´as paralelismo. La ejecuci´on es segura ya que la suscripci´on al cerrojo, el aislamiento de las transacciones y el aislamiento fuerte con respecto al c´odigo no transaccional [9] abortan las transacciones que hacen alg´un acceso indebido. Las contribuciones de este art´ıculo son las siguientes: •Un mecanismo de irrevocabilidad relajada: Se permite paralelismo entre las transacciones normales y la irrevocable, pero las primeras han de parar antes de finalizar y esperar a que acabe la irrevocable. De esta manera se preserva el c´omputo realizado a no ser que un conflicto las haga abortar. El modo irrevocable se arbitra por un protocolo basado en token independiente del protocolo de coherencia. •Un fallback de suscripci´on relajada con espera escapada: Es el hom´ologo software del mecanismo anterior. Se trata del fallback propuesto en [8] con una espera escapada que retrasa la finalizaci´on de la transacci´on hasta que acabe la transacci´on que est´a en el fallback. El sistema transaccional ha de permitir instrucciones escapadas dentro de las transacciones [10]. •Un mecanismo de irrevocabilidad relajada con anticipaci´on de reemplazo: Se realizan ligeras modificaciones al protocolo de coherencia para anticipar un reemplazo de un bloque transaccional de cach´e, de manera que se pide la irrevocabilidad antes de que se produzca. Este mecanismo no se puede implementar en software. Con estas propuestas se pretende tener una soluci´on BE-HTM que no requiera un esfuerzo extra por parte del usuario y que maximice el paralelismo. La evaluaci´on con el sistema simulado Simics [11]/GEMS [12] y con la suite de benchmarks STAMP [13] muestra un rendimiento mejorado para ciertos benchmarks de hasta el 28%. II. Trabajo Relacionado Intel Haswell [2] e IBM System z [4] y Power 8 [5] incluyen sistemas BE-HTM que requieren un fallback software para garantizar el progreso de las aplicaciones transaccionales. Estos sistemas usan las cach´es privadas para mantener los datos transaccionales y se basan en el protocolo de coherencia para detectar conflictos. En cuanto a las instrucciones de escape [10], s´olo Power 8 permite una forma de instrucciones no transaccionales dentro de transacciones a trav´es de su modo transaccional suspendido [14]. IBM Blue Gene/Q [3] usa una soluci´on diferente que utiliza la cach´e L2 para almacenar los datos transaccionales, gracias a su cach´e asociativa por conjuntos con multiversi´on, donde un bloque puede estar a su vez en forma transaccional y no transaccional. Para asegurar el progreso de las transacciones utiliza un modo de irrevocabilidad implementado en un runtime software. Si una transacci´on supera un n´umero de abortos dado entra en irrevocabilidad, y su identificador se inserta en una tabla hash para que sucesivas ejecuciones de la misma s´olo permitan un aborto antes de entrar en irrevocabilidad. BG/Q aborta la transacci´on en un fallo de capacidad a diferencia de nuestro sistema con anticipaci´on de reemplazo. Adem´as, puede sufrir el problema de contenci´on debido al cerrojo con el que implementa la irrevocabilidad. En lo que se refiere a fallbacks software, Calciu et al. [8] proponen el fallback con suscripci´on relajada para sistemas como Haswell, que proporcionan aislamiento fuerte, y hardware sandboxing. Su fallback favorece el paralelismo entre las transacciones que no han tomado el fallback y aquella que lo ha tomado. Pero si a la hora de finalizar una transacci´on se comprueba en la suscripci´on al cerrojo que el fallback sigue en ejecuci´on se aborta la transacci´on. La irrevocabilidad en el contexto de HTM fue propuesta en un principio para asegurar el progreso en el sistema BE-HTM TCC [15]. Blundell et al. [16] la introducen para ejecutar las transacciones que exceden los recursos. Su sistema OneTM-Serialized es una implementaci´on simplificada que no permite la ejecuci´on de transacciones que no han excedido los recursos ni la ejecuci´on de c´odigo transaccional en paralelo con la irrevocable. Ofrecen otra versi´on de su sistema llamada OneTM-Concurrent que permite m´as concurrencia, pero para su implementaci´on necesitan incluir informaci´on transaccional en memoria principal para que se puedan detectar conflictos entre el c´odigo (no) transaccional y la transacci´on irrevocable. Nuestra propuesta de irrevocabilidad consigue una concurrencia similar sin necesidad de una modificaci´on tan dr´astica. III. Arquitectura del Sistema La arquitectura del sistema que hemos utilizado en este art´ıculo se muestra en la Fig. 1. El sistema usa la cach´e L1 privada para almacenar los valores nuevos de las escrituras transaccionales, mientras que los Banco L2 CPU L1 I&D ... ... ... xR/xW Datos Controlador Directorio/Datos V Controlador de Memoria Controlador de Memoria Controlador Fig. 1. Arquitectura del sistema base BE-HTM. valores antiguos se mantienen en la L2. Se guardan un par de bits de lectura y escritura transaccionales (xR/xW) por bloque de cach´e L1. Estos bits se pueden borrar en un solo ciclo cuando se aborta o se finaliza una transacci´on. En caso de aborto, los bloques cuyo bit de escritura transaccional est´a a 1 tambi´en son invalidados. El protocolo de cach´e mantiene aislamiento fuerte [9] e implementa una pol´ıtica de detecci´on de conflictos eager. La pol´ıtica de resoluci´on de conflictos es requester-wins, es decir, el que pide el dato aborta al que lo tiene. El protocolo de cach´e est´a basado en directorio y est´a modificado para soportar el sistema transaccional. Las modificaciones son: •Copiar en la primera escritura transaccional: Un bloque modificado en L1 tiene que ser guardado en L2 antes de que una transacci´on escriba en ´el para que la L2 mantenga la copia antigua m´as reciente. •Abortar en reemplazos: Un reemplazo de un bloque transaccional supone abortar la transacci´on, incluso si el reemplazo en L1 es debido a un reemplazo en L2 por la propiedad de inclusi´on. •Servir los datos antiguos desde la L2: Si una transacci´on requiere un dato de una transacci´on que fue abortada debe de ser servido por la cach´e L2. Un paquete reenviado desde la L2 a una L1 ser´a devuelto por esta a la L2 para que sirva el dato. Por ´ultimo, el sistema BE-HTM permite instrucciones de escape [10] y es impl´ıcitamente transaccional, lo que quiere decir que todas las instrucciones incluidas en una transacci´on son tomadas como transaccionales, excepto aquellas que est´en escapadas. IV. Irrevocabilidad Relajada El mecanismo de irrevocabilidad relajada implica cambios en los procedimientos de inicio y finalizaci´on de una transacci´on, e involucra un protocolo de comunicaci´on de irrevocabilidad para indicar a todos los n´ucleos del multiprocesador el cambio a modo irrevocable por parte de una transacci´on. Sin embargo, no se modifica el protocolo de coherencia ni el conjunto de instrucciones. Al iniciar una transacci´on primero hemos de comprobar si la transacci´on se tiene que ejecutar en modo irrevocable. Usualmente, esto consiste en verificar que la transacci´on haya llegado a su l´ımite de abortos. Si la transacci´on tiene que entrar en irrevocabilidad se pide a trav´es del protocolo de comunicaci´on (V´ease la Secci´on IV-B). Otra transacci´on en modo irrevocable puede hacernos esperar. Una vez que se nos permite entrar en modo irrevocable la transacci´on se ejecuta con el sistema de aislamiento transaccional desactivado, es decir, como si fuera c´odigo no transaccional. De esta manera no se puede abortar. Cuando se llega al final de la transacci´on lo ´unico que tenemos que hacer es comunicar el final de la irrevocabilidad. En caso de que no tengamos que entrar en irrevocabilidad todav´ıa, el inicio de la transacci´on se ejecuta con normalidad, activando el aislamiento transaccional, lo que llevar´a a que cada lectura y escritura marque su respectivo bit de bloque de la cach´e (xR/xW). Cuando la transacci´on llega a la fase de finalizaci´on se comprueba la existencia de una transacci´on irrevocable en el sistema. Si la hay, la transacci´on se para hasta que finalice la irrevocable. N´otese que una transacci´on puede ser abortada estando en el estado de espera. A. Correctitud El mecanismo de irrevocabilidad relajada asegura una ejecuci´on correcta debido a que se cumplen tres propiedades en el sistema BE-HTM: •Aislamiento transaccional: esta propiedad asegura que cualquier escritura transaccional s´olo ser´a visible por la transacci´on que la ejecut´o. •Aislamiento fuerte: define la relaci´on entre los accesos transaccionales y el c´odigo no transaccional. Con aislamiento fuerte, si una instrucci´on no transaccional escribe una posici´on de memoria que est´a en el conjunto de datos de una transacci´on, se abortar´a la transacci´on. •Finalizaci´on postergada: el mecanismo de irrevocabilidad posterga la finalizaci´on de la transacci´on siempre que haya una transacci´on irrevocable en el sistema. La Fig. 2 muestra los cuatro posibles casos de ejecuci´on de una transacci´on normal e irrevocable. El primero muestra una transacci´on irrevocable en el primer hilo (Th1) que empieza despu´es de una normal en el segundo (Th2). Pero la transacci´on de Th2 finaliza antes que la irrevocable. En este caso se deber´ıa abortar la transacci´on de Th2 ya que ha le´ıdo la posici´on Y (LD Y) escrita por la irrevocable (ST Y) y finaliza antes, lo que compromete la serializabilidad [17]. Sin embargo, a diferencia del fallback con suscripci´on relajada descrito en la Secci´on II, nuestro mecanismo de irrevocabilidad no aborta la transacci´on, si no que posterga su finalizaci´on hasta que acabe la irrevocable. En el peor caso, la transacci´on ser´a abortada un poco m´as tarde debido a un conflicto con otra transacci´on o con la irrevocable por aislamiento fuerte. Con suerte, la transacci´on podr´a finalizar mejorando as´ı la concurB C Th1 I F Th2 C B Th1 I F C Th2 B Th1 I F C Th2 C B Th1 I F C Th2 PP Transaccional Parado No transaccional Caso 1 Caso 2 Caso 3 Caso 4 ST Y LD Y Tiempo I P F Parar Transacción Inicio Irrevocabilidad Final Irrevocabilidad B C Inicio Transacción Final Transacción Leyenda ST X LD X ST X Fig. 2. Casos de ejecuci´on para evaluar la correctitud de la irrevocabilidad relajada. rencia. El Caso 2 muestra un escenario correcto donde la irrevocable acaba antes que la transacci´on normal. De hecho, el Caso 1 es una adaptaci´on artificial al Caso 2 gracias a la finalizaci´on postergada. La misma adaptaci´on se realiza con el Caso 3 y el 4 donde la irrevocable empieza antes que la normal. De nuevo, la serializabilidad podr´ıa romperse si Th1 modifica X antes de que la transacci´on de Th2 lo lea. Postergar la finalizaci´on soluciona el problema. B. Protocolo de Comunicaci´on de Irrevocabilidad Para la comunicaci´on de la irrevocabilidad proponemos un protocolo basado en token donde s´olo el n´ucleo que posee el token puede ejecutar una transacci´on en modo irrevocable. Cada n´ucleo tiene un bit, I, que indica si hay una transacci´on irrevocable corriendo en el sistema. Se necesita otro bit, T, para se˜nalizar si se posee el token. Junto con este par de bits (I,T), cada n´ucleo posee un contador (C) que mantiene el n´umero de reintentos de la transacci´on en curso. El n´ucleo pide la irrevocabilidad cuando C llega a cero. Dependiendo del valor del par de bits (I,T) el controlador de L1 de cada n´ucleo act´ua en consecuencia: •(I,T) = (0,0): No hay transacciones irrevocables y no tenemos el token. Si tenemos que pedir irrevocabilidad se difunde un mensaje de petici´on de token que ser´a respondido por el n´ucleo que lo posee. Si ese n´ucleo acaba de iniciar una transacci´on irrevocable no mandar´a el token y quedaremos a la espera. Si recibimos el token ponemos el bit T a 1 y difundimos un mensaje de irrevocabilidad para que el resto de n´ucleos ponga su bit I a 1. Cuando est´en a 1 podremos continuar en modo irrevocable, (1,1). En caso de encontrar (0,0) al finalizar una transacci´on es que no hay transacciones irrevocables y no tenemos que postergar la finalizaci´on. Th1 Th2 Th3 X A B C I G L Inicio Transacción Final Transacción Pedir Irrevocabilidad Recibir ACKs Aborto Transacción Adquirir Cerrojo Liberar Cerrojo Transaccional Parado No transaccional Leyenda Fallback con Suscripción Relajada BBB L L L A A A X Irrevocabilidad Relajada con Anticipación B B B A G AA I C C Th1 Th2 Th3 A O O OReemplazo de capacidad E G X C C A X A EFinal Irrevocabilidad AACK Fig. 3. Escenario de ejecuci´on de irrevocabilidad relajada con anticipaci´on contra fallback con suscripci´on relajada. •(I,T) = (0,1): El n´ucleo tiene el token por lo que puede informar de que va a entrar en irrevocabilidad directamente ya que nadie m´as est´a en modo irrevocable. •(I,T) = (1,0): Otro n´ucleo est´a en modo irrevocable. Si tenemos que pedir irrevocabilidad pararemos hasta que I sea 0. De la misma manera, si tenemos que finalizar una transacci´on tambi´en pararemos hasta recibir el mensaje de fin de la irrevocabilidad. En ese momento se finalizar´a la transacci´on. El caso en el que varias transacciones piden el token al mismo tiempo se arbitra por medio de las colas de mensajes que poseen los routers de la red de interconexi´on y de la cola del controlador de memoria del n´ucleo que posee el token. El uso de este protocolo de comunicaci´on evita el efecto de la contenci´on por cerrojo (v´ease la Secci´on VII-C). Adem´as, no es necesario alojar el cerrojo y el contador en la L1, lo que podr´ıa causar abortos innecesarios. V. Irrevocabilidad Relajada con Anticipaci´ on de Reemplazo La anticipaci´on a un reemplazo de un bloque transaccional consiste en pedir irrevocabilidad antes de que se produzca el reemplazo para continuar la transacci´on en modo irrevocable sin tener que perder el c´omputo hecho hasta el momento. Esta optimizaci´on no se puede realizar en fallbacks software. La Fig. 3 muestra c´omo se comportar´ıa la irrevocabilidad relajada con anticipaci´on de reemplazo en contraste con el fallback con suscripci´on relajada. El hilo 1, Th1, encuentra un reemplazo de cach´e que causar´ıa un aborto. Pero en el caso de la irrevocabilidad se pide irrevocabilidad y se retiene el reemplazo. En cuanto al fallback, Th1 aborta y reintenta la transacci´on tras adquirir el cerrojo del fallback. Las otras transacciones contin´uan debido a la suscripci´on relajada. Sin embargo, Th2 finaliza antes que el fallback por lo que tiene que abortar. Despu´es de abortar trata de adquirir el cerrojo pero tiene que esperar a que lo libere Th1. La transacci´on de Th3 finaliza despu´es de la de Th1 yTh2 pero tiene que abortar porque Th2 adquiri´o el cerrojo un poco antes. Con la irrevocabilidad relajada se espera hasta recibir el mensaje de final de irrevocabilidad, que es cuando Th2 finaliza su transacci´on. En este caso, la transacci´on de Th3 que finalizaba despu´es de las anteriores no tiene que esperar. A. Implementaci´on La implementaci´on de la anticipaci´on de reemplazo requiere ligeras modificaciones del protocolo de coherencia de cach´e puesto que hay que intervenir las acciones realizadas en los eventos de reemplazo. La Tabla I muestra dichas modificaciones sombreadas. El reemplazo de bloques no transaccionales, ¬(xR∨xW), se realiza sin modificaci´on. Sin embargo, si el bloque es transaccional, xR∨xW, se comprueba el contador de reintentos (C) para ver si la transacci´on ha llegado a su l´ımite. Si no ha llegado, la transacci´on aborta y se decrementa el contador. El bloque cambia su estado a inv´alido, I. N´otese que un reemplazo de cach´e puede no ser un evento persistente. Por lo tanto, la transacci´on se reintenta hasta que llega al l´ımite menos uno, C≤1, de manera que se anticipa el ´ultimo reintento y se pide irrevocabilidad. El mensaje que caus´o el reemplazo es reciclado en la cola de la CPU hasta que entremos en irrevocabilidad, parando as´ı al procesador. Un paso importante que tiene que realizar el protocolo de irrevocabilidad es limpiar los bits xR y xW como si se tratar´a de finalizar la transacci´on. De esta manera, el mensaje reciclado que caus´o el reemplazo transaccional causar´a ahora un reemplazo no transaccional. Los reemplazos de bloques de L1 debidos a reemplazos en L2 y la propiedad de inclusi´on se muestran como Reempla L2 en la Tabla I. Los reemplazos de L2 no transaccionales se dejan igual, se reconoce el reemplazo y se invalida el dato. Se manda el dato tambi´en en caso de que se haya modificado. Sin embargo, cuando el dato a reemplazar por la L2 es transaccional en la L1, xR∨xW, abortamos la transacci´on y decrementamos el contador de reintentos siempre que no hayamos llegado al l´ımite de abortos o haya otra transacci´on en modo irrevocable, (I,T)=(1,0). Esta ´ultima condici´on, que no est´a presente en los reemplazos de L1, se necesita para abortar la transacci´on, ya que puede haber un interbloqueo si es la irrevocable la que necesita reemplazar TABLA I Modificaciones del protocolo de coherencia de cach´ e L1 para la anticipaci´ on de reemplazo. Estado Eventos Reempla L1 Reempla L1 Reempla L1 Reempla L2 Reempla L2 Reempla L2 ¬(xR∨xW) (xR∨xW)∧(C>1) (xR∨xW)∧(C≤1) ¬(xR∨xW) (xR∨xW) (xR∨xW) (1,0)∨(C>1) (0,-)∧(C≤1) I – – – ACK – – S – /I Aborto, C-1 /I Irre, Z ACK /I Aborto, C-1 /I Irre, Zz E PUT(no datos) /I Aborto, C-1 /I Irre, Z ACK /I Aborto, C-1 /I Irre, Zz M PUT+Datos /I Aborto, C-1 /I Irre, Z ACK+Data /I Aborto, C-1 /I Irre, Zz Irre: pedir irrevocabilidad. Z, Zz: reciclar las colas de CPU y de red, respectivamente. (#,#): par de bits (I,T). el bloque de L2 para continuar. De esta manera, un hilo s´olo puede esperar a entrar en irrevocabilidad si su transacci´on lleg´o al l´ımite de reintentos y ninguna transacci´on del sistema est´a en modo irrevocable, (0,-)∧(C≤1). En el caso de que una transacci´on acabe de pedir irrevocabilidad pero todav´ıa no hemos sido informados, permaneceremos parados reciclando el mensaje de reemplazo y cuando los bits (I,T)=(0,-) cambien a (1,0) se lanzar´a el evento anterior y nuestra transacci´on ser´a abortada. VI. Fallbacks Software La Fig. 4 muestra el c´odigo de un fallback con suscripci´on relajada. Definimos dos primitivas para empezar una transacci´on: (i) TAKE_XACT_CHECKPOINT toma un checkpoint para guardar el punto al que volver tras un aborto, pero no empieza el aislamiento transaccional (l´ınea 3); y (ii) BEGIN_XACT inicia el sistema transaccional de manera que cada lectura y escritura sea aislada adecuadamente (l´ınea 8). As´ı es posible insertar c´odigo no transaccional entre las dos primitivas para comprobar si tenemos que ejecutar el fallback. El procedimiento de inicio de una transacci´on (l´ıneas 2–10) comienza tomando el punto de retorno e incrementando la variable local que mantiene el n´umero de reintentos de la transacci´on (l´ınea 4). Si la transacci´on lleg´o al l´ımite de reintentos definido globalmente en RETRY_LIMIT se intenta adquirir el cerrojo global (l´ınea 6). Si no, el hilo ejecuta de forma transaccional (l´ınea 8). El procedimiento de finalizaci´on (l´ıneas 11–17) comprueba la variable local que almacena el n´umero de reintentos para saber si se adquiri´o el cerrojo. Si no, se realiza la suscripci´on al cerrojo (l´ıneas 13 y 14) comprobando si el cerrojo est´a a cero. Se trata de la suscripci´on relajada descrita en la Secci´on II. Si est´a a uno abortamos expl´ıcitamente. Si venimos de ejecutar el fallback liberamos el cerrojo (l´ınea 16). En la Fig. 4 se puede ver nuestra propuesta de fallback con suscripci´on relajada con espera escapada que es el hom´ologo software de la irrevocabilidad relajada sin anticipaci´on de reemplazo. Consiste en sustituir la cl´ausula condicional por un bucle en el que se permanecer´a hasta que el cerrojo se libere. Pero esta espera debe estar escapada para no incluir el cerrojo en el conjunto de lectura de la transacci´on, ya que de otro modo la liberaci´on del cerrojo abor1 localRetries = 0; 2 void beginTransaction(&localRetries) { 3 TAKE_XACT_CHECKPOINT; //Punto de retorno 4 localRetries++; //Incrementar reintentos 5 if (localRetries > RETRY_LIMIT) { //Fallback? 6 while(!lockAcquire(globalLock)) ; //Adquirir cerrojo 7 } else { // Ejecución transaccional 8 BEGIN_XACT; 9 } 10 } 11 void endTransaction(localRetries) { 12 if (localRetries <= RETRY_LIMIT) { 13 if(lock != 0) //Suscripción relajada 14 ABORT_XACT; 15 COMMIT_XACT; 16 } else lockRelease(globalLock); 17 } BEGIN_ESCAPE; //Espera escapada while(lock != 0) ; END_ESCAPE; { { Fig. 4. C´odigo de fallback con suscripci´on relajada y con espera escapada. tar´ıa la transacci´on debido al aislamiento fuerte. VII. Evaluaci´ on A. Metodolog´ıa Hemos usado el simulador Simics [11] junto con el m´odulo GEMS [12] que implementa el simulador de memoria de un multiprocesador. Hemos simulado el BE-HTM de la secci´on III con las siguientes caracter´ısticas: 16 n´ucleos escalares, con cach´e L1 privada de 32KB y 4 v´ıas. Cach´e L2 unificada y compartida dividida en 16 bancos de 512KB y 8 v´ıas. Directorio de vector de bits completo y red Garnet [18]. El n´umero de hilos est´a limitado a 15 para que el sistema no haga migraciones. Los benchmarks son de la suite de la universidad de Stanford STAMP [13]. La Tabla II muestra los par´ametros que se han usado para cada benchmark y las principales caracter´ısticas transaccionales como el n´umero de transacciones, el porcentaje de tiempo dentro de transacci´on y la media del tama˜no de los conjuntos de lectura y escritura de las transacciones, en bloques de cach´e. B. Resultados En esta secci´on se analizan los resultados obtenidos con nuestros mecanismos de irrevocabilidad, compar´andolos con los resultados del fallback hom´ologo al mecanismo de irrevocabilidad sin anticipaci´on. Tambi´en se analizan los resultados del fallback con suscripci´on relajada. La Fig. 5 muestra TABLA II Benchmarks: Par´ ametros y caracter´ ısticas transaccionales. Benchmark Entrada # Xact Tiempo avg|RS|avg|WS| en Xact Bayes -v32 -r1024 -n2 -p20 -i2 -e2 -s1 654 94% 87.64 48.91 Genome -g512 -s32 -n32768 19496 85% 23.34 3.58 Intruder -a10 -l16 -n4096 -s1 54933 92% 9.87 3.06 Kmeans-high -m15 -n15 -t0.05 -i random-n2048-d16-c16 8235 46% 6.23 1.75 Kmeans-low -m40 -n40 -t0.05 -i random-n2048-d16-c16 10980 12% 6.23 1.75 Labyrinth -i random-x32-y32-z3-n96 222 100% 139.34 95.12 SSCA2 -s14 -i1.0 -u1.0 -l9 -p9 93721 13% 3.00 2.00 Vacation-high -n4 -q60 -u90 -r16384 -t4096 4095 95% 63.20 10.16 Vacation-low -n2 -q90 -u98 -r16384 -t4096 4095 93% 48.17 8.60 Yada -a20 -i633.2 5447 100% 62.45 38.21 los resultados de rendimiento sobre la aplicaci´on secuencial para los sistemas mencionados . Todos los experimentos fueron realizados con el contador de reintentos configurado a cinco repeticiones, que es un valor frecuentemente usado en la bibliograf´ıa [4], [2]. Los resultados muestran tres benchmarks que no escalan: Bayes, Labyrinth y Yada. Estos benchmarks dan un rendimiento como el de la aplicaci´on secuencial. Adem´as, con un s´olo hilo los resultados son incluso peores que el secuencial. Esta degradaci´on se debe al n´umero de reintentos antes de la irrevocabilidad. Las transacciones que desbordan la cach´e abortan cinco veces hasta que se entra en irrevocabilidad lo que hace que se rinda peor que el secuencial. El mecanismo de irrevocabilidad que anticipa el ´ultimo aborto rinde un poco mejor que los dem´as debido a que hay un aborto menos. El siguiente grupo de benchmarks escala adecuadamente y muestra poca diferencia entre los distintos m´etodos estudiados. Este grupo se compone de Kmeans-low, SSCA2 y Vacation-low. Estos benchmarks tienen transacciones peque˜nas en media, Kmeans-low y SSCA2 pasan al rededor de un 13% del tiempo dentro de transacci´on (v´ease la Tabla II) y todos ellos muestran baja contenci´on. La Tabla III muestra el n´umero de transacciones irrevocables desglosadas por causa y podemos ver que el porcentaje de transacciones irrevocables est´a en torno al 5% para 15 hilos. Adem´as, Kmeans y SSCA2 no muestran transacciones irrevocables debido a reemplazos de cach´e por lo que el sistema con anticipaci´on no produce ning´un beneficio. Por el contrario, Vacation s´ı muestra transacciones irrevocables debido a reemplazos, debido a su conjunto de lectura m´as grande, pero no son suficientes como para suponer una mejora de rendimiento. Sin embargo, con respecto al fallback relajado nuestras propuestas muestran una mejora notable para 15 hilos ya que al haber baja contenci´on los abortos del fallback relajado penalizan el rendimiento para ning´un benchmark. El ´ultimo grupo de benchmarks muestra una mejora en el rendimiento cuando se usa la irrevocabilidad en lugar del fallback software: Genome, Intruder, Kmeans-high y Vacation-high. Se puede observar que la irrevocabilidad relajada con y sin anticipaci´on pueden dar un resultado muy parecido TABLA III N´ umero de transacciones irrevocables por causa: debido a un reemplazo de L1, L2, o conflicto. Bench # Transacciones Irrevocables (L1/L2/Conflicto) 8 th’s 15 th’s Bayes 211(62/0/149) 226(34/0/191) Genome 1119(922/0/197) 1434(1165/0/268) Intruder 6397(42/0/6355) 16619(89/0/16530) Kmeans-high 1043(0/0/1043) 1986(0/0/1986) Kmeans-low 291(0/0/291) 567(0/0/567) Labyrinth 106(29/0/77) 117(22/0/96) SSCA2 283(0/0/283) 527(0/0/527) Vacation-high 336(268/0/68) 428(302/0/126) Vacation-low 103(69/0/33) 247(181/3/63) Yada 1863(581/0/1282) 1883(540/2/1342) entre s´ı y mejor que el fallback con espera escapada, hom´ologo de la irrevocabilidad sin anticipaci´on, sobre todo para Intruder, Kmeans-high y Vacationhigh con un 14%, un 25% y un 13% de mejora respectivamente. Esto ocurre cuando la causa principal de entrar en irrevocabilidad son los conflictos, y los reemplazos no tienen una posici´on dominante, como se puede ver en la Tabla III. Vacation-high, sin embargo, muestra un mayor n´umero de transacciones irrevocables debidas a reemplazos, y el mecanismo de irrevocabilidad con anticipaci´on realmente muestra mejores resultados que el que no tiene anticipaci´on, pero no parece algo significativo. La Secci´on VII-C explica el efecto que la contenci´on de cerrojos tiene en el fallback hom´ologo a nuestro mecanismo de irrevocabilidad, que hace que el fallback pierda rendimiento. Por ´ultimo, Genome muestra una mejora de rendimiento notable de un 28% con respecto al fallback con espera escapada y al mecanismo de irrevocabilidad sin anticipaci´on. En este caso, las transacciones irrevocables de Genome son principalmente debidas a fallos de capacidad, ya que tiene un numeroso grupo de transacciones con un conjunto de lectura grande. En cualquier caso, nuestros mecanismos de irrevocabilidad no penalizan el rendimiento. C. Efecto de la Contenci´on de Cerrojos Hemos visto como el mecanismo de irrevocabilidad relajada sin anticipaci´on puede dar mejores resultados que su hom´ologo software, incluso cuando se im- 1 2 4 8 15 # Hilos 0 1 2 Rendimiento Bayes 1 2 4 8 15 # Hilos 0 1 2 3 4 5 6 Rendimiento Genome 1 2 4 8 15 # Hilos 0 1 2 3 4 Rendimiento Intruder 1 2 4 8 15 # Hilos 0 1 2 3 4 5 6 7 8 9 Rendimiento Kmeans-high 1 2 4 8 15 # Hilos 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Rendimiento Kmeans-low 1 2 4 8 15 # Hilos 0 1 2 Rendimiento Labyrinth 1 2 4 8 15 # Hilos 0 1 2 3 4 5 6 7 8 9 Rendimiento SSCA2 1 2 4 8 15 # Hilos 0 1 2 3 4 5 6 7 8 9 10 Rendimiento Vacation-high 1 2 4 8 15 # Hilos 0 1 2 3 4 5 6 7 8 9 10 11 12 Rendimiento Vacation-low 1 2 4 8 15 # Hilos 0 1 2 Rendimiento Yada IrreRelajada+Anticipa IrreRelajada FallbackRelajado+EsperaEscapada FallbackRelajado Fig. 5. Rendimiento sobre la aplicaci´on secuencial de los mecanismos de irrevocabilidad relajada con y sin anticipaci´on, junto con los fallbacks con suscripci´on relajada con y sin espera escapada. plementan esencialmente de la misma manera. Sin embargo, el fallback utiliza cerrojos que introducen un efecto de contenci´on del que carece nuestro sistema de irrevocabilidad, que utiliza el protocolo de comunicaci´on basado en token. Con el uso de cerrojos se puede dar la situaci´on de que un grupo de transacciones est´e esperando para finalizar sus transacciones debido a la transacci´on que est´a en el fallback. Est´an postergando su finalizaci´on con la espera escapada. Por otro lado podemos tener un grupo de transacciones que est´a esperando a que termine la transacci´on que est´a en el fallback, para entrar uno de ellos. Cuando la transacci´on que est´a en el fallback libera el cerrojo, se invalidan todas las copias privadas del mismo que residen en las cach´es L1, y los dos grupos de transacciones esperando por distinto motivo piden acceso al cerrojo. Si la que obtiene el acceso primero es una de las que quer´ıa entrar al fallback, esta pondr´a el cerrojo a uno y todas las dem´as transacciones encontrar´an el cerrojo adquirido nuevamente. Por lo tanto, aquellas que estaban postergando su finalizaci´on, seguir´an en la espera escapada, con el riesgo de poder ser abortadas. Este efecto de contenci´on debido al cerrojo no se da en nuestro protocolo de comunicaci´on de irrevocabilidad ya que las transacciones que estaban postergando la finalizaci´on finalizan inmediatamente al recibir el mensaje de fin de irrevocabilidad. El efecto de contenci´on es m´as probable a medida que se incrementa el n´umero de hilos y en consecuencia la contenci´on transaccional. VIII. Conclusiones Recientemente podemos encontrar en el mercado multiprocesadores con extensiones transaccionales best-effort que necesitan de un fallback software para garantizar el progreso de las aplicaciones y superar las limitaciones hardware. En este art´ıculo proponemos un nuevo tipo de irrevocabilidad que garantiza el progreso de las aplicaciones transaccionales y esconde las limitaciones del hardware al usuario a la vez que maximiza el paralelismo. Se propone la irrevocabilidad relajada basada en el concepto de suscripci´on relajada de cerrojos en fall- backs software. El mecanismo favorece la concurrencia postergando la finalizaci´on de las transacciones hasta la finalizaci´on de la transacci´on irrevocable y no necesita modificar el protocolo de coherencia. Proponemos un fallback hom´ologo basado en cerrojo con espera escapada que obtiene un rendimiento peor en algunos casos debido al efecto de la contenci´on de cerrojos. Nuestro mecanismo de irrevocabilidad evita ese efecto con un protocolo de comunicaci´on de irrevocabilidad basado en token. Tambi´en se propone un mecanismo de irrevocabilidad con anticipaci´on de reemplazo que requiere ligeras modificaciones al protocolo de coherencia y que no puede ser implementado en software. Esta soluci´on mejora el rendimiento de aquellas aplicaciones cuyas transacciones irrevocables sean causadas principalmente por reemplazos de cach´e. La evaluaci´on de las propuestas se lleva a cabo con el sistema simulado Simics/GEMS y con la suite de benchmarks STAMP, y obtenemos mejoras de rendimiento de hasta el 28% sobre las soluciones basadas en fallback. Agradecimientos Este trabajo ha sido realizado gracias a los proyectos TIN2013-42253-P, del Ministerio de Econom´ıa y Competitividad del gobierno de Espa˜na, y P12-TIC1470, de la Junta de Andaluc´ıa. Referencias [1] M. Herlihy and J.E.B. Moss, “Transactional memory: Architectural support for lock-free data structures,” in 20th Ann. Int’l. Symp. on Computer Architecture (ISCA’93), 1993, pp. 289–300. [2] Richard M Yoo, Christopher J Hughes, Konrad Lai, and Ravi Rajwar, “Performance Evaluation of Intel Transactional Synchronization Extensions for High-performance Computing,” in Int’l Conf. on High Performance Computing, Networking, Storage and Analysis (SC’13), 2013, pp. 19:1–19:11. [3] Amy Wang, Matthew Gaudet, Peng Wu, Jos´e Nelson Amaral, Martin Ohmacht, Christopher Barton, Raul Silvera, and Maged Michael, “Evaluation of Blue Gene/Q hardware support for transactional memories,” in 21st Int’l Conf. on Parallel Architectures and Compilation Techniques (PACT’12), 2012, pp. 127–136. [4] Christian Jacobi, Timothy Slegel, and Dan Greiner, “Transactional Memory Architecture and Implementation for IBM System z,” in 45th Ann. Int’l. Symp. on Microarchitecture (MICRO’12), Dec. 2012, pp. 25–36. [5] Allon Adir, Charles Meissner, Amir Nahir, Randall R. Pratt, Mike Schiffli, Brett St. Onge, Brian Thompto, Elena Tsanko, Avi Ziv, Dave Goodman, Daniel Hershcovich, Oz Hershkovitz, Bryan Hickerson, Karen Holtz, Wisam Kadry, Anatoly Koyfman, John Ludden, and Brett St Onge, “Verification of Transactional Memory in POWER8,” in 51st Ann. Design Automation Conf. (DAC’14), 2014, pp. 1–6. [6] Adam Welc, Saha Bratin, and Ali-Reza Adl-Tabatabai, “Irrevocable transactions and their applications,” in 20th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA’08), june 2008, pp. 285–296. [7] Luke Dalessandro, Fran¸cois Carouge, Sean White, Yossi Lev, Mark Moir, Michael L. Scott, and Michael F. Spear, “Hybrid NOrec: A Case Study in the Effectiveness of Best Effort Hardware Transactional Memory,” ACM SIGPLAN Notices, vol. 47, no. 4, pp. 39, jun 2012. [8] Irina Calciu, Tatiana Shpeisman, Gilles Pokam, and Maurice Herlihy, “Improved Single Global Lock Fallback for Best-effort Hardware Transactional Memory,” in 9th Workshop on Transactional Computing (TRANSACT’14), 2014. [9] Milo M K Martin, Colin Blundell, and E Lewis, “Subtleties of Transactional Memory Atomicity Semantics,” IEEE Computer Architecture Letters, vol. 5, no. 2, pp. 17, 2006. [10] Michelle J Moravan, Jayaram Bobba, Kevin E Moore, Luke Yen, Mark D Hill, Ben Liblit, Michael M Swift, and David A Wood, “Supporting Nested Transactional Memory in logTM,” in 12th Int’l. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS’06), 2006, pp. 359–370. [11] P.S. Magnusson, M. Christensson, J. Eskilson, D. Forsgren, G. Hallberg, J. Hogberg, F. Larsson, A. Moestedt, B. Werner, and B. Werner, “Simics: A full system simulation platform,” IEEE Computer, vol. 35, no. 2, pp. 50–58, 2002. [12] M.M.K. Martin, D.J. Sorin, B.M. Beckmann, M.R. Marty, M. Xu, A.R. Alameldeen, K.E. Moore, M.D. Hill, and D.A. Wood, “Multifacet’s general executiondriven multiprocessor simulator GEMS toolset,” ACM SIGARCH Computer Architecture News, vol. 33, no. 4, pp. 92–99, 2005. [13] C.C. Minh, J. Chung, C. Kozyrakis, and K. Olukotun, “STAMP: Stanford Transactional Applications for MultiProcessing,” in IEEE Int’l Symp. on Workload Characterization (IISWC’08), 2008, pp. 35–46. [14] Harold W Cain, Maged M Michael, Brad Frey, Cathy May, Derek Williams, and Hung Le, “Robust Architectural Support for Transactional Memory in the Power Architecture,” in 40th Ann. Int’l. Symp. on Computer Architecture (ISCA’13), 2013, pp. 225–236. [15] L. Hammond, V. Wong, M. Chen, B.D. Carlstrom, J.D. Davis, B. Hertzberg, M.K. Prabhu, H. Wijaya, C. Kozyrakis, and K. Olukotun, “Transactional memory coherence and consistency,” in 31th Ann. Int’l. Symp. on Computer Architecture (ISCA’04), 2004, pp. 102–113. [16] Colin Blundell, Joe Devietti, E Christopher Lewis, and Milo M K Martin, “Making the Fast Case Common and the Uncommon Case Simple in Unbounded Transactional Memory,” in 34th Ann. Int’l. Symp. on Computer Architecture (ISCA’07), 2007, ISCA ’07, pp. 24–34. [17] Tim Harris, James Larus, and Ravi Rajwar, Transactional Memory, 2nd edition, Morgan & Claypool Publishers, 2010. [18] N. Agarwal, T. Krishna, Li-Shiuan Peh, and N.K. Jha, “GARNET: A detailed on-chip network model inside a full-system simulator,” in IEEE Int’l. Symp. on Performance Analysis of Systems and Software (ISPASS’09), April 2009, pp. 33–42.