ScaLAPACK 简介
在上一篇中我们介绍了一个非常实用的工具 mpipool，下面我们将简要地介绍并行分布式线性代数运算工具 ScaLAPACK，然后我们会介绍在 python 中使用 ScaLAPACK 的工具 scalapy。
简介
ScaLAPACK（Scalable LAPACK 简称）是一个并行计算软件包，适用于分布式存储的 MIMD （multiple instruction, multiple data）并行计算机。它是采用消息传递机制实现处理器/进程间通信，因此使用起来和编写传统的 MPI 程序比较类似。ScaLAPACK 主要针对密集和带状线性代数系统，提供若干线性代数求解功能，如各种矩阵运算，矩阵分解，线性方程组求解，最小二乘问题，本征值问题，奇异值问题等，具有高效、可移植、可伸缩、高可靠性等优点，利用它的求解库可以开发出基于线性代数运算的并行应用程序。
ScaLAPACK 的主要思想是：
- 以一种块状循环分布的方式在各个进程之间分布数据矩阵；
- 使用块状划分的算法以尽量保证数据的重用性；
- 设计良好的底层模块使得使用高层模块编写的并行编程和普通串行串行基本一致。
软件等级
ScaLAPACK 是建立在一系列软件基础之上的，其软件等级如下：
ScaLAPACK 软件等级
上图中在水平线以下标记为 local 的软件成分是单处理器/单进程调用的，数据只存储在单进程上；在水平线以上标记为 global 的软件成分一般是同步并行调用的，其数据（矩阵或向量）分布在多个处理器/多个进程上。
其中的主要成分为：
- BLAS （Basic Linear Algebra Subprograms），包含很多常用的线性代数运算子程序，如向量点积，矩阵和向量乘积，矩阵和矩阵乘积等；
- LAPACK （Linear Algebra PACKage），包含一系列的程序，可以求解如线性方程组，最小二乘问题，本征值问题，奇异值问题等，通过调用 BLAS 完成大部分工作以获得高的运算性能；
- BLACS （Basic Linear Algebra Communication Subprograms），是一个专门为线性代数运算而设计的消息传递库；
- PBLAS （Parallel BLAS），为 ScaLAPACK 而设计的一个分布式内存 BLAS 库。
进程网格和块状循环分布
进程网格类似于我们前面介绍过的虚拟进程拓扑的二维笛卡尔拓扑，实际上是将各个进程映射成一个 p × q 的二维数组（矩阵），比如说由 8 个进程创建一个 2 × 4 进程网格，其排列如下：
2 × 4 进程网格
在调用 ScaLAPACK 的相关例程进行线性代数运算之前，需要将数据（矩阵或者向量）分布到进程网格上，数据是以一种块状循环的方式进行分布的。下图展示了将一个 8 × 8 的数据矩阵以块状循环方式分布到一个 2 × 3 进程网格上的结果，可见分布后每个进程本地的子数据矩阵是原整体矩阵的并不连续的部分，如进程 P02 的本地数据是原整体矩阵的 1，3，5，7 行和 3，6 列。
块状循环分布
使用步骤
使用 ScaLAPACK 求解线性代数问题一般分为以下几个步骤：
- 初始化进程网格；
- 将数据（矩阵或向量）按照块状循环方式分布到进程网格上；
- 调用 ScaLAPACK 求解例程；
- 释放进程网格。
以上非常简要地介绍了 ScaLAPACK 软件，更多的内容可以参考 Netlib 的 ScaLAPACK 或 Intel MKL 的 ScaLAPACK 介绍。虽然 ScaLAPACK 在设计上作了很多工作使其方法接口与 LAPACK 尽量保持一致，但是直接使用 Fortran 或 C 语言按照以上步骤使用 ScaLAPACK 仍然是一件比较麻烦和容易出错的事情，就好比我们使用 numpy.linalg 或 scipy.linalg （在底层调用 BLAS 和 LAPACK）中的相关函数比直接调用 BLAS 和 LAPACK 中的相关例程要容易和方便的多，我们也希望使用一个 Python 包装之后的 ScaLAPACK，在下一篇中我们就将介绍这样一个工具 scalapy。
