Goで並列saxpyを実装してもコア全体でうまくスケーリングできない

Question

saxpyの実装を実装しようとしていますが、両方ともブロックされていて、自分のマシンで使用できる8コアを使って並列計算できます。私は、自分のマシンのL1キャッシュに収まる小さいサイズのベクトルxとy（分割256kB - 128kBデータ、128kBコード）を連続して計算できるという前提から始めました。この仮定をテストするために、saxpy（BSS）のブロックされたシリアルバージョンとsaxpy（BPS）のブロックされた並列バージョンであるsaxpyの2つの実装を書いた。ブロッキングアルゴリズムは、ベクトルのサイズが4096要素より長い場合にのみ使用されます。次は実装されている：

const cachecap = 32*1024/8 // 4096 
func blocked_serial_saxpy(a float64, x []float64, incx int, b float64, y []float64, incy int, z []float64, incz int) { 
    zn := len(z) 
    //fmt.Println("zn: ", zn) 
    if zn <= cachecap { 
     serial_saxpy(a, x, incx, b, y, incy, z, incz) 
     return 
    } 

    nblocks := zn/cachecap + 1 
    //fmt.Println("nblocks: ", nblocks) 
    for i := 0; i < nblocks; i++ { 
     beg := i * cachecap 
     end := (i + 1) * cachecap 
     if end >= zn { 
      end = zn 
     } 
     //fmt.Println("beg, end: ", beg, end) 
     xb := x[beg:end] 
     yb := y[beg:end] 
     zb := z[beg:end] 
     serial_saxpy(a, xb, incx, b, yb, incy, zb, incz) 
    } 
} 
func blocked_parallel_saxpy(a float64, x []float64, incx int, b float64, y []float64, incy int, z []float64, incz int) { 
    zn := len(z) 
    if zn <= cachecap { 
     //fmt.Println("zn <= cachecap: using serial_saxpy") 
     serial_saxpy(a, x, incx, b, y, incy, z, incz) 
     return 
    } 

    nblocks := zn/cachecap + 1 
    //fmt.Println("nblocks: ", nblocks) 
    nworkers := runtime.GOMAXPROCS(0) 
    if nblocks < nworkers { 
     nworkers = nblocks 
    } 
    //fmt.Println("nworkers: ", nworkers) 

    //buf := blockSize*nworkers 
    //if buf > nblocks { 
    // buf = nblocks 
    //} 
    //sendchan := make(chan block, buf) 
    sendchan := make(chan block, nblocks) 

    var wg sync.WaitGroup 
    for i := 0; i < nworkers; i++ { 
     wg.Add(1) 
     go func() { 
      defer wg.Done() 
      a, b := a, b 
      incx, incy, incz := incx, incy, incz 
      for blk := range sendchan { 
       beg, end := blk.beg, blk.end 
       serial_saxpy(a, x[beg:end], incx, b, y[beg:end], incy, z[beg:end], incz) 
      } 
     }() 
    } 

    for i := 0; i < nblocks; i++ { 
     beg := i * cachecap 
     end := (i + 1) * cachecap 
     if end >= zn { 
      end = zn 
     } 
     //fmt.Println("beg:end", beg, end) 
     sendchan <- block{beg, end} 
    } 
    close(sendchan) 
    wg.Wait() 
} 

func serial_saxpy(a float64, x []float64, incx int, b float64, y []float64, incy int, z []float64, incz int) { 
    if incx <= 0 || incy <= 0 || incz <= 0 { 
     panic("AxpBy: zero or negative increments not supported") 
    } 

    n := len(z)/incz 
    if incx == 1 && incy == 1 && incz == 1 { 
     if a == 1 && b == 1 { 
      for i := 0; i < n; i++ { 
       z[i] = x[i] + y[i] 
      } 
      return 
     } 

     if a == 0 && b == 1 { 
      copy(z, y) 
      //for i := 0; i < n; i++ { 
      // z[i] = y[i] 
      //} 
      return 
     } 

     if a == 1 && b == 0 { 
      copy(z, x) 
      //for i := 0; i < n; i++ { 
      // z[i] = x[i] 
      //} 
      return 
     } 

     if a == 0 && b == 0 { 
      return 
     } 

     for i := 0; i < n; i++ { 
      z[i] = a*x[i] + b*y[i] 
     } 
     return 
    } 

    // unequal increments or equal increments != 1 
    ix, iy, iz := 0, 0, 0 
    if a == 1 && b == 1 { 
     for i := 0; i < n; i, ix, iy, iz = i+1, ix+incx, iy+incy, iz+incz { 
      z[iz] = x[ix] + y[iy] 
     } 
     return 
    } 

    if a == 0 && b == 1 { 
     for i := 0; i < n; i, ix, iy, iz = i+1, ix+incx, iy+incy, iz+incz { 
      z[iz] = y[iy] 
     } 
     return 
    } 

    if a == 1 && b == 0 { 
     for i := 0; i < n; i, ix, iy, iz = i+1, ix+incx, iy+incy, iz+incz { 
      z[iz] = x[ix] 
     } 
     return 
    } 

    if a == 0 && b == 0 { 
     return 
    } 

    for i := 0; i < n; i, ix, iy, iz = i+1, ix+incx, iy+incy, iz+incz { 
     z[iz] = a*x[ix] + b*y[iy] 
    } 
} 

私は、3つの関数blocked_serial_saxpy、blocked_pa​​rallel_saxpyとserial_saxpyのためのベンチマークを書きました。以下の画像は、それぞれのベクトルの大きさの1E3、1E4、1E5、2E5、3E5、4E5、6E5、8E5および1E6とベンチマークの結果を示しています

私はblocked_pa​​rallel_saxpy実装のパフォーマンスを視覚化するには、I結果をプロットしたところ、これは私が得たものです： プロットを見ると、すべてのCPUが使用されている並列高速化とblock_parallel_saxpyベンチマーク中に100％表示されないのはなぜですか？タスクマネージャからの画像は以下の通りです：

ここで何が起こっているのか理解してくれる人がいますか？私が目にしていること、問題の症状、またはそれがどうあるべきか？それが前者なら、それを修正する方法はありますか？

を編集しました：blocked_pa​​rallel_saxpyコードを次のように変更しました。ブロックの総数（nblocks）を除算して、nworkerゴルーチン計算nworkerいいえ。のブロックを並行して実行します。さらに、チャンネルを削除しました。私はコードをベンチマークしており、それはチャネルとの並列実装と同じように動作します。なぜベンチマークを付けなかったのですか？

func blocked_parallel_saxpy(a float64, x []float64, incx int, b float64, y []float64, incy int, z []float64, incz int) { 
    zn := len(z) 
    if zn <= cachecap { 
     serial_saxpy(a, x, incx, b, y, incy, z, incz) 
     return 
    } 

    nblocks := zn/cachecap + 1 
    nworkers := runtime.GOMAXPROCS(0) 
    if nblocks < nworkers { 
     nworkers = nblocks 
    } 

    var wg sync.WaitGroup 
    for i := 0; i < nworkers; i++ { 
     for j := 0; j < nworkers && (i+j) < nblocks; j++ { 
      wg.Add(1) 
      go func(i, j int) { 
       defer wg.Done() 
       a, b := a, b 
       incx, incy, incz := incx, incy, incz 
       k := i + j 
       beg := k * cachecap 
       end := (k + 1) * cachecap 
       if end >= zn { 
        end = zn 
       } 
       serial_saxpy(a, x[beg:end], incx, b, y[beg:end], incy, z[beg:end], incz) 
      }(i, j) 
     } 
    wg.Wait() 
} 

Edit.2：私はチャンネルせずに、再び、blocked_pa​​rallel_saxpyの別のバージョンを書かれています。今度は、NumCPUゴルーチン、各処理nblocks/nworkers + 1ブロック、各ブロックはcachecap noです。長さの要素のここでも、コードは前の2つの実装と同じように動作します。

func blocked_parallel_saxpy(a float64, x []float64, incx int, b float64, y []float64, incy int, z []float64, incz int) { 
    zn := len(z) 
    if zn <= cachecap { 
     serial_saxpy(a, x, incx, b, y, incy, z, incz) 
     return 
    } 

    nblocks := zn/cachecap + 1 
    nworkers := runtime.GOMAXPROCS(runtime.NumCPU()) 
    if nblocks < nworkers { 
     nworkers = nblocks 
    } 

    k := nblocks/nworkers + 1 
    var wg sync.WaitGroup 
    wg.Add(nworkers) 
    for i := 0; i < nworkers; i++ { 
     go func(i int) { 
      defer wg.Done() 
      for j := 0; j < k && (j+i*k) < nblocks; j++ { 
       beg := (j + i*k) * cachecap 
       end := beg + cachecap 
       if end > zn { 
        end = zn 
       } 
       //fmt.Printf("i:%d, j:%d, k:%d, [beg:end]=[%d:%d]\n", i, j, k, beg, end) 
       serial_saxpy(a, x[beg:end], incx, b, y[beg:end], incy, z[beg:end], incz) 
      } 
     }(i) 
    } 

    wg.Wait() 
} 

Answer 1

チャネルなしの並列バージョンを試してみましょう。各ワーカーは、調整なしで8番目のブロックごとに計算します。

Answer 2

FWIW、linuxで動作します：BlockedSaxpyとParrSaxpyがどこに呼び出されているかを見ることができます。

まず、1つのコアが最大化されていることがわかります。つまり、blocked_serial_saxpyが呼び出されます。次に、使用されているすべてのコアが表示されますが、単一のコアより少ないCPUしか使用しません。それはblocked_parrallel_saxpyが呼び出されたときです。SIZEはここSIZE=2e06上で動作するバージョンですランダム5126

です。ここでも、後者のベンチマークで動作しているすべてのコアを見ることができます。今私はあなたの機能が少し改善できると思いますが、私は夕食のために飢えていないときのための運動としてそれを残します。 SIZE=2e8で

、我々は最終的にこの結果を参照してください。

go test -bench=. -benchtime=10s -cpuprofile=test.prof 
BenchmarkBlockedSaxpy-8   20  662405409 ns/op 
BenchmarkParrSaxpy-8    30  474503967 ns/op 

は最後に、3つの音：

1. saxpyはfloat32ためです。あなたはdaxpyを意味しますが、私は賢明です。
2. さらに：gonumにはすばらしいd/saxpy機能があります。
3. runtime.GOMAXPROCS(runtime.NumCPU())の代わりにruntime.NumCPU()を使用してください。