1280007
Memory Prefetching Using Adaptive Stream Detection
We present adaptive stream detection, a simple technique for modulating the aggressiveness of a stream prefetcher to match a workload's observed spatial locality. We use this concept to design a prefetcher that resides on an on-chip memory controller. The result is a prefetcher with small hardware costs that can exploit workloads with low amounts of spatial locality. Using highly accurate simulators for the IBM Power5+, we show that this prefetcher improves performance of the SPEC2006fp benchmarks by an average of 32.7% when compared against a Power5+ that performs no prefetching. On a set of 5 commercial benchmarks that have low spatial locality, this prefetcher improves performance by an average of 15.1%. When compared against a typical Power5+ that does perform processor-side prefetching, the average performance improvement of these benchmark suites is 10.2% and 8.4%. We also evaluate the power and energy impact of our technique. For the same benchmark suites, DRAM power consumption increases by less than 3%, while energy usage decreases by 9.8% and 8.2%, respectively. Moreover, the power consumption of the prefetcher itself is low; it is estimated to increase the power consumption of the Power5+ chip by 0.06%
5795237
The portable parallel implementation of two novel mathematical biology algorithms in ZPL
This paper shows that mathematical models of biological pattern formation are ideally suited to data parallelism. We present two new algorithms, one for simulating the dynamic structure of fibroblasts, and the other for studying the self-organization of motile bacteria. We describe implementations of these algorithms using a high level data parallel language called ZPL, and we give performance results for the Kendall Square Research KSR-2 and the Intel Paragon that include comparisons against sequential Fortran.
15307682
Accommodating polymorphic data decompositions in explicitly parallel programs
Explicitly parallel programs have the potential for greater performance than their implicitly parallel counterparts. However, this benefit can be accompanied by additional programming difficulties. We address one particular problem that has implications for both scalability and portability: the need for programs do accommodate diverse data decompositions. We explain why programs with explicit communication have difficulties in handling changes in data decomposition, and we present a solution to this problem which involves the notions of derivative functions and configuration parameters. We illustrate the technique by using three different data decompositions to solve the Modified Gram-Schmidt method on four parallel machines.<<ETX>>
7870525
Adaptive History-Based Memory Schedulers
As memory performance becomes increasingly important to overall system performance, the need to carefully schedule memory operations also increases. This paper presents a new approach to memory scheduling that considers the history of recently scheduled operations. This history-based approach provides two conceptual advantages: (1) it allows the scheduler to better reason about the delays associated with its scheduling decisions, and (2) it allows the scheduler to select operations so that they match the program's mixture of Reads and Writes, thereby avoiding certain bottlenecks within the memory controller. We evaluate our solution using a cycle-accurate simulator for the recently announced IBM Power5. When compared with an in-order scheduler, our solution achieves IPC improvements of 10.9% on the NAS benchmarks and 63% on the data-intensive Stream benchmarks. Using microbenchmarks, we illustrate the growing importance of memory scheduling in the context of CMP's, hardware controlled prefetching, and faster CPU speeds.
1057171
ZPL's WYSIWYG performance model
ZPL is a parallel array language designed for high performance scientific and engineering computations. Unlike other parallel languages, ZPL is founded on a machine model (the CTA) that accurately abstracts contemporary MIMD parallel computers. This makes it possible to correlate ZPL programs with machine behavior. As a result, programmers can reason about how code will perform on a typical parallel machine and thereby make informed decisions between alternative programming solutions. The paper describes ZPL's performance model and its syntactic cues for conveying operation cost. The what you see is what you get (WYSIWYG) nature of ZPL operations is demonstrated on the IBM SP-2, Intel Paragon, SGI Power Challenge, and Cray T3E. Additionally, the model is used to evaluate two algorithms for matrix multiplication. Experiments show that the performance model correctly predicts the faster solution on all four platforms for a range of problem sizes.
9009444
A Portable Parallel N-Body Solver
We present parallel solutions for direct and fast n-body solvers written in the ZPL language. We describe the direct solver, compare its performance against a sequential C program, and show performance results for two very different parallel machines; the KSR-2 and the Paragon. We also discuss the implementation of the fast solver in ZPL, including factors pertinent to data movement.
626075
Neural methods for dynamic branch prediction
This article presents a new and highly accurate method for branch prediction. The key idea is to use one of the simplest possible neural methods, the perceptron, as an alternative to the commonly used two-bit counters. The source of our predictor's accuracy is its ability to use long history lengths, because the hardware resources for our method scale linearly, rather than exponentially, with the history length. We describe two versions of perceptron predictors, and we evaluate these predictors with respect to five well-known predictors. We show that for a 4 KB hardware budget, a simple version of our method that uses a global history achieves a misprediction rate of 4.6% on the SPEC 2000 integer benchmarks, an improvement of 26% over gshare. We also introduce a global/local version of our predictor that is 14% more accurate than the McFarling-style hybrid predictor of the Alpha 21264. We show that for hardware budgets of up to 256 KB, this global/local perceptron predictor is more accurate than Evers' multicomponent predictor, so we conclude that ours is the most accurate dynamic predictor currently available. To explore the feasibility of our ideas, we provide a circuit-level design of the perceptron predictor and describe techniques that allow our complex predictor to operate quickly. Finally, we show how the relatively complex perceptron predictor can be used in modern CPUs by having it override a simpler, quicker Smith predictor, providing IPC improvements of 15.8% over gshare and 5.7% over the McFarling hybrid predictor.
10271144
Robust image authentication method surviving JPEG lossy compression
Image authentication verifies the originality of an image by detecting malicious manipulations. This goal is different from that of image watermarking which embeds into the image a signature surviving most manipulations. Existing methods for image authentication treat all types of manipulation equally (i.e., as unacceptable). However, some applications demand techniques that can distinguish acceptable manipulations (e.g., compression) from malicious ones. In this paper, we describe an effective technique for image authentication which can prevent malicious manipulations but allow JPEG lossy compression. The authentication signature is based on the invariance of the relationship between DCT coefficients of the same position in separate blocks of an image. This relationship will be preserved when these coefficients are quantized in a JPEG compression process. Our proposed method can distinguish malicious manipulations from JPEG lossy compression regardless of how high the compression ratio is. We also show that, in different practical cases, the design of authenticator depends on the number of recompression times and on whether the image is decoded into integral values in the pixel domain during the recompression process. Theoretical and experimental results indicate that this technique is effective for image authentication.
7754068
Optimal state feedback based resource allocation for resource-constrained control tasks
In many application areas, including control systems, careful management of system resources is key to providing the best application performance. Most traditional resource management techniques for real-time systems with multiple control loops are based on open-loop strategies that statically allocate a constant CPU share to each controller, independent of their current resource needs. This provides average control performance with minimal overhead but in general fails to provide the best performance possible within the available resources. We show that by using feedback to dynamically allocate resources to controllers as a function of the current state of their controlled systems, control performance can be significantly improved. We present an optimal resource allocation policy that maximizes control performance within the available resources and provide experimental results showing that the optimal policy 1) significantly increases control performance compared to traditional control system implementations (by more than 20% in our experiments), 2) maximizes control performance over other feedback-based policies, 3) saves resources when perturbations occur infrequently, and 4) incurs negligible overhead.
5783340
Zero-error information hiding capacity of digital images
We derive a theoretical capacity for digital image watermarking with zero transmission errors. We present three different discrete memoryless channel model to represent the watermarking process. Given the magnitude bound of noise set by applications and the acceptable watermark magnitude determined by the just-noticeable distortion, we estimate the zero-error capacity by applying Shannon's (1948) adjacency-reducing mapping technique. The capacity we estimate here corresponds to a deterministic guarantee of zero error, different from the traditional theorem approaching zero error asymptotically.
206626471
Noisy Speech Segmentation/Enhancement with Multiband Analysis and Neural Fuzzy Networks
Background noise added to speech can decrease the performance of speech segmentation and enhancement. To solve this problem, new methods have been developed in this thesis. First, a new speech segmentation method (ATF-based SONFIN algorithm) is proposed in fixed noise-level environment. This method contains the multiband analysis and a neural fuzzy network, and it achieves higher recognition rate than the TF-based robust algorithm by 5%. In addition, a new speech segmentation method called RTF-based RSONFIN algorithm is proposed for variable noise-level environment. The RTF-based RSONFIN algorithm contains a recurrent neural fuzzy network. This method contains the multiband analysis and achieve higher recognition rate than the TF-based robust algorithm by 12%.