我該如何並行化這個解算器代碼

我試圖優化和並行化一些代碼，在圖形結構中用鏈接和節點進行模擬。主熱點是這樣一個循環：我該如何並行化這個解算器代碼

void ExecuteAll() 
{ 
    for(long i = TotalCount(); i >= 1; i--) 
    { 
     long k = linkOrder[i]; 
     long link = firstLink[k]; 
     if (link == 0) 
      continue; 

     double d = 0.; 
     for(; link != 0; link = nextLink[link]) 
     { 
      long kk = getNode(link); 
      d += fak[link]*res[kk]; 
     } 
     d += res[k]; 
     double d2 = d/fak2[k]; 
     res[k] = d2; 
     res2[k] += d2; 
    } 
}

我返工這個通過實施這樣的一類具有多線程工作：

class myDemoClass 
{  
    bool volatile *isDone; 
public: 

    void ExecuteSlice() 
    { 
     for(long i = TotalCount() - mThreadIndex; i >= 1; i -= threadCount) 
     { 
      long k = linkOrder[i]; 
      Execute(k); 
     } 
    } 

    void Execute(long k) 
    { 
     long link = firstLink[k]; 
     if (link == 0) 
     { 
      isDone[k] = true; 
      return; 
     } 
     double d = 0.; 
     for(; link != 0; link = nextLink[link]) 
     { 
      long kk = getNode(link); 

      for(int x = 0; ! isDone[kk]; x++) 
       {} // Wait until data is ready. Time too short for sleep or event 

      d += fak[link]*res[kk]; 
     } 
     d += res[k]; 
     double d2 = d/fak2[k]; 
     res[k] = d2; 
     res2[k] += d2; 

     isDone[k] = true; 
    } 
}

我創建這個類的一個實例爲每個線程哪裏每個線程運行在i的所有值的切片上。我引入了一個新的數組bool volatile *isDone，因爲我不能使用非處理節點的結果。我試圖插入一個睡眠或事件，而不是for(;...;){}循環，但事實證明，等待狀態對此太短。

這似乎工作正常。所有對Execute（）的調用中只有10％必須進入等待循環，因爲圖形從起點開始越來越多，並且結果是正確的。

但是，當使用具有8個線程的新代碼時，令人驚訝的是，在8核心XEON機器上沒有可衡量的性能增益（或損失）。我知道這個代碼在緩存失效方面並不是最優的，主要是因爲isDone和res是從多個核心寫入和讀取的。但在大多數情況下，解除引用的索引距離彼此很遠。該圖有大約1.000.000個節點和鏈接。

如何提高此代碼的並行度？

來源

2011-06-20 RED SOFT ADAIR

線程代碼在哪裏？ – Mark

你應該使用互斥或原子compare_and_swap而不是靜音循環（編譯器可能會刪除）。 –

@Mark。線程代碼太大而不能顯示在這裏。但主要是它爲每個CPU啓動一個線程並啓動ExecuteSlice（）函數。 @Joel靜音循環未被優化，因爲iSDone被標記爲易失性。 –

你不能只使用volatile這樣的代碼線程安全。易失性有助於單線程應用程序將變量映射到外部設備，方法是確保始終重新讀取值，但對於線程來說不夠充分，因爲編譯器不僅可以對語句進行重新排序，還可以對處理器重新排序指令。你應該使用一個適當的多線程原語來實現這一點，無論是由庫提供的還是編譯器特定的實現（例如Win32上的互鎖函數，或者gcc上的Atomic Builtins）。同樣，不清楚您的其他數據結構對於多線程修改是否安全。

至於性能，很難說出問題所在，因爲我們對圖表結構一無所知，而且代碼太抽象以致無法解決這個問題。但是，您似乎花費了大量的時間來反覆處理可能已處理或尚未處理的鏈接。理想情況下，你可以用另一種方式來處理一個沒有依賴關係的鏈接，然後當它完成時，從依賴這個鏈接的鏈接開始，等等，這意味着沒有等待。也許像拓撲類似的東西在這裏會有所幫助。

來源

2011-06-20 12:29:46 Kylotan

我現在瘋了測試使用循環條件InterlockedCompareExchange而不是「！isDone [kk]」。性能顯着下降，並且比單線程版本差。 –

正確的同步比做錯事更昂貴。你必須選擇一個。 – Kylotan

OpenMP是事實上標準，以及支持在當前的編譯器，用於陣列處理代碼的並行進入，你根本不希望過於擔心線程管理多個內核運行結構相同的任務。看看這個，它可能有助於澄清你的想法，甚至可以解決問題。

這最好用於純粹的CPU綁定任務 - 我不清楚這是否適合您，因爲您指的是等待數據到達？在這種情況下，多線程邏輯可能無法達到您所期望或希望的程度。

來源

2011-06-20 13:10:03

您的回答與我的問題無關。 OpenMP對數組很有用。這不是數組問題。 –

同意。我的想法是，您可能可以重新設計初始邏輯，以便可以並行化，而不必讓您擔心自己的許多線程代碼。 –

如果你不想用線程化的東西來代替你的代碼，OpenMP實際上是最好的。 –

的一點想法可能是有用的：

爲了確保您的線程代碼工作我會通過一些計算，是已知的並行以及（沒有立即想到爲例）測試。然後，您可以測試單線程和多線程實現，並確保您的整體線程應用程序按預期工作。
你確定你的算法能夠很好地並行嗎？正如Steve提到的，CPU綁定計算最適合並行，而代碼看起來像是CPU和IO的混合。根據什麼getNode()你可能是IO綁定，這將限制你可以通過使用多線程算法獲得什麼。對您的代碼進行性能分析和基準測試將有助於確定您的最佳應用優勢所在。
不要使用volatile作爲提到的其他發佈者的多線程同步。它現在確實可以爲你工作，但不能保證它在未來不會崩潰。考慮一下最糟糕的情況，它會在幾個月的時間內微妙地崩潰，輕微地破壞所有的模擬結果，但不夠明顯。
對於「等待」循環也是可疑的，應該改變爲適當的線程等待。當一個線程在這個循環中「等待」時，它正在消耗CPU時間，通過在另一個線程中完成實際工作可能更好。如果這個等待循環僅僅被使用了10％的時間，你的收益（如果有的話）會很小，但是不能保證它的使用總是這麼小。

來源

2011-06-20 14:41:23 uesp

我該如何並行化這個解算器代碼

回答

相關問題