File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Exploiting duplication to minimize the execution times of parallel programs on message-passing systems

TitleExploiting duplication to minimize the execution times of parallel programs on message-passing systems
Authors
Issue Date1994
Citation
Ieee Symposium On Parallel And Distributed Processing - Proceedings, 1994, p. 426-433 How to Cite?
AbstractCommunication overhead is one of the main factors that can limit the speedup of parallel programs on message-passing parallel architectures. This limiting factor is more predominant in distributed systems such as clusters of homogeneous or heterogeneous workstations. However, excessive communication overhead can be reduced by redundantly executing some of the tasks of a parallel program on which other tasks critically depend. In this paper, we study the problem of duplication-based static scheduling of parallel programs on parallel and distributed systems. Previous duplication-based scheduling algorithms assumed the availability of unlimited number of homogeneous processors. In this paper, we consider more practical scenarios: when the number of processors is limited, and when the system consists of heterogeneous computers. For the first scenario, we propose an algorithm which minimizes the execution of a parallel program by controlling the level of duplication according to the number of processors available. For the second scenario, we design an algorithm which simultaneously exploits duplication and processor heterogeneity to minimize the total execution time of a parallel program. The proposed algorithms are suitable for low as well as high communication-to-computation ratios.
Persistent Identifierhttp://hdl.handle.net/10722/158150
ISSN

 

DC FieldValueLanguage
dc.contributor.authorKwok, YuKwongen_US
dc.contributor.authorAhmad, Ishfaqen_US
dc.date.accessioned2012-08-08T08:58:17Z-
dc.date.available2012-08-08T08:58:17Z-
dc.date.issued1994en_US
dc.identifier.citationIeee Symposium On Parallel And Distributed Processing - Proceedings, 1994, p. 426-433en_US
dc.identifier.issn1063-6374en_US
dc.identifier.urihttp://hdl.handle.net/10722/158150-
dc.description.abstractCommunication overhead is one of the main factors that can limit the speedup of parallel programs on message-passing parallel architectures. This limiting factor is more predominant in distributed systems such as clusters of homogeneous or heterogeneous workstations. However, excessive communication overhead can be reduced by redundantly executing some of the tasks of a parallel program on which other tasks critically depend. In this paper, we study the problem of duplication-based static scheduling of parallel programs on parallel and distributed systems. Previous duplication-based scheduling algorithms assumed the availability of unlimited number of homogeneous processors. In this paper, we consider more practical scenarios: when the number of processors is limited, and when the system consists of heterogeneous computers. For the first scenario, we propose an algorithm which minimizes the execution of a parallel program by controlling the level of duplication according to the number of processors available. For the second scenario, we design an algorithm which simultaneously exploits duplication and processor heterogeneity to minimize the total execution time of a parallel program. The proposed algorithms are suitable for low as well as high communication-to-computation ratios.en_US
dc.languageengen_US
dc.relation.ispartofIEEE Symposium on Parallel and Distributed Processing - Proceedingsen_US
dc.titleExploiting duplication to minimize the execution times of parallel programs on message-passing systemsen_US
dc.typeConference_Paperen_US
dc.identifier.emailKwok, YuKwong:ykwok@eee.hku.hken_US
dc.identifier.authorityKwok, YuKwong=rp00128en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-0028727449en_US
dc.identifier.spage426en_US
dc.identifier.epage433en_US
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridKwok, YuKwong=7101857718en_US
dc.identifier.scopusauthoridAhmad, Ishfaq=7201878459en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats