List-ranking on interconnection networks

AbstractThe 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 k–k 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 k–k routing. Thus, the results are within a factor two from optimal, those for meshes even match the lower bound up to lower-order terms