爲相互依賴的線程測量並行計算時間

Question

我有一個關於並行程序中運行時測量的問題（我使用C++，但我認爲問題更一般）。

一些簡短的解釋：3個線程並行運行（pthread），以不同的方式解決相同的問題。取決於他自己的計算中的狀態/可用信息，每個線程可以將信息傳遞給另一個線程（例如，由一個線程獲得的部分解決方案，但不是另一個線程），以加速其他線程。一旦第一個線程準備就緒，整個過程就會停止。 現在我想要有一個獨特的時間度量來評估從開始到解決問題的運行時間。 （最後，我想確定通過並行計算使用協同效應是否快於在單個線程上計算）。

在我看來，問題在於，（由於操作系統暫停/取消暫停單線程），信息在進程中傳遞的時間點在每個進程的狀態中都不是確定性的。這意味着，在線程1上的xxx單元的CPU時間之後獲取某個信息，但無法控制線程2是否在計算後花費了CPU時間的yyy或zzz單位接收到此信息。假設這些信息在任何情況下都會完成線程2的計算，線程2的運行時間是yyy或zzz，具體取決於操作系統的操作。

如何獲得運行時比較的確定性行爲？我可以命令操作系統運行每個線程「不受干擾」（在多核機器上）嗎？在執行（C++）基礎上有什麼我可以做的嗎？

或者還有其他概念用於評估此類實現的運行時間（時間增益）嗎？

問候 馬丁

Answer 1

任何時候有人使用在同一個句子中的術語「確定性」和「多核」，它集警鐘長鳴:-)

有你的程序中的非確定性的兩大來源：1）操作系統，它通過操作系統抖動和調度決策增加了線程時序噪聲;和2）該算法，因爲程序根據（部分解決方案的）通信發生的順序遵循不同的路徑。

作爲一名程序員，關於操作系統噪聲可以做的並不多。即使是在專用（靜止）節點上運行的程序，標準操作系統也會增加很多噪音。計算節點的特殊用途操作系統可以通過某種方式來減少這種噪音，例如Blue Gene systems exhibit significantly less OS noise and therefore less variation in timings。

關於該算法，您可以通過添加同步將確定性引入到您的程序中。如果兩個線程同步，例如交換部分解決方案，那麼在同步之前和之後的計算順序是確定性的。您當前的代碼是異步的，因爲一個線程「發送」了部分解決方案，但不等待它被「接收」。您可以通過將計算分成步驟並在每個步驟之後的線程之間進行同步來將其轉換爲確定性代碼。例如，對於每個線程：

1. 計算一個步驟
2. 記錄部分解決方案（如果有的話）
3. 屏障 - 等待所有其它線程
4. 閱讀來自其他線程的部分解決方案
5. 重複1 -4

當然，我們不希望這段代碼執行得很好，因爲現在每個線程必須等待所有其他線程完成他們的計算在進行下一步之前。

最好的方法可能是接受非確定性，並使用統計方法比較您的時間。對給定數量的線程多次運行程序並記錄時間的範圍，平均值和標準偏差。你可能已經足夠了解例如對於給定數量的線程，所有運行的最大計算時間，或者您可能需要進行統計測試，例如Student's t-test來回答更復雜的問題，例如「從4線程增加到8線程會減少運行時間有多複雜」。正如DanielKO所說，時間上的波動是用戶實際上會遇到的情況，因此測量這些信息並對其進行統計量化是有意義的，而不是試圖完全消除它們。

Answer 2

有什麼用這種測量的？

假設您可以通過某種人爲的方法以線程運行不受干擾的方式（甚至通過使用緩存，MMU等其他進程的間接事件）來設置OS調度程序，這對於實際並行程序的使用？

現代操作系統很難讓應用程序控制一般的中斷處理，內存管理，線程調度等。除非您直接與金屬對話，否則您的確定性測量不僅不切實際，你的程序的用戶將永遠不會體驗到它們（除非它們與測量結果的金屬接近）。

所以我的問題是，爲什麼你需要這樣嚴格的條件來測量你的程序？在一般情況下，只需接受波動，因爲這是用戶最可能看到的。如果某個算法/實現的加速速度太微不足道了，以至於無法與背景噪聲區分開來，那麼對我而言，這比知道實際的加速比分數更有用。