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

摘要：

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

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

所属期刊栏目：28

分类号：TP391.72(计算技术、计算机技术)

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

在线出版日期：2016-07-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1003-1007