Accelerating an iterative Helmholtz solver with FPGAs

Solution of the Helmholtz equation is the main computational burden of full-waveform inversion in the frequency domain. For this task we employ the CARP-CG algorithm (Gordon & Gordon 2010), an iterative solver that preconditions the original Helmholtz system into an equivalent symmetric positive definite system and then applies the method of conjugate gradients. Forming the matrix for the new system is not necessary as its multiplicative action on a vector is implemented using a series of projections onto the rows of the original system. Our contribution is implementing CARP-CG for a host + accelerator (FPGA) computing environment. The computational paradigm is one of dataflow: vector and matrix elements are streamed from memory through the accelerator which applies the row projections. The advantage of an FPGA to process streams of data is that unless the algorithm is memory bandwidth limited, computation time is directly proportional to the amount of data. The complexity of the algorithm implemented on the FPGA is irrelevant since all the operations programmed onto the FPGA happen in the same clock tick. In contrast, on a CPU, more complex algorithms require more clock ticks as the instructions are executed sequentially, or with only a small amount of parallelism. Ongoing work porting the CARP-CG algorithm to the accelerator is presented.