ITR: Algorithms for Irregular Discrete Computations on SMPs

并行计算承诺了非常高的性能，但只在有限的应用范围内实现。在大型分布式内存系统级别上利用并行性受到消息传递成本的阻碍，而共享内存系统大多仍然是小规模的。然而，随着对称多处理器（smp）的出现，适度规模的共享内存正在成为桌面科学和工程应用程序的标准。然而，除了基本线性代数和快速傅立叶变换之外，支持SMP上有效并行计算的工作还很少。幸运的是，研究人员的初步工作表明，可以为不规则（即基于图的）计算设计和实现算法，从而在smp上提供高效、可扩展的性能。该项目将进一步开发、实施、评估和完善这些算法。从技术上讲，该项目将侧重于基于图形或几何的科学驱动问题（例如，系统发育tee和分水岭建模），因此涉及不规则计算。它将为这些问题提供三个主要好处。首先，它将开发新的算法和基本例程库，以支持图形和计算几何算法，利用近二十年来并行随机存取存储器（PRAM）理论工作的见解。其次，它将使用生成的测试实例和真实世界的数据为基于smp的计算提供评估方法，扩展算法工程和实验算法的最新发展。最后，它将为科学问题提供在桌面smp上进行高性能计算的实际演示。

Parallel computing has promised very high performance, but has delivered it only in a narrow range of applications. Exploiting parallelism at the level of large distributed-memory systems is hampered by the cost of message-passing, while shared-memory systems remain mostly small-scale. With the advent of symmetric multiprocessors (SMPs), however, shared-memory on a modest scale is becoming the standard for desktop scientific and engineering applications. Yet very little has been done yet to support effective parallel computing on an SMP beyond basic linear algebra and fast Fourier transforms. Fortunately, preliminary work by the investigators indicates that it is possible to design and implement algorithms for irregular (i.e. graph-based) computations that provide efficient, scalable performance on SMPs. This project will further develop, implement, assess, and refine those algorithms.Technically, the project will focus on science-driven problems that are graph- or geometry-based (e.g. phylogeny tees and watershed modeling) and thus involve irregular computation. It will provide three main benefits for these problems. First, it will develop new algorithms and a library of basic routines to support graph and computational geometry algorithms, leveraging insights from nearly twenty years of theoretical work on Parallel Random Access Memory (PRAM). Second, it will produce an assessment methodology for SMP-based computations using both generated test instances and real-world data, extending recent developments in algorithmic engineering and experimental algorithmics. Finally, it will provide a practical demonstration of high performance computing on desktop SMPs for scientific problems.