加速問題go

Question

我寫了一個非常簡單的程序來測試並行程序的性能。我寫了一個非常簡單的程序，通過分區試驗來分解一個大的半數字。由於不涉及任何通訊，我預計幾乎完美的加速。但是，該計劃似乎非常糟糕。

我使用系統time命令，使用1,2,4和8個進程對運行在8（真正的非HT）內核計算機上的程序進行計時。我分解的數字是「28808539627864609」。這裏是我的結果：

 
cores time (sec) speedup 
    1 60.0153  1 
    2 47.358  1.27 
    4 34.459  1.75 
    8 28.686  2.10 

如何解釋這種不好的加速？這是我的程序中的錯誤，還是運行時出現問題？我怎麼能得到更好的表演？我不是在談論算法本身（我知道有更好的算法來分解半數數字），而是我平行化的方式。

這裏是我的程序的源代碼：

package main 

import (
    "big" 
    "flag" 
    "fmt" 
    "runtime" 
) 

func factorize(n *big.Int, start int, step int, c chan *big.Int) { 

    var m big.Int 
    i := big.NewInt(int64(start)) 
    s := big.NewInt(int64(step)) 
    z := big.NewInt(0) 

    for { 
     m.Mod(n, i) 
     if m.Cmp(z) == 0{ 
      c <- i 
     } 
     i.Add(i, s) 
    } 
} 

func main() { 
    var np *int = flag.Int("n", 1, "Number of processes") 
    flag.Parse() 

    runtime.GOMAXPROCS(*np) 

    var n big.Int 
    n.SetString(flag.Arg(0), 10) // Uses number given on command line 
    c := make(chan *big.Int) 
    for i:=0; i<*np; i++ { 
     go factorize(&n, 2+i, *np, c) 
    } 
    fmt.Println(<-c) 
} 

---

編輯

問題似乎真的涉及到Mod功能。用Rem代替它可以帶來更好但仍不完美的表現和加速。用QuoRem代替它可以使性能提高3倍，並且提高速度。結論：似乎內存分配殺死了Go中的並行性能。爲什麼？你有任何關於此的參考？

Answer 1

Big.Int方法通常需要分配內存，通常要保存計算結果。問題是隻有一個堆，所有的內存操作都被序列化。在這個程序中，這個數字相當小，而像Mod和Add這樣的可並行化的計算時間相對於重複分配所有微小內存的不可並行操作來說是小的。

至於加速，有一個明顯的答案是不要使用big.Int，如果你不必。您的示例數字恰好適合64位。如果你計劃在非常大的數字上工作，這個問題將會自行消失。您將花更多時間進行計算，並且在堆中花費的時間相對會少得多。

順便說一句，在你的程序中有一個錯誤，雖然它與性能無關。當你找到一個因子並在通道上返回結果時，你發送一個指向局部變量i的指針。這很好，除非你沒有跳出循環。在goroutine中的循環繼續遞增i，並且在主要goroutine開始捕捉指針離開通道並跟隨它時，該值幾乎肯定是錯誤的。

Answer 2

我不讀go所以這可能是一個問題的答案，這不是你問的問題。如果是這樣，請按照您的意願降低或刪除。

如果你想對'n'做一個'時間來分解整數n'，你會得到一個隨機起伏的情節。對於您選擇的任何n，將會有一個範圍爲1..n的整數，這個整數在一個處理器上花費的時間最長。如果您的並行策略是將n個整數分佈在p個處理器上，那麼其中一個處理器至少需要花費時間來分解最難的整數，然後再將時間分解爲其餘的負載。

也許你做了類似的事情？

Answer 3

通過通道發送i後，i應該用新分配big.Int更換：

if m.Cmp(z) == 0 { 
    c <- i 
    i = new(big.Int).Set(i) 
} 

這是必要的，因爲沒有保障時fmt.Println將處理線fmt.Println(<-c)收到的整數。 fmt.Println通常不會導致goroutine切換，所以如果i沒有被新分配的big.Int取代，並且運行時切換回執行函數factorize中的for循環，則for循環將在其之前覆蓋i被打印 - 在這種情況下，程序將不會打印出通過通道發送的整數1st。

---

該fmt.Println可引起夠程切換的事實意味着for循環在功能factorize可以潛在消耗大量的CPU時間，當main夠程從信道c接收時刻和時的瞬間之間main goroutine終止。事情是這樣的：

run factorize() 
<-c in main() 
call fmt.Println() 
continue running factorize() // Unnecessary CPU time consumed 
return from fmt.Println() 
return from main() and terminate program 

---

另一個原因是小多核加速是內存分配。函數(*Int).Mod在內部使用(*Int).QuoRem，並且每次調用時都會創建一個新的big.Int。爲了避免內存分配，使用QuoRem直接：

func factorize(n *big.Int, start int, step int, c chan *big.Int) { 
    var q, r big.Int 
    i := big.NewInt(int64(start)) 
    s := big.NewInt(int64(step)) 
    z := big.NewInt(0) 

    for { 
     q.QuoRem(n, i, &r) 
     if r.Cmp(z) == 0 { 
      c <- i 
      i = new(big.Int).Set(i) 
     } 
     i.Add(i, s) 
    } 
} 

不幸的是，在圍棋的夠程調度釋放r60.3包含阻止該代碼使用所有的CPU內核的錯誤。當程序以-n=2（GOMAXPROCS = 2）開始時，運行時將只使用1個線程。

去每週發佈有更好的運行時間，如果n=2傳遞給程序可以利用2線程。這使我的機器的加速大約爲1.9。

---

用戶「高性能標記」在答覆中提到了導致多核心放緩的另一個潛在因素。如果程序將工作分解爲多個子任務，並且結果僅來自1個子任務，則意味着其他子任務可能會執行一些「額外工作」。運行程序n>=2可能總共比使用n=1運行程序消耗更多的CPU時間。

的瞭解有多少額外的工作正在做，你可能要（以某種方式）目前打印出所有夠程所有i的值在程序退出函數main()。