計算公式結果的最佳方法是什麼？

Question

我目前有一個應用程序可以包含100個用戶定義的公式。目前，我使用反向波蘭符號來執行計算（將值和變量壓入堆棧，然後將它們從堆棧彈出並評估）。開始並行化這個過程的最好方法是什麼？我應該看看功能語言嗎？

計算是在數組數組上進行的，例如一個簡單的A + B實際上可能意味着100個加法。我目前正在使用德爾福，但這不是未來的要求。我將使用最適合這項工作的工具。公式也可能相互依賴因此，例如，我們可能有一個公式C = A + B，第二個公式爲D = C + A。

Answer 1

讓我們假設你的公式（方程）不是循環的，否則你不能「僅僅」評估它們。如果已矢量方程式如A = B + C，其中A，B和C是數組，讓我們概念性他們分成方程上的組件，因此，如果該數組的大小是5，這個等式被分成

a1 = b1 + c1 
a2 = b2 + c2 
... 
a5 = b5 + c5 

現在假設這一點，你有一個關於簡單量（無論是整數，理性還是別的）的大量方程組。

如果你有兩個方程E和F，比方說那個F depends_on E如果F的右側提到E的左側，例如

E: a = b + c 
F: q = 2*a + y 

我們獲得對如何計算這個，你總是可以使用隨機迭代來解決這個（這是在解釋只是一箇中間步驟），該算法如下：

1 while (there is at least one equation which has not been computed yet) 
2 select one such pending equation E so that: 
3  for every equation D such that E depends_on D: 
4  D has been already computed 
5 calculate the left-hand side of E 

這個過程無論正確答案終止你如何讓你的選擇在線// 2.現在很酷的是th在它也容易並行化。你可以在任意數量的線程中運行它！你所需要的是一個併發安全隊列，它保存那些已經計算出其先決條件（那些方程依賴於）的方程，但它們還沒有被計算出來。每個線程一次從這個隊列中彈出一個方程（線程安全），計算答案，然後檢查是否有新的方程，以便它們的所有先決條件已經計算出來，然後將這些方程（線程安全）到工作隊列。完成。

Answer 2

不知道更多，如果可能的話，我會建議採取SIMD風格的方法。也就是說，創建線程來計算單個數據集的所有公式。試圖將公式的計算劃分爲並行化並不會產生太多的速度改進，因爲要求能夠將計算分割成適合線程化的離散單元的邏輯將難以編寫並且難以正確地進行，開銷將取消取得任何速度收益。它也會因收益遞減而迅速受損。

現在，如果您有一組適用於多組數據的公式，那麼並行化會變得更容易，並且可以更好地擴展。每個線程對一組數據進行所有計算。爲每個CPU核創建一個線程，併爲每個核設置其親和性。每個線程都實例化公式評估代碼的一個實例。創建一個加載單個數據集的主管並將其傳遞給一個空閒線程。如果沒有線程空閒，請等待第一個線程完成處理其數據。處理所有數據集並完成所有線程後，退出。使用這種方法，由於線程切換較慢並且對總體速度產生負面影響，因此擁有比CPU上的內核更多的線程沒有任何優勢。

如果您只有一個數據集，那麼這不是一項簡單的任務。它需要解析分支的評估樹而不依賴於其他分支，並且需要對這些分支進行挖掘以分離在每個核心上運行的線程並等待結果。然後，您會遇到同步數據並確保數據一致性的問題。