dc.contributor.author |
Venugopalan, S |
en |
dc.contributor.author |
Sinnen, Oliver |
en |
dc.contributor.editor |
Xiang, Y |
en |
dc.contributor.editor |
Stojmenovic, I |
en |
dc.contributor.editor |
Apduhan, B |
en |
dc.contributor.editor |
Wang, G |
en |
dc.contributor.editor |
Nakano, K |
en |
dc.contributor.editor |
Zomaya, A |
en |
dc.coverage.spatial |
Fukuoka, Japan |
en |
dc.date.accessioned |
2017-11-13T02:02:01Z |
en |
dc.date.issued |
2012 |
en |
dc.identifier.citation |
Editors: Xiang Y, Stojmenovic I, Apduhan B, Wang G, Nakano K, Zomaya A. Algorithms and Architectures for Parallel Processing: 12th International Conference, ICA3PP 2012, Fukuoka, Japan, September 4-7, 2012, Proceedings, Part I. Springer Verlag, Berlin, Germany. LNCS 7439: 129-138. 2012 |
en |
dc.identifier.isbn |
9783642330773 |
en |
dc.identifier.issn |
0302-9743 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/36398 |
en |
dc.description.abstract |
Task parallelism does not automatically scale with the use of parallel processors. Optimised scheduling of tasks is necessary to maximise the utilisation of each available processor. It is common to use heuristics to find solutions for task scheduling problem instances. However, there is no guarantee that the heuristic solution is close to the optimal solution. The outcome of this work is to provide optimal solutions for small and medium sized instances of the task scheduling problem. Two optimal scheduling formulations using Integer Linear Programming (ILP) are proposed for the Multiprocessor Scheduling Problem with Communication Delays: ILP-RevisedBoolean Logic and ILP-Transitivity Clause. ILP-RevisedBooleanLogic is designed to work efficiently when the number of processors available to be scheduled on is small. ILP-TransitivityClause is efficient when a larger number of processors are available to be scheduled on. Each formulation uses a different linearisation of the Integer Bilinear Programming formulation and is tested on CPLEX using known benchmark graphs for task scheduling. |
en |
dc.publisher |
Springer Verlag |
en |
dc.relation.ispartof |
12th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP 2012) |
en |
dc.relation.ispartofseries |
Algorithms and Architectures for Parallel Processing: 12th International Conference, ICA3PP 2012, Fukuoka, Japan, September 4-7, 2012, Proceedings, Part I |
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/0302-9743/ |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.title |
Optimal linear programming solutions for multiprocessor scheduling with communication delays |
en |
dc.type |
Conference Item |
en |
dc.identifier.doi |
10.1007/978-3-642-33078-0_10 |
en |
pubs.issue |
Part 1 |
en |
pubs.begin-page |
129 |
en |
pubs.volume |
LNCS 7439 |
en |
dc.description.version |
AM - Accepted Manuscript |
en |
dc.rights.holder |
Copyright: Springer Verlag |
en |
pubs.end-page |
138 |
en |
pubs.finish-date |
2012-09-07 |
en |
pubs.place-of-publication |
Berlin, Germany |
en |
pubs.publication-status |
Published |
en |
pubs.start-date |
2012-09-04 |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |
pubs.subtype |
Proceedings |
en |
pubs.elements-id |
361762 |
en |
pubs.org-id |
Engineering |
en |
pubs.org-id |
Department of Electrical, Computer and Software Engineering |
en |
dc.identifier.eissn |
1611-3349 |
en |
pubs.record-created-at-source-date |
2017-11-13 |
en |