Change search
ReferencesLink to record
Permanent link

Direct link
List-ranking on interconnection networks
Umeå University, Faculty of Science and Technology, Departement of Computing Science.
2003 (English)In: Information and Computation, Vol. 181, no 2, 75-87 p.Article in journal (Refereed) Published
Abstract [en]

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.
URN: urn:nbn:se:umu:diva-21976ISBN: 0890-5401OAI: diva2:212238
Available from: 2009-04-21 Created: 2009-04-21 Last updated: 2009-04-21

Open Access in DiVA

No full text

Other links

<Go to ISI>://000181566300001
By organisation
Departement of Computing Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 22 hits
ReferencesLink to record
Permanent link

Direct link