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.