CAREER: A Scalable, Polymorphic, and Efficient Architecture for Irregular and Sparse Computations (APEX)

Specialized architectures have emerged as a prevailing solution to meet escalating computation demands in the post-Moore era. However, accelerating sparse and irregular computations remains a formidable challenge due to unstructured data. Such irregular and sparse data patterns are prevalent in numerous application domains, such as machine learning, data analytics, and scientific computing. While exploiting sparsity is essential in reducing storage and computation requirements, it poses challenges to current and future computing systems including amorphous parallelism, unpredictable memory access, and irregular communication patterns. This project addresses these challenges by leveraging graph theory to explore untapped optimization opportunities across different aspects of sparse computations, including architecture, theory, and algorithm. All research findings and simulation toolkits will be disseminated to the community through conference and journal publications, professional meetings, and a dedicated website. Beyond the technical contributions, the research will also play a major role in education by integrating discovery with teaching and training. The project aims to design a transformative computing framework for a wide range of irregular and sparse applications, emphasizing improved parallelism, data locality, and communication. The key idea is to (1) abstract sparse computations using novel graph representations, and (2) utilize graph theory to construct regular and predictive data and computation patterns optimized for parallel processing. This research will result in (1) novel graph formulations and analytical tools for sparse computations to reveal hidden parallelism and data reuse opportunities, (2) a set of well-developed graph algorithms that can exploit amorphous parallelism and structured communication patterns for complex sparse applications towards improved system scalability, (3) polymorphic accelerator architectures that can dynamically adapt to various sparse computation and communication demands, and (4) proof-of-concept and open-source tools that will expand and enhance the research capabilities of the computer architecture community in this critical area. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.