The Experts below are selected from a list of 2586 Experts worldwide ranked by ideXlab platform
Tomić Sasa - One of the best experts on this subject based on the ideXlab platform.
-
Towards lightweight and high-performance hardware Transactional memory
Universitat Politècnica de Catalunya, 2012Co-Authors: Tomić SasaAbstract:Conventional lock-based synchronization serializes accesses to critical sections guarded by the same lock. Using multiple locks brings the possibility of a deadlock or a livelock in the program, making parallel programming a difficult task. Transactional Memory (TM) is a promising paradigm for parallel programming, offering an alternative to lock-based synchronization. TM eliminates the risk of deadlocks and livelocks, while it provides the desirable semantics of Atomicity, Consistency, and Isolation of critical sections. TM speculatively executes a series of memory accesses as a single, Atomic, Transaction. The speculative changes of a Transaction are kept private until the Transaction commits. If a Transaction can break the Atomicity or cause a deadlock or livelock, the TM system aborts the Transaction and rolls back the speculative changes. To be effective, a TM implementation should provide high performance and scalability. While implementations of TM in pure software (STM) do not provide desirable performance, Hardware TM (HTM) implementations introduce much smaller overhead and have relatively good scalability, due to their better control of hardware resources. However, many HTM systems support only the Transactions that fit limited hardware resources (for example, private caches), and fall back to software mechanisms if hardware limits are reached. These HTM systems, called best-effort HTMs, are not desirable since they force a programmer to think in terms of hardware limits, to use both HTM and STM, and to manage concurrent Transactions in HTM and STM. In contrast with best-effort HTMs, unbounded HTM systems support overflowed Transactions, that do not fit into private caches. Unbounded HTM systems often require complex protocols or expensive hardware mechanisms for conflict detection between overflowed Transactions. In addition, an execution with overflowed Transactions is often much slower than an execution that has only regular Transactions. This is typically due to restrictive or approximative conflict management mechanism used for overflowed Transactions. In this thesis, we study hardware implementations of Transactional memory, and make three main contributions. First, we improve the general performance of HTM systems by proposing a scalable protocol for conflict management. The protocol has precise conflict detection, in contrast with often-employed inexact Bloom-filter-based conflict detection, which often falsely report conflicts between Transactions. Second, we propose a best-effort HTM that utilizes the new scalable conflict detection protocol, termed EazyHTM. EazyHTM allows parallel commits for all non-conflicting Transactions, and generally simplifies Transaction commits. Finally, we propose an unbounded HTM that extends and improves the initial protocol for conflict management, and we name it EcoTM. EcoTM features precise conflict detection, and it efficiently supports large as well as small and short Transactions. The key idea of EcoTM is to leverage an observation that very few locations are actually conflicting, even if applications have high contention. In EcoTM, each core locally detects if a cache line is non-conflicting, and conflict detection mechanism is invoked only for the few potentially conflicting cache lines.La Sincronización tradicional basada en los cerrojos de exclusión mutua (locks) serializa los accesos a las secciones críticas protegidas este cerrojo. La utilización de varios cerrojos en forma concurrente y/o paralela aumenta la posibilidad de entrar en abrazo mortal (deadlock) o en un bloqueo activo (livelock) en el programa, está es una de las razones por lo cual programar en forma paralela resulta ser mucho mas dificultoso que programar en forma secuencial. La memoria transaccional (TM) es un paradigma prometedor para la programación paralela, que ofrece una alternativa a los cerrojos. La memoria transaccional tiene muchas ventajas desde el punto de vista tanto práctico como teórico. TM elimina el riesgo de bloqueo mutuo y de bloqueo activo, mientras que proporciona una semántica de Atomicidad, coherencia, aislamiento con características similares a las secciones críticas. TM ejecuta especulativamente una serie de accesos a la memoria como una transacción atómica. Los cambios especulativos de la transacción se mantienen privados hasta que se confirma la transacción. Si una transacción entra en conflicto con otra transacción o sea que alguna de ellas escribe en una dirección que la otra leyó o escribió, o se entra en un abrazo mortal o en un bloqueo activo, el sistema de TM aborta la transacción y revierte los cambios especulativos. Para ser eficaz, una implementación de TM debe proporcionar un alto rendimiento y escalabilidad. Las implementaciones de TM en el software (STM) no proporcionan este desempeño deseable, en cambio, las mplementaciones de TM en hardware (HTM) tienen mejor desempeño y una escalabilidad relativamente buena, debido a su mejor control de los recursos de hardware y que la resolución de los conflictos así el mantenimiento y gestión de los datos se hace en hardware. Sin embargo, muchos de los sistemas de HTM están limitados a los recursos de hardware disponibles, por ejemplo el tamaño de las caches privadas, y dependen de mecanismos de software para cuando esos límites son sobrepasados. Estos sistemas HTM, llamados best-effort HTM no son deseables, ya que obligan al programador a pensar en términos de los límites existentes en el hardware que se esta utilizando, así como en el sistema de STM que se llama cuando los recursos son sobrepasados. Además, tiene que resolver que transacciones hardware y software se ejecuten concurrentemente. En cambio, los sistemas de HTM ilimitados soportan un numero de operaciones ilimitadas o sea no están restringidos a límites impuestos artificialmente por el hardware, como ser el tamaño de las caches o buffers internos. Los sistemas HTM ilimitados por lo general requieren protocolos complejos o mecanismos muy costosos para la detección de conflictos y el mantenimiento de versiones de los datos entre las transacciones. Por otra parte, la ejecución de transacciones es a menudo mucho más lenta que en una ejecución sobre un sistema de HTM que este limitado. Esto es debido al que los mecanismos utilizados en el HTM limitado trabaja con conjuntos de datos relativamente pequeños que caben o están muy cerca del núcleo del procesador. En esta tesis estudiamos implementaciones de TM en hardware. Presentaremos tres contribuciones principales: Primero, mejoramos el rendimiento general de los sistemas, al proponer un protocolo escalable para la gestión de conflictos. El protocolo detecta los conflictos de forma precisa, en contraste con otras técnicas basadas en filtros Bloom, que pueden reportar conflictos falsos entre las transacciones. Segundo, proponemos un best-effort HTM que utiliza el nuevo protocolo escalable detección de conflictos, denominado EazyHTM. EazyHTM permite la ejecución completamente paralela de todas las transacciones sin conflictos, y por lo general simplifica la ejecución. Por último, proponemos una extensión y mejora del protocolo inicial para la gestión de conflictos, que llamaremos EcoTM. EcoTM cuenta con detección de conflictos precisa, eficiente y es compatible tanto con transacciones grandes como con pequeñas. La idea clave de EcoTM es aprovechar la observación que en muy pocas ubicaciones de memoria aparecen los conflictos entre las transacciones, incluso en aplicaciones tienen muchos conflictos. En EcoTM, cada núcleo detecta localmente si la línea es conflictiva, además existe un mecanismo de detección de conflictos detallado que solo se activa para las pocas líneas de memoria que son potencialmente conflictivas
-
Towards lightweight and high-performance hardware Transactional memory
Universitat Politècnica de Catalunya, 2012Co-Authors: Tomić SasaAbstract:Conventional lock-based synchronization serializes accesses to critical sections guarded by the same lock. Using multiple locks brings the possibility of a deadlock or a livelock in the program, making parallel programming a difficult task. Transactional Memory (TM) is a promising paradigm for parallel programming, offering an alternative to lock-based synchronization. TM eliminates the risk of deadlocks and livelocks, while it provides the desirable semantics of Atomicity, Consistency, and Isolation of critical sections. TM speculatively executes a series of memory accesses as a single, Atomic, Transaction. The speculative changes of a Transaction are kept private until the Transaction commits. If a Transaction can break the Atomicity or cause a deadlock or livelock, the TM system aborts the Transaction and rolls back the speculative changes. To be effective, a TM implementation should provide high performance and scalability. While implementations of TM in pure software (STM) do not provide desirable performance, Hardware TM (HTM) implementations introduce much smaller overhead and have relatively good scalability, due to their better control of hardware resources. However, many HTM systems support only the Transactions that fit limited hardware resources (for example, private caches), and fall back to software mechanisms if hardware limits are reached. These HTM systems, called best-effort HTMs, are not desirable since they force a programmer to think in terms of hardware limits, to use both HTM and STM, and to manage concurrent Transactions in HTM and STM. In contrast with best-effort HTMs, unbounded HTM systems support overflowed Transactions, that do not fit into private caches. Unbounded HTM systems often require complex protocols or expensive hardware mechanisms for conflict detection between overflowed Transactions. In addition, an execution with overflowed Transactions is often much slower than an execution that has only regular Transactions. This is typically due to restrictive or approximative conflict management mechanism used for overflowed Transactions. In this thesis, we study hardware implementations of Transactional memory, and make three main contributions. First, we improve the general performance of HTM systems by proposing a scalable protocol for conflict management. The protocol has precise conflict detection, in contrast with often-employed inexact Bloom-filter-based conflict detection, which often falsely report conflicts between Transactions. Second, we propose a best-effort HTM that utilizes the new scalable conflict detection protocol, termed EazyHTM. EazyHTM allows parallel commits for all non-conflicting Transactions, and generally simplifies Transaction commits. Finally, we propose an unbounded HTM that extends and improves the initial protocol for conflict management, and we name it EcoTM. EcoTM features precise conflict detection, and it efficiently supports large as well as small and short Transactions. The key idea of EcoTM is to leverage an observation that very few locations are actually conflicting, even if applications have high contention. In EcoTM, each core locally detects if a cache line is non-conflicting, and conflict detection mechanism is invoked only for the few potentially conflicting cache lines.La Sincronización tradicional basada en los cerrojos de exclusión mutua (locks) serializa los accesos a las secciones críticas protegidas este cerrojo. La utilización de varios cerrojos en forma concurrente y/o paralela aumenta la posibilidad de entrar en abrazo mortal (deadlock) o en un bloqueo activo (livelock) en el programa, está es una de las razones por lo cual programar en forma paralela resulta ser mucho mas dificultoso que programar en forma secuencial. La memoria transaccional (TM) es un paradigma prometedor para la programación paralela, que ofrece una alternativa a los cerrojos. La memoria transaccional tiene muchas ventajas desde el punto de vista tanto práctico como teórico. TM elimina el riesgo de bloqueo mutuo y de bloqueo activo, mientras que proporciona una semántica de Atomicidad, coherencia, aislamiento con características similares a las secciones críticas. TM ejecuta especulativamente una serie de accesos a la memoria como una transacción atómica. Los cambios especulativos de la transacción se mantienen privados hasta que se confirma la transacción. Si una transacción entra en conflicto con otra transacción o sea que alguna de ellas escribe en una dirección que la otra leyó o escribió, o se entra en un abrazo mortal o en un bloqueo activo, el sistema de TM aborta la transacción y revierte los cambios especulativos. Para ser eficaz, una implementación de TM debe proporcionar un alto rendimiento y escalabilidad. Las implementaciones de TM en el software (STM) no proporcionan este desempeño deseable, en cambio, las mplementaciones de TM en hardware (HTM) tienen mejor desempeño y una escalabilidad relativamente buena, debido a su mejor control de los recursos de hardware y que la resolución de los conflictos así el mantenimiento y gestión de los datos se hace en hardware. Sin embargo, muchos de los sistemas de HTM están limitados a los recursos de hardware disponibles, por ejemplo el tamaño de las caches privadas, y dependen de mecanismos de software para cuando esos límites son sobrepasados. Estos sistemas HTM, llamados best-effort HTM no son deseables, ya que obligan al programador a pensar en términos de los límites existentes en el hardware que se esta utilizando, así como en el sistema de STM que se llama cuando los recursos son sobrepasados. Además, tiene que resolver que transacciones hardware y software se ejecuten concurrentemente. En cambio, los sistemas de HTM ilimitados soportan un numero de operaciones ilimitadas o sea no están restringidos a límites impuestos artificialmente por el hardware, como ser el tamaño de las caches o buffers internos. Los sistemas HTM ilimitados por lo general requieren protocolos complejos o mecanismos muy costosos para la detección de conflictos y el mantenimiento de versiones de los datos entre las transacciones. Por otra parte, la ejecución de transacciones es a menudo mucho más lenta que en una ejecución sobre un sistema de HTM que este limitado. Esto es debido al que los mecanismos utilizados en el HTM limitado trabaja con conjuntos de datos relativamente pequeños que caben o están muy cerca del núcleo del procesador. En esta tesis estudiamos implementaciones de TM en hardware. Presentaremos tres contribuciones principales: Primero, mejoramos el rendimiento general de los sistemas, al proponer un protocolo escalable para la gestión de conflictos. El protocolo detecta los conflictos de forma precisa, en contraste con otras técnicas basadas en filtros Bloom, que pueden reportar conflictos falsos entre las transacciones. Segundo, proponemos un best-effort HTM que utiliza el nuevo protocolo escalable detección de conflictos, denominado EazyHTM. EazyHTM permite la ejecución completamente paralela de todas las transacciones sin conflictos, y por lo general simplifica la ejecución. Por último, proponemos una extensión y mejora del protocolo inicial para la gestión de conflictos, que llamaremos EcoTM. EcoTM cuenta con detección de conflictos precisa, eficiente y es compatible tanto con transacciones grandes como con pequeñas. La idea clave de EcoTM es aprovechar la observación que en muy pocas ubicaciones de memoria aparecen los conflictos entre las transacciones, incluso en aplicaciones tienen muchos conflictos. En EcoTM, cada núcleo detecta localmente si la línea es conflictiva, además existe un mecanismo de detección de conflictos detallado que solo se activa para las pocas líneas de memoria que son potencialmente conflictivas.Postprint (published version
Ing-ray Chen - One of the best experts on this subject based on the ideXlab platform.
-
a nonblocking Atomic Transaction processing algorithm with real time property
International Journal of Reliability Quality and Safety Engineering, 2001Co-Authors: Iling Yen, Biao Chen, Lirong Dai, Ing-ray ChenAbstract:Many multiple server systems are now being used for heavily accessed web services. Performance, availability, and real-time Transaction processing are important requirements for many of these applications. In this paper, we apply the multi-invariant data structure (MIDS) concept to develop an Atomic Transaction processing algorithm. We show that our algorithm achieves non-blocking property. It also allows preemption at any point of Transaction processing without suffering from inconsistency problems or high recovery costs. Thus, the algorithm is suitable for real-time Transaction processing systems. Preliminary performance study results show that our algorithm incurs almost no overhead compared with two phase commit protocol.
-
Real-time Atomic Transaction processing using multi-invariant data structure
Proceedings 4th IEEE International Symposium on High-Assurance Systems Engineering, 1999Co-Authors: Ing-ray Chen, Biao ChenAbstract:Many multiple server systems are now being used for heavily accessed web services. Performance, availability, and real-time Transaction processing are important requirements for many of these applications. In this paper, we apply the multi-invariant data structure (MIDS) concept for real-time Transaction processing. We used the MIDS scheme to develop a highly available, reliable, real-time Transaction processing algorithm. We show that with very little overhead compared to the two-phase commit protocol, we achieve non-blocking Atomic Transaction processing. Also, the algorithm is suitable for real-time processing since a task can be preempted at any point of execution without expensive recovery procedure.
Biao Chen - One of the best experts on this subject based on the ideXlab platform.
-
a nonblocking Atomic Transaction processing algorithm with real time property
International Journal of Reliability Quality and Safety Engineering, 2001Co-Authors: Iling Yen, Biao Chen, Lirong Dai, Ing-ray ChenAbstract:Many multiple server systems are now being used for heavily accessed web services. Performance, availability, and real-time Transaction processing are important requirements for many of these applications. In this paper, we apply the multi-invariant data structure (MIDS) concept to develop an Atomic Transaction processing algorithm. We show that our algorithm achieves non-blocking property. It also allows preemption at any point of Transaction processing without suffering from inconsistency problems or high recovery costs. Thus, the algorithm is suitable for real-time Transaction processing systems. Preliminary performance study results show that our algorithm incurs almost no overhead compared with two phase commit protocol.
-
Real-time Atomic Transaction processing using multi-invariant data structure
Proceedings 4th IEEE International Symposium on High-Assurance Systems Engineering, 1999Co-Authors: Ing-ray Chen, Biao ChenAbstract:Many multiple server systems are now being used for heavily accessed web services. Performance, availability, and real-time Transaction processing are important requirements for many of these applications. In this paper, we apply the multi-invariant data structure (MIDS) concept for real-time Transaction processing. We used the MIDS scheme to develop a highly available, reliable, real-time Transaction processing algorithm. We show that with very little overhead compared to the two-phase commit protocol, we achieve non-blocking Atomic Transaction processing. Also, the algorithm is suitable for real-time processing since a task can be preempted at any point of execution without expensive recovery procedure.
M Zaptletal - One of the best experts on this subject based on the ideXlab platform.
-
the web services businessactivity initiator ws ba i protocol an extension to the web services businessactivity specification
International Conference on Web Services, 2007Co-Authors: H Erven, G Hicker, Christian Huemer, M ZaptletalAbstract:The Web services Transaction protocol family includes the WS-Atomic Transaction and the WS-business activity specifications in order to carry out distributed Transactions in a Web services (WS) environment. The WS-Atomic Transaction specification defines all necessary interfaces to carry out Transactional work. In contrary, the WS-business activity specification for long-running Transactions intentionally left the interface between initiator and coordinator undefined. This allows vendors to integrate WS-business activity coordinators into their business process engines. However, it requires proprietary protocols between initiator and coordinator. We propose an extension protocol to the WS-business activity specification that explicitly defines this interface between initiator and coordinator. This extension allows coordinators and initiators from different vendors to interoperate transparently. Accordingly, participants no longer need to trust an initiator-selected and likely initiator-run coordination service, but may use commonly trusted, third-party coordination services.
Alexey Gotsman - One of the best experts on this subject based on the ideXlab platform.
-
reconfigurable Atomic Transaction commit
Principles of Distributed Computing, 2019Co-Authors: Manuel Bravo, Alexey GotsmanAbstract:Modern data stores achieve scalability by partitioning data into shards and fault-tolerance by replicating each shard across several servers. A key component of such systems is a Transaction Certification Service (TCS), which Atomically commits a Transaction spanning multiple shards. Existing TCS protocols require 2f+1 crash-stop replicas per shard to tolerate f failures. In this paper we present Atomic commit protocols that require only f+1 replicas and reconfigure the system upon failures using an external reconfiguration service. We furthermore rigorously prove that these protocols correctly implement a recently proposed TCS specification. We present protocols in two different models---the standard asynchronous message-passing model and a model with Remote Direct Memory Access (RDMA), which allows a machine to access the memory of another machine over the network without involving the latter's CPU. Our protocols are inspired by a recent FARM system for RDMA-based Transaction processing. Our work codifies the core ideas of FARM as distributed TCS protocols, rigorously proves them correct and highlights the trade-offs required by the use of RDMA.
-
reconfigurable Atomic Transaction commit extended version
arXiv: Distributed Parallel and Cluster Computing, 2019Co-Authors: Manuel Bravo, Alexey GotsmanAbstract:Modern data stores achieve scalability by partitioning data into shards and fault-tolerance by replicating each shard across several servers. A key component of such systems is a Transaction Certification Service (TCS), which Atomically commits a Transaction spanning multiple shards. Existing TCS protocols require 2f+1 crash-stop replicas per shard to tolerate f failures. In this paper we present Atomic commit protocols that require only f+1 replicas and reconfigure the system upon failures using an external reconfiguration service. We furthermore rigorously prove that these protocols correctly implement a recently proposed TCS specification. We present protocols in two different models--the standard asynchronous message-passing model and a model with Remote Direct Memory Access (RDMA), which allows a machine to access the memory of another machine over the network without involving the latter's CPU. Our protocols are inspired by a recent FARM system for RDMA-based Transaction processing. Our work codifies the core ideas of FARM as distributed TCS protocols, rigorously proves them correct and highlights the trade-offs required by the use of RDMA.