Rapid multipole graph drawing on the GPU

Apeksha Godiyal; Jared Hoberock; Michael Garland; John C. Hart

doi:10.1007/978-3-642-00219-9_10

Rapid multipole graph drawing on the GPU

Apeksha Godiyal, Jared Hoberock, Michael Garland, John C. Hart

Siebel School of Computing and Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

As graphics processors become powerful, ubiquitous and easier to program, they have also become more amenable to general purpose high-performance computing, including the computationally expensive task of drawing large graphs. This paper describes a new parallel analysis of the multipole method of graph drawing to support its efficient GPU implementation. We use a variation of the Fast Multipole Method to estimate the long distance repulsive forces in force directed layout. We support these multipole computations efficiently with a k-d tree constructed and traversed on the GPU. The algorithm achieves impressive speedup over previous CPU and GPU methods, drawing graphs with hundreds of thousands of vertices within a few seconds via CUDA on an NVIDIA GeForce 8800 GTX.

Original language	English (US)
Title of host publication	Graph Drawing - 16th International Symposium, GD 2008, Revised Papers
Publisher	Springer
Pages	90-101
Number of pages	12
ISBN (Print)	3642002188, 9783642002182
DOIs	https://doi.org/10.1007/978-3-642-00219-9_10
State	Published - 2009
Event	16th International Symposium on Graph Drawing, GD 2008 - Heraklion, Crete, Greece Duration: Sep 21 2008 → Sep 24 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5417 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	16th International Symposium on Graph Drawing, GD 2008
Country/Territory	Greece
City	Heraklion, Crete
Period	9/21/08 → 9/24/08

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/978-3-642-00219-9_10

Library availability

Discover UIUC Full Text

Cite this

Godiyal, A., Hoberock, J., Garland, M., & Hart, J. C. (2009). Rapid multipole graph drawing on the GPU. In Graph Drawing - 16th International Symposium, GD 2008, Revised Papers (pp. 90-101). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5417 LNCS). Springer. https://doi.org/10.1007/978-3-642-00219-9_10

Rapid multipole graph drawing on the GPU. / Godiyal, Apeksha; Hoberock, Jared; Garland, Michael et al.
Graph Drawing - 16th International Symposium, GD 2008, Revised Papers. Springer, 2009. p. 90-101 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5417 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Godiyal, A, Hoberock, J, Garland, M & Hart, JC 2009, Rapid multipole graph drawing on the GPU. in Graph Drawing - 16th International Symposium, GD 2008, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5417 LNCS, Springer, pp. 90-101, 16th International Symposium on Graph Drawing, GD 2008, Heraklion, Crete, Greece, 9/21/08. https://doi.org/10.1007/978-3-642-00219-9_10

@inproceedings{9254a52fad7c4bc0903be07aa1995bec,

title = "Rapid multipole graph drawing on the GPU",

abstract = "As graphics processors become powerful, ubiquitous and easier to program, they have also become more amenable to general purpose high-performance computing, including the computationally expensive task of drawing large graphs. This paper describes a new parallel analysis of the multipole method of graph drawing to support its efficient GPU implementation. We use a variation of the Fast Multipole Method to estimate the long distance repulsive forces in force directed layout. We support these multipole computations efficiently with a k-d tree constructed and traversed on the GPU. The algorithm achieves impressive speedup over previous CPU and GPU methods, drawing graphs with hundreds of thousands of vertices within a few seconds via CUDA on an NVIDIA GeForce 8800 GTX.",

author = "Apeksha Godiyal and Jared Hoberock and Michael Garland and Hart, {John C.}",

year = "2009",

doi = "10.1007/978-3-642-00219-9_10",

language = "English (US)",

isbn = "3642002188",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "90--101",

booktitle = "Graph Drawing - 16th International Symposium, GD 2008, Revised Papers",

address = "Germany",

note = "16th International Symposium on Graph Drawing, GD 2008 ; Conference date: 21-09-2008 Through 24-09-2008",

}

TY - GEN

T1 - Rapid multipole graph drawing on the GPU

AU - Godiyal, Apeksha

AU - Hoberock, Jared

AU - Garland, Michael

AU - Hart, John C.

PY - 2009

Y1 - 2009

N2 - As graphics processors become powerful, ubiquitous and easier to program, they have also become more amenable to general purpose high-performance computing, including the computationally expensive task of drawing large graphs. This paper describes a new parallel analysis of the multipole method of graph drawing to support its efficient GPU implementation. We use a variation of the Fast Multipole Method to estimate the long distance repulsive forces in force directed layout. We support these multipole computations efficiently with a k-d tree constructed and traversed on the GPU. The algorithm achieves impressive speedup over previous CPU and GPU methods, drawing graphs with hundreds of thousands of vertices within a few seconds via CUDA on an NVIDIA GeForce 8800 GTX.

AB - As graphics processors become powerful, ubiquitous and easier to program, they have also become more amenable to general purpose high-performance computing, including the computationally expensive task of drawing large graphs. This paper describes a new parallel analysis of the multipole method of graph drawing to support its efficient GPU implementation. We use a variation of the Fast Multipole Method to estimate the long distance repulsive forces in force directed layout. We support these multipole computations efficiently with a k-d tree constructed and traversed on the GPU. The algorithm achieves impressive speedup over previous CPU and GPU methods, drawing graphs with hundreds of thousands of vertices within a few seconds via CUDA on an NVIDIA GeForce 8800 GTX.

UR - http://www.scopus.com/inward/record.url?scp=68749114440&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=68749114440&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-00219-9_10

DO - 10.1007/978-3-642-00219-9_10

M3 - Conference contribution

AN - SCOPUS:68749114440

SN - 3642002188

SN - 9783642002182

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 90

EP - 101

BT - Graph Drawing - 16th International Symposium, GD 2008, Revised Papers

PB - Springer

T2 - 16th International Symposium on Graph Drawing, GD 2008

Y2 - 21 September 2008 through 24 September 2008

ER -

Rapid multipole graph drawing on the GPU

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this