Search NASA⌕ Search

Engineering topics

Kalyanaraman, Ananth

Publications and source records attributed to Kalyanaraman, Ananth.

Towards scaling community detection on distributed-memory heterogeneous systems

Distributed multi-GPU systems pose significant challenges and opportunities for efficient execution of parallel applications. Graph algorithms are generally characterized by irregular memory accesses, low computation to communication ratios, and load balancing problems that are especially hard to address on multi-GPU systems. Graph community detection is an important problem in the emerging domain of graph analytics with numerous applications. In this paper, we present our ongoing work on distributed-memory multi-GPU implementation for graph community detection. Our work parallelizes the widely used (albeit serial) Louvain method on distributed multi-GPU platforms. Supported by an extensive set of experiments on a multi-GPU enabled supercomputer (OLCF Summit) and a single compute node (Nvidia DGX-2®), we demonstrate competitive performance to existing distributed-memory CPU-based implementation, and up to 6.5 better results than Nvidia RAPIDS® CUGRAPH. To the best of our knowledge, this work represents the first effort for community detection on distributed multi-GPU systems. Our approach and related findings can be extended to numerous other iterative graph algorithms on multi-GPU systems.

97 MATHEMATICS AND COMPUTING↗

Single-node Partitioned-Memory for Huge Graph Analytics: Cost and Performance Trade-offs

Nonvolatile memory NVDIMMs, available as Intel Optane, are less expensive than DRAM and bring large byte-addressable storage within reach to many applications. Evaluations on graph analytics have shown promising performance only when DRAM is used as a hardware cache (Memory mode). An open question is whether graph applications can exploit Optane and DRAM directly (AppDirect mode) and achieving better-than-DRAM average bandwidth and run times. We evaluate Optane as a volatile pool on two large-scale graph applications with very different computational patterns, Grappolo and Ripples. We show that AppDirect mode can deliver better-than-DRAM performance, by allocating data structures to Optane and DRAM according to their access characteristics, resulting in higher average memory bandwidth and lower average latency. Memory mode provides DRAM-competitive performance with capacity equal to persistent memory. We demonstrate occasional 4x improvement using the latest AppDirect option and frequently observe competitive performance between Optane AppDirect Memory modes and DRAM.

Ghosh, Sayan↗

EXAGRAPH: Graph and combinatorial methods for enabling exascale applications

Combinatorial algorithms in general and graph algorithms in particular play a critical enabling role in numerous scientific applications. However, the irregular memory access nature of these algorithms makes them one of the hardest algorithmic kernels to implement on parallel systems. With tens of billions of hardware threads and deep memory hierarchies, the exascale computing systems in particular pose extreme challenges in scaling graph algorithms. The codesign center on combinatorial algorithms, ExaGraph, was established to design and develop methods and techniques for efficient implementation of key combinatorial (graph) algorithms chosen from a diverse set of exascale applications. Algebraic and combinatorial methods have a complementary role in the advancement of computational science and engineering, including playing an enabling role on each other. In this paper, we survey the algorithmic and software development activities performed under the auspices of ExaGraph from both a combinatorial and an algebraic perspective. In particular, we detail our recent efforts in porting the algorithms to manycore accelerator (GPU) architectures. We also provide a brief survey of the applications that have benefited from the scalable implementations of different combinatorial algorithms to enable scientific discovery at scale. We believe that several applications will benefit from the algorithmic and software tools developed by the ExaGraph team.

97 MATHEMATICS AND COMPUTING↗

pnnl/pakman

PaKman: A Scalable Algorithm for Generating Genomic Contigs on Distributed Memory Machines. PaKman presents a fully distributed method that tackles assembly of large genomes through the combinationof a novel data-structure (PaK-Graph) and algorithmic strategies to simplify communication and I/O footprint during the assembly process.

Ghosh, Priyanka↗

NoC-enabled Software/Hardware Co-Design Framework for Accelerating k-mer Counting

Counting k-mers (substrings of fixed length k) in DNA and protein sequences generate non-uniform and irregular memory access patterns. Processing-in-Memory (PIM) architectures have potential to significantly reduce the overheads associated with such frequent and irregular memory accesses. However, existing k-mer counting algorithms are not designed to exploit the advantages of PIM architectures. Furthermore, owing to thermal constraints, the allowable power budget is limited in conventional PIM designs. Moreover, k-mer counting generates long-range, non-uniform traffic patterns which needs to be handled by an efficient Network-on-Chip (NoC). In this paper, we present an NoC-enabled hardware/software co-design framework to implement high-performance k-mer counting. The proposed architecture enables more computational power, efficient communication between cores/memory – all without creating a thermal bottleneck. The software component overcomes the I/O bottleneck, aids in NoC design and exposes more in-memory opportunities to exploit in PIM. Experimental results show that the proposed architecture outperforms a state-of-the-art software implementation using Hybrid Memory Cube (HMC), by up to 7.14X, while allowing significantly higher power budget.

Joardar, Biresh K.↗

Scaling and Quality of Modularity Optimization Methods for Graph Clustering

Real-world graphs exhibit structures known as “communities” or “clusters” consisting of a group of vertices with relatively high connectivity between them, as compared to the rest of the vertices in the network. Graph clustering or community detection is a fundamental graph operation used to analyze real-world graphs occurring in the areas of computational biology, cybersecurity, electrical grids, etc. Similar to other graph algorithms, owing to irregular memory accesses and inherently sequential nature, current algorithms for community detection are challenging to parallelize. However, in order to analyze large networks, it is important to develop scalable parallel implementations of graph clustering that are capable of exploiting the architectural features of modern supercomputers. In response to the 2019 Streaming Graph Challenge, we present quality and performance analysis of our distributed- memory community detection using Vite, which is our distributed memory implementation of the popular Louvain method, on the ALCF Theta supercomputer. Clustering methods such as Louvain that rely on modularity maximization are known to suffer from the resolution limit problem, preventing identification of clusters of certain sizes. Hence, we also include quality analysis of our shared-memory implementation of the Fast-tracking Resistance method, in comparison with Louvain on the challenge datasets. Furthermore, we introduce an edge-balanced graph distribution for our distributed memory implementation, that significantly reduces communication, offering up to 80% improvement in the overall execution time. In addition to performance/quality analysis, we also include details on the power/energy consumption, and memory traffic of the distributed-memory clustering implementation using real-world graphs with over a billion edges.

Ghosh, Sayan↗

Fast and Scalable Implementations of Influence Maximization Algorithms

The Influence Maximization problem has been extensively studied in the past decade because of its practical applications in finding the key influencers in social networks. Due to the hardness of the underlying problem, existing algorithms have tried to trade off practical efficiency with approximation guarantees. However, even such approximate solutions take several hours of compute time on modest sized real world inputs. On the other hand, there is a lack of effective parallel and distributed algorithms to solve this problem. In this paper, we present efficient parallel algorithms for multithreaded and distributed systems to solve the influence maximization with approximation guarantee. Our algorithms extend state-of-the-art sequential approach based on computing reverse reachability sets. We present a detailed experimental evaluation, and analyze their performance and their sensitivity to input parameters, using real world inputs. Our experimental results demonstrate significant speedup on parallel architectures. We further show a speedup of up to 586X relative to the state-of-the-art sequential baseline using 1024 nodes of a supercomputer at far greater accuracy and twice the seed set size. To the best of our knowledge, this is the first effort in parallelizing the influence maximization operation at scale.

Minutoli, Marco↗

CisSERS: Customizable In Silico Sequence Evaluation for Restriction Sites

High-throughput sequencing continues to produce an immense volume of information that is processed and assembled into mature sequence data. Here, data analysis tools are urgently needed that leverage the embedded DNA sequence polymorphisms and consequent changes to restriction sites or sequence motifs in a high-throughput manner to enable biological experimentation. Cis SERS was developed as a standalone open source tool to analyze sequence datasets and provide biologists with individual or comparative genome organization information in terms of presence and frequency of patterns or motifs such as restriction enzymes. Predicted agarose gel visualization of the custom analyses results was also integrated to enhance the usefulness of the software. Cis SERS offers several novel functionalities, such as handling of large and multiple datasets in parallel, multiple restriction enzyme site detection and custom motif detection features, which are seamlessly integrated with real time agarose gel visualization. Using a simple fasta-formatted file as input, Cis SERS utilizes the REBASE enzyme database. Results from Cis SERSenable the user to make decisions for designing genotyping by sequencing experiments, reduced representation sequencing, 3’UTR sequencing, and cleaved amplified polymorphic sequence (CAPS) molecular markers for large sample sets. Cis SERS is a java based graphical user interface built around a perl backbone. Several of the applications of Cis SERS including CAPS molecular marker development were successfully validated using wet-lab experimentation. Here, we present the tool Cis SERSand results from in-silico and corresponding wet-lab analyses demonstrating that Cis SERS is a technology platform solution that facilitates efficient data utilization in genomics and genetics studies.

59 BASIC BIOLOGICAL SCIENCES↗

Biological and Environmental Research Exascale Requirements Review. An Office of Science review sponsored jointly by Advanced Scientific Computing Research and Biological and Environmental Research, March 28-31, 2016, Rockville, Maryland

Understanding the fundamentals of genomic systems or the processes governing impactful weather patterns are examples of the types of simulation and modeling performed on the most advanced computing resources in America. High-performance computing and computational science together provide a necessary platform for the mission science conducted by the Biological and Environmental Research (BER) office at the U.S. Department of Energy (DOE). This report reviews BER’s computing needs and their importance for solving some of the toughest problems in BER’s portfolio. BER’s impact on science has been transformative. Mapping the human genome, including the U.S.-supported international Human Genome Project that DOE began in 1987, initiated the era of modern biotechnology and genomics-based systems biology. And since the 1950s, BER has been a core contributor to atmospheric, environmental, and climate science research, beginning with atmospheric circulation studies that were the forerunners of modern Earth system models (ESMs) and by pioneering the implementation of climate codes onto high-performance computers. See http://exascaleage.org/ber/ for more information.

54 ENVIRONMENTAL SCIENCES↗

BioEarth: Envisioning and developing a new regional earth system model to inform natural and agricultural resource management

As managers of agricultural and natural resources are confronted with uncertainties in global change impacts, the complexities associated with the interconnected cycling of nitrogen, carbon, and water present daunting management challenges. Existing models provide detailed information on specific sub-systems (land, air, water, economics, etc). An increasing awareness of the unintended consequences of management decisions resulting from interconnectedness of these sub-systems, however, necessitates coupled regional earth system models (EaSMs). Decision makers’ needs and priorities can be integrated into the model design and development processes to enhance decision-making relevance and "usability" of EaSMs. BioEarth is a current research initiative with a focus on the U.S. Pacific Northwest region that explores the coupling of multiple stand-alone EaSMs to generate usable information for resource decision-making. Direct engagement between model developers and non-academic stakeholders involved in resource and environmental management decisions throughout the model development process is a critical component of this effort. BioEarth utilizes a "bottom-up" approach, upscaling a catchment-scale model to basin and regional scales, as opposed to the "top-down" approach of downscaling global models utilized by most other EaSM efforts. This paper describes the BioEarth initiative and highlights opportunities and challenges associated with coupling multiple stand-alone models to generate usable information for agricultural and natural resource decision-making.

agricultural↗