A formal approach to realtime parallel processing
Shahram Barkhordarian · 1986
This dissertation focuses on the design of realtime parallel processors and proposes a formalism based on scheduling theory. Formal methods in designing and programming special purpose computers are presented for minimizing the time delay between the input and the response. The resource constrained scheduling model is used to statically produce the best method for executing a given program on a given parallel computer organization so that the total execution time of the program is minimum. In practice, many programs are too large to execute at theoretical minimum execution times, given limited resources. For such large programs, it is desirable to produce a possible implementation for which total execution time is lower than some prespecified value T(,max). A set of heuristic solutions for producing satisfactory results for these large programs is provided. The computational complexity of the problems involved in minimizing the execution time of a given program on a given computer organization is analyzed. Some of these problems are shown to belong to the class called NP-complete.