AF: Small: Theoretical Frameworks for Modern Parallel Computing Environments

University Of Texas At Austin, Austin TX

Investigators

Abstract

A dominant feature of computing today is that parallelism is present in virtually all computing environments, from laptops and desktops to supercomputers. The proposed research will address foundational issues that explore the power of parallelism as well as methods to harness its potential with maximum efficiency. This research has two main components: (1) It will revisit classical complexity theory developed for parallel computing to address new issues of speed-up efficiency, communication costs, and the diversity of parallel architectures, especially the challenges present in moving between shared-memory and distributed-memory environments. (2) It will develop efficient and portable multicore algorithms for many fundamental graph-theoretic problems as well as efficient run-time schedulers, caching and cache replacement strategies, and strategies for dealing with false sharing, an inevitable consequence of the shared-memory environment in a parallel setting that is found in multicores. It will also investigate models and algorithms for supercomputing environments configured as networks of multicores, and for GPU (graphics processing unit) computing. Over the past several decades theoretical computer science has made many fundamental advances in our understanding of parallelism. The project aims to expand the scope of traditional complexity theory to bring communication costs and other key parameters in parallel computation into the fold of complexity theory. It proposes to develop new efficient and portable algorithms for multicores, which are of major importance in the current times, as parallelism enters mainstream computation.