A bridging model for multi-core computing
A bridging model for multi-core computing
复制标题
DOI：
10.1007/978-3-540-87744-8_2
复制
发表时间：
2008-09
期刊：
影响因子：
--
通讯作者：
L. Valiant
中科院分区：
文献类型：
--
作者：
L. Valiant
为一个并行系统编写软件是一个可行但艰巨的任务。事实证明，将如此耗费的大量智力工作重新用于第二个系统的编程更具挑战性。在顺序计算算法中，教科书和可移植软件是使软件系统能够在不断变化的硬件平台上高效移植的资源。这些资源目前在多核架构领域缺乏，在多核架构中，寻求高性能的程序员没有可比的机会来构建其他人的智力成果。为了解决这个问题，我们提出了一个桥接模型，旨在捕捉多核架构的最基本的资源参数。我们建议，为这种架构设计高效的算法所需的相当大的智力努力可能是最富有成效的扩展在设计便携式算法，一劳永逸，这样一个桥接模型。可移植算法将包含对基本资源参数和输入大小的所有合理组合的有效设计，并且将形成用于特定机器的实现或编译的基础。我们的Multi-BSP模型是一个多层次的模型，它具有处理器数量、内存/缓存大小、通信成本和同步成本的显式参数。最低级别对应于共享内存或PRAM，承认该模型的相关性，无论内存和处理器数量的限制，它可能是有效的模拟it. We提出参数感知的便携式算法，有效地运行在所有相关的架构与任何数量的水平和任何组合的参数。对于这些算法，我们定义了一个无参数的最优性概念。我们表明，对于几个基本问题，包括标准矩阵乘法，快速傅立叶变换，比较排序，存在最佳的便携式算法在这个意义上说，所有组合的机器参数。因此，在许多参数设置中可以找到一些算法的通用性和优雅性。
Writing software for one parallel system is a feasible though arduous task. Reusing the substantial intellectual effort so expended for programming a second system has proved much more challenging. In sequential computing algorithms textbooks and portable software are resources that enable software systems to be written that are efficiently portable across changing hardware platforms. These resources are currently lacking in the area of multi-core architectures, where a programmer seeking high performance has no comparable opportunity to build on the intellectual efforts of others. In order to address this problem we propose a bridging model aimed at capturing the most basic resource parameters of multi-core architectures. We suggest that the considerable intellectual effort needed for designing efficient algorithms for such architectures may be most fruitfully expended in designing portable algorithms, once and for all, for such a bridging model. Portable algorithms would contain efficient designs for all reasonable combinations of the basic resource parameters and input sizes, and would form the basis for implementation or compilation for particular machines. Our Multi-BSP model is a multi-level model that has explicit parameters for processor numbers, memory/cache sizes, communication costs, and synchronization costs. The lowest level corresponds to shared memory or the PRAM, acknowledging the relevance of that model for whatever limitations on memory and processor numbers it may be efficacious to emulate it. We propose parameter-aware portable algorithms that run efficiently on all relevant architectures with any number of levels and any combination of parameters. For these algorithms we define a parameter-free notion of optimality. We show that for several fundamental problems, including standard matrix multiplication, the Fast Fourier Transform, and comparison sorting, there exist optimal portable algorithms in that sense, for all combinations of machine parameters. Thus some algorithmic generality and elegance can be found in this many parameter setting.