CIF: Small: Energy-Efficient Scheduling and Load Balancing

现代计算机系统消耗大量的能量，并且大型计算设施的能量成本可以达到数十亿美元。同时，电池功率是蜂窝电话和其它小型移动的设备的限制因素。该建议旨在设计和实现调度和负载平衡算法，更好地优化能源效率，而不牺牲服务质量。由于这些算法可以在软件中实现（无需设计或构建新的设备），因此它们是一个很有前途的方向，可以处理不断增长的能源需求。调度和负载平衡自然是在线问题，任务在算法运行期间到达，并且事先不知道。该建议的智力价值包括改进我们的技术，以在此类在线问题中产生可证明具有竞争力的结果，以及在任务部分可预测的情况下探索新的混合模型。该建议的目的是产生算法的能量和任务完成率之间的关系非常一般（以前的工作一般假设二次关系，这是不现实的），并允许更一般的表示服务质量。这些问题的数学技术包括线性规划舍入，在线原始-对偶，和基于流的分析在线加权matching.The更广泛的影响，这一建议涉及算法的实施和测试，可能导致大量节省能源。这些实现还需要处理许多实际问题，例如收集关于到达任务的数据（算法通常假设优先级和工作负载等信息是已知的）和设计有效的用户界面。这些将导致一些优秀的本科生项目，学生可以接触到先进的理论技术在算法设计，同时也产生节能软件的真实的设备。

Modern computer systems consume substantial amounts of energy, and energy costs for large computing facilities can reach into the billions of dollars. At the same time, battery power is a limiting factor for cellular phones and other small mobile devices. This proposal aims to design and implement scheduling and load-balancing algorithms which better optimize for energy-efficiency without sacrificing quality of service. Since these algorithms can be implemented in software (without the design or construction of new devices), they are a promising direction to deal with the growing demand for energy to power computation.Scheduling and load-balancing are naturally online problems, where tasks arrive during the run of the algorithm and are not known in advance. The intellectual merit of this proposal includes improving our techniques for producing provably competitive results in such online problems, as well as exploring new hybrid models in cases where the tasks are partially predictable. The proposal aims to produce algorithms under very general relationships between energy and task completion rate (prior work has generally assumed a quadratic relationship, which is not realistic) and to permit more general representations of quality of service. Algorithmic techniques for these problems include linear program rounding, online primal-dual, and flow-based analysis for variants of online weighted matching.The broader impact of this proposal involves the implementation and testing of algorithms, potentially leading to substantial savings in energy. The implementations also require dealing with a number of practical problems, such as collecting data about tasks on arrival (algorithms typically assume that information like priorities and workloads are known) and designing effective user interfaces. These will lead to a number of excellent undergraduate projects in which students can be exposed to advanced theoretical techniques in algorithm design while also producing energy-conserving software for real devices.