File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

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

TitleA parallel algorithm for compile-time scheduling of parallel programs on multiprocessors
Authors
KeywordsCompile-Time Scheduling
Task Graphs
Multiprocessors
Parallel Processing
Parallel Programming Tool
Issue Date1997
PublisherIEEE.
Citation
Proceedings of the 1997 International Conference on Parallel Architectures and Compilation Techniques, San Francisco, California, November 10-14, 1997, p. 90-101 How to Cite?
AbstractProposes a parallel randomized algorithm, called PFAST (Parallel Fast Assignment using Search Technique), 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 (Computer-Aided SCHeduling), 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 an 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/54034
ISSN

 

DC FieldValueLanguage
dc.contributor.authorKwok, YKen_HK
dc.contributor.authorAhmad, Ien_HK
dc.date.accessioned2009-04-03T07:35:03Z-
dc.date.available2009-04-03T07:35:03Z-
dc.date.issued1997en_HK
dc.identifier.citationProceedings of the 1997 International Conference on Parallel Architectures and Compilation Techniques, San Francisco, California, November 10-14, 1997, p. 90-101en_HK
dc.identifier.issn1089-795Xen_HK
dc.identifier.urihttp://hdl.handle.net/10722/54034-
dc.description.abstractProposes a parallel randomized algorithm, called PFAST (Parallel Fast Assignment using Search Technique), 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 (Computer-Aided SCHeduling), 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 an 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_HK
dc.languageengen_HK
dc.publisherIEEE.en_HK
dc.rights©1997 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.en_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectCompile-Time Schedulingen_HK
dc.subjectTask Graphsen_HK
dc.subjectMultiprocessorsen_HK
dc.subjectParallel Processingen_HK
dc.subjectParallel Programming Toolen_HK
dc.titleA parallel algorithm for compile-time scheduling of parallel programs on multiprocessorsen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1089-795X&volume=&spage=90&epage=101&date=1997&atitle=A+parallel+algorithm+for+compile-time+scheduling+of+parallel+programs+on+multiprocessorsen_HK
dc.identifier.emailKwok, YK: ykwok@eee.hku.hken_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1109/PACT.1997.644006en_HK
dc.identifier.hkuros36996-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats