Multi-Level Graph Layout on the GPU

This paper presents a new algorithm for force directed graph layout on the GPU. The algorithm, whose goal is to compute layouts accurately and quickly, has two contributions. The rst contribution is proposing a general multi-level scheme, which is based on spectral partitioning. The second contribution is computing the layout on the GPU. Since the GPU requires a data parallel programming model, the challenge is devising a mapping of a naturally unstructured graph into a well-partitioned structured one. This is done by computing a balanced partitioning of a general graph. This algorithm provides a general multi-level scheme, which has the potential to be used not

only for computation on the GPU, but also on emerging multi-core architectures. The algorithm manages to compute high quality layouts of large graphs in a fraction of the time required by existing algorithms of similar quality. An application for visualization of the topologies of ISP (Internet Service Provider) networks is presented. Index Terms Graph layout, GPU, graph partitioning. 1 INTRODUCTION Graph drawing addresses the problem of constructing geometric rep- resentations of graphs [24,38]. It has applications in a variety of areas, including software engineering, software visualization, databases, in- formation systems, decision support systems, biology, and chemistry. Producing pleasing graph layouts fast is still a challenging problem. For instance, one of the most popular graph layout algorithms, the force directed algorithm, is computationally expensive. The complex- ity of each iteration of the algorithm is O(V 2 + E). On large graphs, the layout procedure can take anywhere from a few seconds to several minutes to complete, hindering the capability to use this algorithm to explore large data sets. In recent years, a popular way to accelerate computations is to per- form them on the GPU (graphics processing unit) [5,14,31,32]. This is due to the high computational power, low cost, and ubiquity of GPUs in every modern PC. GPUs are geared towards repetitively performing the same computation on large streams of data. Therefore, the GPU suits uniformly structured data, such as images or matrices. Graphs do not posses a uniform structure, hence, they do not admit any intuitive and natural representation that suits computation on the GPU. This paper proposes two ways in which force directed algorithms can be accelerated. The rst is a general multi-level scheme, which is based on spectral partitioning. The second is computation of a graph layout on the GPU. Multi-level graph layout algorithms have been proposed in the past [9, 15, 18, 20, 26, 34, 40]. In these algorithms, the given graph is recursively coarsened, to compute its multi-level representation. In contrast, in our scheme, the algorithm works on a high-detailed graph at all levels of the partitioning. Thus, a good hierarchical representa- tion of the graph is obtained. The scheme proposed in this paper is a general multi-level scheme, which is based on spectral partitioning. Using a bottom up approach, layouts of increasing detail are com- puted. It is shown how coarse layouts of a graph can be ef ciently extended to the nal high quality...

Website: webee.technion.ac.il | Filesize: -
No of Page(s): 8
Download Multi-Level Graph Layout on the GPU.pdf