基于规则的可逆网络时延优化算法  

Rule-Based Optimization of Delay in Reversible Network

作　　者：张海豹[1] 管致锦[2] 程学云[2] 

机构地区：[1]南通大学电子信息学院,南通226019 [2]南通大学计算机科学与技术学院,南通226019

出　　处：《计算机辅助设计与图形学学报》2013年第11期1746-1758,共13页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(60873069)

摘　　要：为降低可逆网络的时延,构建了可逆网络的时延模型,并提出相应的可逆网络时延优化算法.将可逆网络表示成乐谱线的形式,每经过一个可逆门就加上相应时延值,可逆门目标位输出时延值取该门所有输出时延的最大值;基于可逆网络中子序列的移动和时延优化规则提出了时延优化算法,该算法分别从左到右和从右到左扫描可逆网络,当有符合时延优化规则的情况时做相应的优化;对比2种情况所得可逆网络的时延值,输出时延最优网络.对国际认可的所有3变量可逆函数及部分具有代表性的Benchmark例题进行验证的结果表明,文中算法能有效地减少可逆网络的时延,降低可逆网络的量子代价.To reduce the delay of reversible network, we built delay model of reversible network, and put forward a delay optimization algorithm of reversible network. Reversible network was shown in music line style, the corresponding delay values were accumulated after passing every reversible gate; delay of target output took the maximum value of all output delay of the gate. The proposed optimization algorithm was based on moving and simplification rules of sub-sequence in reversible network. The algorithm scanned reversible network bidirectionally and optimized it when satisfying the delay optimization rules. We can obtain two results according to the scanning direction, and the result with less delay is our last result. The experimental results on all 3-variables reversible functions and some representative examples in the Benchmark show that, the delay in reversible network can be reduced effectively and the cost of reversible network is decreased.

关 键 词：可逆逻辑综合 可逆函数 Toffoli门 可逆网络 时延 

分 类 号：TP302.2[自动化与计算机技术—计算机系统结构]