摘要
通过分析两类特殊置换———组内置换和组置换的特征 ,利用这两种置换存在无冲突路由算法的特性给出了FFT运算在分组光纤被动星型网上的实现及其路由算法 .在适当分组的情况下 ,本算法在n个处理器的分组被动星型网上计算n点FFT的总通信开销为T =2logn+ 1个时间片 ,此时硬件上需要n个连接器和 2n n个发送器和接收器 ,算法的时间代价和硬件代价平衡 ,算法性能达到最优 .
The characteristics of two kinds of special permutations, in group permutation and group permutation are analysed, and their conflict free routing algorithms are given. Based on this fact, the FFT algorithm's implementation and its routing algorithm on partitioned optical passive star network are given. When the POPS' group number g equals the group size d, the algorithm gets the optimal performance and the balance of the time cost and the hardware cost. Under this condition, the n node FFT calculation could be executed in T=2\%log\%n+1 time slot in an n process POPS with n couplers and 2nn transmitters.
