27000155
Towards a Machine-Independent Solution of Sparse Cholesky Factorization
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.
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.
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%
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.
7770599
Improving soft real-time performance through better slack reclaiming
Modern operating systems frequently support applications with a variety of timing constraints including hard real-time, soft real-time, and best-effort. To guarantee performance, critical applications typically over-reserve resources based on worst-case resource usage estimates, while others may reserve based on average-case or other estimates. When resources are fully subscribed, the performance of soft- and non-real-time applications depends upon the effective distribution of dynamic slack - reserved, but unused resources - from other tasks. Motivated by several representative examples, we derive four general principles for the effective management of slack. We have implemented these principles in four progressively better slack schedulers that demonstrate their effectiveness. BACKSLASH, which employs all four principles, misses fewer soft realtime deadlines than all of the other slack schedulers we examined
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%.
7664224
Probability Estimates for Multi-class Classification by Pairwise Coupling
Pairwise coupling is a popular multi-class classification method that combines all comparisons for each pair of classes. This paper presents two approaches for obtaining class probabilities. Both methods can be reduced to linear systems and are easy to implement. We show conceptually and experimentally that the proposed approaches are more stable than the two existing popular methods: voting and the method by Hastie and Tibshirani (1998)
268525
Optimizing the Use of High Performance Software Libraries
This paper describes how the use of software libraries, which is prevalent in high performance computing, can benefit from compiler optimizations in much the same way that conventional programming languages do. We explain how the compilation of these informal languages differs from the compilation of more conventional languages. In particular, such compilation requires precise pointer analysis, domain-specific information about the library's semantics, and a configurable compilation scheme. We describe a solution that combines dataflow analysis and pattern matching to perform configurable optimizations.
3084140
Ranking individuals by group comparisons
This paper proposes new approaches to rank individuals from their group competition results. Many real-world problems are of this type. For example, ranking players from team games is important in some sports. We propose an exponential model to solve such problems. To estimate individual rankings through the proposed model we introduce two convex minimization formulas with easy and efficient solution procedures. Experiments on real bridge records and multi-class classification demonstrate the viability of the proposed model.