Assefaw Gebremedhin, Research, Parallel Graph Algorithms

Graph (network) computations are critical kernels in many algorithms in computational science and engineering, data mining, data analysis, etc. In large-scale applications, the graph computations need to be performed in parallel. Effective parallelization of graph algorithms--with emphasis on performance and scalability--is a particularly challenging endeavor, for a variety of reasons. In many graph algorithms runtime is dominated by memory latency rather than processor speed, there exist little computation to hide memory access costs, data locality is poor, and available concurrency is low.

Listed below in reverse chronological order are papers I have written together with a number of different collaborators introducing a range of techniques for dealing with these challenges in the context of a variety graph problems. Much of my earlier work in this direction focused on distributed-memory platforms. My more recent effort targets the emerging and rapidly growing multicore platforms as well as massively multithreaded platforms. I am in general interested in exploring the interplay between algorithms, architectures, and applications in developing scalable systems.

Software

MPI-based implementations of some of the distributed memory parallel algorithms for the distance-1 and distance-2 coloring problems I developed together with colleagues are publicly available via the Zoltan software toolkit of Sandia National Laboratories.

Papers

Go back to Research Areas or go forward to
  • Coloring and Automatic Differentiation
  • Parallel Computation Models