A Practical Implementation of Parallel Dynamic Load Balancing for Adaptive Computing in VLSI Device Simulation

We present a new parallel semiconductor device simulation using the dynamic load balancing approach. This semiconductor device simulation based on the adaptive finite volume method with a posteriori error estimation has been developed and successfully implemented on a 16-PC Linux cluster with a message passing interface library. A constructive monotone iterative technique is also applied for solution of the system of nonlinear algebraic equations. Two different parallel versions of the algorithm to perform a complete device simulation are proposed. The first is a dynamic parallel domain decomposition approach, and the second is a parallel current-voltage characteristic points simulation. This implementation shows that a well-designed load balancing simulation can significantly reduce the execution time up to an order of magnitude. Compared with the measured data, numerical results on various submicron VLSI devices are presented, to show the accuracy and efficiency of the method.     

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.     

Parallel Poisson and Biharmonic solvers

In this paper we develop direct and iterative algorithms for the solution of finite difference approximations of the Poisson and Biharmonic equations on a square, using a number of arithmetic units in parallel. Assuming ann×n grid of mesh points, we show that direct algorithms for the Poisson and Biharmonic equations require 0(logn) and 0(n) time steps, respectively. The corresponding speedup over the sequential algorithms are 0(n ²) and 0(n ²logn). We also compare the efficiency of these direct algorithms with parallel SOR and ADI algorithms for the Poisson equation, and a parallel semi-direct method for the Biharmonic equation treated as a coupled pair of Poisson equations.     

Parallel implementation of finite-element/newton method for solution of steady-state and transient nonlinear partial differential equations

Domain decomposition by nested dissection for concurrent factorization and storage (CFS) of asymmetric matrices is coupled with finite element and spectral element discretizations and with Newton's method to yield an algorithm for parallel solution of nonlinear initial-and boundary-value problem. The efficiency of the CFS algorithm implemented on a MIMD computer is demonstrated by analysis of the solution of the two-dimensional, Poisson equation discretized using both finite and spectral elements. Computation rates and speedups for the LU-decomposition algorithm, which is the most time consuming portion of the solution algorithm, scale with the number of processors. The spectral element discretization with high-order interpolating polynomials yields especially high speedups because the ratio of communication to computation is lower than for low-order finite element discretizations. The robustness of the parallel implementation of the finite-element/Newton algorithm is demonstrated by solution of steady and transient natural convection in a two-dimensional cavity, a standard test problem for low Prandtl number convection. Time integration is performed using a fully implicit algorithm with a modified Newton's method for solution of nonlinear equations at each time step. The efficiency of the CFS version of the finite-element/Newton algorithm compares well with a spectral element algorithm implemented on a MIMD computer using iterative matrix methods.Submitted toJ. Scientific Computing, August 25, 1994.     

A Coupled Lattice Boltzmann Method to Solve Nernst–Planck Model for Simulating Electro-osmotic Flows

In this paper, we focus on the nonlinear coupling mechanism of the Nernst–Planck model and propose a coupled lattice Boltzmann method (LBM) to solve it. In this method, a new LBM for the Nernst–Planck equation is developed, a multi-relaxation-time (MRT)-LBM for flow field and an LBM for the Poisson equation are used. And then, we discuss the choice of the model and found that the MRT-LBM is much more stable and accurate than the LBGK model. A reasonable iterative sequence and evolution number for each LBM are proposed by considering the properties of the coupled LBM. The accuracy and stability of the presented coupled LBM are also discussed through simulating electro-osmotic flows (EOF) in micro-channels. Furthermore, to test the applicability of it, the EOF with non-uniform surface potential in micro-channels based on the Nernst–Planck model is simulated. And we investigate the effects of non-uniform surface potential on the pattern of the EOF at different external applied electric fields. Finally, a comparison of the difference between the Nernst–Planck model and the Poisson–Boltzmann model is presented.     

A Finite Difference Method and Analysis for 2D Nonlinear Poisson–Boltzmann Equations

A fast finite difference method based on the monotone iterative method and the fast Poisson solver on irregular domains for a 2D nonlinear Poisson–Boltzmann equation is proposed and analyzed in this paper. Each iteration of the monotone method involves the solution of a linear equation in an exterior domain with an arbitrary interior boundary. A fast immersed interface method for generalized Helmholtz equations on exterior irregular domains is used to solve the linear equation. The monotone iterative method leads to a sequence which converges monotonically from either above or below to a unique solution of the problem. This monotone convergence guarantees the existence and uniqueness of a solution as well as the convergence of the finite difference solution to the continuous solution. A comparison of the numerical results against the exact solution in an example indicates that our method is second order accurate. We also compare our results with available data in the literature to validate the numerical method. Our method is efficient in terms of accuracy, speed, and flexibility in dealing with the geometry of the domain     

Incomplete block-factorization preconditioners for solving three-dimensional elliptic difference equations on systolic processors ∗ ∗∗

An architecture of a parallel computing system for matrix computations based on a systolic array of processors is considered and a version of incomplete block-factorizations of sparse matrices that arise in finite difference solution of three dimensional elliptic differential equations of second order is studied. The parallelization, both of factorization and solution processes, is investigated and the implementation of a stationary preconditioned iterative method on the considered computer architecture is described. Representative numerical tests for the efficiency of the consecutive version of the method for solving three-dimensional finite difference approximations to the Poisson equation are presented.     

Three-dimensional Poisson solver for a charged beam with large aspect ratio in a conducting pipe

In this paper, we present a three-dimensional Poisson equation solver for the electrostatic potential of a charged beam with large longitudinal to transverse aspect ratio in a straight and a bent conducting pipe with open-end boundary conditions. In this solver, we have used a Hermite-Gaussian series to represent the longitudinal spatial dependence of the charge density and the electric potential. Using the Hermite-Gaussian approximation, the original three-dimensional Poisson equation has been reduced into a group of coupled two-dimensional partial differential equations with the coupling strength proportional to the inverse square of the longitudinal-to-transverse aspect ratio. For a large aspect ratio, the coupling is weak. These two-dimensional partial differential equations can be solved independently using an iterative approach. The iterations converge quickly due to the large aspect ratio of the beam. For a transverse round conducting pipe, the two-dimensional Poisson equation is solved using a Bessel function approximation and a Fourier function approximation. The three-dimensional Poisson solver can have important applications in the study of the space-charge effects in the high intensity proton storage ring accelerator or induction linear accelerator for heavy ion fusion where the ratio of bunch length to the transverse size is large.     

A group-theory method to find stationary states in nonlinear discrete symmetry systems

In the field of nonlinear optics, the self-consistency method has been applied to searching optical solitons in different media. In this paper, we generalize this method to other systems, adapting it to discrete symmetry systems by using group theory arguments. The result is a new technique that incorporates symmetry concepts into the iterative procedure of the self-consistency method, that helps the search of symmetric stationary solutions. An efficient implementation of this technique is also presented, which restricts the computational work to a reduced section of the entire domain and is able to find different types of solutions by specifying their symmetry properties. As a practical application, we develop an efficient algorithm for solving the nonlinear Schrödinger equation with a discrete symmetry potential.     

基于动态网格细分的烟雾模拟

提出了一种基于动态网格细分的烟雾模拟方法,该方法主要采取图形设备上的动态网格管理对烟雾进行并行处理以达到泊松方程的迭代求解。为了实现高性能,利用高速缓存以提高存取权限和适应硬件的能力。实验结果表明,该方法能够实现比较快速的模拟,结果比较令人满意。     

An Iterative Method for Optimal Feedback Control and Generalized HJB Equation

In this paper, a new iterative method is proposed to solve the generalized Hamilton-Jacobi-Bellman (GHJB) equation through successively approximate it. Firstly, the GHJB equation is converted to an algebraic equation with the vector norm, which is essentially a set of simultaneous nonlinear equations in the case of dynamic systems. Then, the proposed algorithm solves GHJB equation numerically for points near the origin by considering the linearization of the non-linear equations under a good initial control guess. Finally, the procedure is proved to converge to the optimal stabilizing solution with respect to the iteration variable. In addition, it is shown that the result is a closed-loop control based on this iterative approach. Illustrative examples show that the update control laws will converge to optimal control for nonlinear systems.      

Efficient Gradient‐Domain Compositing Using an Approximate Curl‐free Wavelet Projection

Gradient‐domain compositing has been widely used to create a seamless composite with gradient close to a composite gradient field generated from one or more registered images. The key to this problem is to solve a Poisson equation, whose unknown variables can reach the size of the composite if no region of interest is drawn explicitly, thus making both the time and memory cost expensive in processing multi‐megapixel images. In this paper, we propose an approximate projection method based on biorthogonal Multiresolution Analyses (MRA) to solve the Poisson equation. Unlike previous Poisson equation solvers which try to converge to the accurate solution with iterative algorithms, we use biorthogonal compactly supported curl‐free wavelets as the fundamental bases to approximately project the composite gradient field onto a curl‐free vector space. Then, the composite can be efficiently recovered by applying a fast inverse wavelet transform. Considering an n‐pixel composite, our method only requires 2n of memory for all vector fields and is more efficient than state‐of‐the‐art methods while achieving almost identical results. Specifically, experiments show that our method gains a 5× speedup over the streaming multigrid in certain cases.     

Quasilinearization approach to computations with singular potentials

We pioneered the application of the quasilinearization method (QLM) to the numerical solution of the Schrödinger equation with singular potentials. The spiked harmonic oscillator r²+λr−α is chosen as the simplest example of such potential. The QLM has been suggested recently for solving the Schrödinger equation after conversion into the nonlinear Riccati form. In the quasilinearization approach the nonlinear differential equation is treated by approximating the nonlinear terms by a sequence of linear expressions. The QLM is iterative but not perturbative and gives stable solutions to nonlinear problems without depending on the existence of a smallness parameter. The choice of zero iteration is based on general features of solutions near the boundaries.We show that the energies of bound state levels in the spiked harmonic oscillator potential which are notoriously difficult to compute for small couplings λ, are easily calculated with the help of QLM for any λ and α with accuracy of twenty significant figures.     

Computationally efficient simultaneous policy update algorithm for nonlinear H∞ state feedback control with Galerkin's method

The main bottleneck for the application of H_∞ control theory on practical nonlinear systems is the need to solve the Hamilton–Jacobi–Isaacs (HJI) equation. The HJI equation is a nonlinear partial differential equation (PDE) that has proven to be impossible to solve analytically, even the approximate solution is still difficult to obtain. In this paper, we propose a simultaneous policy update algorithm (SPUA), in which the nonlinear HJI equation is solved by iteratively solving a sequence of Lyapunov function equations that are linear PDEs. By constructing a fixed point equation, the convergence of the SPUA is established rigorously by proving that it is essentially a Newton's iteration method for finding the fixed point. Subsequently, a computationally efficient SPUA (CESPUA) based on Galerkin's method, is developed to solve Lyapunov function equations in each iterative step of SPUA. The CESPUA is simple for implementation because only one iterative loop is included. Through the simulation studies on three examples, the results demonstrate that the proposed CESPUA is valid and efficient. Copyright © 2012 John Wiley & Sons, Ltd.     

Monotone iterative simulation of the multilane traffic dispersion model

In this study, the multilane traffic flow is modeled as a nonlinear Poisson equation in a two-dimensional space. The model is derived from the interaction among vehicles and the assumption that vehicles will tend toward the equilibrium state under a given traffic condition. A monotone iterative scheme for the nonlinear model, which is a finite difference approximation of the model, is presented. The convergency is also discussed herein. At last, a numerical example is employed to explain the model.     

The fundamental collocation method applied to the nonlinear poisson equation in two dimensions

The fundamental collocation method is adapted to the nonlinear Poisson equation in two dimensions with mixed boundary conditions of the Dirichlet and Neumann type. The technique is an iterative collocation procedure which requires a representation of the boundary of a finite region by N points and of the interior by M points. The order of the problem as determined by the dimensions of the collocation matrices is N × N for each iteration. The method also employs an adjustable parameter S which can be used to check for stability. The accuracy and efficiency are shown to be quite good on three example problems, two of which are for heat-transfer and non-Newtonian laminar flow. Suggestions for improving the method are made.     

Simulation of bipolar high-voltage devices in the neighborhood of breakdown

This paper investigates numerical techniques for the solution of the system of nonlinear elliptic PDE's that simulates bipolar semiconductor devices under high reverse bias voltage. Bipolar devices are usually modeled as a set of three elliptic PDE's representing the field equation and the electron and hole current continuity equations. However, these equations can be solved effectively in the case of low-voltage devices only, e.g. by use of the the BAMBI program. As shown in this paper, it is possible to simplify the model in case of high-voltage devices. A powerful software toolkit, ELLAPACK, has been used to solve the resulting two-dimensional Poisson equation. ELLAPACK enabled us to easily compare several numerical solution techniques for their efficiency to solve this problem. To analyze the effectiveness of the toolkit as a whole, a comparison was made between ELLAPACK and a special-purpose program written by us.     

A hybrid algorithm for approximate optimal control of nonlinear Fredholm integral equations

In this paper, a novel hybrid method based on two approaches, evolutionary algorithms and an iterative scheme, for obtaining the approximate solution of optimal control governed by nonlinear Fredholm integral equations is presented. By converting the problem to a discretized form, it is considered as a quasi-assignment problem and then an iterative method is applied to find an approximate solution for the discretized form of the integral equation. An analysis for convergence of the proposed iterative method and its implementation for numerical examples are also given.     

Computer simulation of the temperature and electromagnetic field in an inductively heated semiconductor

The electromagnetic and temperature fields in an inductively heated semiconductor interact with each other in a sophisticated way through the heat dependence of the material parameters and the heat source density determined by the eddy currents. The paper deals with a computer analysis of the interacting fields taking into account the nonlinear temperature dependence of the material parameters. The basic electromagnetic and heat conduction equations are discussed, and a transformation will be introduced for the calculation of the electromagnetic field outside the material. The nonlinear equation system resulting from discretization is solved by an iterative method, whose relaxation factor is optimized during the iteration. Experiences gained in the course of the numerical calculations are reported, and results of a calculation performed with specific physical data are described.     

一种针对大波数Helmholtz方程的高性能并行预条件迭代求解算法

针对传统串行迭代法求解大波数Helmholtz方程存在效率低下且受限于单机内存的问题,提出了一种基于消息传递接口(Message Passing Interface,MPI) 的并行预条件迭代法。该算法利用复移位拉普拉斯算子对Helmholtz方程进行预条件处理,联合稳定双共轭梯度法和基于矩阵的多重网格法来求解预条件方程离散后的大规模线性系统,在Linux集群系统上基于 MPI环境实现了求解算法的并行计算,重点解决了多重网格的并行划分、信息传递和多重网格组件的构建问题。数值实验表明,对于大波数问题,提出的算法具有良好的并行加速比,相较于串行算法极大地提高了计算效率。