On Feasibility of FPGAs Without Dedicated Programmable Interconnect Structure
Anastasiia Kucherenko, Stefan Nikolić, Paolo Ienne · 2019
It is a well known fact that a great majority of FPGA chip area goes into the programmable interconnect structure. Since area consumption is mostly proportional to the level of flexibility the interconnect structure offers, how much of this flexibility is really needed for the implementation of any design of interest is a logical question to pose. Going one step further, one may wonder if a dedicated programmable interconnect structure is even necessary. This work answers exactly this second question by providing constructive capability proofs, for a broad class of FPGA architectures composed solely of look-up tables (LUTs) connected in a fixed manner, to implement any circuit graph. Our proposed architectures consist of identical cells of LUTs with fixed connections, arranged on a 2D grid. Direct wires between cell input and output pins are also allowed, enabling long uninterrupted connections. We begin by formalizing the above architecture class, and then describe an algorithm capable of mapping any circuit on one specific member of it, in which each cell consists of a single 4-LUT. We derive area and runtime bounds for the algorithm, and finally extend it to be applicable to any architecture in which no LUT receives more than K - 4 inputs from within the cell (K is LUT size) and the number of sink LUTs of the cell does not exceed the number of source LUTs. Presented algorithms serve to answer the posed question, but, due to area-inefficiency, do not have much practical value at this point.