Optimal Load Allocation for Parallel and Distributed Processing
| dc.contributor.author | Haddad, Emile K. | en |
| dc.contributor.department | Computer Science | en |
| dc.date.accessioned | 2013-06-19T14:36:12Z | en |
| dc.date.available | 2013-06-19T14:36:12Z | en |
| dc.date.issued | 1989-04-01 | en |
| dc.description.abstract | The problem of minimizing the execution completion time of a given total load, to be partitioned into interacting tasks and allocated to run on a generalized model of a heterogeneous centralized or distributed multiprocessing system, is examined. The problem is formulated as a nonlinear, nonconvex nonseparable, minimax resource- allocation, continuous, mathematical programming problem. It is assumed that the quantitative functional dependence of the individual processor execution time on the partitioned load allocation is known and specified in analytical or graphical formats of a fairly general nature with no a priori restrictions of differentiability, monotonicity, convexity, and unimodality commonly imposed in previous investigations of the problem. A Theorem stating the necessary and sufficient condition for minimum concurrent processing completion time is derived. The new result represents an analytical breakthrough applicable to a wide class of hitherto analytically unsolved optimization problems in various application disciplines. The derivation starts from a precise representation of the parallel execution time and proceeds through an exact analysis that does not resort to the simplifying assumptions or analytical approximations found in analogous previous investigations. The load partitioning is considered to vary over a continuum, thus allowing the achievement of ideal optimization through one-step repartitioning of the given load. The optimization procedure determines the set of all global minimum points of the completion time function as well as all its local minima, thus allowing further lexicographic optimization and suboptimal trade-offs. The conditions of the Theorem admit a straightforward graphical interpretation which facilitates its implementation and readily extends its applicability to empirically or simulationally determined models of the system. | en |
| dc.format.mimetype | application/pdf | en |
| dc.identifier | http://eprints.cs.vt.edu/archive/00000149/ | en |
| dc.identifier.sourceurl | http://eprints.cs.vt.edu/archive/00000149/01/TR-89-12.pdf | en |
| dc.identifier.trnumber | TR-89-12 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/19513 | en |
| dc.language.iso | en | en |
| dc.publisher | Department of Computer Science, Virginia Polytechnic Institute & State University | en |
| dc.relation.ispartof | Historical Collection(Till Dec 2001) | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.title | Optimal Load Allocation for Parallel and Distributed Processing | en |
| dc.type | Technical report | en |
| dc.type.dcmitype | Text | en |
Files
Original bundle
1 - 1 of 1