تجزیه و تحلیل حساسیت برنامه ریزی درخت در دو ماشین با تاخیر ارتباطی

This paper presents a sensitivity analysis for the problem of scheduling trees with communication delays on two identical processors, to minimize the makespan. Tasks are supposed to have unit execution time (uet), and the values associated to communication delays are supposed unknown before the execution. The paper compares the optimal makespans with and without communication delays. The results are used to obtain sensitivity bounds for algorithms providing optimal schedules for graphs with unit execution and communication times (uect). The notion of processor-ordered schedules, for two-processor systems, is introduced. It describes schedules in which all communications are oriented from one processor to the other. It is shown that these schedules are dominant for unit delays, for zero delays, but not for delays of less than or equal to one. We establish that algorithms building optimal processor-ordered schedules for uect graphs admit an absolute sensitivity bound equal to the difference between the maximum and the minimum actual communication delays: . This bound is tight.

Last years have seen a growing number of teams involved in the conception, the deployment and the use of infrastructures and applications distributed over a wide geographical area [26] and [25]. Peer-to-peer computing [24] and [27] as well as programs running on grids [28] are some examples of such applications. They are made of many tasks processed on computing devices located on various, possibly very distant, places. The underlying interconnection network linking together all computing elements is partially common with the internet. As a consequence, codes running on such environments may be subject to unexpected slowdowns occurring somewhere on the network. Then, it is not surprising that most peer-to-peer applications are merely based on the common master/slaves algorithmic scheme, while resources managers of grids give greater importance to high-throughput rather than to application performances. In order to avoid poor performances, the tasks of the application have to be distributed among the computing elements in order to obtain a good trade-off between load balanding and minimization of the communication overhead. Within previously described environments, both execution times of tasks and communication delays may vary. In addition, the application itself may be subject to structural variations depending on the input data, then, it is unlikely that a pure static scheduling strategy could lead to good performances. However, in our work a careful analysis of the schedule structure shows the importance of the distribution of tasks for minimizing the impact of communication variations. In this paper, we focus our study on the degradation of schedules when communication durations estimated a priori differ from actual ones. The application model is a tree-structured task graph with unit-estimated communication delays and unit execution time (uect task graphs). The overlapping of communications by computations is allowed and communications between tasks executed on the same processor are neglected (known as the locality assumption). This set of hypotheses corresponds to the standard delay model (SDM) [3] and [6]. Using this environment execution model, in [8], the authors proved that scheduling complete binary trees on an unlimited number of processors with arbitrary communication delays is an NP-Hard problem. The problem remains NP-Hard for binary trees when communications depend on the size of the tree. When the communication delays are equal to a constant value c, the problem can be solved polynomially for complete k-ary trees. For arbitrary trees, keeping the same assumptions, the NP-Hardness of the problem is proved in [9]. The same complexity result holds for uect trees on an arbitrary number of processors organised as a full-connected graph [9], [10] and [12]. When the number of processors, say m, is fixed, the problem may be solved using a dynamic programming approach (complexity O(n2(m−1))) [20]. Finally, this problem becomes polynomial when the number of processors is 2 [9], [11], [12] and [13] or is not limited [4]. The main results are summed up in the following table using the notation described in [5]. A survey on scheduling problems with communication delays can be found in [14]. α|β|γ notation Result Reference | complete binary tree, , | NP-Hard [8] | tree (n vertices), , c=f(n)| NP-Hard [8] | complete k-ary tree, , c | Polynomial [8] | tree, , c | NP-Hard [9] P | tree, , c=1| NP-Hard [9], [10], [12] and [19] | tree, , c=1| [20] | tree, , c=1| Polynomial [9], [11], [13] and [22] | tree, , c=1| Polynomial [4] Table options While many works have been devoted to the study of scheduling precedence tasks graphs with communication delays, very few is known about the sensitivity analysis of these problems. Without communication delays, in [2] Graham studied the impact of changes for both numerical and structural parameters on the behaviour of list scheduling algorithms. When changes on processing times of the tasks are considered, Wagelmans showed that the sensitivity of a list scheduling rule increases with the quality of the schedule produced [7] and [15], and for the case of independent tasks Penz et al. showed that the sensitivity can be limited to the square root of the magnitude of the perturbation [16]. When communication delays are taken into account and for an unlimited number of processors, Gerasoulis and Yang [18] have proposed a relative sensitivity bound based on the notion of granularity. In [21] we proposed a stabilization scheme for m machines and arbitrary task graphs. This paper is a study of the sensitivity analysis of statically computed schedules for the problem (P2 | tree, pi=1, c=1 | Cmax) when the actual communication delays differ from the estimated ones. To this end, new results are presented for the makespan values with and without communications. We also introduce the notion of processor-ordered schedules, a structural property of the communications between processors, and we show their robustness when communication delays change. The paper is organized as follows: in Section 2, the model is precisely defined. Section 3 compares the two classical problems with and without communications. Within Section 4 tight relative and absolute bounds are presented for the two-machine problem. The sensitivity analysis of several algorithms providing optimal schedules in the uect case is presented in Section 5. We show that the cluster-based scheduling algorithm presented in [22] is by far the most robust. Some future trends for research are proposed in the conclusion.

In this paper, we have characterized the sensitivity of algorithms for scheduling trees with communication delays on two processors. The study focuses on changes concerning communication delays. We have shown that the best absolute sensitivity bound is and that the worst relative sensitivity bound is equal to . We have also proved that no algorithm can present better robustness than CBoS since it verifies the absolute bound. This is due to the fact that CBoS is processor-ordered. By contrast the three other known algorithms reach the worst relative bound. It is shown in the paper that algorithms producing processor-ordered schedules are dominant when all communication delays are equal to 0, or equal to 1. Unfortunately, they are not dominant in the sct case. In [7] a sensitivity analysis of list-scheduling algorithms was presented. When changes in processing times are considered, the author shows that the sensitivity of a schedule increases with its quality. Fortunately, our work shows that when changes in communication delays are considered, some algorithms can provide optimal schedules for estimated values while being the most robust. Further directions of research will focus on the sensitivity analysis where communication delays and/or execution times may vary, and when the number of available processors is equal to m. The goal is to identify cases for which optimality and robustness are compatible.