FPGA based path solvers for DFGs in high level synthesis

Retiming is a transformation which can be applied to Digital Signal Processing Blocks that can increase the clock frequency. Folding in retiming can also reduce the resource utilization and power consumption. This transformation requires computation of critical path and shortest path at various stages. In this particular work, a FPGA based path finder is designed to compute critical path and shortest path in the Data Flow Graphs (DFGs). Since this path computation is performed using FPGA based IC, the speed of retiming transformation increases. This also reduces the resource utilization of the general purpose machine in which retiming transformation is usually performed. Critical path in sequential circuit is defined as the longest path between any two storage components. This determines the minimum feasible clock period for any sequential circuit. We need to compute the critical path before we apply retiming transformation to any digital Signal Processing block. Similarly shortest path computation is required in retiming while solving the system inequalities in the constraint graph. In this work, shortest path computation is performed using Floyd-Warshall algorithm. Since FPGA based hardware for path solvers performs much faster when compared to general purpose processor [where actual retiming is done], the speed with which the retiming transformation is performed increases. Xilinx ISE design suit is used with device as SPARTEN3E XC3S250E for the work presented.