File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/71.752781
- Scopus: eid_2-s2.0-0033076467
- WOS: WOS:000079130800005
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: FASTEST: A practical low-complexity algorithm for compile-time assignment of parallel programs to multiprocessors
Title | FASTEST: A practical low-complexity algorithm for compile-time assignment of parallel programs to multiprocessors |
---|---|
Authors | |
Keywords | Automatic parallelization Compile-time scheduling Multiprocessors Parallel algorithm Parallel processing Parallel programming tool Random neighborhood search Task graphs |
Issue Date | 1999 |
Publisher | I 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? |
Abstract | In 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 Identifier | http://hdl.handle.net/10722/42802 |
ISSN | 2023 Impact Factor: 5.6 2023 SCImago Journal Rankings: 2.340 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kwok, YK | en_HK |
dc.contributor.author | Ahmad, I | en_HK |
dc.date.accessioned | 2007-03-23T04:32:29Z | - |
dc.date.available | 2007-03-23T04:32:29Z | - |
dc.date.issued | 1999 | en_HK |
dc.identifier.citation | Ieee Transactions On Parallel And Distributed Systems, 1999, v. 10 n. 2, p. 147-159 | en_HK |
dc.identifier.issn | 1045-9219 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/42802 | - |
dc.description.abstract | In 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.extent | 284420 bytes | - |
dc.format.extent | 28160 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.format.mimetype | application/msword | - |
dc.language | eng | en_HK |
dc.publisher | I E E E. The Journal's web site is located at http://www.computer.org/tpds | en_HK |
dc.relation.ispartof | IEEE Transactions on Parallel and Distributed Systems | en_HK |
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. | - |
dc.subject | Automatic parallelization | en_HK |
dc.subject | Compile-time scheduling | en_HK |
dc.subject | Multiprocessors | en_HK |
dc.subject | Parallel algorithm | en_HK |
dc.subject | Parallel processing | en_HK |
dc.subject | Parallel programming tool | en_HK |
dc.subject | Random neighborhood search | en_HK |
dc.subject | Task graphs | en_HK |
dc.title | FASTEST: A practical low-complexity algorithm for compile-time assignment of parallel programs to multiprocessors | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://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+Multiprocessors | en_HK |
dc.identifier.email | Kwok, YK:ykwok@eee.hku.hk | en_HK |
dc.identifier.authority | Kwok, YK=rp00128 | en_HK |
dc.description.nature | published_or_final_version | en_HK |
dc.identifier.doi | 10.1109/71.752781 | en_HK |
dc.identifier.scopus | eid_2-s2.0-0033076467 | en_HK |
dc.identifier.hkuros | 44689 | - |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-0033076467&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 10 | en_HK |
dc.identifier.issue | 2 | en_HK |
dc.identifier.spage | 147 | en_HK |
dc.identifier.epage | 159 | en_HK |
dc.identifier.isi | WOS:000079130800005 | - |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | Kwok, YK=7101857718 | en_HK |
dc.identifier.scopusauthorid | Ahmad, I=7201878459 | en_HK |
dc.identifier.issnl | 1045-9219 | - |