Multigrid solvers in reconfigurable hardware. (c2006)

Abstract

Physical, chemical and biological phenomena are modeled using Partial Differential Equations (PDEs). Interpreting and solving PDEs is the key for understanding the behavior of the modeled system. The broad field of modeling real systems has drawn the researchers' attention for designing efficient algorithms for solving PDEs. The Multigrid method has been shown to be the fastest method due to its high convergence rate regardless of the problem size. However, the computation of such solvers is complex and time consuming. Many attempts for exploiting the inherent parallelism of Multigrid have been made to achieve the desired efficiency and scalability of the method. Yet, most efforts fail in this respect due to many factors (time and resources) governed by software implementations upon parallelizing the algorithm. Reconfigurable Computing (RC), a new computing paradigm which combines the flexibility of software and the performance of hardware, is best suited for such computational intensive applications. In this thesis, we present a hardware implementation of the V-cycle MG algorithm for the solution of a 2D Poisson Equation using different classes of Field Programmable Gate Arrays (FPGAs). We use Handel-C, a high-level design language for hardware development, to code our design which is synthesized, and placed & routed using the FPGAs proprietary software. Our design has been tested using the Handel-C simulator; afterwards, we have targeted a Xilinx Virtex II Pro FPGA, Altera Stratix FPGA and the RCI 0 board from Celoxica. The performance of MG on hardware has been compared with the performance of a software version, written in C++, and running on a General Purpose Processor. Final results demonstrate that running the V -cycle MG on an FPGA exploits the inherent parallelism of the algorithm yielding an algorithm which outperforms a software version.