Accelerating Large-Scale Sorting through Parallel Algorithms

This study explores the application of parallel algorithms to enhance large-scale sorting, focusing on the QuickSort method. Implemented in both sequential and parallel forms, the paper provides a detailed comparison of their performance. This study investigates the efficacy of both techniques through the lens of array generation and pivot selection to manage datasets of varying sizes. This study meticulously documents the performance metrics, recording 16,499.2 milliseconds for the serial implementation and 16,339 milliseconds for the parallel implementation when sorting an array by using C++ chrono library. These results suggest that while the performance gains of the parallel approach over its serial counterpart are not immediately pronounced for smaller datasets, the benefits are expected to be more substantial as the dataset size increases.

A Class of Parallel Algorithms of Real-TimeNumerical Simulation for Stiff Dynamic System

In this paper a class of real-time parallel modified Rosenbrock methods of numerical simulation is constructed for stiff dynamic systems on a multiprocessor system, and convergence and numerical stability of these methods are discussed. A-stable real-time parallel formula of two-stage third-order and A(α)-stable real-time parallel formula with o ≈ 89.96° of three-stage fourth-order are particularly given. The numerical simulation experiments in parallel environment show that the class of algorithms is efficient and applicable, with greater speedup.

Some Massively Parallel Algorithms from Nature

We introduced the work on parallel problem solvers from physics and biology being developed by the research team at the State Key Laboratory of Software Engineering, Wuhan University. Results on parallel solvers include the following areas: Evolutionary algorithms based on imitating the evolution processes of nature for parallel problem solving, especially for parallel optimization and model-building; Asynchronous parallel algorithms based on domain decomposition which are inspired by physical analogies such as elastic relaxation process and annealing process, for scientific computations, especially for solving nonlinear mathematical physics problems. All these algorithms have the following common characteristics: inherent parallelism, self-adaptation and self-organization, because the basic ideas of these solvers are from imitating the natural evolutionary processes.

Design of efficient parallel algorithms on shared memory multiprocessors

The design of parallel algorithms is studied in this paper. These algorithms are applicable to shared memory MIMD machines In this paper, the emphasis is put on the methods for design of the efficient parallel algorithms. The design of efficient parallel algorithms should be based on the following considerationst algorithm parallelism and the hardware-parallelism; granularity of the parallel algorithm, algorithm optimization according to the underling parallel machine. In this paper , these principles are applied to solve a model problem of the PDE. The speedup of the new method is high. The results were tested and evaluated on a shared memory MIMD machine. The practical results were agree with the predicted performance.

CONVERGENCE ANALYSIS OF SOME FINITE ELEMENT PARALLEL ALGORITHMS FOR THE STATIONARY INCOMPRESSIBLE MHD EQUATIONS

By combination of iteration methods with the partition of unity method(PUM),some finite element parallel algorithms for the stationary incompressible magnetohydrodynamics(MHD)with different physical parameters are presented and analyzed.These algorithms are highly efficient.At first,a global solution is obtained on a coarse grid for all approaches by one of the iteration methods.By parallelized residual schemes,local corrected solutions are calculated on finer meshes with overlapping sub-domains.The subdomains can be achieved flexibly by a class of PUM.The proposed algorithm is proved to be uniformly stable and convergent.Finally,one numerical example is presented to confirm the theoretical findings.

Parallel Optimization of Program Instructions Using Genetic Algorithms

This paper describes an efficient solution to parallelize softwareprogram instructions, regardless of the programming language in which theyare written. We solve the problem of the optimal distribution of a set ofinstructions on available processors. We propose a genetic algorithm to parallelize computations, using evolution to search the solution space. The stagesof our proposed genetic algorithm are: The choice of the initial populationand its representation in chromosomes, the crossover, and the mutation operations customized to the problem being dealt with. In this paper, geneticalgorithms are applied to the entire search space of the parallelization ofthe program instructions problem. This problem is NP-complete, so thereare no polynomial algorithms that can scan the solution space and solve theproblem. The genetic algorithm-based method is general and it is simple andefficient to implement because it can be scaled to a larger or smaller number ofinstructions that must be parallelized. The parallelization technique proposedin this paper was developed in the C# programming language, and our resultsconfirm the effectiveness of our parallelization method. Experimental resultsobtained and presented for different working scenarios confirm the theoreticalresults, and they provide insight on how to improve the exploration of a searchspace that is too large to be searched exhaustively.

Local and parallel finite element algorithms for time-dependent convection-diffusion equations

Local and parallel finite element algorithms based on two-grid discretization for the time-dependent convection-diffusion equations are presented. These algorithms are motivated by the observation that, for a solution to the convection-diffusion problem, low frequency components can be approximated well by a relatively coarse grid and high frequency components can be computed on a fine grid by some local and parallel proce- dures. Hence, these local and parallel algorithms only involve one small original problem on the coarse mesh and some correction problems on the local fine grid. One technical tool for the analysis is the local a priori estimates that are also obtained. Some numerical examples are given to support our theoretical analvsis.

Research on the Optimal Parallel Algorithms of Broadcast-Class Problems

Speedup is considered as the criterion of determining whether a parallel algorithm is optimal. But broadcast-class problems, existing only on parallel computer system, have no sequential algorithms at all. Speedup standard becomes invalid here. Through this research on broadcast algorithms under several typical parallel computation models,a model-independent evaluation standard min C2 is developed, which can be not only used to determine an optimal broadcasting algorithm, but also normalized to apply to any parallel algorithm. As a new idea, min C2 will lead to a new way in this field.

Parallel Algorithms for Large-scale Linearly Constrained Minimization Problem

In this paper, two PVD-type algorithms are proposed for solving inseparable linear constraint optimization. Instead of computing the residual gradient function, the new algorithm uses the reduced gradients to construct the PVD directions in parallel computation, which can greatly reduce the computation amount each iteration and is closer to practical applications for solve large-scale nonlinear programming. Moreover, based on an active set computed by the coordinate rotation at each iteration, a feasible descent direction can be easily obtained by the extended reduced gradient method. The direction is then used as the PVD direction and a new PVD algorithm is proposed for the general linearly constrained optimization. And the global convergence is also proved.

New Heuristic Distributed Parallel Algorithms for Searching and Planning

This paper proposes new heuristic distributed parallel algorithms for search-ing and planning, which are based on the concepts of wave concurrent prop-agations and competitive activation mechanisms. These algorithms are char-acterized by simplicity and clearness of control strategies for searching, anddistinguished abilities in many aspects, such as high speed processing, widesuitability for searching AND/OR implicit graphs, and ease in hardware imple-mentation.

Financial Data Modeling by Using Asynchronous Parallel Evolutionary Algorithms

In this paper, the high-level knowledge of financial data modeled by ordinary differential equations (ODEs) is discovered in dynamic data by using an asynchronous parallel evolutionary modeling algorithm (APHEMA). A numerical example of Nasdaq index analysis is used to demonstrate the potential of APHEMA. The results show that the dynamic models automatically discovered in dynamic data by computer can be used to predict the financial trends.

Efficient Parallel Algorithms for Some Graph Theory Problems

In this paper,a sequential algorithm computing the all vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure arrayof an undirected graph.The time complexify of the parallel algorithm is O(n^3/p).If D,P andare known,it is shown that the problems to find all connected components, to compute the diameter of an undirected graph,to determine the center of a directed graph and to search for a directed cycle with the minimum(maximum)length in a directed graph can all be solved in O(n^2/p^+ logp)time.

PARALLEL(M-N) SVD ALGORITHMS ON THE SIMD COMPUTERS

Let A be m by n matrix, M and N be positive definite matrices of order in and n respectively. This paper presents an efficient method for computing (M-N) singular value decomposition((M-N) SVD) of A on a cube connected single instruction stream-multiple data stream(SIMD) parallel computer. This method is based on a one-sided orthogonalization algorithm due to Hestenes. On the cube connected SIMD parallel computer with o(n) processors, the (M -- N) SVD of a matrix A requires a computation time of o(m3 log m/n).

Asynchronous Parallel Evolutionary Algorithms for Constrained Optimizations

Recently Guo Tao proposed a stochastic search algorithm in his PhD thesis for solving function optimization problems. He combined the subspace search method (a general multi-parent recombination strategy) with the population hill-climbing method. The former keeps a global search for overall situation, and the latter keeps the convergence of the algorithm. Guo's algorithm has many advantages, such as the simplicity of its structure, the higher accuracy of its results, the wide range of its applications, and the robustness of its use. In this paper a preliminary theoretical analysis of the algorithm is given and some numerical experiments has been done by using Guo's algorithm for demonstrating the theoretical results. Three asynchronous parallel evolutionary algorithms with different granularities for MIMD machines are designed by parallelizing Guo's Algorithm.

PARALLEL MINIMIZATION ALGORITHMS by GENERALIZED SUBDIFFERENTIABILITY

Abstract Recently a, monotone generalized directional derixrative has been introduced for Lipschitz functions. This concept has been applied to represent and optimize nonsmooth functions. The second a.pplication result,ed relevant for parallel computing, by allowing to define minimization algorithms with high degree of inherent parallelism. The paper presents first the theoretical background, namely the notions of monotone generalized directional derivative and monotone generalized subdifferential. Then it defines the tools for the procedures, that is a necessary optimality condition and a steel>est descent direction. Therefore the minimization algorithms are outlined. Successively the used architectures and the performed numerical expertence are described, by listing and commenting the t.ested functions and the obtained results.

Parallel rapid relaxation inversion of 3D magnetotelluric data

We implement a parallel algorithm with the advantage of MPI （Message Passing Interface） to speed up the rapid relaxation inversion for 3D magnetotelluric data. We test the parallel rapid relaxation algorithm with synthetic and real data. The execution efficiency of the algorithm for several different situations is also compared. The results indicate that the parallel rapid relaxation algorithm for 3D magnetotelluric inversion is effective. This parallel algorithm implemented on a common PC promotes the practical application of 3D magnetotelluric inversion and can be suitable for the other geophysical 3D modeling and inversion.

An efficient parallel algorithm for shortest pathsin planar layered digraphs

This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log^3n) time with n processors. The algorithms uses a divide and conquer approach and is based on the novel idea of a one-way separator, which has the property that any directed path can be crossed only once.

Perturbation Methods of Stability Analysis for Parallel Real-Time Digital Simulation Models

In this paper, the stability analysis for parallel real-time digital simulation models is discussed. The coupling coefficient perturbation method and the simulation stepsize perturbation method are established. For two classes of systems of test equations, we construct the parallel simulation models and prove that they have the stability behaviour which is similar to the original continuous systems.

Fast Parallel Method for Polynomial Evaluation at Points in Arithmetic Progression

We present a fast method for polynomial evaluation at points in arithmetic progression. By dividing the progression into m new ones and evaluating the polynomial at each point of these new progressions recursively,this method saves most of the multiplications in the price of little increase of additions comparing to Horner's method, while their accuracy are almost the same. We also introduce vector structure to the recursive process making it suitable for parallel applications.

Optimal parallel algorithm for shortest-paths problem on interval graphs

This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.