File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Parallel approach for multiprocessor scheduling

TitleParallel approach for multiprocessor scheduling
Authors
Issue Date1995
Citation
Ieee Symposium On Parallel And Distributed Processing - Proceedings, 1995, p. 289-293 How to Cite?
AbstractThe objective of this research is to propose a low-complexity static scheduling and allocation algorithm for message-passing architectures by considering factors such as communication delays, link contention, message routing and network topology. As opposed to the conventional list-scheduling approach, our technique works by first serializing the task graph and 'injecting' all the tasks to one processor. The parallel tasks are then 'bubbled up' to other processors and are inserted at appropriate time slots. The edges among the tasks are also scheduled by treating communication links between the processors as resources. The proposed approach takes into account the link contention and underlying communication routing strategy, and can self-adjust on regular as well as arbitrary network topologies. To reduce the complexity, our scheduling algorithm is itself parallelized. To our knowledge, this is the first attempt in designing a parallel algorithm for scheduling. The proposed approach implemented on an iPSC/860 hypercube, while yielding a high speedup in its execution, performs considerably better under a wide range of parameters including the task graph size, communication-to-computation ratio, and the target system topology. Comparisons are made with two other approaches.
Persistent Identifierhttp://hdl.handle.net/10722/158158
ISSN

 

DC FieldValueLanguage
dc.contributor.authorAhmad, Ishfaqen_US
dc.contributor.authorKwok, YuKwongen_US
dc.date.accessioned2012-08-08T08:58:19Z-
dc.date.available2012-08-08T08:58:19Z-
dc.date.issued1995en_US
dc.identifier.citationIeee Symposium On Parallel And Distributed Processing - Proceedings, 1995, p. 289-293en_US
dc.identifier.issn1063-6374en_US
dc.identifier.urihttp://hdl.handle.net/10722/158158-
dc.description.abstractThe objective of this research is to propose a low-complexity static scheduling and allocation algorithm for message-passing architectures by considering factors such as communication delays, link contention, message routing and network topology. As opposed to the conventional list-scheduling approach, our technique works by first serializing the task graph and 'injecting' all the tasks to one processor. The parallel tasks are then 'bubbled up' to other processors and are inserted at appropriate time slots. The edges among the tasks are also scheduled by treating communication links between the processors as resources. The proposed approach takes into account the link contention and underlying communication routing strategy, and can self-adjust on regular as well as arbitrary network topologies. To reduce the complexity, our scheduling algorithm is itself parallelized. To our knowledge, this is the first attempt in designing a parallel algorithm for scheduling. The proposed approach implemented on an iPSC/860 hypercube, while yielding a high speedup in its execution, performs considerably better under a wide range of parameters including the task graph size, communication-to-computation ratio, and the target system topology. Comparisons are made with two other approaches.en_US
dc.languageengen_US
dc.relation.ispartofIEEE Symposium on Parallel and Distributed Processing - Proceedingsen_US
dc.titleParallel approach for multiprocessor schedulingen_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-0029228748en_US
dc.identifier.spage289en_US
dc.identifier.epage293en_US
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridAhmad, Ishfaq=7201878459en_US
dc.identifier.scopusauthoridKwok, YuKwong=7101857718en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats