## 4 Conclusions  
UA-FLPs are widely used in different fields, including industrial facility design, warehouse organization, school facility layout, and VLSI element placement. However, UA-FLP is an NP-hard problem. With the increase in the problem size, the amount of calculation will become larger and larger, and the execution time is getting longer and longer even though metaheuristic approaches such as GA are applied to solve UA-FLP. In the traditional CPU workstations, when the number of the facilities reaches a certain level, it is difficult to calculate the appropriate solution within a reasonable period of time. IMGA, one of the most promising variants among the parallelized models of GA, can explore different regions of the search space. IMGA can improve the solution for most of the problem data set for the UA-FLP [21]. However, the IMGA method for UA-FLP still requires long execution time, so that the authors pointed an interesting future work: parallelizing IMGA. Using GPU to solve large-scale and complex computing has been widely investigated. Modern GPU, as specialized computer processors, can manipulate large amounts of data efficiently by  
Figure 16: Execution times of the different methods. Figure 17: Comparisons of performance ratio between two GPU versions and CPU version, respectively. The previous GPU version is implemented with previous parallel methods while our GPU version is implemented with our proposed methods. highly parallel many-core system. Parallel IMGA on GPU is focused in the recent work [22], while their parallelization approaches are preliminary because the authors mainly emphasize comparing performances between different parallel architectures. In addition, they used only one mathematical function to model and implement the IMGA. In this paper, we further investigated on parallelizing IMGA by GPU. We proposed multiple parallel algorithms for the main steps in the IMGA when solving the UA-FLP, including initialization, selection, mutation, and migration operators. In data initialization, there are two parts: generations of facility sequence and bay divisions. To generate the facility sequence, we proposed an improved method to eliminate a large number of comparisons in conventional method. Our method can also avoid regeneration of random numbers for the same array element. For the above reasons, our approach can reduce the time complexity from the previous O(\(p^{2}\)) to O(\(p\)). To generate bay divisions, our improved method used bitwise operators, instead of a lot of module operators in conventional methods, resulting in the time complexity is greatly reduced from O(\(p\)) to O(1). According to the previous work [22], when choosing a selection operator, we should take into account the relationship between it and the recombination operator. Therefore, we implemented two selection strategies--tournament selection and roulette wheel selection--to investigate which is better for UA-FLP. Through experimental results, roulette wheel selection is more suitable for UA-FLP due to the crossover strategies adopted, which is quite different from that in the reference [22] because two different crossover strategies are used for FBS encoding in UA-FLP. To parallelize the mutation operator, our method needs not to check for duplications, which improved the mutation performance. For migration parallelization, we proposed an enhanced method that uses one thread to deal with one gene, instead of one chromosome, to improve the migrated performance. Our improved migration algorithm is better than the conventional one because we take full advantage of the fine-grained parallelism and utilize memory coalescing to access global memory. Experiments were conducted to compare performances between the different parallel algorithms for each step. Based on theoretical derivation and experimental results, we integrated the better parallel method in each step into the parallel IMGA for UA-FLP on GPU.