AitF: Efficient Memory Management via Randomized, Streaming, and Online Algorithms

从小型低功耗和移动设备到大型数据中心，内存管理是计算机系统的重要组成部分。为了存储输入数据和计算状态而需要执行的任何重要计算过程都需要内存。高效内存管理的目标是将可用内存分配给需要执行的不同进程，从而使后续计算的速度最大化；系统使用的能量被最小化；并且可以充分利用可用的内存硬件。这个项目的重点是改进现有的内存管理方法，并可能导致在广泛应用中使用的计算机基础设施的重大改进。该项目还将通过课程开发和直接参与研究，培养学生将算法设计应用于计算机系统领域。在这个项目中，我们专注于设计和分析新的随机算法，以解决在内存管理环境中出现的各种问题。这包括轻量级数据流或“基于草图”的算法，这些算法速度快，使用有限的内存，而在线算法需要在不知道这些数据上的哪些数据或操作在未来是相关的情况下，就如何最好地使用少量可用内存做出决策。我们还将开发一种新的随机化技术，用于压缩内存，甚至适用于像C和c++这样使用显式内存管理且对象不能重新定位的语言。我们的方法可以减轻潜在灾难性碎片的风险，从而提高内存利用率和性能。

Memory management is an essential component of computer systems ranging from small low-power and mobile devices up to large data centers. Memory is necessary for any non-trivial computing process that needs to be performed in order to store the input data and the state of the computation. The goal of efficient memory management is to allocate the available memory to the different processes that need to be performed in such a way that the speed of the subsequent computation is maximized; the energy used by the system is minimized; and the available memory hardware is fully exploited. This project is focused on improving existing memory management approaches and could lead to significant improvements in the computer infrastructure used in a broad range of applications. The project will also train students, both through curriculum development and direct involvement in the research, in the application of algorithm design to the field of computer systems.In this project, we focus on designing and analyzing new randomized algorithms for various problems that arise in the context of memory management. These include both lightweight data stream or "sketch-based" algorithms that are fast and use limited memory, and online algorithms that need to commit to decisions about how to best to use a small amount of available memory without knowing what data or operations on this data will be relevant in the future. We will also develop a new randomized technique for compacting memory even for languages such as C and C++ that use explicit memory management and where objects cannot be relocated. Our approach should mitigate the risk of potentially catastrophic fragmentation and thereby improve memory utilization and performance.