Rapid Multipole Graph Drawing on the GPU

Godiyal, Apeksha and Hoberock, Jared and Garland, Michael and Hart, John C. (2009) Rapid Multipole Graph Drawing on the GPU. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 90-101 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_10).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_10
Classifications:M Methods > M.400 Force-directed / Energy-based
P Styles > P.720 Straight-line
G Algorithms and Complexity > G.560 Geometry
ID Code:899

Repository Staff Only: item control page

References

Aluru, S., Prabhu, G.M., Gustafson, J.: Truly distribution-independent algorithms for the n-body problem. In: Proc. Supercomputing. pp. 420–428 (1994)

Appel, A.W.: An efficient program for many-body simulation.SIAM J. Sci. & Stat. Comp. 6(1), 85–103 (1985)

Barnes, J., Hut, P.: A hierarchical o(n log n) force-calculation algorithm. Nature 324(6096), 446–449 (Dec 1986)

Batini, C.: Applications of graph drawing to software engineering (abstract). SIGACT News 24(1), 57 (1993)

Bentley, J.L.: Multidimensional binary search trees used for associative searching. CACM 18(9), 509–517 (1975)

Carr, N.A., Hoberock, J., Crane, K., Hart, J.C.: Fast gpu ray tracing of dynamic meshes using geometry images. In: Proc. Graphics Interface. pp. 203–209 (2006)

Davidson,R., Harel, D.: Drawing graphs nicely using simulated annealing. ACM Trans. Graph. 15(4), 301–331 (1996)

Dikaiakos, M.D., Stadel, J.: A performance study of cosmological simulations on message-passing and shared-memory multiprocessors. In: Intl. Conf. on Supercomputing. pp. 94–101 (1996)

Eades, P.A.: A heuristic for graph drawing. Congressus Numerantium 42, 149–160 (1984)

Foley, T., Sugerman, J.: Kd-tree acceleration structures for a GPU raytracer. In: Proc. Graphics Hardware. pp. 15–22 (2005)

Frishman, Y., Tal, M.A.: Multi-level graph layout on the gpu. IEEE Trans. Vis. Comp. Graph. 13(6), 1310–1319 (2007)

Fruchterman, T.M.J., Reingold,E.M.: Graph drawing by force-directed placement. Software - Practice and Experience 21(11), 1129–1164 (1991)

Gajer, P., Goodrich, M.T., Kobourov, S.G.: A multi-dimensional approach to force-directed layouts of large graphs. Comput. Geom. Theory Appl. 29(1), 3–18 (2004)

Gajer, P., Kobourov, S.G.: Grip: Graph drawing with intelligent placement. In: Proc. Graph Drawing. pp. 222–228 (2001)

Grama, A.Y., Kumar, V., Sameh, A.: Scalable parallel formulations of the BarnesHut method for n-body simulations. In: Proc. Supercomputing. pp. 439–448 (1994)

Greengard, L.F.: The rapid evaluation of potential fields in particle systems. Ph.D. thesis, Yale, New Haven, CT, USA (1987)

Gumerov, N.A., Duraiswami, R.: Fast multipole methods on graphics processors. J. Comp. Physics 227, 8290–8313 (2008)

Hachul, S., Jünger, M.: Large-graph layout with the fast multipole multilevel method. Tech. rep., Zentrum für Angewandte Informatik Köln (December 2005)

Hachul, S., Jünger, M.: An experimental comparison of fast algorithms for drawing general large graphs. (Proc. Graph Drawing) LNCS 3843, 235–250 (2006)

Harel, D., Koren, Y.: A fast multi-scale method for drawing large graphs. (Proc. Graph Drawing), LNCS 1984, 183–196, Springer, Heidelberg(2001)

Harel, D., Koren, Y.: Graph drawing by high dimensional embedding. (Proc. Graph Drawing), LNCS 2528 (2002)

Kamada, T., Kawai, S.: An algorithm for drawing general undirected graphs. Inf. Process. Lett. 31(1), 7–15 (1989)

Koren, Y., Carmel, L., Harel, D.: ACE: a fast multiscale eigenvectors computation for drawing huge graphs (2001)

Mahmoud, H.M.: Sorting: A Distribution Theory, chap. High Qulaity Ambient Occlusion. Wiley-Interscience (2000)

NVIDIA: CUDA data parallel primitives library, http://www.gpgpu.org/developer/cudpp/

NVIDIA: CUDA programming guide (2007), http://developer.nvidia.com/ob ject/cuda.html

Pharr, M., Fernando, R.: GPU Gems 2: Programming Techniques for HighPerformance Graphics and General-Purpose Computation. Addison-Wesley Professional (2005)

Sarin, V.: Analyzing the error bounds of multipole-based treecodes. Proc. Supercomputing p. 19 (1998)

Sengupta, S.,Harris, M., Zhang, Y., Owens, J.D.: Scan primitives for gpu computing. In: Proc. Graphics Hardware. pp. 97–106 (Aug 2007)

Stock, M.J., Gharakhani, A.: Toward efficient gpu-accelerated n-body simulations. In: 46th AIAA Aerospace Sciences Meeting & Exhibit (2008)

Uhlmann, J.K.: Enhancing multidimensional tree structures by using a bi-linear decomposition. Natl. Tech. Info. Svc. ADA229756 (1990)

Walshaw, C.: A multilevel algorithm for force-directed graph drawing. (Proc. Graph Drawing) LNCS 1984, 171–182 (2001)

Walshaw, C.: Graph collection at staffweb.cms.gre.ac.uk/∼wc06/partition/ (2007)