Parallel Implementations of Candidate Solution Evaluation Algorithm for N-Queens Problem
The N-Queens problem plays an important role in academic research and practical application. Heuristic algorithm is often used to solve variant 2 of the N-Queens problem. In the process of solving, evaluation of the candidate solution, namely, fitness function, often occupies the vast majority of ru...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2021-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2021/6694944 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832554121706602496 |
|---|---|
| author | Jianli Cao Zhikui Chen Yuxin Wang He Guo |
| author_facet | Jianli Cao Zhikui Chen Yuxin Wang He Guo |
| author_sort | Jianli Cao |
| collection | DOAJ |
| description | The N-Queens problem plays an important role in academic research and practical application. Heuristic algorithm is often used to solve variant 2 of the N-Queens problem. In the process of solving, evaluation of the candidate solution, namely, fitness function, often occupies the vast majority of running time and becomes the key to improve speed. In this paper, three parallel schemes based on CPU and four parallel schemes based on GPU are proposed, and a serial scheme is implemented at the baseline. The experimental results show that, for a large-scale N-Queens problem, the coarse-grained GPU scheme achieved a maximum 307-fold speedup over a single-threaded CPU counterpart in evaluating a candidate solution. When the coarse-grained GPU scheme is applied to simulated annealing in solving N-Queens problem variant 2 with a problem size no more than 3000, the speedup is up to 9.3. |
| format | Article |
| id | doaj-art-ddce06f8ab404affbf3cd453295402d9 |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2021-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-ddce06f8ab404affbf3cd453295402d92025-02-03T05:52:26ZengWileyComplexity1076-27871099-05262021-01-01202110.1155/2021/66949446694944Parallel Implementations of Candidate Solution Evaluation Algorithm for N-Queens ProblemJianli Cao0Zhikui Chen1Yuxin Wang2He Guo3School of Software Technology, Dalian University of Technology, Dalian, ChinaSchool of Software Technology, Dalian University of Technology, Dalian, ChinaSchool of Computer Science and Technology, Dalian University of Technology, Dalian, ChinaSchool of Software Technology, Dalian University of Technology, Dalian, ChinaThe N-Queens problem plays an important role in academic research and practical application. Heuristic algorithm is often used to solve variant 2 of the N-Queens problem. In the process of solving, evaluation of the candidate solution, namely, fitness function, often occupies the vast majority of running time and becomes the key to improve speed. In this paper, three parallel schemes based on CPU and four parallel schemes based on GPU are proposed, and a serial scheme is implemented at the baseline. The experimental results show that, for a large-scale N-Queens problem, the coarse-grained GPU scheme achieved a maximum 307-fold speedup over a single-threaded CPU counterpart in evaluating a candidate solution. When the coarse-grained GPU scheme is applied to simulated annealing in solving N-Queens problem variant 2 with a problem size no more than 3000, the speedup is up to 9.3.http://dx.doi.org/10.1155/2021/6694944 |
| spellingShingle | Jianli Cao Zhikui Chen Yuxin Wang He Guo Parallel Implementations of Candidate Solution Evaluation Algorithm for N-Queens Problem Complexity |
| title | Parallel Implementations of Candidate Solution Evaluation Algorithm for N-Queens Problem |
| title_full | Parallel Implementations of Candidate Solution Evaluation Algorithm for N-Queens Problem |
| title_fullStr | Parallel Implementations of Candidate Solution Evaluation Algorithm for N-Queens Problem |
| title_full_unstemmed | Parallel Implementations of Candidate Solution Evaluation Algorithm for N-Queens Problem |
| title_short | Parallel Implementations of Candidate Solution Evaluation Algorithm for N-Queens Problem |
| title_sort | parallel implementations of candidate solution evaluation algorithm for n queens problem |
| url | http://dx.doi.org/10.1155/2021/6694944 |
| work_keys_str_mv | AT jianlicao parallelimplementationsofcandidatesolutionevaluationalgorithmfornqueensproblem AT zhikuichen parallelimplementationsofcandidatesolutionevaluationalgorithmfornqueensproblem AT yuxinwang parallelimplementationsofcandidatesolutionevaluationalgorithmfornqueensproblem AT heguo parallelimplementationsofcandidatesolutionevaluationalgorithmfornqueensproblem |