In this paper, we assess the impact of heterogeneity on scheduling independent tasks on master-slave platforms. We assume a realistic one-port model where the master can communicate with a single slave at any time. We...
详细信息
In this paper, we assess the impact of heterogeneity on scheduling independent tasks on master-slave platforms. We assume a realistic one-port model where the master can communicate with a single slave at any time. We target both on-line and off-line scheduling problems, and we focus on simpler instances where all tasks have the same size. While such on-line problems can be solved in polynomial time on homogeneous platforms, we show that there does not exist any optimal deterministic algorithm for heterogeneous platforms. Whether the source of heterogeneity comes from computation speeds, or from communication bandwidths, or from both, we establish lower bounds on the competitive ratio of any deterministic algorithm. We provide such bounds for the most important objective functions: the minimization of the makespan (or total execution time), the minimization of the maximum response time (difference between completion time and release time), and the minimization of the sum of all response times. Altogether, we obtain nine theorems which nicely assess the impact of heterogeneity on on-line scheduling. For off-line scheduling, we prove several result for problems with release dates, either optimality or NP-hardness. These theoretical contributions are complemented on the practical side by the implementation of several heuristics on a small but fully heterogeneous MPI platform. Our results show the superiority of those heuristics which fully take into account the relative capacity of the communication links. (C) 2008 Elsevier B.V. All rights reserved.
In this paper we present the multistage off-line method, a new and rather natural way to model off-line packet routing problems, which reduces the problem of off-line packet routing to that of finding edge disjoint pa...
详细信息
In this paper we present the multistage off-line method, a new and rather natural way to model off-line packet routing problems, which reduces the problem of off-line packet routing to that of finding edge disjoint paths on a multistage graph. The multistage off-line method can model any kind of routing pattern on any graph and can incorporate the size of the maximum queue allowed in any processor. The paths for the packets are computed by a greedy heuristic method. Based on the multistage off-line method, we study the permutation packet routing problem on two-dimensional meshes. We ran millions of experiments based on random generated data and, for all of our experiments, we were able to compute a solution of length equal to the maximum distance a packet had to travel, and thus, match the actual lower bound for each routing pattern.
Online frequency assignment for wireless cellular networks is one of the important research areas in recent time, where the geographical coverage area is divided into regular hexagonal regions called cells. Sequence o...
详细信息
ISBN:
(纸本)9781479980840
Online frequency assignment for wireless cellular networks is one of the important research areas in recent time, where the geographical coverage area is divided into regular hexagonal regions called cells. Sequence of requests arrives over time to the cells that are headed by the base stations. Each of the requests is either a new call or a drop-call which is served by the base station by assigning the frequencies or releasing the frequencies respectively. In order to minimize the span of frequencies use to serve all the requests for new calls originating from same or neighboring cells, reassignment of the frequency of the dropped-call is done to an already existing call that uses the highest frequency. For z-colorable networks, which are the generalization of the (3-colorable) cellular networks, we have suggested an efficient onlinealgorithm for frequency reassignment, minimizing the span of frequency usages. The competitive ratio of the proposed onlinealgorithm is (z+1)/3, which is sharper than the competitive ratio (z+1)/2 of existing similar problem without allowing reassignment of frequency. The optimality of the new algorithm is verified by finding the absolute lower and upper bounds of its competitive ratio for 3colrable cellular network as a particular case when x = 3.
We study the worst-case performance of approximation algorithms for the problem of multiprocessor task scheduling on m identical processors with resource augmentation, whose objective is to minimize the makespan. In t...
详细信息
ISBN:
(纸本)9781565553224
We study the worst-case performance of approximation algorithms for the problem of multiprocessor task scheduling on m identical processors with resource augmentation, whose objective is to minimize the makespan. In this case, the approximation algorithms are given k (k >= 0) extra processors than the optimal off-line algorithm. For on-linealgorithms, the Greedy algorithm and shelf algorithms are studied. For off-line algorithm, we consider the LPT (longest processing time) algorithm. Particularly, we prove that the schedule produced by the LPT algorithm is no longer than the optimal off-line algorithm if and only if k >= m - 2.
暂无评论