Method for Mapping Cyclo-Dynamic Dataflow Into Pipelined Datapath

An overview of high-level synthesis (HLS) systems for designing pipelined datapaths is presented in the paper. The goal is to explore methods of mapping algorithms to the pipelined datapaths implementing the cyclic data flow graphs with dynamic schedules. The cyclo-dynamic dataflow (CDDF) is selected as the very expressive model for describing a wide domain of the dataflow algorithms. CDDF is distinguished in that, the algorithm period depends on the calculated data and has a dynamic schedule. A set of mapping conditions is formulated that provide the deadlock-free schedule of CDDF when it is mapped into the pipelined datapath. Due to the proposed method, the algorithm is represented by a set of CDDF and finite state machines (FSMs). The latter are subgraphs of CDDF. CDDF is optimized using retiming and pipelining methods. After that CDDF and its FSMs are described by the hardware description language like VHDL as well as the synchronous dataflow is described. The proposed method involves describing cyclo-dynamic data flow graphs in VHDL and optimizing them for implementation in the field programable gate arrays (FPGAs). The example of the sequence detector design shows the method implementation in detail. More sophisticated LZW decompression algorithm mapping demonstrates that the proposed method is rather effective and can give the pipelined datapath which effectivenes is comparable with that of the best hardware solution. The method can be implemented in modern HLS systems.