Análisis comparativo del uso de STMs en a códigos de reducción irregulares

An´alisis comparativo del uso de STMs en c´odigos de reducci´on irregulares Manuel Pedrero, Eladio Guti´errez, Sergio Romero y ´ Oscar Plata1 Resumen— La memoria transaccional (TM) constituye un paradigma de concurrencia optimista en arquitecturas multin´ucleo que puede ser de utilidad en la explotaci´on de paralelismo en aplicaciones irregulares, en las que la informaci´on sobre las dependencias de datos no est´a disponible hasta la ejecuci´on. Este trabajo presenta y discute c´omo aprovechar las caracter´ısticas de un sistema STM (software transactional memory) en patrones de computaci´on que involucren operaciones de reducci´on, ligadas frecuentemente a aplicaciones irregulares. Con el fin de comparar el uso de enfoques STM en esta clase de patrones con otras soluciones m´as cl´asicas, se ha implementado como prueba de concepto un sistema STM, que denominaremos ReduxSTM, que combina dos ideas: una consolidaci´on (commit) ordenada de las transacciones, que asegura una equivalencia con la ejecuci´on secuencial del c´odigo; y una extensi´on del mecanismo de privatizaci´on subyacente al sistema STM que contempla las operaciones de reducci´on. Palabras clave— Software Transactional Memory (STM), operaciones de reducci´on, aplicaciones irregulares. I. Introducci´ on La disponibilidad de m´ultiples n´ucleos compartiendo una memoria global en los computadores actuales est´a teniendo una gran influencia en c´omo se dise˜nan las aplicaciones. Al descomponer un problema en tareas concurrentes, el rendimiento final est´a determinado en buena parte por c´omo se gestionan las posibles dependencias de datos y de control. En general las dependencias se gestionan de una manera conservadora, especialmente cuando se resuelven en tiempo de compilaci´on. En el caso de aplicaciones que presentan un patr´on irregular de referencias de memoria ´esta gesti´on puede resultar muy limitada, ya que muchas dependencias no se conocen completamente hasta que la aplicaci´on no se ejecuta. En este contexto, la memoria transaccional (TM) [1] proporciona un modelo de concurrencia optimista en arquitecturas multin´ucleo, facilitando al programador la explotaci´on de paralelismo en c´odigos –como los de las aplicaciones irregulares– que no son f´acilmente analizables de forma est´atica. TM ha surgido como una alternativa que facilita la coordinaci´on de threads concurrentes. TM proporciona el concepto de transacci´on: una estructura de programaci´on que garantiza atomicidad, consistencia y aislamiento en bloque de las instrucciones que la componen. Las transacciones pueden ejecutarse concurrentemente, pero el sistema garantiza que los resultados de la ejecuci´on sean los mismos que en una ejecuci´on secuencial. 1Dpto. de Arquitectura de Computadores, Universidad de M´alaga, 29071 M´alaga, e-mail: [email protected], [email protected], [email protected], [email protected] En un sistema TM, las transacciones se ejecutan de manera especulativa, de forma que las modificaciones en las posiciones de memoria quedan registradas por un gestor de versiones. Si dos transacciones concurrentes entran en conflicto (escritura/escritura, lectura/escritura en la misma posici´on de memoria), una de ellas debe abortar. Tras restaurar su estado inicial (rollback), la transacci´on que aborta reintentar´a la ejecuci´on especulativa. Cuando una transacci´on termina su ejecuci´on libre de conflictos, consolida sus datos modificados (commit) haci´endolos visibles al resto del sistema. Se dice que la gesti´on de versiones en un sistema TM es eager si los cambios se trasladan a memoria inmediatamente, manteniendo un buffer con los valores antiguos (undo log) que se usar´a para restaurar el estado inicial en caso de aborto. Por el contrario, en una gesti´on de versiones lazy las modificaciones se mantienen en un buffer de escritura (redo log), consolid´andose al final de la transacci´on, durante la fase de commit. Con una terminolog´ıa similar, la detecci´on de conflictos se puede realizar inmediatamente (eager) o bien posponerse hasta el comienzo de la fase de commit (lazy). Encontramos en la literatura un buen n´umero de propuestas TM, implementadas bien en software (STM), en hardware (HTM) o con enfoques h´ıbridos (HyTM) [2]. Dadas las ventajas de TM, se han realizado esfuerzos encaminados a extraer paralelismo de aplicaciones secuenciales ya existentes mediante este paradigma. De hecho, muchas de las caracter´ısticas b´asicas de TM, como la detecci´on de conflictos, la privatizaci´on especulativa de posiciones de memoria y el aborto/reintento de la ejecuci´on se pueden encontrar en otras t´ecnicas como el multithreading especulativo (SpMT), o la especulaci´on a nivel de thread (threadlevel speculation ´o TLS) [3], las cuales se han probado eficaces en la paralelizaci´on de programas con threads. En general paralelizar un programa secuencial implica descomponer el programa en tareas y resolver correctamente las dependencias de datos entre las mismas. De este modo, la concurrencia optimista que ofrece TM puede ayudar en la paralelizaci´on de aplicaciones irregulares, donde un an´alisis est´atico no es suficiente para determinar la mayor parte de las dependencias. Las transacciones, definidas como secciones del programa secuencial, pueden ejecutarse concurrentemente, dejando a cargo del sistema TM la detecci´on y resoluci´on de los conflictos entre transacciones en tiempo de ejecuci´on. N´otese sin embargo que, adem´as de los conflictos de datos, podr´ıa requerirse una ordenaci´on de las transacciones para asegurar resultados correctos. Los sistemas TM convencionales no garantizan ning´un orden de commit entre las transacciones. En este trabajo se discute c´omo utilizar un sistema TM para explotar patrones de reducci´on (operaciones asociativas y conmutativas) con accesos de memoria irregulares (no conocidos en compilaci´on) y se compara esta alternativa con otras soluciones cl´asicas. Para ello se ha desarrollado ReduxSTM; un sistema STM que a˜nade caracter´ısticas espec´ıficas para este tipo de operaciones. ReduxSTM garantiza el commit de las transacciones en un orden equivalente al secuencial, y proporciona un tratamiento espec´ıfico de las reducciones aprovechando la privatizaci´on subyacente al sistema STM. Con ello se pretende reducir el n´umero de abortos derivados de las operaciones de reducci´on esperando trasladar este hecho a una mejora del rendimiento. II. Patrones de reducci´ on en aplicaciones irregulares Una sentencia de reducci´on es un patr´on de la forma O=O⊕ξ, donde ⊕es un operador asociativo y conmutativo aplicado a un objeto de memoria O (objeto o variable de reducci´on), y ξes una expresi´on computada con objetos privados que no dependen de O. Se dice que un bucle es completamente de reducci´on (o reducci´on de histograma) si contiene sentencias de reducci´on y las ´unicas dependencias entre iteraciones son causadas por el objeto de reducci´on. As´ı mismo, el objeto de reducci´on no debe ser accedido por ninguna otra sentencia que no sea de reducci´on [4]. Las operaciones de reducci´on son parte habitual del n´ucleo de muchas aplicaciones computacionales como el ´algebra de matrices dispersas, resolutores de ecuaciones diferenciales, etc. En estos casos el objeto de reducci´on (com´unmente un vector multidimensional) es accedido a trav´es de ´ındices indirectos, lo que confiere una naturaleza irregular a la aplicaci´on. Desde el punto de vista de las dependencias de datos, las sentencias de reducci´on causan dependencias entre iteraciones, ya que la variable de reducci´on es le´ıda y a su vez escrita. No obstante, en los bucles completamente de reducci´on, las iteraciones se pueden reordenar sin problemas siempre que todas las reducciones sobre el objeto de reducci´on tengan el mismo operador, al ser ´este conmutativo y asociativo. No obstante puede haber situaciones donde la condici´on de bucle de reducci´on no se verifique completamente. Por ejemplo si se accede al objeto de reducci´on fuera de las sentencias de reducci´on, si se combinan varios operadores diferentes (aunque sean de reducci´on), o si ocurren otras dependencias entre las iteraciones debidas a otras variables no reductivas [5], [6]. A pesar de ello, puede que la condici´on de reducci´on se siga verificando para un subconjunto de iteraciones. Es lo que se conoce como reducciones parciales. Un ejemplo de esto se muestra en la figura 3. A la hora de paralelizar bucles de reducci´on, podemos clasificar los m´etodos propuestos en la literatura en dos grandes grupos: (a) m´etodos que garantizan la exclusi´on mutua entre los accesos a los objetos de reducci´on [7], y (b) m´etodos que acumulan parcialmente el resultado en copias privadas de los objetos de reducci´on [8], [9], [10] y luego realizan una reducci´on global en el objeto de reducci´on original. A. Exclusi´on mutua Una forma obvia de resolver los conflictos causados por las sentencias de reducci´on es convertir el bucle secuencial completamente de reducci´on en un DOALL, encerrando las sentencias de reducci´on (o un grupo de ellas) en una secci´on cr´ıtica, de manera que s´olo un thread acceder´a a las variables de reducci´on a la vez. El principal inconveniente de este enfoque es el alto grado de serializaci´on, aunque puede mejorarse empleando locks de grado fino (finegrained locks). Si el objeto de reducci´on es un vector, asociar´ıamos un lock por cada elemento del mismo, de modo que dos threads puedan acceden a elementos diferentes en paralelo, y s´olo haya serializaci´on en caso de producirse un conflicto real. Un enfoque similar se puede conseguir con operaciones at´omicas, aunque su disponibilidad depende en gran medida de la arquitectura hardware. En este grupo de t´ecnicas podemos incluir modelos basados en tareas, como la cl´ausula omp task depend incluida recientemente en el est´andar OpenMP u otras soluciones similares como las de [11] y [12]. En estos casos las variables de reducci´on se marcar´ıan como una dependencia de entrada-salida de la tarea. La principal limitaci´on de estos enfoques en c´odigos irregulares es su capacidad para expresar dependencias complejas, como las indirecciones, y tambi´en para expresar las dependencias cuando ´estas se computan dentro de la tarea. B. Privatizaci´on Privatizar los objetos de reducci´on es una soluci´on bastante eficaz y extendida a la hora de paralelizar bucles de reducci´on. En este caso se distribuye el espacio de reducci´on entre los threads, cada uno de los cuales opera sobre copias privadas de las variables de reducci´on. Estas copias deben inicializarse al elemento neutro del operador. Tras finalizar su trabajo, las reducciones parciales realizadas en las copias privadas han de reducirse de forma segura sobre los objetos de reducci´on originales. Dos t´ecnicas representativas de este grupo son Replicated Buffer y Array Expansion, que se diferencian en c´omo resuelven los conflictos en la reducci´on final. El principal inconveniente de la privatizaci´on es su gasto de memoria extra, ya que multiplicamos el tama˜no de los objetos de reducci´on por el n´umero de threads. III. Enfoques TM en patrones de reducci´ on Al considerar la paralelizaci´on de un bucle de reducci´on completo, un enfoque directo mediante TM consiste en sustituir la secci´on cr´ıtica que abarca las Read subscript arrays: edge(1,*), edge(2,*) do itime=1,nTimes do i=1,nEdges n1 = edge(1,i) n2 = edge(2,i) Compute ζ1,ζ2,ζ3 vel(1,n1)=vel(1,n1)+ζ1 vel(2,n1)=vel(2,n1)+ζ2 vel(3,n1)=vel(3,n1)+ζ3 vel(1,n2)=vel(1,n2)-ζ1 vel(2,n2)=vel(2,n2)-ζ2 vel(3,n2)=vel(3,n2)-ζ3 enddo ..... enddo Compute subscript arrays: m(*), mbeg(*), mend(*) do irow=1, nRows do i=1,jdt+1 im =m(i) imb=mbeg(i) ime=mend(i) do is=imb,ime,2 Compute ζ1,ζ2... do ilev=1,2*jdlev f1(ilev,im)=f1(ilev,im)+ζ1 f2(ilev,im)=f2(ilev,im)+ζ2 ..... enddo enddo ..... enddo do ihop=1, nHops Update subscripts: B1(*),B2(*) do itime=1,nTimes do ih=1,nParticles i=B1(ih) j=B2(ih) Compute r(i,j),ζ(i,j), η(i,j), θ(i, j) if (r.lt. CutOff) then AX(i)=AX(i) + ζ AX(j)=AX(j) - ζ AY(i)=AY(i) + ζ AY(j)=AY(j) - ζ U = U + η P = P + θ endif enddo ..... enddo enddo (a) (b) (c) Fig. 1 Algunos c´ odigos con bucles de reducci´ on: (a) Unstructured, (b) transformada de Legendre y (c) din´ amica molecular 2D. for (i=0; i<NInd; i++){ Compute ξ1,ξ2 #pragma omp critical{ ... A[idx1[i]] ⊕=ξ1 A[idx2[i]] ⊕=ξ2 ... } } for (i=0; i<NInd; i++){ Compute ξ1,ξ2 BEGIN_XACT() ... TM_WRITE(A[idx1[i]]], TM_READ(A[idx1[i]] ⊕ξ1)) TM_WRITE(A[idx2[i]]], TM_READ(A[idx2[i]] ⊕ξ1)) ... END_XACT() } (a) (b) Fig. 2 Uso de transacciones (b) como reemplazo de una secci´ on cr´ ıtica (a). for (i=0; i<N; i++){ A[K[i]] = ...; ... = A[L[i]]; A[R[i]] = A[R[i]] ⊕ξ; } Fig. 3 Ejemplo de bucle con una zona de reducci´ on parcial. Los sub´ ındices, K, L and R, restringen el acceso a A tal como se muestra. Los accesos A[K[:]] and A[L[:]] no se solapan. sentencias de reducci´on por una transacci´on, tal como se muestra en la figura 2. Esta soluci´on es simple desde el punto de vista de la programabilidad, y los potenciales conflictos que surgen debido a las indirecciones son gestionados por el sistema TM. En caso de escenarios de baja contenci´on, el sistema TM podr´a mantener un buen nivel de paralelismo frente a la fuerte serializaci´on que se produce en el caso de emplear secciones cr´ıticas (mutex, spinlocks, atomics, etc). Si adem´as imponemos cierto orden en el TM de forma que los commits de las transacciones tengan lugar de forma equivalente al orden de la ejecuci´on secuencial, entonces podemos pensar en el sistema TM como una herramienta de apoyo a un enfoque TLS. Esto es especialmente interesante para aquellos casos en los que la paralelizaci´on de las reducciones no se puede abordar con soluciones cl´asicas porque las condiciones de bucle de reducci´on no se verifican completamente. Un ejemplo de esta situaci´on se muestra en la figura 3, donde hay conflictos potenciales entre accesos a un vector en una sentencia de reducci´on y accesos fuera de ella. Sin embargo puede existir un subconjunto de iteraciones que cumplan la condici´on de reducci´on si existen restricciones en los sub´ındices como las mostradas en la figura [5]. En la figura 4 podemos observar otro ejemplo donde existen lecturas y escrituras a trav´es de punteros que pueden ser alias de las variables de reducci´on. Este hecho impide saber en tiempo de compilaci´on si se trata de un bucle completamente de reducci´on y si, consecuentemente, las iteraciones pueden o no reordenarse con seguridad [6]. Estos patrones, a los que hemos denominado reducciones parciales, han sido tratados en la literatura por medio de enfoques especulativos, como se discute en la siguiente secci´on. IV. Trabajos relacionados La idea de resolver la paralelizaci´on de bucles de reducci´on especulativamente no es nueva. En [13] se propone el test LRPD que, tras una fase de inspecci´on, es capaz de seleccionar aquellas iteraciones que se pueden lanzar especulativamente en paralelo mediante una estructura DOALL. Esta idea ha sido reformulada recientemente con Privateer [4]. Otro enfoque especulativo reciente para bucles de reducci´on lo encontramos en [6], centrado en la detecci´on y ejecuci´on especulativa de variables de reducci´on parcial (PRV). En [14] y [15] se explora la posibilidad de utilizar un sistema TM en bucles de reducci´on, deshabilitando la detecci´on de conflictos y extendiendo el buffer de escritura para tal fin. Este enfoque requiere el conocimiento previo de que el bucle sea completamente de reducci´on y no es aplicable en el caso de reducciones parciales. Otras propuestas m´as for (termptr = ... ; termptr = termptr->nextterm) { ... for (netptr = ... ; netptr=netptr->nterm) { ... *costptr += ...; // Reduction sentence } ... rowsptr = tmp_rows[net] ; for (row = 0 ; rowsptr[row] == 0 ; row++ ){ ... } ... tmp_num_feeds[net] = f ; ... tmp_missing_rows[net] = -m ; ... delta_vert_cost += ( ... ); // Reduction sentence } Fig. 4 Esquema de un bucle de la funci´ on new dbox a() del c´ odigo 300.twolf (benchmark SPEC CPU2000). Los alias entre punteros hacen imposible saber si se trata de un bucle de reducci´ on aunque contiene sentencias de reducci´ on. generales basadas en TM y que son aplicables a reducciones irregulares las encontramos en [16], [17], [18]. IPOT [16] es capaz de lanzar bloques de instrucciones en paralelo contenidas en estructuras similares a transacciones ordenadas, y permite relajar las restricciones de consistencia para mejorar el rendimiento. ALTER [17] propone un esquema TLS al estilo transaccional en el que las variables pueden ser anotadas permiti´endoles un chequeo de consistencia m´as permisivo. Una de estas anotaciones est´a pensada precisamente para las variables de reducci´on. En [18] se propone una t´ecnica de paralelizaci´on autom´atica basada en transacciones hardware ordenadas. Por ´ultimo cabe destacar RMW (Read-ModifyWrite without aborts [19]), un enfoque STM reciente que proporciona soporte espec´ıfico para los patrones de lectura-modificaci´on-escritura de los cuales las reducciones son un caso particular. Este enfoque general est´a limitado, no obstante, por su limitada escalabilidad, no contempla transacciones ordenadas y est´a pensado fundamentalmente para variables escalares, excluyendo vectores y estructuras multidimensionales que aparecen con frecuencia en c´odigos con reducciones. V. ReduxSTM Adem´as de ser un sustituto directo de una secci´on cr´ıtica, las transacciones realizan una privatizaci´on selectiva de aquellas variables marcadas como transaccionales. La idea que se plantea es aplicar este mecanismo de privatizaci´on subyacente a las variables de reducci´on, permitiendo evitar aquellos abortos derivados de las sentencias de reducci´on siempre que sea posible. Las transacciones realizar´an reducciones parciales sobre su versi´on local de la variable, realiz´andose la reducci´on global en la variable compartida durante la fase de commit. La asociatividad y conmutatividad del operador garantiza que esto pueda hacerse de forma segura. De esta manera el programador s´olo tiene que marcar como transaccioTABLA I Diferentes t´ ecnicas de paralelizaci´ on de bucles completamente de reducci´ on. Requerimiento de memoria extra Paralelismo potencial Sobrecarga de sincronismo Reducci´on final Privatizaci´on muy alto muy alto muy bajo s´ı Secci´on cr´ıtica muy bajo muy bajo alto ninguno Lock de grano fino alto alto alto ninguno Ops. at´omicas ninguno muy alto alto ninguno TM (directo) bajo alto/medio bajo s´ı ReduxSTM bajo muy alto bajo s´ı nales las operaciones de reducci´on (sentencias) sin tener conocimiento de si se trata de un bucle completamente de reducci´on o de una reducci´on parcial. Aquellas sentencias de reducci´on que tengan conflictos con otros accesos a memoria (escritura o lectura) ser´an detectadas y corregidas por el STM de forma transparente al programador. Nuestra propuesta, ReduxSTM, soporta por tanto patrones potenciales de reducci´on, donde resulta complicado determinar est´aticamente si son reducciones parciales o totales. ReduxSTM ha sido planteado como una prueba de concepto para comprobar si un sistema TM se puede beneficiar de un tratamiento espec´ıfico de los patrones de reducci´on. ReduxSTM ha sido construido como una librer´ıa desde cero. Una comparativa de los diferentes enfoques discutidos se incluye en la tabla I. A. Caracter´ısticas Soporte de reducciones. Una de las caracter´ısticas clave de ReduxSTM es la capacidad de explotar la privatizaci´on selectiva asociada al sistema transaccional. Al explotar esta privatizaci´on impl´ıcita se consiguen eliminar abortos innecesarios, mejorando el grado de concurrencia. Con este prop´osito se introduce una nueva primitiva para las operaciones de reducci´on, que el programador podr´a usar junto con las ya existentes de lectura y escritura. Esta primitiva es tratada por los gestores de conflictos y de versiones como una tercera operaci´on b´asica: lectura (R), escritura (W) y reducci´on (Rdx). Su sem´antica es una lectura, seguida de una escritura en la misma posici´on de memoria tras haber realizado la operaci´on de reducci´on. La nueva primitiva Rdx(add, val, ⊕) es sem´anticamente equivalente a W(add, R(add)⊕val) pero permite una ejecuci´on m´as eficiente. Transacciones ordenadas. Una segunda caracter´ıstica importante de ReduxSTM es el mantenimiento de una restricci´on de orden entre los commits de las transacciones. De esta manera podemos garantizar que la ejecuci´on especulativa lleva al mismo resultado que la versi´on secuencial. Obs´ervese que, aunque los bucles completamente de reducci´on pueden ser reordenados sin problemas, esto no es as´ı en el caso de las reducciones parciales, donde las reducciones coexisten con lecturas y escrituras sobre las variables de reducci´on fuera de las sentencias de reducci´on. TABLA II Conflictos transaccionales potenciales. STM Est´andar ReduxSTM (Orden + Rdx.) R−W aborto no hay conflicto W−R aborto aborto W−W aborto no hay conflicto Rdx−R como R-W-R aborto R−Rdx como R-R-W no hay conflicto Rdx−W como R-W-W no hay conflicto W−Rdx como W-R-W no hay conflicto Rdx−Rdx como R-W-R-W no hay conflicto Esta restricci´on de orden en la fase de commit se convierte en el mecanismo b´asico de atomicidad de los commits, pero a su vez tiene un coste de rendimiento, ya que supone esperas no deseables en el turno de commit. No obstante, la oportunidad de mejora radica en el ahorro de abortos y rollbacks generados por las falsas dependencias asociadas a las reducciones [3], [15] como se muestra en la tabla II. La primera columna especifica dos operaciones realizadas por dos transacciones diferentes, donde la primera debe realizar la fase de commit antes de la segunda. Por ejemplo, R−W, estar´ıa asociado a una anti-dependencia. La segunda columna corresponde al comportamiento de un TM convencional y la tercera a nuestra propuesta. Gesti´on de versiones. Soportar reducciones (que pueden entrar en conflicto con lecturas y escrituras) junto con las transacciones ordenadas conlleva una gesti´on de versiones lazy, donde la consolidaci´on de las posiciones de memoria se realiza al finalizar la transacci´on en la fase de commit. Para ello se introducen dos buffers privados que almacenan informaci´on disjunta: el write buffer y el reduction buffer. El primero ya existe en los sistemas transaccionales convencionales y el segundo es espec´ıfico para las operaciones de reducci´on. Obs´ervese que es necesario un reduction buffer por cada operaci´on de reducci´on soportada (suma, producto, etc). Cada vez que se ejecuta una reducci´on transaccional sobre una posici´on de memoria, se busca dicha posici´on en el write buffer. Si dicha posici´on est´a ah´ı, se reduce el valor especificado en la reducci´on con el valor almacenado en el buffer y se mantiene en el write buffer ya que se viola la condici´on de reducci´on. En caso contrario, el valor de reducci´on se opera con el valor correspondiente del reduction buffer (o con el elemento neutro del operador si es la primera operaci´on sobre esta posici´on), actualizando dicha posici´on en el reduction buffer con el resultado de la operaci´on (reducci´on parcial). Si una posici´on almacenada en el reduction buffer es escrita con posterioridad en la misma transacci´on, debe ser eliminada de este buffer e insertada en el write buffer ya que deja de cumplirse en este momento la condici´on de reducci´on. Obs´ervese que una lectura de una posici´on que est´a marcada como reducci´on en una transacci´on implica combinar el valor de memoria con el acumulado parcialmente en el buffer de reducci´on. Detecci´on de conflictos. En ReduxSTM la validaci´on/invalidaci´on de las transacciones se realiza durante la fase de commit, por lo que la detecci´on de conflictos se considera lazy [20]. Gesti´on de commits. Puesto que s´olo una transacci´on puede estar en fase de commit para garantizar el orden, tal transacci´on es la responsable de comprobar y resolver posibles conflictos con otras transacciones activas. El orden de finalizaci´on garantiza la naturaleza at´omica de la fase de commit, y por tanto act´ua como el principal mecanismo de sincronizaci´on. La fase de commit est´a sujeta a las caracter´ısticas particulares de la estrategia de implementaci´on, tal como se discute en la secci´on V-B. Independientemente de la implementaci´on, la fase de commit de una transacci´on debe (1) Esperar su turno de commit; (2) Comprobar y resolver posibles conflictos con otras transacciones; y (3) Consolidar (actualizar) la memoria principal con los valores almacenados en los buffers de reducci´on y escritura (los valores de reducci´on necesitar´an ser acumulados seg´un su operador asociado). B. Implementaci´on Hemos seleccionado dos algoritmos STM bien conocidos, Commit Time Invalidation yTime-Based Validation, como base de nuestras implementaciones de ReduxSTM. La elecci´on de estos algoritmos radica en que son adecuados para implementar de forma efectiva las caracter´ısticas descritas anteriormente. Ambas implementaciones fueron codificadas desde cero. Commit Time Invalidation (CTI) En esta implementaci´on la transacci´on que realiza el commit marcar´a como invalidadas (a abortar) aquellas transacciones activas que tengan alg´un conflicto con ella [21]. Los conflictos de datos se detectan a partir de las direcciones de memoria. Al comenzar su fase de commit, y tras esperar su turno, cada transacci´on comprueba si es o no v´alida, abortando en caso negativo. Si es v´alida, consolida (commit) los datos transaccionales en la memoria, tras lo cual comprueba posibles conflictos con las transacciones en ejecuci´on, invalid´andolas si sus conjuntos de datos de lectura no son disjuntos con los conjuntos de escritura y reducci´on de la transacci´on en el commit (ver tabla II). Nuestra implementaci´on usa filtros de Bloom para representar cada uno de los conjuntos de datos (lectura, escritura y reducci´on). Time-based validation (TS) A diferencia de la estrategia anterior, ´esta emplea marcas de tiempo (timestamps) para registrar cu´ando tienen lugar las lecturas y actualizaciones [22]. Nuestra implementaci´on usa como reloj global de estas marcas el orden global de la ´ultima transacci´on finalizada. Cada transacci´on mantiene una tabla privada para las marcas de tiempo de sus lecturas. As´ı mismo se mantiene una tabla global de marcas de tiempo para las escrituras y reducciones consolidadas en memoria. En la fase de commit se comprueba si hay lecturas cuya marca de tiempo sea posterior a la de la escritura consolidada correspon- TABLA III C´ odigos testeados Fluidanimate Forma parte de la suite PARSEC [23]. Esta aplicaci´on simula fluidos usados en animaciones de tiempo real. Se comprobaron dos configuraciones: una de 100K part´ıculas durante 5 fotogramas y otra de 500K part´ıculas durante 500 fotogramas. MD2 Esta aplicaci´on [24] corresponde a una simulaci´on de din´amica molecular 2D en sistemas con un n´umero elevado de part´ıculas con interacciones de corto alcance. Para limitar la complejidad del problema las interacciones se acotan a part´ıculas cercanas mediante una lista de part´ıculas vecinas. Unstructured Este c´odigo [25] resuelve las ecuaciones de Euler en simulaciones f´ısicas. En cada paso de tiempo la aplicaci´on computa fuerzas y velocidades en los nodos de una malla. Legendre Corresponde al n´ucleo de la transformada de Legendre [26] usada en predicci´on meteorol´ogica. En cada paso de tiempo se invocan la transformada directa e inversa que llevan asociadas reducciones irregulares debido a los accesos a trav´es de indirecciones. 300.twolf Es un simulador de place and route incluido en el benchmark SPEC 2000 [27]. Contiene patrones de reducci´on interesantes en la rutina new dbox a() (dimbox.c), donde pueden aparecer conflictos potenciales entre variables de reducci´on y de no reducci´on debido a los alias entre punteros. diente, en cuyo caso la transacci´on debe abortar. Para reducir la memoria requerida por las marcas de tiempo, las tablas est´an limitadas en tama˜no y son accedidas por un hash de la direcci´on de memoria, lo que implica cierta probabilidad de falsos positivos. VI. Evaluaci´ on experimental En esta secci´on se eval´ua experimentalmente c´omo se comportan las t´ecnicas STM en c´odigos dominados por operaciones de reducci´on, en especial cuando se incluye soporte para reducciones. Los experimentos se realizaron en un servidor con 256 GB de RAM y 16 cores (32 threads) Intel Xeon E5-2698 a 2.3GHz, con sistema operativo Linux kernel 3.13 (64 bits). Los programas se compilaron con GNU GCC 4.8.2 con opci´on de optimizaci´on -O2. Como sistema STM de referencia a efectos de comparaci´on se ha empleado TinySTM (v.1.0.5) [22], un STM que puede considerarse representativo del estado del arte actual. Se emplearon tanto la versi´on base como la versi´on ordenada de TinySTM. En la evaluaci´on se han seleccionado varios c´odigos representativos que se describen brevemente en la tabla III. Fluidanimate, MD2, Unstructured y Legendre contienen bucles completamente de reducci´on. Por su parte, el c´odigo 300.twolf incluye patrones de reducci´on parcial. Las t´ecnicas de paralelizaci´on que se han comparado son las siguientes: - Locks de grano grueso (CG Locks), que se corresponde con el uso de locks para proteger secciones cr´ıticas; - Locks de grano fino (FG Locks), donde se usa un lock individual para proteger cada elemento del array de reducci´on compartido; -Privatizaci´on completa de los arrays de reducci´on, implementada como Array Expansion [9]; -TinySTM (configuraci´on por defecto) usado como referencia; -TinySTM-ordered, la versi´on de TinySTM con commits ordenados; -ReduxSTM en sus dos implementaciones: basada en marcas de tiempo (ReduxSTM-TS) y con invalidaci´on en fase de commit (ReduxSTM-CTI). En todos los sistemas STM la paralelizaci´on de los bucles de reducci´on se llev´o a cabo descomponiendo los bucles en bloques de iteraciones consecutivas (chunks) y ejecutando cada bloque dentro de una transacci´on. Obs´ervese que el n´umero de iteraciones en cada bloque determina el tama˜no de la transacci´on y es un par´ametro relevante, que debe ser elegido cuidadosamente: transacciones muy grandes reducen la carga extra introducida por la instrumentaci´on del sistema transaccional, pero implican mayores conjuntos de datos y por tanto mayor probabilidad de conflicto y de abortos. Las transacciones peque˜nas tienen menor probabilidad de conflicto, pero implican un mayor coste de instrumentaci´on debido al lanzamiento y cierre de las transacciones (por ejemplo de la inicializaci´on de las estructuras de datos). En la privatizaci´on y las t´ecnicas basadas en locks, los bucles se han particionado equitativamente entre los threads, sin agrupar las iteraciones en chunks. Recu´erdese que la privatizaci´on requiere una fase de inicializaci´on y otra de reducci´on final. Los locks se han implementado con spinlocks de POSIX. Adicionalmente, para los locks de grano fino, se ha optimizado el c´odigo mediante el uso de un mismo lock para aquellos bloques de sentencias de reducci´on cuyos accesos a los arrays de reducci´on est´an indexados por el mismo ´ındice. Esto reduce el n´umero de locks necesario y el n´umero de pares lock/unlock ejecutados, lo que se traduce en una menor sobrecarga. A. Comparaci´on de rendimiento A continuaci´on se ofrece una comparativa de las diferentes t´ecnicas en t´erminos de rendimiento. El speedup observado ha sido calculado con respecto a la versi´on secuencial no instrumentada de los c´odigos, usando el menor tiempo de ejecuci´on de entre al menos diez ejecuciones. En los experimentos, las variables independientes consideradas son el n´umero de threads y el tama˜no de las transacciones (iteraciones por bloque) en los sistemas STM. En este caso, los speedups mostrados corresponden al mejor chunk, esto es, al tama˜no de transacci´on que proporciona un speedup m´as alto. Las gr´aficas que muestran el speedup en funci´on del tama˜no de transacci´on muestran ejecuciones con 16 threads. La figura 5 muestra los resultados para Fluidanimate usando dos conjuntos de datos de 100K y 500K part´ıculas. Como se espera, los locks de grano grueso no aceleran en absoluto debido al uso de un s´olo lock global. Este m´etodo podr´ıa tener sentido en aplicaciones en las que el tiempo de ejecuci´on en secci´on Malla de 100 Knodos Malla de 500 Knodos 0 2 4 6 1 2 4 8 16 1 2 4 8 16 Threads Threads Speedup CG Locks FG Locks Privatization TinySTM TinySTM Ord. ReduxSTM TS ReduxSTM CTI Malla de 100 Knodos Malla de 500 Knodos 2 3 4 5 1 10 100 500 1000 1 10 100 500 1000 Tamaño de transacción Tamaño de transacción Speedup (16 threads) TinySTM TinySTM Ord. ReduxSTM TS ReduxSTM CTI Fig. 5 Fluidanimate: speedup para el mejor tama˜ no de transacci´ on en cada caso, e influencia del tama˜ no de transacci´ on para 16 threads. cr´ıtica fuera despreciable con respecto al resto, pero no es el caso en este problema. Los mejores resultados se obtienen con locks de grano fino o privatizaci´on, debido principalmente a la baja contenci´on del problema. Obs´ervese que, para la malla m´as grande, el rendimiento de la privatizaci´on deja de escalar para un n´umero de threads alto. Esto es consecuencia de las caracter´ısticas NUMA de la arquitectura y la gran cantidad de memoria extra que necesita este m´etodo. Por su parte, todos los sistemas STM presentan un comportamiento similar, debido a que la tasa de abortos se mantiene baja. Esta situaci´on no le da gran margen de ventaja a ReduxSTM. En este escenario los enfoques STM obtienen un speedup moderado sin grandes requerimientos de memoria. Con respecto la influencia del tama˜no de transacci´on, el comportamiento de los sistemas STM es muy dependiente de las caracter´ısticas de la entrada. De esta manera, para la malla m´as peque˜na la penalizaci´on de las transacciones grandes es m´as significativa que en el caso de la malla mayor, para la cual las transacciones m´as peque˜nas implican una alta penalizaci´on. MD2 incluye reducciones sobre variables escalares y sobre vectores (ver figura 1(c)). En este c´odigo se han probado dos estrategias, que se muestran en la figura 6. En la primera, todas las variables de reducci´on (escalares y vectoriales) han sido tratadas transaccionalmente. En la segunda, las variables escalares fueron privatizadas, de manera que el n´umero de sentencias de reducci´on sobre objetos compartidos se reduce de 6 a 4 por iteraci´on. Esta optimizaci´on es bastante com´un en este tipo de c´odigos [28], pero requiere un conocimiento mayor por parte del programador/compilador. Sin la privatizaci´on de escalares, la elevada contenci´on causada por los escalares hacen SIN privatización de escalares CON privatización de escalares 0 1 2 3 4 5 1 2 4 8 16 1 2 4 8 16 Threads Threads Speedup CG Locks FG Locks Privatization TinySTM TinySTM Ord. ReduxSTM TS ReduxSTM CTI SIN privatización de escalares CON privatización de escalares 0.0 0.5 1.0 1.5 2.0 1 10 100 500 1000 1 10 100 500 1000 Tamaño de transacción Tamaño de transacción Speedup (16 threads) TinySTM TinySTM Ord. ReduxSTM TS ReduxSTM CTI Fig. 6 MD2: speedup para el mejor tama˜ no de transacci´ on en cada caso, e influencia del tama˜ no de transacci´ on para 16 threads. 0 2 4 6 8 1 2 4 8 16 1 2 4 8 16 Threads Threads Speedup CG Locks FG Locks Privatization TinySTM TinySTM Ord. ReduxSTM TS ReduxSTM CTI Carga computacional base Con carga computacional EXTRA Carga computacional base Con carga computacional EXTRA 0 2 4 6 1 10 100 500 1000 1 10 100 500 1000 Tamaño de transacción Speedup (16 threads) TinySTM TinySTM Ord. ReduxSTM TS ReduxSTM CTI Tamaño de transacción Fig. 7 Unstructured: speedup para el mejor tama˜ no de transacci´ on en cada caso, e influencia del tama˜ no de transacci´ on para 16 threads. que TinySTM tenga una tasa de abortos muy alta, y por tanto un peor rendimiento. Como se observa, es precisamente en estos casos de alta contenci´on en las variables de reducci´on donde ReduxSTM obtiene una ventaja en el rendimiento. En cualquier caso, el peque˜no tama˜no de los arrays de reducci´on hacen que la privatizaci´on obtenga los mejores resultados, sobrepasando a los locks de grado fino. La figura 7 presenta los resultados de Unstructu- 0.00 0.25 0.50 0.75 1.00 1.25 1 2 4 8 16 Threads Speedup CG Locks FG Locks Privatization TinySTM TinySTM Ord ReduxSTM TS ReduxSTM CTI Fig. 8 Legendre: speedup (considerando una iteraci´ on por transacci´ on). red. En estos experimentos, el soporte para reducciones de ReduxSTM le permite tener ventaja con respecto a TinySTM. El rendimiento de TinySTM se degrada r´apidamente por los conflictos. Por contra, ReduxSTM se beneficia de su filtrado de conflictos para poder conseguir mejores resultados con transacciones m´as grandes. Como en los casos anteriores, los locks de grano fino y la privatizaci´on siguen teniendo los mejores speedups. No obstante tambi´en se ha testeado el c´odigo incorporando una carga computacional sint´etica adicional. En casos con mayor intensidad computacional, ReduxSTM es capaz de alcanzar el speedup de la privatizaci´on. La figura 8 recoge los resultados para Legendre. En este caso no se han analizado diferentes tama˜nos de transacci´on, dado que el bucle exterior paralelizado no contiene un n´umero elevado de iteraciones. En este c´odigo ninguna de las t´ecnicas consigue un buen rendimiento. La baja intensidad computacional del mismo (es un problema memory-bound) hace que cualquier instrumentaci´on adicional deteriore el rendimiento. La figura 9 muestra los resultados obtenidos con 300.twolf. Los resultados est´an referidos a la rutina new_dbox_a(). Esta funci´on presenta un patr´on de acceso a memoria con alta contenci´on, y la cantidad de paralelismo explotable est´a limitada por la baja intensidad computacional del c´odigo. S´olo se han considerado chunks de una y dos iteraciones por transacci´on, ya que transacciones mayores degradan el rendimiento. Es importante destacar que en este problema s´olo son aplicables los m´etodos que garantizan el orden de la ejecuci´on secuencial original, ya que las operaciones de reducci´on coexisten con otras operaciones de lectura y escritura potencialmente conflictivas. No obstante, aunque TinySTM no ordenado no cumple esta condici´on, se ha incluido a modo de referencia optimista. N´otese que ReduxSTM presenta un rendimiento significativamente mejor para todas las configuraciones. Cabe mencionar que, a pesar de que es dif´ıcil de explotar paralelismo en este benchmark, ReduxSTM es capaz de obtener aceleraci´on hasta un n´umero relativamente alto de threads aunque, para la carga computacional analizada, a partir de 8 threads los conflictos empeoran el rendimiento. 1 iteración por transacción 2 iteraciones por transacción 1 2 3 4 1 2 4 8 16 1 2 4 8 16 Threads Threads Speedup TinySTM* TinySTM Ord. ReduxSTM TS ReduxSTM CTI Fig. 9 300-Twolf: speedup para transacciones de una y dos iteraciones. S´ olo los STM ordenados garantizan el resultado correcto. TinySTM (no ordenado) se muestra como una referncia optimista. VII. Conclusiones Es conocido que muchas aplicaciones con patrones irregulares de acceso de memoria son dif´ıciles de paralelizar. En este contexto, la concurrencia optimista que proporcionan los sistemas de memoria transaccional (TM) puede resultar ´util para extraer paralelismo. En este trabajo se ha presentado ReduxSTM, un sistema TM software con soporte espec´ıfico para operaciones de reducci´on, un patr´on com´un en muchas aplicaciones irregulares. Las caracter´ısticas clave de ReduxSTM son que los commits de las transacciones se realizan en el orden equivalente al secuencial y que se utiliza la privatizaci´on subyacente al TM para filtrar los conflictos derivados de las operaciones de reducci´on cuando es posible, disminuyendo as´ı el n´umero de potenciales conflictos y, por tanto, de abortos. Comparado con t´ecnicas cl´asicas de paralelizaci´on de bucles de reducci´on, se ha comprobado que los enfoques STM son un buen compromiso entre facilidad de programaci´on, paralelismo explotado y sobrecarga de memoria extra necesaria; y que es posible mejorar el rendimiento de los STM si se a˜nade soporte espec´ıfico para reducciones, especialmente en patrones con una alta contenci´on. Agradecimientos Este trabajo ha recibido soporte del Gobierno de Espa˜na (proyecto TIN2013-42253-P), de la Junta de Andaluc´ıa (proyecto P12-TIC-1470) y de la Universidad de M´alaga, campus de excelencia internacional Andaluc´ıa Tech. 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), San Diego, CA, USA, 1993, pp. 289–300. [2] T. Harris, J. Larus, and R. Rajwar, Transactional Memory, 2nd Ed, Morgan & Claypool Publishers, USA, 2010. [3] L. Porter, B. Choi, and D.M. Tullsen, “Mapping out a path from hardware transactional memory to speculative multithreading,” in 18th Int’l. Conf. on Parallel Architectures and Compilation Techniques (PACT’09), Raleigh, NC, USA, 2009. [4] N.P. Johnson, H. Kim, P. Prabhu, A. Zaks, and D.I. August, “Speculative separation for privatization and reduc- tions,” in 33rd ACM Conf. on Programming Language Design and Implementation (PLDI’12), Beijing, China, 2012, pp. 359–370. [5] Lawrence Rauchwerger, “Speculative parallelization of loops,” in Encyclopedia of Parallel Computing, pp. 1901– 1912. Springer, 2011. [6] L. Han, W. Liu, and J.M. Tuck, “Speculative parallelization of partial reduction variables,” in 8th Ann. IEEE/ACM Int’l. Symp. on Code Generation and Optimization (CGO’10), Toronto, Canada, 2010, pp. 141– 150. [7] W. Blume, R. Doallo, R. Eigenmann, J. Grout, J. Hoeflinger, and T. Lawrence, “Parallel programming with Polaris,” IEEE Computer, vol. 29, no. 12, pp. 78–82, 1996. [8] M.W. Hall, J.M. Anderson, S.P. Amarasinghe, B.R. Murphy, S.W. Liao, and E. Bu, “Maximizing multiprocessor performance with the SUIF compiler,” IEEE Computer, vol. 29, no. 12, pp. 84–89, 1996. [9] P. Feautrier, “Array expansion,” in 2nd Int’l Conf. on Supercomputing (ICS’88), Saint Malo, France, 1988, pp. 429–441. [10] H. Yu and L. Rauchwerger, “An adaptive algorithm selection framework for reduction parallelization,” IEEE Trans. on Parallel and Distributed Systems, vol. 17, no. 10, pp. 1084–1096, 2006. [11] Josep M Perez, Rosa M Badia, and Jesus Labarta, “A dependency-aware task-based programming environment for multi-core architectures,” in 10th IEEE Int’l Conf. on Cluster Computing, 2008, pp. 142–151. [12] Carlos H Gonz´alez and Basilio B Fraguela, “A framework for argument-based task synchronization with automatic detection of dependencies,” Parallel Computing, vol. 39, no. 9, pp. 475–489, 2013. [13] Lawrence Rauchwerger and David A Padua, “The LRPD test: Speculative run-time parallelization of loops with privatization and reduction parallelization,” IEEE Trans, on Parallel and Distributed Systems, vol. 10, no. 2, pp. 160–180, 1999. [14] M. Gonzalez-Mesa, R. Quislant, E. Gutierrez, and O. Plata, “Dealing with reduction operations using transactional memory,” in 25th Int’l. Symp. on Computer Architecture and High Performance Computing (SBACPAD’13), Porto de Galinhas, Brasil, 2013, pp. 128–135. [15] M.A. Gonzalez-Mesa, E. Gutierrez, E.L. Zapata, and O. Plata, “Effective transactional memory execution management for improved concurrency,” ACM Trans. on Architecture and Code Optimization, vol. 11, no. 3, pp. 24:1–24:27, 2014. [16] C. von Praun, C. Ceze, and C. Cascaval, “Implicit parallelism with ordered transactions,” in 12th ACM Symp. on Principles and Practice of Parallel Programming (PLDI’07), San Diego, CA, USA, 2007, pp. 79–89. [17] A. Udupa, K. Rajan, and W. Thies, “ALTER: Exploiting breakable dependences for parallelization,” 32nd ACM Conf. on Programming Language Design and Implementation (PLDI’11), pp. 480–491, 2011. [18] M. DeVuyst, D.M. Tullsen, and S.W. Kim, “Runtime parallelization of legacy code on a transactional memory system,” in 6th Int’l. Conf. on High Performance and Embedded Architectures and Compilers (HiPEAC’11), Heraklion, Greece, 2011, pp. 127–136. [19] Wenjia Ruan, Yujie Liu, and Michael Spear, “Transactional Read-Modify-Write without aborts,” ACM Trans. on Architecture and Code Optimization, vol. 11, no. 4, pp. 1–24, 2015. [20] Ricardo Quislant, Eladio Gutierrez, Emilio L Zapata, and Oscar Plata, “Conflict detection in hardware transactional memory,” in Transactional Memory. Foundations, Algorithms, Tools, and Applications, pp. 127–149. Springer, 2015. [21] J.E. Gottschlich, M. Vachharajani, and J.G. Siek, “An efficient software transactional memory using commit-time invalidation,” in 8th Ann. IEEE/ACM Int’l. Symp. on Code Generation and Optimization (CGO’10), Toronto, Canada, 2010, pp. 101–110. [22] Pascal Felber, Christof Fetzer, Patrick Marlier, and Torvald Riegel, “Time-based software transactional memory,” IEEE Trans. on Parallel and Distributed Systems, vol. 21, no. 12, pp. 1793–1807, 2010. [23] C. Bienia, S. Kumar, J.P. Singh, and K. Li, “The PARSEC benchmark suite: Characterization and architectural implications,” in 17th Int’l. Conf. on Parallel Architectures and Compilation Techniques (PACT’08), Toronto, Canada, 2008, pp. 72–81. [24] J.J. Morales and S. Toxvaerd, “The Cell-Neighbour table method in molecular dynamics simulations,” Computer Physics Communications, vol. 71, pp. 71–76, 1992. [25] Ian Foster, Rob Schreiber, and Paul Havlak, “HPF-2, scope of activities and motivating applications,” Tech. Rep., Technical Report CRPC-TR94492, Rice University, 1994. [26] N. Mukherjee and J.R. Gurd, “A comparative analysis of four parallelisation schemes,” in 13th Int’l. Conf. on Supercomputing (ICS’99), Portland, OR, USA, 1999, pp. 278–285. [27] Manohar K. Prabhu and Kunle Olukotun, “Exposing speculative thread parallelism in SPEC2000,” in 10th ACM Symp. on Principles and Practice of Parallel Programming (PPoPP’05), Chicago, IL, USA, 2005, p. 142. [28] M. Dai Wang, M. Burcea, L. Li, et al., “Exploring the performance and programmability design space of hardware transactional memory,” in ACM Workshop on Transactional Computing (TRANSACT’14), Salt Lake City, UT, USA, 2014.