Parallel and Distributed Algorithms for Caching, Scheduling, and Sorting Problems

该项目关注的是设计和分析简单而有效的算法，以解决并行和分布式计算中出现的一些基本问题。 高速缓存，调度和排序相关的问题被认为是。有效的高速缓存策略是至关重要的，几乎任何计算系统的性能，无论是顺序，并行，或分布式。 因此，几十年来，人们一直在深入研究这种战略。 不幸的是，在许多现有系统中成功优化缓存性能的久经考验的技术似乎不能很好地扩展到复杂的广域网，如互联网。 该项目的两个主要目标是为这种复杂网络建立合适的抽象模型，并为这些抽象模型设计简单有效的缓存策略。 调度决定了何时何地执行每个任务，并会显著影响性能。 传统上，这种调度决策留给程序员，这种方法允许最佳性能的可能性，但使并行编程困难。 工作窃取算法是一种简单而有效的“自动”任务调度方法。 然而，这种调度程序的实际效用主要取决于它所产生的开销量。 本计画探讨如何改善分散式资料结构的效能，例如工作窃取演算法中使用的并发双端队列，并提出两个排序相关的问题。 第一个是关于一个简单的周期性计划排序的二维网格上的分析。 该方案非常适合于VLSI实现，并被证明可以达到最佳的平均情况下的性能。 第二个排序相关的问题是关于一个简单的随机n输入电路的分析，该电路被构造为根据一个近似均匀的随机排列将输入映射到输出。 这种电路在密码学和高效路由网络的设计中有许多应用。

This project is concerned with the design and analysis of simple and efficient algorithms for a number of basic problems arising in parallel and distributed computing. Problems related to caching, scheduling and sorting are considered.Efficient caching strategies are critical to the performance of virtually any computing system, be it sequential, parallel, or distributed. As a consequence, such strategies have been intensively studied for decades. Unfortunately, the time-tested techniques that successfully optimize cache performance in many existing systems do not seem to scale well to complex wide-area networks such as the Internet. Two major goals of this project are to develop suitable abstract models of such complex networks, and to design simple and efficient caching strategies for these abstract models.Efficient scheduling of dynamically generated tasks is a central problem in parallel computing. Scheduling determines when and where to execute each task and can dramatically affect performance. Traditionally, such scheduling decisions are left to the programmer, an approach that allows for the possibility of optimal performance, but makes parallel programming difficult. The work-stealing algorithm is a simple and provably efficient "automatic" task-scheduling method. However, the practical utility of such a scheduler depends critically on the amount of overhead that it incurs. This project explores methods for improving the performance of distributed data structures as the concurrent deque used in the work-stealing algorithm.Two sorting-related problems are addressed in this project. The first is concerned with the analysis of a simple periodic scheme for sorting on a two-dimensional mesh. The scheme is well-suited for VLSI implementation and is conjectured to achieve optimal average-case performance. The second sorting-related problem is concerned with the analysis of a simple randomized n-imput circuit that is conjectured to map the inputs to the outputs according to a near-uniform random permutation. Such a circuit has a number of applications in cryptography and in the design of efficient routing networks.