Multi-criteria divisible load scheduling in binary tree network

The Divisible Load Theory (DLT) is a paradigm in the area of parallel and distributed computing. Based on the divisible load theory, the computation and communication can be divided into some arbitrary independent parts, in which each part can be processed independently by a processor. A class of the scheduling methods which is defined based on the DLT is called the Divisible Load Scheduling (DLS). The traditional divisible load scheduling assumes that the processors report their true computation and communication rates, i.e., they do not cheat the algorithm. In the real applications, the processors may cheat the algorithm, which means, the processors might not report their true computation or communication rates. However, the problem that the processors may not report their true computation rates is called computation rate-cheating problem. The same definition can be considered for the communication rate-cheating problem. However, this problem was investigated by Thomas E. Carroll and D. Grosu in their research publications. The results of their research indicate that the computation rate-cheating reduces the performance of the divisible load scheduling. This thesis focuses on the computation and communication rate-cheating problems aiming to reduce the effects of computation and communication rate-cheating on the performance of the divisible load scheduling model. We adopt a multi-criteria approach to the problem. We propose three different multicriteria based methods in order to improve the performance of the divisible load scheduling. The first method is a multi-objective divisible load scheduling method. The results show that this method is able to considerably improve the performance of the divisible load scheduling when the processors cheat their computation rates. The experimental results indicate that the proposed method is able to reduce the finish time by approximately 66% in the best case. The limitation of the proposed multiobjective method is that this method slightly increases the start-up time. In order to reduce the limitation of the multi-objective method, a second method has been proposed, which is an Analytical Hierarchy Process (AHP) method. It is briefly called AHP-based method. The experimental results show that the AHP-based method is able to improve the performance of divisible load scheduling. In addition, it has a lower start-up time com- paring the multi-objective method. In the third proposed method, it is assumed that both the communication and computation might not be reported at the true rates; hence, we have a new approach to the communication and computation rate-cheating problems. We propose a priority-based divisible load scheduling method for the first time. The results show that this method is able to allocate the optimal load when the processors cheat their computation and communication rates. The proposed priority-based divisible load scheduling method is a novel effort in the area of divisible load scheduling over the past two decades.

Preview Text IPM 2016 9 - IR.pdf Download (1MB) | Preview

Actions (login required)

View Item