PYI: Resource Bounds and Parallel Computation.

本研究包括两个方面：证明解决问题所需资源的下界和寻找满足这些资源边界的算法。本研究的主要焦点是并行模型的各种特性如何影响执行计算所需的资源。大型共享内存机器很可能在处理器互连网络上实现，这种实现建议共享内存模型具有比以前研究的机器更强大的基本操作——基本操作，如无界扇入阈值函数和其他无界扇入关联操作。正在研究的是这些更强大的机器的局限性和能力，这些机器最近被提出作为大型并行计算机的非常有用的抽象。目前仍有许多非常基本的计算问题，如除法、连通性和传递闭包等，存在并行算法，但其并行复杂性尚未得到清楚的理解。提高这些基本问题的资源利用率尤为重要，因为解决这些问题的算法是解决许多更复杂问题的并行算法的基础。

This research has two aspects: proving lower bounds on the resources needed to solve problems and finding algorithms which meet those resource bounds. A major focus of this research is on how various features of parallel models affect the resources needed for performing computations. Large shared-memory machines are likely to be implemented on processor interconnection networks and this implementation suggests shared-memory models with even more powerful primitive operations than those of the machines previously studied - primitive operations like unbounded fan- in threshold functions and other unbounded fan-in associative operations. Under investigation are the limitations and capabilities of these more powerful machines which have recently been proposed as very useful abstractions of large parallel computers. There still are a number of very basic computational problems such as division, connectivity, and transitive closure for which parallel algorithms exist but whose parallel complexity is not clearly understood. It is particularly important to improve the resource usage for these basic problems because the algorithms for solving them underlie the parallel algorithms for many more complex problems.