Variable Granularity Access Tracking Scheme for Improving the Performance of Software Transactional Memory

Software transactional memory (STM) has been proposed as a promising programming paradigm for shared memory multi-threaded programs as an alternative to conventional lock based synchronization primitives. Typical STM implementations employ a conflict detection scheme, which works with uniform access granularity, tracking shared data accesses either at word/cache line or at object level. It is well known that a single fixed access tracking granularity cannot meet the conflicting goals of reducing false conflicts without impacting concurrency adversely. A fine grained granularity while improving concurrency can have an adverse impact on performance due to lock aliasing, lock validation overheads, and additional cache pressure. On the other hand, a coarse grained granularity can impact performance due to reduced concurrency. Thus, in general, a fixed or uniform granularity access tracking (UGAT) scheme is application-unaware and rarely matches the access patterns of individual application or parts of an application, leading to sub-optimal performance for different parts of the application(s). In order to mitigate the disadvantages associated with UGAT scheme, we propose a Variable Granularity Access Tracking (VGAT) scheme in this paper. We propose a compiler based approach wherein the compiler uses inter-procedural whole program static analysis to select the access tracking granularity for different shared data structures of the application based on the application's data access pattern. We describe our prototype VGAT scheme, using TL2 as our STM implementation. Our experimental results reveal that VGAT-STM scheme can improve the application performance of STAMP benchmarks from 1.87% to up to 21.2%.

Reconciling transactional conflicts with compiler's help

Software transactional memory(STM) is a promising programming paradigm for shared memory multithreaded programs. While STM offers the promise of being less error-prone and more programmer friendly compared to traditional lock-based synchronization, it also needs to be competitive in performance in order for it to be adopted in mainstream software. A major source of performance overheads in STM is transactional aborts. Conflict resolution and aborting a transaction typically happens at the transaction level which has the advantage that it is automatic and application agnostic. However it has a substantial disadvantage in that STM declares the entire transaction as conflicting and hence aborts it and re-executes it fully, instead of partially re-executing only those part(s) of the transaction, which have been affected due to the conflict. This "Re-execute Everything" approach has a significant adverse impact on STM performance. In order to mitigate the abort overheads, we propose a compiler aided Selective Reconciliation STM (SR-STM) scheme, wherein certain transactional conflicts can be reconciled by performing partial re-execution of the transaction. Ours is a selective hybrid approach which uses compiler analysis to identify those data accesses which are legal and profitable candidates for reconciliation and applies partial re-execution only to these candidates selectively while other conflicting data accesses are handled by the default STM approach of abort and full re-execution. We describe the compiler analysis and code transformations required for supporting selective reconciliation. We find that SR-STM is effective in reducing the transactional abort overheads by improving the performance for a set of five STAMP benchmarks by 12.58% on an average and up to 22.34%.

Analyzing Cache Performance Bottlenecks of STM Applications and addressing them with Compiler's help

Software transactional memory (STM) is a promising programming paradigm for shared memory multithreaded programs as an alternative to traditional lock based synchronization. However adoption of STM in mainstream software has been quite low due to its considerable overheads and its poor cache/memory performance. In this paper, we perform a detailed study of the cache behavior of STM applications and quantify the impact of different STM factors on the cache misses experienced by the applications. Based on our analysis, we propose a compiler driven Lock-Data Colocation (LDC), targeted at reducing the cache overheads on STM. We show that LDC is effective in improving the cache behavior of STM applications by reducing the dcache miss latency and improving execution time performance.

Making STMs Cache Friendly with Compiler Transformations

Software transactional memory (STM) is a promising programming paradigm for shared memory multithreaded programs. In order for STMs to be adopted widely for performance critical software, understanding and improving the cache performance of applications running on STM becomes increasingly crucial, as the performance gap between processor and memory continues to grow. In this paper, we present the most detailed experimental evaluation to date, of the cache behavior of STM applications and quantify the impact of the different STM factors on the cache misses experienced by the applications. We find that STMs are not cache friendly, with the data cache stall cycles contributing to more than 50% of the execution cycles in a majority of the benchmarks. We find that on an average, misses occurring inside the STM account for 62% of total data cache miss latency cycles experienced by the applications and the cache performance is impacted adversely due to certain inherent characteristics of the STM itself. The above observations motivate us to propose a set of specific compiler transformations targeted at making the STMs cache friendly. We find that STM's fine grained and application unaware locking is a major contributor to its poor cache behavior. Hence we propose selective Lock Data co-location (LDC) and Redundant Lock Access Removal (RLAR) to address the lock access misses. We find that even transactions that are completely disjoint access parallel, suffer from costly coherence misses caused by the centralized global time stamp updates and hence we propose the Selective Per-Partition Time Stamp (SPTS) transformation to address this. We show that our transformations are effective in improving the cache behavior of STM applications by reducing the data cache miss latency by 20.15% to 37.14% and improving execution time by 18.32% to 33.12% in five of the 8 STAMP applications.

Structural basis for the function of anti-idiotypic antibody in immune memory

We had earlier proposed a hypothesis to explain the mechanism of perpetuation of immunological memory based on the operation of idiotypic network in the complete absence of antigen. Experimental evidences were provided for memory maintenance through anti-idiotypic antibody (Ab2) carrying the internal image of the antigen. In the present work, we describe a structural basis for such memory perpetuation by molecular modeling and structural analysis studies. A three-dimensional model of Ab2 was generated and the structure of the antigenic site on the hemagglutinin protein H of Rinderpest virus was modeled using the structural template of hemagglutinin protein of Measles virus. Our results show that a large portion of heavy chain containing the CDR regions of Ab2 resembles the domain of the hemagglutinin housing the epitope regions. The similarity demonstrates that an internal image of the H antigen is formed in Ab2, which provides a structural basis for functional mimicry demonstrated earlier. This work brings out the importance of the structural similarity between a domain of hemagglutinin protein to that of its corresponding Ab2. It provides evidence that Ab2 is indeed capable of functioning as surrogate antigen and provides support to earlier proposed relay hypothesis which has provided a mechanism for the maintenance of immunological memory.

Structural basis for the function of anti-idiotypic antibody in immune memory

We had earlier proposed a hypothesis to explain the mechanism of perpetuation of immunological memory based on the operation of idiotypic network in the complete absence of antigen. Experimental evidences were provided for memory maintenance through anti-idiotypic antibody (Ab(2)) carrying the internal image of the antigen. In the present work, we describe a structural basis for such memory perpetuation by molecular modeling and structural analysis studies. A three-dimensional model of Ab(2) was generated and the structure of the antigenic site on the hemagglutinin protein H of Rinderpest virus was modeled using the structural template of hemagglutinin protein of Measles virus. Our results show that a large portion of heavy chain containing the CDR regions of Ab(2) resembles the domain of the hemagglutinin housing the epitope regions. The similarity demonstrates that an internal image of the H antigen is formed in Ab(2), which provides a structural basis for functional mimicry demonstrated earlier. This work brings out the importance of the structural similarity between a domain of hemagglutinin protein to that of its corresponding Ab(2). It provides evidence that Ab(2) is indeed capable of functioning as surrogate antigen and provides support to earlier proposed relay hypothesis which has provided a mechanism for the maintenance of immunological memory.

SHAMP: An experimental shared memory multimicroprocessor system for performance evaluation of parallel algorithms

In this paper, the design and implementation of a single shared bus, shared memory multiprocessing system using Intel's single board computers is presented. The hardware configuration and the operating system developed to execute the parallel algorithms are discussed. The performance evaluation studies carried out on Image are outlined.

Comment on path integration of a quadratic action with a generalized memory

Using the promeasure technique, we give an alternative evaluation of a path integral corresponding to a quadratic action with a generalized memory.

Constitutive modeling of shape memory alloy wire with non-local rate kinetics

A constitutive modeling approach for shape memory alloy (SMA) wire by taking into account the microstructural phase inhomogeneity and the associated solid-solid phase transformation kinetics is reported in this paper. The approach is applicable to general thermomechanical loading. Characterization of various scales in the non-local rate sensitive kinetics is the main focus of this paper. Design of SMA materials and actuators not only involve an optimal exploitation of the hysteresis loops during loading-unloading, but also accounts for fatigue and training cycle identifications. For a successful design of SMA integrated actuator systems, it is essential to include the microstructural inhomogeneity effects and the loading rate dependence of the martensitic evolution, since these factors play predominant role in fatigue. In the proposed formulation, the evolution of new phase is assumed according to Weibull distribution. Fourier transformation and finite difference methods are applied to arrive at the analytical form of two important scaling parameters. The ratio of these scaling parameters is of the order of 10(6) for stress-free temperature-induced transformation and 10(4) for stress-induced transformation. These scaling parameters are used in order to study the effect of microstructural variation on the thermo-mechanical force and interface driving force. It is observed that the interface driving force is significant during the evolution. Increase in the slopes of the transformation start and end regions in the stress-strain hysteresis loop is observed for mechanical loading with higher rates.

Comment on “path integration of a quadratic action with a generalized memory

Using the promeasure technique, we give an alternative evaluation of a path integral corresponding to a quadratic action with a generalized memory.

Sensing Shape Recovery Using Conductivity Noise in Thin Films of NiTi Shape Memory Alloys

Low frequency fluctuations in the electrical resistivity, or noise, have been used as a sensitive tool to probe into the temperature driven martensite transition in dc magnetron sputtered thin films of nickel titanium shape-memory alloys. Even in the equilibrium or static case, the noise magnitude was more than nine orders of magnitude larger than conventional metallic thin films and had a characteristic dependence on temperature. We observe that the noise while the temperature is being ramped is far larger as compared to the equilibrium noise indicating the sensitivity of electrical resistivity to the nucleation and propagation of domains during the shape recovery. Further, the higher order statistics suggests the existence of long range correlations during the transition. This new characterization is based on the kinetics of disorder in the system and separate from existing techniques and can be integrated to many device applications of shape memory alloys for in-situ shape recovery sensing.

Design and evaluation of a dual-microcomputer shared memory system with a shared I/O bus

The design, implementation and evaluation are described of a dual-microcomputer system based on the concept of shared memory. Shared memory is useful for passing large blocks of data and it also provides a means to hold and work with shared data. In addition to the shared memory, a separate bus between the I/O ports of the microcomputers is provided. This bus is utilized for interprocessor synchronization. Software routines helpful in applying the dual-microcomputer system to realistic problems are presented. Performance evaluation of the system is carried out using benchmarks.

On Bit Steering in the Minimization of the Control Memory of Microprogrammed Processors

The microcommands constituting the microprogram of the control memory of a microprogrammed processor can be partitioned into a number of disjoint sets. Some of these sets are then encoded to minimize the word width of the ROM storing the microprogram. A further reduction in the width of the ROM words can be achieved by a technique known as bit steering where one or more bits are shared by two or more sets of microcommands. These sets are called the steerable sets. This correspondence presents a simple method for the detection and encoding of steerable sets. It has been shown that the concurrency matrix of two steerable sets exhibits definite patterns of clusters which can be easily recognized. A relation "connection" has been defined which helps in the detection of three-set steerability. Once steerable sets are identified, their encoding becomes a straightforward procedure following the location of the identifying clusters on the concurrency matrix or matrices.

Effect of mechanical cycling on the stress-strain response of a martensitic Nitinol shape memory alloy

An experimental investigation into the ambient temperature, load-controlled tension�tension fatigue behavior of a martensitic Nitinol shape memory alloy (SMA) was conducted. Fatigue life for several stress levels spanning the critical stress for detwinning was determined and compared with that obtained on an alloy similar in composition but in the austenitic state at room temperature. Results show that the fatigue life of the pseudo-plastic alloy is superior to superelastic shape memory alloy. The stress�strain hysteretic response, monitored throughout the fatigue loading, reveals progressive strain accumulation with the cyclic loading. In addition, the area of hysteresis and recoverable and frictional energies were found to decrease with increasing number of fatigue cycles. Post-mortem characterization of the fatigued specimens through calorimetry and fractography was conducted in order to get further insight into the fatigue micromechanisms. These results are discussed in terms of reversible and irreversible microstructural changes that take place during cyclic loading. Aspects associated with self-heating of martensitic alloy undergoing high frequency stress cycling are discussed.

Direct physical evidence for the back-transformation of stress-induced martensite in the vicinity of cracks in pseudoelastic NiTi shape memory alloys

Crack loading and crack extension in pseudoelastic binary NiTi shape memory alloy (SMA) miniature compact tension (CT) specimens with 50.7 at.% Ni (austenitic, pseudoelastic) was investigated using infrared (IR) thermography during in situ loading and unloading. IR thermographic measurements allow for the observation of heat effects associated with the stress-induced transformation of martensite from B2 to BIT during loading and the reverse transformation during unloading. The results are compared with optical images and discussed in terms of the crack growth mechanisms in pseudoelastic NiTi SMAs. Direct experimental evidence is presented which shows that crack growth occurs into a stress-induced martensitic microstructure, which immediately retransforms to austenite in the wake of the crack.