AF:Small: Algorithmic Management of Heterogeneous Resources

AF:Small：异构资源的算法管理

基本信息

批准号：
1907673
负责人：
Kirk Pruhs
金额：
$ 23.94万
依托单位：
University of Pittsburgh
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-10-01 至 2024-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1907673&HistoricalAwards=false
关键词：
AF Small Algorithmic Management Heterogeneous

项目摘要

Energy arguably ascended over time as the dominant computational resource circa 2000, when standard information technologies could no longer cope with the consequences of Moore's law, which states that the density of computational units doubles every couple of years. Thus the community is about a decade or two into an information-technology revolution in which a wide range of technologies are being redesigned with energy as a first-class design constraint. Over the last several decades, when time and space were the dominant computational resources, computer-science researchers developed many techniques for designing algorithms that made efficient use of these resources, and for analyzing the time and space required by particular algorithms on simple models of a computer. These techniques are commonly taught in algorithms and theory/complexity classes that are required for computer scientists. The ability to reason abstractly about time and space in simple computational models is undoubtedly a valuable skill for computer scientists and software engineers, and many of the most successful computing companies are famous for job interviews that tests these reasoning skills. The PI's long term goal is to build a body of knowledge related to algorithm design and analysis techniques for problems related to managing heterogeneous resources, and managing energy as a computational resource. The PI expects that this body of knowledge will eventually be taught to future software engineers, and will serve these software engineers, when faced with problems in which power/energy/temperature is the key scarce resource, just as the current algorithmic theory of time as a computation resource now serves them. One of the most common mechanisms for achieving energy efficiency is building a system with heterogeneous devices with different energy/performance characteristics. For a given area and power budget, heterogeneous designs often give significantly better performance, for a given energy/hardware budget, for standard workloads than homogeneous designs. The PI will address algorithmic problems related to managing heterogeneous resources in several technologies arising from this information-technology revolution. Briefly, these problems are online convex optimization with applications to energy-efficient load balancing of data centers, energy-efficient routing in a network, designing combinatorial circuits that optimally trade-off energy efficiency and reliability, determining the complexity of finding schedules that optimally trade-off energy and performance, and analyzing scheduling algorithms on a heterogeneous multiprocessor. Managing heterogeneous resources is algorithmically significantly more challenging than managing heterogeneous resources, and many existing algorithmic techniques are not sufficient for handling these algorithmic problems. This project aims to invent new algorithmic techniques for solving these problems.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.

可以说，随着时间的推移，能源在 2000 年左右逐渐成为占主导地位的计算资源，当时标准信息技术无法再应对摩尔定律的后果，摩尔定律指出计算单元的密度每隔几年就会翻一番。因此，社会大约经历了一两年的信息技术革命，其中广泛的技术正在被重新设计，能源作为一流的设计约束。在过去的几十年里，当时间和空间成为主要的计算资源时，计算机科学研究人员开发了许多技术来设计有效利用这些资源的算法，并在简单的模型上分析特定算法所需的时间和空间。电脑。这些技术通常在计算机科学家所需的算法和理论/复杂性课程中教授。对于计算机科学家和软件工程师来说，在简单的计算模型中对时间和空间进行抽象推理的能力无疑是一项宝贵的技能，许多最成功的计算公司都以测试这些推理技能的面试而闻名。 PI 的长期目标是建立与算法设计和分析技术相关的知识体系，以解决与管理异构资源和管理能源作为计算资源相关的问题。 PI 期望这些知识体系最终能够传授给未来的软件工程师，并在面临功率/能量/温度是关键稀缺资源的问题时为这些软件工程师提供服务，就像当前的时间算法理论一样现在有计算资源为他们服务。实现能源效率的最常见机制之一是构建具有不同能源/性能特征的异构设备的系统。对于给定的面积和功率预算，对于给定的能源/硬件预算、标准工作负载，异构设计通常比同构设计提供更好的性能。 PI 将解决与管理这次信息技术革命所产生的多种技术中的异构资源相关的算法问题。简而言之，这些问题是在线凸优化，应用于数据中心的节能负载平衡、网络中的节能路由、设计最佳权衡能源效率和可靠性的组合电路、确定寻找最佳交易调度的复杂性-关闭能源和性能，并分析异构多处理器上的调度算法。管理异构资源在算法上比管理异构资源更具挑战性，并且许多现有的算法技术不足以处理这些算法问题。该项目旨在发明新的算法技术来解决这些问题。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（9）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Hallucination Helps: Energy Efficient Virtual Circuit Routing

幻觉有帮助：节能虚拟电路路由

DOI：
10.1137/18m1228591
发表时间：
2020-01
期刊：
SIAM Journal on Computing
影响因子：
1.6
作者：
Antoniadis, Antonios;Im, Sungjin;Krishnaswamy, Ravishankar;Moseley, Benjamin;Nagarajan, Viswanath;Pruhs, Kirk;Stein, Clifford
通讯作者：
Stein, Clifford

A Poly-log Competitive Posted-Price Algorithm for Online Metrical Matching on a Spider

一种用于蜘蛛在线度量匹配的多对数竞争性定价算法