Home
Assefaw Gebremedhin, Research, Parallel Graph Algorithms
Graph (network) computations are critical kernels in many algorithms
in data mining, data analysis, scientific computing, computational science and engineering, etc.
In large-scale applications, the graph computations need to be performed in parallel.
Parallelizing graph algorithms effectively -- with emphasis on scalability
and performance -- is particularly challenging 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
Multi-core and multi-threaded architrectures
-
H.Lu, M. Halappanavar, D. Chavarri-a-Miranda, A.H. Gebremedhin and
A. Kalyanaraman, Balanced Coloring for Parallel Computing Applications ,
Proceedings of IPDPS 2015.
Abstract
Paper
in PDF
-
R.A. Rossi, D.F. Gleich, A.H. Gebremedhin and M.M.A Patwary,
Fast Maximum Clique Algorithms for Large Graphs, Proceedings of WWW2014.
Abstract
Paper
in PDF
-
U. Catalyurek, J. Feo, A.H. Gebremedhin, M. Halappanavar and A. Pothen,
Graph Coloring Algorithms for Multi-core and Massively Multi-threaded Architectures, Parallel Computing 38 (2012), 576-594.
Abstract
Paper
in PDF
-
M.M.A. Patwary, A.H. Gebremedhin and A. Pothen,
New Multithreaded Ordering and Coloring Algorithms for Multicore Architectures,
In E. Jeannot, R. Namyst and J. Roman, editors, Euro-Par 2011,
volume 6853 of Lecture Notes in Computer Science, pages 250--262. Springer, 2011.
Abstract
Paper
in PDF
Distributed-memory architectures
-
U. Catalyurek, F. Dobrian, A.H. Gebremedhin, M. Halappanavar and A. Pothen,
Distributed-memory Parallel Algorithms for Matching and Coloring,
Proceedings of IEEE International Parallel and Distributed
Processing Symposium, Workshops and PhD Forums (IPDPSW),
Workshop on Parallel Computing and Optimization (PCO'11), pages 1966--1975, 2011
.
Abstract
Paper
in PDF
-
D. Bozdag, U. Catalyurek, A.H. Gebremedhin, F. Manne, E. Boman and F. Ozgunner,
Distributed-memory Parallel Algorithms for Distance-2 Coloring and
Related Problems in Derivative Computation,
SIAM Journal on Scientific Computing Vol 32, Issue 4, pp 2418--2446, 2010.
Abstract
Paper
in PDF
-
D. Bozdag, A.H. Gebremedhin, F. Manne, E. Boman and U. Catalyurek,
A framework
for Scalable Greedy Coloring on Distributed Memory Parallel Computers,
Journal of Parallel and Distributed Computing Vol 68, No 4, pp 515-535,
2008.
Abstract
Paper
in PDF
-
D. Bozdag, U. Catalyurek, A.H. Gebremedhin, F. Manne, E. G. Boman and F.
Ozguner, A Parallel Distance-2 Graph Coloring Algorithm for Distributed
Memory Computers, Lecture Notes in Computer Science, vol 3726,
2005, pages 796 - 806,Springer. Proc. of HPCC 2005, Sept 21 - 25, 2005,
Sorrento, Italy.
Abstract
Paper in PDF
-
E.G. Boman, D. Bozdag, U. Catalyurek, A.H. Gebremedhin and F. Manne, A
Scalable Parallel Graph Coloring Algorithm for Distributed Memory
Computers, Lecture
Notes in Computer Science, vol 3648 , 2005, pages 241 - 251,Springer.
Proc. of EuroPar 2005, 30 Aug - 2 Sept, 2005, Lisboa, Portugal.
Abstract
Paper in PDF
Shared-memory and coarse-grained multiprocessors
-
A.H. Gebremedhin, F.Manne and T. Woods,
Speeding up Parallel Graph Coloring,
Lecture Notes in Computer Science, vol 3732, pp 1079-1088, 2005,
Springer. Proc. of Para 2004, June 20 - 23, 2004, Lyngby, Denmark.
Abstract
Paper in PDF
-
A. Gebremedhin, I.Guerrin-Lassous, J. Gustedt and J.A. Telle, Graph
Coloring on Coarse Grained Multicomputers, Discrete Applied
Mathematics, Vol 131, No 1, pp 179--198, 2003.
Abstract
Paper in PDF
-
A.H. Gebremedhin, F. Manne and A. Pothen, Parallel Distance-k Coloring
Algorithms for Numerical Optimization, In B. Monien and R. Feldmann
(Eds.): EuroPar 2002, Lecture Notes in Computer Science 2400, pp. 912-921,
Springer-Verlag 2002.
Abstract
Paper in PDF
-
A. Gebremedhin and F. Manne, Scalable Parallel Graph Coloring Algorithms,
Concurrency: Practice and Expereince,
Vol 12, pp1131--1146, 2000.
Abstract
Paper in PDF
-
A.H. Gebremedhin, I.G. Lassous, J. Gustedt and J.A. Telle, Graph Coloring
on a Coarse Grained Multiprocessor,In Brandes, Ulrik, Wagner
and Dorothea (Eds.): WG 2000, Lecture Notes in Computer Science 1928, pp.
184-195, 2000, Springer-Verlag.
Abstract
Paper in PDF
-
A.H. Gebremedhin and F. Manne, Parallel Graph Coloring Algorithms using
OpenMP, In Proc. of EWOMP'99, First European Workshop on OpenMP,
Sept.30 - Oct. 1, 1999, Lund, Sweden.
Abstract
Paper in PDF
Go back to Research Areas or go side-ways to
Network Science
Coloring and Automatic Differentiation
Parallel Computation Models