File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Parallel algorithm for compile-time scheduling of parallel programs on multiprocessors

TitleParallel algorithm for compile-time scheduling of parallel programs on multiprocessors
Authors
Issue Date1997
Citation
Parallel Architectures And Compilation Techniques - Conference Proceedings, Pact, 1997, p. 90-101 How to Cite?
AbstractIn this paper, we propose a parallel randomized algorithm, called Parallel Fast Assignment using Search Technique (PFAST), for scheduling parallel programs represented by directed acyclic graphs (DAGs) during compile-time. The PFAST algorithm has O(e) time complexity where e is the number of edges in the DAG. This linear-time algorithm works by first generating an initial solution and then refining it using a parallel random search. Using a prototype computer-aided parallelization and scheduling tool called CASCH, the algorithm is found to outperform numerous previous algorithms while taking dramatically smaller execution times. The distinctive feature of this research is that, instead of simulations, our proposed algorithm is evaluated and compared with other algorithms using the CASCH tool with real applications running on the Intel Paragon. The PFAST algorithm is also evaluated with randomly generated DAGs for which optimal schedules are known. The algorithm generated optimal solutions for a majority of the test cases and close-to-optimal solutions for the others. The proposed algorithm is the fastest scheduling algorithm known to us and is an attractive choice for scheduling under running time constraints.
Persistent Identifierhttp://hdl.handle.net/10722/158221
ISSN

 

DC FieldValueLanguage
dc.contributor.authorKwok, YuKwongen_US
dc.contributor.authorAhmad, Ishfaqen_US
dc.date.accessioned2012-08-08T08:58:37Z-
dc.date.available2012-08-08T08:58:37Z-
dc.date.issued1997en_US
dc.identifier.citationParallel Architectures And Compilation Techniques - Conference Proceedings, Pact, 1997, p. 90-101en_US
dc.identifier.issn1089-795Xen_US
dc.identifier.urihttp://hdl.handle.net/10722/158221-
dc.description.abstractIn this paper, we propose a parallel randomized algorithm, called Parallel Fast Assignment using Search Technique (PFAST), for scheduling parallel programs represented by directed acyclic graphs (DAGs) during compile-time. The PFAST algorithm has O(e) time complexity where e is the number of edges in the DAG. This linear-time algorithm works by first generating an initial solution and then refining it using a parallel random search. Using a prototype computer-aided parallelization and scheduling tool called CASCH, the algorithm is found to outperform numerous previous algorithms while taking dramatically smaller execution times. The distinctive feature of this research is that, instead of simulations, our proposed algorithm is evaluated and compared with other algorithms using the CASCH tool with real applications running on the Intel Paragon. The PFAST algorithm is also evaluated with randomly generated DAGs for which optimal schedules are known. The algorithm generated optimal solutions for a majority of the test cases and close-to-optimal solutions for the others. The proposed algorithm is the fastest scheduling algorithm known to us and is an attractive choice for scheduling under running time constraints.en_US
dc.languageengen_US
dc.relation.ispartofParallel Architectures and Compilation Techniques - Conference Proceedings, PACTen_US
dc.titleParallel algorithm for compile-time scheduling of parallel programs on multiprocessorsen_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-0031334862en_US
dc.identifier.spage90en_US
dc.identifier.epage101en_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