Home News About Us Contact Contributors Disclaimer Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Display Documents



ID: 518107.0, MPI für Informatik / Algorithms and Complexity Group
How Helpers Hasten h-Relations
Authors:Sanders, Peter; Solis-Oba, Roberto
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2000
Title of Proceedings:Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00)
Start Page:392
End Page:402
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Saarbrücken, Germany
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
2000
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2010-03-02
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-E294CF768CBC2EE0C12569DD00693B1E-...
ISBN:3-540-41004-X
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.