Synthesizing multi-phase HDL programs

We present a novel approach to synthesizing hardware implementation from hardware description language (HDL) programs that could not be automatically synthesized before. We deal with multi phase/multi stage designs, and demonstrate that this problem can be mapped into a class of timed automata which is called “multi phase” finite state machines (FSM). We propose three procedures to decompose a multi phase FSM into a network of interacting single phase FSMs. The first two procedures are based on the region graph expansion of a timed automata (R. Alur and D. Dill, 1990). The first procedure extracts single phase FSMs iteratively from a region graph. The second procedure formulates the decomposition problem as an integer linear programming. These two region graph based procedures may suffer from explosion in the number of regions. The third procedure, without building intermediate transition structures, constructs single phase FSMs directly from the transition structure of a multi phase FSM. It is more efficient but redundancy might exist in the constructed FSMs. Not only can these procedures be used for the synthesis from a multi phase design, they can also be used to speed up FSM based simulation