A Digital Circuit Parallel All-indegree Topological-sort Optimization Algorithm

The design iteration is necessary, when a design can’t reach the optimization target after retiming. To cope with this problem, PAITS（parallel all-indegree topological-sort） and digital circuit PAITS optimization algorithm are proposed, which based on the principle of topological-sort and the circuit parallel characteristic. The possible position in which the pipeline in the circuit is inserted and the corresponding information can be obtained after the circuit is sorted by PAITS. Finally the circuit can be optimized without its RTL code being rewritten. The experimental results also demonstrated significant improvement over retiming algorithms in area by reduction of 20%~40% with the same registers stage in. Moreover, PAITS’s time complexity is prominently reduced compared with FEAS.