dc.contributor.author |
Venugopalan, Sarad |
en |
dc.contributor.author |
Sinnen, Oliver |
en |
dc.date.accessioned |
2016-09-05T20:53:41Z |
en |
dc.date.accessioned |
2017-08-16T02:36:15Z |
en |
dc.date.issued |
2016-05 |
en |
dc.identifier.citation |
Journal of Parallel and Distributed Computing, 2016, 92, pp. 35 - 49 |
en |
dc.identifier.issn |
0743-7315 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/35130 |
en |
dc.description.abstract |
To fully benefit from a multi-processor system, tasks need to be scheduled optimally. Given that the task scheduling problem with communication delays, P|prec,cij|CmaxP|prec,cij|Cmax, is a well known strong NP-hard problem, exhaustive approaches are necessary. The previously proposed A* based algorithm retains its entire state space in memory and often runs out of memory before it finds an optimal solution. This paper investigates and proposes two memory limited optimal scheduling algorithms: Iterative Deepening A* (IDA*) and Depth-First Branch and Bound A* (BBA*). When finding a guaranteed near optimal schedule length is sufficient, the proposed algorithms can be combined, reporting the gap while they run. Problem specific pruning techniques, which are crucial for good performance, are studied for the two proposed algorithms. Extensive experiments are conducted to evaluate and compare the proposed algorithms with previous optimal algorithms. |
en |
dc.description.uri |
http://www.journals.elsevier.com/journal-of-parallel-and-distributed-computing/ |
en |
dc.publisher |
Elsevier |
en |
dc.relation.ispartofseries |
Journal of Parallel and Distributed Computing |
en |
dc.relation.replaces |
http://hdl.handle.net/2292/30226 |
en |
dc.relation.replaces |
2292/30226 |
en |
dc.rights |
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. Details obtained from http://www.sherpa.ac.uk/romeo/issn/0743-7315/ |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.rights.uri |
https://creativecommons.org/licenses/by-nc-nd/4.0/ |
en |
dc.title |
Memory limited algorithms for optimal task scheduling on parallel systems |
en |
dc.type |
Journal Article |
en |
dc.identifier.doi |
10.1016/j.jpdc.2016.03.003 |
en |
pubs.begin-page |
35 |
en |
pubs.volume |
92 |
en |
dc.description.version |
AM - Accepted Manuscript |
en |
dc.rights.holder |
Copyright: Elsevier |
en |
pubs.author-url |
http://www.sciencedirect.com/science/article/pii/S0743731516000241 |
en |
pubs.end-page |
49 |
en |
pubs.publication-status |
Published |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |
pubs.subtype |
Article |
en |
pubs.elements-id |
527321 |
en |
pubs.org-id |
Engineering |
en |
pubs.org-id |
Department of Electrical, Computer and Software Engineering |
en |
pubs.record-created-at-source-date |
2016-09-06 |
en |