A floating-point solver for band structured linear equations

Field programmable gate arrays (FPGAs) have gradually been increasing their capacities and started to incorporate optimized coarse-grained modules such as BlockRAMs, multipliers, and even processors. These developments have extended their field of applications and one field that has been gaining significant interest is the acceleration of floating-point scientific computing. In this field, a recurring subtask is the solution of systems of linear equations. One well studied method that has proven to be very efficient in software and robust at finding such solutions is the conjugate gradient (CG) algorithm. In this paper we present a hardware CG method which takes advantage of the banded structure present in many common problems. With the flexibility provided by FPGAs, this implementation employs wide-parallelization to convert the per iteration computation time for an order n matrix with band width w from Theta(nw) clock cycles for a software implementation to Theta(n) in hardware. It also explores deep-pipelining so that solutions to P problems are produced every Theta(n) cycles opposed to every Theta(Pnw) cycles in software. Results demonstrate that performances up to 32 GFLOPs are achievable on a Virtex5-330T FPGA and a software comparison reports significant speed-ups in relation to high-end CPUs.