high performance computing on graphics processing units: hgpu.org

Twilight, an interactive multi-touch graph visualization research tool jointly developed by the University of Amsterdam and SURFsara, uses the Fruchterman-Reingold algorithm (amongst others) to create meaningful layouts for graphs. The required time for this algorithm to complete scales exponentially with the size of the graphs, therefore rendering large graphs quickly becomes impractical. To combat this an investigation was conducted into parallelizing this algorithm for use on Graphical Processing Units. This thesis describes the design and implementation of an OpenCL based implementation of the Fruchterman-Reingold algorithm. We show that this implementation speeds up the rendering of graphs by a factor of up to 15 times compared to the original implementation within Twilight.