Scalable Parallel Symbolic Computation for Irregular Problems

这项研究是一个正在进行的项目的一部分，该项目旨在为大型符号计算提供软件基础设施。建议采用丰富的计算群论算法集，与该P.I.是非常熟悉的，作为分析更广泛使用并行性的障碍的测试平台。除了不规则计算的算法困难（这是符号计算的特点）之外，还有基于当今硬件中RAM限制的障碍。这些硬件障碍显然是真实的。在最新的体系结构上，对RAM的随机访问可能花费超过1，000个CPU周期。这对符号代数计算的影响比传统的数值或商业应用程序大得多，后者强调对RAM的顺序访问。即使是符号代数中的一些非并行应用程序，在当前的体系结构上也主要是内存限制（受RAM缓慢的限制），而不是CPU限制。这就需要对记录和档案管理的复杂性模型进行修订，使其不统一。

ABSTRACT0204113Gene CoopermanNotrheastern UThe proposed research is part of an ongoing project to provide the software infrastructure for large symbolic computations. It is proposed to employ the rich set of computational group theory algorithms, with which the P.I. is intimately familiar, as a testbed for analyzing the barriers to wider use of parallelism. In additionto the algorithmic difficulties of irregular computations that characterize much of symbolic computation, there are barriers based on limitations of RAM in today's hardware. These hardware barriers aredemonstrably real. A random access to RAM can cost more than 1,000 CPU cycles on the most recent architectures. This affects symbolic algebra computations to a much greater extent than traditionalnumerical or commercial applications, which emphasize sequential access to RAM. Even some non-parallel applications in symbolic algebra are shown to be primarily memory-bound (bound by slowness of RAM),rather than CPU-bound, on current architectures. This requires a revised, non-uniform complexity model of RAM.