Accession Number : AD0628220

Title :   THE AUTOMATIC ASSIGNMENT AND SEQUENCING OF COMPUTATIONS ON PARALLEL PROCESSOR SYSTEMS,

Corporate Author : CALIFORNIA UNIV LOS ANGELES DEPT OF ENGINEERING

Personal Author(s) : Martin,David F.

Report Date : JAN 1966

Pagination or Media Count : 425

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.

Descriptors :   (*OPERATIONS RESEARCH, DATA PROCESSING), (*SCHEDULING, MATHEMATICAL PROGRAMMING), (*MATHEMATICAL PROGRAMMING, SCHEDULING), COMPUTER PROGRAMMING

Subject Categories : Operations Research
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE