Development of fast routing algorithms using adaptation and randomization

我们的模型是N个处理器在一个N × N网格上的分布<N><N>，其中每个处理器与四个相邻的处理器相连。每个处理器都有一个恒定的队列大小，也就是说，一个处理器只能容纳恒定数量的数据包。在单位步长内，每个处理器可以向四个邻居中的一个发送一个分组。在这个问题中，每个处理器最初持有一个要发送到另一个处理器的数据包。没有两个处理器持有目的地为同一处理器的数据包。算法的性能通过最坏情况下的完成时间来评估。虽然网格直径为2 μ m<N>，但迄今为止最著名的算法只能实现O（N）时间，并且是否可以改进一直是一个悬而未决的问题。在1998年，我们的研究小组开发了一个时间复杂度为O（N^）的算法<0.75>。首先，我们开发了一个O（N<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.