3376

Two improved GPU acceleration strategies for force-directed graph layout

Wang Yong-Xian, Li Zong-Zhe, Yao Lu, Cao Wei, Wang Zheng-Hua
Nat. Key Lab. for Parallel & Distrib. Process., Nat. Univ. of Defense Technol., Changsha, China
International Conference on Computer Application and System Modeling (ICCASM), 2010

@conference{yong2010two,

   title={Two improved GPU acceleration strategies for force-directed graph layout},

   author={Yong-Xian, W. and Zong-Zhe, L. and Lu, Y. and Wei, C. and Zheng-Hua, W.},

   booktitle={Computer Application and System Modeling (ICCASM), 2010 International Conference on},

   volume={13},

   pages={V13–132},

   organization={IEEE}

}

Source Source   

831

views

Force directed approach is one of the most widely used methods in graph drawing research. However, the running time is increased intolerablely along with the enlargement of the graph size, which restricts the algorithm’s practicability. By the aid of GPU (graphics processing unit) computing platform, we can speed-up the graph layout with low cost, but the existing GPU implementation mainly employees an “one-by-one” style to update the vertex’ coordination per iteration, which has a lower convergent rate than the “batch” style which is instead used commonly in traditional CPU implementation. As a result, the aesthetics of graph layout would be decreased if the total running time is restricted. It is hard to achieve both a high speedup factor of GPU over CPU and a high convergent rate in existing GPU computing implementation. In order to solve this problem partially, this paper presents two new strategies to implement the large-scale graph layout on CPU+GPU heteromerous platform to accelerate the force directed layout for graph drawing problem. The numerical computation results show that our GPU implementation can dramatically improve the performance of force-direct layout and is 20 times on a NVIDIA GeForce 9800 GT GPU at 1.44 GHz faster than the one on single-CPU core of Intel Pentium 4 PC at 3.0 GHz for the graph layout with moderate size (typically 1000 vertices).
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: