All-Pairs Shortest-Paths for Large Graphs on the GPU (Englisch)

In: Graphics Hardware   ;  47-55  ;  2008

Wie erhalte ich diesen Titel?

Download
Kommerziell Vergütung an den Verlag: 14,50 € Grundgebühr: 4,00 € Gesamtpreis: 18,50 €
Akademisch Vergütung an den Verlag: 4,50 € Grundgebühr: 2,00 € Gesamtpreis: 6,50 €

The all-pairs shortest-path problem is an intricate part in numerous practical applications. We describe a shared memory cache efficient GPU implementation to solve transitive closure and the all-pairs shortest-path problem on directed graphs for large datasets. The proposed algorithmic design utilizes the resources available on the NVIDIA G80 GPU architecture using the CUDA API. Our solution generalizes to handle graph sizes that are inherently larger then the DRAM memory available on the GPU. Experiments demonstrate that our method is able to significantly increase processing large graphs making our method applicable for bioinformatics, internet node traffic, social networking, and routing problems.

  • Titel:
    All-Pairs Shortest-Paths for Large Graphs on the GPU
  • Autor / Urheber:
  • Erschienen in:
  • Verlag:
    The Eurographics Association
  • Erscheinungsort:
    Postfach 8043, 38621 Goslar, Germany
  • Erscheinungsjahr:
    2008
  • Format / Umfang:
    9 pages
  • ISBN:
  • ISSN:
  • DOI:
  • Medientyp:
    Aufsatz (Konferenz)
  • Format:
    Elektronische Ressource
  • Sprache:
    Englisch
  • Datenquelle:
  • Exportieren:
  • ORKG:

Inhaltsverzeichnis Konferenzband

Die Inhaltsverzeichnisse werden automatisch erzeugt und basieren auf den im Index des TIB-Portals verfügbaren Einzelnachweisen der enthaltenen Beiträge. Die Anzeige der Inhaltsverzeichnisse kann daher unvollständig oder lückenhaft sein.

1
Tracy: A Debugger and System Analyzer for Cross-Platform Graphics Development
Kyöstilä, Sami / Kangas, Kari J. / Pulli, Kari | 2008
13
Total Recall: A Debugging Framework for GPUs
Sharif, Ahmad / Lee, Hsien-Hsin S. | 2008
21
A Hardware Processing Unit for Point Sets
Heinzle, Simon / Guennebaud, Gaël / Botsch, Mario / Gross, Markus | 2008
33
Coherent Layer Peeling for Transparent High-Depth-Complexity Scenes
Carr, Nathan / Mech, Radomir / Miller, Gavin | 2008
41
Non-Uniform Fractional Tessellation
Munkberg, Jacob / Hasselgren, Jon / Akenine-Möller, Tomas | 2008
47
All-Pairs Shortest-Paths for Large Graphs on the GPU
Katz, Gary J. / Jr., Joseph T. Kider | 2008
57
On Dynamic Load Balancing on Graphics Processors
Cederman, Daniel / Tsigas, Philippas | 2008
65
GPU Accelerated Pathfinding
Bleiweiss, Avi | 2008
75
Floating-Point Buffer Compression in a Unified Codec Architecture
Ström, Jacob / Wennersten, Per / Rasmusson, Jim / Hasselgren, Jon / Munkberg, Jacob / Clarberg, Petrik / Akenine-Möller, Tomas | 2008
85
DHTC: An Effective DXTC-based HDR Texture Compression Scheme
Sun, Wen / Lu, Yan / Wu, Feng / Li, Shipeng | 2008
95
An Improved Shading Cache for Modern GPUs
Sitthi-amorn, Pitchaya / Lawrence, Jason / Yang, Lei / Sander, Pedro V. / Nehab, Diego | 2008
Feedback