AF: Small: Toward A Unified Model of Parallelism And Locality

点击翻译按钮获取中文摘要

The project will study the challenges and limitations of combining parallelism and locality in algorithm design for modern many-core architectures. With data transfer being one of the primary bottlenecks in modern high-performance computing (HPC), parallel algorithms with better locality will result in more efficient utilization of the HPC resources, resulting in faster and more energy-efficient implementations. The applied aspect of the project will produce a collection of software libraries that can be used by modern HPC practitioners. The techniques discovered and developed during this project will be incorporated into the CS courses at the University of Hawaii, to educate future generation of students in more efficient techniques for modern parallel computing.The current large number of parallel, distributed and I/O-efficient models of computation, which capture the challenges of utilizing parallelism and locality, is confusing for both theoreticians and practitioners alike. This project will investigate the relationship between all of these models and the possibility of using the Parallel External Memory (PEM) model as a unifying model combining parallelism and locality. The results of this research will expand our collective understanding of the power and limitation of various existing models, answering the question why some fundamental problems are easy in some models, yet are hard in others.The project will develop a number of fully-scalable PEM algorithms, while identifying problems that don't admit full scalability. It will produce a number of new algorithmic techniques for combining parallelism and locality. The experimental aspect of the project will validate the performance and scalability of the produced algorithms by implementing them as software libraries. These libraries will be made publicly available in the form of open-source software.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.