SHF: Small: K-Way Speculation for Mapping Applications with Dependencies on Modern HPC Systems

SHF:小型:依赖于现代 HPC 系统的地图应用程序的 K-Way 推测

基本信息

  • 批准号:
    2007793
  • 负责人:
  • 金额:
    $ 50万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2020
  • 资助国家:
    美国
  • 起止时间:
    2020-08-01 至 2023-07-31
  • 项目状态:
    已结题

项目摘要

Modern hardware provides parallelism in the form of a large number of threads. If an application involves independent work components, these components can be mapped to such hardware for parallel execution. However, when the work components are not independent, often such hardware is under-utilized. One technique used to overcome this problem is speculation – which involves guessing certain values or outcomes and assigning work to threads based on them. If the guess turns out to be incorrect, we need to re-execute the work. In current approaches one value or outcome is considered (or speculated): i.e., whether a specific value will be computed or loaded, or whether there will be dependence or not. With presence of massive number of threads, there is an opportunity to consider k-way speculation, e.g., speculating two or more likely values, or in parallel executing one thread that assumes dependence and another that assumes there is no dependence. This project is developing techniques enabling k-way speculation, using k guessed values to benefit from parallelism provided by modern hardware with multiple threads. The motivation arrives from the fact that modern hardware has a very high degree of parallelism, and it is better to have redundancy in using this parallelism, as compared to settling for a sequential execution. The class of applications this project targets span across scientific computing, data analytics, machine learning, and optimization, and thus this project impacts all of these areas. This project will also make contributions towards advancing curriculum and broadening participation in computing. This project builds on two demonstrated results relevant to k-way speculation. First, in certain cases, one might speculate k values, and while none of them may be correct, execution using them can be used to reconstruct the function. Second, for Finite State Machines (FSMs), it has been shown that k-way speculation is a better alternative to both (1-way) speculation and enumeration. Both approaches, k-way speculation and reconstruction and k-way speculation for FSMs, are not scalable to a very large number of cores because of the overhead of merging across different speculated executions. In addition, existing loop-transformation methods respect dependencies and cannot identify and exploit loops that can be parallelized despite dependencies. The following research directions are explored. First, techniques are being developed to remove this bottleneck. Second, the existing framework is being extended to consider nested loops, where one of the levels involves dependencies. Third, several classes of algorithms involve speculation and are candidates for benefiting from k-way speculation, possibly with reconstruction, and this is being explored. Finally, it is being examined if the function corresponding to the loop body does not have a closed-form combination, can the execution on speculated values nevertheless represent the function to a certain level of precision.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.
现代硬件以大量线程的形式提供并行性。如果应用程序涉及独立的工作组件,则可以将这些组件映射到此类硬件以进行并行执行。然而,当工作组件不是独立的时,通常这样的硬件未被充分利用。用来克服这个问题的一种技术是推测,它涉及猜测某些值或结果,并根据它们将工作分配给线程。如果猜测结果是不正确的,我们需要重新执行工作。 在当前的方法中,考虑(或推测)一个值或结果:即,是否将计算或加载特定值,或者是否存在依赖性。在存在大量线程的情况下,有机会考虑k路推测,例如,推测两个或更多可能的值,或者并行执行一个假设依赖性的线程和另一个假设不存在依赖性的线程。该项目正在开发技术,使k路推测,使用k猜测值,以受益于现代硬件提供的并行多线程。 动机来自于现代硬件具有非常高的并行度的事实,并且与满足于顺序执行相比,在使用这种并行性时具有冗余更好。该项目针对的应用程序类别涵盖科学计算、数据分析、机器学习和优化,因此该项目会影响所有这些领域。该项目还将为推进计算机课程和扩大参与做出贡献。 这个项目建立在两个已证明的结果相关的k路投机。 首先,在某些情况下,人们可能会推测k值,虽然它们都不正确,但使用它们的执行可以用来重建函数。 其次,对于有限状态机(FSM),已经表明k路推测是(1路)推测和枚举的更好替代方案。这两种方法,k路推测和重构以及FSM的k路推测,由于跨不同推测执行的合并的开销,不能扩展到非常大量的核。此外,现有的循环转换方法尊重依赖性,并且不能识别和利用尽管依赖性但可以并行化的循环。探索了以下研究方向。首先,正在开发技术来消除这一瓶颈。第二,现有的框架正在扩展,以考虑嵌套循环,其中一个级别涉及依赖关系。第三,几类算法涉及推测,并且是从k路推测中受益的候选者,可能具有重建,并且这正在被探索。最后,如果对应于循环体的功能没有一个封闭形式的组合,则正在检查对推测值的执行是否仍然能够在一定程度上代表该功能。该奖项反映了NSF的法定使命,并通过使用基金会的智力价值和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(5)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
A Programming API Implementation for Secure Data Analytics Applications with Homomorphic Encryption on GPUs
GPU 上采用同态加密的安全数据分析应用程序编程 API 实现
  • DOI:
    10.1109/hipc53243.2021.00059
  • 发表时间:
    2021
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Lou, Shuangsheng;Agrawal, Gagan
  • 通讯作者:
    Agrawal, Gagan
Shrinking Sample Search Algorithm for Automatic Tuning of GPU Kernels
用于自动调整 GPU 内核的收缩样本搜索算法
  • DOI:
    10.1109/hipc53243.2021.00040
  • 发表时间:
    2021
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Li, Xiang;Agrawal, Gagan
  • 通讯作者:
    Agrawal, Gagan
Scaling Sparse Matrix Multiplication on CPU-GPU Nodes
在 CPU-GPU 节点上扩展稀疏矩阵乘法
End-to-End LU Factorization of Large Matrices on GPUs
{{ 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 }}

Gagan Agrawal其他文献

MMIS-07, 08: Mining Multiple Information Sources Workshop Report
MMIS-07, 08:挖掘多信息源研讨会报告
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
    朱兴全;Gagan Agrawal;Yuri Breitbart;Ruoming Jin
  • 通讯作者:
    Ruoming Jin
Middleware for data mining applications on clusters and grids
  • DOI:
    10.1016/j.jpdc.2007.06.007
  • 发表时间:
    2008-01-01
  • 期刊:
  • 影响因子:
  • 作者:
    Leonid Glimcher;Ruoming Jin;Gagan Agrawal
  • 通讯作者:
    Gagan Agrawal
<strong>POSTER:</strong> MDS-044 Cancer Disparities in Survival of Patients With Hematologic Malignancies in the Context of Social Determinants of Health: A Systematic Review
  • DOI:
    10.1016/s2152-2650(23)00577-3
  • 发表时间:
    2023-09-01
  • 期刊:
  • 影响因子:
  • 作者:
    Marisol Miranda-Galvis;Kellen Tjioe;Andrew Balas;Gagan Agrawal;Jorge Cortes
  • 通讯作者:
    Jorge Cortes
Organizing Records for Retrieval in Multi-Dimensional Range Searchable Encryption
多维范围可搜索加密中组织检索记录
  • DOI:
  • 发表时间:
    2024
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Mahdieh Heidaripour;Ladan Kian;Maryam Rezapour;Mark Holcomb;Benjamin Fuller;Gagan Agrawal;Hoda Maleki
  • 通讯作者:
    Hoda Maleki
The interaction between social determinants of health and cervical cancer survival: A systematic review
健康的社会决定因素与宫颈癌生存之间的相互作用:系统评价
  • DOI:
    10.1016/j.ygyno.2023.12.020
  • 发表时间:
    2024-02-01
  • 期刊:
  • 影响因子:
    4.100
  • 作者:
    Kellen Cristine Tjioe;Marisol Miranda-Galvis;Marian Symmes Johnson;Gagan Agrawal;E. Andrew Balas;Jorge E. Cortes
  • 通讯作者:
    Jorge E. Cortes

Gagan Agrawal的其他文献

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

{{ truncateString('Gagan Agrawal', 18)}}的其他基金

Collaborative Research: CNS Core: Small: A Compilation System for Mapping Deep Learning Models to Tensorized Instructions (DELITE)
合作研究:CNS Core:Small:将深度学习模型映射到张量化指令的编译系统(DELITE)
  • 批准号:
    2230945
  • 财政年份:
    2023
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
Collaborative Research: CNS Core: Small: A Compilation System for Mapping Deep Learning Models to Tensorized Instructions (DELITE)
合作研究:CNS Core:Small:将深度学习模型映射到张量化指令的编译系统(DELITE)
  • 批准号:
    2341378
  • 财政年份:
    2023
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
OAC Core: SHF: SMALL: ICURE -- In-situ Analytics with Compressed or Summary Representations for Extreme-Scale Architectures
OAC 核心:SHF:SMALL:ICURE——针对超大规模架构的压缩或摘要表示的原位分析
  • 批准号:
    2333899
  • 财政年份:
    2023
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
SHF: Small: K-Way Speculation for Mapping Applications with Dependencies on Modern HPC Systems
SHF:小型:依赖现代 HPC 系统的地图应用程序的 K-Way 推测
  • 批准号:
    2334273
  • 财政年份:
    2023
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
Collaborative Research: SHF:SMALL: Compile-Parallelize-Schedule-Retarget-Repeat (EASER) Paradigm for Dealing with Extreme Heterogeneity
合作研究:SHF:SMALL:处理极端异构性的编译-并行化-调度-重定向-重复 (EASER) 范式
  • 批准号:
    2333895
  • 财政年份:
    2023
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
Collaborative Research: SHF:SMALL: Compile-Parallelize-Schedule-Retarget-Repeat (EASER) Paradigm for Dealing with Extreme Heterogeneity
合作研究:SHF:SMALL:处理极端异构性的编译-并行化-调度-重定向-重复 (EASER) 范式
  • 批准号:
    2146852
  • 财政年份:
    2022
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
OAC Core: SHF: SMALL: ICURE -- In-situ Analytics with Compressed or Summary Representations for Extreme-Scale Architectures
OAC 核心:SHF:SMALL:ICURE——针对超大规模架构的压缩或摘要表示的原位分析
  • 批准号:
    2007775
  • 财政年份:
    2020
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
OAC Core: SHF: SMALL: ICURE -- In-situ Analytics with Compressed or Summary Representations for Extreme-Scale Architectures
OAC 核心:SHF:SMALL:ICURE——针对超大规模架构的压缩或摘要表示的原位分析
  • 批准号:
    2034850
  • 财政年份:
    2020
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
II-New: Infrastructure for Energy-Aware High Performance Computing (HPC) and Data Analytics on Heterogeneous Systems
II-新:异构系统上的能源感知高性能计算 (HPC) 和数据分析基础设施
  • 批准号:
    1513120
  • 财政年份:
    2015
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
SI2-SSE: Collaborative Research: Software Elements for Transfer and Analysis of Large-Scale Scientific Data
SI2-SSE:协作研究:用于大规模科学数据传输和分析的软件元素
  • 批准号:
    1339757
  • 财政年份:
    2013
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard 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 万元
  • 项目类别:
    重大研究计划

相似海外基金

SHF: Small: K-Way Speculation for Mapping Applications with Dependencies on Modern HPC Systems
SHF:小型:依赖现代 HPC 系统的地图应用程序的 K-Way 推测
  • 批准号:
    2334273
  • 财政年份:
    2023
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
Probing planet atmospheres and finding small planets nearby: paving the way for detecting life elsewhere
探测行星大气层并寻找附近的小行星:为探测其他地方的生命铺平道路
  • 批准号:
    RGPIN-2018-05814
  • 财政年份:
    2022
  • 资助金额:
    $ 50万
  • 项目类别:
    Discovery Grants Program - Individual
Probing planet atmospheres and finding small planets nearby: paving the way for detecting life elsewhere
探测行星大气层并寻找附近的小行星:为探测其他地方的生命铺平道路
  • 批准号:
    RGPIN-2018-05814
  • 财政年份:
    2021
  • 资助金额:
    $ 50万
  • 项目类别:
    Discovery Grants Program - Individual
Probing planet atmospheres and finding small planets nearby: paving the way for detecting life elsewhere
探测行星大气层并寻找附近的小行星:为探测其他地方的生命铺平道路
  • 批准号:
    RGPIN-2018-05814
  • 财政年份:
    2020
  • 资助金额:
    $ 50万
  • 项目类别:
    Discovery Grants Program - Individual
Probing planet atmospheres and finding small planets nearby: paving the way for detecting life elsewhere
探测行星大气层并寻找附近的小行星:为探测其他地方的生命铺平道路
  • 批准号:
    RGPIN-2018-05814
  • 财政年份:
    2019
  • 资助金额:
    $ 50万
  • 项目类别:
    Discovery Grants Program - Individual
Probing planet atmospheres and finding small planets nearby: paving the way for detecting life elsewhere
探测行星大气层并寻找附近的小行星:为探测其他地方的生命铺平道路
  • 批准号:
    RGPIN-2018-05814
  • 财政年份:
    2018
  • 资助金额:
    $ 50万
  • 项目类别:
    Discovery Grants Program - Individual
SBE: Small: Cybersecurity risks of dynamic, two-way distributed electricity markets
SBE:小:动态双向分布式电力市场的网络安全风险
  • 批准号:
    1618803
  • 财政年份:
    2016
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
CIF: Small: Optimizing Two-way Communications with Feedback
CIF:小:通过反馈优化双向通信
  • 批准号:
    1620794
  • 财政年份:
    2015
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
HCC: Small: FIDO - Facilitating Interaction for Dogs with Occupations: Wearable computing for two-way communication with assistance dogs
HCC:小型:FIDO - 促进狗与职业的互动:可穿戴计算用于与辅助犬的双向通信
  • 批准号:
    1320690
  • 财政年份:
    2013
  • 资助金额:
    $ 50万
  • 项目类别:
    Continuing Grant
CIF: Small: Optimizing Two-way Communications with Feedback
CIF:小:通过反馈优化双向通信
  • 批准号:
    1320419
  • 财政年份:
    2013
  • 资助金额:
    $ 50万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了