This paper explores data speculation for improving the performance of Hardware Transactional Memory (HTM). We attempt to reduce transactional conflicts by decoupling them from cache coherence conflicts; many HTMs do not distinguish between transactional conflicts and coherence conflicts, leading to false transactional conflicts. We also attempt to mitigate the effects of coherence conflicts by using value prediction in transactions. We show that coherence decoupling and value prediction in transactions complement each other, because they both speculate on data in ways that are infeasible in the absence of HTM support.

This paper introduces NZTM, a nonblocking, zero-indirection, object-based, hybrid transactional memory system. NZTM comprises a nonblocking software transactional memory (STM) system that can exploit best-effort hardware transactional memory (HTM) if available to improve performance.

Communication latencies within critical sections constitute a major bottleneck in some classes of emerging parallel workloads. In this paper, we argue for the use of Inferentially Queued Locks (IQLs) [31], not just for efficient synchronization but also for reducing communication latencies, and we propose a novel mechanism, Speculative Push (SP), aimed at reducing these communication latencies. With IQLs, the processor infers the existence, and limits, of a critical section from the use of synchronization instructions and joins a queue of lock requestors. The SP mechanism extracts information about program structure by observing IQLs. SP allows the cache controller, responding to a request for a cache line that likely includes a lock variable, to predict the data sets the requestor will modify within the associated critical section. The controller then pushes these lines from its own cache to the target cache, as well as writing them to memory. Overlapping the protected data transfer with that of the lock can substantially reduce the communication latencies within critical sections. By pushing data in exclusive state, the mechanism can collapse a read-modify-write sequences within a critical section into a single local cache access. The write-back to memory allows the receiving cache to ignore the push. Neither mechanism requires any programmer or compiler support nor any instruction set changes. Our experiments demonstrate that IQLs and SP can improve performance of applications employing frequent synchronization.

This paper is motivated by the difficulty in writing correct high-performance programs. Writing shared-memory multi-threaded programs imposes a complex trade-off between programming ease and performance, largely due to subtleties in coordinating access to shared data. To ensure correctness programmers often rely on conservative locking at the expense of performance. The resulting serialization of threads is a performance bottleneck. Locks also interact poorly with thread scheduling and faults, resulting in poor system performance.We seek to improve multithreaded programming trade-offs by providing architectural support for optimistic lock-free execution. In a lock-free execution, shared objects are never locked when accessed by various threads. We propose Transactional Lock Removal (TLR) and show how a program that uses lock-based synchronization can be executed by the hardware in a lock-free manner, even in the presence of conflicts, without programmer support or software changes. TLR uses timestamps for conflict resolution, modest hardware, and features already present in many modern computer systems.TLR's benefits include improved programmability, stability, and performance. Programmers can obtain benefits of lock-free data structures, such as non-blocking behavior and wait-freedom, while using lock-protected critical sections for writing programs.

Serialization of threads due to critical sections is a fundamental bottleneck to achieving high performance in multithreaded programs. Dynamically, such serialization may be unnecessary because these critical sections could have safely executed concurrently without locks. Current processors cannot fully exploit such parallelism because they do not have mechanisms to dynamically detect such false inter-thread dependences. We propose Speculative Lock Elision (SLE), a novel micro-architectural technique to remove dynamically unnecessary lock-induced serialization and enable highly concurrent multithreaded execution. The key insight is that locks do not always have to be acquired for a correct execution. Synchronization instructions are predicted as being unnecessary and elided. This allows multiple threads to concurrently execute critical sections protected by the same lock. Misspeculation due to inter-thread data conflicts is detected using existing cache mechanisms and rollback is used for recovery. Successful speculative elision is validated and committed without acquiring the lock. SLE can be implemented entirely in microarchitecture without instruction set support and without system-level modifications, is transparent to programmers, and requires only trivial additional hardware support. SLE can provide programmers a fast path to writing correct high-performance multithreaded programs.

Efficiency of synchronization mechanisms can limit the parallel performance of many shared-memory applications. In addition, the ever increasing performance gap between processor and interprocessor communication may further compromise the scalability of these primitives. Ideally, synchronization primitives should provide high performance under both high and low contention without requiring substantial programmer effort and software support. QOLR has been shown to offer substantial speedups and to outperform other synchronization primitives consistently, but at the cost of software support and protocol complexity. This paper proposes the use of speculation and delays to implement a purely hardware-based queueing mechanism called Implicit QOLB. Making use of the pervasiveness of the Load-Linked/Store-Conditional primitives, we present a series of hardware mechanisms to optimize performance for sharing patterns exhibited by locks and associated data. The mechanisms do not require any change to existing software or instruction sets. IQOLB sits alongside the cache-coherence protocol and guides the decisions the protocol makes with respect to lock (and associated data) transfers. Preliminary evaluations indicate that IQOLB may perform as well as, if not better than, QOLB without the additional software and protocol complexity.

We propose Instruction-based Prediction as a means to optimize directory based cache coherent NUMA shared memory. Instruction-based prediction is based on observing the behavior of load and store instructions in relation to coherent events and predicting their future behavior. Although this technique is well established in the uniprocessor world, it has not been widely applied for optimizing transparent shared memory. Typically, in this environment, prediction is based on data block access history (address based prediction) in the form of adaptive cache coherence protocols. The advantage of instruction-based prediction is that it requires few hardware resources in the form of small prediction structures per node to match (or exceed) the performance of address based prediction. To show the potential of instruction-based prediction we propose and evaluate three different optimizations: i) a migratory sharing optimization, ii) a wide sharing optimization, and iii) a producer consumer optimization based on speculative execution. With execution driven simulation and a set of nine benchmarks we show that i) for the first two optimizations, instruction-based prediction, using few predictor entries per node, outpaces address based schemes, and (ii) for the producer consumer optimization which uses speculative execution, low mis speculation rates show promise for performance improvements.

In this paper we argue that widely shared data are a more serious problem than previously recognized, and that furthermore, it is possible to provide transparent support that actually gives an advantage to accesses to widely shared data by exploiting their redundancy to improve accessibility.The GLOW extensions to cache coherence pmtocofs -previously proposed-provide such support for widely shared data by defining functionality in the network domain.However in their static form the GLOW extensions relied on the user to identify and expose widely shared data to the hardware.This approach suffers because: i) it requires modification of the programs, ii) it is not always possible to statically idenhfi the widely shared data, and iii) it is incompatible with cornmod@ hardware.To address these issues, we study three dynamic schemes to discover widely shared data at runtime.The first scheme is inspired by read-combining and is based on observing requests in the network switches -the GLOW agents.The agents intercept requests whose addresses have been observed recently.This scheme tracks closely the pegormance of the static GLOW while it always outpelfomrs ordinary congestion-based readcombining.In the second scheme, the memory directory discovers widely shared data by counting the number of reaa!s between writes.Information about the widely shared nature of data is distributed to the nodes which subsequently use special wide sharing requests to access them.Simulations confrm that this scheme works well when the widely shared nature of the data is persistent over time.The third and most significant scheme is based on predicting which load instructions are going to access widely shared data.Although the implementation of this scheme is not as straighrforwani in a commodity-parts environment, it outperforms all others. 1 Introduction Shared-memory multiprocessing is only attractive if it can support a programming paradigm and programming languages efficiently.Numerous studies have characterized the sharing patterns of programs that have been written for such multiprocessors [25], and it is generally believed that widely shared data occur infrequently and do not significantly affect performance.In this paper we argue that in fact widely shared data inherent in some parallel algorithms are a more serious problem than previously recognized, and that furthermore, it is possible to provide support that actually gives an advantage to widely shared data.The idea of read-combining [ 1 l] evolved because of the concern for network contention for widely shared data.Read-combining is highly dynamic, and reduces traffic in the network by recognizing

DataScalar architectures improve memory system performance by running computation redundantly across multiple processors, which are each tightly coupled with an associated memory. The program data set (and/or text) is distributed across these memories. In this execution model, each processor broadcasts operands it loads from its local memory to all other units. In this paper, we describe the benefits, costs, and problems associated with the DataScalar model. We also present simulation results of one possible implementation of a DataScalar system. In our simulated implementation, six unmodified SPEC95 binaries ran from 7% slower to 50% faster on two nodes, and from 9% to 100% faster on four nodes, than on a system with a comparable, more traditional memory system. Our intuition and results show that DataScalar architectures work best with codes for which traditional parallelization techniques fail. We conclude with a discussion of how DataScalar systems may accommodate traditional parallel processing, thus improving performance over a much wider range applications than is currently possible with either model.

Efficient synchronization primitives are essential for achieving high performance in fine-grain, shared-memory parallel programs. One function of synchronization primitives is to enable exclusive access to shared data and critical sections of code. This paper makes three contributions. (1) We enumerate the five sources of overhead that locking synchronization primitives can incur. (2) We describe four mechanisms (local spinning, queue-based locking, collocation, and synchronized prefetch) that reduce these synchronization overheads. (3) With detailed simulations, we show the extent to which these four mechanisms can improve the performance of shared-memory programs. We evaluate the space of these mechanisms using seventeen synchronization constructs, which are formed from six base typed of locks (TEST&SET, TEST&TEST&SET, MCS, LH, M, and QOLB). We show that large performance gains (speedups of more than 1.5 for three of five benchmarks) can be achieved if at least three optimizing mechanisms are used simultaneously. We find that QOLB, which incorporates all four mechanisms, outperforms all other primitives (including reactive synchronization) in all cases. Finally, we demonstrate the superior performance of a low-cost implementation of QOLB, which runs on an unmodified cluster of commodity workstations.

Programsthat make extensive use of widely shared var-

This paper makes the case that pin bandwidth will be a critical consideration for future microprocessors. We show that many of the techniques used to tolerate growing memory latencies do so at the expense of increased bandwidth requirements. Using a decomposition of execution time, we show that for modern processors that employ aggressive memory latency tolerance techniques, wasted cycles due to insufficient bandwidth generally exceed those due to raw memory latencies. Given the importance of maximizing memory bandwidth, we calculate effective pin bandwidth, then estimate optimal effective pin bandwidth. We measure these quantities by determining the amount by which both caches and minimal-traffic caches filter accesses to the lower levels of the memory hierarchy. We see that there is a gap that can exceed two orders of magnitude between the total memory traffic generated by caches and the minimal-traffic caches---implying that the potential exists to increase effective pin bandwidth substantially. We decompose this traffic gap into four factors, and show they contribute quite differently to traffic reduction for different benchmarks. We conclude that, in the short term, pin bandwidth limitations will make more complex on-chip caches cost-effective. For example, flexible caches may allow individual applications to choose from a range of caching policies. In the long term, we predict that off-chip accesses will be so expensive that all system memory will reside on one or more processor chips.

The jine-grain nature of shared-memory multiprocessor communication introduces overheads that can be substantial.Using the Scalable Coherent Inte~ace (SCI) as a base hardware platform and the SPLASH benchmark suite for applications, we analyze three techniques to reduce this overhead: (i) ejicient synchronization primitives, and in particular a hardware primitive called QOLB; (ii) weakened memory ordering constraints; and (iii) optimization of the cache-coherence protocol for two nodes sharing data.We per-jorrn simulations both for current technology and technology that we anticipate will be available jive years hence.We find that QOLB (of which this study perjorms thejirst detailed simulations)shows a large and consistent improvement, much larger than that predicted by Mellor-Crummey and Scott [19].The relaxation of memory ordering constraints also provides a consistent performance improvement.In accordance with prior results, we show that a more aggressive memory model produces more substantial performance improvements.The optimization for twonode sharing shows mixed results, correlating unsurprisingly with the presence of that sharing pattern in an application.Our most important results are (i) that the overheads eliminated with these optimization are largely orthogonal-the peiforrnance gains from supporting multiple optimization concurrently are for the most part additive-and(ii) that technological improvements increase both these overheads and the success of the optimization at reducing them.

In a pipelined-channel interconnection network, multiple bits may be simultaneously in flight on a single wire. This allows the cycle time of the network to be independent of the wire lengths, significantly affecting the network design trade-offs. This paper investigates the design and performance of pipelined channel k-ary n-cube networks, with particular emphasis on the choice of dimensionality and radix. Networks are investigated under the constant link width, constant node size and constant bisection constraints. We find that the optimal dimensionality of pipelined-channel networks is higher than that of nonpipelined-channel networks, with the difference being greater under looser wiring constraints. Their radix should remain roughly constant as network size is grown, decreasing slightly for some unidirectional tori and increasing slightly for some bidirectional meshes. Pipelined-channel networks are shown to provide lower latency and higher bandwidth than their nonpipelined-channel counterparts, especially for high-dimensional networks. The paper also investigates the effects of switching overhead and message lengths, indicating where results agree with and differ from previous results obtained for nonpipelined-channel networks.>

Multis, shared-memory multiprocessors that are implemented with single buses and snooping cache protocols are inherently limited to a small number of processors, and, as systems grow beyond a single bus, the bandwidth requirements of broadcast operations limit scalability. Hardware support to provide cache coherence without the use of broadcast can become very expensive. An approach to maintaining coherence using approximate information held in special-purpose caches called pruning-caches that provides robust performance over a wide range of workloads is presented. The pruning-cache approach is compared to the more conventional inclusion cache for providing multilevel inclusion (MLI) in the cache hierarchy. It is shown that pruning-caches are more cost-effective and more robust. Using both analysis and simulation, it is also shown that the k-ary n-cube topology provides scalable, bottleneck-free communication for uniform, point-to-point traffic.>

The Scalable Coherent Interface (SCI) is an emerging IEEE standard that provides computer-bus-like services to a set of nodes via fast, unidirectional links. This paper presents the first detailed performance study of the SCI ring, using both analytical models and simulation. Performance is analyzed for uniform and nonuniform traffic, and the effect of the ring's flow control protocol is studied.

This paper proposes a set of efficient primitives for process synchronization in multiprocessors. The only assumptions made in developing the set of primitives are that hardware combining is not implemented in the inter-connect, and (in one case) that the interconnect supports broadcast.

This paper discusses a restricted form of the general Fetch&P operation and how the restricted form can be combined. In this restricted form, all processors participating in the combining have identical Fetch&P operations. Most applications of Fetch&P proposed in the literature satisfy the restrictions imposed. We show how this restricted form of Fetch&P allows an easy implementation of combining, especially in bus-based multiprocessors and multiprocessors with a separate synchronization memory. Applications of the proposed restricted Fetch&P operation are also considered.

We discuss the issues about the interdependency between code scheduling and register allocation. We present two methods as solutions: (1) an integrated code scheduling technique; and (2) a DAG-driven register allocator. The integrated code scheduling method combines two scheduling techniques—one to reduce pipeline delays and the other to minimize register usage—into a single phase. By keeping track of the number of available registers, the scheduler can choose the appropriate scheduling technique to schedule a better code sequence. The DAG-driven register allocator uses a dependency graph to assist in assigning registers; it introduces much less extra dependency than does an ordinary register allocator. For large basic blocks, both approaches were shown to generate more efficient code sequences than conventional techniques in the simulations.

The Wisconsin Multicube, a large-scale, shared-memory multiprocessor architecture that uses a snooping cache protocol over a grid of buses, is introduced. The authors describe its cache coherence protocol and discuss efficient synchronization primitive. Then they discuss a number of other important design issues and modeling results. They introduce the general Multicube topology and discuss the scalability of the Wisconsin Multicube. A formal description of the cache consistency protocol is also given.>

A multiprocessor cache memory system is described that supplies data to the processor based on virtual addresses, but maintains consistency in the main memory, both across caches and across virtual address spaces. Pages in the same or different address spaces may be mapped to share a single physical page. The same hardware is used for maintaining consistency both among caches and among virtual addresses. Three different notions of a cache "block" are defined: (1) the unit for transferring data to/from main storage, (2) the unit over which tag information is maintained, and (3) the unit over which consistency is maintained. The relation among these block sizes is explored, and it is shown that they can be optimized independently. It is shown that the use of large address blocks results in low overhead for the virtual address cache.

In this paper, the WISQ architecture is described. This architecture is designed to achieve high performance by exploiting new compiler technology and using a highly segmented pipeline. By having a highly segmented pipeline, a very-high-speed clock can be used. Since a highly segmented pipeline will require relatively long pipelines, a way must be provided to minimize the effects of pipeline bubbles that are formed due to data and control dependencies. It is also important to provide a way of supporting precise interrupts. These goals are met, in part, by providing a reorder buffer to help restore the machine to a precise state. The architecture then makes the pipelining visible to the programmer/compiler by making the reorder buffer accessible and by explicitly providing that issued instructions cannot be affected by immediately preceding ones. Compiler techniques have been identified that can take advantage of the reorder buffer and permit a sustained execution rate approaching or exceeding one per clock. These techniques include using trace scheduling and providing a relatively easy way to “undo” instructions if the predicted branch path is not taken. We have also studied ways to further reduce the effects of branches by not having them executed in the execution unit. In particular, branches are detected and resolved in the instruction fetch unit. Using this approach, the execution unit is sent a stream of instructions (without branches) that are guaranteed to execute.

Single-chip computers are becoming increasingly limited by the access constraints to off-chip memory. To achieve high performance, the structure of on-chip memory must be appropriate, and it must be allocated effectively to minimize off-chip communication. We report experiments that demonstrate that on-chip memory can be effective for local variable accesses. For best use of the limited on-chip area, we suggest organizing memory as registers and argue that an effective register spilling scheme is required. We introduce a heuristic algorithm for register spilling within basic blocks and demonstrate that trace optimization techniques can extend the use of the algorithm to global allocation. Through trace simulation, we show that the use of registers can be more effective in reducing the bus traffic than cache memory of the same size.

Garcia-Molina, Lipton, and Valdes [1] introduced a new machine architecture called "massive memory machines" (MMM). The primary application of their proposed architecture was for so-called memory bound computations. In this correspondence we argue: 1) that massive memories will likely become feasible, but will be most effective with much more powerful processors, and 2) that a massive memory on the proposed machine will perform poorly in the same cases that virtual memory performs poorly: whenever there is poor locality of memory reference. Other problems with the architecture are also discussed. These related issues include: 1) the infeasibility of large on-chip dual port memory, 2) the support of multiprocessing on an ESP, 3) the possibility of memory prerequest, 4) the potential of trading program size for execution time, and 5) the time required for clearing the entire memory.

article Free Access Share on PIPE: a VLSI decoupled architecture Authors: J. R. Goodman The University of Wisconsin-Madison, Computer Sciences Department, 1210 W. Dayton St., Madison, WI The University of Wisconsin-Madison, Computer Sciences Department, 1210 W. Dayton St., Madison, WIView Profile , Jian-tu Hsieh The University of Wisconsin-Madison, Computer Sciences Department, 1210 W. Dayton St., Madison, WI The University of Wisconsin-Madison, Computer Sciences Department, 1210 W. Dayton St., Madison, WIView Profile , Koujuch Liou The University of Wisconsin-Madison, Computer Sciences Department, 1210 W. Dayton St., Madison, WI The University of Wisconsin-Madison, Computer Sciences Department, 1210 W. Dayton St., Madison, WIView Profile , Andrew R. Pleszkun The University of Wisconsin-Madison, Computer Sciences Department, 1210 W. Dayton St., Madison, WI The University of Wisconsin-Madison, Computer Sciences Department, 1210 W. Dayton St., Madison, WIView Profile , P. B. Schechter The University of Wisconsin-Madison, Computer Sciences Department, 1210 W. Dayton St., Madison, WI The University of Wisconsin-Madison, Computer Sciences Department, 1210 W. Dayton St., Madison, WIView Profile , Honesty C. Young The University of Wisconsin-Madison, Computer Sciences Department, 1210 W. Dayton St., Madison, WI The University of Wisconsin-Madison, Computer Sciences Department, 1210 W. Dayton St., Madison, WIView Profile Authors Info & Claims ACM SIGARCH Computer Architecture NewsVolume 13Issue 3June 1985 pp 20–27https://doi.org/10.1145/327070.327117Published:01 June 1985Publication History 101citation592DownloadsMetricsTotal Citations101Total Downloads592Last 12 Months50Last 6 weeks13 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Instruction cache replacement policies and organizations are analyzed both theoretically and experimentally. Theoretical analyses are based on a new model for cache references —the loop model. First the loop model is used to study replacement policies and cache organizations. It is concluded theoretically that random replacement is better than LRU and FIFO, and that under certain circumstances, a direct-mapped or set-associative cache may perform better than a full-associative cache organization. Experimental results using instruction trace data are then given and analyzed. The experimental results indicate that the loop model provides a good explanation for observed cache performance.

The Static Column RAM devices recently introduced offer the potential for implementing a direct-mapped cache on-chip with only a small increase in complexity over that needed for a conventional dynamic RAM memory system. Trace-driven simulation shows that such a cache can only be marginally effective if used in the obvious way. However it can be effective in satisfying the requests from a processor containing an on-chip cache. The SCRAM cache is more effective if the processor cache handles both instructions and data.

The importance of reducing processor-memory bandwidth is recognized in two distinct situations: single board computer systems and microprocessors of the future. Cache memory is investigated as a way to reduce the memory-processor traffic. We show that traditional caches which depend heavily on spatial locality (look-ahead) for their performance are inappropriate in these environments because they generate large bursts of bus traffic. A cache exploiting primarily temporal locality (look-behind) is then proposed and demonstrated to be effective in an environment where process switches are infrequent. We argue that such an environment is possible if the traffic to backing store is small enough that many processors can share a common memory and if the cache data consistency problem is solved. We demonstrate that such a cache can indeed reduce traffic to memory greatly, and introduce an elegant solution to the cache coherency problem.

Instruction caches are analyzed both theoretically and experimentally. The theoretical analysis begins with a new model for cache referencing behavior—the loop model. This model is used to study cache organizations and replacement policies. It is concluded theoretically that random replacement is better than LRU and FIFO, and that under certain circumstances, a direct-mapped or set associative cache may perform better than a full associative cache organization. Experimental results using instruction trace data are then given. The experimental results are shown to support the theoretical conclusions.

A new interconnection topology for incrementally expansible multicomputer systems is described, which combines the easy expansibility of tree structures with the compactness of the n-dimensional hypercube. The addition of n-cube links to the binary tree structure provides direct paths between nodes which have frequent data exchange in algorithms such as sorting and fast Fourier transforms (FFT's). The derivation of a family of such Hypertree structures is outlined, and the basic properties such as average path length, uniformity of the distribution of message traffic, and routing algorithms are analyzed.

With the increasing availability of high-speed multiplication units in large computers it is attractive to develop an iterative procedure to compute division and square root, using multiplication as the primary operation. In this paper, we present three new methods of performing square rooting rapidly which utilize multiplication and no division. Each algorithm is considered for convergence rate, efficiency, and implementation. The most typical and efficient one of the already-known algorithms which utilizes multiplication, here called the N algorithm, is introduced for the purpose of comparison with the new algorithms. The effect and importance of the initial approximation is considered. (One of the algorithms, here called the G algorithm, is described in detail with the emphasis on its high efficiency.)