A high-level design framework for the automatic generation of high-throughput systolic binomial-tree solvers

Abstract

The binomial-tree model is a numerical method widely used in finance with a computational complexity which is quadratic with respect to the solution accuracy. The existing research has employed reconfigurable computing to provide faster solutions compared with general-purpose processors, but they require low-level manual design by a hardware engineer, and can only solve American options. This paper presents a formal mathematical framework that captures a large class of binomial-tree problems, and provides a systolic data-movement template that maps the framework into digital hardware. This paper also presents a fully automated design flow, which takes C-level user descriptions of binomial trees, with custom data types and tree operations, and automatically generates fully pipelined reconfigurable hardware solutions in field-programmable gate array (FPGA) bit-stream files. On a Xilinx Virtex-7 xc7vx980t FPGA at a 100-MHz clock frequency, we require 54-μs latency to solve three 876-step 32-bit fixed-point American option binomial trees, with a pricing rate of 114k trees/s. From the same device and in comparison to the existing solutions with equivalent FPGA technology, we always achieve better throughput. This ranges from 1.4× throughput compared with a hand-tuned register-transfer level systolic design, to 9.1× and 5.6× improvement with respect to scalar and vector architectures, respectively.