AF:Small: Algorithmic Management of Heterogeneous Resources

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

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.