Scalable scheduling in parallel, distributed, and grid systems

A study of scalable data intensive scheduling involving load distribution on single level tree networks and multilevel tree networks is presented. A general theory of tree systems and its applications in scheduling is also proposed. Means of analyzing the performance of multilevel tree networks by collapsing single level subtrees into equivalent nodes from the bottommost level upwards to the topmost level are studied. Speedup, a performance measure of multilevel tree networks, is obtained for scheduling models using different scheduling policies.; In a specific scheduling model, which is a simplified model of the general theory model, store and forward switching and cut through switching are used for data transmission from the root node in the topmost level to the rest of the nodes in the lower levels. Within a subtree, simultaneous distribution and sequential distribution are employed when a parent node distributes fraction loads to its equivalent children nodes.; In contrast, the features of the general theory model are functional computation time, functional trigger delay, and functional start delay. These features are more general than those of a specific scheduling model.; We derive recursive speedup formulae for specific scheduling models and subsequently obtain a general scheduling speedup formula for the general theory scheduling model. This general speedup formula is also verified by the speedup formulae derived in the specific scheduling model.; Two different computational models are distinguished in this dissertation. One is a linear computational model; the other is a nonlinear computational model. For the nonlinear computational model, we obtain the performance of this model whose data are dependent on each other.; The new study of a general theory of tree systems proved and verified conclusively that general scheduling speedup formulae can describe the speedup performances of a variety of specified scheduling models. Furthermore, the speedup formula of a scalable layered homogeneous tree network using cut through switching can provide a linear speedup without saturation if the speedup is compared to the total computing capability of this tree network.