论文部分内容阅读
Benes网络是多级互联网络中的非阻塞网络;任何置换都能被分解为两个半置换,每一个半置换都是在Benes网络内用一条路径实现的最大的部分置换。然而,实现连接要求的分解算法的时间复杂度与置换的大小成正比。在此文中,我们给出半置换可分解性的相似证明,提议对数时间复杂度的并行分解算法。这个算法在Benes网络中最理想的高速无阻塞路由步骤也在此文中介绍。
The Benes network is a non-blocking network in a multistage Internet; any permutation can be decomposed into two semi-permutations, each of which is the largest partial permutation that one path achieves within a Benes network. However, the time complexity of the decomposition algorithm that implements the connection requirements is proportional to the size of the permutation. In this paper, we give a similar proof of semi-permutability and propose a parallel decomposition algorithm for log-time complexity. The optimal high-speed, non-blocking routing procedure for this algorithm in Benes networks is also covered in this article.