Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  How Helpers Hasten h-Relations

Sanders, P., & Solis-Oba, R. (2000). How Helpers Hasten h-Relations. In M. Paterson (Ed.), Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00) (pp. 392-402). Berlin, Germany: Springer.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-33BA-9 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-33BC-5
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Sanders, Peter1, Autor           
Solis-Oba, Roberto1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We study the problem of exchanging a set of messages among a group of processors, using the model of simplex communication. Messages may consist of different numbers of packets. Let $\Lmax$ denote the maximum number of packets that a processor must send and receive. If all the packets need to be delivered directly, at least $\frac{3}{2}\Lmax$ communication steps are needed to solve the problem in the worst case. We show that by allowing forwarding, only $\frac{6}{5}\Lmax + \Oh{1}$ time steps are needed to exchange all the messages, and this is optimal. Our work was motivated by the importance of irregular message exchanges in distributed-memory parallel computers, but it can also be viewed as an answer to an open problem on scheduling file transfers posed by Coffmann, Garey, Johnsson, and LaPaugh in 1985.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-022000
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 518107
Anderer: Local-ID: C1256428004B93B8-E294CF768CBC2EE0C12569DD00693B1E-Sanders2000a
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Saarbrücken, Germany
Start-/Enddatum: 2000

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00)
Genre der Quelle: Konferenzband
 Urheber:
Paterson, Mike, Herausgeber
Affiliations:
-
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 392 - 402 Identifikator: ISBN: 3-540-41004-X

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 1879 Artikelnummer: - Start- / Endseite: - Identifikator: -