File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: On parallelizing the multiprocessor scheduling problem

TitleOn parallelizing the multiprocessor scheduling problem
Authors
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. 4, p. 414-432 How to Cite?
AbstractExisting heuristics for scheduling a node and edge weighted directed task graph to multiple processors can produce satisfactory solutions but incur high time complexities, which tend to exacerbate in more realistic environments with relaxed assumptions. Consequently, these heuristics do not scale well and cannot handle problems of moderate sizes. A natural approach to reducing complexity, while aiming for a similar or potentially better solution, is to parallelize the scheduling algorithm. This can be done by partitioning the task graphs and concurrently generating partial schedules for the partitioned parts, which are then concatenated to obtain the final schedule. The problem, however, is nontrivial as there exists dependencies among the nodes of a task graph which must be preserved for generating a valid schedule. Moreover, the time clock for scheduling is global for all the processors (that are executing the parallel scheduling algorithm), making the inherent parallelism invisible. In this paper, we introduce a parallel algorithm that is guided by a systematic partitioning of the task graph to perform scheduling using multiple processors. The algorithm schedules both the tasks and messages, and is suitable for graphs with arbitrary computation and communication costs, and is applicable to systems with arbitrary network topologies using homogeneous or heterogeneous processors. We have implemented the algorithm on the Intel Paragon and compared it with three closely related algorithms. The experimental results indicate that our algorithm yields higher quality solutions while using an order of magnitude smaller scheduling times. The algorithm also exhibits an interesting trade-off between the solution quality and speedup while scaling well with the problem size.
Persistent Identifierhttp://hdl.handle.net/10722/42801
ISSN
2015 Impact Factor: 2.661
2015 SCImago Journal Rankings: 1.590
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorAhmad, Ien_HK
dc.contributor.authorKwok, YKen_HK
dc.date.accessioned2007-03-23T04:32:28Z-
dc.date.available2007-03-23T04:32:28Z-
dc.date.issued1999en_HK
dc.identifier.citationIeee Transactions On Parallel And Distributed Systems, 1999, v. 10 n. 4, p. 414-432en_HK
dc.identifier.issn1045-9219en_HK
dc.identifier.urihttp://hdl.handle.net/10722/42801-
dc.description.abstractExisting heuristics for scheduling a node and edge weighted directed task graph to multiple processors can produce satisfactory solutions but incur high time complexities, which tend to exacerbate in more realistic environments with relaxed assumptions. Consequently, these heuristics do not scale well and cannot handle problems of moderate sizes. A natural approach to reducing complexity, while aiming for a similar or potentially better solution, is to parallelize the scheduling algorithm. This can be done by partitioning the task graphs and concurrently generating partial schedules for the partitioned parts, which are then concatenated to obtain the final schedule. The problem, however, is nontrivial as there exists dependencies among the nodes of a task graph which must be preserved for generating a valid schedule. Moreover, the time clock for scheduling is global for all the processors (that are executing the parallel scheduling algorithm), making the inherent parallelism invisible. In this paper, we introduce a parallel algorithm that is guided by a systematic partitioning of the task graph to perform scheduling using multiple processors. The algorithm schedules both the tasks and messages, and is suitable for graphs with arbitrary computation and communication costs, and is applicable to systems with arbitrary network topologies using homogeneous or heterogeneous processors. We have implemented the algorithm on the Intel Paragon and compared it with three closely related algorithms. The experimental results indicate that our algorithm yields higher quality solutions while using an order of magnitude smaller scheduling times. The algorithm also exhibits an interesting trade-off between the solution quality and speedup while scaling well with the problem size.en_HK
dc.format.extent759099 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.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.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.titleOn parallelizing the multiprocessor scheduling problemen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1045-9219&volume=10&issue=4&spage=414&epage=431&date=1999&atitle=On+parallelizing+the+multiprocessor+scheduling+problemen_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.762819en_HK
dc.identifier.scopuseid_2-s2.0-0032665048en_HK
dc.identifier.hkuros44668-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0032665048&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume10en_HK
dc.identifier.issue4en_HK
dc.identifier.spage414en_HK
dc.identifier.epage432en_HK
dc.identifier.isiWOS:000079988700006-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridAhmad, I=7201878459en_HK
dc.identifier.scopusauthoridKwok, YK=7101857718en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats