Basic Linear Algebra Subprograms

Basic Linear Algebra SubprogramsBLAS)は数値線形代数の基礎的演算に必要な関数を定義する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 実装として OpenBLASATLAS英語版 がある。

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

機能編集

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

Level 1編集

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

 

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

Level 2編集

Level 2 BLAS  の行列を含み   オーダーを持つ演算のセットである[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]。すなわち次の演算である(  は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

Sparse BLAS編集

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

SpMV編集

疎行列ベクトル積: sparse matrix vector products; SpMV)は疎行列Sp)を用いた行列ベクトル積(MV)である[9]。すなわち次の演算である(  は Sparse Matrix)。

 

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 向けフレームワーク。PowerPCIntel Core 向けに最適化されたBLASとLAPACKを含む。
ACML
AMD Core Math Library。Athlon および Opteron 上のLinuxWindowsをサポート。
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 実装。

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

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

関連項目編集

参考文献編集

  • 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