基于DHT快速插值并行算模的研究

文中所研究的这种快速插值并行算模,是一种基于DHT(Discrete Hartley Transform)的流水型模块式(即把若干个插值模块形序列全部变换为一条“流水线长龙状”序列)算模。这种算模的计算过程既不需要数据记录设施,亦不需要缓冲暂存环节,而且插值运算时间的复杂性同插值模块因子的复杂性独立无关。这种快速插值并行算模的每个计算周期持续时间相当于执行一个累积运算(加法运算和乘法运算)时间,运算简便迅速,因此对于实施高速计算应用非常有用。

基于可重构多处理器系统的AOE网问题的并行算法

研究了基于三维Ｍｅｓｈ连接的可重构总线处理器系统的ＡＯＥ（ａｃｔｉｖｉｔｙｏｎｅｄｇｅ）网问题的并行算法．提出了ＡＯＥ网中拓扑排序问题和关键路径问题并行求解的有效算法。

基于斐波那契序列的多播算法

该文提出了一种基于斐波那契序列的多播算法 ,并在 log P模型 [1 ] 下对算法的性能进行了分析 .log P模型是一种广泛使用的并行计算模型 ,它利用 L,o,g,P四个参数来分别表示发送一条消息的等待时间或最大延迟、处理器的开销、源结点发送消息的时间间隔、处理器 /存储器模块数 .在 log P模型下 ,该文所述的基于斐波那契序列的多播算法的时间复杂度为 0 .72 0 2 2· log2 K· (g+m ax{ L+2· o,2· g} ) ,而传统的采用均匀二分的多播算法时间复杂度为 log2 K· (L+2· o) ,其中 K为结点数 .当 g 0 .3884· (L+2· o)时 ,基于斐波那契序列的多播算法性能将优于采用均匀二分策略的多播算法 .由于实际情况中 L +2 o g,因此 ,基于斐波那契序列的多播算法性能更优 .

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.

A Fast and Efficient Global Router for Congestion Optimization

An efficient parallel global router using random optimization that is independent of net ordering is proposed.Parallel approaches are described and strategies guaranteeing the routing quality are discussed.The wire length model is implemented on multiprocessor,which enables the algorithm to approach feasibility of large scale problems.Timing driven model on multiprocessor and wire length model on distributed processors are also presented.The parallel algorithm greatly reduces the run time of routing.The experimental results show good speedups with no degradation of the routing quality.

The group search-based parallel algorithm for the serial Monte Carlo inversion method

With the development of parallel computing technology,non-linear inversion calculation efficiency has been improving.However,for single-point search-based non-linear inversion methods,the implementation of parallel algorithms is a difficult issue.We introduce the idea of group search to the single-point search-based non-linear inversion algorithm, taking the quantum Monte Carlo method as an example for two-dimensional seismic wave velocity inversion and practical impedance inversion and test the calculation efficiency of using different node numbers.The results show the parallel algorithm in theoretical and practical data inversion is feasible and effective.The parallel algorithm has good versatility. The algorithm efficiency increases with increasing node numbers but the algorithm efficiency rate of increase gradually decreases as the node numbers increase.

PARAMETER IDENTIFICATION OF LUGRE FRICTION MODEL FOR FLIGHT SIMULATION SERVO SYSTEM BASED ON ANT COLONY ALGORITHM

In light of the high nonlinearity of LuGre friction model, a novel method based on ant colony algorithm(ACA) for identifying the friction parameters of flight simulation servo system is proposed. ACA is a parallelized bionic optimization algorithm inspired from the behavior of real ants, and a kind of positive feedback mechanism is adopted in ACA. On the basis of brief introduction of LuGre friction model, a method for identifying the static LuGre friction parameters and the dynamic LuGre friction parameters using ACA is derived. Finally, this new friction parameter identification scheme is applied to a electric-driven flight simulation servo system with high precision. Simulation and application results verify the feasibility and the effectiveness of the scheme. It provides a new way to identify the friction parameters of LuGre model.

PARALLEL COMPUTATION OF 3-D HYPERSONIC FLOWS ON UNSTRUCTURED HYBRID MESHES

A parallel virtual machine （PVM） protocol based parallel computation of 3-D hypersonic flows with chemical non-equilibrium on hybrid meshes is presented. The numerical simulation for hypersonic flows with chemical non-equilibrium reactions encounters the stiffness problem, thus taking huge CPU time. Based on the domain decomposition method, a high efficient automatic domain decomposer for three-dimensional hybrid meshes is developed, and then implemented to the numerical simulation of hypersonic flows. Control equations are multicomponent N-S equations, and spatially discretized scheme is used by a cell-centered finite volume algorithm with a five-stage Runge-Kutta time step. The chemical kinetic model is a seven species model with weak ionization. A point-implicit method is used to solve the chemical source term. Numerical results on PC-Cluster are verified on a bi-ellipse model compared with references.

Parallel EOI algorithm with different insertion schemes

A parallel embedding overlapped iterative (EOI) algorithm about classicimplicit equations with asymmetric Saul'yev schemes (CIS-EOI) to solve one-dimensional diffusionequations is discussed to improve the properties of the segment classic implicit iterative (SCII)algorithm. The structure of CIS-EOI method is given and the stability of scheme and convergence ofiteration are proved by matrix method. The property of gradual-approach convergence is alsodiscussed. It has been shown that the convergent rate is faster and the property of gradual-approachconvergence also becomes better with the increasing of the net point in subsystems than with theSCII algorithm. The simulation examples show that the parallel iterative algorithm with a differentinsertion scheme CIS-EOI is more effective.

PARALLELIZED UPWIND FLUX SPLITTING SCHEME FOR SUPERSONIC REACTING FLOWS ON UNSTRUCTURED HYBRID MESHES

A parallelized upwind flux splitting scheme for supersonic reacting flows on hybrid meshes is presented. The complexity of super/hyper-sonic combustion flows makes it necessary to establish solvers with higher resolution and efficiency for multi-component Euler/N-S equations. Hence, a spatial second-order van Leer type flux vector splitting scheme is established by introducing auxiliary points in interpolation, and a domain decomposition method used on unstructured hybrid meshes for obtaining high calculating efficiency. The numerical scheme with five-stage Runge-Kutta time step method is implemented to the simulation of combustion flows, including the supersonic hydrogen/air combustion and the normal injection of hydrogen into reacting flows. Satisfying results are obtained compared with limited references.

Parallel Implementation of Global Illumination Using PVM

In this paper an attempt of employing network resources to solve a complex and time-consuming problem is presented. The global illumination problem is selected as the study objective. An improved density estimation algorithm is first developed, in which the more inherent concurrency is explored. Then its parallel implementation by using a PVM mechanism and the running performance analysis are provided. The analysis results show the expected speed-up obtained and demonstrate that the PVM has good application prospects for parallel computation in a distributed network.

Two-dimensional inversion of spectral induced polarization data using MPI parallel algorithm in data space

Traditional two-dimensional（2D） complex resistivity forward modeling is based on Poisson＇s equation but spectral induced polarization（SIP） data are the coproducts of the induced polarization（IP） and the electromagnetic induction（EMI） effects.This is especially true under high frequencies,where the EMI effect can exceed the IP effect.2D inversion that only considers the IP effect reduces the reliability of the inversion data.In this paper,we derive differential equations using Maxwell＇s equations.With the introduction of the Cole-Cole model,we use the finite-element method to conduct2 D SIP forward modeling that considers the EMI and IP effects simultaneously.The data-space Occam method,in which different constraints to the model smoothness and parametric boundaries are introduced,is then used to simultaneously obtain the four parameters of the Cole-Cole model using multi-array electric field data.This approach not only improves the stability of the inversion but also significantly reduces the solution ambiguity.To improve the computational efficiency,message passing interface programming was used to accelerate the 2D SIP forward modeling and inversion.Synthetic datasets were tested using both serial and parallel algorithms,and the tests suggest that the proposed parallel algorithm is robust and efficient.

A Parallel Algorithm for Adaptive Local Refinement of Tetrahedral Meshes Using Bisection

Local mesh refinement is one of the key steps in the implementations of adaptive finite element methods. This paper presents a parallel algorithm for distributed memory parallel computers for adaptive local refinement of tetrahedral meshes using bisection. This algorithm is used in PHG, Parallel Hierarchical Grid Chttp：//lsec. cc. ac. cn/phg/）, a toolbox under active development for parallel adaptive finite element solutions of partial differential equations. The algorithm proposed is characterized by allowing simukaneous refinement of submeshes to arbitrary levels before synchronization between submeshes and without the need of a central coordinator process for managing new vertices. Using the concept of canonical refinement, a simple proof of the independence of the resulting mesh on the mesh partitioning is given, which is useful in better understanding the behaviour of the biseetioning refinement procedure.

Optimal online algorithms for scheduling on two identical machines under a grade of service

This work is aimed at investigating the online scheduling problem on two parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels, so each job and machine are labelled with the GoS levels, and each job can be processed by a particular machine only when its GoS level is no less than that of the machine. The goal is to minimize the makespan. For non-preemptive version, we propose an optimal online al-gorithm with competitive ratio 5/3. For preemptive version, we propose an optimal online algorithm with competitive ratio 3/2.

Parallel computation of unified finite-difference time-domain for underwater sound scattering

In this work, we treat scattering objects, water, surface and bottom in a truly unified manner in a parallel finitedifference time-domain （FDTD） scheme, which is suitable for distributed parallel computing in a message passing interface （MPI） programming environment. The algorithm is implemented on a cluster-based high performance computer system. Parallel computation is performed with different division methods in 2D and 3D situations. Based on analysis of main factors affecting the speedup rate and parallel efficiency, data communication is reduced by selecting a suitable scheme of task division. A desirable scheme is recommended, giving a higher speedup rate and better efficiency. The results indicate that the unified parallel FDTD algorithm provides a solution to the numerical computation of acoustic scattering.

Parallel Computing of the Underwater Explosion Cavitation Effects on Full-scale Ship Structures

As well as shock wave and bubble pulse loading, cavitation also has very significant influences on the dynamic response of surface ships and other near-surface marine structures to underwater explosive loadings. In this paper, the acoustic-structure coupling method embedded in ABAQUS is adopted to do numerical analysis of underwater explosion considering cavitation. Both the shape of bulk cavitation region and local cavitation region are obtained, and they are in good agreement with analytical results. The duration of reloading is several times longer than that of a shock wave. In the end, both the single computation and parallel computation of the cavitation effect on the dynamic responses of a full-scale ship are presented, which proved that reloading caused by cavitation is non-ignorable. All these results are helpful in understanding underwater explosion cavitation effects.

3D parallel inversion of time-domain airborne EM data

To improve the inversion accuracy of time-domain airborne electromagnetic data, we propose a parallel 3D inversion algorithm for airborne EM data based on the direct Gauss-Newton optimization. Forward modeling is performed in the frequency domain based on the scattered secondary electrical field. Then, the inverse Fourier transform and convolution of the transmitting waveform are used to calculate the EM responses and the sensitivity matrix in the time domain for arbitrary transmitting waves. To optimize the computational time and memory requirements, we use the EM ＂footprint＂ concept to reduce the model size and obtain the sparse sensitivity matrix. To improve the 3D inversion, we use the OpenMP library and parallel computing. We test the proposed 3D parallel inversion code using two synthetic datasets and a field dataset. The time-domain airborne EM inversion results suggest that the proposed algorithm is effective, efficient, and practical.

Parallelization and performance tuning of molecular dynamics code with OpenMP

An OpenMP approach was proposed to parallelize the sequential molecular dynamics(MD) code on shared memory machines. When a code is converted from the sequential form to the parallel form, data dependence is a main problem. A traditional sequential molecular dynamics code is anatomized to find the data dependence segments in it, and the two different methods, i.e., recover method and backward mapping method were used to eliminate those data dependencies in order to realize the parallelization of this sequential MD code. The performance of the parallelized MD code was analyzed by using some performance analysis tools. The results of the test show that the computing size of this code increases sharply form 1 million atoms before parallelization to 20 million atoms after parallelization, and the wall clock during computing is reduced largely. Some hot-spots in this code are found and optimized by improved algorithm. The efficiency of parallel computing is 30% higher than that of before, and the calculation time is saved and larger scale calculation problems are solved.

Parallel programming characteristics of a DSP-based parallel system

This paper firstly introduces the structure and working principle of DSP-based parallel system, parallel accelerating board and SHARC DSP chip. Then it pays attention to investigating the system’s programming characteristics, especially the mode of communication, discussing how to design parallel algorithms and presenting a domain-decomposition-based complete multi-grid parallel algorithm with virtual boundary forecast (VBF) to solve a lot of large-scale and complicated heat problems. In the end, Mandelbrot Set and a non-linear heat transfer equation of ceramic/metal composite material are taken as examples to illustrate the implementation of the proposed algorithm. The results showed that the solutions are highly efficient and have linear speedup.

Navigation Map Data Representation and Parallel Display Algorithm in an Embedded Environment

Map data display is the basic information representation mode under embedded real-time navigation. After a navigation display data set （NDIS_SET） with several dimensions and corresponding mathematical description formula are designed, a series of rules and algorithms are advanced to optimize embedded navigation data and promote data index and input efficiency. A new parallel display algorithm with navigation data named N PDIS is then presented to adapt to limited embedded resources of computation and memory after a normal navigation data display algorithm named NDIS and related problems are analyzed, N_PDIS can synchronously create two preparative bitmapa by two parallel threads and switch one of them to screen automatically. Compared with NDIS, the results show that N_PDIS is more effective in improving display efficiency.