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

Rule-Based Optimization of Delay in Reversible Network

为降低可逆网络的时延,构建了可逆网络的时延模型,并提出相应的可逆网络时延优化算法.将可逆网络表示成乐谱线的形式,每经过一个可逆门就加上相应时延值,可逆门目标位输出时延值取该门所有输出时延的最大值;基于可逆网络中子序列的移动和时延优化规则提出了时延优化算法,该算法分别从左到右和从右到左扫描可逆网络,当有符合时延优化规则的情况时做相应的优化;对比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.