Basic Linear Algebra Subprograms

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

BLAS

最新版	3.10.0 / 2021年7月 (2021-07)
プログラミング 言語	Fortran
種別	数値解析ソフトウェア
公式サイト	BLAS (Basic Linear Algebra Subprograms)
(テンプレートを表示)

BLASの関数を多用するソフトウェアにおいてBLAS実装（ライブラリ）の質は速度に直結する。高度な最適化は実装が動くハードウェアにも依存するため、特定CPUに特化したライブラリが提供される場合もある（インテルCPU向け: Intel Math Kernel Library）。オープンソースの最適化 BLAS 実装として OpenBLAS や (ATLAS)（英語版） がある。

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

機能

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

Level 1

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

${\displaystyle {\boldsymbol {y}}\leftarrow \alpha {\boldsymbol {x}}+{\boldsymbol {y}}\!}$ 

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

Level 2

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

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

GEMV

一般行列ベクトル積（英: general matrix vector products; GEMV）は一般行列（GE）を用いた行列ベクトル積（MV）である^[7]。すなわち次の演算である（${\displaystyle A}$  はGeneral Matrix）。

${\displaystyle {\boldsymbol {y}}\leftarrow \alpha A{\boldsymbol {x}}+\beta {\boldsymbol {y}}\!}$ 

Level 3

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

${\displaystyle C\leftarrow \alpha AB+\beta C\!}$ 

また、${\displaystyle B\leftarrow \alpha T^{-1}B}$  を三角行列 ${\displaystyle T}$  について解く演算なども含まれる。このレベルにはよく使われる汎用行列乗算（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 

Sparse BLAS

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

SpMV

疎行列ベクトル積（英: sparse matrix vector products; SpMV）は疎行列（Sp）を用いた行列ベクトル積（MV）である^[9]。すなわち次の演算である（${\displaystyle A}$  は Sparse Matrix）。

${\displaystyle {\boldsymbol {y}}\leftarrow \alpha A{\boldsymbol {x}}+\beta {\boldsymbol {y}}\!}$ 

PBLAS

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

実装

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

reference BLAS

netlib による公式リファレンス実装。C言語版とFORTRAN版がある。

Accelerate

Appleによる OS X 向けフレームワーク。PowerPC と Intel Core 向けに最適化されたBLASとLAPACKを含む。

ACML

AMD Core Math Library。Athlon および Opteron 上のLinuxとWindowsをサポート。

ATLAS

オープンソース実装（C言語とFortran 77）

clBLAS

AMD が提供する、主に GPU 向けの OpenCL 上で動くオープンソース実装。

cuBLAS

NVIDIA CUDA SDK には、NVIDIA の GPU 上で動作するBLAS機能（C言語インタフェース）が含まれる。

ESSL

IBMの Engineering and Scientific Subroutine Library。PowerPC上のAIXおよびLinuxで動作。

GotoBLAS

後藤和茂が GotoBLAS を開発し、OpenBLAS へと引き継がれている。GotoBLAS は2010年2月が最後のバージョン。

HP MLIB

ヒューレット・パッカードの数学ライブラリ。IA-64/PA-RISC/x86/Opteron上のHP-UXおよびLinuxで動作。

Intel Math Kernel Library

インテルによる実装。x86, x86-64, IA64, Xeon Phi 上の Linux/Windows/macOS で動作。

MathKeisan

日本電気による実装。NEC SX上のSUPER-UXと、Itanium上のLinuxをサポート。

OpenBLAS

オープンソース実装。x86, x86-64, MIPS, ARM, ARM64 上の Linux, Microsoft Windows, macOS, FreeBSD で動作。

PDLIB/SX

1994年に発表された日本電気の(SX-4)向け数学ライブラリ（パブリックドメイン）。現在は配布されていない。

SCSL

SGIの実装。LAPACK も含む。IRIX上で動作。

Sun Performance Linaray

SPARC/AMD64上の Solaris 8, 9, 10 で動作する BLAS および LAPACK 実装。

(BLIS)（英語版）

BLASのスーパーセット。

BLASではないが類似ライブラリ

Elemental

(分散メモリ)（コンピュータ・クラスター）用の密行列・疎行列の線形代数および最適化ライブラリ。

GNU Scientific Library

C言語での実装。

uBLAS

BLAS機能を提供する汎用テンプレートクラスライブラリ。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 提唱論文

脚注

1. ^ "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).
2. ^ Lawson, et al. (1979).
3. ^ "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.
4. ^ "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.
5. ^ "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.
6. ^ "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.
7. ^ "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.
8. ^ Sparse BLAS: A Baseline Implementation of the BLAS Standard
9. ^ "疎行列ベクトル積 (SpMV) の実装について述べる." 大島, et al. (2015). 動的な並列実行気機構を用いたSpMV実装の性能評価. 情報処理学会研究報告. Vol2015-HPC-148, No.3.
10. ^ PBLAS Home Page

外部リンク

• BLAS FAQ
• BLAS operations 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