下一节:稀疏BLAS 上一级:矩阵向量与矩阵矩阵乘法 上一节:矩阵向量与矩阵矩阵乘法

BLAS

在过去大约15年的时间里,算法和软件领域在解决线性代数问题方面取得了大量进展。 线性代数社区早已认识到将算法开发成软件库的必要性,几年前,作为社区共同努力的结果,制定了一个识别线性代数算法和软件所需基本操作的事实标准。 希望构成这一标准的例程(统称为基本线性代数子程序(BLAS))能够在众多制造商的高级架构计算机上得到高效实现,从而使这些例程在广泛机器上高效运行的可移植性优势得以充分发挥。这一目标在很大程度上已经实现。

我们为高级架构计算机设计线性代数算法的关键洞察是,为了达到高性能,必须尽量减少数据在内存层次结构不同级别之间移动的频率。 因此,我们在实现中利用向量化和并行化的主要算法方法是使用分块算法,特别是在执行矩阵-向量和矩阵-矩阵操作(即2级和3级BLAS)时,结合高度优化的核心程序。 通常,使用分块算法需要以块而非向量或标量的形式移动数据,虽然移动的数据总量不变,但由于移动数据所需的消息数量减少,与移动相关的延迟(或启动成本)大大降低。

第二个关键思想是,用户可以通过调整指定数据布局的参数来调整算法的性能。在共享内存机器上,这由块大小控制,而在分布式内存机器上,则由块大小和逻辑进程网格的配置控制。

问题来了,“我们如何才能对影响性能的这些不同因素进行足够控制,以达到机器所能提供的性能水平?”答案是通过使用BLAS。

现在有三个级别的BLAS:

1级BLAS [288]:用于向量操作,例如 y \leftarrow \alpha x + y

2级BLAS [133]:用于矩阵-向量操作,例如 y \leftarrow \alpha A x + \beta y

3级BLAS [134]:用于矩阵-矩阵操作,例如 C \leftarrow \alpha A B + \beta C

这里,ABC 是矩阵;xy 是向量;\alpha\beta 是标量。

1级BLAS在LAPACK等软件包中被使用,主要是为了方便而非性能:它们执行的计算量微不足道,并且在大多数现代超级计算机上无法实现高效率。

2级BLAS可以在许多向量处理器上达到接近峰值性能,例如CRAY X-MP或Y-MP的单个处理器,或Convex C-2机器。然而,在其他向量处理器如CRAY-2或IBM 3090 VF上,2级BLAS的性能受限于不同内存级别之间的数据移动速率。

3级BLAS克服了这一限制。这第三级BLAS对O(n^2)数据执行O(n^3)浮点运算,而2级BLAS仅对O(n^2)数据执行O(n^2)操作。3级BLAS还允许我们以对调用它们的软件透明的方式利用并行性。尽管2级BLAS提供了一些利用并行性的空间,但3级BLAS提供了更大的空间。

用户社区广泛采用BLAS,不仅出于性能原因,还因为围绕像BLAS这样的核心例程开发软件是良好的软件工程实践。大多数现代高性能计算机都有高度优化的BLAS实现。BLAS使得软件能够用可移植的代码实现高性能。

本着早期的BLAS会议以及消息传递接口(MPI)和高性能Fortran(HPF)论坛的标准化努力精神,成立了一个技术论坛,以考虑在现代软件、语言和硬件发展的背景下扩展BLAS。BLAS技术论坛会议始于1995年11月在田纳西大学举办的一个研讨会。会议由大学和软件及硬件供应商主办。

成立了各种工作组来考虑诸如整体功能、语言接口、稀疏BLAS、分布式内存密集型BLAS、扩展和混合精度BLAS、区间BLAS以及对现有BLAS的扩展等问题。论坛的规则采用了MPI和HPF论坛使用的规则。

本文件中定义的标准的主要目标是使线性代数库(无论是公共领域还是商业)能够高效、可靠且轻松地互操作。我们相信,硬件和软件供应商、更高级别库的编写者以及应用程序程序员都从该论坛的努力中受益,并是这些标准的预期最终用户。

关于BLAS和BLAS技术论坛的更多信息可以在本书的主页上获得,ETHOME。 BLAS技术论坛的网页可以在以下网址找到:

http://www.netlib.org/blas/blast-forum/blast-forum.html



下一节:稀疏BLAS 上一级:矩阵向量与矩阵矩阵乘法 上一节:矩阵向量与矩阵矩阵乘法
Susan Blackford 2000-11-20