A fast parallel algorithm for routing in permutation networks
A fast parallel algorithm for routing in permutation networks
复制标题
排列网络中路由的快速并行算法
DOI：
--
复制
发表时间：
1981
影响因子：
3.7
通讯作者：
L. Valiant
中科院分区：
文献类型：
--
作者：
G. Lev;N. Pippenger;L. Valiant
给出了置换网络中的路由算法，即计算实现给定置换的开关设置。该算法需要串行时间<i>O</i>（<i>n</i>（log<i>N</i>）<sup>2</sup>）（对于一个处理器随机访问<i>O</i>（<i>n</i>）字的存储器）或并行时间<i>O</i>（（log<i>n</i>）<sup>3</sup>）（对于<i>n个</i>同步处理器无冲突随机访问<i>O</i>（<i>n</i>）字的公共存储器）。当所有的开关大小都是2的整数幂时，这些时间界限可以通过进一步的对数因子来减少。
An algorithm is given for routing in permutation networks-that is, for computing the switch settings that implement a given permutation. The algorithm takes serial time <i>O</i>(<i>n</i>(log <i>N</i>)<sup>2</sup>) (for one processor with random access to a memory of <i>O</i>(<i>n</i>) words) or parallel time <i>O</i>((log <i>n</i>)<sup>3</sup>) (for <i>n</i> synchronous processors with conflict-free random access to a common memory of <i>O</i>(<i>n</i>) words). These time bounds may be reduced by a further logarithmic factor when all of the switch sizes are integral powers of two.