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.