List-ranking on interconnection networks
2003 (English)In: Information and Computation, Vol. 181, no 2, 75-87 p.Article in journal (Refereed) Published
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 no-vel 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 = omega(log(2) N). 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 = omega(d(2)). 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. (C) 2002 Elsevier Science (USA). All rights reserved.
Place, publisher, year, edition, pages
2003. Vol. 181, no 2, 75-87 p.
IdentifiersURN: urn:nbn:se:umu:diva-21976ISBN: 0890-5401OAI: oai:DiVA.org:umu-21976DiVA: diva2:212238