AF: Small: Collaborative Research: Algorithms for Reallocation Problems

虚拟化通常涉及重新映射物理资源（例如，存储、存储器、处理器）转换为逻辑资源，使得这些计算资源可以在动态环境中共享。重新映射过程有一个在线组件，请求到达，系统响应。在传统的在线问题中，资源被认为是合理分配的。然而，在虚拟化环境中，可以重新分配或重新分配先前分配的资源。该项目正式确定了当重新分配有一定的成本时，如何有效地重新分配计算资源。该项目研究了大规模系统设计中重新分配问题的算法复杂性，特别是重新分配成本函数方面的通用重新分配算法。该研究计划解决了内存和存储重新分配，存储系统中的横向扩展和分片，动态组合和几何结构（有限元网格，度量空间）的重新分配以及经典的在线分配问题（调度和装箱）。该项目有三个目标：（1）研究重新分配的渐进性能，（2）获得对于广泛类别的重新分配成本函数具有通用性的结果，以及（3）量化广泛使用的已知启发式算法的性能。今天的计算方式，在笔记本电脑和台式机上，在超级计算机和数据中心以及云计算中，关键取决于虚拟化。硬件趋势（例如，多核、固态盘）和软件趋势（例如，以数据为中心的计算）意味着虚拟化变得更加普遍。重分配算法对虚拟化系统的性能有很大的影响。该项目中概述的算法方法有望提高大型系统的性能、可伸缩性和可预测性。因此，这项研究显示出在未来十年内改善计算基础设施的巨大潜力。

Virtualization typically involves remapping physical resources (e.g., storage, memory, processors) into logical resources so that these computational resources can be shared in dynamic environments. The remapping process has an online component, in that requests arrive and the system responds. In traditional online problems, resources are thought of as irrevocably assigned. However, in virtualized environments, previously allocated resources can be reassigned or reallocated. This project formalizes how computational resources can be reallocated efficiently when there is some cost for the reallocation.The project investigates the algorithmic complexity of reallocation problems arising from large-scale systems design, and especially reallocation algorithms that are universal with respect to reallocation-cost functions. The research plan addresses problems in memory and storage reallocation, scaleout and sharding in storage systems, reallocation for dynamic combinatorial and geometric structures (finite-element meshes, metric spaces), and classical online allocation problems (scheduling and bin packing). The aim of the project is three-fold: (1) to study the asymptotic performance of reallocation, (2) to obtain results that are universal with respect to a wide class of reallocation cost functions, and (3) to quantify the performance of known heuristics in widespread use.The way computation works today, on laptops and desktops, in supercomputers and data centers, and in cloud computing, critically depends upon virtualization. Hardware trends (e.g., multicore, solid state disks) and software trends (e.g., data-centric computing) mean that virtualization is becoming even more prevalent. Reallocation algorithms have a large impact on the performance of virtualized systems. The algorithmic approach outlined in this project promises to improve the performance, scalability, and predictably of large systems. As such, this research show great promise for improving the general infrastructure of computing in the next decade.