Scalable Parallel Symbolic Computation for Irregular Problems

不规则问题的可扩展并行符号计算

• 批准号: 0204113
• 负责人: Gene Cooperman
• 金额: $ 24.77万
• 依托单位: Northeastern University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-07-15 至 2006-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0204113&HistoricalAwards=false
• 关键词: Scalable; Parallel; Symbolic; Computation; Irregular

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.

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