Efficient interprocedural analysis for program parallelization and restructuring
An approach to efficient interprocedural analysis for program parallelization and restructuring is presented. Such analysis is needed for parallelizing loops which contain procedure calls. Our approach captures call effect on data dependencies by propagating the precise information of array subscripts from the called procedure. This allows the optimizing compiler to choose an efficient yet precise data dependence test scheme depending on the complexity of array reference patterns. The other existing methods do not provide such flexibility, hence may suffer from either imprecision or inefficiency. The paper also discusses usage of classical summary information in several important transformations for program parallelization. Experimental results are reported.

title: The Cedar System And An Initial Performance Study
abstract: In this paper, we give an overview of the Cedar mutliprocessor and present recent performance results. These include the performance of some computational kernels and the Perfect Benchmarks@ . We also present a methodology f o r judging parallel system performance and apply this methodology to Cedar, Cray YMP-8, and Thinking Machines CM-5.

title: Data locality enhancement by memory reduction
abstract: In this paper, we propose memory reduction as a new approach to data locality enhancement. Under this approach, we use the compiler to reduce the size of the data repeatedly referenced in a collection of nested loops. Between their reuses, the data will more likely remain in higher-speed memory devices, such as the cache. Specifically, we present an optimal algorithm to combine loop shifting, loop fusion and array contraction to reduce the temporary array storage required to execute a collection of loops. When applied to 20 benchmark programs, our technique reduces the memory requirement, counting both the data and the code, by 51% on average. The transformed programs gain a speedup of 1.40 on average, due to the reduced footprint and, consequently, the improved data locality.

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: 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: 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: Efficient thermal-oriented 3D floorplanning and thermal via planning for two-stacked-die integration
abstract: New three-dimensional (3D) floorplanning and thermal via planning algorithms are proposed for thermal optimization in two-stacked die integration. Our contributions include (1) a two-stage design flow for 3D floorplanning, which scales down the enlarged solution space due to multidevice layer structure; (2) an efficient thermal-driven 3D floorplanning algorithm with power distribution constraints; (3) a thermal via planning algorithm considering congestion minimization. Experiments results show that our approach is nine times faster with better solution quality compared to a recent published result. In addition, the thermal via planning approach is proven to be very efficient to eliminate localized hot spots directly.

title: A parsimonious tree-grow method for haplotype inference
abstract: Haplotype information has become increasingly important in analyzing fine-scale molecular genetics data, such as disease genes mapping and drug design. Parsimony haplotyping is one of haplotyping problems belonging to NP-hard class.



In this paper, we aim to develop a novel algorithm for the haplotype inference problem with the parsimony criterion, based on a parsimonious tree-grow method (PTG). PTG is a heuristic algorithm that can find the minimum number of distinct haplotypes based on the criterion of keeping all genotypes resolved during tree-grow process. In addition, a block-partitioning method is also proposed to improve the computational efficiency. We show that the proposed approach is not only effective with a high accuracy, but also very efficient with the computational complexity in the order of O(m2n) time for n single nucleotide polymorphism sites in m individual genotypes.


AVAILABILITY
The software is available upon request from the authors, or from http://zhangroup.aporc.org/bioinfo/ptg/



chen@elec.osaka-sandai.ac.jp

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: Computational Differences between Asymmetrical and Symmetrical Networks
abstract: Symmetrically connected recurrent networks have recently been used as models of a host of neural computations. However, biological neural networks have asymmetrical connections, at the very least because of the separation between excitatory and inhibitory neurons in the brain. We study characteristic differences between asymmetrical networks and their symmetrical counterparts in cases for which they act as selective amplifiers for particular classes of input patterns. We show that the dramatically different dynamical behaviours to which they have access, often make the asymmetrical networks computationally superior. We illustrate our results in networks that selectively amplify oriented bars and smooth contours in visual inputs.

title: WICCAP: from semi-structured data to structured data
abstract: Web data extraction is a technique for extracting and integrating data from Web based semistructured data. Wrappers function like the kernel of Web data extraction systems providing information mediator between users and a large number of heterogeneous data sources. Typically, they process semistructured documents generated from structured databases based on rules that are usually hidden to users. Much research has been done to use various methods to represent the knowledge of hidden rules and exploit techniques such as grammar induction, inductive logic programming, etc., to discover these rules that can be used by wrappers to extract data. An important property of semistructured data is its hierarchical structure. Intuitively, we can devise a method that can use this structure information to generate wrappers. We describe a Web data extraction system - WICCAP and its internal Web Data Extraction Language (WDEL) that provides unified view of Web data resources and extracted data. We describe some rule generation features of WICCAP and provide detailed description of the internal language and its implementation. We have conducted experiments to show the ease on generating wrappers with this approach.