论文部分内容阅读
对于一N×N的Benes可重排非阻塞网络,本文提出了两种半自动选路法:单边法和中间选路法。前者仅对网络的一半开关逐个进行设置,另一半则采用自选路法设置之,在单处理机上这种设置时间为较之Waksman的算法速度提高了一倍;后者使用相联存贮模型,将源和目的地址对在网络的中间级(即第logN级)进行适当的排列,使得左右两边的开关设置可以利用源和目的地址自动选路。此算法的时间复杂度为O(N),较之Waksman的算法平均加速了O(logN)倍。