Massively parallel algorithms from physics and biology

In this paper the recent developments of lattice kinetic models are discussed followed by the fundamental concepts of Evolutionary Algorithms and their application to optimization, machine learning, Neural networks and many other areas. Finally, the application of Evolutionary Algorithms to the biological eco-system is presented.     

Massively parallel GPU computing for fast stereo correspondence algorithms

Current accurate stereo matching algorithms employ some key techniques that are not suitable for parallel GPU architecture. It will be tricky and cumbersome to directly take these techniques into GPU applications. Trying to tackle this difficulty, we design two GPU-based stereo matching algorithms, one using a local fixed aggregation window whose size is configurable, and the other using an adaptive aggregation window which only includes necessary pixels. We use the winner-takes-all (WTA) principle for optimization and a plain voting refinement for post-processing; both do not need complex data structures. We aim to implement on GPU platforms fast stereo matching algorithms that produce results with same-level quality as other WTA local dense methods that use window-based cost aggregation. In our GPU-based implementation of the fixed window partially demosaiced CFA stereo matching application, accelerations up to 20 times are obtained for large size images. In our GPU-based implementation of the adaptive window color stereo matching application, experiment results show that it can handle four pairs of standard images from Middlebury database within roughly 100 ms.     

Massively parallel augmenting path algorithms for the assignment problem

In this paper we describe how to apply fine grain parallelism to augmenting path algorithms for the dense linear assignment problem. We prove by doing that the technique we suggest, can be efficiently implemented on commercial available, massively parallel computers. Using n processors, our method reduces the computational complexity from the sequentialO(n ³) to the parallel complexity ofO(n ²). Exhaustive experiments are performed on a Maspar MP-2 in order to determine which of the algorithmic flavors that fits best onto this kind of architecture.     

Validating trace-driven microarchitectural simulations

Benchmark complexity and sluggish performance analysis create an ever-increasing gap between workload size and the speed of analysis. Experimental results with a new data-sampling methodology, however, show promise in closing this gap     

Massively parallel adaptive mesh refinement and coarsening for dynamic fracture simulations

We use the graphical processing unit (GPU) to perform dynamic fracture simulation using adaptively refined and coarsened finite elements and the inter-element cohesive zone model. Due to the limited memory available on the GPU, we created a specialized data structure for efficient representation of the evolving mesh given. To achieve maximum efficiency, we perform finite element calculation on a nodal basis (i.e., by launching one thread per node and collecting contributions from neighboring elements) rather than by launching threads per element, which requires expensive graph coloring schemes to avoid concurrency issues. These developments made possible the parallel adaptive mesh refinement and coarsening schemes to systematically change the topology of the mesh. We investigate aspects of the parallel implementation through microbranching examples, which has been explored experimentally and numerically in the literature. First, we use a reduced-scale version of the experimental specimen to demonstrate the impact of variation in floating point operations on the final fracture pattern. Interestingly, the parallel approach adds some randomness into the finite element simulation on the structured mesh in a similar way as would be expected from a random mesh. Next, we take advantage of the speedup of the implementation over a similar serial implementation to simulate a specimen whose size matches that of the actual experiment. At this scale, we are able to make more direct comparisons to the original experiment and find excellent agreement with those results.     

Massively parallel methods for semiconductor device modelling

In this paper we describe, analyse and implement a parallel iterative method for the solution of the steady-state drift diffusion equations governing the behaviour of a semiconductor device in two space dimensions. The unknowns in our model are the electrostatic potential and the electron and hole quasi-Fermi potentials. Our discretisation consists of a finite element method with mass lumping for the electrostatic potential equation and a hybrid finite element with local current conservation properties for the continuity equations. A version of Gummel's decoupling algorithm which only requires the solution of positive definite symmetric linear systems is used to solve the resulting nonlinear equations. We show that this method has an overall rate of convergence which only degrades logarithmically as the mesh is refined. Indeed the (inner) nonlinear solves of the electrostatic potential equation converge quadratically, with a mesh independent asymptotic constant. We also describe an implementation on a MasPar MP-1 data parallel machine, where the required linear systems are solved by the preconditioned conjugate gradient method. Domain decomposition methods are used to parallelise the required matrix-vector multiplications and to build preconditioners for these very poorly-conditioned systems. Our preconditioned linear solves also have a rate of convergence which degrades logarithmically as the grid is refined relative to subdomain size, and their performance is resilient to the severe layers which arise in the coefficients of the underlying elliptic operators. Parallel experiments are given.     

Massively parallel quantum computer simulator

We describe portable software to simulate universal quantum computers on massive parallel computers. We illustrate the use of the simulation software by running various quantum algorithms on different computer architectures, such as a IBM BlueGene/L, a IBM Regatta p690+, a Hitachi SR11000/J1, a Cray X1E, a SGI Altix 3700 and clusters of PCs running Windows XP. We study the performance of the software by simulating quantum computers containing up to 36 qubits, using up to 4096 processors and up to 1 TB of memory. Our results demonstrate that the simulator exhibits nearly ideal scaling as a function of the number of processors and suggest that the simulation software described in this paper may also serve as benchmark for testing high-end parallel computers.     

Massively parallel architectures for large scale neural networksimulations

A toroidal lattice architecture (TLA) and a planar lattice architecture (PLA) are proposed as massively parallel neurocomputer architectures for large-scale simulations. The performance of these architectures is almost proportional to the number of node processors, and they adopt the most efficient two-dimensional processor connections for WSI implementation. They also give a solution to the connectivity problem, the performance degradation caused by the data transmission bottleneck, and the load balancing problem for efficient parallel processing in large-scale neural network simulations. The general neuron model is defined. Implementation of the TLA with transputers is described. A Hopfield neural network and a multilayer perceptron have been implemented and applied to the traveling salesman problem and to identity mapping, respectively. Proof that the performance increases almost in proportion to the number of node processors is given.     

Massively parallel software rendering for visualizing large-scaledata sets

We describe two highly scalable, parallel software volume-rendering algorithms - one renders unstructured grid volume data and the other renders isosurfaces. We designed one algorithm for distributed-memory parallel architectures to render unstructured grid volume data. We designed the other for shared-memory parallel architectures to directly render isosurfaces. Through the discussion of these two algorithms, we address the most relevant issues when using massively parallel computers to render large-scale volumetric data. The focus of our discussion is direct rendering of volumetric data     

Optimizing graph algorithms for improved cache performance

We develop algorithmic optimizations to improve the cache performance of four fundamental graph algorithms. We present a cache-oblivious implementation of the Floyd-Warshall algorithm for the fundamental graph problem of all-pairs shortest paths by relaxing some dependencies in the iterative version. We show that this implementation achieves the lower bound on processor-memory traffic of /spl Omega/(N/sup 3///spl radic/C), where N and C are the problem size and cache size, respectively. Experimental results show that this cache-oblivious implementation shows more than six times the improvement in real execution time over that of the iterative implementation with the usual row major data layout, on three state-of-the-art architectures. Second, we address Dijkstra's algorithm for the single-source shortest paths problem and Prim's algorithm for minimum spanning tree problem. For these algorithms, we demonstrate up to two times the improvement in real execution time by using a simple cache-friendly graph representation, namely adjacency arrays. Finally, we address the matching algorithm for bipartite graphs. We show performance improvements of two to three times in real execution time by using the technique of making the algorithm initially work on subproblems to generate a suboptimal solution and, then, solving the whole problem using the suboptimal solution as a starting point. Experimental results are shown for the Pentium III, UltraSPARC III, Alpha 21264, and MIPS R12000 machines.     

基于最小效用的流媒体缓存替换算法

提出最小缓存替换算法SCU-K，综合考虑流媒体文件最近K次访问情况，使缓存大小动态适应媒体流行度、字节有用性和已缓存部分大小的变化，降低了文件前缀部分被替换的概率，避免LRU和LFU算法中出现的媒体文件被连续替换的问题。在与LRU，LFU和LRU-2算法的对比实验中，SCU-K算法在提高缓存空间利用率、字节命中率和降低启动延迟方面具有更好的性能。     

Massively parallel computations on many-variable polynomials

We show that a multivariate homogeneous polynomial can be represented on a hypercube in such a way that sums, products and partial derivatives can be performed by massively parallel computers. This representation is derived from the theoretical results of Beauzamy-Bombieri-Enflo-Montgomery [1]. The norm associated with it, denoted by [·], is itself a very efficient tool: when products of polynomials are performed, the best constant in inequalities of the form [PQ]C[P][Q] are provided, and the extremal pairs (that is, the pairs of polynomials for which the product is as small as possible) can be identified.Supported by the C.N.R.S (France) and the N.S.F. (USA), by contracts E.T.C.A./C.R.E.A. No. 20351/90 and 20357/91 (Ministry of Defense, France), and by Research Contract EERP-FR 22, DIGITAL Eq. Corp.     

Massively parallel computation of conservation laws

We present a new method for computing solutions of conservation laws based on the use of cellular automata with the method of characteristics. The method exploits the high degree of parallelism available with cellular automata and retains important features of the method of characteristics. It yields high numerical accuracy and extends naturally to adaptive meshes and domain decomposition methods for perturbed conservation laws. We describe the method and its implementation for a Dirichlet problem with a single conservation law for the one-dimensional case.

Numerical results for the one-dimensional law with the classical Burgers nonlinearity or the Buckley-Leverett equation show good numerical accuracy outside the neighborhood of the shocks. The error in the area of the shocks is of the order of the mesh size. The algorithm is well suited for execution on both massively parallel computers and vector machines. We present timing results for an Alliant FX/8, Connection Machine Model 2, and CRAY X-MP.     

Scalable cache invalidation algorithms for mobile data access

In this paper, we address the problem of cache invalidation in mobile and wireless client/server environments. We present cache invalidation techniques that can scale not only to a large number of mobile clients, but also to a large number of data items that can be cached in the mobile clients. We propose two scalable algorithms: the Multidimensional Bit-Sequence (MD-BS) algorithm and the Multilevel Bit-Sequence (ML-BS) algorithm. Both algorithms are based on our prior work on the Basic Bit-Sequences (BS) algorithm. Our study shows that the proposed algorithms are effective for a large number of cached data items with low update rates. The study also illustrates that the algorithms ran be used with other complementary techniques to address the problem of cache invalidation for data items with varied update and access rates.     

Disk cache architectures for transaction-like applications in parallel computers

Computing - I/O in computer systems is prone to become a bottleneck. This is a particular severe problem in highly parallel machines where some applications are fully I/O bound if only one or few...     

Environments for prototyping parallel algorithms

The current ferment in parallel computer architecture has exacerbated the already large problems in developing and testing parallel algorithms. Although only experimentation will identify effective designs, the variety of computing paradigms has precluded development of the (necessary) general environment for parallel programming. We propose an environment design system where design specification is divorced from implementation. Because the design system, Polylith, provides the communication structure of a parallel computation, the computation's individual tasks can be written in one of several relatively portable sequential languages.     

Line-drawing algorithms for parallel machines

The fact that conventional line-drawing algorithms, when applied directly on parallel machines, can lead to very inefficient codes is addressed. It is suggested that instead of modifying an existing algorithm for a parallel machine, a more efficient implementation can be produced by going back to the invariants in the definition. Popular line-drawing algorithms are compared with two alternatives; distance to a line (a point is on the line if sufficiently close to it) and intersection with a line (a point on the line if an intersection point). For massively parallel single-instruction-multiple-data (SIMD) machines (with thousands of processors and up), the alternatives provide viable line-drawing algorithms. Because of the pixel-per-processor mapping, their performance is independent of the line length orientation     

Massively parallelized replica-exchange simulations of polymers on GPUs

We discuss the advantages of parallelization by multithreading on graphics processing units (GPUs) for parallel tempering Monte Carlo computer simulations of an exemplified bead-spring model for homopolymers. Since the sampling of a large ensemble of conformations is a prerequisite for the precise estimation of statistical quantities such as typical indicators for conformational transitions like the peak structure of the specific heat, the advantage of a strong increase in performance of Monte Carlo simulations cannot be overestimated. Employing multithreading and utilizing the massive power of the large number of cores on GPUs, being available in modern but standard graphics cards, we find a rapid increase in efficiency when porting parts of the code from the central processing unit (CPU) to the GPU.     

Massively parallel processing in coastal ocean circulation model

Massively parallel computers are becoming quite common in their use in computational fluid dynamics. In this study, a parallel algorithm of a 3-D primitive-equation coastal ocean circulation model is designed on the hypercube MIMD computer architecture. The grid is partitioned using one-dimensional domain decomposition. The code is tested in a uniform rectangular grid problem for which the model domain in each node is a cube. For the problem where the grain size (n _y ) is fixed, the speedup is linear and is close to ideal forP 8 processors. The overhead (F _C ) increases as the number of processors increases. The background overhead is inversely proportional to the size of the grain. The slopeF _C vs.P is a measure of the fraction of non-parallel code. For the problem where the domain is fixed, the speedup is 7.8 using 8-processors and 29.6 using 32-processors. The overhead increases linearly withP. The slopeF _C is a measure of the communication cost. The load balancing problem is examined for a model of the Gulf of California whose computational domain is irregular.