As emerging memory technologies (e.g., non-volatile memory (NVM)) coming out and machine learning algorithms successfully applying to different fields, the potentials of cache replacement policy for NVM-based systems with the integration of machine learning algorithms are worthy of being exploited to improve the performance of computer systems. In this work, we proposed a machine learning based cache replacement algorithm, named ExpCache, to improve the system performance with NVM as the main memory. By considering the non-volatility characteristic of the NVM devices, we split the whole NVM into two caches, including a read cache and a write cache, for retaining different types of requests. The pages in each cache are managed by both LRU and LFU policies for balancing the recency and frequency of workloads. The online Expert machine learning algorithm is responsible for selecting a proper policy to evict a page from one of the caches based on the access patterns of workloads. In experimental results, the proposed ExpCache outperforms previous studies in terms of hit ratio and the number of dirty pages written back to storage.

Hybrid storage systems are widely used in big data fields to balance system performance and cost. However, due to a poor understanding of the characteristics of database block requests, past studies in this area cannot fully utilize the performance gain from emerging storage devices. This study presents a hybrid storage database system, called HeuristicDB, which uses an emerging non-volatile memory (NVM) block device as an extension of the database buffer pool. To consider the unique performance behaviors of NVM block devices and the block-level characteristics of database requests, a set of heuristic rules that associate database (block) requests with the appropriate quality of service for the purpose of caching priority are proposed. Using online analytical processing (OLAP) and online transactional processing (OLTP) benchmarks, both trace-based examination and system implementation on MySQL are carried out to evaluate the effectiveness of the proposed design. The experimental results indicate that HeuristicDB provides up to 75% higher performance and migrates 18X fewer data between storage and the NVM block device than existing systems.

Deduplication provides significant benefits for accelerating large-scale storage systems, particularly backup systems, by eliminating the redundancy of the streaming data. Given the extraordinary growth of data, modern deduplication backup systems are challenged with the task of effectively and efficiently identifying data duplicates while having limited memory for fingerprint indexing. Based on our observation about an enterprise backup system, for the newly created client, there are no historical backups so that the prefetching algorithm has no reference basis to perform effective fingerprint prefetching. The generic prefetching approach such as Progressive Sampling requires large memory to maintain the prefetching performance. In our paper, we discovered the backup content correlation exists among the backups from some different clients based on the study of the real-world dataset. We propose a fingerprint prefetching algorithm, prefetching backup content correlated fingerprint (PBCCF) to improve the prefetching performance, by applying lightweight machine learning and statistical techniques to discover the backup patterns and generalize their features only using the high-level meta data. The experimental results reveal that PBCCF succeeds at identifying the highly correlated backups and fingerprints to maintain a good deduplication rate while significantly saving memory compared to the Progressive Sampling.

The advent of the AI era has made it increasingly important to have an efficient backup system to protect training data from loss. Furthermore, a backup of the training data makes it possible to update or retrain the learned model as more data are collected. However, a huge backup overhead will result if a complete copy of all daily collected training data is always made to backup storage, especially because the data typically contain highly redundant information that makes no contribution to model learning. Deduplication is a common technique in modern backup systems to reduce data redundancy. However, existing deduplication methods are invalid for training data. Hence, this paper proposes a novel deduplication strategy for the training data used for learning in a deep neural network classifier. Experimental results showed that the proposed deduplication strategy achieved 93% backup storage space reduction with only 1.3% loss of classification accuracy.

Near-sensor convolution engines have many applications in Internet-of-Things. Pulsed unary processing has been recently proposed for high-performance and energy-efficient processing of data using simple digital logic. In this work, we propose a low-cost, high-performance, and energy-efficient near-sensor convolution engine based on pulsed unary processing. The proposed engine removes the necessity of using costly analog-to-digital converters. Synthesis results show that the proposed pulse-based design significantly improves the hardware cost and energy consumption compared to the conventional fixed-point binary and also to the stochastic computing-based designs.

Stochastic logic performs computation on data represented by random bit-streams. The representation allows complex arithmetic to be performed with very simple logic, but it suffers from high latency and poor precision. Furthermore, the results are always somewhat inaccurate due to random fluctuations. In this paper, we show that randomness is not a requirement for this computational paradigm. If properly structured, the same arithmetical constructs can operate on deterministic bit-streams, with the data represented uniformly by the fraction of 1's versus 0's. This paper presents three approaches for the computation: relatively prime stream lengths, rotation, and clock division. Unlike stochastic methods, all three of our deterministic methods produce completely accurate results. The cost of generating the deterministic streams is a small fraction of the cost of generating streams from random/pseudorandom sources. Most importantly, the latency is reduced by a factor of (1/2n), where n is the equivalent number of bits of precision. When computing in unary, the bit-stream length increases with each level of logic. This is an inevitable consequence of the representation, but it can result in unmanageable bit-stream lengths. We discuss two methods for maintaining constant bit-streams lengths via approximations, based on low-discrepancy sequences. These methods provide the best accuracy and area x delay product. They are fast-converging and therefore offer progressive precision.

In the past few years, ever-increasing amounts of image data have been generated by users globally, and these images are routinely stored in cold storage systems in compressed formats. This article investigates the use of approximate storage that leverages the use of cheaper, lower reliability memories that can have higher error rates. Since traditional JPEG-based schemes based on variable-length coding are extremely sensitive to error, the direct use of approximate storage results in severe quality degradation. We propose an error-resilient adaptive-length coding (ALC) scheme that divides all symbols into two classes, based on their frequency of occurrence, where each class has a fixed-length codeword. This provides a balance between the reliability of fixed-length coding schemes, which have a high storage overhead, and the storage-efficiency of Huffman coding schemes, which show high levels of error on low-reliability storage platforms. Further, we use data partitioning to determine which bits are stored in approximate or reliable storage to lower the overall cost of storage. We show that ALC can be used with general non-volatile storage, and can substantially reduce the total cost compared to traditional JPEG-based storage.

Near-sensor convolution engines have many applications in Internet-of-Things. Pulsed unary processing has been recently proposed for high-performance and energy-efficient processing of data using simple digital logic. In this work, we propose a low-cost, high-performance, and energy-efficient near-sensor convolution engine based on pulsed unary processing.

Stochastic computing (SC) has been used for low-cost and low power implementation of neural networks. Inherent inaccuracy and long latency of processing random bit-streams have made prior SC-based implementations inefficient compared to conventional fixed-point designs. Random or pseudo-random bitstreams often need to be processed for a very long time to produce acceptable results. This long latency leads to a significantly higher energy consumption than binary design counterparts. Low-discrepancy sequences have been recently used for fast-converging deterministic computation with stochastic constructs. In this work, we propose a low-cost, low-latency, and energy-efficient implementation of convolutional neural networks based on low-discrepancy deterministic bit-streams. Experimental results show a significant reduction in the energy consumption compared to previous random bitstream-based implementations and to the optimized fixed-point design with no quality degradation.

With expansion of neural network (NN) applications lowering their hardware implementation cost becomes an urgent task especially in back-end applications where the power-supply is limited. Stochastic computing (SC) is a promising solution to realize low-cost hardware designs. Implementation of matrix multiplication has been a bottleneck in previous stochastic neural networks (SC-NNs). In this paper, we introduce spintronic components into the design of SC-NNs. A novel spin-CMOS matrix multiplier is proposed in which the stochastic multiplications are performed by CMOS AND gates while the sum of products is implemented by spintronic compressor gates. The experimental results indicate that compared to the conventional binary implementations the proposed hybrid spin-CMOS architecture can achieve over 125x, 4.5x and 43x; reduction in terms of power, energy and area consumptions, respectively. Moreover, compared to previous CMOS-based SC-NNs, our design saves the power by 3.1x - 7.3x, reduces energy consumption by 3.1x - 7.3x and decreases area by 1.4x - 7.6x while maintaining similar recognition rates.

Solid state drive (SSD) as a fast storage device has been playing an important role across many applications from mobile computing to large distributed systems in recent years. However, the performance of the SSD can be degraded tremendously due to the intrinsic properties of NAND-based flash memory including limited erase cycles and asymmetric write and erase operations. Previous works separated hot/cold data into different blocks in order to improve SSD performance. “Hotness” is typically defined as the cumulative update frequencies of pages. However, we believe that an additional new parameter, average update time interval, should also be considered into the “hotness” definition associated with the update frequency. Moreover, to adaptively classify hot/cold data, a machine learning algorithm is applied to better accommodate the dynamically changed I/O access patterns of traces. In this paper, a machine learning (ML) based SSD management called HAML-SSD is proposed. The purpose of applying the ML algorithm is to dynamically cluster the data with similar “hotness” based on a new definition of “hotness”. Thus, a two-dimension clustering algorithm is used for storing the pages categorized into the same cluster within the same block. Moreover, to obtain reasonable training time, a specific hardware component called HAML-unit is designed in the SSD. Finally, the experimental results indicate that the HAML-SSD decreases the response time around 26.3% - 57.7% compared to previous works with the evaluation of real traces.

Communication overheads in distributed systems constitute a large fraction of the total execution time, and limit the scalability of applications running on these systems. We propose a DCT-based approximate communication scheme that takes advantage of the error resiliency of several widely-used applications, and improves communication efficiency by substantially reducing message lengths. Our scheme is implemented into the Message Passing Interface (MPI) library. When evaluated on several representative MPI applications on a real cluster system, it is seen that the fraction of total execution time devoted to communication reduces from 59% to 23%, even accounting for the computational overhead required for DCT encoding. For many communication-intensive applications, it is shown that our approximate communication scheme effectively speeds up the total execution time without much loss in quality of the result.

With increased interests of neural networks, hardware implementations of neural networks have been investigated. Researchers pursue low hardware cost by using different technologies such as stochastic computing (SC) and quantization. More specifically, the quantization is able to reduce total number of trained weights and results in low hardware cost. SC aims to lower hardware costs substantially by using simple gates instead of complex arithmetic operations. However, the advantages of both quantization and SC in neural networks are not well investigated. In this article, we propose a new stochastic multiplier with simple CMOS transistors called the stochastic hybrid multiplier for quantized neural networks. The new design uses the characteristic of quantized weights and tremendously reduces the hardware cost of neural networks. Experimental results indicate that our stochastic design achieves about 7.7x energy reduction compared to its counterpart binary implementation while maintaining slightly higher recognition error rates than the binary implementation. Compared to previous stochastic neural network implementations, our work derives at least 4x, 9x, and 10x reduction in terms of area, power, and energy, respectively.

Neural networks are becoming prevalent in many areas, such as pattern recognition and medical diagnosis. Stochastic computing is one potential solution for neural networks implemented in low-power back-end devices such as solar-powered devices and Internet of Things (IoT) devices. In this article, we investigate a new architecture of stochastic neural networks with a hardware-oriented approximate activation function. The newly proposed approximate activation function can be hidden in the proposed architecture and thus reduce the whole hardware cost. Additionally, to further reduce the hardware cost of the stochastic implementation, a new hybrid stochastic multiplier is proposed. It contains OR gates and a binary parallel counter, which aims to reduce the number of inputs of the binary parallel counter. The experimental results indicate the newly proposed approximate architecture without hybrid stochastic multipliers achieves more than 25%, 60%, and 3x reduction compared to previous stochastic neural networks, and more than 30x, 30x, and 52% reduction compared to conventional binary neural networks, in terms of area, power, and energy, respectively, while maintaining the similar error rates compared to the conventional neural networks. Furthermore, the stochastic implementation with hybrid stochastic multipliers further reduces area about 18% to 80%, power from 15% to 113.1%, and energy about 15% to 131%, respectively.

Stochastic logic performs computation on data represented by random bit-streams. The representation allows complex arithmetic to be performed with very simple logic, but it suffers from high latency and poor precision. Furthermore, the results are always somewhat inaccurate due to random fluctuations. In this paper, we show that randomness is not a requirement for this computational paradigm. If properly structured, the same arithmetical constructs can operate on deterministic bit-streams, with the data represented uniformly by the fraction of 1's versus 0's. This paper presents three approaches for the computation: relatively prime stream lengths, rotation, and clock division. Unlike stochastic methods, all three of our deterministic methods produce completely accurate results. The cost of generating the deterministic streams is a small fraction of the cost of generating streams from random/pseudorandom sources. Most importantly, the latency is reduced by a factor of (1/2n), where n is the equivalent number of bits of precision. When computing in unary, the bit-stream length increases with each level of logic. This is an inevitable consequence of the representation, but it can result in unmanageable bit-stream lengths. We discuss two methods for maintaining constant bit-streams lengths via approximations, based on low-discrepancy sequences. These methods provide the best accuracy and area × delay product. They are fast-converging and therefore offer progressive precision.

Recently, deterministic approaches to stochastic computing (SC) have been proposed. These compute with the same constructs as stochastic computing but operate on deterministic bit streams. These approaches reduce the area, greatly reduce the latency (by an exponential factor), and produce completely accurate results. However, these methods do not scale well. Also, they lack the property of progressive precision enjoyed by SC. As a result, these deterministic approaches are not competitive for applications where some degree of inaccuracy can be tolerated. In this work we introduce two fast-converging, scalable deterministic approaches to SC based on low-discrepancy sequences. The results are completely accurate when running the operations for the required number of cycles. However, the computation can be truncated early if some inaccuracy is acceptable. Experimental results show that the proposed approaches significantly improve both the processing time and area-delay product compared to prior approaches.

The extraordinary increase in the scale of the backup system and the daily data generated by large enterprise companies are making it extremely challenging to perform data protection efficiently. Traditionally this challenge is left for the backup administrators who are tasked with ensuring the backup and recovery goals are met by designing elaborate static backup schedules. However, the inability of the static backup schedules to adapt alongside the dynamic backup environment results in backup systems that miss their goals. The inefficiency of static backup schedules makes designing an intelligent scheduling algorithm for dynamic backup systems significantly necessary and important. In our paper, we propose an intelligent backup scheduler, HyperProtect, to effectively and efficiently allocate the vast amount of backup contents generated by large scale backup systems to the storage units. To perform empirical comparison of various schedulers, we propose three metrics, storage throughput utilization, backup time consistency, and storage switching to evaluate the backup and restore performance. Based on the experimental results, our scheduler, HyperProtect, achieves more than 55% decrease on storage switching while maintaining good storage throughput utilization and backup time consistency within 1% and 10% of the existing backup scheduler, respectively.

A plethora of research efforts have focused on fine-tuning branch predictors to increasingly higher levels of accuracy. However, several important optimization, financial, and statistical data analysis algorithms rely on probabilistic computation. These applications draw random values from a distribution and steer control flow based on those values. Such probabilistic branches are challenging to predict because of their inherent probabilistic nature. As a result, probabilistic codes significantly suffer from branch mispredictions. This paper proposes Probabilistic Branch Support (PBS), a hardware/software cooperative technique that leverages the observation that the outcome of probabilistic branches needs to be correct only in a statistical sense. PBS stores the outcome and the probabilistic values that lead to the outcome of the current execution to direct the next execution of the probabilistic branch, thereby completely removing the penalty for mispredicted probabilistic branches. PBS relies on marking probabilistic branches in software for hardware to exploit. Our evaluation shows that PBS improves MPKI by 45% on average (and up to 99%) and IPC by 6.7% (up to 17%) over the TAGE-SC-L predictor. PBS requires 193 bytes of hardware overhead and introduces statistically negligible algorithmic inaccuracy.

The RAID-6 configuration is more tolerant of disk failures than other RAID levels because of its ability to tolerate two disk failures. However, previous RAID-6 codes suffer from two major overheads - the time of encoding or decoding processes plus the need to access multiple blocks when updating parities or recovering failed blocks. For example, the PS and Reed-Solomon codes do not have optimal computation complexity, while P-code, X-code and RDP-code must access multiple blocks to update parities during write operations. This work proposes a new XOR- based RAID-6 code, called Tier-code, which not only achieves the optimal parity computation complexity, but also increases the write and degraded-mode read performance compared to previous codes. It uses two tiers of coding, one at the block level and the other at the chunk level. Experimental results of software testing, simulation and ASIC synthesis for this new hierarchical code demonstrate that Tier-code can outperform the previous RAID-6 codes in both write performance and degraded-mode read performance while maintaining the optimal computation complexity in both hardware and software implementations.

This paper proposes a memory efficient failure detection and consensus algorithm, for fail-stop type process failures, based on epidemic protocols. It is suitable for extreme scale systems with reliable networks (no message loss) and high failure frequency. Communication time dominates the execution time at scale. The redundant failure detections and non-uniform information dissemination speed of epidemic algorithms make approximate epidemic-based consensus detection a useful way to trade communication overhead for accuracy. An approximate technique to the consensus detection is also proposed in this paper for faster consensus detection. Results show that the algorithm detects consensus correctly on failed processes with logarithmic scalability. The algorithm is tolerant to process failures both before and during the execution and the number of failures (occurring both before and during execution) have virtually no effect on the consensus detection time at scale. Comparison with similar deterministic consensus detection technique shows that the algorithm detects consensus at the same time with high probability. Further, benefits of the proposed approximate technique increase as system size increases. Compared to the non-approximate version, for a system size of 218 processes, the communication saved is 34% with accuracy loss of the order of 10^-4 in consensus detection.

The primary advantages of stochastic computing are the very simple hardware required to implement complex operations, its ability to gracefully tolerate noise, and the skew tolerance. Its relatively long latency, however, is a potential barrier to widespread use of this paradigm, particularly when high accuracy is required. This work proposes a new, high-speed, yet accurate approach for implementing stochastic circuits that uses synchronized analog pulses as a new way of representing correlated stochastic numbers.

Neural networks are becoming prevalent in many areas, such as pattern recognition and medical diagnosis. Stochastic computing is one potential solution for neural networks implemented in low-power back-end devices such as solar-powered devices and Internet-of-things (IoT) devices. In this paper, we investigate a new architecture of stochastic neural networks with a hardware-oriented approximate activation function. The new proposed approximate activation function can be omitted while keeping the functionality well. Thus, it reduces the stochastic implementation complexity and hardware costs. Moreover, the new architecture significantly improves recognition error rates compared to previous stochastic neural networks with sigmoid function. Three classical types of neural networks are explored, multiple layer perceptron (MLP), restricted Boltzmann machine (RBM) and convolutional neural networks (CNN). The experimental results indicate the new proposed architecture achieves more than 25%, 60% and 3× reduction than previous stochastic neural networks, and more than 30×, 30× and 52% reduction than conventional binary neural networks, in terms of area, power and energy, respectively, while maintaining the similar error rates compared to the conventional neural networks.

Sorting is a common task in a wide range of applications from signal and image processing to switching systems. For applications that require high performance, sorting is often performed in hardware. Hardware cost and power consumption are the dominant concerns. The usual approach is to wire up a network of compare-and-swap units in a configuration called a Batcher (or Bitonic) network. This paper proposes a novel area-and power-efficient approach to sorting networks based on "unary processing." Data is encoded as serial bit-streams, with values represented by the fraction of 1's in a stream of 0's and 1's. (This is an evolution of prior work on stochastic logic. Unlike stochastic logic, the unary approach is deterministic and completely accurate.) Synthesis results of complete sorting networks show up to 87% area and power saving compared to the conventional binary implementations. However, the latency increases. To mitigate the increased latency, the paper uses a novel time-encoding of data. The approach is validated with implementation of an important application of sorting: median filtering. The result is a low-cost, energy-efficient implementation of median filtering with only a slight accuracy loss.

With the rise of cloud storage and many data intensive applications, there is an unprecedented growth in the volume of unstructured data. In response, key-value object storage is becoming more popular for the ease with which it can store, manage, and retrieve large amounts of this data. Seagate recently launched Kinetic direct-access-over-Ethernet hard drives which incorporate a LevelDB key-value store inside each drive. In this work, we evaluate these drives using micro as well as macro benchmarks to help understand the performance limits, trade-offs, and implications of replacing traditional hard drives with Kinetic drives in data centers and high performance systems. We perform in-depth throughput and latency benchmarking of these Kinetic drives (each acting as a tiny independent server) from a client machine connected to them via Ethernet. We compare these results to a SATA-based and a faster SAS-based traditional server running LevelDB. Our sample Kinetic drives are CPU-bound, but they still average sequential write throughput of 63 MB/sec and sequential read throughput of 78 MB/sec for 1 MB value sizes. They also demonstrate unique Kinetic features including direct disk-to-disk data transfer. Our macro benchmarking using the Yahoo Cloud Serving Benchmark (YCSB) shows that mid-range LevelDB servers outperform the Kinetic drives for several workloads; however, this is not always the case. For larger value sizes, even these first generation sample Kinetic drives outperform a full server for several different workloads.

Adopting a new technology, such as a new storage system, is a complicated process because the supporting ecosystems also have to be changed. As a result, any new technology requires exhaustive performance evaluation to justify the cost of switching. However, synthetic workloads or benchmarks typically cannot completely characterize the actual workload. On the other hand, the time and effort required to obtain an appropriate trace can be prohibitive. This work presents a block-level performance measurement tool for storage systems combined with a trace re- player, a trace characteristics analyzer, and a trace re-generator. This new tool is compatible with several different platforms, including Linux and AIX. The purpose of the tool is to evaluate system performance when executing a given application, and to help users determine which system best fits their specific application. Additionally, the trace analyzer can provide details about the characteristics of a given trace. Using the trace analysis results, the re- generator can produce arbitrarily long I/O traces to improve the accuracy of the performance evaluation. The tool also can be used to determine whether a particular system can be adapted to a specific application, and to make comparisons between systems.

Computations based on stochastic bit streams have several advantages compared to deterministic binary radix computations, including low power consumption, low hardware cost, high fault tolerance, and skew tolerance. To take advantage of this computing technique, previous work proposed a combinational logic-based reconfigurable architecture to perform complex arithmetic operations on stochastic streams of bits. The long execution time and the cost of converting between binary and stochastic representations, however, make the stochastic architectures less energy efficient than the deterministic binary implementations. This article introduces a methodology for synthesizing a given target function stochastically using finite-state machines (FSMs), and enhances and extends the reconfigurable architecture using sequential logic. Compared to the previous approach, the proposed reconfigurable architecture can save hardware area and energy consumption by up to 30% and 40%, respectively, while achieving a higher processing speed. Both stochastic reconfigurable architectures are much more tolerant of soft errors (bit flips) than the deterministic binary radix implementations, and their fault tolerance scales gracefully to very large numbers of errors.

In the paradigm of stochastic computing, arithmetic functions are computed on randomized bit streams. The method naturally and effectively tolerates very high clock skew. Exploiting this advantage, this paper introduces polysynchronous clocking, a design strategy in which clock domains are split at a very fine level. Each domain is synchronized by an inexpensive local clock. Alternatively, the skew requirements for a global clock distribution network can be relaxed. This allows for a higher working frequency and so lower latency. The benefits of both approaches are quantified. Polysynchronous clocking results in significant latency, area, and energy savings for wide variety of applications.

Stochastic computing (SC) is a promising technique for applications that require low area overhead and fault tolerance, but can tolerate relatively high latency. In the SC paradigm, logical computation is performed on randomized bit streams. In prior work, streams were generated with linear feedback shift registers; these contributed heavily to the hardware cost and consumed a significant amount of power. This paper introduces a new approach for encoding signal values: computation is performed on analog periodic pulse signals. Exploiting pulse width modulation, time-encoded signals corresponding to specific values are generated by adjusting the frequency and duty cycles of pulse width modulated (PWM) signals. With this approach, the latency, area, and energy consumption are all greatly reduced. Experimental results on image processing applications show up to 99% performance speedup, 98% saving in energy dissipation, and 40% area reduction compared to prior stochastic approaches. Circuits synthesized with the proposed approach can work as fast and energy-efficiently as a conventional binary design while retaining the fault-tolerance and low-cost advantages of conventional stochastic designs.

Clock distribution networks (CDNs) are costly in high-performance ASICs. This paper proposes a new approach: splitting clock domains at a very fine level, down to the level of a handful of gates. Each domain is synchronized with an inexpensive clock signal, generated locally. This is possible by adopting the paradigm of stochastic computation, where signal values are encoded as random bit streams. The design method is illustrated with the synthesis of circuits for applications in signal and image processing.

Artificial neural networks are powerful computational systems with interconnected neurons. Generally, these networks have a very large number of computation nodes which forces the designer to use software-based implementations. However, the software based implementations are offline and not suitable for portable or real-time applications. Experiments show that compared with the software based implementations, FPGA-based systems can greatly speed up the computation time, making them suitable for real-time situations and portable applications. However, the FPGA implementation of neural networks with a large number of nodes is still a challenging task.

The newer storage systems often have to deal with multiple disk failures. Thus, RAID (Redundant Array of Independent Disk) is becoming increasingly important for two primary benefits: (1) high read performance and (2) robust fault tolerance. In addition, the recent RAID codes achieve better IO performance by using only XORs (optimal computational complexity) to compute parities. However, this achieved optimal computational complexity limits the further IO performance improvement. In this paper, we are proposing a new code called PS-code (Parity Stripe code) that employs improved Cauchy Reed Solomon codes for computing the parity to further improve write and degraded mode read performance. Furthermore, we extend the novelty by reducing the number of writes required for updating the parity. We simulated the PS-code in the DiskSim environment and devised a new metric called multi- block access complexity to perform an improved evaluation of the performance of the PS-code on workloads that represent real life scenario such as multi-block updates. Also, the experimental results demonstrate that the PS-code, on average, achieves 66%-86% better write performance and achieves 8.9%-23.6% higher degraded-mode read performance compared to previous works including P-code, RDP code, X-code, and HV-code. Finally, the comparison between the vertical and horizontal codes demonstrates that the vertical codes have better read performance than the horizontal codes in most cases.

Artificial neural networks (ANNs) usually require a very large number of computation nodes and can be implemented either in software or directly in hardware, such as FPGAs. Software-based approaches are offline and not suitable for real-time applications, but they support a large number of nodes. FPGA-based implementations, in contrast, can greatly speedup the computation time. However, resource limitations in an FPGA restrict the maximum number of computation nodes in hardware-based approaches. This work exploits stochastic bit streams to implement the Restricted Boltzmann Machine (RBM) handwritten digit recognition application completely on an FPGA. Exploiting this approach saves a large number of hardware resources making the FPGA-based implementation of large ANNs feasible.

Binarization plays an important role in document image processing, particularly in degraded document images. Among all local adaptive image thresholding algorithms, the Nick method has shown excellent binarization performance for degraded document images. However, local image thresholding algorithms, including the Nick method, are computationally intensive, requiring significant time to process input images. In this paper, we propose three CUDA GPU parallel implementations of the Nick local image thresholding algorithm for faster binarization of large images. Our experimental results show that the GPU-accelerated implementations of the Nick method can achieve up to 150x performance speedup on a GeForce GTX 480 compared to its optimized sequential implementation.

Computer architects face two major challenges in building future exa-scale systems: high energy consumption and the increasing gap between processor and storage speeds. Moving the processing closer to the data, inside the persistent storage, will help mitigate these challenges. This will result in a hierarchical compute structure across the system with a major component of the processing hierarchy inside the Solid State Drive. This new architecture is called the Storage Processing Unit. We perform design space exploration and propose several optimizations to the application space and the architectural space. This research significantly improves the energy use and performance of the system. We observe energy savings from 11 - 423X and performance gains from 4 - 66X for applications including k-means, Sparse BLAS, and others.

We consider the design of IIR filters operating on oversampled sigma-delta modulated bit streams using stochastic arithmetic. Conventional digital filters process multi-bit data at the Nyquist rate using multi-bit multipliers and adders. High resolution ADCs based on the sigma-delta modulation generate random bits at an oversampled rate as intermediate data. We propose to filter the sigma-delta modulated bit streams directly and present first and second order low pass IIR filters based on the stochastic integrator. Experimental results show a significant reduction in hardware area by using stochastic filters.

Most digital systems operate on a positional representation of data, such as binary radix. An alternative is to operate on random bit streams where the signal value is encoded by the probability of obtaining a one versus a zero. This representation is much less compact than binary radix. However, complex operations can be performed with very simple logic. Furthermore, since the representation is uniform, with all bits weighted equally, it is highly tolerant of soft errors (i.e., bit flips). Both combinational and sequential constructs have been proposed for operating on stochastic bit streams. Prior work has shown that combinational logic can implement multiplication and scaled addition effectively while linear finite-state machines (FSMs) can implement complex functions such as exponentiation and tanh effectively. Prior work on stochastic computation has largely been validated empirically.This paper provides a rigorous mathematical treatment of stochastic implementation of complex functions such as exponentiation and tanh implemented using linear FSMs. It presents two new functions, an absolute value function and exponentiation based on an absolute value, motivated by specific applications. Experimental results show that the linear FSM-based constructs for these functions have smaller area-delay products than the corresponding deterministic constructs. They also are much more tolerant of soft errors.

Maintaining the reliability of integrated circuits as transistor sizes continue to shrink to nanoscale dimensions is a significant looming challenge for the industry. Computation on stochastic bit streams, which could replace conventional deterministic computation based on a binary radix, allows similar computation to be performed more reliably and often with less hardware area. Prior work discussed a variety of specific stochastic computational elements (SCEs) for applications such as artificial neural networks and control systems. Recently, very promising new SCEs have been developed based on finite-state machines (FSMs). In this paper, we introduce new SCEs based on FSMs for the task of digital image processing. We present five digital image processing algorithms as case studies of practical applications of the technique. We compare the error tolerance, hardware area, and latency of stochastic implementations to those of conventional deterministic implementations using binary radix encoding. We also provide a rigorous analysis of a particular function, namely the stochastic linear gain function, which had only been validated experimentally in prior work.

Stochastic encoding represents a value using the probability of ones in a random bit stream. Computation based on this encoding has good fault-tolerance and low hardware cost. However, one of its major issues is long processing time. We have to use a long enough bit stream to represent a value to guarantee that random fluctuations introduce only small errors to final computation results. For example, for most digital image processing algorithms, we need a 512-bit stream to represent an 8-bit pixel value stochastically to guarantee that the final computation error is less than 5%. To solve this issue, this paper proposes to share bits between adjacent bit streams to represent adjacent deterministic values. For example, in image processing applications, the bit stream which represents the current pixel value can share parts of the bits in the bit stream which represents the previous pixel value. We use an image contrast stretching algorithm to evaluate this method. Our experimental results show that the proposed methods can improve the performance by 90%.

Stochastic computing is a novel approach to real arithmetic, offering better error tolerance and lower hardware costs over the conventional implementations. Stochastic modules are digital systems that process random bit streams representing real values in the unit interval. Stochastic modules based on finite state machines (FSMs) have been shown to realize complicated arithmetic functions much more efficiently than combinational stochastic modules. However, a general approach to synthesize FSMs for realizing arbitrary functions has been elusive. We describe a systematic procedure to design FSMs that implement arbitrary real-valued functions in the unit interval using the Taylor series approximation.

Researchers showed that performing computation directly on storage devices improves system performance in terms of energy consumption and processing time. For example, Riedel et al. [2] proposed an active disk which performs computation using the processor in a hard disk drive (HDD). Their experimental results showed that the active disk-based system had a factor of 2x performance improvement [2]. However, because the performance gap between the HDDs and CPUs becomes larger and larger, the active disk-based improvement is quite limited. As the role of flash memory increases in storage architectures, solid-state drives (SSDs) have gradually displaced the HDDs with higher access performance and lower power consumption. Researchers also proposed an active flash, which performs computation using a controller in the SSD [1]. However, the SSD controller needs to implement a flash translation layer to make the SSD as an emulated HDD for most operating systems. It also needs to communicate with a host interface to transfer required data. The additional computation power can be utilized is quite limited. To maximize the computation power on the SSD, we propose a processor design called storage processing unit (SPU).

The Stochastic Computational Element (SCE) uses streams of random bits (stochastic bits streams) to perform computation with conventional digital logic gates. It can guarantee reliable computation using unreliable devices. In stochastic computing, the linear Finite State Machine (FSM) can be used to implement some sophisticated functions, such as the exponentiation and tanh functions, more efficiently than combinational logic. However, a general approach about how to synthesize a linear FSM-based SCE for a target function has not been available. In this paper, we will introduce three properties of the linear FSM used in stochastic computing and demonstrate a general approach to synthesize a linear FSM-based SCE for a target function. Experimental results show that our approach produces circuits that are much more tolerant of soft errors than deterministic implementations, while the area-delay product of the circuits are less than that of deterministic implementations.

Workload consolidation is a key technique in reducing costs in virtualized datacenters. When considering storage consolidation, a key problem is the unpredictable performance behavior of consolidated workloads on a given storage system. In practice, this often forces system administrators to grossly overprovision storage to meet application demands. In this paper, we show that existing modeling techniques are inaccurate and ineffective in the face of heterogenous devices. We introduce Romano, a storage performance management system designed to optimize truly heterogeneous virtualized datacenters. At its core, Romano constructs and adapts approximate workload-specific performance models of storage devices automatically, along with prediction intervals. It then applies these models to allow highly efficient IO load balancing.

Nanoelectromechanical systems (NEMS) is an emerging nanoscale technology that combines mechanical and electrical effects in devices. A variety of NEMS-based devices have been proposed for integrated chip designs. Amongst them are near-ideal digital switches. The electromechanical principles that are the basis of these switches impart the capability of extremely low power switching characteristics to digital circuits. NEMS switching devices have been mostly used as simple switches to provide digital operation, however, we observe that their unique operation can be used to accomplish logic functions directly. In this paper, we propose a novel technique called `weighted area logic' to design logic circuits with NEMS-based switches. The technique takes advantage of the unique structural configurations possible with the NEMS devices to convert the digital switch from a simple ON-OFF switch to a logical switch. This transformation not only reduces the delay of complex logic units, but also decreases the power and area of the implementation further. To demonstrate this, we show the new designs of the logic functions of NAND, XOR and a three input function Y = A + B.C, and compose them into a 32-bit adder. Through simulation, we quantify the power, delay and area advantages of using the weighted area logic technique over a standard CMOS-like design technique applied to NEMS.

The paradigm of logical computation on stochastic bit streams has several key advantages compared to deterministic computation based on binary radix, including error-tolerance and low hardware area cost. Prior research has shown that sequential logic operating on stochastic bit streams can compute non-polynomial functions, such as the tanh function, with less energy than conventional implementations. However, the functions that can be computed in this way are quite limited. For example, high order polynomials and non-polynomial functions cannot be computed using prior approaches. This paper proposes a new finite-state machine (FSM) topology for complex arithmetic computation on stochastic bit streams. It describes a general methodology for synthesizing such FSMs. Experimental results show that these FSM-based implementations are more tolerant of soft errors and less costly in terms of the area-time product that conventional implementations.

Numerical integration is a widely used approach for computing an approximate result of a definite integral. Conventional digital implementations of numerical integration using binary radix encoding are costly in terms of hardware and have long computational delay. This work proposes a novel method for performing numerical integration based on the paradigm of logical computation on stochastic bit streams. In this paradigm, ordinary digital circuits are employed but they operate on stochastic bit streams instead of deterministic values; the signal value is encoded by the probability of obtaining a one versus a zero in the streams. With this type of computation, complex arithmetic operations can be implemented with very simple circuitry. However, typically, such stochastic implementations have long computational delay, since long bit streams are required to encode precise values. This paper proposes a stochastic design for numerical integration characterized by both small area and short delay -- so, in contrast to previous applications, a win on both metrics. The design is based on mathematical analysis that demonstrates that the summation of a large number of terms in the numerical integration could lead to a significant delay reduction. An architecture is proposed for this task. Experiments confirm that the stochastic implementation has smaller area and shorter delay than conventional implementations.

Computation performed on stochastic bit streams is less efficient than that based on a binary radix because of its long latency. However, for certain complex arithmetic operations, computation on stochastic bit streams can consume less energy and tolerate more soft errors. In addition, the latency issue could be solved by using a faster clock frequency or in combination with a parallel processing approach. To take advantage of this computing technique, previous work proposed a combinational logic-based reconfigurable architecture to perform complex arithmetic operations on stochastic streams of bits. In this paper, we enhance and extend this reconfigurable architecture using sequential logic. Compared to the previous approach, the proposed reconfigurable architecture takes less hardware area and consumes less energy, while achieving the same performance in terms of processing time and fault-tolerance.

Phase change memory (PCM) is a promising technology to solve energy and performance bottlenecks for memory and storage systems. To help understand the reliability characteristics of PCM devices, we present a simple fault model to categorize four types of PCM errors. Based on our proposed fault model, we conduct extensive experiments on real PCM devices at the memory module level. Numerical results uncover many interesting trends in terms of the lifetime of PCM devices and error behaviors. Specifically, PCM lifetime for the memory chips we tested is greater than 14 million cycles, which is much longer than for flash memory devices. In addition, the distributions for four types of errors are quite different. These results can be used for estimating PCM lifetime and for measuring the fabrication quality of individual PCM memory chips.

Recent advances in flash memory show great potential to replace traditional hard drives (HDDs) with flash-based solid state drives (SSDs) from personal computing to distributed systems. However, it is still a long way to go before completely using SSDs for enterprise data storage. Considering the cost, performance, and reliability of SSDs, a practical solution is to combine both SSDs and HDDs together. This paper proposes a hybrid storage system named PASS (Performance-dAta Synchronization - hybrid storage System) to tradeoff between I/O performance and data discrepancy between SSDs and HDDs. PASS includes a high-performance SSD and a traditional HDD to store mirrored data for reliability. All of the I/O requests are redirected to the primary SSD first and then the updated data blocks are copied to the backup HDD asynchronously. In order to hide the latency of copying operations, we use an I/O window to coalesce write requests and maintain an ordered I/O queue to shorten the HDD seek and rotation times. Depending on the charateristics of different I/O workloads, we develop an adaptive policy to dynamically balance the foreground I/O processing and background mirroring. We implement a prototype system of PASS by developing a Linux device driver and conduct experiments on the IoMeter, PostMark, and TPCC benchmarks. Our results show that PASS can achieve up to 12 times the performance of a RAID1 storage system for the IoMeter and PostMark workloads while tolerating less than 2% data discrepancy between the primary SSD and the backup HDD. More interestingly, while PASS does not produce any performance benefit for the TPC-C benchmark, it does allow the system to scale to larger sizes than when using an HDD-based RAID system alone.

Given an N-point sequence, finding its k largest components in the frequency domain is a problem of great interest. This problem, which is usually referred to as a sparse Fourier Transform, was recently brought back on stage by a newly proposed algorithm called the sFFT. In this paper, we present a parallel implementation of sFFT on both multi-core CPUs and GPUs using a human voice signal as a case study. Using this example, an estimate of k for the 3dB cutoff points was conducted through concrete experiments. In addition, three optimization strategies are presented in this paper. We demonstrate that the multi-core-based sFFT achieves speedups of up to three times a single-threaded sFFT while a GPU-based version achieves up to ten times speedup. For large scale cases, the GPU-based sFFT also shows its considerable advantages, which is about 40 times speedup compared to the latest out-of-card FFT implementations [2].

The kernel density estimation (KDE)-based image segmentation algorithm has excellent segmentation performance. However, this algorithm is computational intensive. In addition, although this algorithm can tolerant noise in the input images, such as the noise due to snow, rain, or camera shaking, it is sensitive to the noise from the internal computing circuits, such as the noise due to soft errors or PVT (process, voltage, and temperature) variation. Tolerating this kind of noise becomes more and more important as device scaling continues to nanoscale dimensions. Stochastic computing, which uses streams of random bits (stochastic bits streams) to perform computation with conventional digital logic gates, can guarantee reliable computation using unreliable devices. In this paper, we present a stochastic computing implementation of the KDE-based image segmentation algorithm. Our experimental results show that, under the same time constraint, the stochastic implementation is much more tolerant of faults and consumes less hardware and power compared to a conventional (nonstochastic) implementation. Furthermore, compared to a Triple Modular Redundancy (TMR) fault tolerance technique, the stochastic architecture tolerates substantially more soft errors with lower power consumption.

Exciting developments are taking place in the field of spintronics, particularly with the advances in the fabrication and characterization of devices such as Magnetic Tunnel Junctions (MTJ). The distinction of spintronic devices from conventional electronic devices makes it challenging to design efficient, scalable and low power logic circuits with MTJs. We propose a programmable and scalable technique to design MTJ-based logic circuits that are capable of implementing any 2-input logic truth table. We present the energy-delay trade-offs of this design with respect to circuit parameters. We also demonstrate that this circuit can be scaled to a 6-input logic function without incurring an increase in the energy consumption.

As device scaling continues to nanoscale dimensions, circuit reliability will continue to become an ever greater problem. Stochastic computing, which performs computing with random bits (stochastic bits streams), can be used to enable reliable computation using those unreliable devices. However, one of the major issues of stochastic computing is that applications implemented with this technique are limited by the available computational elements. In this paper, first we will introduce and prove a stochastic absolute value function. Second, we will demonstrate a mathematical analysis of a stochastic tanh function, which is a key component used in a stochastic comparator. Third, we will present a quantitative analysis of a one-parameter linear gain function, and propose a new two-parameter version. The validity of the present stochastic computational elements is demonstrated through four basic digital image processing algorithms: edge detection, frame difference based image segmentation, median filter based noise reduction, and image contrast stretching. Our experimental results show that stochastic implementations tolerate more noise and consume less hardware than their conventional counterparts.

The bloom filter is a probabilistic data structure that provides a compact representation of a set of elements. To keep false positive probabilities low, the size of the bloom filter must be dimensioned a priori to be linear in the maximum number of keys inserted, with the linearity constant ranging typically from one to few bytes. A bloom filter is most commonly used as an in memory data structure, hence its size is limited by the availability of RAM space on the machine. As datasets have grown over time to Internet scale, so have the RAM space requirements of bloom filters. If sufficient RAM space is not available, we advocate that flash memory may serve as a suitable medium for storing bloom filters, since it is about one-tenth the cost of RAM per GB while still providing access times orders of magnitude faster than hard disk. We present BLOOMFLASH, a bloom filter designed for flash memory based storage, that provides a new dimension of trade off with bloom filter access times to reduce RAM space usage (and hence system cost). The simple design of a single flat bloom filter on flash suffers from many performance bottlenecks, including in-place bit updates that are inefficient on flash and multiple reads and random writes spread out across many flash pages for a single lookup or insert operation. To mitigate these performance bottlenecks, BLOOMFLASH leverages two key design innovations: (i) buffering bit updates in RAM and applying them in bulk to flash that helps to reduce random writes to flash, and (ii) a hierarchical bloom filter design consisting of component bloom filters, stored one per flash page, that helps to localize reads and writes on flash. We use two real-world data traces taken from representative bloom filter applications to drive and evaluate our design. BLOOMFLASH achieves bloom filter access times in the range of few tens of microseconds, thus allowing up to order of tens of thousands operations per sec.

Existing garbage collection algorithms for the flash-based storage use score-based heuristics to select victim blocks for reclaiming free space and wear leveling. The score for a block is estimated using metadata information such as age, block utilization, and erase count. To quickly find a victim block, these algorithms maintain a priority queue in the SRAM of the storage controller. This priority queue takes O(K) space, where K stands for flash storage capacity in total number of blocks. As the flash capacity scales to larger size, K also scales to larger value. However, due to higher price per byte, SRAM will not scale proportionately. In this case, due to SRAM scarcity, it will be challenging to implement a larger priority queue in the limited SRAM of a large-capacity flash storage. In addition to space issue, with any update in the metadata information, the priority queue needs to be continuously updated, which takes O(lg(K)) operations. This computation overhead also increases with the increase of flash capacity. In this paper, we have taken a novel approach to solve the garbage collection metadata management problem of a large-capacity flash storage. We propose a sampling-based approach to approximate existing garbage collection algorithms in the limited SRAM space. Since these algorithms are heuristic-based, our sampling-based algorithm will perform as good as unsampled (original) algorithm, if we choose good samples to make garbage collection decisions. We propose a very simple policy to choose samples. Our experimental results show that small number of samples are good enough to emulate existing garbage collection algorithms.

Abstract The lattice‐Boltzmann method is well suited for implementation in single‐instruction multiple‐data (SIMD) environments provided by general purpose graphics processing units (GPGPUs). This paper discusses the integration of these GPGPU programs with OpenMP to create lattice‐Boltzmann applications for multi‐GPU clusters. In addition to the standard single‐phase single‐component lattice‐Boltzmann method, the performances of more complex multiphase, multicomponent models are also examined. The contributions of various GPU lattice‐Boltzmann parameters to the performance are examined and quantified with a statistical model of the performance using Analysis of Variance (ANOVA). By examining single‐ and multi‐GPU lattice‐Boltzmann simulations with ANOVA, we show that all the lattice‐Boltzmann simulations primarily depend on effects corresponding to simulation geometry and decomposition, and not on the architectural aspects of GPU. Additionally, using ANOVA we confirm that the metrics ofEfficiencyandUtilizationare not suitable for memory‐bandwidth‐dependent codes. Copyright © 2010 John Wiley & Sons, Ltd.

Mounting concerns over variability, defects, and noise motivate a new approach for digital circuitry: stochastic logic, that is to say, logic that operates on probabilistic signals and so can cope with errors and uncertainty. Techniques for probabilistic analysis of circuits and systems are well established. We advocate a strategy for synthesis. In prior work, we described a methodology for synthesizing stochastic logic, that is to say logic that operates on probabilistic bit streams. In this paper, we apply the concept of stochastic logic to a reconfigurable architecture that implements processing operations on a datapath. We analyze cost as well as the sources of error: approximation, quantization, and random fluctuations. We study the effectiveness of the architecture on a collection of benchmarks for image processing. The stochastic architecture requires less area than conventional hardware implementations. Moreover, it is much more tolerant of soft errors (bit flips) than these deterministic implementations. This fault tolerance scales gracefully to very large numbers of errors.

The emerging field of spintronics is undergoing exciting developments with the advances recently seen in spintronic devices, such as magnetic tunnel junctions (MTJs). While they make excellent memory devices, recently they have also been used to accomplish logic functions. The properties of MTJs are greatly different from those of electronic devices like CMOS semiconductors. This makes it challenging to design circuits that can efficiently leverage the spintronic capabilities. The current approaches to achieving logic functionality with MTJs include designing an integrated CMOS and MTJ circuit, where CMOS devices are used for implementing the required intermediate read and write circuitry. The problem with this approach is that such intermediate circuitry adds overheads of area, delay and power consumption to the logic circuit. In this paper, we present a circuit to accomplish logic operations using MTJs on data that is stored in other MTJs, without an intermediate electronic circuitry. This thus reduces the performance overheads of the spintronic circuit while also simplifying fabrication. With this circuit, we discuss the notion of performing logic operations with a non-volatile memory device and compare it with the traditional method of computation with separate logic and memory units. We find that the MTJ-based logic unit has the potential to offer a higher energy-delay efficiency than that of a CMOS-based logic operation on data stored in a separate memory module.

The NAND flash memory based storage has faster read, higher power savings, and lower cooling cost compared to the conventional rotating magnetic disk drive. However, in case of flash memory, read and write operations are not symmetric. Write operations are much slower than read operations. Moreover, frequent update operations reduce the lifetime of the flash memory. Due to the faster read performance, flash-based storage is particularly attractive for the read-intensive database workloads, while it can produce poor performance when used for the update-intensive database workloads. This paper aims to improve write performance and lifetime of flash-based storage for the update-intensive workloads. In particular, we propose a new hierarchical approach named as deferred update methodology. Instead of directly updating the data records, first we buffer the changes due to update operations as logs in two intermediate in-flash layers. Next, we apply multiple update logs in bulk to the data records. Experimental results show that our proposed methodology significantly improves update processing overhead and longevity of the flash-based storages.

Solid state drives (SSDs) allow single-drive performance that is far greater than disks can produce. Their low latency and potential for parallel operations mean that they are able to read and write data at speeds that strain operating system I/O interfaces. Additionally, their performance characteristics expose gaps in existing benchmarking methodologies. We discuss the impact on Linux system design of a prototype PCI Express SSD that operates at least an order of magnitude faster than most drives available today. We develop benchmarking strategies and focus on several areas where current Linux systems need improvement, and suggest methods of taking full advantage of such high-performance solid state storage. We demonstrate that an SSD can perform with high throughput, high operation rates, and low latency under the most difficult conditions. This suggests that high-performance SSDs can dramatically improve parallel I/O performance for future high performance computing (HPC) systems.

Mounting concerns over variability, defects and noise motivate a new approach for integrated circuits: the design of stochastic logic, that is to say, digital circuitry that operates on probabilistic signals, and so can cope with errors and uncertainty. Techniques for probabilistic analysis are well established. We advocate a strategy for synthesis. In this paper, we present a reconfigurable architecture that implements the computation of arbitrary continuous functions with stochastic logic. We analyze the sources of error: approximation, quantization, and random fluctuations. We demonstrate the effectiveness of our method on a collection of benchmarks for image processing. Synthesis trials show that our stochastic architecture requires less area than conventional hardware implementations. It achieves a large speed up compared to software conventional implementations. Most importantly, it is much more tolerant of soft errors (bit flips) than these deterministic implementations.

As CMOS devices are scaled down into the nanometer regime, concerns about reliability are mounting. Instead of viewing nano-scale characteristics as an impediment, technologies such as PCMOS exploit them as a source of randomness. The technology generates random numbers that are used in probabilistic algorithms. With the PCMOS approach, different voltage levels are used to generate different probability values. If many different probability values are required, this approach becomes prohibitively expensive.

Lattice Boltzmann methods (LBM) are used for the computational simulation of Newtonian fluid dynamics. LBM-based simulations are readily parallelizable; they have been implemented on general-purpose processors, field-programmable gate arrays (FPGAs), and graphics processing units (GPUs). Of the three methods, the GPU implementations achieved the highest simulation performance per chip. With memory bandwidth of up to 141 GB/s and a theoretical maximum floating point performance of over 600 GFLOPS, CUDA-ready GPUs from NVIDIA provide an attractive platform for a wide range of scientific simulations, including LBM. This paper improves upon prior single-precision GPU LBM results for the D3Q19 model by increasing GPU multiprocessor occupancy, resulting in an increase in maximum performance by 20%, and by introducing a space-efficient storage method which reduces GPU RAM requirements by 50% at a slight detriment to performance. Both GPU implementations are over 28 times faster than a single-precision quad-core CPU version utilizing OpenMP.

Solid state disks (SSDs) using NAND flash memory are increasingly being adopted in the high-end servers of datacenters to improve performance of the I/O-intensive applications. Compared to the traditional enterprise class hard disks, SSDs provide faster read performance, lower cooling cost, and higher power efficiency. However, write performance of a flash based SSD can be up to an order of magnitude slower than its read performance. Furthermore, frequent write operations degrade the lifetime of flash memory. A nonvolatile cache can greatly help to solve these problems. Although a RAM cache is relative high in cost, it has successfully eliminated the performance gap between fast CPU and slow magnetic disk. Similarly, a nonvolatile cache in an SSD can alleviate the disparity between the flash memory's read and write performance. A small write cache that reduces the number of flash block erase operations, can lead to substantial performance gain for write-intensive applications and can extend the overall lifetime of flash based SSDs. This paper presents a novel write caching algorithm, the Large Block CLOCK (LB-CLOCK) algorithm, which considers `recency' and `block space utilization' metrics to make cache management decisions. LB-CLOCK dynamically varies the priority between these two metrics to adapt to changes in workload characteristics. Our simulation based experimental results show that LB-CLOCK outperforms the best known existing flash caching algorithms for a wide range of workloads.

In order to manage risks to the IT environments and to satisfy government and industry regulations, most enterprises are required to conduct risk assessments. These risk assessments are used to drive organizational decisions on information security. However, despite this need, current approaches lack granular guidance on some key steps and have focused on qualitative data rather than quantitative data which reduces the value of the results for the decision makers. This paper proposes a statistical design of experiments approach that will enhance the quantitative aspects of the risk assessment exercise and will make risk assessments smarter, more precise and more efficient. Specifically, our paper demonstrates that a Plackett-Burman design can be used to: (a) identify the subset of security controls that are critical to the enterprise; (b) determine the configuration of these controls; and (c) quantitatively analyze the impact of security enhancements. This paper expands on our previous research by applying statistical models at a macro security architecture level as opposed to determining parameters for individual controls.

Future nanoscale devices are expected to be more fragile and sensitive to external influences than conventional CMOS-based devices. Researchers predict that it will no longer be possible to test a device and then throw it away if it is found to be defective, as every circuit is expected to have multiple hard and soft defects. Fundamentally new fault-tolerant architectures are required to produce reliable systems that will survive with manufacturing defects and transient faults. This paper introduces the History Index of Correct Computation (HICC) as a run-time reconfiguration technique for fault-tolerant nano-computing. This approach identifies reliable blocks on-the-fly by monitoring the correctness of their outputs and forwarding only good results, ignoring the results from unreliable blocks. Simulation results show that history-based TMR modules offer a better response to fault tolerance at the module level than do conventional fault-tolerant approaches when the faults are nonuniformly distributed among redundant units. A correct computation rate of 99% is achieved despite a 13% average injected fault rate, when one of the redundant units and the decision unit are fault-free as well as when both have a low injected fault rate of 0.1%. A correct computation rate of 89% is achieved when faults are nonuniformly distributed at an average fault rate of 11% and fault rate in the decision unit is 0.5%. The robustness of the history-based mechanism is shown to be better than both majority voting and a Hamming detection and correction code.

In the last decade, the focus of fault-tolerance methods has tended towards circuit level modifications, such as transistor resizing, and away from expensive system level redundancy approaches. We present the results from a screening experiment to identify significant parameters in circuit level soft error simulations to guide such approaches to fault- tolerance. This approach allows us to assess which parameters will have the most significance for reducing soft error rates and the impact that process variation will have on the accuracy of soft error rate estimates. We identify supply voltage and transistor type as being the most significant parameters affecting soft errors in logic cells across several technology scales. Additionally, we provide a ranking of more than a dozen parameters, across four technology scales, based on the significance of their impact on soft error rates.

Radiation induced single-event upsets are becoming an increasing issue for designers due to the impact on overall design reliability. This paper presents a method for translating probabilistic information from lower levels in the design hierarchy into efficient, fast, and useful tools at higher levels. This method allows designers to incorporate soft error reliability analysis into the verification process at greatly reduced simulation expense with high accuracy. We also include metrics to estimate the error in the method. Results from both abstracted verification simulations and Verilog soft error simulations are presented. Our method bridges a gap between low level reliability measurements and high level reliability simulations.

Although high branch prediction accuracy is necessary for high performance, it typically comes at the cost of larger predictor tables and/or more complex prediction algorithms. Unfortunately, large predictor tables and complex algorithms require more chip area and have higher power consumption, which precludes their use in embedded processors. As an alternative to large, complex branch predictors, in this paper, we investigate adding complementary branch predictors (CBP) to embedded processors to reduce their power consumption and/or improve their branch prediction accuracy. A CBP differs from a conventional branch predictor in that it focuses only on frequently mispredicted branches while letting the conventional branch predictor predict the more predictable ones. Our results show that adding a small 16-entry (28 byte) CBP reduces the branch misprediction rate of static, bimodal, and gshare branch predictors by an average of 51.0%, 42.5%, and 39.8%, respectively, across 38 SPEC 2000 and MiBench benchmarks. Furthermore, a 256-entry CBP improves the energy-efficiency of the branch predictor and processor up to 97.8% and 23.6%, respectively. Finally, in addition to being very energy-efficient, a CBP can also improve the processor performance and, due to its simplicity, can be easily added to the pipeline of any processor.

This work addresses the problem of building representative subsets of benchmarks from an original large set of benchmarks, using statistical analysis techniques. The subsets should be developed in this way to include only the necessary information for evaluating the performance of a computer system or application. The development of representative workloads is not a trivial procedure, since incorrectly selecting benchmarks the representative subset can produce erroneous results. A number of statistical analysis techniques have been developed for identifying representative workloads. The goal of these approaches is to reduce the dimensionality of the original set of benchmarks prior to identifying similar benchmarks. In this work we propose a combination of independent component analysis (ICA) and evolutionary algorithm (EA) as a more efficient way for reducing the computational complexity of the problem and the redundant information of the original set of benchmarks. Experimental results validate that the proposed technique generates more representative workloads than prior techniques.

With increasing levels of integration of multiple processing cores and new features to support software functionality, recent generations of microprocessors face difficult validation challenges. The systematic validation approach starts with defining the correct behaviors of the hardware and software components and their interactions. This requires new modeling paradigms that support multiple levels of abstraction. Mutual consistency of models at adjacent levels of abstraction is crucial for manual refinement of models from the full chip level to production register transfer level, which is likely to remain the dominant design methodology of complex microprocessors in the near future. In this paper, we present microprocessor modeling and validation environment (MMV), a validation environment based on metamodeling, that can be used to create models at various abstraction levels and to generate most of the important validation collaterals, viz., simulators, checkers, coverage, and test generation tools. We illustrate the functionalities in MMV by modeling a 32-bit reduced instruction set computer processor at the system, instruction set architecture, and microarchitecture levels. We show by examples how consistency across levels is enforced during modeling and also how to generate constraints for automatic test generation.

Functional validation of modern microprocessors is an important and complex problem. One of the problems in functional validation is the generation of test cases that has higher potential to find faults in the design. We propose a model based test generation framework that generates tests for design fault classes inspired from software validation. There are two main contributions in this paper. Firstly, we propose a microprocessor modeling and test generation framework that generates test suites to satisfy modified condition decision coverage (MCDC), a structural coverage metric that detects most of the classified design faults as well as the remaining faults not covered by MCDC. Secondly, we show that there exists good correlation between types of design faults proposed by software validation and the errors/bugs reported in case studies on microprocessor validation. We demonstrate the framework by modeling and generating tests for the microarchitecture of VESPA, a 32-bit microprocessor. In the results section, we show that the tests generated using our framework's coverage directed approach detects the fault classes with 100% coverage, when compared to model-random test generation

With continuing increase in soft error rates, its foreseeable that multiple faults will eventually need to be considered when modeling circuit sensitivity and evaluating fault- tolerance techniques. Previous work that considers multiple faults assumes the faults are permanent. These assumptions aren't directly valid for soft errors. In this work, we evaluate two currently available models for analyzing circuit sensitivities but subject them to multiple transient fault environments. The first model targets the application of triple modular redundancy (TMR) to a non-branching (no fan-out) circuit with permanent faults. We demonstrate this model's inability to adequately predict sensitivity when circuits with branching are considered and subjected to transient faults. We motivate the need for a model that captures logical masking. This is provided by modifying a soft error rate (SER) estimation algorithm to handle multiple faults and gate input interdependence. We conclude that the simple non-branching model can predict a trade-off threshold for when TMR can benefit a circuit. However accurately predicting the magnitude of reliability changes requires the inclusion of more complicated branching effects and logical masking.

Deep submicron technology is expected to be plagued by many reliability issues including soft errors in logic. To address this, we demonstrate how exploiting the natural fault masking characteristics of logical functions can be achieved by exploring the design space for selecting subsets of cells from within a cell library prior to synthesis. Subset selection alone is shown to improve the reliability of combinational logic circuits by more than 35%. We compare how subset libraries effect the trade-offs between reliability, area, power, and performance. Further, we show that added benefits of reduced cell library size can benefit the design.

Due to the long simulation time of the reference input set, computer architects often use reduced time simulation techniques to shorten the simulation time. However, what has not yet been thoroughly evaluated is the accuracy of these techniques relative to the reference input set and with respect to each other. To rectify this deficiency, this paper uses three methods to characterize reduced input set, truncated execution, and sampling-based simulation techniques while also examining their speed versus accuracy trade-off and configuration dependence. Our results show that the three sampling-based techniques, SimPoint, SMARTS, and random sampling, have the best accuracy, the best speed versus accuracy trade-off, and the least configuration dependence. On the other hand, the reduced input set and truncated execution simulation techniques had generally poor accuracy, were not significantly faster than the sampling-based techniques, and were severely configuration dependent. The final contribution of this paper is a decision tree, which can help architects choose the most appropriate technique for their simulations.

Due to the amount of time required to design a new processor, one set of benchmark programs may be used during the design phase while another may be the standard when the design is finally delivered. Using one benchmark suite to design a processor while using a different, presumably more current, suite to evaluate its ultimate performance may lead to sub-optimal design decisions if there are large differences between the characteristics of the two suites and their respective compilers. We call this changes across time "drift". To evaluate the impact of using yesterday's benchmark and compiler technology to design tomorrow's processors, we compare common benchmarks from the SPEC 95 and SPEC 2000 benchmark suites. Our results yield three key conclusions. First, we show that the amount of drift, for common programs in successive SPEC benchmark suites, is significant. In SPEC 2000, the main memory access time is a far more significant performance bottleneck than in SPEC 95, while less significant SPEC 2000 performance bottlenecks include the L2 cache latency, the L1 I-cache size, and the number of reorder buffer entries. Second, using two different statistical techniques, we show that compiler drift is not as significant as benchmark drift. Third, we show that benchmark and compiler drift can have a significant impact on the final design decisions. Specifically, we use a one-parameter-at-a-time optimization algorithm to design two different year-2000 processors, one optimized for SPEC 95 and the other optimized for SPEC 2000, using the energy-delay product (EDP) as the optimization criterion. The results show that using SPEC 95 to design a year-2000 processor results in an 18.5% larger EDP and a 20.8% higher CPI than using the SPEC 2000 benchmarks to design the corresponding processor. Finally, we make a few recommendations to help computer architects minimize the effects of benchmark and compiler drift.

Operating temperatures have become an important concern in high performance microprocessors. Floorplanning or block-level placement offers excellent potential for thermal optimization through better heat spreading between the blocks, but these optimizations can also impact the throughput of a microarchitecture, measured in terms of the number of instructions per cycle (IPC). In nanometer technologies, global buses can have multicycle delays that depend on the positions of the blocks, and it is important for a floorplanner to be microarchitecturally-aware to be sure that thermal and IPC considerations are appropriately balanced. This paper proposes a methodology for thermally-aware microarchitecture floorplanning. The approach models the interactions between the IPC and the temperature distribution, and incorporates both factors in the floorplanning cost function. Our approach uses transient modeling and optimizes both the peak and the average temperatures, and employs a design of experiments (DOE) based strategy, which effectively captures the huge exponential search space with a small number of cycle-accurate simulations. A comparison with a technique based on previous work indicates that the proposed approach results in good reductions both in the average and the peak temperatures for a range of SPEC benchmarks.

Recent research has proposed statistical simulation as a technique for fast performance evaluation of superscalar microprocessors. The idea in statistical simulation is to measure a program's key performance characteristics, generate a synthetic trace with these characteristics, and simulate the synthetic trace. Due to the probabilistic nature of statistical simulation the performance estimate quickly converges to a solution, making it an attractive technique to efficiently cull a large microprocessor design space. In this paper, we evaluate the efficacy of statistical simulation in exploring the design space. Specifically, we characterize the following aspects of statistical simulation: (i) fidelity of performance bottlenecks, with respect to cycle-accurate simulation of the program, (ii) ability' to track design changes, and (Hi) trade-off between accuracy and complexity in statistical simulation models. In our characterization experiments, we use the Plackett & Burman (P&B) design to systematically stress statistical simulation by creating different performance bottlenecks. The key results from this paper are: (1) Synthetic traces stress at least the same 10 most significant processor performance bottlenecks as the original workload, (2) Statistical simulation can effectively track design changes to identify feasible design points in a large design space of aggressive microarchitectures, (3) Our evaluation of 4 statistical simulation models shows that although a very detailed model is needed to achieve a good absolute accuracy in performance estimation, a simple model is sufficient to achieve good relative accuracy, and (4) The P&B design technique can be used to quickly identify areas to focus on to improve the accuracy of the statistical simulation model.

Due to the long simulation times of the reference input sets, microarchitects resort to alternative techniques to speed up cycle-accurate simulations. However, the reduction in the runtimes comes with an associated loss of accuracy in replicating the characteristics of the reference sets. In addition, the effect of these inaccuracies on the overall performance can vary across different microarchitecture optimizations or enhancements. In this work, we study and compare two such techniques, reduced input sets and statistical sampling, in the context of microarchitecture-aware floorplanning, a physical design stage, where the objective is to find an IPC-optimal global placement of the blocks of a microprocessor. The variation in the IPC results due the insertion of additional flip-flops on some across-chip wires of the processor that have multicycle delays in nanometer technology nodes. The objective of IPC-aware floorplanning is to minimize the amount of pipelining required by the system buses that are critical in determining the system performance. Our results indicate that, although the two techniques exhibit contrasting behavior in quantifying the criticality of bus latencies, the ensuing floorplanning optimization process results in almost identical performance improvements for both reduced input sets and sampling. The reason behind this is that, for discrete optimization problems such as IPC-aware floorplanning, a reasonably accurate relative ordering of performance bottlenecks is sufficient, absolute accuracy is not necessary.

Simulators have become an integral part of the computer architecture research and design process. Since they have the advantages of cost, time, and flexibility, architects use them to guide design space exploration and to quantify the efficacy of an enhancement. However, long simulation times and poor accuracy limit their effectiveness. To reduce the simulation time, architects have proposed several techniques that increase the simulation speed or throughput. To increase the accuracy, architects try to minimize the amount of error in their simulators and have proposed adding statistical rigor to their simulation methodology. Since a wide range of approaches exist and since many of them overlap, this paper describes, classifies, and compares them to aid the computer architect in selecting the most appropriate one.

This paper extends the depth first search (DFS) used in the previously proposed witness string method for generating efficient test vectors. A state pruning method is added that exploits different search heuristics in simultaneous searches. Using an IBM Power4 multiprocessor system with the Berkeley Active Message library, we show that this new method of state pruning is efficient and produces quantitatively better witness strings compared to both pure and guided DFS.

Since across-chip interconnect delays can exceed a clock cycle in nanometer technologies, it has become essential in high performance designs to add flip-flops on wires with multi-cycle delays. Although such a wire pipelining strategy allows higher operating frequencies, it can reduce the delivered performance of a microarchitecture, since the extra flip-flops inserted may increase the operation latencies and stall cycles. Moreover, the addition of latencies on some wires can have a large impact on the overall performance while other wires are relatively insensitive to additional latencies. This varying sensitivity suggests the need for a throughput-aware strategy for pipelining the interconnects that interacts closely with the physical design step, which determines the lengths of these multicycle wires. We use a statistical design of experiments strategy based on a multifactorial design, which intelligently uses a limited number of simulations to rank the importance of the wires. When applied at the floorplanning level, our results show improvements both in the overall system performance and in the total wire length when compared with an existing technique.

Due to the simulation time of the reference input set, architects often use alternative simulation techniques. Although these alternatives reduce the simulation time, what has not been evaluated is their accuracy relative to the reference input set, and with respect to each other. To rectify this deficiency, this paper uses three methods to characterize the reduced input set, truncated execution, and sampling simulation techniques while also examining their speed versus accuracy trade-off and configuration dependence. Finally, to illustrate the effect that a technique could have on the apparent speedup results, we quantify the speedups obtained with two processor enhancements. The results show that: 1) the accuracy of the truncated execution techniques was poor for all three characterization methods and for both enhancements, 2) the characteristics of the reduced input sets are not reference-like, and 3) SimPoint and SMARTS, the two sampling techniques, are extremely accurate and have the best speed versus accuracy trade-offs. Finally, this paper presents a decision tree which can help architects choose the most appropriate technique for their simulations.

Obtaining consistent bandwidth with predictable latency from disk-based storage systems has proven difficult due to the storage system's inability to understand quality of service (QoS) requirements. In this paper, we present a feasibility study of QoS with the object-based storage device (OSD) specification. We look at OSD's ability to provide QoS guarantees for consistent bandwidth with predictable latency. Included in this paper is a description of QoS requirements of a sample application and how these requirements are translated into parameters that are then communicated to, and interpreted by, the OSD. Implementation problems lead to the failure of a hard real-time QoS model, but this failure is not due to the OSD protocol. The paper concludes with a description of how well the revision 9 OSD standard (OSDR9) is able to accommodate QoS. We provide suggestions for improving the OSD specification and its ability to communicate QoS requirements.

Due to cost, time, and flexibility constraints, computer architects use simulators to explore the design space when developing new processors and to evaluate the performance of potential enhancements. However, despite this dependence on simulators, statistically rigorous simulation methodologies are typically not used in computer architecture research. A formal methodology can provide a sound basis for drawing conclusions gathered from simulation results by adding statistical rigor and, consequently, can increase the architect's confidence in the simulation results. This paper demonstrates the application of a rigorous statistical technique to the setup and analysis phases of the simulation process. Specifically, we apply a Plackett and Burman design to: 1) identify key processor parameters, 2) classify benchmarks based on how they affect the processor, and 3) analyze the effect of processor enhancements. Our results showed that, out of the 41 user-configurable parameters in SimpleScalar, only 10 had a significant effect on the execution time. Of those 10, the number of reorder buffer entries and the L2 cache latency were the two most significant ones, by far. Our results also showed that instruction precomputation - a value reuse-like microarchitectural technique - primarily improves the processor's performance by relieving integer ALU contention.

The speculated execution of threads in a multithreaded architecture, plus the branch prediction used in each thread execution unit, allows many instructions to be executed speculatively, that is, before it is known whether they actually needed by the program. In this study, we examine how the load instructions executed on what turn out to be incorrectly executed program paths impact the memory system performance. We find that incorrect speculation (wrong execution) on the instruction and thread-level provides an indirect prefetching effect for the later correct execution paths and threads. By continuing to execute the mispredicted load instructions even after the instruction or thread-level control speculation is known to be incorrect, the cache misses observed on the correctly executed paths can be reduced by 16 to 73 percent, with an average reduction of 45 percent. However, we also find that these extra loads can increase the amount of memory traffic and can pollute the cache. We introduce the small, fully associative wrong execution cache (WEC) to eliminate the potential pollution that can be caused by the execution of the mispredicted load instructions. Our simulation results show that the WEC can improve the performance of a concurrent multithreaded architecture up to 18.5 percent on the benchmark programs tested, with an average improvement of 9.7 percent, due to the reductions in the number of cache misses.

Wireless sensor networks is an emerging paradigm of computing and networking where a node may be selfpowered, and have sensing, computing, and communication capabilities. They have been proposed for use in a wide variety of applications. The objective of this article is to describe a wireless sensor network for monitoring of the health of aircraft engines. We describe the architecture of the wireless sensor network along with how it fits into the general area of wireless sensor networks.

Advanced molecular nanotechnology devices are expected to have exceedingly high transient fault rates and large numbers of inherent device defects compared to conventional CMOS devices. We introduce the recursive nanobox processor grid as an application specific, fault-tolerant, parallel computing system designed for fabrication with unreliable nanotechnology devices. In this initial study we construct VHDL models of the nanobox processor cell ALU and evaluate the effectiveness of our recursive fault masking approach in the presence of random transient errors. Our analysis shows that the ALU can calculate correctly 100 percent of the time with raw FIT (failures in time) rates as high as 10/sub 23/. We achieve this error correction with an area overhead on the order of 9x, which is quite reasonable given the high integration densities expected with nanodevices.

Predicting the values that are likely to be produced by instructions has been suggested as a way of increasing the instruction-level parallelism available in a superscalar processor. One of the potential difficulties in cost-effectively predicting values for a given instruction, however, is selecting the proper type of predictor, such as a last-value predictor, a stride predictor, or a context-based predictor. We propose a compiler-directed classification scheme that statically partitions all of the instructions in a program into several groups, each of which is associated with a specific value predictability pattern. This value predictability pattern is encoded into the instructions to identify the type of value predictor that will be best suited for predicting the values that are likely to be produced by each instruction at runtime. Both a profile-based compiler implementation and an implementation based on the GCC compiler are studied to show the performance bounds for the proposed technique. Our simulations using an extension to the SimpleScalar tool set and the SPEC95 and SPEC2000 benchmark programs indicate that this approach can efficiently use the limited hardware resources in superscalar processors. This static partitioning approach produces better performance than a dynamically partitioned approach and a simple round-robin distribution approach for a given hardware configuration. Finally, we demonstrate the connection between value locality behavior and source-level program structures, thereby leading to a deeper understanding of the causes of this behavior.

Due to cost, time, and flexibility constraints, simulators are often used to explore the design space when developing new processor architectures, as well as when evaluating the performance of new processor enhancements. However, despite this dependence on simulators, statistically rigorous simulation methodologies are not typically used in computer architecture research. A formal methodology can provide a sound basis for drawing conclusions gathered from simulation results by adding statistical rigor, and consequently, can increase confidence in the simulation results. This paper demonstrates the application of a rigorous statistical technique to the setup and analysis phases of the simulation process. Specifically, we apply a Plackett and Burman design to: (1) identify key processor parameters; (2) classify benchmarks based on how they affect the processor; and (3) analyze the effect of processor performance enhancements. Our technique expands on previous work by applying a statistical method to improve the simulation methodology instead of applying a statistical model to estimate the performance of the processor.

The fact that instructions in programs often produce repetitive results has motivated researchers to explore various techniques, such as value prediction and value reuse, to exploit this behavior. Value prediction improves the available instruction-level parallelism (ILP) in superscalar processors by allowing dependent instructions to be executed speculatively after predicting the values of their input operands. Value reuse, on the other hand, tries to eliminate redundant computation by storing the previously produced results of instructions and skipping the execution of redundant instructions. Previous value reuse mechanisms use a single instruction or a naturally formed instruction group, such as a basic block, a trace, or a function, as the reuse unit. These naturally-formed instruction groups are readily identifiable by the hardware at runtime without compiler assistance. However, the performance potential of a value reuse mechanism depends on its reuse detection time, the number of reuse opportunities, and the amount of work saved by skipping each reuse unit. Since larger instruction groups typically have fewer reuse opportunities than smaller groups, but they provide greater benefit for each reuse-detection process, it is very important to find the balance point that provides the largest overall performance gain. We propose a new mechanism called subblock reuse. Subblocks are created by slicing basic blocks either dynamically or with compiler guidance. The dynamic approaches use the number of instructions, numbers of inputs and outputs, or the presence of store instructions to determine the subblock boundaries. The compiler-assisted approach slices basic blocks using data-flow considerations to balance the reuse granularity and the number of reuse opportunities.

During the course of a program's execution, a processor performs mangy trivial computations; that is, computations that can be simplified or where the result is zero, one, or equal to one of the input operands. This paper shows that, despite compiling a program with aggressive optimizations (-O3), approximately 30% of all arithmetic instructions, which account for 12% of all dynamic instructions, are trivial computations. The amount of trivial computation is not heavily dependent on the program's specific input values. Our results show that eliminating trivial computations dynamically at run-time yields an average speedup of 8% for a typical processor. Even for a very aggressive processor (i.e. one with no functional unit constraints), the average speedup is still 6%. It also is important to note that the area cost (i.e. hardware) required to dynamically detect and eliminate these trivial computations is very low, consisting of only a few comparators and multiplexers.

Abstract Parallel execution of application programs on a multiprocessor system may lead to performance degradation if the workload of a parallel region is not large enough to amortize the overheads associated with the parallel execution. Furthermore, if too many processes are running on the system in a multiprogrammed environment, the performance of the parallel application may degrade due to resource contention. This work proposes a comprehensive dynamic processor allocation scheme that takes both program behavior and system load into consideration when dynamically allocating processors. This mechanism was implemented on the Solaris operating system to dynamically control the execution of parallel C and Java application programs. Performance results show the effectiveness of this scheme in dynamically adapting to the current execution environment and program behavior, and that it outperforms a conventional time‐shared system. Copyright © 2002 John Wiley & Sons, Ltd.

Value prediction has been suggested as a way to increase the instruction-level parallelism available in a superscalar processor. One of the potential difficulties in cost-effectively predicting values for a given instruction, however, is selecting the proper type of predictor. We propose a compiler-directed classification scheme that statically partitions instructions in a program into several groups, each of which is associated with a specific value predictability pattern. This value predictability pattern is encoded into the instructions to identify the type of value predictor that can be best suited for each instruction at run-time. Both an ideal profile-based compiler implementation and an implementation based on the GCC compiler are studied. We use execution-driven simulation and SPEC95 and SPEC2000 benchmarks to study the performance of this approach. This work also demonstrates the connection between value locality and source-level program structures thereby leading to a deeper understanding of the causes of this behavior.

Abstract Parallel applications typically do not perform well in a multiprogrammed environment that uses time‐sharing to allocate processor resources to the applications' parallel threads. Co‐scheduling related parallel threads, or statically partitioning the system, often can reduce the applications' execution times, but at the expense of reducing the overall system utilization. To address this problem, there has been increasing interest in dynamically allocating processors to applications based on their resource demands and the dynamically varying system load. TheLoop‐Level Process Control (LLPC)policy (Yue K, Lilja D. Efficient execution of parallel applications in multiprogrammed multiprocessor systems.10th International Parallel Processing Symposium, 1996; 448–456) dynamically adjusts the number of threads an application is allowed to execute based on the application's available parallelism and the overall system load. This study demonstrates the feasibility of incorporating the LLPC strategy into an existing commercial operating system and parallelizing compiler and provides further evidence of the performance improvement that is possible using this dynamic allocation strategy. In this implementation, applications are automatically parallelized and enhanced with the appropriate LLPC hooks so that each application interacts with the modified version of the Solaris operating system. The parallelism of the applications are then dynamically adjusted automatically when they are executed in a multiprogrammed environment so that all applications obtain a fair share of the total processing resources. Copyright © 2001 John Wiley & Sons, Ltd.

This paper presents a new parallelization model, called coarse-grained thread pipelining, for exploiting speculative coarse-grained parallelism from general-purpose application programs in shared-memory multiprocessor systems. This parallelization model, which is based on the fine-grained thread pipelining model proposed for the superthreaded architecture, allows concurrent execution of loop iterations in a pipelined fashion with runtime data-dependence checking and control speculation. The speculative execution combined with the runtime dependence checking allows the parallelization of a variety of program constructs that cannot be parallelized with existing runtime parallelization algorithms. The pipelined execution of loop iterations in this new technique results in lower parallelization overhead than in other existing techniques. We evaluated the performance of this new model using some real applications and a synthetic benchmark. These experiments show that programs with a sufficiently large grain size compared to the parallelization overhead obtain significant speedup using this model. The results from the synthetic benchmark provide a means for estimating the performance that can be obtained from application programs that will be parallelized with this model. The library routines developed for this thread pipelining model are also useful for evaluating the correctness of the codes generated by the superthreaded compiler and in debugging and verifying the simulator for the superthreaded processor.

A single node of a modern scalable multiprocessor consists of several ASICs comprising tens of millions of gates. This level of integration and complexity imposes an enormous onus on the verification process. A variety of tools, ranging from discrete-event logic simulation to formal model checking, can be used to attack this problem. Unfortunately, conventional simulation techniques, with their primitive interface to the hardware (i.e. test vectors), are inadequate tools for reasoning about the correctness of complex architectural features, such as cache coherence protocols and memory consistency models. Similarly, model checkers offer very limited utility on such large designs. We have previously proposed a novel verification framework, called Raven, that addresses many of these challenges. In this paper we examine the performance implications of verifying systems at higher levels of abstraction. A detailed performance analysis is conducted to compare this higher-level approach against an equivalent Verilog test bench. We establish lower and upper bounds on the performance of the Raven environment executing on a single-processor on a set of distributed processors, and on a shared-memory multiprocessor.

Parallel execution of application programs on a multiprocessor system may lead to performance degradation if the workload of a parallel region is not large enough to amortize the overheads associated with the parallel execution. Furthermore, if too many processes are running on the system in a multiprogrammed environment, the performance of the parallel application may degrade due to resource contention. We propose a comprehensive dynamic processor allocation scheme that takes both program behavior and system load into consideration when dynamically allocating processors. We implemented this mechanism in the Java run-time system on Solaris to dynamically control the execution of parallel Java application programs. Performance results show the effectiveness of this scheme in dynamically adapting to the current execution environment and that it outperforms a conventional time-shared system.

This paper presents a new approach to improve performance of Java programs by extending the superthreaded speculative execution model to exploit coarse-grained parallelism on a shared-memory multiprocessor system. The parallelization model, called Java Speculative MultiThreading (JavaSpMT), combines control speculation with run-time dependence checking to parallelize a wide variety of loop constructs, including do-while loops, that cannot be parallelized using standard parallelization techniques. JavaSpMT is implemented using the standard Java multithreading mechanism and the parallelization is expressed using a Java source-to-source transformation. Thus, the transformed programs are still portable to any shared-memory multiprocessor system with a Java Virtual Machine implementation that supports native threads.

Speculative execution and instruction reuse are two important strategies that have been investigated for improving processor performance. Value prediction at the instruction level has been introduced to allow even more aggressive speculation and reuse than previous techniques. This study suggests that using compiler support to extend value reuse to a coarser granularity than a single instruction, such as a basic block, may have substantial performance benefits. We investigate the input and output values of basic blocks and find that these values can be quite regular and predictable. For the SPEC benchmark programs evaluated, 90 percent of the basic blocks have fewer than four register inputs, five live register outputs, four memory inputs, and two memory outputs. About 16 to 41 percent of all the basic blocks are simply repeating earlier calculations when the programs are compiled with the -O2 optimization level in the GCC compiler. Compiler optimizations, such as loop-unrolling and function inlining, affect the sizes of basic blocks, but have no significant or consistent impact on their value locality, nor the resulting performance. Based on these results, we evaluate the potential benefit of basic block reuse using a novel mechanism called the block history buffer. This mechanism records input and live output values of basic blocks to provide value reuse at the basic block level. Simulation results show that using a reasonably sized block history buffer to provide basic block reuse in a 4-way issue superscalar processor can improve execution time for the tested SPEC programs by 1 to 14 percent, with an overall average of 9 percent when using reasonable hardware assumptions.

Algorithms for scheduling independent tasks on to the processors of a multiprocessor system must trade-off processor load balance, memory locality, and scheduling overhead. Most existing algorithms, however, do not adequately balance these conflicting factors. This paper introduces the self-adjusting dynamic scheduling (SADS) class of algorithms that use a unified cost model to explicitly account for these factors at runtime. A dedicated processor performs scheduling in phases by maintaining a tree of partial schedules and incrementally assigning tasks to the least-cost schedule. A scheduling phase terminates whenever any processor becomes idle, at which time partial schedules are distributed to the processors. An extension of the basic SADS algorithm, called DBSADS, controls the scheduling overhead by giving higher priority to partial schedules with more task-to-processor assignments. These algorithms are compared to two distributed scheduling algorithms within a database application on an Intel Paragon distributed memory multiprocessor system.

Value prediction at the instruction level has been introduced to allow more aggressive speculation and reuse than previous techniques. We investigate the input and output values of basic blocks and find that these values can be quite regular and predictable, suggesting that using compiler support to extend value prediction and reuse to a coarser granularity may have substantial performance benefits. For the SPEC benchmark programs evaluated, 90% of the basic blocks have fewer than 4 register inputs, 5 live register outputs, 4 memory inputs and 2 memory outputs. About 16% to 41% of all the basic blocks are simply repeating earlier calculations when the programs are compiled with the -O2 optimization level in the GCC compiler. We evaluate the potential benefit of basic block reuse using a novel mechanism called a block history buffer. This mechanism records input and live output values of basic blocks to provide value prediction and reuse at the basic block level. Simulation results show that using a reasonably sized block history buffer to provide basic block reuse in a 4-way issue superscalar processor can improve execution time for the tested SPEC programs by 1% to 14% with an overall average of 9%.

Data prefetching has been proposed as a means of hiding the memory access latencies of data referencing patterns that defeat caching strategies. Prefetching techniques that either use special cache logic to issue prefetches or that rely on the processor to issue prefetch requests typically involve some compromise between accuracy and instruction overhead. A data prefetch controller (DPC) is proposed that combines low instruction overhead with the flexibility and accuracy of a compiler-directed prefetch mechanism. At run-time, the processor and prefetch controller each execute separate, but cooperating instruction streams. Simulations in which both programs are generated from a single application source file using a commercial compiler show that the prefetch controller can significantly improve the cache utilization and execution time of several SPECfp95 benchmarks. Performance comparisons also indicate that the DPC outperforms software prefetching techniques and prefetching via a hardware reference prediction table.

The common single-threaded execution model limits processors to exploiting only the relatively small amount of instruction-level parallelism that is available in application programs. The superthreaded processor, on the other hand, is a concurrent multithreaded architecture (CMA) that can exploit the multiple granularities of parallelism that are available in general-purpose application programs. Unlike other CMAs that rely primarily on hardware for run-time dependence detection and speculation, the superthreaded processor combines compiler-directed thread-level speculation of control and data dependences with run-time data dependence verification hardware. This hybrid of a superscalar processor and a multiprocessor-on-a-chip can utilize many of the existing compiler techniques used in traditional parallelizing compilers developed for multiprocessors. Additional unique compiler techniques, such as the conversion of data speculation into control speculation, are also introduced to generate the superthreaded code and to enhance the parallelism between threads. A detailed execution-driven simulator is used to evaluate the performance potential of this new architecture. It is found that a superthreaded processor can achieve good performance on complex application programs through this close coupling of compile-time and run-time information.

The different types of messages used by a parallel application program executing in a distributed computing system can each have unique characteristics so that no single communication network can produce the lowest latency for all messages. For instance, short control messages may be sent with the lowest overhead on one type of network, such as Ethernet, while bulk data transfers may be better suited to a different type of network, such as Fibre Channel or HIPPI. This work investigates how to exploit multiple heterogeneous communication networks that interconnect the same set of processing nodes using a set of techniques we call performance-based path determination (PBPD). The performance-based path selection (PBPS) technique selects the best (lowest latency) network among several for each individual message to reduce the communication overhead of parallel programs. The performance-based path aggregation (PBPA) technique, on the other hand, aggregates multiple networks into a single virtual network to increase the available bandwidth. We test the PBPD techniques on a cluster of SGI multiprocessors interconnected with Ethernet, Fibre Channel, and HiPPI networks using a custom communication library built on top of the TCP/IP protocol layers. We find that PBPS can reduce communication overhead in applications compared to using either network alone, while aggregating networks into a single virtual network can reduce communication latency for bandwidth-limited applications. The performance of the PBPD techniques depends on the mix of message sizes in the application program and the relative overheads of the networks, as demonstrated in our analytical models.

We propose a new universal High-Level Information (HLI) format to effectively integrate front-end and back-end compilers by passing front-end information to the back-end compiler. Importing this information into an existing back-end leverages the state-of-the-art analysis and transformation capabilities of existing front-end compilers to allow the back-end greater optimization potential than it has when relying on only locally-extracted information. A version of the HLI has been implemented in the SUIF parallelizing compiler and the GCC back-end compiler. Experimental results with the SPEC benchmarks show that HLI can provide GCC with substantially more accurate data dependence information than it can obtain on its own. Our results show that the number of dependence edges in GCC can be reduced by an average of 48% for the integer benchmark programs and an average of 54% for the floating-point benchmark programs studied, which provides greater flexibility to GCC's code scheduling pass. Even with the scheduling optimization limited to basic blocks, the use of HLI produces moderate speedups compared to using only GCC's dependence tests when the optimized programs are executed on MIPS R4600 and R10000 processors.

The cache replacement policy is one of the factors that determines the effectiveness of cache memories. We study the impact of incorporating the cache block coherence state information in the random replacement policy in a shared memory multiprocessor. We assign replacement priority to each cache block within a set based on its state. To reduce the probability of replacing a recently accessed block and to adapt to the program's access patterns, we also associate with each set an MRU (Most Recently Used) state. The MRU state causes the lowest replacement priority to be assigned to the blocks in the same state as the MRU state. Our evaluations indicate that, with the appropriate priority assignment and a set associativity size less than 16, the proposed policy can outperform the Random and Random & Invalid policies and, in some cases, can even outperform the LRU policy.

This thesis presents a new parallelization model, called coarse-grained thread pipelining, for exploiting coarse-grained parallelism from general-purpose application programs in shared-memory multiprocessor systems. This parallelization model, which is based on the fine-grained thread pipelining model proposed for the superthreaded architecture [7], allows concurrent execution of loop iterations in a pipelined fashion with run-time data dependence checking and control speculation. The speculative execution combined with the run-time dependence analysis allows the parallelization of a variety of program constructs that cannot be parallelized with existing run-time parallelization algorithms. The pipelined execution of loop iterations in this new technique results in lower parallelization overhead than in other existing techniques. We evaluated the performance of our coarse-grained thread pipelining model using some real applications and a synthetic benchmark. These experiments show that...

In developing a simulator for a new processor architecture, it often is not clear whether it is more efficient to write a new simulator or to modify an existing simulator. Writing a new simulator forces the processor architect to develop or adapt all of the related software tools. However, modifying an existing simulator and related tools, which are usually not well-documented, can be time-consuming and error-prone. We describe the SImulator for Multithreaded Computer Architectures (SIMCA) that was developed with the primary goal of obtaining a functional simulator as quickly as possible to begin evaluating the superthreaded architecture. The performance of the simulator itself was important, but secondary. We achieved our goal using a technique called process-pipelining that exploits the unique features of this new architecture to hide the details of the underlying simulator. This approach allowed us to quickly produce a functional simulator whose performance is only 3.8-4.9 times slower than the base simulator.

Several parallel programming languages, libraries and environments have been developed to ease the task of writing programs for multiprocessors. Proponents of each approach often point out various language features that are designed to provide the programmer with a simple programming interface. However, virtually no data exist that quantitatively evaluate the relative ease of use of different parallel programming languages. The paper borrows techniques from the software engineering field to quantify the complexity of three predominant programming models: shared-memory, message-passing and high-performance Fortran. It is concluded that traditional software complexity metrics are effective indicators of the relative complexity of parallel programming languages. The impact of complexity on run-time performance is also discussed in the context of message-passing vs. HPF on an IBM SP2. © 1998 John Wiley & Sons, Ltd.

Several parallel programming languages, libraries and environments have been developed to ease the task of writing programs for multiprocessors. Proponents of each approach often point out various language features that are designed to provide the programmer with a simple programming interface. However, virtually no data exists that quantitatively evaluates the relative ease of use of different parallel programming languages. The paper borrows techniques from the software engineering field to quantify the complexity of three predominate programming models: shared memory, message passing and High-Performance Fortran. It is concluded that traditional software complexity metrics are effective indicators of the relative complexity of parallel programming languages. The impact of complexity on run-time performance is also discussed in the context of message passing versus HPF on an IBM SP2.

Heterogeneity is becoming quite common in distributed parallel computing systems, both in processor architectures and in communication networks. Different types of networks have different performance characteristics, while different types of messages may have different communication requirements. In this work, we analyze two techniques for exploiting these heterogeneous characteristics and requirements to reduce the communication overhead of parallel application programs executed on distributed computing systems. The performance based path selection (PBPS) technique selects the best (lowest latency) network among several for each individual message, while the second technique aggregates multiple networks into a single virtual network. We present a general approach for applying and evaluating these techniques to a distributed computing system with multiple interprocessor communication networks. We also generate performance curves for a cluster of IBM workstations interconnected with Ethernet, ATM, and Fibre Channel networks. As we show with several of the NAS benchmarks, these curves can be used to estimate the potential improvement in communication performance that can be obtained with these techniques, given some simple communication characteristics of an application program.

Existing techniques for sharing the processing resources in multiprogrammed shared-memory multiprocessors, such as time-sharing, space-sharing, and gang-scheduling, typically sacrifice the performance of individual parallel applications to improve overall system utilization. We present a new processor allocation technique called Loop-Level Process Control (LLPC) that dynamically adjusts the number of processors an application is allowed to use for the execution of each parallel section of code, based on the current system load. This approach exploits the maximum parallelism possible for each application without overloading the system. We implement our scheme on a Silicon Graphics Challenge multiprocessor system and evaluate its performance using applications from the Perfect Club benchmark suite and synthetic benchmarks. Our approach shows significant improvements over traditional time-sharing and gang-scheduling. It has performance comparable to, or slightly better than, static space-sharing, but our strategy is more robust since, unlike static space-sharing, it does not require a priori knowledge of the applications' parallelism characteristics.

Efficiently scheduling parallel tasks on to the processors of a shared-memory multiprocessor is critical to achieving high performance. Given perfect information at compile-time, a static scheduling strategy can produce an assignment of tasks to processors that ideally balances the load among the processors while minimizing the run-time scheduling overhead and the average memory referencing delay. Since perfect information is seldom available, however, dynamic scheduling strategies distribute the task assignment function to the processors by having idle processors allocate work to themselves from a shared queue. While this approach can improve the load balancing compared to static scheduling, the time required to access the shared work queue adds directly to the overall execution time. To overlap the time required to dynamically schedule tasks with the execution of the tasks, we examine a class of self-adjusting dynamic scheduling (SADS) algorithms that centralizes the assignment of tasks to processors. These algorithms dedicate a single processor of the multiprocessor to perform a novel on-line branch-and-bound technique that dynamically computes partial schedules based on the loads of the other processors and the memory locality (affinity) of the tasks and the processors. Our simulation results show that this centralized scheduling outperforms self-scheduling algorithms even when using only a small number of processors.

We evaluate the performance impact of two different write-buffer configurations (one word per buffer entry and one block per buffer entry) and two different write policies (write-through and write-back), when using the partial block invalidation coherence mechanism in a shared-memory multiprocessor. Using an execution-driven simulator, we find that the one word per entry buffer configuration with a write-back policy is preferred for small write-buffer sizes when both buffers have an equal number of data words, and when they have equal hardware cost. Furthermore, when partial block invalidation is supported, we find that a write-through policy is preferred over a write-back policy due to its simpler cache hit detection mechanism, its elimination of write-back transactions, and its competitive-performance when the write-buffer is relatively large.

Abstract There has been a recent increase of interest in heterogeneous computing systems, due partly to the fact that a single parallel architecture may not be adequate for exploiting all of a program's available parallelism. In some cases, heterogeneous systems have been shown to produce higher performance for lower cost than a single large machine. However, there has been only limited work on developing techniques and frameworks for partitioning and scheduling applications across the components of a heterogeneous system. In this paper we propose a general model for describing and evaluating heterogeneous systems that considers the degree of uniformity in the processing elements and the communication channels as a measure of the heterogeneity in the system. We also propose a class of dynamic scheduling algorithms for a heterogeneous computing system interconnected with an arbitrary communication network. These algorithms execute a novel optimization technique to dynamically compute schedules based on the potentially non‐uniform computation and communication costs on the processors of a heterogeneous system. A unique aspect of these algorithms is that they easily adapt to different task granularities, to dynamically varying processor and system loads, and to systems with varying degrees of heterogeneity. Our simulations are designed to facilitate the evaluation of different scheduling algorithms under varying degrees of heterogeneity. The results show improved performance for our algorithms compared to the performance resulting from existing scheduling techniques.

Abstract With the variety of computer architectures available today, it is often difficult to determine which particular type of architecture will provide the best performance on a given application program. In fact, one type of architecture may be well suited to executing one section of a program while another architecture may be better suited to executing another section of the same program. One potentially promising approach for exploiting the best features of different computer architectures is to partition an application program to simultaneously execute on two or more types of machines interconnected with a high‐speed communication network. A fundamental difficulty with this heterogeneous computing, however, is the problem of determining how to partition the application program across the interconnected machines. The goal of this paper is to show how a programmer or a compiler can use a model of a heterogeneous system to determine the machine on which each subtask should be executed. This technique is illustrated with a simple model that relates the relative performance of two heterogeneous machines to the communication time required to transfer partial results across their interconnection network. Experiments with a Connection Machine CM‐200 demonstrate how to apply this model to partition two different application programs across the sequential front‐end processor and the parallel back‐end array.

Cache coherence schemes that dynamically adapt to memory referencing patterns have been proposed to improve coherence enforcement in shared-memory multiprocessors. By using only run-time information, however, these existing schemes are incapable of looking ahead in the memory referencing stream. We present a combined hardware-software strategy that uses the predictive capability of the compiler to select updating or invalidating for each write reference. To determine the potential performance improvement that can be achieved with this optimization, three different levels of compiler capabilities are examined. Simulations using memory traces show that with an ideal compiler, this optimization can potentially reduce the miss ratio by 0.4% to 15% compared to an invalidating-only scheme, while reducing the generated network traffic by 13% to 94% compared to an updating-only scheme. In addition, this optimization can potentially reduce the miss ratio by up to 13%, while reducing the generated network traffic by up to 92%, compared to a dynamic adaptive scheme. Furthermore, performance can be potentially improved even with a compiler capable of performing only imprecise array subscript analysis and no interprocedural analysis.>

Dynamically tagged directories are memory-efficient mechanisms for maintaining cache coherence in shared-memory multiprocessors. These directories use special-purpose caches of pointers that are subject to two types of overflow: (1) pointer overflow, which limits the maximum sharing of a memory block, and (2) set overflow, which forces the premature invalidation of cached blocks. We propose a superassociative tagged directory that can preserve some of the cached copies of a memory block when a set overflows by allowing multiple address tags in the same set to contain the same address value. Verilog descriptions are used to estimate its implementation cost and timing delay, and a multiprocessor cache simulator is used to evaluate its performance.>

Techniques for scheduling parallel tasks on to the processors of a multiprocessor architecture must tradeoff three interrelated factors: 1) scheduling and synchronization costs, 2) load balancing, and 3) memory locality. Current scheduling techniques typically consider only one or two of these three factors at a time. We propose a novel Self- Adjusting Scheduling (SAS) algorithm that addresses all three factors simultaneously. This algorithm dedicates a single processor to execute an on-line branch-and-bound algorithm to search for partial schedules concurrent with the execution of tasks previously assigned to the remaining processors. This overlapped scheduling and execution, along with self-adjustment of duration of partial scheduling periods reduces scheduling and synchronization costs significantly. To satisfy the load-balancing and locality management, SAS introduces a unified cost model that accounts for both of these factors simultaneously. We compare the simulated performance of SAS with the Affinity Scheduling algorithm (AFS). The results of our experiments demonstrate that the potential loss of performance caused by dedicating a processor to scheduling is outweighed by the higher performance produced by SAS's dynamically adjusted schedules, even in systems with a small number of processors. SAS is a general on-line optimization technique that can be applied to a variety of dynamic scheduling problems.

Several techniques have been used to reduce the performance impact of process synchronization in fine-grained multiprocessor systems. These existing techniques tend to have long synchronization times or high shared-bus use, or they require complex and expensive hardware. A new technique is presented that uses distributed hardware locking queues to reduce both contention and latency to the minimum values that can be obtained using a shared-bus. This technique is shown to require at most two shared-bus transactions, with one transaction being typical. The latency for process continuation after obtaining a lock is reduced to near zero. Barrier synchronization using this distributed mechanism requires only one shared-bus transaction per processor involved in the barrier. This new technique is scalable and applicable to both new architectures and to existing systems, and is less complex than other hardware solutions.

Both hardware-controlled and compiler-directed mechanisms have been proposed for maintaining cache coherence in large-scale shared-memory multiprocessors, but both of these approaches have significant limitations. We examine the potential performance improvement of a new software-hardware controlled cache coherence mechanism. This approach augments the run-time information available to a directory-based coherence mechanism with compile-time analysis that statically identifies write references that cannot cause coherence problems and writes that should be written through to memory. These references are marked as not needing to send invalidation messages to thereby reduce the network traffic produced by the directory while maintaining cache consistency. For those memory references that are ambiguous, due to conditional branches, or due to the need for complex data flow analysis, for instance, the compiler conservatively marks the references and relies on the hardware directory to ensure coherence. Trace-driven simulations are used to emulate the compile-time analysis on memory traces and to estimate potential performance improvement that could be expected from a compiler performing this optimization on the Perfect Club benchmark programs. By reducing the number of invalidations, this optimized directory scheme is capable of reducing the processor-memory network traffic by up to 54 percent compared to an unoptimized directory mechanism. In addition, the overall miss ratio can be reduced up to 42 percent due to a corresponding reduction in the number of write misses.

Trace-driven simulations of numerical Fortran programs are used to study the impact of the parallel loop scheduling strategy on data prefetching in a shared memory multiprocessor with private data caches. The simulations indicate that to maximize memory performance, it is important to schedule blocks of consecutive iterations to execute on each processor, and then to adaptively prefetch single-word cache blocks to match the number of iterations scheduled. Prefetching multiple single-word cache blocks on a miss reduces the miss ratio by approximately 5% to 30% compared to a system with no prefetching. In addition, the proposed adaptive prefetching scheme further reduces the miss ratio while significantly reducing the false sharing among cache blocks compared to nonadaptive prefetching strategies. Reducing the false sharing causes fewer coherence invalidations to be generated, and thereby reduces the total network traffic. The impact of the prefetching and scheduling strategies on the temporal distribution of coherence invalidations also is examined. It is found that invalidations tend to be evenly distributed throughout the execution of parallel loops, but tend to be clustered when executing sequential program sections. The distribution of invalidations in both types of program sections is relatively insensitive to the prefetching and scheduling strategy.>

Dynamiically tagged directories have been recently proposed as a memory-efficient mechanism for maintaining cache coherence in large-scale shared-memory multiprocessors. In order to efficiently use these directories, the number of pointer operations must be minimized and pointers should be allocated as late as possible. If pointers are allocated too early, frequent pointer overflow will occur, which in turn may cause cache thrashing.

Efficiently maintaining cache coherence is a major problem in large-scale shared memory multiprocessors. Hardware directory coherence schemes have very high memory requirements, while software-directed schemes must rely on imprecise compile-time memory disambiguation. Recently proposed dynamically tagged directory schemes allocate pointers to blocks only as they are referenced, which significantly reduces their memory requirements, but they still allocate pointers to blocks that do not need them. The authors present two compiler optimizations that exploit the high-level sharing information available to the compiler to further reduce the size of a tagged directory by allocating pointers only when necessary. Trace-driven simulations are used to show that the performance of this combined hardware-software approach is comparable to other coherence schemes, but with significantly lower memory requirements. In addition, these simulations suggest that this approach is less sensitive to the quality of the memory disambiguation and interprocedural analysis performed by the compiler than software-only coherence schemes.>

Efficiently maintaining cache coherence is a major problem in large-scale shared memory multiprocessors.Hardware directory schemes have very high memory requirements, while software-directed schemes must rely on imprecise compile-time memory disambiguation.Recently proposed dynamic directory schemes allocate pointers to blocks only as they are referenced, which significantly reduces their memory requirements, but they still allocate pointers to blocks that do not need them.We show how compiler marking can further reduce the directory size by allocating pointers only when necessary.Using trace-driven simulations, we find that the performance of this new approach is comparable to other coherence schemes, but with significantly lower memory requirements.