"Online algorithms, paging and multicore architectures (CMP)"

在线算法和分析是对计算问题的研究，在这些问题中，必须在不完全或部分信息的情况下做出最终的、不可撤销的决定。它的应用范围从内存管理和调度，到灾区探索，再到在不断发展的城市中规划服务中心的位置。 在实践中，已经进行了多次失败的尝试，以模拟和预测“好的”在线算法的所需特征；然而，这一目标尚未完全实现。我们相信，这项研究现已接近成果。事实上，最近我们引入了一个寻呼算法模型，它回答了一个长期存在的问题，即观察到的最近最少使用(LRU)启发式算法的优越性。我们将特别研究更好的寻呼、列表更新、装箱和缓冲数据包路由性能措施。 这项研究的第二个目标是研究多核体系结构的分页和缓存算法。到目前为止，我们已经表明，对于离线版本，这个问题是NP-完全的；主要的挑战是分配高速缓存大小；执行的公平性问题对性能至关重要。在匹配的理论保证下，我们将提出新的实用的芯片多处理器分页算法。 同样重要的是，我们正在为现代多核体系结构开发一个理论模型，其中包括同步、处理器间通信、分页以及编程和分析的简易性等问题。建立的串行计算(RAM)模型很好地权衡了上述参数，并为I/O界限模型开发了适当的扩展。相比之下，在并行计算方面，没有一个单一的模型脱颖而出，PRAM和/或Valiant的BSP模型是替代模型的主要候选者。我们将研究PRAM模型的更新，但处理器数量有限。因此，我们从以前的PRAM工作中受益，同时避免了它更令人烦恼的特点。本研究旨在提出一种既易于研究又能准确反映物理硬件的新的多核模型，这是开发下一代高效算法的关键一步。

Online algorithms and analysis is the study of computational problems in which final, irrevocable decisions must be made under incomplete or partial information. Its applications range from memory management and scheduling, to exploration of a disaster area, to planning the location of service centers in a growing city. Numerous failed attempts to model and predict the desired characteristics of a "good" online algorithm in practice have been made; however this goal has yet to be fully realized. We believe that this research is now near fruition. Indeed, recently we introduced a model for paging algorithms which answered a long standing question on the observed superiority of the Least Recently Used (LRU) heuristic. We will study in particular better measures for the performance of paging, list update, bin packing and buffered packet routing. A second objective of this research is to study paging and caching algorithms for multicore architectures. We have shown thus far that this problem is NP-complete for the offline version; that the main challenge is in the assignment of cache sizes; and that issues of fairness of execution are crucial to performance. We will propose novel practical algorithms for paging in chip multiprocessors with matching theoretical guarantees. Equally important, we are developing a theoretical model for modern multicore architectures that includes issues of synchronization, interprocessor communication, paging, and ease of programming and analysis. The established model of serial computation (RAM) is an excellent tradeoff of the parameters above, and suitable extensions have been developed for I/O bound models. In contrast, for parallel computations no single model has stood out, with the PRAM and/or the BSP model of Valiant being the leading candidates for a replacement. We will study an update of the PRAM model but with a bounded number of processors. Thus we benefit from previous PRAM work while avoiding its more vexing characteristics. This research aims to introduce a new multicore model which is both amenable to study and accurately reflects the physical hardware, which is a key step for the development of the next generation of efficient algorithms.