Scalable Parallel Symbolic Computation for Irregular Problems

点击翻译按钮获取中文摘要

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.