High-Performance VLSI Model Elliptic Solvers

摘要

VLSI parallel algorithms for a solution of fundamental elliptic problems with Laplace operators (Dirichlet and first boundary value problem for Poisson and biharmonic equation respectively) on a rectangular N × N grid are proposed. A standard multigrid algorithm is adopted for Poisson equation which allows a parallel solution of this problem in T = O(logN) parallel steps. A special network consisting of N × N processor elements and of O(N logN) interconnection lines in each direction results in a design the area of which is A = O(N~2 log~2 N). AT~2 estimation for a complexity of this Poisson solver is O(N~2log~4 N) which improves the best result known until now by a factor of O(N/logN). This VLSI multigrid Poisson solver is applied to the semidirect method for solving the biharmonic equation. The parallel time of the algorithm is O(N~(1/2) log~2 N) and the area needed is A = O(N~3logN). The total complexity for such VLSI semidirect solver is AT~2 = O(N~4log~5N).