List-ranking on interconnection networks
The list-ranking problem is considered for parallel computers which communicate through an interconnection network. Each PU holds k nodes of a set of linked lists. A novel randomized algorithm gives a considerable improvement over earlier ones: for a large class of networks and sufficiently large k, it takes only twice the number of steps required by a kk routing. For hypercubes the condition is k=?(log2N). Even better results are achieved for d-dimensional meshes: we show that the ranking time exceeds the routing time only by lower-order terms for all k=?(d2). We also show that list-ranking requires at least the time required for kk routing. Thus, the results are within a factor two from optimal, those for meshes even match the lower bound up to lower-order terms.
list-ranking interconnection networks randomization hypercubes meshes parallel algorithms