A high-level design framework for the automatic generation of high-throughput systolic binomial-tree solvers
File(s)TVLSI_2017_paper.pdf (800.06 KB)
Accepted version
Author(s)
Tavakkoli, A
Thomas, DB
Type
Journal Article
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.
Date Issued
2018-02-01
Date Acceptance
2017-10-05
Citation
IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2018, 26 (2), pp.341-354
ISSN
1063-8210
Publisher
Institute of Electrical and Electronics Engineers
Start Page
341
End Page
354
Journal / Book Title
IEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume
26
Issue
2
Copyright Statement
© 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Identifier
https://ieeexplore.ieee.org/document/8081850
Subjects
Science & Technology
Technology
Computer Science, Hardware & Architecture
Engineering, Electrical & Electronic
Computer Science
Engineering
Binomial-tree numerical method
field-programmable gate arrays (FPGAs)
hardware design automation
high-level synthesis (HLS)
option pricing
reconfigurable hardware accelerators
systolic arrays
EXPLORING RECONFIGURABLE ARCHITECTURES
OPTION
Computer Hardware & Architecture
0805 Distributed Computing
0906 Electrical and Electronic Engineering
1006 Computer Hardware
Publication Status
Published
Date Publish Online
2017-10-24