Hybrid real-coded genetic algorithm for data partitioning in multi-round load distribution and scheduling in heterogeneous systems
- Authors
- Suresh, S.; Huang, Hao; Kim, H. J.
- Issue Date
- 11월-2014
- Publisher
- ELSEVIER
- Keywords
- Data partitioning; Scheduling; Genetic algorithm; Divisible loads; Parallel computing
- Citation
- APPLIED SOFT COMPUTING, v.24, pp.500 - 510
- Indexed
- SCIE
SCOPUS
- Journal Title
- APPLIED SOFT COMPUTING
- Volume
- 24
- Start Page
- 500
- End Page
- 510
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/96864
- DOI
- 10.1016/j.asoc.2014.07.021
- ISSN
- 1568-4946
- Abstract
- Data partitioning and scheduling is one the important issues in minimizing the processing time for parallel and distributed computing system. We consider a single-level tree architecture of the system and the case of affine communication model, for a general m processor system with n rounds of load distribution. For this case, there exists an optimal activation order, optimal number of processors m* (m* <= m), and optimal rounds of load distribution n* (n* <= n), such that the processing time of the entire processing load is a minimum. This is a difficult optimization problem because for a given activation order, we have to first identify the processors that are participating (in the computation process) in every round of load distribution and then obtain the load fractions assigned to them, and the processing time. Hence, in this paper, we propose a real-coded genetic algorithm (RCGA) to solve the optimal activation order, optimal number of processors m* (m* <= m), and optimal rounds of load distribution n* (n* <= n), such that the processing time of the entire processing load is a minimum. RCGA employs a modified crossover and mutation operators such that the operators always produce a valid solution. Also, we propose different population initialization schemes to improve the convergence. Finally, we present a comparative study with simple real-coded genetic algorithm and particle swarm optimization to highlight the advantage of the proposed algorithm. The results clearly indicate the effectiveness of the proposed real-coded genetic algorithm. (C) 2014 Elsevier B.V. All rights reserved.
- Files in This Item
- There are no files associated with this item.
- Appears in
Collections - ETC > 1. Journal Articles
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.