En informática e ingeniería , la memoria transaccional intenta simplificar la programación concurrente al permitir que un grupo de instrucciones de carga y almacenamiento se ejecuten de forma atómica . Es un mecanismo de control de concurrencia análogo a las transacciones de bases de datos para controlar el acceso a la memoria compartida en la computación concurrente . Los sistemas de memoria transaccional proporcionan abstracción de alto nivel como alternativa a la sincronización de subprocesos de bajo nivel. Esta abstracción permite la coordinación entre lecturas y escrituras simultáneas de datos compartidos en sistemas paralelos. [1]
Motivación
En la programación concurrente, se requiere sincronización cuando los subprocesos paralelos intentan acceder a un recurso compartido. Las construcciones de sincronización de subprocesos de bajo nivel, como los bloqueos, son pesimistas y prohíben que los subprocesos que están fuera de una sección crítica realicen cambios. El proceso de aplicar y liberar bloqueos a menudo funciona como una sobrecarga adicional en las cargas de trabajo con poco conflicto entre los subprocesos. La memoria transaccional proporciona un control de concurrencia optimista al permitir que los subprocesos se ejecuten en paralelo con una interferencia mínima. [2] El objetivo de los sistemas de memoria transaccional es admitir de forma transparente las regiones de código marcadas como transacciones mediante la aplicación de la atomicidad , la coherencia y el aislamiento .
Una transacción es una colección de operaciones que pueden ejecutar y confirmar cambios siempre que no exista un conflicto. Cuando se detecta un conflicto, una transacción volverá a su estado inicial (antes de cualquier cambio) y se volverá a ejecutar hasta que se eliminen todos los conflictos. Antes de una confirmación exitosa, el resultado de cualquier operación es puramente especulativo dentro de una transacción. A diferencia de la sincronización basada en bloqueos en la que las operaciones se serializan para evitar la corrupción de datos, las transacciones permiten un paralelismo adicional siempre que pocas operaciones intenten modificar un recurso compartido. Dado que el programador no es responsable de identificar explícitamente los bloqueos o el orden en que se adquieren, los programas que utilizan memoria transaccional no pueden producir un interbloqueo . [2]
Con estas construcciones en su lugar, la memoria transaccional proporciona una abstracción de programación de alto nivel al permitir a los programadores encerrar sus métodos dentro de bloques transaccionales. Las implementaciones correctas aseguran que los datos no se puedan compartir entre subprocesos sin pasar por una transacción y producen un resultado serializable . Por ejemplo, el código se puede escribir como:
def transfer_money ( from_account , to_account , amount ): "" "Transferir dinero de una cuenta a otra." "" con la transacción (): from_account . saldo - = monto a_cuenta . saldo + = monto
En el código, el bloque definido por "transacción" tiene atomicidad, consistencia y aislamiento garantizados por la implementación de la memoria transaccional subyacente y es transparente para el programador. Las variables dentro de la transacción están protegidas de conflictos externos, lo que garantiza que se transfiera la cantidad correcta o que no se tome ninguna acción. Tenga en cuenta que los errores relacionados con la simultaneidad aún son posibles en programas que utilizan una gran cantidad de transacciones, especialmente en implementaciones de software en las que la biblioteca proporcionada por el lenguaje no puede imponer un uso correcto. Los errores introducidos a través de transacciones a menudo pueden ser difíciles de depurar, ya que los puntos de interrupción no se pueden colocar dentro de una transacción. [2]
La memoria transaccional está limitada porque requiere una abstracción de memoria compartida. Aunque los programas de memoria transaccional no pueden producir un punto muerto, los programas pueden todavía sufrir de una livelock o recurso inanición . Por ejemplo, las transacciones más largas pueden revertirse repetidamente en respuesta a múltiples transacciones más pequeñas, perdiendo tiempo y energía. [2]
Hardware vs software
La abstracción de la atomicidad en la memoria transaccional requiere un mecanismo de hardware para detectar conflictos y deshacer cualquier cambio realizado en los datos compartidos. [3] Los sistemas de memoria transaccional de hardware pueden comprender modificaciones en procesadores, caché y protocolo de bus para soportar transacciones. [4] [5] [6] [7] [8] Los valores especulativos en una transacción deben almacenarse en búfer y no deben ser vistos por otros hilos hasta el momento de la confirmación. Los búferes grandes se utilizan para almacenar valores especulativos mientras se evita la propagación de escritura a través del protocolo de coherencia de caché subyacente . Tradicionalmente, los búferes se han implementado utilizando diferentes estructuras dentro de la jerarquía de memoria, como colas de almacenamiento o cachés. Los búferes más alejados del procesador, como el caché L2, pueden contener valores más especulativos (hasta unos pocos megabytes). El tamaño óptimo de un colchón todavía está en debate debido al uso limitado de transacciones en programas comerciales. [3] En una implementación de caché, las líneas de caché generalmente se aumentan con bits de lectura y escritura. Cuando el controlador de hardware recibe una solicitud, el controlador usa estos bits para detectar un conflicto. Si se detecta un conflicto de serialización en una transacción paralela, se descartan los valores especulativos. Cuando se utilizan cachés, el sistema puede presentar el riesgo de conflictos falsos debido al uso de granularidad de línea de caché. [3] El enlace de carga / condicional de almacenamiento (LL / SC) que ofrecen muchos procesadores RISC puede verse como el soporte de memoria transaccional más básico; sin embargo, LL / SC generalmente opera con datos del tamaño de una palabra de máquina nativa, por lo que solo se admiten transacciones de una sola palabra. [4] Aunque la memoria transaccional de hardware proporciona un rendimiento máximo en comparación con las alternativas de software, se ha visto un uso limitado en este momento.
La memoria transaccional de software proporciona semántica de memoria transaccional en una biblioteca de tiempo de ejecución de software o en el lenguaje de programación, [9] y requiere un soporte de hardware mínimo (normalmente una operación de comparación e intercambio atómico , o equivalente). Como desventaja, las implementaciones de software generalmente tienen una penalización en el rendimiento, en comparación con las soluciones de hardware. La aceleración de hardware puede reducir algunos de los gastos generales asociados con la memoria transaccional de software.
Debido a la naturaleza más limitada de la memoria transaccional de hardware (en las implementaciones actuales), el software que la usa puede requerir un ajuste bastante extenso para beneficiarse completamente de ella. Por ejemplo, el asignador de memoria dinámica puede tener una influencia significativa en el rendimiento y, del mismo modo, el relleno de la estructura puede afectar el rendimiento (debido a la alineación de la caché y los problemas de falsa compartición); en el contexto de una máquina virtual, varios subprocesos en segundo plano pueden provocar abortos inesperados de transacciones. [10]
Historia
Una de las primeras implementaciones de la memoria transaccional fue el búfer de almacenamiento cerrado utilizado en los procesadores Crusoe y Efficeon de Transmeta . Sin embargo, esto solo se usó para facilitar optimizaciones especulativas para la traducción binaria, en lugar de cualquier forma de multiproceso especulativo o exponerlo directamente a los programadores. Azul Systems también implementó memoria transaccional de hardware para acelerar sus dispositivos Java , pero esto se ocultó de manera similar a los forasteros. [11]
Sun Microsystems implementó memoria transaccional de hardware y una forma limitada de multiproceso especulativo en su procesador Rock de alta gama . Esta implementación demostró que podría usarse para elisión de bloqueo y sistemas de memoria transaccional híbridos más complejos, donde las transacciones se manejan con una combinación de hardware y software. El procesador Rock fue cancelado en 2009, justo antes de la adquisición por parte de Oracle ; Si bien los productos reales nunca se lanzaron, los investigadores dispusieron de varios sistemas prototipo. [11]
En 2009, AMD propuso el Advanced Synchronization Facility (ASF), un conjunto de extensiones x86 que proporcionan una forma muy limitada de soporte de memoria transaccional de hardware. El objetivo era proporcionar primitivas de hardware que pudieran usarse para la sincronización de nivel superior, como la memoria transaccional de software o los algoritmos sin bloqueo. Sin embargo, AMD no ha anunciado si ASF se utilizará en productos y, de ser así, en qué plazo. [11]
Más recientemente, IBM anunció en 2011 que Blue Gene / Q tenía soporte de hardware para memoria transaccional y multiproceso especulativo. La memoria transaccional se puede configurar en dos modos; el primero es un modo desordenado y de una sola versión, donde una escritura de una transacción causa un conflicto con cualquier transacción que lea la misma dirección de memoria. El segundo modo es para multiproceso especulativo, que proporciona una memoria transaccional ordenada y con múltiples versiones. Los subprocesos especulativos pueden tener diferentes versiones de la misma dirección de memoria, y la implementación de hardware realiza un seguimiento de la antigüedad de cada subproceso. Los subprocesos más jóvenes pueden acceder a datos de subprocesos más antiguos (pero no al revés), y las escrituras en la misma dirección se basan en el orden de los subprocesos. En algunos casos, las dependencias entre subprocesos pueden hacer que las versiones más recientes se anulen. [11]
Intel 's transaccional sincronización de extensiones (TSX) está disponible en algunos de los Skylake procesadores. También se implementó anteriormente en los procesadores Haswell y Broadwell , pero las implementaciones resultaron ser defectuosas en ambas ocasiones y se deshabilitó el soporte para TSX. La especificación TSX describe la API de memoria transaccional para que la utilicen los desarrolladores de software, pero no incluye detalles sobre la implementación técnica. [11] La arquitectura ARM tiene una extensión similar. [12]
A partir de GCC 4.7, está disponible una biblioteca experimental para memoria transaccional que utiliza una implementación híbrida. La variante PyPy de Python también introduce memoria transaccional al lenguaje.
Implementaciones disponibles
- Hardware:
- Armar extensión de memoria transaccional (TME) [13]
- Procesador de rocas (cancelado por Oracle )
- Procesador Blue Gene / Q de IBM (supercomputadora Sequoia) [14]
- IBM zEnterprise EC12 , el primer servidor comercial que incluye instrucciones de procesador de memoria transaccional
- Extensiones de sincronización transaccional de Intel (TSX), disponibles en procesadores seleccionados basados en Haswell y más nuevos hasta que se eliminen en Comet Lake
- IBM POWER8 y 9 , eliminado en POWER10 ( Power ISA v.3.1 ) [15] [16] [17]
- Software:
- Vega 2 de Azul Systems [18]
- STM Monad en el compilador de Glasgow Haskell [19]
- STMX en Common Lisp [20]
- Refs en Clojure
- gcc 4.7+ para C / C ++ [21] [22] [23] [24]
- PyPy [25]
- Parte del marco de transacciones de picotm para C [26]
- El TVar en concurrent-ruby, una biblioteca de concurrencia para Ruby [27]
Ver también
- Semántica de la memoria
- Exclusión mutua automática
Referencias
- ^ Harris, Tim; Larus, James; Rajwar, Ravi (2 de junio de 2010). "Memoria transaccional, 2ª edición". Conferencias de síntesis sobre arquitectura informática . 5 (1): 1–263. doi : 10.2200 / S00272ED1V01Y201006CAC011 . ISSN 1935-3235 .
- ^ a b c d "Memoria transaccional: historia y desarrollo" . Centro de Kukuruku . Consultado el 16 de noviembre de 2016 .
- ^ a b c Solihin, Yan (2016). Fundamentos de la arquitectura multinúcleo paralela . Berkeley, California: Chapman & Hall. págs. 287-292. ISBN 978-1-4822-1118-4.
- ^ a b Herlihy, Maurice; Moss, J. Eliot B. (1993). "Memoria transaccional: soporte arquitectónico para estructuras de datos sin bloqueo" (PDF) . Actas del 20º Simposio Internacional de Arquitectura de Computadores (ISCA) . págs. 289–300.
- ^ Stone, JM; Stone, HS; Heidelberger, P .; Turek, J. (1993). "Múltiples reservas y la actualización de Oklahoma". Tecnología IEEE paralela y distribuida: sistemas y aplicaciones . 1 (4): 58–71. doi : 10.1109 / 88.260295 .
- ^ Hammond, L; Wong, V .; Chen, M .; Carlstrom, BD; Davis, JD; Hertzberg, B .; Prabhu, MK; Honggo Wijaya; Kozyrakis, C .; Olukotun, K. (2004). "Coherencia y consistencia de la memoria transaccional". Actas del 31º Simposio Internacional Anual de Arquitectura de Computadoras (ISCA) . págs. 102-13. doi : 10.1109 / ISCA.2004.1310767 .
- ^ Ananian, CS; Asanovic, K .; Kuszmaul, BC; Leiserson, CE; Lie, S. (2005). "Memoria transaccional ilimitada". XI Simposio Internacional de Arquitectura de Computadoras de Alto Rendimiento . págs. 316–327. doi : 10.1109 / HPCA.2005.41 . ISBN 0-7695-2275-0.
- ^ "LogTM: memoria transaccional basada en registros" (PDF) . WISC.
- ^ "El lenguaje de programación transaccional ATOMOΣ" (PDF) . Stanford.
- ^ Odaira, R .; Castanos, JG; Nakaike, T. (2013). "¿Los programas C y Java escalan de manera diferente en la memoria transaccional de hardware?". 2013 IEEE International Symposium on Workload Characterization (IISWC) . pag. 34. doi : 10.1109 / IISWC.2013.6704668 . ISBN 978-1-4799-0555-3.
- ^ a b c d e David Kanter (21 de agosto de 2012). "Análisis de la memoria transaccional de Haswell" . Tecnologías del mundo real . Consultado el 19 de noviembre de 2013 .
- ^ "Arm lanza SVE2 y TME para arquitectura de perfil A - Blog de procesadores - Procesadores - Comunidad de Arm" . community.arm.com . Consultado el 25 de mayo de 2019 .
- ^ "Intrínsecos de extensión de memoria transaccional (TME)" . Consultado el 5 de mayo de 2020 .
- ^ "IBM planta memoria transaccional en CPU" . EE Times.
- ^ Brian Hall; Ryan Arnold; Peter Bergner; Wainer dos Santos Moschetta; Robert Enenkel; Pat Haugen; Michael R. Meissner; Alex Mericas; Philipp Oehler; Berni Schiefer; Brian F. Veale; Suresh Warrier; Daniel Zabawa; Adhemerval Zanella (2014). Técnicas de optimización y ajuste del rendimiento para procesadores IBM, incluido IBM POWER8 (PDF) . IBM Redbooks. págs. 37–40. ISBN 978-0-7384-3972-3.
- ^ Wei Li, funciones integradas de memoria transaccional de hardware del compilador IBM XL para IBM AIX en sistemas basados en procesadores IBM POWER8
- ^ "Power ISA Versión 3.1" . openpowerfoundation.org. 2020-05-01 . Consultado el 10 de octubre de 2020 .
- ^ Java en 1000 núcleos - Tales of Hardware / Software CoDesign en YouTube
- ^ "Control.Monad.STM" . hackage.haskell.org . Consultado el 6 de febrero de 2020 .
- ^ "Página de inicio de STMX" .
- ^ Wong, Michael. "Construcciones de lenguaje transaccional para C ++" (PDF) . Consultado el 12 de enero de 2011 .
- ^ "Breve tutorial de memoria transaccional GCC" .
- ^ "Opciones de dialecto C - Uso de la colección de compiladores GNU (GCC)" .
- ^ "TransactionalMemory - Wiki de GCC" .
- ^ Rigo, Armin. "Uso de todos estos núcleos: memoria transaccional en PyPy" . europython.eu . Consultado el 7 de abril de 2015 .
- ^ "picotm - Administrador de transacciones abierto, personalizable e integrado portátil" .
- ^ "Concurrente :: TVar" .
Otras lecturas
- Harris, Tim; Larus, James R .; Rajwar, Ravi (diciembre de 2010), Transactional Memory, segunda edición , Synthesis Lectures on Computer Architecture, 5 , Morgan & Claypool, págs. 1–263, doi : 10.2200 / S00272ED1V01Y201006CAC011
- McKenney, Paul E .; Michael, Maged M .; Triplett, Josh; Walpole, Jonathan (julio de 2010). "Por qué el césped puede no ser más verde en el otro lado: una comparación de bloqueo vs memoria transaccional". SIGOPS Oper. Syst. Rev . Nueva York, NY, EE.UU .: ACM . 44 (3): 93-101. doi : 10.1145 / 1842733.1842749 . ISSN 0163-5980 .
- Dave Dice, Yossi Lev, Mark Moir, Dan Nussbaum y Marek Olszewski. (2009) "Experiencia inicial con una implementación de memoria transaccional de hardware comercial". Informe técnico de Sun Microsystems (60 págs.) SMLI TR-2009-180. Una versión corta apareció en ASPLOS'09 doi : 10.1145 / 1508244.1508263
- Amy Wang, Matthew Gaudet, Peng Wu, José Nelson Amaral, Martin Ohmacht, Christopher Barton, Raul Silvera y Maged Michael. " Evaluación del soporte hardware Blue Gene / Q para memorias transaccionales ". En Actas de la 21ª conferencia internacional sobre arquitecturas paralelas y técnicas de compilación, págs. 127-136. ACM, 2012.
- Jacobi, C., Slegel, T. y Greiner, D. (2012, diciembre). " Arquitectura e implementación de memoria transaccional para IBM System z ". En Microarchitecture (MICRO), 2012 45th Annual IEEE / ACM International Symposium on (págs. 25–36). IEEE.
- Harold W. Cain, Maged M. Michael, Brad Frey, Cathy May, Derek Williams y Hung Le. "Soporte arquitectónico robusto para la memoria transaccional en la arquitectura de energía". En ISCA '13 Proceedings of the 40th Annual International Symposium on Computer Architecture, págs. 225–236, ACM, 2013. doi : 10.1145 / 2485922.2485942
enlaces externos
- Michael Neuling (IBM), " ¿Cuál es el trato con la memoria transaccional de hardware? ", Charla introductoria en linux.conf.au 2014
- Transactional Memory Online : bibliografía categorizada sobre la memoria transaccional