THE AUTOMATIC ASSIGNMENT AND SEQUENCING OF COMPUTATIONS ON PARALLEL PROCESSOR SYSTEMS,
Abstract
The problem of optimal a priori assignment and sequencing of computations on parallel processor systems is investigated. The problem is formulated as a mathematical program in which it is desired to minimize a defined expected cost of computation subject to (1) maintaining partial orderings between computations; (2) a feasible computation-processor correspondence; (3) system inventory constraints. The method of solution is one of successive approximation, consisting of a systematic perturbation of an initial feasible assignment and sequence, accepting or rejecting trial solutions to achieve monotonic cost reduction. Since only a limited portion of the solution space is explored, the solution is generally suboptimal. The partially-ordered set of computations is represented by a cyclic directed graph, the characterization of which requires a priori estimates of arc traversal (branching) probabilities, the expected number of times each cycle will be traversed, and the mean execution times of each computation. Each processor is characterized by an operation list and a mean execution time vector. Analytical contributions in this study include computationally efficient algorithms for vertex computational probabilities and approximate mean path length on acyclic directed graphs, and the formal transformation of a restricted class of cyclic directed graphs into temporally-equivalent acyclic graphs.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1966
- Accession Number
- AD0628220
Entities
People
- David F. Martin
Organizations
- University of California, Los Angeles