AF: Small: Theoretical Frameworks for Modern Parallel Computing Environments

当今计算的一个主要特征是并行性存在于几乎所有的计算环境中，从笔记本电脑和台式机到超级计算机。拟议的研究将解决探索并行的力量以及以最大效率利用其潜力的方法的基础问题。这项研究有两个主要组成部分：（1）它将重新审视经典的复杂性理论开发的并行计算，以解决新的问题的加速效率，通信成本，和并行架构的多样性，特别是在共享内存和分布式内存环境之间的移动所面临的挑战。(2)它将为许多基本的图论问题开发高效和可移植的多核算法，以及高效的运行时缓存，缓存和缓存替换策略，以及处理错误共享的策略，这是多核中并行设置中共享内存环境的必然结果。它还将研究配置为多核网络的超级计算环境和GPU（图形处理单元）计算的模型和算法。在过去的几十年里，理论计算机科学在我们对并行性的理解方面取得了许多根本性的进展。该项目旨在扩展传统复杂性理论的范围，将并行计算中的通信成本和其他关键参数纳入复杂性理论。它提出了开发新的高效和便携式算法的多核，这是非常重要的，在当今时代，并行进入主流计算。

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.