Parallel algorithms for clustering biological graphs on distributed and shared memory architectures. (1st January 2014)

• Record Type: Journal Article
• Authors: Rytsareva, Inna; Chapman, Timothy; Kalyanaraman, Ananth
• Is Part Of: International journal of high performance computing and networking. Volume 7:Number 4(2014)
• Page Start: 241
• Page End: 257
• Publication Date: 2014-01-01
• Subjects: graph clustering -- shared memory OpenMP algorithm -- MapReduce algorithm -- hash tables -- union-find data structure -- Shingling heuristic -- protein family identification -- protein domain family; High performance computing -- Periodicals; Computer networks -- Periodicals; High performance computing; Periodicals; 004.05
• Languages: English
• ISSNs: 1740-0562

Abstract

Graph algorithms on parallel architectures present an interesting case study for irregular applications. In this paper, we address one such irregular application – one of clustering real-world graphs constructed out of biological data using parallel computers. We present the design and evaluation of two different parallel implementations of a serial graph clustering heuristic called the Shingling heuristic, which was developed by Gibson et al. In the OpenMP shared memory implementation pClust-sm, we were able to improve both the asymptotic runtime and memory complexities of the serial implementation, and drastically reduce the time to solution from the order of several days to a few minutes on larger inputs (~100 M edges). With the Hadoop MapReduce implementation pClust-mr, we were able to demonstrate linear scaling up to 64 cores on modest sized inputs (~11 M edges) and enhance the problem size reach by about two orders of magnitude relative to a serial implementation.