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.