Advanced Teleprocessing Systems. Semi-annual Technical Report October 1, 1983 - March 31, 1984.

摘要

THe idea of multiprocessing has been with us for many years. We would like to know, however, how much gain (i.e., speed-up) is really achieved when multi-processors are used. In this dessertation, we model a computer job as a Directed Acyclic Graph (DAG), each node in the DAG representing a separate task that can be processed by any processor. Four parameters are used to characterize the concurrency problem which results in 16 cases. The four parameters are: (1.) How the jobs arrive: either a fixed number of jobs at time zero or jobs arriving from a Poisson source; (2.) the DAG: either the same for each job or each job randomly selecting its DAG; (3.) service time of each task: constant or exponentially distributed; (4.) the number of processors: either a fixed number or an infinite number (infinite number of processors meaning that whenever a task requires a processor, one will be available). For all cases studied, we define a common concurrency measure which gives a comparison of how much parallelism can be achieved. The concurrency measure is obtained exactly for several cases by first converting the DAG into a Markov chain where each state represents a possible set of tasks that can be executed in parallel. From this Markov chain, and by utilizing a special feature in the chain, we are able to find the equilibrium probabilities of each state and the average time required to process a single job.