Basic Linear Algebra Subprograms

Basic Linear Algebra Subprograms（BLAS）は数値線形代数の基礎的演算に必要な関数を定義するAPIである"This paper describes a package, called the BLAS, of thirty-eight FORTRAN-callable subprograms for basic operations of numerical linear algebra." Lawson, et al. (1979).。ベクトル・行列演算を含む38の関数からなるLevel 1 BLASが1979年に発表されたのちLawson, et al. (1979).、Level 2 および Level 3 まで拡張された。多数の実装が作成・整備され続けており、この分野におけるデファクトスタンダードとなっている。BLASの基礎演算を利用してLAPACKなどの上位パッケージが構築されており、科学技術計算・高性能計算で多用される。

BLASの関数を多用するソフトウェアにおいてBLAS実装（ライブラリ）の質は速度に直結する。高度な最適化は実装が動くハードウェアに依存するため、多くのハードウェアベンダーが自社デバイスに特化したライブラリを提供している（インテル：Intel oneAPI Math Kernel Library）。オープンソースの最適化 BLAS 実装として OpenBLAS などがある。

LINPACK ベンチマークの性能は、BLAS のサブルーチンである DGEMM（倍精度汎用行列乗算）の性能に大きく影響される。

対応しているデータ型は単精度浮動小数点数と倍精度浮動小数点数。近年 CPU および GPU で広く実装されている bfloat16 は、各 BLAS 実装が独自拡張OpenBLAS Extensions · OpenMathLib/OpenBLAS Wiki - GitHubとして実装していていて、今のところ、公式の BLAS 実装では実装されていない。

 機能 
BLASの機能は以下の3レベルに分類される。

 Level 1 
このレベルには、以下のような形式のベクトル演算が含まれる。

他にもドット積やノルムなどが含まれる。

 Level 2 
Level 2 BLAS は  の行列を含み  のオーダーを持つ演算のセットである"Level 2 BLAS involve O(mn) scalar operations, where m and n are the dimensions of the matrix involved." p.2 of Dongarra, et al. (1988). An Extended Set of Fortran Basic Linear Algebra Subprograms. ACM Trans. Math. Software.。元々の BLAS（Level 1 BLAS）を拡張し1段階抽象度の高い演算セットとして提案された"In this paper we refer to the existing BLAS of Lawson et al. as Level 1 BLAS, and the new extended set as Level 2 BLAS. ... Hence, in a natural sense, Level 2 BLAS are performing basic operations at one level higher than Level 1 BLAS." p.2 of Dongarra, et al. (1988). An Extended Set of Fortran Basic Linear Algebra Subprograms. ACM Trans. Math. Software.。

行列の種類を示す記号には GE (GEneral matrix)、HE (HErmitian matrix)、SY (SYmmetric matrix)、TR (TRiangular matrix) などがある"Characters two and three in the name denote the kind of matrix involved, as follows" p.4 of Dongarra, et al. (1988). An Extended Set of Fortran Basic Linear Algebra Subprograms. ACM Trans. Math. Software.。演算を示す記号には MV (matrix-vector product)、 R (Rank-one update)、 R2 (Rank-two update)、 SV (solving a system of linear equations) がある"The fourth and fifth characters in the name denote the type of operation, as follows" p.4 of Dongarra, et al. (1988). An Extended Set of Fortran Basic Linear Algebra Subprograms. ACM Trans. Math. Software.。

 GEMV 
一般行列ベクトル積（; GEMV）は一般行列（GE）を用いた行列ベクトル積（MV）である"General matrix vector products. ... For a general matrix,    _GEMV" p.9 of Dongarra, et al. (1988). An Extended Set of Fortran Basic Linear Algebra Subprograms. ACM Trans. Math. Software.。すなわち次の演算である（ はGeneral Matrix）。

 Level 3 
このレベルには、以下のような形式の行列同士の演算が含まれる。

また、 を三角行列  について解く演算なども含まれる。このレベルにはよく使われる汎用行列乗算（GEMM）操作が含まれる。

 API 
BLASはAPIであり、各演算関数を次のように定義する。

 GEMM 
各行列の変換フラグ・次元・係数・アクセスオフセットを引数に取り、行列積和演算を実行、演算結果がCへ書き出される。Trans = "N" | "T" | "C"
T = float32 | float64 | complex

def _GEMM<T>(
    TRANSA: Trans,  # Flag of A transformation (None, Transpose, Conjugate_transpose)
    TRANSB: Trans,  # Flag of B transformation (None, Transpose, Conjugate_transpose)
    M: int,         # The number of C row == (A row (TRANSA=N) OR A col (TRANSA=T))
    N: int,         # The number of C col == (B col (TRANSA=N) OR B row (TRANSA=T))
    K: int,         # The number of A_col & B_row (TRANSA=N) OR A_row & B_col (TRANSA=T)
    ALPHA: T,       # a scalar of "C <- aAB + bC"
    A: Matrix[T],   # A matrix of "C <- aAB + bC"
    LDA: int,       # Leading dimension of A
    B: Matrix[T],   # B matrix of "C <- aAB + bC"
    LDB: int,       # Leading dimension of B
    BETA: T,        # b scalar of "C <- aAB + bC"
    C: Matrix[T],   # C matrix of "C <- aAB + bC" (scaled accumulator)
    LDC: int
) -> None

高速に計算するにはキャッシュヒット率を高める必要がある。OpenBLASの元となったGotoBLASを開発した後藤和茂が2008年にその手法を説明した論文を書いている。また、それを元にAlgorithmicaに分かりやすく解説した文章がある。BLASには、行列積、つまり、かけ算して足し算する計算しか含まれていないが、この手法は任意の二項演算子に対して使用可能である。

 Sparse BLAS 
Sparse BLASは、疎行列を対象としたBLASであるSparse BLAS: A Baseline Implementation of the BLAS Standard。疎行列は格納形式と演算実装を工夫することで高効率の計算が可能である。Sparse BLAS はこの用途に特化した実装をもつBLASである。疎行列を示す記号には Sp (Sparse) が用いられる。

 SpMV 
疎行列ベクトル積（; SpMV）は疎行列（Sp）を用いた行列ベクトル積（MV）である"疎行列ベクトル積 (SpMV) の実装について述べる." 大島, et al. (2015). 動的な並列実行気機構を用いたSpMV実装の性能評価. 情報処理学会研究報告. Vol2015-HPC-148, No.3.。すなわち次の演算である（ は Sparse Matrix）。

 PBLAS 
PBLASは、コンピュータ・クラスター（並列計算）向けの並列BLAS（Parallel Basic Linear Algebra Subprograms）PBLAS Home Page。MPI などの上で動作する BLACS を通信プロトコルとして利用する。

 実装 
BLAS演算は多数の積和演算からなる。またLevel 2およびLevel 3ではベクトル・行列を扱う。ゆえに計算機におけるBLAS実装ではSIMD命令をもちいた最適化が可能である。利用される命令とその特性は命令セットアーキテクチャにより異なり、またメモリ等の実行環境によっても最適設定は異なる。その結果、特定CPUに特化したBLAS実装や実行時に環境へのチューニングをおこなうBLASなど、異なる特性をもつ様々なBLAS実装が存在する。

リファレンス実装もBLASとLAPACKをまとめて実装しているが、多くのBLASライブラリも同様にLAPACKを含めて実装している。

特定のデバイスに限定していない汎用の実装
 Reference BLAS netlib による公式リファレンス実装。C言語版とFORTRAN版がある。BLASとLAPACKがまとめて実装されている。DebianやUbuntuなどでは、OpenBLASなどをインストールしない限りこれが使われる。
 BLAS++ BLASのC++ API。C言語版のAPIと1対1で対応する。Intel, AMD, NVIDIA, IBM などのハードウェアベンダーの出しているBLAS実装を利用して動作する。
  BLASのスーパーセット。
 OpenBLAS オープンソース実装。x86, x86-64, MIPS32, MIPS64, ARM32, ARM64, POWER, IBM zEnterprise, RISC-V 上の Linux, Microsoft Windows, macOS, FreeBSD, OpenBSD, NetBSD, DragonFly BSD, Android, iOS, AIX, Haiku, Solaris で動作。

ハードウェアベンダーによる、特定のデバイス向けの実装
 Accelerate Apple による自社デバイス用の自社OS（macOSやiOSなど）向けフレームワーク。BLAS と LAPACK を含む。
 AMD Optimizing CPU Libraries (AOCL) AMD の CPU (EPYC, Ryzen, Ryzen Threadripper) 上のLinuxとWindowsをサポート。
 Arm Performance Libraries ARM64上で動作。
 cuBLAS NVIDIA CUDA SDK には、NVIDIA の GPU 上で動作するBLAS機能（C言語インタフェース）が含まれる。
 Engineering and Scientific Subroutine Library (ESSL) IBMによる実装。POWER上のAIXおよびLinuxで動作。
 Intel oneAPI Math Kernel Library インテルによる実装。インテルの CPU および GPU をサポート。Linux/Windows で動作。
 NEC Numeric Library Collection 日本電気による実装。NEC SX用。旧称MathKeisan。
 Oracle Developer Studio Performance Library SPARC と x86-64 上の Oracle Solaris と Linux で動作する BLAS および LAPACK 実装。旧称Sun Performance Library。
 rocBLAS AMD の GPU 向けのオープンソース実装。

かつて開発されていたライブラリ
 Automatically Tuned Linear Algebra Software (ATLAS) オープンソース実装（C言語とFortran 77）
 clBLAS AMD が提供する、主に GPU 向けの OpenCL 上で動くオープンソース実装。2017年が最後のバージョン。後継はrocBLAS。
 GotoBLAS 後藤和茂が GotoBLAS を開発し、OpenBLAS へと引き継がれている。GotoBLAS は2010年2月が最後のバージョン。
 Hewlett-Packard Mathematical Software Library (HP MLIB) ヒューレット・パッカードの数学ライブラリ。IA-64/PA-RISC/x86/Opteron上のHP-UXおよびLinuxで動作。
 PDLIB/SX 1994年に発表された日本電気のSX-4向け数学ライブラリ（パブリックドメイン）。現在は配布されていない。
 Scientific Computing Software Library (SCSL) SGIの実装。LAPACK も含む。IRIX上で動作。

 BLASではないが類似ライブラリ 
 Elemental 分散メモリ（コンピュータ・クラスター）用の密行列・疎行列の線形代数および最適化ライブラリ。
 GNU Scientific Library C言語での実装。
 uBLAS BLAS機能を提供する汎用C++テンプレートクラスライブラリ。Boostライブラリの一部。高性能を追求するというよりも、C++の最新機能を使ってアルゴリズムを正しく実装することに注力している。

 関連項目 
数値解析
LAPACK

 脚注 

 参考文献 
 C. L. Lawson, R. J. Hanson, D. R. Kincaid, F. T. Krogh. (1979). Basic Linear Algebra Subprograms for Fortran Usage. doi: 10.1145/355841.355847
 BLAS (Level 1 BLAS) 提唱論文
 Dongarra, Croz, Hammarling and R. J. Hanson. (1988). An Extended Set of FORTRAN Basic Linear Algebra Subprograms. doi: 10.1145/42288.42291
 Level 2 BLAS 提唱論文

 外部リンク 
BLAS FAQ
 GNU Scientific Library reference manual
BLAS Quick Reference Guide LAPACK Users' Guide
 Lawson Oral History BLAS設計者の1人 Charles L. Lawson のインタビュー。by Thomas Haigh, 6 and 7 November, 2004, San Clemente, California. Society for Industrial and Applied Mathematics, Philadelphia, PA.
 Dongarra Oral History BLAS、LINPACK、ATLAS 設計に関わった Jack J. Dongarra のインタビュー。 by Thomas Haigh, 26 April, 2005, University of Tennessee, Knoxville TN. Society for Industrial and Applied Mathematics, Philadelphia, PA

Category:数値解析ソフトウェア
Category:パブリックドメインソフトウェア