Basic Linear Algebra Subprograms

**Basic Linear Algebra Subprograms**（**BLAS**）は数値線形代数の基礎的演算に必要な関数を定義するAPIである。ベクトル・行列演算を含む38の関数からなるLevel 1 BLASが1979年に発表されたのち、Level 2 および Level 3 まで拡張された。多数の実装が作成・整備され続けており、この分野におけるデファクトスタンダードとなっている。BLASの基礎演算を利用してLAPACKなどの上位パッケージが構築されており、科学技術計算・高性能計算で多用される。

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

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

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

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

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

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

### Level 2
**Level 2 BLAS** は m \times n の行列を含み O(mn) *の*オーダーを持つ演算のセットである。元々の BLAS（Level 1 BLAS）を拡張し1段階抽象度の高い演算セットとして提案された。

行列の種類を示す記号には *GE* (GEneral matrix)、*HE* (HErmitian matrix)、*SY* (SYmmetric matrix)、*TR* (TRiangular matrix) などがある。演算を示す記号には *MV* (matrix-vector product)、 *R* (Rank-one update)、 *R2* (Rank-two update)、 *SV* (solving a system of linear equations) がある。

#### GEMV
**一般行列ベクトル積**（; **GEMV**）は一般行列（*GE*）を用いた行列ベクトル積（*MV*）である。すなわち次の演算である（A はGeneral Matrix）。

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

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

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

### GEMM
各行列の変換フラグ・次元・係数・アクセスオフセットを引数に取り、行列積和演算を実行、演算結果がCへ書き出される。
```python3
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 はこの用途に特化した実装をもつBLASである。疎行列を示す記号には *Sp* (Sparse) が用いられる。

### SpMV
**疎行列ベクトル積**（; **SpMV**）は疎行列（*Sp*）を用いた行列ベクトル積（*MV*）である。すなわち次の演算である（A は Sparse Matrix）。

## PBLAS
PBLASは、コンピュータ・クラスター（並列計算）向けの並列BLAS（Parallel Basic Linear Algebra Subprograms）。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: 
** BLAS (Level 1 BLAS) 提唱論文
* Dongarra, Croz, Hammarling and R. J. Hanson. (1988). *An Extended Set of FORTRAN Basic Linear Algebra Subprograms*. doi: 
** 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