Development of fast routing algorithms using adaptation and randomization

点击翻译按钮获取中文摘要

Our model in this research is a distribution of N processors on a √<N>×√<N> mesh, where each processor is connected with four neighboring processors. Each processor has a constant queue size, namely, a processor can hold only a constant number of packets. At a unit step, each processor can send a packet to one of four neighbors.We treat a permutation routing problem on the above model. In this problem, each processor initially holds a packet to be sent to another processor. No two processors hold packets whose destination is the same processor. Performance of algorithms is evaluated by the worst case completion time. Although the diameter of mesh is 2√<N>, the best known algorithm so far achieved only O(N) time, and it had been a long open problem whether it can be improved. In 1998, our research group developed an algorithm whose time complexity is O(N^<0.75>).In this research, we improved the upper bound. First, we developed an O(√<N>) time algorithm using bit reversal permutation. However, constant coefficient was as big a 1000. To reduce it, we refined the bit reversal permutation and obtained a (2.954+ε)√<N> time algorithm.