Optimization in Extremum Graph Computation

Dhurjati Das Prasad

Abstract

Extremum Graphs are a subset of the Morse Smale (MS) Complex. It is a simpler representation possible of Morse decomposition of scalar fields. One of the benefits it provides is the preservation of topological and geometric properties.Tachyon is a software library that provides an efficient implementation of a parallel algorithm for computing the extremum graph. Its implementation utilizes Graphic Processing Unit (GPU) as well as Central Processing Unit (CPU) in tandem to reduce time costs as much as possible. Detailed observations on the execution of the tachyon show that as we move from one dimension to another (i.e., 3D to 4D to ND), the computation time increases exponentially. To reduce the computation time, we employed optimizations in the tachyon and found significant improvement. A few methods worth mentioning are the conversion of adjacency matrix ( O(4^D) ) to edge list ( O(3^D) ); Reducing the number of calls to a function from 2^D + 3^D calls to 2^D calls, with the help of a small local lookup table; Utilizing shared memory (default: 48KB) of GPU, which is an on-chip memory, gave a tremendous improvement in run time in higher dimensions, because of earlier thrashing issues persisted in GPU operations.

[PDF]