Average-Case Parallel Algorithms, and Aspects of Architectures

本研究的目的是：1。设计和分析具有快速平均情况时间的算法，同时获得速度，更简单的算法，并开发一种比通常强调最坏情况时间更符合实践的算法分析。细粒度共享内存和中粒度分布式内存都将被考虑到。这包括建模和实现具有一系列局部/全局权衡的算法的工作，以便这些算法可以移植到各种机器上，并在每台机器上轻松优化。2. 确定并发写的各种抽象模型之间的关系，强调具有潜在光学实现的模型。3. 开发问题之间的约简，并根据一些标准问题开发并行算法，以简化体系结构之间的可移植性。4. 开发一种分布式内存机器，在各种几何问题上与共享内存机器的性能相匹配。

The objectives of this research are to: 1. Design and analyze algorithms with fast average-case time, simultaneously obtaining speed, simpler algorithms, and developing an analysis of algorithms which matches practice better than the usual emphasis on worst-case time. Both fine-grained shared memory, and medium-grained distributed memory, machines will be considered. This includes work on modeling and implementing algorithms with a range of local/global tradeoffs, so that such algorithms can be ported to a variety of machines and be easily optimized on each. 2. Determine relationships among various abstract models of concurrent writes, emphasizing models with potential optical implementations. 3. Develop reductions among problems, and develop parallel algorithms in terms of a few standard problems, to simplify portability among architectures. 4. Develop a distributed-memory machine which matches the performance of shared-memory machines on a variety of geometrical problems.