Exact Mapping of Rewritten Linear Functions to Configurable Logic

Inhalt:
We describe a method of mapping linear arithmetic functions to a targeted network of multipliers, adders, registers, muxes, and ROMs holding coefficients. The network may be fairly specific, or made more configurable by varying the primitives’ control signals and adding routing muxes. Examples of possible functions include FIR and IIR filters, convolution, and FFTs. The method implicitly considers rewriting the function, such as by the associative and distributive properties of arithmetic, or methods such as Winograd filtering that benefit from combined computation of successive outputs. The method is intended to be used to implement IP for existing FPGA math blocks, evaluate new FPGA math block architectures, or potentially as a subroutine in high-level synthesis. Illustrative architectures using the PolarFire(TM) FPGA math block are presented, including: a symmetric FIR in which the math block operates at twice the speed of the fabric; a general (asymmetric) FIR that produces one sample per clock cycle with fewer multipliers than taps; and a folded symmetric FIR using fewer memory blocks than multipliers. The method is related to modulo scheduling and relies on a SAT or ILP solver.