Accelerating Implicit Finite Difference Schemes Using a Hardware Optimised Implementation of the Thomas Algorithm for FPGAs
Samuel J. Palmer, David Barrie Thomas · arXiv (Cornell University) · 2014
The design and implementation of the Thomas algorithm optimised for hardware acceleration on an FPGA is presented. The hardware based algorithm combined with custom data flow and low level parallelism available in an FPGA reduces the overall complexity from 8N down to 5N arithmetic operations, and combined with a data streaming interface reduces memory overheads to only 2 N-length vectors per N-tridiagonal system to be solved. The Thomas Core developed allows for multiple tridiagonal systems to be solved in parallel, giving potential use for solving multiple implicit finite difference schemes or accelerating higher dimensional alternating-direction-implicit schemes used in financial derivatives pricing. This paper also discusses the limitations arising from the fixed-point arithmetic used in the design and how the resultant rounding errors can be controlled to meet a specified tolerance level.