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

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

作　　者：史江义[1] 高睿怡 舒浩[1] 马佩军[1] 邸志雄[2] 

机构地区：[1]西安电子科技大学宽带隙半导体技术国家重点学科实验室,西安710071 [2]西南交通大学信息科学与技术学院,成都611756

出　　处：《计算机辅助设计与图形学学报》2016年第6期1003-1007,共5页Journal of Computer-Aided Design & Computer Graphics

基　　金：中央高校基本科研业务费专项资金(A0920502051513-67);国家自然科学基金青年科学基金(61504110)

摘　　要：针对当数字电路的时序难以满足优化目标时要进行设计迭代的问题, 通过改进产生线性序列的拓扑排序算法, 提出了并行全入度拓扑排序和数字电路并行全入度拓扑排序优化算法. 该算法通过对电路的有向图并行全入度拓扑排序, 得到电路中插入寄存器可选位置的详细信息; 然后结合得到的信息和优化目标, 直接选择流水线插入位置优化电路, 无需设计迭代. 实验结果表明, 插入同样级数流水线时, 使用文中算法优化的电路面积比重定时优化的减少20%-40%; 与经典有效重定时判定算法FEAS 相比, 该算法拥有更低的时间复杂度.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.

关 键 词：优化算法 并行全入度拓扑排序 有向图 流水线设计 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]