  Productivity issues such as lengthy compilation and limited code reuse have
restricted usage of field-programmable gate arrays (FPGAs), despite significant
technical advantages. Recent work into overlays -- virtual coarse-grained
architectures implemented atop FPGAs -- has aimed to address these concerns
through abstraction, but have mostly focused on pipelined applications with
minimal control requirements. Although research has introduced overlays for
finite-state machines, those architectures suffer from limited scalability and
flexibility, which we address with a new overlay architecture using memory
decomposition on transitional logic. Although our overlay provides modest
average improvements of 15% to 29% fewer lookup tables for individual
finite-state machines, for the more common usage of an overlay supporting
different finite-state machines, our overlay achieves a 77% to 99% reduction in
lookup tables. In addition, our overlay reduces compilation time to tenths of a
second to enable rapid iterative-development methodologies.
