Development of fast routing algorithms using adaptation and randomization

在本研究中，我们的模型是N个处理器在√<N>×√<N>网格上的分布，其中每个处理器与四个相邻处理器相连。每个处理器都有一个固定的队列大小，也就是说，一个处理器只能容纳固定数量的数据包。在单位步进中，每个处理器可以向四个相邻处理器中的一个发送数据包。我们在上述模型上处理一个排列路由问题。在这个问题中，每个处理器最初持有一个要发送到另一个处理器的数据包。没有两个处理器保存目的地是同一个处理器的数据包。用最坏情况下的完成时间来评价算法的性能。虽然网格直径为2√<N>，但目前已知的算法只实现了O(N)时间，能否改进一直是一个开放的问题。1998年，课题组开发了一种时间复杂度为0 （N^<0.75>）的算法。在本研究中，我们改进了上界。首先，我们开发了一个使用位反转置换的O（√<N>）时间算法。然而，常系数和1000一样大。为了减少它，我们改进了位反转排列，得到了一个(2.954+ε)√<N>的时间算法。

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.