AF: Small: Shared-Memory Parallel Algorithms: Theory and Practice

AF:小型:共享内存并行算法:理论与实践

基本信息

  • 批准号:
    1910030
  • 负责人:
  • 金额:
    $ 40万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2019
  • 资助国家:
    美国
  • 起止时间:
    2019-07-01 至 2022-06-30
  • 项目状态:
    已结题

项目摘要

With the advent in recent years of multicore processors ranging from fifty dollar hobby kits to multi-million dollar supercomputers, shared-memory parallel algorithms have increasingly significant practical and theoretical relevance. This project is developing new algorithmic approaches and results relevant to today's shared-memory parallel machines. The impact of this project will be felt in applications being able to make better use of the computational power of modern multi-core architectures. The project seeks to develop library implementations of many of these algorithms which will be made available to the public. On the educational side, the project will result in coursework that will help undergraduate students learn about parallel algorithms and their implementation.The project focuses on three areas. The first is research on developing results in a model, the binary forking model, that is more relevant to today's machines than some previous models. In particular the model matches the software platforms that are available on most parallel machines, and supports an asynchronous form of parallelism that are most relevant to the machines they run on. The second area is to better understand the parallelism already available in many sequential algorithms. The goal is to derive algorithms that are simpler and more efficient. The third area is to develop algorithms that allow the user to efficiently make batches of updates to underlying data structures. This is referred to as batch parallel dynamic algorithms, and follows significant prior work on sequential single update dynamic updates. In the binary forking model each task can only fork into two child tasks, but can do so recursively and asynchronously. At present no tight performance bounds for the binary forking model are known even for some basic problems such as sorting and graph connectivity, which this project seeks to remedy. For the thrust on understanding parallelism in sequential algorithms, the project will study the dependencies among sub-computations in iterative sequential algorithms. In the thrust on parallel batched algorithms the project is looking at applying the ideas to graph connectivity and related problems. The goal is to achieve algorithms that are work-efficient relative to the best (or near best) sequential algorithms---and in particular for graph connectivity to achieve O(log^2 n) amortized work per update, while allowing batches of updates.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.
近年来,随着从50美元的业余爱好工具包到数百万美元的超级计算机的多核处理器的出现,共享内存并行算法具有越来越重要的实践和理论意义。该项目正在开发与当今共享内存并行机相关的新算法方法和结果。该项目的影响将在能够更好地利用现代多核架构的计算能力的应用程序中感受到。该项目寻求开发其中许多算法的库实现,并将向公众提供。在教育方面,该项目将产生课程作业,帮助本科生学习并行算法及其实现。该项目集中在三个领域。第一个是对一个模型的开发结果的研究,该模型比以前的一些模型更适合于今天的机器。特别是,该模型与大多数并行机上可用的软件平台相匹配,并支持与它们运行的机器最相关的异步形式的并行性。第二个领域是更好地理解许多顺序算法中已有的并行性。其目标是得出更简单、更有效的算法。第三个领域是开发允许用户高效地对底层数据结构进行批量更新的算法。这被称为批处理并行动态算法,并且遵循在顺序单次更新动态更新方面的大量先前工作。在二进制分叉模型中,每个任务只能分叉成两个子任务,但可以递归和异步地完成。目前还不知道二进制分叉模型的严格性能界限,甚至对于排序和图连接等一些基本问题也是已知的,本项目试图解决这些问题。为了理解顺序算法中的并行性,该项目将研究迭代顺序算法中的子计算之间的依赖关系。在并行批处理算法的推动下,该项目正着眼于将这些想法应用于图的连通性和相关问题。我们的目标是实现相对于最好(或接近最好)的顺序算法而言工作效率更高的算法-特别是对于图形连接性,以实现O(log^2n)次更新的分期工作,同时允许批量更新。该奖项反映了NSF的法定使命,并通过使用基金会的智力优势和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(21)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Parallel Minimum Cuts in O ( m log 2 n ) Work and Low Depth
O ( m log 2 n ) 工作和低深度并行最小切削
Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
Parallel Batch-Dynamic Trees via Change Propagation
通过变更传播的并行批动态树
  • DOI:
    10.4230/lipics.esa.2020.2
  • 发表时间:
    2020
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Umut Acar, Daniel Anderson
  • 通讯作者:
    Umut Acar, Daniel Anderson
Joinable Parallel Balanced Binary Trees
可连接的并行平衡二叉树
Work-Efficient Batch-Incremental Minimum Spanning Trees with Applications to the Sliding-Window Model
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Guy Blelloch其他文献

Guy Blelloch的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Guy Blelloch', 18)}}的其他基金

SHF: Medium: Algorithmic lambda-Calculus for the Design, Analysis, and Implementation of Parallel Algorithms
SHF:Medium:用于并行算法设计、分析和实现的算法 lambda 演算
  • 批准号:
    1901381
  • 财政年份:
    2019
  • 资助金额:
    $ 40万
  • 项目类别:
    Continuing Grant
SPX: Parallel Models and Algorithms for Emerging Memory Systems
SPX:新兴内存系统的并行模型和算法
  • 批准号:
    1919223
  • 财政年份:
    2019
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
XPS: FULL: Bridging Parallel and Queueing-Theoretic Scheduling
XPS:FULL:桥接并行和排队理论调度
  • 批准号:
    1629444
  • 财政年份:
    2016
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
XPS: FULL: FP: Write-Efficient Parallel Algorithms for Emerging Memory Technologies
XPS:FULL:FP:用于新兴内存技术的写高效并行算法
  • 批准号:
    1533858
  • 财政年份:
    2015
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
SHF: AF: Large: Collaborative Research: Parallelism without Concurrency
SHF:AF:大型:协作研究:无并发的并行性
  • 批准号:
    1314590
  • 财政年份:
    2013
  • 资助金额:
    $ 40万
  • 项目类别:
    Continuing Grant
NSF Workshop on Research Directions in the Principles of Parallel Computing
NSF 并行计算原理研究方向研讨会
  • 批准号:
    1242283
  • 财政年份:
    2012
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
SHF: AF: Small: Locality with Dynamic Parallelism
SHF:AF:小:具有动态并行性的局部性
  • 批准号:
    1018188
  • 财政年份:
    2010
  • 资助金额:
    $ 40万
  • 项目类别:
    Continuing Grant
ITR/SY+IM+AP: Center for Applied Algorithms
ITR/SY IM AP:应用算法中心
  • 批准号:
    0122581
  • 财政年份:
    2001
  • 资助金额:
    $ 40万
  • 项目类别:
    Continuing Grant
ITR: Algorithms: From Theory to Application
ITR:算法:从理论到应用
  • 批准号:
    0085982
  • 财政年份:
    2000
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
Advanced Languages for Scientific Computation Environments
科学计算环境的高级语言
  • 批准号:
    9706572
  • 财政年份:
    1997
  • 资助金额:
    $ 40万
  • 项目类别:
    Continuing Grant

相似国自然基金

昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
    n/a
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
  • 批准号:
    32000033
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
  • 批准号:
    81900988
  • 批准年份:
    2019
  • 资助金额:
    21.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

CIF: Small: Shared Information: Theory and Applications
CIF:小:共享信息:理论与应用
  • 批准号:
    2310203
  • 财政年份:
    2023
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
Alternate splicing as a source of shared neoantigens in a non-small cell lung cancer
替代剪接作为非小细胞肺癌共享新抗原的来源
  • 批准号:
    10750090
  • 财政年份:
    2023
  • 资助金额:
    $ 40万
  • 项目类别:
SHF: Small: CT-DDS -- Scalable Concolic Testing of Parallel Applications With Shared Dynamic Data Structures
SHF:小型:CT-DDS——具有共享动态数据结构的并行应用程序的可扩展 Concolic 测试
  • 批准号:
    2226448
  • 财政年份:
    2022
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
Design of Mobility Intelligence for Small Mobility in Shared Space
共享空间小型移动出行智能设计
  • 批准号:
    22H00211
  • 财政年份:
    2022
  • 资助金额:
    $ 40万
  • 项目类别:
    Grant-in-Aid for Scientific Research (A)
CNS Core: Small: Secured Spectrum Allocation and Patrolling in Shared Spectrum Systems
CNS 核心:小型:共享频谱系统中的安全频谱分配和巡逻
  • 批准号:
    2128187
  • 财政年份:
    2021
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
CHS: Small: Collaborative Research: Shared Mobility Systems to Address Transportation Barriers of Underserved Urban and Rural Communities
CHS:小型:合作研究:共享出行系统,解决服务不足的城乡社区的交通障碍
  • 批准号:
    1910281
  • 财政年份:
    2020
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
Collaborative Research: SWIFT: SMALL: Learning-Efficient Spectrum Access for No-Sensing Devices in Shared Spectrum
合作研究:SWIFT:SMALL:共享频谱中无感知设备的学习高效频谱访问
  • 批准号:
    2030026
  • 财政年份:
    2020
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
Collaborative Research: SWIFT: SMALL: Learning-Efficient Spectrum Access for No-Sensing Devices in Shared Spectrum
合作研究:SWIFT:SMALL:共享频谱中无感知设备的学习高效频谱访问
  • 批准号:
    2029978
  • 财政年份:
    2020
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
CHS: Small: Collaborative Research: Shared Mobility Systems to Address Transportation Barriers of Underserved Urban and Rural Communities
CHS:小型:合作研究:共享出行系统,解决服务不足的城乡社区的交通障碍
  • 批准号:
    1909700
  • 财政年份:
    2020
  • 资助金额:
    $ 40万
  • 项目类别:
    Continuing Grant
CHS: Small: A data-driven computational model of dyadic rapport: Learning and transforming nonverbal behavior in shared virtual environments.
CHS:小型:数据驱动的二元关系计算模型:在共享虚拟环境中学习和转变非语言行为。
  • 批准号:
    1907807
  • 财政年份:
    2019
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了