Retiming finite state machines to control hardened data-paths

We introduce fine grain scheduling (FGS) as a postprocessing step to circuits classically designed as a datapath controlled by a finite state machine (FSM). Such circuits may have timing errors, particularly if they are generated by high level synthesis (HLS) tools that make use of crude temporal estimates during scheduling. FGS reschedules the FSM to ensure correct execution at a requested frequency on the data-path. The proposed algorithm takes into account all the electrical constraints of the data-path, namely propagation times, set-up and hold times of memorization elements, and even delays due to the interconnects if the data-path is placed and routed like HLS algorithms, FGS supports multi-operators cells, multi-cycle operators and chaining. However it also makes use of multi-cycles chaining to allow the chaining of several operators over several cycles without intermediate memorizations. Experimentation of FGS on an MPEG2 variable length decoder and a full MJPEG decoder has demonstrated that the approach is particularly well suited for the design of asynchronous coprocessors. Synchronous processors cannot be scheduled by FGS because the inputs and outputs dates are modified.