A Study of Schedules as Models of Synchronous Parallel Computation
Richard A. DeMillo, K. Vairavan, E. Sycara-Cyranski · Journal of the ACM · 1977
A formal framework for studying the scheduling problem for task systems with multiple outcome operations and independent control structure is presented Models of sequential programs and their parallel representa tlons (schedules) are developed.Schedules are seen to be restrictions of the parallel program schema of Karp and Mdler The restrictions are that the operations are synchronous and of fixed duration Interpretations of schedules are provided, and it as shown that the schedules are determinate and preserve the results of sequential computations in various senses Various equivalence properties of schedules and their relationships are studied.A number of decldablhty questions are answered by using the notion of "parallel derivatives" introduced by Mlllen Optamallty of schedules IS defined m terms of minimal tame executions, and parallel derivatives are used to generate optimal schedules.Finally, the finite representation of optimal schedules as considered