Affine Dependence Classification for Communications Minimization

This paper introduces results on placement and communications minimization for systems of affine recurrence equations. We show how to classify the dependences according to the number and nature of communications they may result in. We give both communication-free conditions and conditions for an efficient use of broadcast or neighbor-to-neighbor communication primitives. Since the dependences of a problem can generally not be all communication-free, we finally introduce a heuristic to globally minimize the communications based on the classification of dependences.     

The interprocedural analysis and automatic parallelization of Scheme programs

Lisp and its descendants are among the most important and widely used of programming languages. At the same time, parallelism in the architecture of computer systems is becoming commonplace. There is a pressing need to extend the technology of automatic parallelization that has become available to Fortran programmers of parallel machines, to the realm of Lisp programs and symbolic computing. In this paper we present a comprehensive approach to the compilation of Scheme programs for shared-memory multiprocessors. Our strategy has two principal components:interprocedural analysis andprogram restructuring. We introduceprocedure strings andstack configurations as a framework in which to reason about interprocedural side-effects and object lifetimes, and develop a system of interprocedural analysis, using abstract interpretation, that is used in the dependence analysis and memory management of Scheme programs. We introduce the transformations ofexit-loop translation andrecursion splitting to treat the control structures of iteration and recursion that arise commonly in Scheme programs. We propose an alternative representation for s-expressions that facilitates the parallel creation and access of lists. We have implemented these ideas in a parallelizing Scheme compiler and run-time system, and we complement the theory of our work with snapshots of programs during the restructuring process, and some preliminary performance results of the execution of object codes produced by the compiler.This work was supported in part by the National Science Foundation under Grant No. NSF MIP-8410110, the U.S. Department of Energy under Grant No. DE-FG02-85ER25001, the Office of Naval Research under Grant No. ONR N00014-88-K-0686, the U.S. Air Force Office of Scientific Research under Grant No. AFOSR-F49620-86-C-0136, and by a donation from the IBM Corportation.     

Accelerating geospatial analysis on GPUs using CUDA

Inverse distance weighting (IDW) interpolation and viewshed are two popular algorithms for geospatial analysis.IDW interpolation assigns geographical values to unknown spatial points using values from ...     

基于MapReduce的MIC算法并行化

MIC是一种分析变量之间可能存在的关系的方法。该方法不仅能够有效识别出变量间各种复杂类型的关系,还能够准确描述噪音数据对存在关系的影响,对探索大数据集中变量之间的关系具有重要意义。针对该方法在处理包含大量变量的数据集时性能方面的不足,首次对它进行了基于MapReduce模型的并行化。提出的并行化方法首先对原算法进行更细颗粒度的划分,然后采用一种基于Map-Reduce-Map任务链的并行模型,该模型不仅有效地增加了并行的计算单元,还大大地降低了不必要的系统开销。最后,通过理论分析和实验验证得出,改进后的算法与原算法相比,在准确率方面具有等效性,运行速度大幅度提升且具有良好的可扩展性;实验同时指出了算法性能的提升与系统资源的关系。     

Parallel processing speed increase of the one-bit auto-correlation function in hardware

Recently, a serial implementation of the one-bit auto- and cross-correlation functions (ACF and CCF respectively) in a field programmable gate array (FPGA) has been developed, based on asynchronous delay elements and counters, known as the counterbased correlation. This paper proposes a method of parallelizing this otherwise serial process, offering significant improvements in the applicability of this approach to more types of ACF. Furthermore, the possibility of obtaining lag results from a parallel data sequence without first shifting the entire sequence has been realized, hence decreasing the number of clock cycles necessary for the calculation of the ACF. A synchronous design was preferred here for reasons of stability and portability, the technology of choice again being an FPGA. The advantages offered by the counterbased implementation in terms of device area usage and speed still apply. A practical implementation in the instrumentation of an upcoming space mission is also discussed.     

Monte Carlo randomization tests for large-scale abundance datasets on the GPU

Statistical tests are often performed to discover which experimental variables are reacting to specific treatments. Time-series statistical models usually require the researcher to make assumptions with respect to the distribution of measured responses which may not hold. Randomization tests can be applied to data in order to generate null distributions non-parametrically. However, large numbers of randomizations are required for the precise p-values needed to control false discovery rates. When testing tens of thousands of variables (genes, chemical compounds, or otherwise), significant q-value cutoffs can be extremely small (on the order of 10⁻⁵ to 10⁻⁸). This requires high-precision p-values, which in turn require large numbers of randomizations. The NVIDIA^® Compute Unified Device Architecture^® (CUDA^®) platform for General Programming on the Graphics Processing Unit (GPGPU) was used to implement an application which performs high-precision randomization tests via Monte Carlo sampling for quickly screening custom test statistics for experiments with large numbers of variables, such as microarrays, Next-Generation sequencing read counts, chromatographical signals, or other abundance measurements. The software has been shown to achieve up to more than 12 fold speedup on a Graphics Processing Unit (GPU) when compared to a powerful Central Processing Unit (CPU). The main limitation is concurrent random access of shared memory on the GPU. The software is available from the authors.     

基于Cilk++的遗传算法并行化改造实现

遗传算法是模拟生物进化过程的一种计算模型,在同一代种群间进行基因的选择、交叉和变异时,具有良好的并行性.遗传算法在实际的应用中,选取的种群数目往往比较大,处理的数据量巨大,因此算法性能比较低.目前,处理器已经进入多核时代,但传统的程序还是基于单核编写,程序性能并没有随着处理器数目增加而增加.因此,通过对遗传算法进行并行化改造,使得算法能够充分利用多核处理器资源,算法的性能大大提升.并行遗传算法的实现,符合未来多核程序设计的发展方向,有利于遗传算法更广泛的运用.     

直接模拟蒙特卡洛问题的并行化方法

对直接模拟蒙特卡洛问题的动态数据分布特点进行了研究，提出了该类问题的并行化方法，并对实际算例进行处理，在集群系统上获得的测试结果表明该方法正确而有效，能够满足用户的高性能计算需要。     

A blocked QR-decomposition for the parallel symmetric eigenvalue problem

In this paper we present a new stable algorithm for the parallel QR-decomposition of “tall and skinny” matrices. The algorithm has been developed for the dense symmetric eigensolver ELPA, where the QR-decomposition of tall and skinny matrices represents an important substep. Our new approach is based on the fast but unstable CholeskyQR algorithm (Stathopoulos and Wu, 2002) [1]. We show the stability of our new algorithm and provide promising results of our MPI-based implementation on a BlueGene/P and a Power6 system.     

Parallel VNS for Bus Terminal Location Problem

This paper considers the Bus Terminal Location Problem (BTLP) which incorporates characteristics of both the p-median and maximal covering problems. We propose a parallel variable neighborhood search algorithm (PVNS) for solving BTLP. Improved local search, based on efficient neighborhood interchange, is used for the p-median problem, and is combined with a reduced neighborhood size for the maximal covering part of the problem. The proposed parallel algorithm is compared with its non-parallel version. Parallelization yielded significant time improvement in function of the processor core count. Computational results show that PVNS improves all existing results from the literature, while using significantly less time. New larger instances, based on rl instances from the TSP library, are introduced and computational results for those new instances are reported.