John Cole
  • MCS, 2005 - current.
    University of New Brunswick, Canada
  • BCS, 2000 - 2005
    University of New Brunswick, Canada


Research Topic: FPGAs, Tridiagonal Toeplitz

Thesis Research:
Pipelined Projection Algorithms for FPGA Technology
Linear systems of equations with Toeplitz coefficient matrices often appear in mathematics and applied science problems. Systems of this form are often the result of the numerical Finite Difference Methods applied to approximate Differential Equations with a system of linear equations. The sparse structure of Toeplitz matrices lend themselves well to iterative algorithms, such as the projection methods, and are highly favored techniques for solving large systems of linear equations. Field Programmable Gate Arrays (FPGAs) have been growing in popularity among the scientific community due to potential for impressive performance evaluating floating point operations in parallel. The regular, sparse, structure inherent in Toeplitz systems admits a highly efficient FPGA projection algorithm pipeline. We will analyze a selection of projection algorithms and derive an optimal pipelined hardware designs. These high level designs allow us to predict, with a high level of accuracy, the actual performance obtainable. The design for the steepest descent pipeline was prototyped on an Altera DE2 FPGA development board. The actual results, matching the theoretical predictions, compare favorably against an efficient software implementation of the algorithm. Development time was a considerable drawback during development, yet many reusable components were produced which could be used to implement various other FGPA algorithms.

Thesis Supervisor(s):
Larry Garey and Ken Kent