AF:Small:Scheduling and Routing: Algorithms with novel cost measures

AF:Small：调度和路由：具有新颖成本度量的算法

• 批准号: 1421161
• 负责人: Clifford Stein
• 金额: $ 41.73万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1421161&HistoricalAwards=false
• 关键词: AF; Small; Scheduling; Routing; Algorithms

Computers, computer systems and the computational infrastructure provided by the internet are now essential for many aspects of modern life.  It is well-known and well-documented that, even as computing power and network bandwidth increase at a rapid rate, users and applications increase their demand for computation and their use of networks at roughly the same pace.  Thus, no matter how much progress is made on the hardware and network ends, efficient algorithms to manage these resources are essential. These efficient algorithms will lead to tremendous savings in both time and money and will have a positive environmental impact. They will also contribute to the decisions that are being made presently about the next generation of the internet, in particular in the design of routing protocols and the management of data centers.It is now well-understood that time and space are not the only resources that need to be carefully managed.  For the past few decades, there has been a growing emphasis on other concerns such as accuracy of solution, availability of information, use of cache, management of disk, etc.  More recently, there has been a growing understanding that energy and power management are also resources that should be carefully managed.  In this project, the PI will study several algorithmic problems that arise in applications such as computer systems and networks.  For each of these, the PI will focus on algorithms for better managing the technologies, and that have objectives that go beyond time or solution quality.  In particular, the project will study energy consumption in both computers and networks, and we will also consider environments in which other resources must be managed, such as minimizing the number of changes to a solution over time. The problem areas studied include power management in routing, power management in scheduling, extending speed scaling to other domains, and online problems with a reassignment cost. The PI will design efficient solutions to important practical problems, and the research will have broader impact.

计算机、计算机系统和互联网提供的计算基础设施现在对于现代生活的许多方面都至关重要，众所周知且有据可查的是，即使计算能力和网络带宽快速增加，用户和应用程序也在增加。他们对计算的需求和对网络的使用大致相同，因此，无论硬件和网络端取得多大进步，管理这些资源的高效算法都是必不可少的，这些高效的算法将带来巨大的节省。时间和金钱，并将产生积极的环境影响。还将有助于目前关于下一代互联网的决策，特别是在路由协议的设计和数据中心的管理方面。现在众所周知，时间和空间并不是唯一的资源在过去的几十年里，人们越来越重视其他问题，例如解决方案的准确性、信息的可用性、缓存的使用、磁盘的管理等。最近，人们的理解也越来越深入。能源和电力管理也是应该谨慎对待的资源在这个项目中，PI 将研究计算机系统和网络等应用中出现的几个算法问题，对于每个问题，PI 将重点关注更好地管理技术的算法，并且这些问题的目标是超越时间或范围的。特别是，该项目将研究计算机和网络的能源消耗，我们还将考虑必须管理其他资源的环境，例如尽量减少解决方案随时间的变化数量。研究的问题领域包括。路由中的电源管理、调度中的电源管理、扩展速度扩展到其他领域，以及具有重新分配成本的在线问题，PI将为重要的实际问题设计有效的解决方案，并且该研究将产生更广泛的影响。

项目成果

Scheduling When You Don't Know the Number of Machines

当您不知道机器数量时进行调度

• DOI: 10.1137/1.9781611975031.82
• 发表时间: 2018-01
• 期刊: Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms
• 作者: Stein, Clifford;Zhong, Mingxian
• 通讯作者: Zhong, Mingxian