The Experts below are selected from a list of 8577 Experts worldwide ranked by ideXlab platform
Alireza Adltabatabai - One of the best experts on this subject based on the ideXlab platform.
-
nepaltm design and implementation of nested parallelism for Transactional Memory systems
European Conference on Object-Oriented Programming, 2009Co-Authors: Haris Volos, Tatiana Shpeisman, Adam Welc, Xinmin Tian, Alireza Adltabatabai, Ravi NarayanaswamyAbstract:Transactional Memory (TM) promises to simplify construction of parallel applications by allowing programmers to reason about interactions between concurrently executing code fragments in terms of high-level properties they should possess. However, all currently existing TM systems deliver on this promise only partially by disallowing parallel execution of computations performed inside transactions. This paper fills in that gap by introducing NePaLTM (Nested PAralleLism for Transactional Memory), the first TM system supporting nested parallelism inside transactions. We describe a programming model where TM constructs (atomic blocks) are integrated with OpenMP constructs enabling nested parallelism. We also discuss the design and implementation of a working prototype where atomic blocks can be used for concurrency control at an arbitrary level of nested parallelism. Finally, we present a performance evaluation of our system by comparing transactions-based concurrency control mechanism for nested parallel computations with a mechanism already provided by OpenMP based on mutual exclusion.
-
nepaltm design and implementation of nested parallelism for Transactional Memory systems
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2009Co-Authors: Haris Volos, Tatiana Shpeisman, Adam Welc, Xinmin Tian, Alireza Adltabatabai, Ravi NarayanaswamyAbstract:We present the programming model, design and implementation of NePalTM; a Transactional Memory system where atomic blocks can be used for concurrency control at an arbitrary level of nested parallelism.
-
code generation and optimization for Transactional Memory constructs in an unmanaged language
Symposium on Code Generation and Optimization, 2007Co-Authors: Cheng Wang, Bratin Saha, Weiyu Chen, Youfeng Wu, Alireza AdltabatabaiAbstract:Transactional Memory offers significant advantages for concurrency control compared to locks. This paper presents the design and implementation of Transactional Memory constructs in an unmanaged language. Unmanaged languages pose a unique set of challenges to Transactional Memory constructs - for example, lack of type and Memory safety, use of function pointers, aliasing of local variables, and others. This paper describes novel compiler and runtime mechanisms that address these challenges and optimize the performance of transactions in an unmanaged environment. We have implemented these mechanisms in a production-quality C compiler and a high-performance software Transactional Memory runtime. We measure the effectiveness of these optimizations and compare the performance of lock-based versus transaction-based programming on a set of concurrent data structures and the SPLASH-2 benchmark suite. On a 16 processor SMP system, the transaction-based version of the SPLASH-2 benchmarks scales much better than the coarse-grain locking version and performs comparably to the fine-grain locking version. Compiler optimizations significantly reduce the overheads of Transactional Memory so that, on a single thread, the transaction-based version incurs only about 6.4% overhead compared to the lock-based version for the SPLASH-2 benchmark suite. Thus, our system is the first to demonstrate that transactions integrate well with an unmanaged language, and can perform as well as fine-grain locking while providing the programming ease of coarse-grain locking even on an unmanaged environment.
-
architectural support for software Transactional Memory
International Symposium on Microarchitecture, 2006Co-Authors: Bratin Saha, Alireza Adltabatabai, Quinn A JacobsonAbstract:Transactional Memory provides a concurrency control mechanism that avoids many of the pitfalls of lock-based synchronization. Researchers have proposed several different implementations of Transactional Memory, broadly classified into software Transactional Memory (STM) and hardware Transactional Memory (HTM). Both approaches have their pros and cons: STMs provide rich and flexible Transactional semantics on stock processors but incur significant overheads. HTMs, on the other hand, provide high performance but implement restricted semantics or add significant hardware complexity. This paper is the first to propose architectural support for accelerating transactions executed entirely in software. We propose instruction set architecture (ISA) extensions and novel hardware mechanisms that improve STM performance. We adapt a high-performance STM algorithm supporting rich Transactional semantics to our ISA extensions (called hardware accelerated software Transactional Memory or HASTM). HASTM accelerates fully virtualized nested transactions, supports language integration, and provides both object-based and cache-line based conflict detection. We have implemented HASTM in an accurate multi-core IA32 simulator. Our simulation results show that (1) HASTM single-thread performance is comparable to a conventional HTM implementation; (2) HASTM scaling is comparable to a STM implementation; and (3) HASTM is resilient to spurious aborts and can scale better than HTM in a multi-core setting. Thus, HASTM provides the flexibility and rich semantics of STM, while giving the performance of HTM.
-
compiler and runtime support for efficient software Transactional Memory
Programming Language Design and Implementation, 2006Co-Authors: Alireza Adltabatabai, Brian T Lewis, Vijay Menon, Brian R Murphy, Bratin Saha, Tatiana ShpeismanAbstract:Programmers have traditionally used locks to synchronize concurrent access to shared data. Lock-based synchronization, however, has well-known pitfalls: using locks for fine-grain synchronization and composing code that already uses locks are both difficult and prone to deadlock. Transactional Memory provides an alternate concurrency control mechanism that avoids these pitfalls and significantly eases concurrent programming. Transactional Memory language constructs have recently been proposed as extensions to existing languages or included in new concurrent language specifications, opening the door for new compiler optimizations that target the overheads of Transactional Memory.This paper presents compiler and runtime optimizations for Transactional Memory language constructs. We present a high-performance software Transactional Memory system (STM) integrated into a managed runtime environment. Our system efficiently implements nested transactions that support both composition of transactions and partial roll back. Our JIT compiler is the first to optimize the overheads of STM, and we show novel techniques for enabling JIT optimizations on STM operations. We measure the performance of our optimizations on a 16-way SMP running multi-threaded Transactional workloads. Our results show that these techniques enable Transactional Memory's performance to compete with that of well-tuned synchronization.
Ravi Narayanaswamy - One of the best experts on this subject based on the ideXlab platform.
-
nepaltm design and implementation of nested parallelism for Transactional Memory systems
European Conference on Object-Oriented Programming, 2009Co-Authors: Haris Volos, Tatiana Shpeisman, Adam Welc, Xinmin Tian, Alireza Adltabatabai, Ravi NarayanaswamyAbstract:Transactional Memory (TM) promises to simplify construction of parallel applications by allowing programmers to reason about interactions between concurrently executing code fragments in terms of high-level properties they should possess. However, all currently existing TM systems deliver on this promise only partially by disallowing parallel execution of computations performed inside transactions. This paper fills in that gap by introducing NePaLTM (Nested PAralleLism for Transactional Memory), the first TM system supporting nested parallelism inside transactions. We describe a programming model where TM constructs (atomic blocks) are integrated with OpenMP constructs enabling nested parallelism. We also discuss the design and implementation of a working prototype where atomic blocks can be used for concurrency control at an arbitrary level of nested parallelism. Finally, we present a performance evaluation of our system by comparing transactions-based concurrency control mechanism for nested parallel computations with a mechanism already provided by OpenMP based on mutual exclusion.
-
nepaltm design and implementation of nested parallelism for Transactional Memory systems
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2009Co-Authors: Haris Volos, Tatiana Shpeisman, Adam Welc, Xinmin Tian, Alireza Adltabatabai, Ravi NarayanaswamyAbstract:We present the programming model, design and implementation of NePalTM; a Transactional Memory system where atomic blocks can be used for concurrency control at an arbitrary level of nested parallelism.
Haris Volos - One of the best experts on this subject based on the ideXlab platform.
-
nepaltm design and implementation of nested parallelism for Transactional Memory systems
European Conference on Object-Oriented Programming, 2009Co-Authors: Haris Volos, Tatiana Shpeisman, Adam Welc, Xinmin Tian, Alireza Adltabatabai, Ravi NarayanaswamyAbstract:Transactional Memory (TM) promises to simplify construction of parallel applications by allowing programmers to reason about interactions between concurrently executing code fragments in terms of high-level properties they should possess. However, all currently existing TM systems deliver on this promise only partially by disallowing parallel execution of computations performed inside transactions. This paper fills in that gap by introducing NePaLTM (Nested PAralleLism for Transactional Memory), the first TM system supporting nested parallelism inside transactions. We describe a programming model where TM constructs (atomic blocks) are integrated with OpenMP constructs enabling nested parallelism. We also discuss the design and implementation of a working prototype where atomic blocks can be used for concurrency control at an arbitrary level of nested parallelism. Finally, we present a performance evaluation of our system by comparing transactions-based concurrency control mechanism for nested parallel computations with a mechanism already provided by OpenMP based on mutual exclusion.
-
nepaltm design and implementation of nested parallelism for Transactional Memory systems
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2009Co-Authors: Haris Volos, Tatiana Shpeisman, Adam Welc, Xinmin Tian, Alireza Adltabatabai, Ravi NarayanaswamyAbstract:We present the programming model, design and implementation of NePalTM; a Transactional Memory system where atomic blocks can be used for concurrency control at an arbitrary level of nested parallelism.
-
performance pathologies in hardware Transactional Memory
IEEE Micro, 2008Co-Authors: Jayaram Bobba, Haris Volos, Kevin E Moore, Luke Yen, Mark D Hill, Michael M Swift, David A WoodAbstract:Transactional Memory is a promising approach to ease parallel programming. Hardware Transactional Memory system designs reflect choices along three key design dimensions: conflict detection, version management, and conflict resolution. The authors identify a set of performance pathologies that could degrade performance in proposed HTM designs. Improving conflict resolution could eliminate these pathologies so designers can build robust HTM systems.
-
performance pathologies in hardware Transactional Memory
International Symposium on Computer Architecture, 2007Co-Authors: Jayaram Bobba, Haris Volos, Kevin E Moore, Luke Yen, Mark D Hill, Michael M Swift, David A WoodAbstract:Hardware Transactional Memory (HTM) systems reflect choices from three key design dimensions: conflict detection, version management, and conflict resolution. Previously proposed HTMs represent three points in this design space: lazy conflict detection, lazy version management, committer wins (LL); eager conflict detection, lazy version management, requester wins (EL); and eager conflict detection, eager version management, and requester stalls with conservative deadlock avoidance (EE). To isolate the effects of these high-level design decisions, we develop a common framework that abstracts away differences in cache write policies, interconnects, and ISA to compare these three design points. Not surprisingly, the relative performance of these systems depends on the workload. Under light Transactional loads they perform similarly, but under heavy loads they differ by up to 80%. None of the systems performs best on all of our benchmarks. We identify seven performance pathologies-interactions between workload and system that degrade performance-as the root cause of many performance differences: FriendlyFire, StarvingWriter, SerializedCommit, FutileStall, StarvingElder, RestartConvoy, and DuelingUpgrades. We discuss when and on which systems these pathologies can occur and show that they actually manifest within TM workloads. The insight provided by these pathologies motivated four enhanced systems that often significantly reduce Transactional Memory overhead. Importantly, by avoiding transaction pathologies, each enhanced system performs well across our suite of benchmarks.
Maurice Herlihy - One of the best experts on this subject based on the ideXlab platform.
-
improving parallelism in hardware Transactional Memory
ACM Transactions on Architecture and Code Optimization, 2018Co-Authors: Dave Dice, Maurice Herlihy, Alex KoganAbstract:Today’s hardware Transactional Memory (HTM) systems rely on existing coherence protocols, which implement a requester-wins strategy. This, in turn, leads to poor performance when transactions frequently conflict, causing them to resort to a non-speculative fallback path. Often, such a path severely limits parallelism. In this article, we propose very simple architectural changes to the existing requester-wins HTM implementations that enhance conflict resolution between hardware transactions and thus improve their parallelism. Our idea is compatible with existing HTM systems, requires no changes to target applications that employ traditional lock synchronization, and is shown to provide robust performance benefits.
-
Embedded-TM: Energy and Throughput Efficient Transactional Memory for Embedded Multicore Systems
2012Co-Authors: Cesare Ferri, Samantha Wood, Tali Moreshet, Iris Bahar, Maurice HerlihyAbstract:Abstract. We propose a new design for an energy-efficient hardware Transactional Memory (HTM) system for power-aware embedded devices. Prior hardware Transactional Memory designs proposed a small, fully-associative Transactional cache at the same level as the L1 cache. We propose an alternative design that unifies the Transactional and L1 caches, and provides a small victim cache to reduce effects of capacity and conflict evictions. We evaluate our new HTM scheme on a variety of benchmarks, both in terms of energy and performance. We show that the victim cache scheme can provide up to a 4X improvement in energy-delay product, compared to a traditional HTM scheme that uses a separate Transactional cache.
-
embedded tm energy and complexity effective hardware Transactional Memory for embedded multicore systems
Journal of Parallel and Distributed Computing, 2010Co-Authors: Cesare Ferri, Samantha Wood, Tali Moreshet, Iris R Bahar, Maurice HerlihyAbstract:We investigate how Transactional Memory can be adapted for embedded systems. We consider energy consumption and complexity to be driving concerns in the design of these systems and therefore adapt simple hardware Transactional Memory (HTM) schemes in our architectural design. We propose several different cache structures and contention management schemes to support HTM and evaluate them in terms of energy, performance, and complexity. We find that ignoring energy considerations can lead to poor design choices, particularly for resource-constrained embedded platforms. We conclude that with the right balance of energy efficiency and simplicity, HTM will become an attractive choice for future embedded system designs.
-
distributed Transactional Memory for metric space networks
Distributed Computing, 2007Co-Authors: Maurice HerlihyAbstract:Transactional Memory is a concurrent programming API in which concurrent threads synchronize via transactions (instead of locks). Although this model has mostly been studied in the context of multiprocessors, it has attractive features for distributed systems as well. In this paper, we consider the problem of implementing Transactional Memory in a network of nodes where communication costs form a metric. The heart of our design is a new cache-coherence protocol, called the Ballistic protocol, for tracking and moving up-to-date copies of cached objects. For constant-doubling metrics, a broad class encompassing both Euclidean spaces and growth-restricted networks, this protocol has stretch logarithmic in the diameter of the network.
-
Transactional Memory architectural support for lock free data structures
International Symposium on Computer Architecture, 1993Co-Authors: Maurice Herlihy, Eliot J B MossAbstract:A shared data structure is lock-free if its operations do not require mutual exclusion. If one process is interrupted in the middle of an operation, other processes will not be prevented from operating on that object. In highly concurrent systems, lock-free data structures avoid common problems associated with conventional locking techniques, including priority inversion, convoying, and difficulty of avoiding deadlock. This paper introduces Transactional Memory , a new multiprocessor architecture intended to make lock-free synchronization as efficient (and easy to use) as conventional techniques based on mutual exclusion. Transactional Memory allows programmers to define customized read-modify-write operations that apply to multiple, independently-chosen words of Memory. It is implemented by straightforward extensions to any multiprocessor cache-coherence protocol. Simulation results show that Transactional Memory matches or outperforms the best known locking techniques for simple benchmarks, even in the absence of priority inversion, convoying, and deadlock.
Zhiyi Huang - One of the best experts on this subject based on the ideXlab platform.
-
performance evaluation of view oriented Transactional Memory
Parallel Computing, 2013Co-Authors: Zhiyi Huang, Kaicheung LeungAbstract:This paper extensively evaluates the performance of View-Oriented Transactional Memory (VOTM) based on two implementations that adopt different Transactional Memory (TM) algorithms. The Restricted Admission Control (RAC) mechanism in VOTM plays a key role in the performance gains of VOTM. In this paper, we use six applications to evaluate the performance advantage of VOTM. Experimental results show that partitioning shared data into separate views can improve performance when one of the views has high contention while others may have low contention, because the contention of each view is independently controlled by RAC. For Memory-intensive applications, even when the contention on application data is not high enough to justify admission control by RAC, partitioning shared data into different views can improve the performance of TM systems due to the reduced contention on the metadata of the TM systems.
-
Restricted admission control in view-oriented Transactional Memory
The Journal of Supercomputing, 2013Co-Authors: Kaicheung Leung, Yawen Chen, Zhiyi HuangAbstract:This paper proposes a Restricted Admission Control (RAC) scheme for View-Oriented Transactional Memory. The scheme can control the number of threads concurrently accessing a view in order to reduce the number of aborts of transactions. The RAC scheme has the merits of both the locking mechanism and the Transactional Memory. A theoretical model is proposed to analyze the performance of the RAC scheme and to provide guidance for dynamic adjustment of the number of concurrent threads accessing the same view. Experimental results demonstrate that theoretical RAC model can mostly provide correct guidance to Transactional concurrency control. Our RAC implementation shows that RAC can optimize concurrency control of transactions and performs much better than conventional Transactional Memory systems such as TinySTM that have no dynamic admission control.
-
view oriented Transactional Memory
International Conference on Parallel Processing, 2011Co-Authors: Kaicheung Leung, Zhiyi HuangAbstract:This paper proposes the View-Oriented Transactional Memory (VOTM) model to seamlessly integrate locking mechanism and Transactional Memory. The VOTM model allows programmers to partition the shared Memory into "views", which are non-overlapping sets of shared data objects. The Restricted Admission Control (RAC) scheme can then control the number of processes accessing each view individually in order to reduce the number of aborts of transactions. The RAC scheme has the merits of both the locking mechanism and the Transactional Memory. Experimental results demonstrate that VOTM outperforms traditional Transactional Memory models such as TinySTM by up to 270%.
