Candidate Name: Abdullah Al Raqibul Islam
Program: Computing
Committee Chairs: Dr. Dong Dai
Committee Members: Dr. Yonghong Yan, Dr. Erik Saule, Dr. Pu Wang, Dr. Weichao Wang
Abstract:

Efficient storage layout and representation of sparse data remain a fundamental challenge for high-performance computing (HPC) applications. This research tackles this challenge in two key domains: dynamic graph storage and sparse matrix computations, through the design of novel storage abstractions.

In the first domain, graph-structured data is ubiquitous in areas like biology, social networks, and recommendation systems. As real-world graphs evolve continuously, dynamic updates must be supported alongside efficient analytics. Classical storage formats such as Compressed Sparse Row (CSR), adjacency lists, and edge lists, as well as more recently PMA-based extensions (e.g., VCSR, PCSR) have shown promise in making balance on both sides. This research explores this data structure design on emerging memory technologies, i.e., Persistent memory (PM). PM devices (such as Intel Optane) offer an appealing blend of large capacity, byte-addressability, and data persistence. This research proposes DGAP, a framework that unifies graph storage and computation on PM to exploit its low-latency, high-bandwidth characteristics. DGAP builds upon a single mutable-CSR data structure augmented with PM-optimized designs--including a per-section append-only edge log, per-thread undo logging for crash consistency, and intelligent data placement to minimize in-place writes. These techniques drastically reduce write amplification and overheads of ensuring persistence. Extensive evaluations show that DGAP outperforms state-of-the-art dynamic graph systems, achieving up to 3.2× faster updates and 3.77× faster analytics on persistent memory. This demonstrates the efficacy of co-designing data structures with novel memory hardware to meet the demands of data-intensive graph applications.

In the second domain, I investigate Sparse General Matrix–Matrix Multiplication (SpGEMM), a core kernel in scientific computing and data analytics. SpGEMM performance is often bottlenecked by irregular memory access patterns, particularly when accessing the second input matrix. To improve data reuse and cache efficiency, this research introduces a cluster-wise SpGEMM algorithm that groups structurally similar rows of the first input matrix (A) and processes them together, thereby achieving more cache-efficient access to the second matrix (B). This approach is supported by a new row-clustered CSR format (CSR\_Cluster), which enhances spatial locality and reduces memory traffic. Experimental evaluations demonstrate consistent performance improvements, with average speedups of 1.39× over conventional approaches.

Taken together, this research establishes a unified perspective on how data-structure design and storage abstractions shape the efficiency of sparse computations in HPC. Beyond these domains, the results suggest broader implications for storage-aware design at multiple levels of the computing stack, from in-memory binary layouts to file-based representations in large-scale scientific workflows.