On process assignment in parallel computing (Q1115176)

An asynchronous MIMD parallel computer, in which a number of identical processors run independently and communicate by sending messages periodically via a communication network, is a frequently assumed computational model. The authors are interested in parallel programs for running on such machines. The program exhibits a greater or lesser degree of parallelism depending on the sparsity of the partial order on the set of actions generated during a typical execution of the program. It is the purpose of this paper to illustrate that list scheduling, generated to cover the restriction that all the actions comprising a single process should be assigned to the same processor, can lead to a schedule whose length is approximately m times greater than the length of the ordinary list schedule for an m processor system.