Static allocation of computation to processors in multicomputers
Michael G. Norman · ERA · 1993
In this thesis we address the static mapping problem—that is the problem of allocating computation to processors—in a MIMD, distributed-memory architecture: a multicompUter. We are primarily interested in the way in which the computation and the multicomPUter can be modelled: the features of the miiiticomputer and the computation that are included and left out, and the way in which that impacts upon the predictions made by the models for the performance of computations. We try to put the various published formulations of the mapping problem into the context of the multicomPuter, and to identify correspondences between features of the models underlying the formulations, and features of the multicomputer and the computation. The two types of models which we choose to consider in detail are precedence constrained scheduling with interproceSsor communication delay, and static process based models. We review approaches to hybridising the two types of model and propose such a model of our own. We also consider the impact of message contention in the multicomPUter. We analyse the models underlying formulations of the mapping problem in a number of ways. We look at the way in which performance gains can be to the models. We consider the way in achieved by adding more processors which the complexity of mapping problems depends upon the modelling of interprocessor communication. We compare bounds on performance given for approximation algorithms in different, but related models. We show, for an example computations how the predictions of the various models differ and