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

点击翻译按钮获取中文摘要

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.