開発環境
- macOS Mojave - Apple (OS)
- Emacs (Text Editor)
- Windows 10 Pro (OS)
- Visual Studio Code (Text Editor)
- Go (プログラミング言語)
並行コンピューティング技法 ―実践マルチコア/マルチスレッドプログラミング (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 コメント:
コメントを投稿