Search

In this article, we propose Failure-atomic Byte-addressable R-tree (FBR-tree) that leverages the byte-addressability, persistence, and high performance of persistent memory while guaranteeing the crash consistency. We carefully control the order of store and cacheline flush instructions and prevent any single store instruction from making an FBR-tree inconsistent and unrecoverable. We also develop a non-blocking lock-free range query algorithm for FBR-tree. Since FBR-tree allows read transactions to detect and ignore any transient inconsistent states, multiple read transactions can concurrently access tree nodes without using shared locks while other write transactions are making changes to them. Our performance study shows that FBR-tree successfully reduces the legacy logging overhead and the lock-free range query algorithm shows up to 2.6x higher query processing throughput than the shared lock-based crabbing concurrency protocol.

NOVA, a state-of-the-art non-volatile memory (NVM) file system, has limited performance due to its coarse-grained per-file lock when multiple threads perform I/Os to a shared file in a manycore environment. For instance, a writer lock blocks other threads attempting to access the same file, although they access different regions of a file. When multiple threads reading the same file share a cache line containing a reader counter, performance can be significantly degraded due to cache consistency protocol as we increase the number of readers. This paper proposes a fine-grained segment-based range lock ( SRL ) that divides a file into multiple segments and manages a lock variable dynamically for each segment. Consequently, write operations can be parallelized without blocking unless there is a conflict in accessing the same range in a file. Moreover, SRL maintains a reader counter per segment that allows multiple reader threads to perform read operations without causing a performance bottleneck. We evaluated an SRL -based NOVA on an Intel Optane DC persistent memory (PM) manycore server. The benchmarking results showed that the average write throughput of the SRL -based NOVA is $3\times $ higher than the original NOVA, and the average read throughput scales linearly, while the original NOVA does not scale.

The e-commerce business process net (EBPN) is a novel formal model for describing an e-commerce system and its interactive parts, such as shoppers, merchants, and the third-party payment platforms. Vulnerability analysis has a great impact on the trustworthiness of EBPN, which is an issue stemming from data inconsistency problems. Data inconsistency problems affect the consistency of the EBPN transaction analysis. The underlying causes of inconsistent data are closely related to concurrent operations, such as control flow and data flow. However, most of the existing detection methods have difficulties characterizing the vulnerabilities and interactions of control and data flows. In this paper, we propose a new method based on the dynamic data slice (DDS) that considers both transaction consistency and data state consistency. First, by analyzing control flow characteristics of EBPN, we obtain the dynamic slice. This dynamic slice is based on all paths of the EBPN reachability graph. Second, we perform the data inconsistency analysis by considering both transaction consistency and data-state consistency. Based on these, we construct a DDS to characterize the behavioral logic and the data-dependence information. The DDS acquires the dynamic data firing sequence. Based on that sequence and a given data marking, we can construct the DDSs for several types of EBPNs. Constructing the DDS can be completed in polynomial time. The DDS is designed to characterize the behavioral logic and data-dependence information. Based on these, we design a method to judge the data constraints. This method satisfies the EBPN need for transaction consistency by considering both the control and data states. In addition, according to the data-dependence information, we can lock the vulnerable regions caused by abnormal trading data in the system. Finally, we give a method to compute the vulnerability level.

In this paper, the current limiting and the interrupting operations of the flux-lock type superconducting fault current limiting interrupter (SFCLI) using the mechanical switch (MS), which could be driven without additional driving power source, were analyzed. The operational principle of the suggested SFCLI is the same as one, except that the MS performs the fault current interrupting operation, driven by the electromagnetic repulsion force generated within the driving coil without the additional driving power source. Furthermore, the interrupting operation of the MS directly, after the current limiting operation of this SFCLI, can contribute to the improvement of the previous SFCL's performance. To verify the operational characteristics of the suggested SFCLI, the MS with the fixed plate (FP) and the moving plate (MP), which were located just above open round bobbin wound by the driving coil, was designed and manufactured. The short-circuit tests of the SFCLI using MS were carried out. Through the analysis on the results of the short-circuit tests, the current limiting and interrupting operations of the flux-lock type SFCLI using the MS could be confirmed to be effectively performed without the additional driving power source.

As more emerging applications are moving to GPUs, thread-level synchronization has become a requirement. However, GPUs only provide warp-level and thread-block-level rather than thread-level synchronization. Moreover, it is highly possible to cause live-locks by using CPU synchronization mechanisms to implement thread-level synchronization for GPUs. In this article, we first propose a software-based thread-level synchronization mechanism called lock stealing for GPUs to avoid live-locks. We then describe how to implement our lock stealing algorithm in mutual exclusive locks and readers-writer locks with high performance. Finally, by putting it all together, we develop a thread-level locking library (TLLL) for commercial GPUs. To evaluate TLLL and show its general applicability, we use it to implement six widely used programs. We compare TLLL against the state-of-the-art ad-hoc GPU synchronization, GPU software transactional memory (STM), and CPU hardware transactional memory (HTM), respectively. The results show that, compared with the ad-hoc GPU synchronization for Delaunay mesh refinement (DMR), TLLL improves the performance by 22 percent on average on a GTX970 GPU, and shows up to 11 percent of performance improvement on a Volta V100 GPU. Moreover, it significantly reduces the required memory size. Such low memory consumption enables DMR to successfully run on the GTX970 GPU with the 10-million mesh size, and the V100 GPU with the 40-million mesh size, with which the ad-hoc synchronization can not run successfully. In addition, TLLL outperforms the GPU STM by 65 percent, and the CPU HTM (running on a Xeon E5-2620 v4 CPU with 16 hardware threads) by 43 percent on average.

Implementation of concurrent data structures in architectures that provide limited synchronization primitives is a critical challenge. Typical lock-based implementations suffer from well-known problems such as poor scalability and unfairness. In this paper, we propose a client-server based synchronization model that can be applied in data structures with low level of parallelism for distributed shared memory many-core systems that support also message-passing communication. Additionally, we utilize a programmable hardware accelerator with appropriate application interfaces to overcome the performance-flexibility dilemma. Experimental results show that the proposed work performs 20 $\times$ faster than the single lock model with 88 $\times$ less idle cycles and 7 $\times$ less power consumption.

Developers of parallel programming are faced with choices of using various Java locks. Choosing the best lock is a challenging task because a multithreaded application implemented using different locks may end up with uncertain performance. There is a strong need for automated tool support that helps Java programmers choose the best lock for each specific application. This paper presents an automated transformation approach to convert an implementation using a synchronized lock to a ReentrantLock or a ReentrantReadWriteLock at the bytecode level. For the ReentrantLock, our approach runs analysis for global monitors using the visitor pattern in the Joeq compiler. For the ReentrantReadWriteLock, a read or write lock is chosen after a side-effect analysis. Then, the proposed system validates the consistency of the analysis results to ensure a correct sequence of lock usage. Finally, lock operations and related thread communication operations are transformed into a ReentrantLock or a ReentrantReadWriteLock using a bytecode transformation framework Javassist. We validate our approach on several benchmarks including RBTree, PC, SPECjbb2005, and HSQLDB. The experimental results show that the proposed automated transformation approach can transform these benchmarks successfully in a timely fashion.

Most of dynamic data race detection essentially relies on the underlying happens-before orders to yield the precise reports. They are notoriously prone to a prohibitively basic overhead. Although there exist a wealth of research advances that succeed in significantly reducing the analysis overhead on memory accesses, there remains an open problem in handling a great deal of fundamentally unscalable synchronization overhead, which can be particularly serious for the large, lock-intensive programs with a long running time and a large number of threads. In this paper, we revisit the synchronization problem of off-the-shelf race detection with a comprehensive study. The key insight of this work is that a full collection of partial orders for synchronization operations in prior work is not necessarily tracked and analyzed from a new perspective of “global clock” representation. We therefore develop this insight into a novel pending-period based approach, aiming at reducing the overhead of monitoring and analysis on unnecessary synchronization operations. Further, we also enable a significant improvement for enhancing the efficiency of existing sampling techniques, in which synchronization operations are often conservatively identified. Our experimental results on a wide variety of programs show that our approach outperforms state-of-the-art by 5.85x (versus FastTrack), 3.51x (versus ThreadSanitizer) and 1.34x (versus IFRit) program execution slowdown improvement on average, which can be more significant as the number of threads is increasing. Particularly for the lock-intensive programs (e.g., barnes ), our approach can be 26.04x faster than FastTrack. Further, our pending period extended sampling is more efficient than Pacer (with up to 31.28 percent improvement in the case of 10 percent sampling rate).

With increasingly complex cyber attacks occurring every day, memory-based forensic techniques are becoming instrumental in digital investigations. Forensic examiners can unravel what happened on a system by acquiring and inspecting in-memory data. However, the foundation of this analysis can be invalidated if the memory acquisition has been altered. In this paper, we study the feasibility of malicious software misusing architectural features to sabotage memory forensics. The misuse of two architectural features, namely, physical address layout and secure containers, is presented. The first architectural feature explored in this paper is the physical address layout. It is used by the northbridge to route memory access to either physical memory or I/O devices on x86 platforms. Observing this design choice, we propose Hidden in I/O Space (HIveS), which manipulates CPU registers to alter the physical address layout to conceal memory. The system uses a novel I/O shadowing technique to lock a memory region named HIveS memory into I/O address space to prevent access. Two novel techniques, blackbox write and TLB camouflage , are developed to further protect the unlocked HIveS memory against memory forensics while allowing access for attackers. The second architectural feature explored in this paper is hardware-aided secure execution technology. More specifically, hardware-enforced memory encryption in Intel secure guard extension is used in malicious enclave software (Malclaveware) to prevent introspection and memory forensics. A prototype of HIveS is built and tested against a set of memory acquisition tools for both Windows and Linux running on the x86 platform. Malclaveware is also prototyped in Windows to demonstrate the risk. More importantly, we proposed countermeasures and mitigations for the newly discovered attacks. Through these discussions, we aim to raise the awareness of the potential risks of misusing hardware architectural features.

Due to the rapid proliferation of sensors and intelligent devices, the cyber-physical-social computing and networking (CPSCN) is emerging as a new computing paradigm. Massive data have been generated in the CPSCN environment. The traditional data deduplication is not able to handle the CPSCN environment due to the involved long latency. This paper presents a low latency in-line data deduplication file system (LDFS). The LDFS decouples the unique data block and fingerprint index by writing the address of data blocks to the corresponding file recipe and fingerprint index, thus avoiding accessing fingerprint index on the path of the read operation. For every unique data block, the LDFS assigns a globally unique ID, and thus, the LDFS only requires one disk access to obtain the corresponding data block reference count using the global ID. In order to guarantee the write performance, the LDFS employs finer granularity lock to optimize the block flushing strategy of write buffer. Experimental results demonstrate that the LDFS significantly enhances the read and write performance on the critical path in contrast to the traditional deduplication file system LessFS. Meanwhile, the LDFS achieves almost the same deduplication ratio (40.8) as that of LessFS.

As the many-core processors become more prevalent, the parallelism degree of applications is rapidly increasing. It is well known that multi-thread approaches are an effective solution to improve performance by exploiting multiple cores. However, the synchronization problem that occurs between multiple threads can limit the concurrency and scalability of applications. Hardware transactional memory (HTM) has been studied to simplify the synchronization problem, and Intel adopted transactional synchronization extensions (TSX) for its processors in the year 2012. TSX can dynamically decide and perform instructions as an atomic transaction. In this paper, we evaluate and analyze the performance of TSX. It is expected that the latest technology implementing HTM to cope with synchronization scalability will be a nice solution for handling the high degree of parallelism. We found two major reasons that cause performance degradation and propose a novel approach to address these more effectively based on our analysis. We also introduced a mechanism, named ParaTM, to transparently adopt TSX for existing lock-based applications. By using ParaTM, one can apply TSX features without modification of the code. From our evaluation using a micro-benchmark and real-world applications, we confirmed ParaTM is highly effective for transparency and performance. ParaTM achieved 1.75 $\times$ , 4.76 $\times$ , and 1.53 $\times$ better performance compared to the traditional lock mechanism for LevelDB, RocksDB, and Memcached, respectively.

The critical sections with the lock protection greatly limit the concurrency of multi-threaded applications. The prior lock elision based technique is presented to exploit the parallelism between critical sections accessing the disjoint shared data, but still fails to notice and expose a high degree of concurrency between critical sections that contend for the same shared data, i.e., conflicting critical sections (CCS). This paper focuses on exploiting the CCS parallelism. The key insight of this work is that, for each running CCS, a large proportion ( $>$ 73.4%) of parallelism between CCSs can be exploited as fully as possible by simply allowing the parallel execution of their first conflict-free code fragment at runtime. We therefore present BSOptimizer, a new microarchitecture, to perform the partial reversion integrated with a series of sophisticated hardware and software strategies for the CCS parallelization. We complement the off-the-shelf cache coherency protocol to perceive the conflict location of CCS, present a predictive checkpoint mechanism to register and predict the concerned conflict point in a lightweight and accurate fashion, and redefine the traditional mutual exclusive semantics with a binary relationship. With these collaborative techniques, each CCS can be scheduled in parallel. Our experimental results on a wide variety of real programs and PARSEC benchmarks show that, compared to the native execution and two state-of-the-art lock elision techniques (including SLE and SLR), BSOptmizer can dramatically improves the performance of programs with a slight ( $ 0.8%) energy consumption and ( $ 3.9%) extra runtime overhead. Our evaluation on a micro-benchmark with software based optimization also verifies that BSOptimizer can accurately exploit the CCS parallelism as promised.

Due to the high complexity in software hierarchy and the shared queue & lock mechanism for synchronized access, existing I/O stack for accessing the FCoE based SAN storage becomes a performance bottleneck, thus leading to a high I/O overhead and limited scalability in multi-core servers. In order to address this performance bottleneck, we propose a synergetic and efficient solution that consists of three optimization strategies for accessing the FCoE based SAN storage: (1) We use private per-CPU structures and disabling kernel preemption method to process I/Os, which significantly improves the performance of parallel I/O in multi-core servers; (2) We directly map the requests from the block-layer to the FCoE frames, which efficiently translates I/O requests into network messages; (3) We adopt a low latency I/O completion scheme, which substantially reduces the I/O completion latency. We have implemented a prototype (called FastFCoE, a protocol stack for accessing the FCoE based SAN storage). Experimental results demonstrate that FastFCoE achieves efficient and scalable I/O throughput, obtaining 1132.1K/836K IOPS (6.6/5.4 times as much as original Linux Open-FCoE stack) for read/write requests.

IBM and Intel now offer commercial systems with Transactional Memory (TM), a programming paradigm whose aim is to facilitate concurrent programming while maximizing parallelism. These TM systems are implemented in hardware and provide a software fallback path to overcome the hardware implementation limitations. They are known as best-effort hardware TM (BE-HTM) systems. The software fallback path must be provided by the user to ensure forward progress, which adds programming complexity to the TM paradigm. We propose a new type of irrevocability (a transactional mode that marks transactions as non-abortable) to deal with BE-HTM limitations in a more efficient manner, and to liberate the user from having to program a fallback path. It is based on the concept of lazy subscription used in the context of software fallback paths, where the fallback lock is checked at the end of the transaction instead of at the beginning. We propose a hardware lazy irrevocability mechanism that does not involve changes in the coherence protocol. It solves the unsafe execution problem of premature commits associated with lazy subscription fallbacks, and can be triggered by the user via an ISA extension, for the sake of versatility. It is compared with its software counterpart, which we propose as an enhanced lazy single global lock with escaped spinning at the end of the transaction. We also propose the lazy irrevocability with anticipation, a mechanism that cannot be implemented in software, which significantly improves the performance of codes with multiple cache evictions of transactional data. The evaluation of the proposals is carried out with the Simics/GEMS simulator along with the STAMP benchmark suite, and we obtain speedups from 14 to 28 percent over the fallback path approaches.

Spin-locks are widely used in software for efficient synchronization. However, they cause serious performance degradation on virtualized platforms, such as the Lock Holder Preemption (LHP) problem and the Lock Waiter Preemption (LWP) problem, due to excessive spinning by virtual CPUs (VCPUs). The excessive spinning occurs when a VCPU waits to acquire a spin-lock. To address the performance degradation, hardware facilities, such as Intel PLE and AMD PF, are provided on processors to preempt VCPUs when they spin excessively. Although these facilities have been predominantly used on mainstream virtualization systems, using them in a manner that achieves the highest performance is still a challenging issue. There are two core problems in using these hardware facilities to reduce excessive spinning. One is to determine the best time to preempt a spinning VCPU (i.e., the selection of spinning thresholds). The other is which VCPU should be scheduled to run after the spinning VCPU is descheduled. Due to the semantic gap between different software layers, the virtual machine monitor (VMM) does not have information about the computation characteristics on VCPUs, which is needed to address the above problems. This makes the problems inherently challenging. We propose a framework named AdPtive Pause-Loop Exiting and Scheduling (APPLES) to address these problems. APPLES monitors the overhead caused by excessive spinning and preempting spinning VCPUs, and periodically adjusts spinning thresholds to reduce the overhead. APPLES also evaluates and schedules “ready” VCPUs in a VM by their potential to reduce the spinning incurred by the spin-lock synchronization. The evaluation is based on the causality and the time of VCPU preemptions. The implementation of APPLES incurs only minimal changes to existing systems (about 100 lines of code in KVM). Experiments show that APPLES can improve performance by 3 $\sim$ 49 percent (14 percent on average) for the workloads with frequent spin-lock operations.

Scalable locking is a key building block for scalable multi-threaded software. Its performance is especially critical in multi-socket, multi-core machines with non-uniform memory access (NUMA). Previous schemes such as in-place locks and delegation locks only perform well under a certain level of contention, and often require non-trivial tuning for a particular configuration. Besides, in large NUMA systems, current delegation locks cannot perform satisfactorily due to lack of optimized NUMA policies. In this work, we propose SANL , a locking scheme that can deliver high performance under various contention levels by adaptively switching between in-place locks and delegation locks. To optimize the performance of delegation locks, we introduce a new NUMA policy that jointly considers node distances and server utilization when choosing lock servers. We have implemented SANL and evaluated it with four popular multi-threaded applications (Memcached, Berkeley DB, Phoenix2 and SPLASH-2), on a 40-core Intel machine and a 64-core AMD machine. The comparison results with seven other representative locking schemes show that SANL outperforms them in most contention situations. For example, in one group test, SANL is 3.7 times faster than RCL lock and 17 times faster than POSIX mutex.

Recently, field-programmable gate array (FPGA) vendors (such as Altera) have started to address the programmability issues of FPGAs via OpenCL SDKs. In this paper, we analyze the performance of relational database applications on FPGAs using OpenCL. In particular, we study how to improve the performance of data partitioning, which is a very important building block in relational database. Since the data partitioning causes random memory accesses, it is time-consuming, and then, it has been the major bottleneck for database operators, such as partitioned hash join. In particular, we import the state-of-the-art OpenCL implementation of data partitioning from OmniDB, which was originally designed and optimized for CPUs/GPUs, and we find that this implementation suffers from both lock overhead and memory bandwidth overhead. Accordingly, we present a multikernel approach to address the lock overhead by leveraging two emerging features ( task kernel and channel ) from Altera OpenCL software development kit. In order to reduce the memory bandwidth overhead, on-chip buckets are used to reduce the number of random global memory transactions. We further develop an FPGA-specific cost model to guide the parameter configuration. We evaluate the proposed design on a recent OpenCL-based FPGA. We have applied our optimized partitioning method to a number of data processing tasks, including hash join, histogram, and hash search. Our experimental results demonstrate that our cost model can accurately guide the user to determine the optimal parameter combination for data partitioning and the optimal parameter combination can achieve $16.6\times$ speedup over the default multithreaded implementation.

In high-end data processing systems, such as databases, the execution concurrency level rises continuously since the introduction of multicore processors. This happens both on premises and in the cloud. For these systems, a buffer pool management of high scalability plays an important role on overall system performance. The scalability of buffer pool management is largely determined by its data replacement algorithm, which is a major component in the buffer pool management. It can seriously degrade the scalability if not designed and implemented properly. The root cause is its use of lock-protected data structures that incurs high contention with concurrent accesses. A common practice is to modify the replacement algorithm to reduce the contention on the lock(s), such as approximating the LRU replacement with the CLOCK algorithm or partitioning the data structures and using distributed locks. Unfortunately, the modification usually compromises the algorithm's hit ratio, a major performance goal. It may also involve significant effort on overhauling the original algorithm design and implementation. This paper provides a general solution to improve the scalability of a buffer pool management using any replacement algorithms for the data processing systems on physical on-premises machines and virtual machines in the cloud. Instead of making a difficult trade-off between the high hit ratio of a replacement algorithm and the low lock contention of its approximation, we design a system framework, called BP-Wrapper , that eliminates almost all lock contention without requiring any changes to an existing algorithm. In BP-Wrapper, we use a dynamic batching technique and a prefetching technique to reduce lock contention and to retain high hit ratio. The implementation of BP-Wrapper in PostgreSQL adds only about 300 lines of C code. It can increase the throughput by up to two folds compared with the replacement algorithms with lock contention when running TPC-C-like and TPC-W-like workloads.

Software Transactional Memory (STM) has recently emerged as a promising synchronization abstraction for multicore architectures. State-of-the-art STM algorithms, however, suffer from performance challenges due to contention and spinning on locks during the transaction commit phase. In this paper, we introduce Remote Transaction Commit (or RTC), a mechanism for executing commit phases of STM transactions. RTC dedicates server cores to execute transactional commit phases on behalf of application threads. This approach has two major benefits. First, it decreases the overheads of spinning on locks during commit, such as the number of cache misses, blocking of lock holders, and CAS operations. Second, it enables exploiting the benefits of coarse-grained locking algorithms (simple and fast lock acquisition, reduced false conflicts) and bloom filter-based algorithms (concurrent execution of independent transactions). Our experimental study on a 64-core machine with four sockets shows that RTC solves the problem of performance degradation due to spin locking on both micro-benchmarks (red-black trees), and macro-benchmarks (STAMP), especially when the commit phase is relatively long and when thread contention increases.

Locks have been widely used as an effective synchronization mechanism among processes and threads. However, we observe that, a large number of false inter-thread dependencies (i.e., unnecessary lock contentions) exist during the program execution on multicore processors, incurring significant performance overhead. This paper presents a performance debugging framework, PerfPlay , to facilitate the identification of unnecessary lock contentions and to guide programmers to improve the program performance by eliminating the unnecessary lock contentions. Since the performance debugging of unnecessary lock contentions is input-sensitive, we first identify the representative inputs for performance debugging. Next, PerfPlay quantifies the performance impact of unnecessary lock contention code regions for each candidate input. Taking into account conflicting attribute of performance impact and input coverage in the real world, we finally make the tradeoff between performance impact and input coverage to recommend the optimal unnecessary lock contention code regions. Our final results on five real-world programs and PARSEC benchmarks demonstrate the significant performance overhead of unnecessary lock contentions, and the effectiveness of PerfPlay in troubleshooting the target unnecessary lock contention code regions with the consideration of both performance impact and input coverage.

In multiprocessor systems, low-latency synchronization is extremely important to effectively exploit fine-grain data parallelism and improve overall performance. This brief presents an efficient synchronization for embedded distributed multiprocessors. The proposed solution works in a completely decentralized request–response manner via explicit message exchange among the processing elements. Scalable lock and barrier synchronization algorithms, which are derived from the inherent distributed characteristics of the underlying architecture, are proposed to enable fair, orderly, and contention-free synchronization. We implement the proposed synchronization model in a distributed 32-core architecture with a commercial cycle-accurate SystemC simulation platform. Experimental results that show our proposed approach achieves ultralow synchronization latency and almost ideal scalability when the core count scales.

Modern transactional processing systems need to be fast and scalable, but this means many such systems settled for weak consistency models. It is however possible to achieve all of strong consistency, high scalability and high performance, by using fine-grained partitions and light-weight concurrency control that avoids superfluous synchronization and other overheads such as lock management. Independent transactions are one such mechanism, that rely on good partitions and appropriately defined transactions. On the downside, it is not usually straightforward to determine optimal partitioning schemes, especially when dealing with non-trivial amounts of data. Our work attempts to solve this problem by automating the partitioning process, choosing the correct transactional primitive, and routing transactions appropriately.

The SPARC M7 processor offers up to 3 $\times$ the throughput performance of Oracle's previous SPARC processor generation for many enterprise workloads. It contains 32 highly optimized S4 cores that include a more efficient L2 cache scheme, support for VIS extensions, virtual address masking, and user-level synchronization instructions to provide substantial single thread performance over the predecessor design. A total of 256 threads per chip provide the throughput performance required by even the most demanding enterprise applications. Both throughput and single thread performance benefit from a large fully shared 64 MB on-chip L3 cache with very low latency. The 0.5 TB/s on-chip communications bandwidth requirements are served via a semi-custom on-chip network (OCN) in place of the traditional crossbar. Hardware database analytics accelerator units (DAX) achieve up to 10 $\times$ the performance for in-memory database queries, include decompression and messaging operations, and support pointer version checking for securing application data through application data integrity (ADI), as well as fine grained memory migration. The SerDes IO operate up to 18 Gbps, offering 1 TB/s total bandwidth for memory and multi-socket interfaces. New on-chip power management features include fast and accurate dynamic power meters, thermal sensors, and a fine-grain thermal, current, and chip power control engine to enable maximum performance/Watt. Special circuits like the voltage shift module (VSM) were developed to cope with the clock and voltage domain crossing issues, while the asymmetric frequency lock loop (AFLL) main clock generation circuit also provides Ldi/dt droop compensation leading to substantial power savings.

We present a new buddy system for memory allocation that we call the lazy iBuddy system. This system is motivated by two observations of the widely used lazy buddy system on multi-core systems. First, most memory requests are for single page frames. However, the lazy buddy algorithm used in Linux continuously splits and coalesces memory blocks for single page frame requests even though the lazy layer is employed. Second, on multi-core systems, responses to bursty memory requests are delayed by lock contention caused by concurrent accesses of the multi-cores. The lazy iBuddy system overcomes the first problem by managing each page frame individually and coalescing pages only when an allocation of multiple page frames is requested. We devise the lazy iBuddy algorithm so that single page frame allocation can be done in O(1). The second problem is alleviated by dividing main memory into multiple buddy spaces and applying a fine-grained locking mechanism. Performance evaluation results based on various workloads on the XEON 16core with 32 GB main memory show that the lazy iBuddy system can improve memory allocation/deallocation time by up to 47 percent with an average of 35 percent compared with the lazy buddy system for the various configurations that we considered.

Spin lock contention in operating systems can limit scalability on multicore systems so significantly that an increase in the number of cores actually leads to reduced speedup (i.e., scalability collapse). Modeling spin lock contention is an effective way to understand the scalability collapse phenomenon and explore collapse avoidance schemes. However, previous spin lock models have disadvantages in accuracy and efficiency. To overcome these drawbacks, this paper proposes LockSim, an event-driven simulator which models both the sequential execution in lock-protected codes (i.e., critical sections) and shared hardware resource contention caused by the cache coherence protocol. Our simulator is verified against real-world workloads with different degrees of spin lock contention. Experimental results suggest that LockSim can reproduce the scalability collapse phenomenon with better accuracy than previous work. Besides, several metrics are also used to characterize this phenomenon and collapse avoidance methods are investigated.

In response to the increasing ubiquity of multicore processors, applications are usually designed or deployed to make each core busy. Unfortunately, lock contention within operating systems can limit the scalability of multicore systems so severely that an increase in the number of cores can actually lead to reduced performance (i.e., scalability collapse). Existing lock implementations have disadvantages in scalability, power consumption, and energy efficiency. In this paper, we observe that the number of tasks requesting a lock has a significant correlation with the occurrence of scalability collapse. Based on this observation, a lock implementation that allows tasks waiting for a lock to either spin or enter a power-saving state based on the number of requesters is proposed. Our lock protocol is called requester-based lock and is implemented in the Linux kernel to replace its default spin lock. Based on the results of a sensitivity analysis, we find that the best policy, in practice, for a task waiting for a lock to be granted is to enter the power-saving state immediately after noticing the lock cannot be acquired. Our requester-based lock scheme is evaluated using intensive benchmarking on AMD 32-core and Intel 40-core systems. Experimental results suggest that our lock avoids scalability collapse completely for most applications and shows better scalability, power consumption, and energy efficiency than previous work. Besides, the requester-based lock is extensible, which means using together with other kinds of spin locks can provide better scalability and energy efficiency.

Data synchronization among multiple cores has been one of the critical issues which must be resolved in order to optimize the parallelism of multicore architectures. Data synchronization schemes can be classified as lock-based methods (“pessimistic”) and lock-free methods (“optimistic”). However, none of these methods consider the nature of embedded systems which have demanding and sometimes conflicting requirements not only for high performance, but also for low power consumption. As an answer to these problems, we propose $C\!\!- \!\! Lock$ , an energy- and performance-efficient data synchronization method for multicore embedded systems. $C\!\!- \!\! Lock$ achieves balanced energy- and performance-efficiency by combining the advantages of lock-based methods and transactional memory (TM) approaches; in $C\!\!- \!\! Lock$ , the core is blocked only when true conflicts exist (advantage of TM), while avoiding roll-back operations which can cause huge overhead with regard to both performance and energy (this is an advantage of locks). Also, in order to save more energy, $C\!\!- \!\! Lock$ disables the clocks of the cores which are blocked for the access to the shared data until the shared data become available. We compared our $C\!\!- \!\! Lock$ approach against traditional locks and transactional memory systems and found that $C\!\!- \!\! Lock$ can reduce the energy-delay product by up to 1.94 times and 13.78 times compared to the baseline and TM, respectively.

In this paper, a flux-lock-type superconducting fault current limiter (SFCL) with the uninterruptible power supplying (UPS) function during the fault period was suggested. The structure of the suggested flux-lock-type SFCL is the same as one of the conventional flux-lock-type SFCLs using magnetic coupling of two coils except for the third winding and two power switches. The third winding is wound on the same iron core as two coils of the flux-lock-type SFCL are wound, and two power switches are connected with the third winding and the load, required for the uninterruptible power supply, respectively. To investigate the operational characteristics of the suggested flux-lock-type SFCL with the UPS function, the short-circuit tests were carried out. Through the analysis for the experimental results, the fault current limiting and the UPS operations of the flux-lock-type SFCL could be confirmed to be performed through the proper design of the suggested flux-lock-type SFCL.

Recent research in disciplined shared-memory programming models presents a unique opportunity for rethinking the multicore memory hierarchy for better efficiency in terms of complexity, performance, and energy. The DeNovo hardware system showed that for deterministic programs written using such disciplined models, hardware can be much more efficient than the current state of the art. For DeNovo to be adopted by commercial systems, however, it is necessary to extend it to support nondeterministic applications as well; for example, applications using lock synchronization. This article proposes DeNovoND, a system that provides support for disciplined nondeterministic codes with locks while retaining the simplicity, performance, and energy benefits of DeNovo. The authors designed and implemented simple memory consistency semantics for safe nondeterminism using distributed queue-based locks and access signatures. The resulting protocol avoids transient states, invalidation traffic, directory sharer-lists, and false sharing, which are all significant sources of inefficiency in existing protocols. Their experiments showed that DeNovoND provides comparable or better execution time for applications designed for lock synchronization. In addition, it incurs 33 percent less network traffic on average relative to a state-of-the-art invalidation-based protocol, which directly translates into energy savings.

We present Magiclock, a novel potential deadlock detection technique by analyzing execution traces (containing no deadlock occurrence) of large-scale multithreaded programs. Magiclock iteratively eliminates removable lock dependencies before potential deadlock localization. It divides lock dependencies into thread specific partitions, consolidates equivalent lock dependencies, and searches over the set of lock dependency chains without the need to examine any duplicated permutations of the same lock dependency chains. We validate Magiclock through a suite of real-world, large-scale multithreaded programs. The experimental results show that Magiclock is significantly more scalable and efficient than existing dynamic detectors in analyzing and detecting potential deadlocks in execution traces of large-scale multithreaded programs.

Many happened-before-based detectors for debugging multithreaded programs implement vector clocks to incrementally track the casual relations among synchronization events produced by concurrent threads and generate trace logs. They update the vector clocks via vector-based comparison and content assignment in every case. We observe that many such tracking comparison and assignment operations are removable in part or in whole, which if identified and used properly, have the potential to reduce the log traces thus produced. This paper presents our analysis to identify such removable tracking operations and shows how they could be used to reduce log traces. We implement our analysis result as a technique entitled LOFT. We evaluate LOFT on the well-studied PARSEC benchmarking suite and five large-scale real-world applications. The main experimental result shows that on average, LOFT identifies 63.9 percent of all synchronization operations incurred by the existing approach as removable and does not compromise the efficiency of the latter.

GPU application implementations using scatter approaches will fall into write contention due to atomic updates of output elements, if these result from more than one input element. Colliding threads will be serialized, seriously harming performance. Dealing with these issues requires a proper understanding of the behavior of the scratchpad or shared memory under conflicting accesses caused by concurrent threads. Thus, this paper presents an exhaustive microbenchmark-based analysis of atomic additions in shared memory that quantifies the impact of access conflicts on latency and throughput. This analysis has led us to discover the lock mechanism that enables atomic updates to shared memory and to propose a performance model to estimate the latency penalties due to collisions by position or bank conflicts. Then, we have derived experiments from this model that show us the way to optimize applications using atomic operations. Position and bank conflicts can be diminished by replication and padding, respectively. The benefits of such techniques are illustrated with the optimization of two widely used voting processes: the centroid updating step in k-means clustering, and histogram calculation.

Massively parallel applications often require periodic data checkpointing for program restart and post-run data analysis. Although high performance computing systems provide massive parallelism and computing power to fulfill the crucial requirements of the scientific applications, the I/O tasks of high-end applications do not scale. Strict data consistency semantics adopted from traditional file systems are inadequate for homogeneous parallel computing platforms. For high performance parallel applications independent I/O is critical, particularly if checkpointing data are dynamically created or irregularly partitioned. In particular, parallel programs generating a large number of unrelated I/O accesses on large-scale systems often face serious I/O serializations introduced by lock contention and conflicts at file system layer. As these applications may not be able to utilize the I/O optimizations requiring process synchronization, they pose a great challenge for parallel I/O architecture and software designs. We propose an I/O mechanism to bridge the gap between scientific applications and parallel storage systems. A static file domain partitioning method is developed to align the I/O requests and produce a client-server mapping that minimizes the file lock acquisition costs and eliminates the lock contention. Our performance evaluations of production application I/O kernels demonstrate scalable performance and achieve high I/O bandwidths.

The performance and scalability issues of multithreaded Java programs on multicore systems are studied in this paper. First, we examine the performance scaling of benchmarks with various numbers of processor cores and application threads. Second, by correlating low-level hardware performance data to JVM threads and system components, the detail analyses of performance and scalability are presented, such as the hardware stall events and memory system latencies. Third, the usages of memory resource are detailed to observe the potential bottlenecks. Finally, the JVM tuning techniques are proposed to alleviate the bottlenecks, and improve the performance and scalability. Several key findings are revealed through this study. First, the lock contentions usually lead to a strong limitation of scalability. Second, in terms of memory access latencies, the most of memory stalls are produced by L2 cache misses and cache-to-cache transfers. Finally, the overhead of minor garbage collections could be an important factor of throughput reductions. Based on these findings, the appropriate Java Virtual Machine (JVM) tuning techniques are examined in this study. We observe that the use of a parallel garbage collector and an appropriate ratio of young to old generation can alleviate the overhead of minor collection and improve the efficiency of garbage collections. Moreover, the cache utilizations could be enhanced with the use of thread-local allocation buffer, and then leads to the performance improvements significantly.

MPI collective I/O has been an effective method for parallel shared-file access and maintaining the canonical orders of structured data in files. Its implementation commonly uses a two-phase I/O strategy that partitions a file into disjoint file domains, assigns each domain to a unique process, redistributes the I/O data based on their locations in the domains, and has each process perform I/O for the assigned domain. The partitioning quality determines the maximal performance achievable by the underlying file system, as the shared-file I/O has long been impeded by the cost of file system's data consistency control, particularly due to the conflicted locks. This paper proposes a few file domain partitioning methods designed to reduce lock conflicts under the extent-based file locking protocol. Experiments from four I/O benchmarks on the IBM GPFS and Lustre parallel file systems show that the partitioning method producing minimum lock conflicts wins the highest performance. The benefit of removing conflicted locks can be so significant that more than thirty times of write bandwidth differences are observed between the best and worst methods.

We present a framework for a distributed and lowcost implementation of synchronization mechanisms for embedded shared-memory multiprocessors. The proposed architecture effectively implements the queued-lock semantics in a completely decentralized manner through low-cost and distributed synchronization controllers performing distributed synchronization management protocols. The proposed approach achieves three major benefits. First, it completely eliminates the overwhelming bus contention traffic when multiple cores compete for a synchronization variable. Second, it exhibits extremely low best-case latency of lock acquisition (with zero bus transactions). Third, the approach enables multiple venues for high energy efficiency as the local synchronization controllers can efficiently determine, without any bus transactions or local cache spinning, the exact timing of when a lock is made available to or a barrier enabled at the local processor. It becomes possible for the system software or the thread library to employ various low-power policies.

The Panama canal project included one of the largest and most important electrical installations in the world in the early 20th century. The use of 1,022 electric motors with an installed capacity of 28,290 hp largely replaced the steam-and water-powered equipment then in common use. Reliability and safety were also engineered into the innovative electrical control system, enabling remote lock operation from a central location.

From 1910 to 1913, construction was under way on a huge hydroelectric complex on the Mississippi River at Keokuk, Iowa. Located at the foot of the Des Moines Rapids, the project included a dam that was constructed from Keokuk to Hamilton, Illinois, on the eastern shore of the river. The power plant was separated from the western shore of the river by a navigation lock to permit barge and ship travel past the dam. Originally, all electric power generation at the site was at a frequency of 25 Hz, primarily due to the slow speed of the generators. The major portion of the station's output was transmitted to the city of St. Louis, Missouri, located about 140 miles to the south. As constructed, the station contained 15 10,000-hp turbines, each driving a 7.5-MW AC generator for a total station output of 112.5 MW. The Keokuk station is still in operation today, but it now generates 60-Hz power. The conversion from 25 Hz began in 1942, but was not completed until 2002.

In distributed Web authoring, shared documents can be accessed concurrently by multiple authors who must be coordinated to avoid conflicts. The current Web standard for distributed authoring and versioning uses a two-phase locking to coordinate concurrent access. As the degree to which authors work concurrently may vary though among cooperative sessions, it is necessary to extend the aforementioned standard so as to support a multitude of lock granularity levels. In this paper, we first examine related protocols from the database literature, and then, we comment on their suitability for distributed authoring in the World Wide Web. Our main contribution is a multiple-granularity locking protocol, in which the locks are optional and they convey the meanings of access mode, locking scope, and locking effect. This protocol allows synchronous collaboration by guaranteeing a conflict-free environment and avoiding update loss while it also supports version control. Specifically, by identifying and timestamping object versions, the protocol preserves author intention and operation causality, which were possible so far with operational transformation only. The protocol's efficiency, finally, is demonstrated by a real test with human users and evaluated with simulation experiments, which reveal significant advantages over other protocols of this kind.

This paper extends pin-tool research by investigating a new method to accurately position high-fidelity pins in an array, with each pin uniquely positioned under computer control. The resultant tool is a reusable prototyping system for the rapid generation of three-dimension (3-D) profiles using CAD extracted data, with application potential in a variety of manufacturing processes. A control assessment identifies a combination of array-addressing, latching positioning hardware, and a combined "setting platen" pin-position feedback and drive as an appropriate technique for pin control. The novel platen motion strategy is capable of moving thousands of pins with a single drive motor. The system incorporates latching "locks" that operate on the "tail" of a new two-part "header and tail" pin design. Key to the lock strategy is the application of shape memory alloy actuators in a back-to-back configuration; the response of this material to electrical input is quantified and applied to achieve the unique lock design. Multiple locks combined into a demonstrator position headers to an accuracy of +0.09 -0.05 mm. The mounting pitch of the prototype system permits the use of 1.0 mm section pins. An extension to the design ultimately allows a 15 000 pin-array to be positioned in ~3 min.

Can-follow concurrency control permits a transaction to read (write) an item write-locked (read-locked) by another transaction with almost no delays. By combining the merits of 2PL and 2V2PL, this approach mitigates the lock contention not only between update and read-only transactions, but also between update and update transactions.

As multicore chips become ubiquitous, the need to provide architectural support for practical parallel programming is reaching critical. Conventional lock-based concurrency control techniques are difficult to use, requiring the programmer to navigate through the minefield of coarse-versus fine-grained locks, deadlock, livelock, lock convoying, and priority inversion. This explicit management of concurrency is beyond the reach of the average programmer, threatening to waste the additional parallelism available with multicore architectures. This comprehensive architecture supports nested transactions, transactional handlers, and two-phase commit. The result is a seamless integration of transactional memory with modern programming languages and runtime environments

This paper investigates optimized synchronization techniques for shared memory on-chip multiprocessors (CMPs) based on network-on-chip (NoC) and targeted at future mobile systems. The proposed solution is based on the idea of locally performing synchronization operations requiring continuous polling of a shared variable, thus, featuring large contentions (e.g., spin locks and barriers). A hardware (HW) module, the synchronization-operation buffer (SB), has been introduced to queue and to manage the requests issued by the processors. By using this mechanism, we propose a spin lock implementation requiring a constant number of network transactions and memory accesses per lock acquisition. The SB also supports an efficient implementation of barriers. Experimental validation has been carried out by using GRAPES, a cycle-accurate performance/power simulation platform for multiprocessor systems-on-chip (MPSoCs). Two different architectures have been explored to prove that the proposed approach is effective independently from caches and coherence schemes adopted. For an eight-processor target architecture, we show that the SB-based solution achieves up to 50% performance improvement and 30% energy saving with respect to synchronization based on the caching of the synchronization variables and directory-based coherence protocol. Furthermore, we prove the scalability of the proposed approach when the number of processors increases

Software-based active replication is expensive in terms of performance overhead. Multithreading can help improve performance; however, thread scheduling is a source of nondeterminism in replica behavior. To achieve strong replica consistency in multithreaded environments, this paper proposes intercepting mutex lock/unlock operations performed by threads on accessing the shared data and contributes with two algorithmic solutions: 1) a loose synchronization algorithm (LSA), which captures the natural concurrency in a leader replica and projects it on follower replicas through interreplica communication, and 2) a preemptive deterministic scheduler (PDS) algorithm, which removes the need for interreplica communication through the notion of round and by suspending threads when it is unable (yet) to schedule them deterministically. Failure behavior and performance of LSA and PDS implementations are evaluated in a triplicated system and compared with existing solutions. A performance evaluation indicates that LSA and PDS outperform existing solutions, with PDS offering lower throughput than LSA. A fault-injection campaign shows that PDS is more robust to errors due to the absence of interreplica communication. Hence, LSA and PDS represent a trade-off between performance and dependability. Finally, LSA and PDS are demonstrated in replicating the Apache Web server, a substantial real-world application.

The maintenance of materialized aggregate join views is a well-studied problem. However, to date the published literature has largely ignored the issue of concurrency control. Clearly, immediate materialized view maintenance with transactional consistency, if enforced by generic concurrency control mechanisms, can result in low levels of concurrency and high rates of deadlock. While this problem is superficially amenable to well-known techniques, such as fine-granularity locking and special lock modes for updates that are associative and commutative, we show that these previous high concurrency locking techniques do not fully solve the problem, but a combination of a "value-based" latch pool and these previous high concurrency locking techniques can solve the problem.

This paper describes a novel robotic end-effector and a method for grasping deformable objects with undefined shapes and geometry, such as sacks and bags. The first prototype end-effector, designed for applications in the U.S. Postal Service, is comprised of two parallel rollers with gripping surfaces in which the rollers are pushed toward each other. When the end-effector comes into contact with any portion of the deformable object, the rollers turn inwardly so that a graspable portion of the object is dragged between the rollers. The rollers stop rotating when a graspable portion of the material/object is caught in between, allowing the object to be maneuvered by the robot. The object is released when the rollers turn outwardly. The end-effector described in this article can grab and hold filled sacks from any point on the sack, regardless of the sack's orientation. Experimental evaluation of the end-effector has proven the design and implementation remarkably effective. This article describes the hardware, control method, and design issues associated with the end-effector. Note to Practitioners - Delivery and postal services around the world currently use sacks to hold letters, magazines, and small boxes. The considerable weight of these sacks, their lack of handles, eyelets, or other operator interfaces, and the unpredictable shape and size of the packages within create awkward and uncomfortable handling predicaments for mail handlers at all U.S. Postal Service distribution centers. Currently, no robotic hand or end-effector is commercially available to grab and hold sacks effectively, so sacks must be handled manually by postal employees in distribution centers. This paper describes the design of a novel robotic end-effector for manipulating deformable objects with undefined shapes, such as sacks and bags. This device, which does not mimic human hand architecture, is simple and practical; it makes use of the friction between two rotating rollers to grab sack material when it is in close proximity of the end-effector. The rollers cease rotation when sufficient sack material is collected between the rollers to support the sack. They reverse their rotation, and turn outwardly to release the sack again. This end-effector is able to grab a sack at any point, does not require the edge of the sack to be gathered and flattened prior to grasp, does not require the sack to be placed on its bottom, needs no operator intervention, does not use the weight of the sack to lock and secure the sack in the end-effector, and does not damage the sack contents.

Due to deterministic and fast lookup performance, ternary content addressable memory (TCAM) has recently been gaining popularity in general policy filtering (PF) for packet classification in high-speed networks. However, the PF table update poses significant challenges for efficient use of TCAM. To avoid erroneous and inconsistent rule matching, the traditional approach is to lock the PF table during the rule update period, but table locking has a negative impact on data path processing. In this paper, we propose a novel scheme, called Consistent Policy Table Update Algorithm (CoPTUA), for TCAM. Instead of minimizing the number of rule moves to reduce the locking time, CoPTUA maintains a consistent PF table throughout the update process, thus eliminating the need for locking the PF table while-ensuring correctness of rule matching. Our analysis and simulation show that, even for a PF table with 100,000 rules, an arbitrary number of rules can be updated simultaneously within 1 second in the worst case, provided that 2 percent of the PF table entries are empty. Thus, CoPTUA enforces any new rule in less than 1 second for practical PF table size with high memory utilization and without impacting data path processing.

Lock-free objects offer significant performance and reliability advantages over conventional lock-based objects. However, the lack of an efficient portable lock-free method for the reclamation of the memory occupied by dynamic nodes removed from such objects is a major obstacle to their wide use in practice. We present hazard pointers, a memory management methodology that allows memory reclamation for arbitrary reuse. It is very efficient, as demonstrated by our experimental results. It is suitable for user-level applications - as well as system programs - without dependence on special kernel or scheduler support. It is wait-free. It requires only single-word reads and writes for memory access in its core operations. It allows reclaimed memory to be returned to the operating system. In addition, it offers a lock-free solution for the ABA problem using only practical single-word instructions. Our experimental results on a multiprocessor system show that the new methodology offers equal and, more often, significantly better performance than other memory management methods, in addition to its qualitative advantages regarding memory reclamation and independence of special hardware support. We also show that lock-free implementations of important object types, using hazard pointers, offer comparable performance to that of efficient lock-based implementations under no contention and no multiprogramming, and outperform them by significant margins under moderate multiprogramming and/or contention, in addition to guaranteeing continuous progress and availability, even in the presence of thread failures and arbitrary delays.

We propose an enhanced concurrency control algorithm that maximizes the concurrency of multidimensional index structures. The factors that deteriorate the concurrency of index structures are node splits and minimum bounding region (MBR) updates in multidimensional index structures. The properties of our concurrency control algorithm are as follows: First, to increase the concurrency by avoiding lock coupling during MBR updates, we propose the PLC (partial lock coupling) technique. Second, a new MBR update method is proposed. It allows searchers to access nodes where MBR updates are being performed. Finally, our algorithm holds exclusive latches not during whole split time but only during physical node split time that occupies the small part of a whole split process. For performance evaluation, we implement the proposed concurrency control algorithm and one of the existing link technique-based algorithms on MIDAS-III that is a storage system of a BADA-IV DBMS. We show through various experiments that our proposed algorithm outperforms the existing algorithm in terms of throughput and response time. Also, we propose a recovery protocol for our proposed concurrency control algorithm. The recovery protocol is designed to assure high concurrency and fast recovery.

Although lock-based critical sections are the synchronization method of choice, they have significant performance limitations and lack certain properties, such as failure atomicity and stability. Addressing both these limitations requires considerable software overhead. Transactional lock removal can dynamically eliminate synchronization operations and achieve transparent transactional execution by treating lock-based critical sections as lock-free optimistic transactions.