Synthia: Synthesis of Interacting Automata targeting LUT-based FPGAs

This paper details the development, implementation, and results of Synthia, a system for the synthesis of Finite State Machines (FSMs) to field-programmable logic. Our approach uses a novel FSM decomposition technique, which partitions both the states of a machine and its inputs between several sub-machines. The technique developed exploits incomplete output specifications in order to minimize the interconnect complexity of the resulting network, and uses a custom Genetic Algorithm to explore the space of possible partitions. User-controlled trade-off between logic depth and logic area is allowed, and the algorithm itself during execution determines the number of sub-FSMs in the resulting decomposition. The results from MCNC benchmarks applied to Xilinx XC4000 and Altera FLEX8000 devices show a typical speedup of 35 % to 37% combined with a typical area reduction of 26 % to 33 % over a standard one-hot encoding of the original circuit. Final results will be available within weeks and incorporated into the paper