File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: FASTEST: A practical low-complexity algorithm for compile-time assignment of parallel programs to multiprocessors

TitleFASTEST: A practical low-complexity algorithm for compile-time assignment of parallel programs to multiprocessors
Authors
KeywordsAutomatic parallelization
Compile-time scheduling
Multiprocessors
Parallel algorithm
Parallel processing
Parallel programming tool
Random neighborhood search
Task graphs
Issue Date1999
PublisherI E E E. The Journal's web site is located at http://www.computer.org/tpds
Citation
Ieee Transactions On Parallel And Distributed Systems, 1999, v. 10 n. 2, p. 147-159 How to Cite?
AbstractIn the area of parallelizing compilers, considerable research has been carried out on data dependency analysis, parallelism extraction, as well as program and data partitioning. However, designing a practical, low complexity scheduling algorithm without sacrificing performance remains a challenging problem. A variety of heuristics have been proposed to generate efficient solutions but they take prohibitively long execution times for moderate size or large problems. In this paper, we propose an algorithm called FASTEST (Fast Assignment and Scheduling of Tasks using an Efficient Search Technique) that has O(e) time complexity, where e is the number of edges in the task graph. The algorithm first generates an initial solution in a short time and then refines it by using a simple but robust random neighborhood search. We have also parallelized the search to further lower the time complexity. We are using the algorithm in a prototype automatic parallelization and scheduling tool which compiles sequential code and generates parallel code optimized with judicious scheduling. The proposed algorithm is evaluated with several application programs and outperforms a number of previous algorithms by generating parallelized code with shorter execution times, while taking dramatically shorter scheduling times. The FASTEST algorithm generates optimal solutions for a majority of the test cases and close-to-optimal solutions for the rest. © 1999 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/42802
ISSN
2015 Impact Factor: 2.661
2015 SCImago Journal Rankings: 1.590
References

 

DC FieldValueLanguage
dc.contributor.authorKwok, YKen_HK
dc.contributor.authorAhmad, Ien_HK
dc.date.accessioned2007-03-23T04:32:29Z-
dc.date.available2007-03-23T04:32:29Z-
dc.date.issued1999en_HK
dc.identifier.citationIeee Transactions On Parallel And Distributed Systems, 1999, v. 10 n. 2, p. 147-159en_HK
dc.identifier.issn1045-9219en_HK
dc.identifier.urihttp://hdl.handle.net/10722/42802-
dc.description.abstractIn the area of parallelizing compilers, considerable research has been carried out on data dependency analysis, parallelism extraction, as well as program and data partitioning. However, designing a practical, low complexity scheduling algorithm without sacrificing performance remains a challenging problem. A variety of heuristics have been proposed to generate efficient solutions but they take prohibitively long execution times for moderate size or large problems. In this paper, we propose an algorithm called FASTEST (Fast Assignment and Scheduling of Tasks using an Efficient Search Technique) that has O(e) time complexity, where e is the number of edges in the task graph. The algorithm first generates an initial solution in a short time and then refines it by using a simple but robust random neighborhood search. We have also parallelized the search to further lower the time complexity. We are using the algorithm in a prototype automatic parallelization and scheduling tool which compiles sequential code and generates parallel code optimized with judicious scheduling. The proposed algorithm is evaluated with several application programs and outperforms a number of previous algorithms by generating parallelized code with shorter execution times, while taking dramatically shorter scheduling times. The FASTEST algorithm generates optimal solutions for a majority of the test cases and close-to-optimal solutions for the rest. © 1999 IEEE.en_HK
dc.format.extent284420 bytes-
dc.format.extent28160 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/msword-
dc.languageengen_HK
dc.publisherI E E E. The Journal's web site is located at http://www.computer.org/tpdsen_HK
dc.relation.ispartofIEEE Transactions on Parallel and Distributed Systemsen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rights©1999 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.subjectAutomatic parallelizationen_HK
dc.subjectCompile-time schedulingen_HK
dc.subjectMultiprocessorsen_HK
dc.subjectParallel algorithmen_HK
dc.subjectParallel processingen_HK
dc.subjectParallel programming toolen_HK
dc.subjectRandom neighborhood searchen_HK
dc.subjectTask graphsen_HK
dc.titleFASTEST: A practical low-complexity algorithm for compile-time assignment of parallel programs to multiprocessorsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1045-9219&volume=10&issue=2&spage=147&epage=159&date=1999&atitle=FASTEST:+A+Practical+Low-Complexity+Algorithm+for+Compile-Time+Assignment+of+Parallel+Programs+to+Multiprocessorsen_HK
dc.identifier.emailKwok, YK:ykwok@eee.hku.hken_HK
dc.identifier.authorityKwok, YK=rp00128en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1109/71.752781en_HK
dc.identifier.scopuseid_2-s2.0-0033076467en_HK
dc.identifier.hkuros44689-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0033076467&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume10en_HK
dc.identifier.issue2en_HK
dc.identifier.spage147en_HK
dc.identifier.epage159en_HK
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridKwok, YK=7101857718en_HK
dc.identifier.scopusauthoridAhmad, I=7201878459en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats