ITR: Algorithms for Irregular Discrete Computations on SMPs

并行计算已经承诺了非常高的性能，但只在很窄的应用范围内提供了它。在大型分布式内存系统的层次上利用并行性受到消息传递成本的阻碍，而共享内存系统仍然大多是小规模的。然而，随着对称多处理器（SMP）的出现，适度规模的共享内存正在成为桌面科学和工程应用的标准。然而，除了基本的线性代数和快速傅立叶变换之外，在SMP上支持有效的并行计算的工作还很少。 幸运的是，研究人员的初步工作表明，有可能设计和实现用于不规则（即基于图形）计算的算法，这些算法可以在SMP上提供高效，可扩展的性能。该项目将进一步开发、实施、评估和完善这些算法。在技术上，该项目将专注于基于图形或几何的科学驱动问题（例如，遗传三通和流域建模），因此涉及不规则计算。它将为这些问题提供三个主要好处。首先，它将开发新的算法和基本例程库，以支持图形和计算几何算法，利用近二十年的并行随机存取存储器（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.