Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 15509] ファイルの概要

このコミットは、Go言語のランタイムパッケージ内のproc_test.goファイルに、行列乗算のベンチマークを追加するものです。proc_test.goは、Goランタイムのパフォーマンス特性、特にゴルーチン（goroutine）の作成やスケジューリング、並行処理の効率などを評価するためのテストやベンチマークが含まれるファイルです。このファイルに数値計算のベンチマークを追加することで、Goランタイムが大規模な計算負荷をどのように処理するか、特に並行処理の観点からその性能を測定する目的があります。

コミット

Goランタイムに、行列乗算のベンチマークを追加しました。

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/72b09bd7aefa1602a9c14c9006442d696d962def

元コミット内容

runtime: add matrix multiplication benchmark

R=golang-dev, r
CC=golang-dev
https://golang.org/cl/7431047

変更の背景

この変更の背景には、Goランタイムの並行処理能力と数値計算性能の評価があります。行列乗算は計算負荷が高く、並列化が可能な典型的なアルゴリズムです。このようなベンチマークをランタイムのテストスイートに追加することで、以下のような目的が考えられます。

  1. ゴルーチンのスケジューリング性能の評価: 行列乗算を再帰的に分割し、ゴルーチンを使って並列処理を行うことで、Goランタイムのゴルーチン生成、スケジューリング、同期のオーバーヘッドと効率を測定できます。
  2. 数値計算におけるGoの性能特性の把握: Goはシステムプログラミング言語として設計されていますが、科学技術計算やデータ処理の分野でも利用が広がっています。行列乗算のような基本的な数値計算のベンチマークは、Goがこれらのタスクでどの程度の性能を発揮できるかを示す指標となります。
  3. 将来的な最適化の指針: ベンチマークの結果は、ランタイムのボトルネックを特定し、将来的なパフォーマンス改善のための指針を提供します。例えば、特定の並行処理パターンが非効率であることが判明すれば、スケジューラやメモリ管理の改善に繋がる可能性があります。
  4. 既存のベンチマークの多様化: proc_test.goには既にゴルーチン作成などのベンチマークがありますが、行列乗算のような異なる計算特性を持つベンチマークを追加することで、より包括的な性能評価が可能になります。

前提知識の解説

Go言語のベンチマーク

Go言語の標準ライブラリには、testingパッケージが提供されており、ユニットテストだけでなくベンチマークテストも記述できます。

  • testing.B: ベンチマーク関数に渡される構造体で、ベンチマークの実行回数や時間計測を制御します。
  • b.N: ベンチマーク関数が実行される回数を示します。testingパッケージは、ベンチマークが安定した結果を出すまでb.Nの値を自動的に調整します。
  • b.StopTimer() / b.StartTimer(): ベンチマークの計測を一時停止/再開するために使用します。セットアップコードや結果の検証コードなど、ベンチマーク対象ではない処理の時間を計測から除外するために重要です。
  • go test -bench=.: ベンチマークを実行するためのコマンドです。

行列乗算 (Matrix Multiplication)

行列Aと行列Bの乗算Cは、Cの要素C[i][j]がAのi行目とBのj列目の要素の積の和として計算されます。 数学的には C_ij = Σ(A_ik * B_kj) と表されます。 サイズN×Nの2つの行列の乗算の計算量はO(N^3)です。これは、各要素の計算にN回の乗算とN-1回の加算が必要で、結果行列にはN^2個の要素があるためです。

分割統治法 (Divide and Conquer)

大きな問題を小さなサブ問題に分割し、それぞれのサブ問題を解決し、その結果を結合して元の問題の解を得るアルゴリズム設計パラダイムです。行列乗算においても、大きな行列を小さなブロックに分割し、再帰的に乗算を行うことで、並列化の機会を増やすことができます。

ゴルーチン (Goroutine) とチャネル (Channel)

Go言語の並行処理の基本要素です。

  • ゴルーチン: 軽量なスレッドのようなもので、goキーワードを使って関数を並行実行します。OSのスレッドよりもはるかに少ないメモリで作成でき、Goランタイムのスケジューラによって効率的に管理されます。
  • チャネル: ゴルーチン間で安全にデータを送受信するための通信メカニズムです。このコミットでは、chan struct{}（空の構造体のチャネル）がゴルーチンの完了通知（同期）のために使用されています。

技術的詳細

このベンチマークは、行列乗算を分割統治法とゴルーチンを用いた並列処理で実装し、その性能を測定します。

BenchmarkMatmult(b *testing.B) 関数

  • b.StopTimer(): ベンチマークの計測を一時停止します。これは、行列の初期化処理がベンチマークの対象ではないためです。
  • n := int(math.Cbrt(float64(b.N))) + 1: ここが重要なポイントです。行列乗算はO(N^3)の計算量を持つため、b.N（ベンチマークの実行回数）が直接行列のサイズNに対応すると、Nが少し大きくなるだけで計算時間が爆発的に増加してしまいます。testingパッケージはb.Nを自動調整しますが、これはベンチマーク関数全体がO(b.N)の計算量を持つことを前提としています。
    • matmult関数はO(N^3)なので、b.N回の操作を達成するためには、行列のサイズNはb.Nの立方根に比例する必要があります。
    • math.Cbrtは立方根を計算します。これにより、b.Nが大きくなっても、行列のサイズNは緩やかに増加し、ベンチマークの実行時間が現実的な範囲に収まるように調整されます。+ 1は、Nが少なくとも1になるようにするためのオフセットです。
  • A, B, C := makeMatrix(n), makeMatrix(n), makeMatrix(n): N×Nの行列A, B, Cを初期化します。
  • b.StartTimer(): 行列乗算の実行直前に計測を再開します。
  • matmult(nil, A, B, C, 0, n, 0, n, 0, n, 8): 実際の行列乗算関数を呼び出します。nilは完了通知チャネルが不要であることを示し、8は分割の閾値（threshold）です。

makeMatrix(n int) Matrix 関数

  • N×Nのfloat64型の行列を作成し、m[i][j] = float64(i*n + j)という単純な値で初期化します。これはベンチマークのためのダミーデータであり、実際の計算結果の正確性はここでは重要ではありません。

matmult(...) 関数

この関数は、行列乗算を再帰的に実行するコアロジックです。分割統治法に基づいており、行列をサブブロックに分割し、必要に応じてゴルーチンを使って並列処理を行います。

  • 引数:

    • done chan<- struct{}: 完了通知用のチャネル。ゴルーチンとして呼び出された場合に、処理完了を通知するために使用されます。
    • A, B, C Matrix: 入力行列A, Bと結果行列C。
    • i0, i1, j0, j1, k0, k1: 現在処理している行列のサブブロックの範囲を示すインデックス。
    • threshold int: 分割を停止し、直接計算に移行するサブブロックの最小サイズ。

  • 分割ロジック:

    • di, dj, dk: 現在のサブブロックの各次元のサイズ。
    • if di >= dj && di >= dk && di >= threshold: i次元（行）が最も大きく、かつ閾値以上の場合、i次元で2分割します。
      • go matmult(done1, ...): 最初の半分を新しいゴルーチンで並行実行します。
      • matmult(nil, ...): 残りの半分を現在のゴルーチンで実行します。
      • <-done1: 新しいゴルーチンの完了を待ちます。これにより、両方のサブ問題が完了してから次のステップに進むことが保証されます。
    • else if dj >= dk && dj >= threshold: j次元（列）が最も大きく、かつ閾値以上の場合、j次元で2分割します。同様に並行実行します。
    • else if dk >= threshold: k次元（内積のループ変数）が最も大きく、かつ閾値以上の場合、k次元で2分割します。
      • 重要: // deliberately not parallel because of data races とコメントされています。k次元での分割は、C[i][j] += A[i][k] * B[k][j]という加算代入操作が複数のゴルーチンから同時に同じC[i][j]にアクセスする可能性があり、データ競合（data race）を引き起こすため、意図的に並列化されていません。これは、並行処理における共有リソースへのアクセス管理の重要性を示しています。

  • 直接計算:

    • else: サブブロックのサイズがthresholdを下回った場合、再帰を停止し、3重ループを使って直接行列乗算を実行します。
    • C[i][j] += A[i][k] * B[k][j]: 行列乗算の基本的な計算式です。

  • 完了通知:

    • if done != nil: doneチャネルが渡されている場合（つまり、このmatmult呼び出しがゴルーチンとして実行された場合）、done <- struct{}{}を送信して完了を通知します。

この実装は、Goのゴルーチンとチャネルを使った並行処理の典型的なパターンを示しており、計算集約型タスクにおけるGoのパフォーマンス特性を評価するのに適しています。

コアとなるコードの変更箇所

src/pkg/runtime/proc_test.go ファイルに以下の変更が加えられました。

  1. import ("math") の追加。
  2. Matrix 型の定義 (type Matrix [][]float64)。
  3. BenchmarkMatmult ベンチマーク関数の追加。
  4. makeMatrix ヘルパー関数の追加。
  5. matmult 行列乗算ロジック関数の追加。
--- a/src/pkg/runtime/proc_test.go
+++ b/src/pkg/runtime/proc_test.go
@@ -5,6 +5,7 @@
 package runtime_test
 
  import (
+	"math"
  	"runtime"
  	"sync/atomic"
  	"testing"
@@ -225,3 +226,67 @@ func benchmarkCreateGoroutines(b *testing.B, procs int) {
  		<-c
  	}
  }
+
+type Matrix [][]float64
+
+func BenchmarkMatmult(b *testing.B) {
+	b.StopTimer()
+	// matmult is O(N**3) but testing expects O(b.N),
+	// so we need to take cube root of b.N
+	n := int(math.Cbrt(float64(b.N))) + 1
+	A := makeMatrix(n)
+	B := makeMatrix(n)
+	C := makeMatrix(n)
+	b.StartTimer()
+	matmult(nil, A, B, C, 0, n, 0, n, 0, n, 8)
+}
+
+func makeMatrix(n int) Matrix {
+	m := make(Matrix, n)
+	for i := 0; i < n; i++ {
+		m[i] = make([]float64, n)
+		for j := 0; j < n; j++ {
+			m[i][j] = float64(i*n + j)
+		}
+	}
+	return m
+}
+
+func matmult(done chan<- struct{}, A, B, C Matrix, i0, i1, j0, j1, k0, k1, threshold int) {
+	di := i1 - i0
+	dj := j1 - j0
+	dk := k1 - k0
+	if di >= dj && di >= dk && di >= threshold {
+		// divide in two by y axis
+		mi := i0 + di/2
+		done1 := make(chan struct{}, 1)
+		go matmult(done1, A, B, C, i0, mi, j0, j1, k0, k1, threshold)
+		matmult(nil, A, B, C, mi, i1, j0, j1, k0, k1, threshold)
+		<-done1
+	} else if dj >= dk && dj >= threshold {
+		// divide in two by x axis
+		mj := j0 + dj/2
+		done1 := make(chan struct{}, 1)
+		go matmult(done1, A, B, C, i0, i1, j0, mj, k0, k1, threshold)
+		matmult(nil, A, B, C, i0, i1, mj, j1, k0, k1, threshold)
+		<-done1
+	} else if dk >= threshold {
+		// divide in two by "k" axis
+		// deliberately not parallel because of data races
+		mk := k0 + dk/2
+		matmult(nil, A, B, C, i0, i1, j0, j1, k0, mk, threshold)
+		matmult(nil, A, B, C, i0, i1, j0, j1, mk, k1, threshold)
+	} else {
+		// the matrices are small enough, compute directly
+		for i := i0; i < i1; i++ {
+			for j := j0; j < j1; j++ {
+				for k := k0; k < k1; k++ {
+					C[i][j] += A[i][k] * B[k][j]
+				}
+			}
+		}
+	}
+	if done != nil {
+		done <- struct{}{}
+	}
+}

コアとなるコードの解説

type Matrix [][]float64

Matrix型は、float64型のスライス（行）のスライスとして定義されており、2次元の行列を表現します。Goでは多次元配列を直接サポートしていないため、このようにスライスのスライスを使って行列を表現するのが一般的です。

func BenchmarkMatmult(b *testing.B)

この関数は、Goのベンチマークテストの規約に従って定義されています。

  • b.StopTimer()とb.StartTimer()を使って、行列の初期化時間を計測から除外しています。
  • n := int(math.Cbrt(float64(b.N))) + 1によって、ベンチマークの実行回数b.Nに応じて行列のサイズnを動的に調整しています。これにより、O(N^3)の計算量を持つ行列乗算が、b.Nに対して適切な時間で実行されるようにスケーリングされます。
  • matmult関数を呼び出して、実際の行列乗算を実行します。最初の引数nilは、この呼び出しがトップレベルであり、完了通知チャネルが不要であることを示します。最後の引数8は、再帰的な分割を停止し、直接計算に移行する際のサブブロックの最小サイズ（閾値）です。

func makeMatrix(n int) Matrix

指定されたサイズnの正方行列を作成し、各要素をfloat64(i*n + j)という単純な値で初期化します。これはベンチマークのためのダミーデータ生成であり、特定の数学的特性を持つ行列である必要はありません。

func matmult(done chan<- struct{}, A, B, C Matrix, i0, i1, j0, j1, k0, k1, threshold int)

この関数は、行列乗算の分割統治アルゴリズムを実装しています。

  • 再帰的な分割:
    • 行列の3つの次元（i、j、k）のうち、最も大きい次元を2分割します。
    • 分割されたサブ問題のうち、片方を新しいゴルーチンで並行実行し、もう片方を現在のゴルーチンで実行します。
    • done1 := make(chan struct{}, 1)と<-done1を使って、並行実行されたゴルーチンの完了を同期します。これにより、すべてのサブ問題が完了するまで親の処理が待機します。
  • データ競合の回避: k次元での分割は、C[i][j] += A[i][k] * B[k][j]という加算代入操作が複数のゴルーチンから同時に同じC[i][j]要素にアクセスする可能性があり、データ競合を引き起こすため、意図的に並列化されていません。これは、並行プログラミングにおいて共有状態の変更を伴う操作には注意が必要であることを示しています。
  • 直接計算への移行: サブブロックのサイズがthreshold以下になった場合、再帰を停止し、3重ループによる直接的な行列乗算を実行します。thresholdの値は、並列化のオーバーヘッドと直接計算の効率のバランスを取るために調整される可能性があります。
  • 完了通知: doneチャネルがnilでない場合（つまり、この関数がゴルーチンとして呼び出された場合）、done <- struct{}{}を送信して、呼び出し元のゴルーチンに処理が完了したことを通知します。

このコードは、Goの並行処理モデル（ゴルーチンとチャネル）を効果的に利用して、計算集約型タスクを並列化する方法の具体的な例を提供しています。

関連リンク

参考にした情報源リンク

  • Go言語のtestingパッケージに関する公式ドキュメント
  • 行列乗算のアルゴリズムに関する一般的な情報
  • Go言語における並行処理（ゴルーチンとチャネル）に関する一般的な情報
  • Go言語のソースコード（src/pkg/runtime/proc_test.go）