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

这个项目是关于设计和分析在并行和分布式计算中出现的一些基本问题的简单而有效的算法。考虑了与缓存、调度和排序相关的问题。高效的缓存策略对于几乎任何计算系统的性能都是至关重要的，无论是顺序的、并行的还是分布式的。因此，这种策略已经被深入研究了几十年。不幸的是，在许多现有系统中成功优化缓存性能的久经考验的技术似乎不能很好地扩展到复杂的广域网（如Internet）。该项目的两个主要目标是为这些复杂的网络开发合适的抽象模型，并为这些抽象模型设计简单有效的缓存策略。动态生成任务的高效调度是并行计算中的一个核心问题。调度决定在何时何地执行每个任务，并且会极大地影响性能。传统上，这样的调度决策留给程序员，这种方法允许实现最佳性能的可能性，但使并行编程变得困难。偷工算法是一种简单有效的“自动”任务调度方法。然而，这种调度器的实际效用主要取决于它所带来的开销。本项目探讨了提高分布式数据结构性能的方法，如工作窃取算法中使用的并发队列。本项目解决了两个与排序相关的问题。首先分析了二维网格上排序的简单周期格式。该方案非常适合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.