An Implementation of Membrane Algorithms on GPU

摘要：

　　Membrane algorithms are a new class of heuristic algorithms, which attempt to incorporate some components of membrane computing models (also called P systems) for designing efficient optimization algorithms, such as the structure of P systems, the way of communication between cells, etc. Membrane algorithms are a kind of parallel methods, where many operations can be performed in parallel. Although the importance of the parallelism of such algorithms is recognized, membrane algorithms were often implemented on the serial computing device Central Processing Unit (CPU), which makes the algorithms cannot work in a more efficient way. In this work, we consider the implementation of membrane algorithms on the parallel computing device Graphics Processing Unit (GPU). Under such implementation, all cells of membrane algorithms can work simultaneously. Experiment results on two classical intractable problems, point set matching problem and TSP, show that GPU implementation of membrane algorithms is much more efficient than CPU implementation in terms of runtime, especially for solving the problems with a high complexity.

关键词： Membrane computing Membrane algorithm Parallel computing device GPU

作者: Xingyi Zhang Dong Qin Zhuanlian Ding Jin Tang

作者单位: Key Lab of Intelligent Computing and Signal Processing of Ministry of Education,School of Computer Science and Technology,Anhui University Hefei 230039,China

会议类型: 国际会议

会议名称: 2013年第二届亚洲膜计算国际会议(2013ACMC)

会议地点: 成都

会议语种:英文

页码: 399-411

在线出版日期: 2013-11-04（万方平台首次上网日期，不代表论文的发表时间）