SHF: Small: A Composable, Sound Optimization Framework for Loops and Recursion

SHF:小型:用于循环和递归的可组合、完善的优化框架

基本信息

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

项目摘要

Over the last several decades, researchers have developed numerous general frameworks to optimize programs that manipulate matrices, grids, and other "regular" structures by using loops. These optimizations can improve parallelism and performance and hence are critical to developing high-performance software. However, a large class of programs does not use loops but instead uses recursive formulations; these programs are inaccessible to existing general frameworks, and heretofore have only been optimized by ad hoc, narrowly-focused techniques. This means that optimization strategies that work for one program, or one domain, often have to be re-thought and re-implemented for new applications. This project's novelties are developing new program representations, transformation strategies, and analysis techniques to build a new, general framework for optimizing programs that use recursion. This project's impacts will be to open up the power of general optimizations and transformations to a broader range of applications that use recursion, which arise in domains ranging from graphics to data mining to simulation.The general framework developed by the investigator in this project leverages several novel components. First, it captures the schedule of computations of recursive applications using computational constructs called multi-tape finite automata, that allow the framework to distinguish between computations that arise from different parts of the program. Second, it represents transformations of that schedule--which can restructure a computation to improve locality or parallelism--using multi-tape finite transducers. Third, it captures dependences in the computation--which restrict the space of legal computation schedules--using a novel abstraction called witness tuples. Finally, the project develops new, decidable algorithms for determining whether a particular transformation is safe. The work is then extended to identify promising transformation strategies, handle more general types of recursive programs, and generate high-performance code in a more effective manner.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.
在过去的几十年里,研究人员已经开发了许多通用的框架来优化程序,通过使用循环来操纵矩阵,网格和其他“规则”结构。这些优化可以提高并行性和性能,因此对于开发高性能软件至关重要。然而,一个大类的程序不使用循环,而是使用递归公式,这些程序是无法访问现有的一般框架,迄今为止,只有通过特设的,狭隘的技术进行优化。这意味着,对于一个程序或一个领域有效的优化策略,通常必须重新考虑并重新实现新的应用程序。这个项目的新颖之处在于开发新的程序表示、转换策略和分析技术,以构建一个新的通用框架来优化使用递归的程序。这个项目的影响将是开放的通用优化和转换的能力,以更广泛的应用程序,使用递归,出现在从图形到数据挖掘到仿真的领域。首先,它捕获递归应用程序的计算时间表,使用称为多带有限自动机的计算结构,允许框架区分来自程序不同部分的计算。其次,它表示该调度的转换-可以使用多带有限转换器重构计算以提高局部性或并行性。第三,它使用一种称为见证元组的新颖抽象来捕获计算中的依赖性--这限制了法律的计算调度的空间。最后,该项目开发了新的,可判定的算法,用于确定特定的转换是否安全。该奖项反映了NSF的法定使命,并通过使用基金会的智力价值和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(9)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Cornucopia : A Framework for Feedback Guided Generation of Binaries
QuickSilver: modeling and parameterized verification for distributed agreement-based systems
QuickSilver:基于分布式协议的系统的建模和参数化验证
  • DOI:
    10.1145/3485534
  • 发表时间:
    2021
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Jaber, Nouraldin;Wagner, Christopher;Jacobs, Swen;Kulkarni, Milind;Samanta, Roopsha
  • 通讯作者:
    Samanta, Roopsha
RT-kNNS Unbound: Using RT Cores to Accelerate Unrestricted Neighbor Search
RT-kNNS Unbound:使用 RT 内核加速无限制邻居搜索
  • DOI:
    10.1145/3577193.3593738
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Nagarajan, Vani;Mandarapu, Durga;Kulkarni, Milind
  • 通讯作者:
    Kulkarni, Milind
DARM: Control-Flow Melding for SIMT Thread Divergence Reduction
DARM:用于减少 SIMT 线程发散的控制流融合
SparseLNR: accelerating sparse tensor computations using loop nest restructuring
{{ 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 }}

Milind Kulkarni其他文献

Can paediatric surgical registrars safely perform supervised hypospadias surgery?
儿科手术注册员可以在监督下安全地进行尿道下裂手术吗?
  • DOI:
  • 发表时间:
    2024
  • 期刊:
  • 影响因子:
    2
  • 作者:
    Charlotte Hughes;Hazem Mosa;Sandra Johnson;J. Parr;Ravindar Anbarasan;Milind Kulkarni;A. Mathur
  • 通讯作者:
    A. Mathur
Garbage Collection for Mostly Serialized Heaps
大多数序列化堆的垃圾收集
InContext: simple parallelism for distributed applications
InContext:分布式应用程序的简单并行性
  • DOI:
    10.1145/1996130.1996144
  • 发表时间:
    2011
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Sunghwan Yoo;Hyojeong Lee;C. Killian;Milind Kulkarni
  • 通讯作者:
    Milind Kulkarni
The Centre for Market and Public Organisation One Kind of Democracy One Kind of Democracy
市场与公共组织中心 一种民主 一种民主
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Siwan Anderson;P. Francois;Ashok Kotwal;Milind Kulkarni;Tim Murugkar;Gustavo Besley;Biju Bobonis;Jim Rao;Jim Fearon;Francesco Robinson;John Trebbi;Debraj Hoddinott;Nava Ray;Robin Ashraf;Garance Burgess;Dilip Genicot;Thomas Mookherjee;Fujiwara
  • 通讯作者:
    Fujiwara
Scheduling Transformation and Dependence Tests for Recursive Programs
递归程序的调度转换和依赖性测试
  • DOI:
  • 发表时间:
    2018
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Kirshanthan Sundararajah;Milind Kulkarni
  • 通讯作者:
    Milind Kulkarni

Milind Kulkarni的其他文献

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

{{ truncateString('Milind Kulkarni', 18)}}的其他基金

Collaborative Research: PPoSS: LARGE: A Full-Stack Architecture for Sparse Computation
协作研究:PPoSS:LARGE:稀疏计算的全栈架构
  • 批准号:
    2216978
  • 财政年份:
    2022
  • 资助金额:
    $ 45万
  • 项目类别:
    Continuing Grant
Travel: Student Travel Grant for the Programming Languages Mentoring Workshop at PLDI 2022
旅费:PLDI 2022 编程语言指导研讨会的学生旅费补助
  • 批准号:
    2227746
  • 财政年份:
    2022
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
SPX: Write Once, Run on Anything: Verified, Tuned Accelerator Kernels from High Level Specifications
SPX:一次写入,在任何设备上运行:根据高级规范进行验证、调整的加速器内核
  • 批准号:
    1919197
  • 财政年份:
    2019
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
NSF Student Travel Grant for 2019 Midwest Programming Languages Summit (MWPLS)
2019 年中西部编程语言峰会 (MWPLS) 的 NSF 学生旅费补助金
  • 批准号:
    1942074
  • 财政年份:
    2019
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
SPX: Collaborative Research: Eat your Wheaties: Multi-Grain Compilers for Parallel Builds at Every Scale
SPX:协作研究:吃你的小麦:用于各种规模并行构建的多粒度编译器
  • 批准号:
    1725672
  • 财政年份:
    2017
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
SI2-SSI: Collaborative Research: ParaTreet: Parallel Software for Spatial Trees in Simulation and Analysis
SI2-SSI:协作研究:ParaTreet:仿真和分析中的空间树并行软件
  • 批准号:
    1550525
  • 财政年份:
    2016
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
SHF: Small: Collaborative Research: Hybrid Static-Dynamic Analyses for RegionSerializability
SHF:小型:协作研究:区域可串行性的混合静态动态分析
  • 批准号:
    1422178
  • 财政年份:
    2014
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
XPS: FULL: FP: Collaborative Research: Taming parallelism: optimally exploiting high-throughput parallel architectures
XPS:完整:FP:协作研究:驯服并行性:最佳地利用高吞吐量并行架构
  • 批准号:
    1439126
  • 财政年份:
    2014
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
XPS: CLCCA: On the Hunt for Correctness and Performance Bugs in Large-scale Programs
XPS:CLCCA:寻找大型程序中的正确性和性能错误
  • 批准号:
    1337158
  • 财政年份:
    2013
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
CAREER:Toward a locality-enhancing transformation framework for irregular programs
职业生涯:为非正规项目建立一个增强地方性的转型框架
  • 批准号:
    1150013
  • 财政年份:
    2012
  • 资助金额:
    $ 45万
  • 项目类别:
    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 RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

Powering Small Craft with a Novel Ammonia Engine
用新型氨发动机为小型船只提供动力
  • 批准号:
    10099896
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Collaborative R&D
"Small performances": investigating the typographic punches of John Baskerville (1707-75) through heritage science and practice-based research
“小型表演”:通过遗产科学和基于实践的研究调查约翰·巴斯克维尔(1707-75)的印刷拳头
  • 批准号:
    AH/X011747/1
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Research Grant
Fragment to small molecule hit discovery targeting Mycobacterium tuberculosis FtsZ
针对结核分枝杆菌 FtsZ 的小分子片段发现
  • 批准号:
    MR/Z503757/1
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Research Grant
Bacteriophage control of host cell DNA transactions by small ORF proteins
噬菌体通过小 ORF 蛋白控制宿主细胞 DNA 交易
  • 批准号:
    BB/Y004426/1
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Research Grant
Windows for the Small-Sized Telescope (SST) Cameras of the Cherenkov Telescope Array (CTA)
切伦科夫望远镜阵列 (CTA) 小型望远镜 (SST) 相机的窗口
  • 批准号:
    ST/Z000017/1
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Research Grant
CSR: Small: Leveraging Physical Side-Channels for Good
CSR:小:利用物理侧通道做好事
  • 批准号:
    2312089
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
CSR: Small: Multi-FPGA System for Real-time Fraud Detection with Large-scale Dynamic Graphs
CSR:小型:利用大规模动态图进行实时欺诈检测的多 FPGA 系统
  • 批准号:
    2317251
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
AF: Small: Problems in Algorithmic Game Theory for Online Markets
AF:小:在线市场的算法博弈论问题
  • 批准号:
    2332922
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
Collaborative Research: FET: Small: Algorithmic Self-Assembly with Crisscross Slats
合作研究:FET:小型:十字交叉板条的算法自组装
  • 批准号:
    2329908
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
NeTS: Small: ML-Driven Online Traffic Analysis at Multi-Terabit Line Rates
NeTS:小型:ML 驱动的多太比特线路速率在线流量分析
  • 批准号:
    2331111
  • 财政年份:
    2024
  • 资助金额:
    $ 45万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了