如何通過流水線來隱藏數據移動帶來的延遲
我們知道數據移動帶來的延遲是阻礙程序性能的一個非常重要的因素。廣義上的數據移動包括幾個不同的方面。它包括不同進程間的信息傳遞(MPI)，比如從一維彈簧系統談多進程並行計算中提到的分散式矩陣矢量乘法。它也包括數據從慢速存儲到高速存儲的移動，一個例子是如何從Wall/CPU time理解多線程程序的並行效率一文中關注的IO時間，具體來講是屬於發生在主存和硬碟之間的數據移動，以及從2018戈登貝爾獎談高性能計算提到的數據在不同層次緩存之間的移動。它還包括數據在異質結構中host和target機器之間的移動。
我們為什麼如此關注數據移動？因為數據移動受延遲和帶寬的限制，在高性能計算程序中往往屬於不可並行或者很難並行的部分。那麼如何來克服這一難點呢？除了採用更先進的硬體來降低數據移動的延遲和提高數據傳輸的帶寬，我們在本文中討論一個來自軟體層面的方法。
首先定義一個高性能計算程序的抽象模型。如圖1所示。我們把程序分成兩個部分。其中一個是計算部分，我們假設這一部分是可被完美並行的，即使用n個計算單元，耗時縮短為原來的1/n。另外一個是數據的輸入或者輸出部分，它抽象了上文中提到的數據移動。為了討論的方便，我們在模型中獨立地看數據的輸入和輸出，從而得到了一個簡單的生產者-消費者模型。這個模型在一定程度涵蓋了前文中提到的針對不同層次而實現的並行模型(基於MPI、多線程和異質結構的並行計算)。我們先看兩個例子。例如從2018戈登貝爾獎談高性能計算中提到的深度學習，其中訓練數據的輸入可以看作圖1中的生產者，對模型的訓練看作是消費者。再例如傳統的動力學模擬，計算部分變成了生產者，對給定時間步的數據輸出變成了消費者。
假設運行圖1中以IO為代表的數據移動部分需要的時間是S, 總的計算量是C（即串列運行計算部分時需要的時間），那麼使用n個工作單元運行這個簡化模型需要的時間就是S+ C/n。從 Amdahls law 知道，數據移動的耗時S決定了這一模型的理論加速比上限。隨著工作單元的增加，數據移動必將變成效率提升的瓶頸。這是因為在這一計算模型中，增加新的工作單元並不能減少S。
在這一模型中，我們還合理地假設生產者和消費者運行在一個大的循環裡面，它們在程序中會被執行很多次。那麼如果重疊生產者和消費者的工作會對運行時間有什麼提升？我們以圖1中的第二個流程為例子，在圖2中示例了這個效果。計算單元作為生產者得到結果後立即進行新的時間步的計算，與此同時輸出單元作為消費者輸出計算單元得到的結果。不難看出，我們實現了一個存在於生產者和消費者之間的流水線。
我們可以看到在這個新的模型中，程序的運行時間變成了 max{S, C/n}。從流水線的角度不難理解這個結果。流水線中最慢的一級決定了流水線的吞吐量。圖2中流水線的深度是2，在最理想的狀況下，程序運行效率和圖1相比也會有2倍的提升。通過實現流水線，我們在某種程度上隱藏了數據移動帶來的延遲。
那麼在實際中會有哪些原因會讓效率的提升無法達到這個理想狀況呢？首先，如果流水線的各級沒有平衡就會降低流水線的吞吐量。比如IO過於頻繁，S>>C/n，那麼圖2的運行時間為 S， 和圖1的運行時間S+ C/n~S相比，就不會有顯著提高。我們再考慮一下這個問題：圖2忽略了哪些細節？比如圖2沒有畫出流水線各級之間的緩存，緩存需要存儲空間，並且計算單元和輸出單元需要在使用緩存上實現某種同步，這又是一個讓我們無法達到理想狀況的原因。
我們簡單談談圖2在實現上的一些細節和難點。首先是對一個多層次並行的程序，實現流水線有多個可能，比如進程的層面考慮使用 non-blocking message，線程層面考慮使用 explicit tasking。 那麼應該在哪一個層面來做流水線？答案並不唯一。主要的考慮仍然是實現流水線的代價和收益。假設在層次i的工作單元（包括圖2中的計算單元+輸出單元）數目是 ，並且我們只需要1個工作單元就可以完成輸出，那麼在i層實現流水線的計算時間變為
。這提示我們在實現之前可以先畫一張表格，列出各個層次的
。當然實際決策遠比這個公式複雜，計算時間不會有著這麼簡單的公式，並且需要考慮在新的實現中如何達到負載均衡，還需要考慮是否實現更多層級的流水線來達到更大的加速比，此外還需要考慮除了計算時間之外的其他成本。因而實際決策往往是設計+實驗的反覆迭代過程。
和圖2中的簡單示例相比，實際問題中阻礙圖2實現的最大障礙往往來自於代碼重構的難度，尤其是當需要重構的代碼有數萬行甚至數百萬行之大、負載開發代碼的人員是一個團隊的時候，如何讓整個團隊接受必須代碼重構這一事實，並且用合適的步伐向著合理的方向前進，這遠比程序本身更複雜。不得不承認，以 Amdahls law 為代表的廣義的高性能計算準則在這種情況下仍然是成立的。
此外，如何採用新的演算法來減少數據移動，在節約系統功耗上有著更重要的意義。這對於運行在下一代E級超級計算機或者移動終端（比如智能手機）上的高性能應用程序尤為重要，甚至可能是成敗的關鍵。
本文提到的流水線技術在底層硬體的設計中早已被廣泛使用。做好高性能計算，除了深入理解來自應用層面的並行性，理解編譯器、操作系統乃至硬體架構會變得至關重要。也許我們會發現高性能計算原理和方法在軟硬體層面上是殊途同歸的。引用一句話來總結這一發現：
「To solve problems at scale, paradoxically, you have to know the smallest details」
這句話來源於一個記錄google團隊開發過程的有趣博客：https://www.newyorker.com/magazine/2018/12/10/the-friendship-that-made-google-huge
推薦閱讀：
