Memoria Transaccional Hardware en Memoria Local de GPU

Memoria Transaccional Hardware en Memoria Local de GPU Alejandro Villegas, ´ Angeles Navarro, Rafael Asenjo, Oscar Plata1 Resumen— Los aceleradores gr´aficos (GPUs) se han convertido en procesadores de prop´osito general muy populares para el c´omputo de aplicaciones que presentan un gran paralelismo de datos. Su modelo de ejecuci´on SIMT (Single Instruction - Multiple Thread) y su jerarqu´ıa de memoria son piezas clave en la alta eficiencia de estas arquitecturas, que permiten el manejo de cientos o miles de hilos de ejecuci´on. La jerarqu´ıa de memoria est´a dividida en dos espacios direccionables: Una memoria local, peque˜na, r´apida y visible por un subconjunto de los hilos en ejecuci´on; y una memoria global, mayor, m´as lenta y visible por todos los hilos. Sin embargo, el modelo de programaci´on SIMT no es eficiente cuando hay que sincronizar este desbordante n´umero de hilos para garantizar exclusi´on m´utua en una secci´on cr´ıtica. Utilizar at´omicos para implementar cerrojos es problem´atico e ineficiente en este tipo de modelo de programaci´on. La memoria transaccional (TM) ha sido propuesta como una alternativa m´as fiable y eficiente que los cerrojos para esta sincronizaci´on. Con TM, se permite el acceso especulativo a la secci´on cr´ıtica, registrando los accesos a memoria, deshaciendo los cambios de aquellos hilos que han tenido un conflicto y reiniciando su ejecuci´on. En este trabajo presentamos una soluci´on TM hardware que sincroniza aquellos hilos de ejecuci´on que comparten la memoria local. En las pruebas realizadas, el uso de TM permite conseguir aceleraciones superiores a las soluciones basadas en cerrojos de grano grueso, as ˜ A como igualar a aquellas basadas en cerrojos de grano fino, pero con un menor esfuerzo de programaci´on. Palabras clave— Arquitecturas GPU, Memoria Transaccional Hardware I. Introducci´ on Los procesadores gr´aficos (GPUs) han sido adoptados como aceleradores muy populares en aplicaciones que presentan un gran paralelismo de datos gracias a su modelo de ejecuci´on Single Instruction - Multiple Thread (SIMT), su jerarqu´ıa de memoria y la disponibilidad de cientos o miles de n´ucleos de ejecuci´on. Tecnolog´ıas como CUDA [1] y OpenCL [2] permiten el acceso a este hardware para el c´omputo de prop´osito general. En este paper utilizamos la nomenclatura de OpenCL. Una GPU est´a compuesta de varios n´ucleos SIMT llamados compute units (CU). Los hilos de ejecuci´on se denominan work-items y se agrupan en work-groups. Un programa a ejecutar se denomina kernel, y est´a compuesto por varios workgroups. En n´umero de work-groups y work-items es definido por el programador. Un work-group es siempre planificado a una misma CU, y una CU puede ejecutar varios work-groups. Los recursos hardware de la CU son repartidos est´aticamente entre todos los work-groups, propiciando cambios de contexto muy ligeros. Dentro de la CU, los work-items de un mis1Universidad de M´alaga, Andaluc´ıa Tech, Dept. of Computer Architecture, Spain. e-mail:{avillegas, angeles, asenjo, oscar}@ac.uma.es mo work-group son agrupados en wavefronts de tama˜no fijo. Dentro de la CU, el wavefront es la unidad planificable. Una CU posee dos espacios de memoria direccionables por los work-items: memoria global y memoria local. La memoria global es accedida por todos los work-items que se encuentran en ejecuci´on. Esta memoria, de gran tama˜no, tiene una gran latencia (en parte aliviada por una jerarqu´ıa de caches no coherentes) y se puede utilizar para comunicar workitems de work-groups planificados en distintas CUs, adem´as de ser la que comunica la GPU con la CPU anfitri´on. La memoria local tiene una latencia y tama˜no menores. Existe un espacio de memoria local en cada una de las CU. Los work-items de un workgroup planificado en una CU tienen acceso a esta memoria de forma compartida. Debido a su baja latencia, la memoria local es utilizada como scratchpad por los work-items de un mismo work-group. Workitems pertenecientes a diferentes work-groups planificados sobre la misma CU no comparten la memoria local de forma l´ogica (esto es, no pueden utilizarla para comunicarse entre ellos), pero s´ı de forma f´ısica. Adem´as de estos dos espacios direccionables, cada work-item posee su propio espacio de memoria privado, t´ıpicamente mapeado en registros. En general, las aplicaciones paralelas con m´ultiples hilos de ejecuci´on deben utilizar mecanismo expl´ıcitos para la sincronizaci´on. Esta sincronizaci´on puede deberse a la necesidad de establecer secciones cr´ıticas en las que la exclusi´on m´utua est´e garantizada. Sin embargo, en el modelo de ejecuci´on SIMT esto supone un reto mayor que en otras arquitecturas. Una soluci´on t´ıpica es serializar la ejecuci´on. En este caso, s´olo un hilo ejecuta la secci´on cr´ıtica de forma secuencial, limitando el paralelismo de la aplicaci´on. Otra soluci´on consiste en delegar la ejecuci´on de la secci´on cr´ıtica a la CPU anfitri´on. Sin embargo, si los datos protegidos por la secci´on cr´ıtica se encuentran en memoria local, habr´ıa que copiarlos a memoria global, y luego al espacio direccionable por la CPU, lo que requiere una gran cantidad de ciclos de reloj. Otra posible soluci´on consiste en implementar un mecanismo de sincronizaci´on basado en cerrojos utilizando operaciones at´omicas. Implementar cerrojos de grano grueso es una soluci´on f´acilmente adoptable por los programadores. Sin embargo, el acceso a la secci´on cr´ıtica se hace en serie, perjudicando el rendimiento. Los cerrojos de grano fino, a priori, pueden ser una soluci´on m´as eficiente. Sin embargo, es m´as dif´ıcil de implementar y propenso a deadlocks ylivelocks. La memoria transaccional (TM) [3], [4] se ha propuesto como una alternativa prometedora al uso de cerrojos. El concepto de transacci´on se propone como complemento a la secci´on cr´ıtica. Al igual que una secci´on cr´ıtica, una transacci´on ejecutada por un hilo de ejecuci´on debe garantizar exclusi´on m´utua. Sin embargo, se permite el acceso concurrente a la transacci´on de forma especulativa por parte de todos los hilos de ejecuci´on. Para garantizar exclusi´on m´utua, todos los accesos a memoria deben ser monitorizados en busca de conflictos con otros hilos de ejecuci´on. Las transacciones que encuentran un conflicto deben deshacer los posibles cambios especulativos en memoria y reiniciar su ejecuci´on. Las que finalizan sin conflicto, pueden hacer definitivos sus cambios en memoria y continuar la ejecuci´on. Existen diversas soluciones TM en arquitecturas CPU [11]. En las arquitecturas GPU est´an empezando a aparecer los primeros trabajos de TM, tanto software [5], [6], [7] como hardware [8], [9]. Dado que las CPUs actuales comienzan a tener soporte TM por hardware, extender este soporte a GPUs es un campo de trabajo importante y con gran impacto. Los actuales trabajos de investigacion en TM por hardware para arquitecturas GPU [8], [9] ´unicamente consideran el espacio de memoria global. Adem´as, estas propuestas requieren cambios significativos en el hardware y organizaci´on de la GPU, motivos por los que los fabricantes pueden estar menos motivados para su implantaci´on. Adem´as, el espacio de memoria local no ha sido tenido en consideraci´on. Este espacio de memoria es importante para los programadores, puesto que es utilizado para mejorar de forma significativa el rendimiento de sus aplicaciones. Por estos motivos, queremos dar un soporte TM hardware en GPU que sea ligero, eficiente, y que cubra todos los espacios de memoria direccionables. As´ımismo, nuestra propuesta es implementada de forma incremental: en una primera etapa damos soporte TM hardware a los work-items de un mismo work-group que comparten la memoria local, mientras que en una segunda etapa extendemos esta implementaci´on para dar soporte a todos los work-items de la GPU que se comunican mediante la memoria global. Este art´ıculo presenta una propuesta de TM hardware ligero y efectivo que permite definir transacciones que operan sobre la memoria local compartida por los work-items de un mismo work-group en una arquitectura GPU. II. Antecedentes Una GPU puede ser vista como un conjunto de compute units (CU) que comparten un espacio de memoria global. Estas CUs son unidades de c´omputo muy vectorizadas en las que el flujo de control se realiza mediante t´ecnicas de predicaci´on [13]. Cada CU contiene diversas unidades funcionales: unidades vectoriales, escalares, de salto, una interfaz a memoria global y una local data share (LDS) que provee de memoria local a los work-groups planificados en dicha CU. Los registros dentro de esta CU se encuentran alojados en las unidades vectoriales y escalares. Los registros vectoriales son utilizados, normalmente, para el c´omputo de prop´osito general y son privados a cada work-item. Los registros escalares son compartidos por todos los work-items de un mismo wavefront y almacenan informaci´on com´un para ellos: ´ındices de bucles, identificadores de work-group, m´ascaras de ejecuci´on para la predicaci´on, etc´etera. Normalmente es el compilador el que decide utilizar estos registros escalares en lugar de los vectoriales como una optimizaci´on en el uso de recursos. Tanto los registros, como los recursos en la LDS y las unidades vectoriales, son divididos est´aticamente al principio del c´omputo. De esta forma se minimiza el coste de un cambio de contexto. La unidad LDS, encargada de manejar el acceso a memoria local, est´a compuesta por multiples bancos de memoria que proporcionan un gran ancho de banda. Cuando los work-items de un wavefront son planificados para acceder a la LDS, se detectan conflictos de banco y, en caso de existirlos, se serializa el acceso. De esta forma, en un instante dado, un banco de memoria local s´olo da servicio a un work-item en concreto. En este art´ıculo realizamos una propuesta de TM hardware, por lo que se ha utilizado un simulador para implementar y evaluar los cambios necesarios en el hardware de las GPU existentes. En este caso, hemos escogido Multi2sim 4.2 [12]. Multi2sim es un simulador de CPU y GPU que incluye modelos de procesadores superescalares, multi-n´ucleo, y diversas arquitecturas GPU. Proporciona un simulador funcional, que ejecuta las instrucciones codificadas en un binario de una arquitectura concreta, y un simulador detallado, que proporciona la simulaci´on de un pipeline completo dando como resultado una simulaci´on a nivel de ciclo. De entre las familias de GPU proporcionadas por el entorno de simulaci´on se ha escogido la Southern Islands de AMD. Esta GPU proporciona una LDS de 64kb dividido en 32 bancos, de los cuales un workgroup solamente puede direccionar 32kb. Cada workgroup se divide en wavefronts de 64 work-items. Cada wavefront es planificado a una de las 4 unidades vectoriales disponibles, lo que proporciona soporte para un total de 4 wavefronts de 64 work-items cada uno (esto es, 256 work-items por work-group). Los wavefronts son las unidades planificadas dentro de la CU, y su planificaci´on se hace de forma rotativa siguiendo una estrategia round-robin. Dentro de un wavefront, el control de flujo se realiza mediante predicaci´on utilizando 2 m´ascaras de bits, ambas de 64 bit: EXEC y VCC. EXEC indica qu´e work-item est´a activo (bit a 1) o inactivo (bit a 0) dentro de un wavefront. VCC se actualiza en las operaciones aritm´eticas y de comparaci´on e indica si el resultado ha sido 0. Su funcionamiento es el de un flag Z vectorizado. Los compiladores utilizan estas dos m´ascaras para implementar condicionales, saltos y bucles. Estas m´ascaras, comunes para todo un wavefront, se mapean en registros escalares. III. TM hardware en Memoria Local En esta secci´on presentamos un TM hardware que proporciona soporte para transacciones que sincronizan work-items de un mismo work-group utilizando para ello la memoria local. Habitualmente, el soporte TM en hardware requiere cambios significativos al hardware (introducir nuevas unidades funcionales), gran cantidad recursos de memoria para almacenar valores especulativos y la implementaci´on de una alternativa software que garantice el progreso. Esta propuesta trata de minimizar los recursos hardware y de memoria necesarios, de forma que sea una soluci´on f´acilmente adoptable por los fabricantes. Adem´as, proponemos un mecanismo de serializaci´on por hardware que evite que los programadores tengan que escribir una alternativa software a la soluci´on TM hardware para garantizar el progreso. Nuestra propuesta extiende el ISA de la arquitectura con 2 nuevas instrucciones para marcar el comienzo y final de la transacci´on: TX Begin y TX Commit. Estas instrucciones pueden ser utilizadas por los compiladores para proporcionar sentencias de m´as alto nivel en lenguajes como OpenCL. El caso de transacciones anidadas se ha dejado como trabajo futuro y a ser resuelto por el hardware y el compilador. Dentro de una transacci´on, todas las operaciones sobre memoria local gestionadas por la LDS son consideradas transaccionales (esto es, no existen unas instrucciones de lectura y escritura expl´ıcitas TX Read yTX Write). Cuando un wavefront ejecuta la instrucci´on TX Begin, sus workitems activos (es decir, los que tienen su bit correspondiente en EXEC puesto a 1) comienzan la transacci´on. El TM hardware propuesto sigue un esquema eager, por lo que, en cada acceso a memoria, se ejecuta un algoritmo de detecci´on de conflictos y de gesti´on de versiones, y el modelo SIMT es informado de los posibles conflictos para prevenir que el work-item en conflicto contin´ue su ejecuci´on. La ejecuci´on de la instrucci´on TX Commit marca el final de la transacci´on para el wavefront. Si ning´un work-item de wavefront ha presentado conflictos, la transacci´on finaliza y la ejecuci´on contin´ua por la siguiente instrucci´on. En el caso de que alg´un workitem presente un conflicto, la transacci´on debe ser reiniciada para dichos work-items saltando de nuevo a la instrucci´on TX Begin. Aprovechamos el hecho de que, en un instante dado, cada banco de LDS es accedido ´unicamente por un work-item para implementar un mecanismo de detecci´on de conflictos y gesti´on de versiones por banco de memoria. La figura 1 muestra los cambios realizados en cada banco de memoria local de la LDS para implementar la funcionalidad propuesta. En los siguientes apartados se explicar´an los cambios al modelo de ejecuci´on SIMT necesarios para gestionar la transacci´on, as´ı como los mecanismos de detecci´on de conflictos y gesti´on de versiones. Bloom Evaluation 256 filters 8 Bytes Local Memory Bank (2 KBytes) 32 Local Memory Banks Version Management HW Space for other WGs 1 Word (4 Bytes) Vars. Backup Owner N Bloom Filters Shadow Area N/4 N Vector Register TCM TCM TCM TCM Scalar Reg. 1 Byte Fig. 1: Recursos hardware y de memoria propuestos para dar soporte TM hardware en los bancos de memoria local. A. Modificaciones al Modelo de Ejecuci´on SIMT El modelo de ejecuci´on SIMT se basa en la existencia de las m´ascaras EXEC y VCC. Cada wavefront mantiene una copia privada de estas m´ascaras, que tienen un bit por cada work-item en el wavefront. En el caso de la arquitectura estudiada, estas m´ascaras son de 64 bits y se alojan utilizando registros escalares. La m´ascara EXEC indica qu´e work-items dentro del wavefront est´an activos, mientras que VCC funciona como un flag Z, indicando el resultado de las instrucciones aritm´eticas y de comparaci´on. Con estas m´ascaras, los compiladores implementan bucles, condiciones y saltos utilizando un mecanismo de predicaci´on. Inicialmente, puede considerarse la reutilizaci´on de estas m´ascaras para implementar los mecanismos de control de flujo de una transacci´on como, por ejemplo, desactivar los work-items que han presentado un conflicto, o implementar los saltos correspondientes al reinicio de una transacci´on. Sin embargo, esto puede generar inconsistencias. Una instrucci´on condicional tipo if-then modifica la m´ascara EXEC para dejar activos ´unicamente los workitems que cumplen la condici´on, restaurando su valor tras la ejecuci´on del bloque condicional. Si la m´ascara EXEC fuese modificada para desactivar un workitem que presenta un conflicto dentro del bloque condicional, ´este seria re-activado (err´oneamente) tras la ejecuci´on de dicho bloque. Por este motivo, proponemos el uso de una nueva m´ascara Transaction Conflict Mask (TCM) por wavefront, mapeada en un registro escalar, que indique qu´e work-item ha presentado un conflicto en los accesos a memoria. La m´ascara TCM, de 64 bits, es inicializada a 0 por la instrucci´on TX Begin. En un acceso a memoria, si se detecta un conflicto, se pone a 1 el bit de TCM correspondiente al work-item que ha presentado el conflicto. Si, al ejecutar la instrucci´on TX Commit, TCM est´a a 0, significa que no ha habido ning´un conflicto y, por tanto, la transacci´on se da por correcta y finalizada. Un 1 en alguno de los bits indica un conflicto. En este caso, la instrucci´on TX Commit copia TCM en EXEC y provoca un salto a la instrucci´on TX Begin. De esta forma, se reinicia la transacci´on s´olo para aquellos work-items que presentaron conflictos. Sin embargo, esto requiere que EXEC sea salvaguardado antes de ejecutar TX Begin por primera vez, y restaurarlo tras salir de TX Commit sin ning´un conflicto. Para ello, hemos reservado por hardware un registro escalar, aunque tambi´en podr´ıa hacerse mediante software utilizando el compilador. Una importante ventaja de utilizar esta m´ascara TCM, completamente manipulada por hardware, es que los compiladores y el programador no necesitan hacer ning´un cambio en la forma de implementar condicionales y bucles. Los ´unicos cambios potencialmente necesarios es promover el uso de registros vectoriales, privados a los work-items, en lugar de los escalares, compartidos por los work-items de un mismo wavefront. El motivo es que, si indice de un bucle es mapeado en uno de estos registros escalares y algunos work-items del wavefront progresan mientras que otros presentan conflictos, el valor que debe tomar este registro compartido puede quedar inconsistente. Por ello, los compiladores deben omitir la optimizaci´on que promociona el uso de registros escalares en lugar de vectoriales para bloques de c´odigo que se vayan a ejecutar dentro de una transacci´on. La utilizaci´on de TCM no garantiza progreso: es posible que la instrucci´on TX Commit deba reiniciar la transacci´on varias veces y se encuentre ante un bucle de reintentos infinitos debido a un conflicto en los accesos por parte de 2 o m´as work-items. Esto se detecta al comprobar que dos veces consecutivas se ha reiniciado la transacci´on sin ning´un cambio en TCM, indicando que no ha habido progreso desde el ´ultimo reintento. Estos conflictos pueden darse bien entre work-items del mismo wavefront, o bien entre work-items del mismo work-group, pero ubicados en diferentes wavefronts. Para garantizar el progreso, sin intervenci´on del programador ni del compilador, proponemos una serializaci´on de la ejecuci´on en 2 niveles. En primera instancia, y dado que los work-items de un wavefront se ejecutan en lockstep, suponemos que el conflicto se ha dado dentro del wavefront. En el caso de 2 reintentos con el mismo valor en TCM, serializamos la ejecuci´on de ese wavefront. En este caso, en lugar de reiniciar TCM a 0 en la instrucci´on TX Begin, se sustituye ´unicamente uno de sus bits a 1 por 0. Esto es equivalente a reiniciar la transacci´on con un solo work-item. Llamamos a este mecanismo wavefront serialization. Si, a´un as´ı, en el siguiente reintento no existe progreso, se debe al conflicto con alg´un work-item de otro wavefront. En este caso, se provoca que todos los dem´as wavefronts aborten la transacci´on, y vuelvan a la instrucci´on TX Begin, quedando detenidos en esta instrucci´on hasta que el wavefront actual ha alcanzado la instrucci´on TX Commit. El wavefront actual debe adoptar el mismo mecanismo que en el caso de wavefront serialization. Cuando este wavefront termina el reintento de transacci´on, se permite el progreso del resto de wavefronts. Este segundo mecanismo se denomina work-group serialization. Para el funcionamiento correcto de estos dos mecanismos se debe garantizar que un work-item que no presenta conflictos con ning´un otro es capaz de finalizar una transacci´on con ´exito. Esto ser´a garantizado por los mecanismos de gesti´on de versiones y detecci´on de conflictos. B. Gesti´on de Versiones La gesti´on de versiones es el mecanismo que maneja los valores especulativos y definitivos de los accesos a memoria de una transacci´on. En primer lugar, debemos gestionar los valores que se encuentran en los registros vectoriales privados a cada work-item. Para ello, proponemos el uso de otros registros. Al iniciar una transacci´on, todos los work-items activos dentro del wavefront realizan una copia de los valores de sus registros en registros auxiliares que llamaremos shadow registers. La detecci´on de un conflicto por parte de un work-item implica restaurar los valores de los shadow registers en los registros originales para reintentar la transacci´on con los valores adecuados. La parte m´as importante y novedosa de la gesti´on de versiones reside en la gesti´on de los valores especulativos en memoria local. La gesti´on de versiones se realiza de manera distribuida en cada uno de los bancos de memoria local (32 bancos en el caso de la arquitectura estudiada). La distribuci´on por bancos asegura que se pueda realizar una gesti´on de versiones en paralelo, puesto que los bancos son accedidos en paralelo por diferentes work-items. Adem´as, esta soluci´on es escalable y portable a otras arquitecturas con un n´umero de bancos diferente. Cuando el programador define variables en el espacio de memoria local, el compilador las agrupa y aloja en una secci´on contigua de la memoria ubicada en la LDS. Para implementar el TM se requiere que el compilador aloje otra zona de memoria contigua a las variables de usuario, que denominaremos shadow memory. Esta shadow memory, de forma l´ogica, contiene pares <owner, value>que indican, para cada palabra de memoria, el work-item que ha accedido a dicha posici´on y el valor a restaurar en caso de detecci´on de conflicto (esto es, se realiza una copia del valor antiguo al acceder a memoria, y se restaura dicha copia al detectar un conflicto, realiz´andose las escrituras a memoria de forma eager sobre la posici´on de memoria definitiva). F´ısicamente, y por eficiencia, los pares <owner, value>de la shadow memory se encuentra ubicados de forma diferente, como puede observarse en la figura 1. Suponiendo que las variables de usuario ocupan Npalabras de memoria de 4 bytes, la shadow memory precisa Npalabras del mismo tama˜no adicionales para gestionar los valores antiguos, y Nbytes adicionales para almacenar el identificador de work-item. Situando estos dos espacios de forma contigua a las variables de usuario de la forma indicada en la figura 1, podemos acceder a los valores antiguos y el identificador del work-item con el c´alculo de 2 offsets. La copia del valor antiguo de una variable en la posici´on Kse encuentra K+N palabras de memoria m´as adelante y el work-item que la ha accedido ha almacenado su identificador K bytes despu´es del ´area de resguardo. Esta forma de gestionar las versiones de las variables asegura que todas las variables pueden ser accedidas dentro de una transacci´on. Esto garantiza que un work-item sin conflictos podr´a progresar, puesto que podr´a hacer copias de todos los accesos especulativos que lleve a cabo. Adem´as el mecanismo basado en offsets es simple y requiere de pocas modificaciones en el hardware del banco de memoria en LDS. Como contrapartida, es un m´etodo que consume gran parte de los recursos de memoria, pudiendo afectar al tama˜no m´aximo de las variables alojadas en memoria local. C. Detecci´on de Conflictos El mecanismo de detecci´on de conflictos registra cada acceso a memoria, determinando si tiene un conflicto con un acceso anterior a la mismo posici´on por parte de otro work-item. Para ello, proponemos un procedimiento de detecci´on de conflicto distribuido, que opera en paralelo en cada uno de los bancos de memoria y que se desarrolla en 3 etapas: 1. Detecci´on de conflictos r´apida: Basada en filtros de Bloom [14]. Cada work-item mantiene, por cada banco de memoria, un filtro de Bloom para registrar sus accesos. Por simplicidad, en la detecci´on de conflictos no se distinguen lecturas y escrituras. Inicialmente consideramos filtros de Bloom de 8 bits por cada work-item. Estos filtros pueden ser almacenados en registros vectoriales como se indica en la figura 1. Aprovechando la localidad espacial que poseen la mayor´ıa de las aplicaciones que explotan paralelismo de datos en la GPU, hemos determinado el uso de una operaci´on m´odulo para registrar los accesos. Cuando a un banco se le solicita la palabra de memoria K, se eva´uan los filtros de Bloom de todos los work-items asignados a dicho banco. La evaluaci´on consiste en comprobar el bit K%8, operaci´on que es simple y para la que proponemos un hardware que pueda hacerlo en paralelo con los 256 filtros de Bloom necesarios. Esta evaluaci´on puede dar 3 resultados: 1) ning´un positivo, 2) positivo ´unicamente en el filtro correspondiente al work-item actual o 3) positivo en un filtro diferente al work-item actual. El caso 1) significa que es un nuevo acceso. Se debe marcar el bit correspondiente en el filtro de Bloom del work-item actual. En el caso 2) no podemos determinar si es un acceso repetido a dicha posici´on de memoria o un nuevo acceso, puesto que no sabemos si el filtro ha devuelto un falso positivo. Este caso debe refinarse en la siguiente etapa. El caso 3) indica el posible acceso de otro work-item a dicha posici´on de memoria, lo que es considerado como un conflicto. En este ´ultimo caso, la m´ascara TCM es actualizada colocando a 1 el bit correspondiente. 2. Modificaci´on de shadow memory: Una vez conocido el resultado de la detecci´on de conflicto, se a˜nade un hardware para gestionar la shadow memory. Si la etapa anterior result´o en el caso 1) (nuevo acceso), se debe hacer una copia del valor en memoria y establecer la ID del work-item actual como due˜no de dicha posici´on en la entrada correspondiente de la shadow memory. En el caso 2) se debe determinar si es un nuevo acceso, o si es un segundo acceso a la misma posici´on. Para ello, se examina la entrada correspondiente en la shadow memory. Si la entrada no est´a asociada al work-item actual, es un nuevo acceso y se procede como en el caso anterior. En otro caso, es un acceso repetido a la misma posici´on y no se requiere ninguna acci´on. Por ´ultimo, el caso 3) indica un conflicto. En este caso, se deben restaurar las posiciones de memoria asociadas al work-item actual a sus valores originales, y se limpian sus filtros de Bloom. 3. Comunicaci´on del conflicto: La primera etapa, detecci´on de conflictos r´apida, actualiz´o la m´ascara TCM y la segunda etapa, en caso de conflicto, restaur´o los valores modificados por el work-item en el banco de memoria actual. Sin embargo, los dem´as bancos de memoria podr´ıan contener valores especulativos que no han sido restaurados. Debido a esto, esta ´ultima etapa lee la m´ascara TCM, que ha sido actualizada en paralelo por todos los bancos, y procede a restaurar los valores originales de las posiciones de memoria accedidas por work-items con conflicto y limpiar sus filtros de Bloom. Debido a que se han introducido un mecanismo que distingue falsos positivos en el filtro de Bloom del work-item que accede a memoria, el progreso est´a garantizado cuando se ejecuta un work-item por wavefront, lo cual asegura que los mecanismos de serializaci´on en wavefront y work-group funcionan adecuadamente. IV. Evaluaci´ on En este trabajo hemos presentado un TM hardware que permite definir transacciones sobre la memoria local compartida por los work-items pertenecientes a un mismo work-group. Normalmente, esta memoria es utilizada como scratchpad para almacenar estructuras de datos de forma temporal. Por ello, inicialmente hemos utilizado una tabla hash (HT) para evaluar nuestra propuesta, ya que es una estructura de datos conocida y utilizada por muchas aplicaciones. El trabajo futuro incluye la evaluaci´on de otras estructuras de datos y algoritmos. En HT, cada uno de los 256 work-items pertenecientes al work-group trata de introducir su ID en una tabla hash. La tabla hash tiene un n´umero fijo de entradas, pero cada entrada tiene capacidad suficiente para almacenar todos los posibles elementos. En la evaluaci´on, el n´umero de entradas se ha variado desde 2 (HT2), duplic´andose, hasta 256 (HT256). El escenario HT2 es el que presenta mayor n´unero de conflictos, ya que cada uno de los 256 work-items est´a tratando de insertar su ID teniendo ´unicamente 2 entradas disponibles para ello; mientras que el escenario HT256 no presenta ning´un conflicto y todos los work-items son capaces de insertar su ID inmediatamente. La en- trada se determina realizando la operaci´on ID %N, siendo Nel n´umero de entradas de la tabla. Una vez conocida su entrada, el work-item debe recorrer todos los elementos de la entrada asignada hasta encontrar un hueco disponible, e insertar en ´el su ID. Este proceso, en el que varios work-items potencialmente colisionan en la misma entrada, debe ser definido dentro de una transacci´on. La transacci´on comprende leer un elemento, comprobar si est´a vac´ıo y, en ese caso, insertar el ID. Se han implementado 3 versiones de este algoritmo: una versi´on utilizando TM por hardware, una versi´on en la que se ha serializado la execuci´on de la transacci´on (TX. Serialization), f´acilmente implementable pero menos eficiente, y, por ´ultimo, una versi´on utilizando cerrojos de grano fino (FGL) que es m´as eficiente pero conlleva un esfuerzo de programaci´on mayor. Dentro de una transacci´on, la latencia asignada a las operaciones de memoria local se ha medido en cada banco de memoria. Se ha estimado en 1 ciclo la evaluaci´on de filtros de Bloom, y tantas veces la latencia de acceso a un banco de memoria como entradas de la shadow memory haya que modificar. Como la memoria local est´a compuesta de 32 bancos, la latencia total ser´a igual a la del banco m´as lento. A las operaciones TX Begin y TX Commit se les ha asignado una latencia igual a las de una instrucci´on de tipo escalar. Las instrucciones escalares son aquellas que afectan a todo un wavefront, como puede ser una barrera o, en este caso, una transacci´on. La figura 2 muestra la evaluaci´on realizada utilizando HT. La figura 2.(a) muestra la aceleraci´on conseguida por el uso de TM y FGL, tomando como base la serializaci´on de la transacci´on. En ella se aprecia que, en casos favorables, nuestra soluci´on TM alcanza el rendimiento proporcionado por FGL. En todos los casos, nuestra propuesta supera a la serializaci´on de la transacci´on consiguiendo una aceleraci´on entre 20X y 70X con un esfuerzo de programaci´on similar. En figura 2.(b) muestra un breakdown de la ejecuci´on, en la que se ve que el coste en ciclos de utilizar una soluci´on TM de estas caracter´ısticas est´a en torno al 15 % del total de ciclos. Los escenarios con menor probabilidad de conflicto emplean un mayor porcentaje de ciclos liberando recursos de las transacciones terminadas, mientras que aquellos con mayor probabilidad de conflicto los emplean en la gesti´on de versiones durante los accesos a memoria. Por ´ultimo, la figura 2.(c) muestra el porcentaje de transacciones que deben ser serializadas de entre el total de transacciones. Debido a que no existe una sincronizaci´on fuerte entre los wavefronts de un mismo work-group, nunca se ha dado la serializaci´on de work-group. V. Trabajo Relacionado Existen otras propuestas recientes de TM sobre arquitecturas GPU. En la vertiente software, encontramos los trabajos de Cederman et al. [5], Xuet al. [6] y Holey et HT2 HT4 HT8 HT16 HT32 HT64 HT128 HT256 Workload 0 20 40 60 80 100 120 Speedup w.r.t. TX. Serialization TM Hardware FGL (a) HT2 HT4 HT8 HT16 HT32 HT64 HT128 HT256 Workload 0.0 0.2 0.4 0.6 0.8 1.0 Execution breakdown TXBegin TXCommit Mem. Overheads TX Code Non-TX Code (b) HT2 HT4 HT8 HT16 HT32 HT64 HT128 HT256 Workload 0.0 0.2 0.4 0.6 0.8 1.0 Type of transaction Wavefront Serialization Transactional Execution (c) Fig. 2: Evaluaci´on de la propuesta TM hardware utilizando HT. al. [7]. Cederman et al. [5] proponen 2 soluciones que consideran transacciones entre thread blocks (workgroups) y no entre work-items. La soluci´on de Xu et al. [6] proponen la primera soluci´on a nivel de workitem que se fundamenta en una detecci´on de conflictos en dos fases: una primera basada en timestamp (m´as r´apida) y una segunda basada en valor (m´as precisa). Holey et al. [7] han propuesto 3 soluciones software TM. La primera realiza una detecci´on de conflictos eager, basada en una estrategia de mantener un registro de los work-items que han leido cada variable y permitiendo un ´unico work-item escritor. La segunda estrategia simplifica la primera y no distingue entre lecturas y escrituras. Se˜nalar que, puesto que la segunda implementaci´on les ha proporcionado mejores resultados que la primera a pesar de no distinguir entre lecturas y escrituras, nos hemos decantado por adoptar la misma estategia para implementar una soluci´on simple y efectiva. La tercera estrategia se basa en anotar, con un timestamp, el instante de modificaci´on de cada variable; validando las lecturas al final de la transacci´on en lugar de en cada acceso. Ninguno de los 3 trabajos anteriores sobre TM software en GPU ha considerado el espacio de memoria local en su implementaci´on. Fung et al. [8], [9] han hecho la ´unica propuesta TM hardware en GPU hasta la fecha. Su propuesta se basa en la creaci´on de unas unidades especializadas para el commit de la transacci´on, que se hace de forma lazy al final (esto es, la detecci´on de conflictos se lleva a cabo una vez alcanzada la instrucci´on TX Commit, en lugar de en cada acceso de memoria). Para ello, cada work-item debe registrar sus accesos en unos buffers de escritura y lectura alojados en su memoria privada, pudiendo coexistir m´ultiples versiones privadas de la misma variable al mismo tiempo. Nuestra propuesta eager elimina la necesidad de almacenar estos buffers y de transmitirlos a las unidades de commit. Adem´as, su trabajo contempla ´unicamente el espacio de memoria global. Nuestra propuesta, que es la ´unica existente en considerar el espacio de memoria local, ser´a extendida a memoria global en un trabajo futuro. De esta forma, podr´a existir una comparaci´on cuantitativa (y no s´olo cualitativa) de ambas propuestas. VI. Conclusiones y Trabajo Futuro En este art´ıculo hemos presentado una soluci´on TM hardware para dar soporte a transacciones sobre la memoria local de arquitecturas GPU. Las principales car´acter´ısticas de esta soluci´on son una granularidad a nivel de work-item y la detecci´on de conflicto y gesti´on de versiones distribuidas en los bancos de memoria. La soluci´on propuesta es potencialmente capaz de igualar aquellas basadas en cerrojos de grano fino y supera a la serializaci´on en el acceso a las secciones cr´ıticas. Adem´as, se propone un mecanismo de serializaci´on que evita que los programadores deban implementar una alternativa software para garantizar el progreso de la transacci´on. El trabajo futuro evaluar´a de forma m´as exhaustiva la soluci´on propuesta, adem´as de incorporar optimizaciones en la gesti´on de memoria y planificaci´on de work-items. En una etapa posterior, se incorporar´a al esquema propuesto el espacio de memoria global disponible en las arquitecturas GPU. Agradecimientos Este trabajo es parte de una colaboraci´on entre el Departamento de Arquitectura de Computadores de la Universidad de M´alaga y el grupo NUCAR de la Northeastern University en Boston, MA, USA. Los autores agradecen al profesor David Kaeli y al investigador Rafael Ubal de dicha universidad su colaboraci´on. Referencias [1] NVIDIA, NVIDIA CUDA Programming Guide. [2] Khronos, The OpenCL Specification. Version 2.0. [3] Maurice Herlihy and J. Eliot 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. [4] Tim Harris, James Larus, and Ravi Rajwar, Transactional Memory, 2nd, Morgan & Claypool Publishers, USA, 2010. [5] Daniel Cederman, Philippas Tsigas, and Muhammad Tayyab Chaudhry, “Towards a software transactional memory for graphics processors,” in 10th Eurographics Conf. on Parallel Graphics and Visualization (EG PGV’10), 2010, pp. 121–129. [6] Yunlong Xu, Rui Wang, Nilanjan Goswami, Tao Li, Lan Gao, and Depei Qian, “Software transactional memory for GPU architectures,” in Ann. IEEE/ACM Int’l. Symp. on Code Generation and Optimization (CGO’14), 2014, pp. 1:1–1:10. [7] A. Holey and A. Zhai, “Lightweight software transactions on GPUs,” in 43rd Int’l Conf. on Parallel Processing (ICPP’14), 2014, pp. 461–470. [8] Wilson W. L. Fung, Inderpreet Singh, Andrew Brownsword, and Tor M. Aamodt, “Hardware transactional memory for GPU architectures,” in 44th Ann. IEEE/ACM Int’l. Symp. on Microarchitecture (MICRO’11), 2011, pp. 296–307. [9] Wilson W. L. Fung and Tor M. Aamodt, “Energy efficient GPU transactional memory via space-time optimizations,” in 46th Ann. IEEE/ACM Int’l. Symp. on Microarchitecture (MICRO’13), 2013, pp. 408–420. [10] David A. Wood Daniel J. Sorin, Mark D. Hill, A Primer on Memory Consistency and Cache Coherence, Morgan & Claypool Publishers, 2011. [11] Nuno Diegues, Paolo Romano, and Lu´ıs Rodrigues, “Virtues and limitations of commodity hardware transactional memory,” in 23rd Int’l. Conf. on Parallel Architectures and Compilation Techniques (PACT’14), 2014, pp. 3–14. [12] Rafael Ubal, Byunghyun Jang, Perhaad Mistry, Dana Schaa, and David Kaeli, “Multi2Sim: A Simulation Framework for CPU-GPU Computing,” in 21st Int’l. Conf. on Parallel Architectures and Compilation Techniques (PACT’12), 2012. [13] Carole Dulong, “The ia-64 architecture at work,” Computer, vol. 31, no. 7, pp. 24–32, 1998. [14] Burton H. Bloom, “Space/time trade-offs in hash coding with allowable errors,” Commun. ACM, vol. 13, no. 7, pp. 422–426, July 1970.