Change search
ReferencesLink to record
Permanent link

Direct link
One-by-one cleaning for practical parallel list ranking
Umeå University, Faculty of Science and Technology, Departement of Computing Science.
2002 (English)In: Algorithmica, Vol. 32, no 3, 345-363 p.Article in journal (Refereed) Published
Abstract [en]

It is hard to achieve good speed-ups for parallel list ranking on distributed-memory machines because the problem requires a substantial number of communication rounds, each incurring some start-up delay. For input sizes N that are very large in comparison with the number of processors P these start-up costs can be amortized to a certain extent. For modest NIP values, so far the best approach was the basic pointer-jumping approach. In this paper a novel algorithm, one-by-one cleaning, is presented. It has the unique property that the routing consists of O(P) rounds in which each processing unit (PU) sends a packet to only one other PU. Pointer jumping requires a logarithmic number of rounds in which each PU sends a packet to all other PUs. Because the constants are small, and the internal work performed is less than that of pointer jumping, one-by-one cleaning is about twice as fast, which is demonstrated by comparing the performance of implementations of both algorithms on the Intel Paragon.

Place, publisher, year, edition, pages
2002. Vol. 32, no 3, 345-363 p.
URN: urn:nbn:se:umu:diva-21975ISBN: 0178-4617OAI: diva2:212237
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>://000173051900001
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: 11 hits
ReferencesLink to record
Permanent link

Direct link