CIF: Small: Energy-Efficient Scheduling and Load Balancing

CIF：小型：节能调度和负载平衡

• 批准号: 1016540
• 负责人: Rafail Ostrovsky
• 金额: $ 34.5万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-08-15 至 2013-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1016540&HistoricalAwards=false
• 关键词: CIF; Small; Energy; Efficient; Scheduling

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.

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