Search results for "Parallel algorithm"

Parallelization of a Lattice Boltzmann Suspension Flow Solver

2002

We have applied a parallel Lattice Boltzmann method to solve the behaviour of the suspension flow. The complex behaviour of the suspension flow cannot be solved by analytical methods, so simulations are the only way to study it. Usually the size of an interesting problem is so big that calculation time on one processor is too long, and this can be solved by parallel program. We have written a parallel suspension flow solver and tested it on massive parallel computers. The measured performance of our program show that the parallelization of suspension particles was successful. We also show that over one million particles can be simulated.

A PARALLEL ALGORITHM FOR ANALYZING CONNECTED COMPONENTS IN BINARY IMAGES

1992

In this paper, a parallel algorithm for analyzing connected components in binary images is described. It is based on the extension of the Cylindrical Algebraic Decomposition (CAD) to a two-dimensional (2D) discrete space. This extension allows us to find the number of connected components, to determine their connectivity degree, and to solve the visibility problem. The parallel implementation of the algorithm is outlined and its time/space complexity is given.

Parallel Algorithms for Listing Well-Formed Parentheses Strings

1998

We present two cost-optimal parallel algorithms generating the set of all well-formed parentheses strings of length 2n with constant delay for each generated string. In our first algorithm we generate in lexicographic order well-formed parentheses strings represented by bitstrings, and in the second one we use the representation by weight sequences. In both cases the computational model is based on an architecture CREW PRAM, where each processor performs the same algorithm simultaneously on a different set of data. Different processors can access the shared memory at the same time to read different data in the same or different memory locations, but no two processors are allowed to write i…

SYSTOLIC GENERATION OF k-ARY TREES

1999

The only parallel generating algorithms for k-ary trees are those of Akl and Stojmenović in 1996 and of Vajnovszki and Phillips in 1997. In the first of them, trees are represented by an inversion table and the processor model is a linear aray multicomputer. In the second, trees are represented by bitstrings and the algorithm executes on a shared memory multiprocessor. In this paper we give a parallel generating algorithm for k-ary trees represented by generalized P–sequences for execution on a linear array multicomputer.

PGAC: A Parallel Genetic Algorithm for Data Clustering

2005

Cluster analysis is a valuable tool for exploratory pattern analysis, especially when very little a priori knowledge about the data is available. Distributed systems, based on high speed intranet connections, provide new tools in order to design new and faster clustering algorithms. Here, a parallel genetic algorithm for clustering called PGAC is described. The used strategy of parallelization is the island model paradigm where different populations of chromosomes (called demes) evolve locally to each processor and from time to time some individuals are moved from one deme to another. Experiments have been performed for testing the benefits of the parallelisation paradigm in terms of comput…

Diagonalization of large matrices: a new parallel algorithm.

2015

On the basis of a dressed matrices formalism, a new algorithm has been devised for obtaining the lowest eigenvalue and the corresponding eigenvector of large real symmetric matrices. Given an N × N matrix, the proposed algorithm consists in the diagonalization of (N - 1)2 × 2 dressed matrices. Both sequential and parallel versions of the proposed algorithm have been implemented. Tests have been performed on a Hilbert matrix, and the results show that this algorithm is up 340 times faster than the corresponding LAPACK routine for N = 10(4) and about 10% faster than the Davidson method. The parallel MPI version has been tested using up to 512 nodes. The speed-up for a N = 10(6) matrix is fair…

A parallel variable neighborhood search approach for the obnoxious p -median problem

2018

Experimental Study of Six Different Implementations of Parallel Matrix Multiplication on Heterogeneous Computational Clusters of Multicore Processors

2010

Two strategies of distribution of computations can be used to implement parallel solvers for dense linear algebra problems for Heterogeneous Computational Clusters of Multicore Processors (HCoMs). These strategies are called Heterogeneous Process Distribution Strategy (HPS) and Heterogeneous Data Distribution Strategy (HDS). They are not novel and have been researched thoroughly. However, the advent of multicores necessitates enhancements to them. In this paper, we present these enhancements. Our study is based on experiments using six applications to perform Parallel Matrix-matrix Multiplication (PMM) on an HCoM employing the two distribution strategies.

IDEA: interface dynamics and energetics algorithm.

2007

IDEA, interface dynamics and energetics algorithm, was implemented, in FORTRAN, under different operating systems to mimic dynamics and energetics of elementary events involved in interfacial processes. The code included a parallel elaboration scheme in which both the stochastic and the deterministic components, involved in the developed physical model, worked simultaneously. IDEA also embodied an optionally running VISUAL subroutine, showing the dynamic energy changes caused by the surface events, e.g., occurring at the gas-solid interface. Monte Carlo and ordinary differential equation system subroutines were employed in a synergistic way to drive the occurrence of the elementary events a…

Parallel Schwarz methods for convection-dominated semilinear diffusion problems

2002

AbstractParallel two-level Schwarz methods are proposed for the numerical solution of convection-diffusion problems, with the emphasis on convection-dominated problems. Two variants of the methodology are investigated. They differ from each other by the type of boundary conditions (Dirichlet- or Neumann-type) posed on a part of the second-level subdomain interfaces. Convergence properties of the two-level Schwarz methods are experimentally compared with those of a variant of the standard multi-domain Schwarz alternating method. Numerical experiments performed on a distributed memory multiprocessor computer illustrate parallel efficiency of the methods.