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将集中于算法，以更好地管理技术，并有超越时间或解决方案质量的目标。2特别是，该项目将研究计算机和网络中的能源消耗，我们也将考虑其他资源必须管理的环境，如最小化随时间变化的解决方案的数量。研究的问题领域包括电源管理路由，电源管理调度，扩展速度缩放到其他领域，和在线问题的重新分配成本。PI将为重要的实际问题设计有效的解决方案，研究将产生更广泛的影响。

项目成果

Scheduling When You Don't Know the Number of Machines

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

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