Extensions and Generalizations

In the above models we assumed that the order of activating processors is known. Determining the optimal order (i.e. giving the shortest total processing time) is not obvious. In the case of multiple busses the problem is NP-hard in the strong sense [BD97]. A solution based on mixed integer linear programming was proposed in [D97]. When communication links are identical the optimal activation order is the order of decreasing PE speeds [BD97]. When $\forall_{2\leq i\leq m}S_i=0$ then the optimal order coincides with decreasing speed of communication links [BD97,BGM94], but the speeds of PEs are irrelevant. Closed-form solutions for finding distribution of the load in bus and tree networks were proposed in [BHR94]. Star and trees of PEs which can communicate over all their ports were considered in [BD97]. [SR94] studies the problem of scheduling multiple divisible applications according to FIFO scheme. The problem of scheduling a divisible task on a bus system in the presence of background activities which affect communication and processing rates is investigated in [SR95]. A new data distribution pattern based on pipelining (i.e. rather a greater number of small chunks is sent to each processor than one big) is proposed in [BGM95a]. In [D97] the idea of divisible tasks was applied in the context of distributed batch systems, and on-line scattering heuristics.