AF: Small: Theoretical Frameworks for Modern Parallel Computing Environments

AF：小型：现代并行计算环境的理论框架

• 批准号: 1320675
• 负责人: Vijaya Ramachandran
• 金额: $ 40万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1320675&HistoricalAwards=false
• 关键词: AF; Small; Theoretical; Frameworks; Modern

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.

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