Parallel Computing

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 we 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 Assefaw’s earlier work in this direction focused on distributed-memory platforms. His more recent effort targets the emerging and rapidly growing multicore platforms as well as massively multithreaded platforms. The list also includes his recent works on other combinatorial problems than graph problems and on problems around matrix computations. At SCADS, we are 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 we developed together with colleagues are publicly available via the Zoltan software toolkit of Sandia National Laboratories.

Papers

Distributed memory architectures
Multi-core and multi-threaded architectures
Shared memory architectures

Distributed-memory architectures 

  • S. Ghosh, M. Halappanavar, A. Kalyanaraman and A.H. Gebremedhin. Exploring MPI Communication Models for Graph Applications Using Graph Matching as a Case Study, IEEE International Parallel and Distributed Processing Symposium (IPDPS 2019).
  • S. Ghosh, M. Halappanavar, A. Tumeo, A. Kalyanaraman and A.H. Gebremedhin. miniVite: A graph Analytics Benchmarking Tool for Massively Parallel Systems, IEEE International Workshop on Performance Modeling, Benchmarking and Simulation (PMBS’18), held in conjunction with ACM/IEEE Supercomputing (SC’18).
  • Sayan Ghosh, Mahantesh Halappanavar, Antonino Tumeo, Ananth Kalyanaraman and Assefaw H. Gebremedhin. Scalable Distributed Memory Community Detection using Vite. 2018 IEEE High Performance Extreme Computing Conference (HPEC’18).
  • S. Ghosh, M. Halappanavar, A. Tumeo, A. Kalyanaraman, H. Lu, D. Chavarria-Miranda, A. Khan and A. H. Gebremedhin, Distributed Louvain Algorithm for Graph Community Detection, IEEE International Parallel and Distributed Processing Symposium (IPDPS 2018). Abstract     Paper in PDF
  • S. Ghosh, J.R. Hammond, A.J. Pena, P. Balaji, A.H. Gebremedhin and B. Chapman, One-sided Interface for Matrix Operations using MPI-3 RMA: A Case Study with Elemental , Proceedings of International Conference on Parallel Processing (ICPP 2016), to appear. 
    Abstract     Paper in PDF
  • 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

Multi-core and multi-threaded architectures

  • H.Lu, M. Halappanavar, D. Chavarri-a-Miranda, A.H. Gebremedhin, A. Panyala and A. Kalyanaraman, Algorithms for Balanced Graph Colorings with Applications in Parallel Computing, IEEE Transactions on Parallel and Distributed Systems 28(5), 1240–1256, 2017.
    Abstract     Paper in PDF
  • S. Ghosh and A.H. Gebremedhin Parallelization of Bin Packing on Multicore Systems, 2016 IEEE International Conference on High Performance Computing, Data, and Analytics (HiPC’16).
    Abstract     Paper in PDF
  • R.A. Rossi, D.F. Gleich, A.H. Gebremedhin, Parallel Maximum Clique Algorithms with Applications to Network Analysis , SIAM Journal on Scientific Computing, Vol 37, Issue 5, pages C589-C618, 2015.
    Abstract    Paper in PDF
  • 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

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