Using GPU and OpenACC to Accelerate the Maze Optimal Routing Algorithm

Yu Liu; Yi Xiao

doi:10.4028/www.scientific.net/AMM.380-384.1338

Paper Titles

An O(n) Time Algorithm to Find Cubic Subgraph in a Halin Graph
p.1318

Nonlinear Non-Gaussian Filtering Algorithm Based on Cubature Kalman and Particle Filter
p.1323

Network Layer Network Topology Discovery Algorithm Research
p.1327

The Role of Modelling in Agile Methodologies
p.1333

Using GPU and OpenACC to Accelerate the Maze Optimal Routing Algorithm
p.1338

Teaching-Learning-Based Optimization Algorithm for Dealing with Real-Parameter Optimization Problems
p.1342

Criteria for α-Diagonally Dominant Matrices and its Applications
p.1346

An Improved Algorithm for Estimating the Parameters of Polynomial-Phase Signals
p.1350

Study on the Influence IDs Model of the Structure and the Behavior Choice
p.1354

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 380-384Using GPU and OpenACC to Accelerate the Maze...

Using GPU and OpenACC to Accelerate the Maze Optimal Routing Algorithm

Abstract:

in order to improve the efficiency of maze optimal routing problem, a GPU acceleration programming model OpenACC is used in this paper. By analyzing an algorithm which solves the maze problem based on ant colony algorithm, we complete the task mapping on the model. Though GPU acceleration, ant colony searching process was changed into parallel matrix operations. To decrease the algorithm accessing overhead and increase operating speed, data were rationally organized and stored for GPU. Experiments of different scale maze matrix show that the parallel algorithm greatly reduces the operation time. Speedup will be increased with the expansion of the matrix size. In our experiments, the maximum speedup is about 6.1. The algorithm can solve larger matrices with a high level of processing performance by adding efficient OpenACC instruction to serial code and organizing the data structure for parallel accessing.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 380-384)

Pages:

1338-1341

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.380-384.1338

Citation:

Cite this paper

Online since:

August 2013

Authors:

Yu Liu, Yi Xiao

Keywords:

Maze Problem, Optimal Routing, Parallel Computing

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] Colorni A and so on. An investigation of some properties of an ant algorithm, Of the Parallel Problem Solving from Nature Conference (PPSNp92)[C]. Brussels. Belgium. Elsevier Publishing, 1922. 509–520.

Google Scholar

[2] Dorigo M and so on. The ant system: Optimization by a colony of cooperating agents [J]. IEEE Transactions on System, Man and Cybernetics Part B. 1996(26) 29-41.

DOI: 10.1109/3477.484436

Google Scholar

[3] Hu Xiao-bing and Huang Xi-yue. Ant colony algorithm in maze optimal path problem, Computer Simulation. 2005(22) 114–116.

Google Scholar

[4] Zhang Gong-jing and Xu Xi-jun. The application of ant colony algorithm to solve the maze optimal path [J]. Journal of Qingdao University (Natural Science). 2008(21) 61–65.

Google Scholar

[5] Stutzle T and Hoos H H. The MAX2MIN ant system and local search for the t raveling sales man problem [C] . In : Proc. ICEC 9721997 IEEE 4th Int. Conf. Evolutionary Computation, (1997).

DOI: 10.1109/icec.1997.592327

Google Scholar

[6] Li Jian-ming and so on. A fine-grained parallel GPU accelerated ant colony algorithm [J]. Control and decision-making. 2009(24) 1132–1136.

Google Scholar

[7] The OpenACC Application Programming Interface. http: /www. openacc. org/sites/default/files/ OpenACC. 1. 0_0. pdf, (2011).

Google Scholar

[8] PGI Accelerator Compilers OpenACC Getting Started Guide. http: /www. pgroup. com/doc/ openACC_gs. pdf, (2012).

Google Scholar