Integrating Parallelizing Compilation Technology and Processor Architecture for Cost-Effective Concurrent multithreading
As the number of transistors on a single chip continues to grow, it is important to think beyond the traditional approaches of compiler optimizations for deeper pipelines and wider instruction issue units to improve performance. This single-threaded execution model limits these approaches to exploiting only the relatively small amount of instruction-level parallelism available in application programs. While integrating an entire multiprocessor onto a single chip is feasible, this architecture is limited to exploiting only relatively coarse-grained parallelism. We propose a concurrent multi-threaded architecture, called the superthreaded architecture, as an alternative. As a hybrid of a wide-issue superscalar processor and a multiprocessor-on-a-chip, this new concurrent multithread-ing architecture can leverage the best of existing and future parallel hardware and compilation technologies. By combining compiler-directed thread-level speculation for control and data dependences with run-time checking of data dependences, the superthreaded architecture can exploit the multiple granularities of parallelism available in general-purpose application programs to reduce the execution time of a single program.

title: Experience in the Automatic Parallelization of Four Perfect-Benchmark Programs
abstract: This paper discusses the techniques used to hand-parallelize, for the Alliant FX/80, four Fortran programs from the Perfect-Benchmark suite. The paper also includes the execution times of the programs before and after the transformations. The four programs considered here were not effectively parallelized by the automatic translators available to the authors. However, most of the techniques used for hand parallelization, and perhaps all of them, have wide applicability and can be incorporated into existing translators.

title: New tiling techniques to improve cache temporal locality
abstract: Tiling is a well-known loop transformation to improve temporal locality of nested loops. Current compiler algorithms for tiling are limited to loops which are perfectly nested or can be transformed, in trivial ways, into a perfect nest. This paper presents a number of program transformations to enable tiling for a class of nontrivial imperfectly-nested loops such that cache locality is improved. We define a program model for such loops and develop compiler algorithms for their tiling. We propose to adopt odd-even variable duplication to break anti- and output dependences without unduly increasing the working-set size, and to adopt speculative execution to enable tiling of loops which may terminate prematurely due to, e.g. convergence tests in iterative algorithms. We have implemented these techniques in a research compiler, Panorama. Initial experiments with several benchmark programs are performed on SGI workstations based on MIPS R5K and R10K processors. Overall, the transformed programs run faster by 9% to 164%.

title: Compiler algorithms for event variable synchronization
abstract: Event variable synchronization is a well known mecha nism for enforcing data dependences in a program that runs in parallel on a shared memory multiprocessor This paper presents compiler algorithms to automati cally generate event variable synchronization code Pre viously published algorithms dealt with single parallel loops in which dependence distances are constant and known by the compiler However loops in real appli cation programs are often arbitrarily nested Moreover compilers are often unable to determine dependence dis tances In contrast our algorithms generate synchro nization code based directly on array subscripts and do not require constant distances in data dependences The algorithms are designed for arbitrarily nested loops in cluding triangular or trapezoidal loops

title: A theoretical foundation for program transformations to reduce cache thrashing due to true data sharing
abstract: Cache thrashing due to true data sharing can degrade the performance of parallel programs significantly. Our previous work showed that parallel task alignment via program transformations can be quite effective for the reduction of such cache thrashing. In this paper, we present a theoretical foundation for such program transformations. Based on linear algebra and the theory of numbers, our work analyzes the data dependences among the tasks created by a fork-join parallel program and determines at compile time how these tasks should be assigned to processors in order to reduce cache thrashing due to true data sharing. Our analysis and program transformations can be easily performed by compilers for parallel computers.

title: On Reducing Data Synchronization in Multiprocessed Loops
abstract: In this correspondence we present and prove the correctness of an algorithm for reducing the number of synchronized memory references to shared data elements in multiprocessed loops. Optimizing compilers for shared memory multiprocessors can use this algorithm to reduce synchronization overhead. The algorithm has been implemented as a new module in the multiprocessors version of Parafrase, the restructuring system of the University of Illinois. We present a brief discussion of experiments we performed to asses the effectiveness of this algorithm in reducing the synchronization overhead for the 61 subroutines of EISPACK, a package for computing matrix eigenvectors and eigenvalues.

title: Haplotype reconstruction from SNP fragments by minimum error correction
abstract: Haplotype reconstruction based on aligned single nucleotide polymorphism (SNP) fragments is to infer a pair of haplotypes from localized polymorphism data gathered through short genome fragment assembly. An important computational model of this problem is the minimum error correction (MEC) model, which has been mentioned in several literatures. The model retrieves a pair of haplotypes by correcting minimum number of SNPs in given genome fragments coming from an individual's DNA.



In the first part of this paper, an exact algorithm for the MEC model is presented. Owing to the NP-hardness of the MEC model, we also design a genetic algorithm (GA). The designed GA is intended to solve large size problems and has very good performance. The strength and weakness of the MEC model are shown using experimental results on real data and simulation data. In the second part of this paper, to improve the MEC model for haplotype reconstruction, a new computational model is proposed, which simultaneously employs genotype information of an individual in the process of SNP correction, and is called MEC with genotype information (shortly, MEC/GI). Computational results on extensive datasets show that the new model has much higher accuracy in haplotype reconstruction than the pure MEC model.

title: Mining multimedia data
abstract: Mining is a young but flourishing field. Many algorithms and applications exist to mine different types of data and extract different types of knowledge. Mining multimedia data is, however, at an experimental stage.We have implemented a prototype for mining high-level multimedia information and knowledge from large multimedia databases. MultiMedia Miner has been designed based on our years of experience in the research and development of a relational data mining system, DBMiner, in the Intelligent Database Systems Research Laboratory, and a Content-Based Image Retrieval system from Digital Libraries, C-BIRD, in the Vision and Media Laboratory.MultiMediaMiner includes the construction of multimedia data cubes which facilitate multiple dimensional analysis of multimedia data, and the mining of multiple kinds of knowledge, including summarization, classification, and association, in image and video databases. The images and video clips used in our experiments are collected by crawling the WWW. Many challenges have yet to be overcome, such as the large number of dimensions, and the existence of multi-valued dimensions.

title: Rational Solutions of Riccati-like Partial Differential Equations
abstract: When factoring linear partial differential systems with a finite-dimensional solution space or analysing symmetries of nonlinear ODEs, we need to look for rational solutions of certain nonlinear PDEs. The nonlinear PDEs are called Riccati-like because they arise in a similar way as Riccati ODEs. In this paper we describe the structure of rational solutions of a Riccati-like system, and an algorithm for computing them. The algorithm is also applicable to finding all rational solutions of Lie?s system { ?xu+u2+a1u+a2v+a3, ?yu+uv+b1u+b2v+b3, ?xv+uv+c1u+c2v+c3, ?yv+v2+d1u+d2v+d3},where a1, . . . , d3are rational functions of x and y.

title: C-Miner: Mining Block Correlations in Storage Systems
abstract: Block correlations are common semantic patterns in storage systems. These correlations can be exploited for improving the effectiveness of storage caching, prefetching, data layout and disk scheduling. Unfortunately, information about block correlations is not available at the storage system level. Previous approaches for discovering file correlations in file systems do not scale well enough to be used for discovering block correlations in storage systems. 
 
In this paper, we propose C-Miner, an algorithm which uses a data mining technique called frequent sequence mining to discover block correlations in storage systems. C-Miner runs reasonably fast with feasible space requirement, indicating that it is a practical tool for dynamically inferring correlations in a storage system. Moreover, we have also evaluated the benefits of block correlation-directed prefetching and data layout through experiments. Our results using real system workloads show that correlation-directed prefetching and data layout can reduce average I/O response time by 12-25% compared to the base case, and 7-20% compared to the commonly used sequential prefetching scheme.

title: Longest-path selection for delay test under process variation
abstract: Under manufacturing process variation, a path through a net is called longest if there exists a process condition under which the path has the maximum delay among all paths through the net. There are often multiple longest paths for each net, due to different process conditions. In addition, a local defect, such as resistive open or a resistive bridge, increases the delay of the affected net. To detect delay faults due to local defects and process variation, it is necessary to test all longest paths through each net. Previous approaches to this problem were inefficient because of the large number of paths that are not longest. This paper presents an efficient method to generate the set of longest paths for delay test under process variation. To capture both structural and process correlation between path delays, we use linear delay functions to express path delays under process variation. A novel technique is proposed to prune paths that are not longest, resulting in a significant reduction in the number of paths. In experiments on International Symposium on Circuits and Systems (ISCAS) circuits, our number of longest paths is 1-6% of the previous best approach, with 300/spl times/ less running time.