2019年9月18日水曜日

開発環境

並行コンピューティング技法 ―実践マルチコア/マルチスレッドプログラミング (Clay Breshears(著)、千住 治郎(翻訳)、オライリージャパン)の6章(並列和とプリフィクススキャン)、6.2(プリフィクススキャン)、6.2.2(より現実的なアルゴリズム)をC言語(Windowsスレッド、POSIXスレッド、Pthreadライブラリ、OpenMPライブラリ等)ではなくGo言語(go文、goroutine、channel等)で取り組んでみる。

コード

main_test.go

package main

import "fmt"

func ExamplePrefixScanSequential() {
 intSlice := []int{3, 5, 2, 5, 7, 9, -4, 6, 7, -3, 1, 7, 6, 8, -1, 2}
 prefixScanSequential(intSlice)
 fmt.Println(intSlice)
 // Output:
 // [3 8 10 15 22 31 27 33 40 37 38 45 51 59 58 60]
}

func ExamplePrefixScanConcurrent() {
 intSlice := []int{3, 5, 2, 5, 7, 9, -4, 6, 7, -3, 1, 7, 6, 8, -1, 2}
 prefixScanConcurrent(intSlice)
 fmt.Println(intSlice)
 // Output:
 // [3 8 10 15 22 31 27 33 40 37 38 45 51 59 58 60]
}

main.go

package main

import (
 "fmt"
 "log"
 "os"
 "runtime"
 "strconv"
 "sync"
 "time"
)

func main() {
 numSlice1 := []int{}
 numSlice2 := []int{}
 max, err := strconv.Atoi(os.Args[1])
 if err != nil {
  log.Fatal(err)
 }
 for i := 0; i < max; i++ {
  numSlice1 = append(numSlice1, 1)
  numSlice2 = append(numSlice2, 1)
 }
 t1 := time.Now().UnixNano()
 prefixScanSequential(numSlice1)
 t1 = time.Now().UnixNano() - t1
 fmt.Printf("逐次アルゴリズム: %vナノ秒\n", t1)
 t2 := time.Now().UnixNano()
 prefixScanConcurrent(numSlice2)
 t2 = time.Now().UnixNano() - t2
 fmt.Printf("並行アルゴリズム: %vナノ秒\n", t2)
}

func prefixScanSequential(numSlice []int) {
 for i := 1; i < len(numSlice); i++ {
  numSlice[i] += numSlice[i-1]
 }
}

func prefixScanConcurrent(numSlice []int) {
 numCPU := runtime.NumCPU()
 lenNumSlice := len(numSlice)
 var wg sync.WaitGroup
 // ステップ1
 inTotals := make([]int, numCPU)
 for i := 0; i < numCPU; i++ {
  wg.Add(1)
  go func(j int) {
   defer wg.Done()
   start := lenNumSlice / numCPU * j
   var end int
   if j == numCPU-1 {
    end = lenNumSlice
   } else {
    end = lenNumSlice / numCPU * (j + 1)
   }
   for i := start + 1; i < end; i++ {
    numSlice[i] = numSlice[i-1] + numSlice[i]
   }
   inTotals[j] = numSlice[end-1]
  }(i)
 }
 wg.Wait()
 // ステップ2
 outTotals := make([]int, numCPU)
 outTotals[0] = 0
 for i := 1; i < numCPU; i++ {
  outTotals[i] = outTotals[i-1] + inTotals[i-1]
 }
 // ステップ3
 for i := 0; i < numCPU; i++ {
  wg.Add(1)
  go func(j int) {
   defer wg.Done()
   lastPrefixTotal := outTotals[j]
   start := lenNumSlice / numCPU * j
   end := lenNumSlice / numCPU * (j + 1)
   for i := start; i < end; i++ {
    numSlice[i] += lastPrefixTotal
   }
  }(i)
 }
 wg.Wait()
}

入出力結果(Bash、cmd.exe(コマンドプロンプト)、Terminal)

$ go test
# _/.../並行コンピューティング技法/ch6/sample2 [_/.../並行コンピューティング技法/ch6/sample2.test]
./sample1_test.go:7:2: undefined: prefixScanSequential
FAIL _/.../並行コンピューティング技法/ch6/sample2 [build failed]
$ go test
PASS
ok   _/.../並行コンピューティング技法/ch6/sample2 0.005s
$ go test
# _/.../並行コンピューティング技法/ch6/sample2 [_/.../並行コンピューティング技法/ch6/sample2.test]
./sample1_test.go:15:2: undefined: prefixScanConcurrent
FAIL _/.../並行コンピューティング技法/ch6/sample2 [build failed]
$ go test
PASS
ok   _/.../並行コンピューティング技法/ch6/sample2 0.005s
$ go run main.go 100
逐次アルゴリズム: 1000ナノ秒
並行アルゴリズム: 48000ナノ秒
$ go run main.go 1000
逐次アルゴリズム: 2000ナノ秒
並行アルゴリズム: 40000ナノ秒
$ go run main.go 10000
逐次アルゴリズム: 18000ナノ秒
並行アルゴリズム: 67000ナノ秒
$ go run main.go 100000
逐次アルゴリズム: 173000ナノ秒
並行アルゴリズム: 146000ナノ秒
$ go run main.go 1000000
逐次アルゴリズム: 1841000ナノ秒
並行アルゴリズム: 1409000ナノ秒
$ go run main.go 10000000
逐次アルゴリズム: 18956000ナノ秒
並行アルゴリズム: 15008000ナノ秒
$ go run main.go 100000000
逐次アルゴリズム: 225162000ナノ秒
並行アルゴリズム: 193983000ナノ秒
$ 

スライスの長さが10万以上でやっと並行アルゴリズムの方が速くなった。あまり並行化しても速度向上の効果がないのか、それとも実装に何か誤りがあるのか。試した要素数以上に設定したらCPUの問題ではなくメモリーの消費が大きくなってメモリー不足な状態になった。

0 コメント:

コメントを投稿

関連コンテンツ