umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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.
Identifiers
URN: urn:nbn:se:umu:diva-21975ISBN: 0178-4617 OAI: oai:DiVA.org:umu-21975DiVA: 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 14 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf