数字电路并行全入度拓扑排序优化算法

摘要

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 optimi-zation algorithm are proposed, which based on the principle of topological-sort and the circuit parallel char-acteristic. The possible position in which the pipeline in the circuit is inserted and the corresponding infor-mation 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 retim-ing 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.%针对当数字电路的时序难以满足优化目标时要进行设计迭代的问题，通过改进产生线性序列的拓扑排序算法，提出了并行全入度拓扑排序和数字电路并行全入度拓扑排序优化算法。该算法通过对电路的有向图并行全入度拓扑排序，得到电路中插入寄存器可选位置的详细信息；然后结合得到的信息和优化目标，直接选择流水线插入位置优化电路，无需设计迭代。实验结果表明，插入同样级数流水线时，使用文中算法优化的电路面积比重定时优化的减少20%~40%；与经典有效重定时判定算法FEAS相比，该算法拥有更低的时间复杂度。