Abstract

Field Programmable Gate Arrays (FPGAs) have become an increasingly important technology in accelerating scientific computing (SC). A frequent task in SC is the solution finding of systems of linear equations (LE). For finding such solution there are a number of well studied algorithms. One algorithm that belongs to the class of iterative methods for solving LEs, and has proven to be very ecient in hardware, is the Conjugate Gradient (CG) method [1]. In this work we present a hardware CG method which takes advantage of the banded structure present in many common problems. With the flexibility provided by FPG As, 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.