Suppr超能文献

基于图形处理器的多层图布局

Multi-level graph layout on the GPU.

作者信息

Frishman Yaniv, Tal Ayellet

出版信息

IEEE Trans Vis Comput Graph. 2007 Nov-Dec;13(6):1310-9. doi: 10.1109/TVCG.2007.70580.

Abstract

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 first 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.

摘要

本文提出了一种用于在图形处理器(GPU)上进行力导向图布局的新算法。该算法旨在准确且快速地计算布局,有两个贡献。第一个贡献是提出了一种基于谱划分的通用多级方案。第二个贡献是在GPU上计算布局。由于GPU需要数据并行编程模型,挑战在于将自然的非结构化图映射到一个划分良好的结构化图。这通过计算通用图的平衡划分来完成。该算法提供了一种通用多级方案,它不仅有潜力用于GPU计算,还可用于新兴的多核架构。该算法能够在现有类似质量算法所需时间的一小部分内计算出大型图的高质量布局。还展示了一个用于互联网服务提供商(ISP)网络拓扑可视化的应用。

文献AI研究员

20分钟写一篇综述,助力文献阅读效率提升50倍。

立即体验

用中文搜PubMed

大模型驱动的PubMed中文搜索引擎

马上搜索

文档翻译

学术文献翻译模型,支持多种主流文档格式。

立即体验