GPU-Based Parallel Particle Swarm Optimization Methods for Graph Drawing

Jianhua Qu, Xiyu Liu, Minghe Sun and Feng Qi

Discrete Dynamics in Nature and Society, 2017, vol. 2017, 1-15

Abstract:

Particle Swarm Optimization (PSO) is a population-based stochastic search technique for solving optimization problems, which has been proven to be effective in a wide range of applications. However, the computational efficiency on large-scale problems is still unsatisfactory. A graph drawing is a pictorial representation of the vertices and edges of a graph. Two PSO heuristic procedures, one serial and the other parallel, are developed for undirected graph drawing. Each particle corresponds to a different layout of the graph. The particle fitness is defined based on the concept of the energy in the force-directed method. The serial PSO procedure is executed on a CPU and the parallel PSO procedure is executed on a GPU. Two PSO procedures have different data structures and strategies. The performance of the proposed methods is evaluated through several different graphs. The experimental results show that the two PSO procedures are both as effective as the force-directed method, and the parallel procedure is more advantageous than the serial procedure for larger graphs.

Date: 2017
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://downloads.hindawi.com/journals/DDNS/2017/2013673.pdf (application/pdf)
http://downloads.hindawi.com/journals/DDNS/2017/2013673.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnddns:2013673

DOI: 10.1155/2017/2013673

Access Statistics for this article

More articles in Discrete Dynamics in Nature and Society from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().