Applying Learning Theory to Systems Problems

将学习理论应用于系统问题

• 批准号: 9877080
• 负责人: Stephen Scott
• 金额: $ 17.02万
• 依托单位: University of Nebraska-Lincoln
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-07-01 至 2003-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9877080&HistoricalAwards=false
• 关键词: Applying; Learning; Theory; Systems; Problems

CCR-9877080Scott This project will focus on applying results developed in learning theory to real-life problems. Such application-based theoretical work is important so that the learning models and problems studied capture as best possible the needs of real-life problems. Working to apply theoretical techniques to real problems creates a better understanding of the real-world problems and thus helps direct future theoretical work, facilitating the transfer of results from theory to practice. Many system control algorithms (e.g. networking protocols) depend heavily on ad hoc methods in their operation, and their performance can be very sensitive to the robustness of these methods. These ad hoc approaches are frequently based on assumptions made about the operating environment, e.g. assuming a particular distribution on the traffic patterns in a communication network without a sound statistical basis. This project will develop a framework based on formal learning methods for assisting in automatic system control. This framework will help to determine if better performance can be obtained by a system control algorithm. One goal of this project is to continue research on dynamically adjusting delays of acknowledgments in the TCP protocol. Delaying acknowledgments has two main advantages. First, it allows a single acknowledgment for more than one packet. Second, if a data packet is being sent in the opposite direction, then one can piggyback the acknowledgment on the outgoing packet. However, there is a tradeoff since delaying the acknowledgment too much can increase the latency. Most TCP implementations, used today employ some sort of acknowledgment delay mechanism. The project applies different learning schemes to predict TCP packet arrivals. The learning schemes include ones based on the Weighted Majority (WM) algorithm, ones based on the Exponentially Weighted Moving Average (EWMA) algorithm, and ones based on distributional assumptions with a sound statistical basis. The new ideas include new loss functions (functions that measure the learners' performance) that are more appropriate for the application. Another application explored in this project is that of branch prediction of general purpose programs. A fast, accurate branch predictor is invaluable to a computer architecture that relies on instruction-level parallelism (ILP) techniques, e.g. pipelined and superscalar architectures. Many commercial architectures employ branch prediction schemes, and it is well known that even a small increase in prediction accuracy can greatly increase the amount of ILP that can be exploited. An interesting facet of the branch prediction problem is that it requires some or all of the algorithms to be implemented in hardware. Thus whatever approaches are adapted eventually lead to algorithms that have fast and compact hardware implementations. The principal investigator's experience in hardware design and in learning theory will help in this regard. Applying learning theory results to these problems and other systems problems will then provide guidance in defining new theoretical learning models that better model real-life scenarios. This project will also carefully develop and study such new learning models.

CCR-9877080Scott这个项目将专注于将学习理论发展的成果应用于现实生活中的问题。这种以应用为基础的理论工作很重要，以便学习模型和所研究的问题尽可能最好地捕捉到现实生活中问题的需求。努力将理论技术应用于实际问题，有助于更好地理解现实世界的问题，从而有助于指导未来的理论工作，促进结果从理论转化为实践。许多系统控制算法(例如网络协议)在它们的操作中严重依赖于自组织方法，并且它们的性能可能对这些方法的健壮性非常敏感。这些自组织方法通常基于对操作环境作出的假设，例如，在没有可靠的统计基础的情况下假设通信网络中的业务模式的特定分布。这个项目将开发一个基于正式学习方法的框架，以帮助自动系统控制。该框架将有助于确定是否可以通过系统控制算法获得更好的性能。本项目的目标之一是继续研究动态调整TCP协议中的确认延迟。延迟确认有两个主要优点。首先，它允许对多个数据包进行一次确认。其次，如果数据分组正以相反的方向发送，则可以在传出的分组上携带确认。但是，由于确认延迟太多可能会增加延迟，因此需要进行权衡。目前使用的大多数TCP实现都采用了某种确认延迟机制。该项目应用不同的学习方案来预测TCP数据包到达。学习方案包括基于加权多数(WM)算法的学习方案，基于指数加权移动平均(EWMA)算法的学习方案，以及基于具有良好统计基础的分布假设的学习方案。新的想法包括更适合应用程序的新损失函数(衡量学习者表现的函数)。这个项目中探索的另一个应用是通用程序的分支预测。对于依赖指令级并行(ILP)技术的计算机体系结构，例如流水线和超标量体系结构，快速、准确的分支预测器是无价的。许多商业架构使用分支预测方案，众所周知，即使是预测精度的微小提高也可以极大地增加可利用的ILP的量。分支预测问题的一个有趣方面是，它需要在硬件中实现一些或所有算法。因此，无论采用哪种方法，最终都会产生具有快速而紧凑的硬件实现的算法。首席研究员在硬件设计和学习理论方面的经验将在这方面提供帮助。将学习理论结果应用于这些问题和其他系统问题，将为定义新的理论学习模型提供指导，这些模型可以更好地模拟现实生活场景。该项目还将认真开发和研究这种新的学习模式。