導(dǎo)讀：Weld 是斯坦福大學(xué) DAWN 實驗室的一個開源項目，在 CIDR 2017 論文中描述了它的初始原型。Weld 用于對結(jié)合了數(shù)據(jù)科學(xué)庫和函數(shù)的現(xiàn)有工作負載進行優(yōu)化，而無需用戶修改代碼。我們在 VLDB 2018 論文中提出了 Weld 的自適應(yīng)優(yōu)化器，并得出了一些可喜的結(jié)果：通過在 Weld IR 上自動應(yīng)用轉(zhuǎn)換可以實現(xiàn)工作負載數(shù)量級的加速。消融研究表明，循環(huán)融合等優(yōu)化具有非常大的影響。本文主要介紹如何使用 Weld 的自適應(yīng)優(yōu)化器進行數(shù)據(jù)分析的端到端優(yōu)化。

分析應(yīng)用程序通常會使用多種軟件庫和函數(shù)，比如使用 Pandas 操作表，使用 NumPy 處理數(shù)字，使用 TensorFlow 進行機器學(xué)習(xí)。開發(fā)人員通過使用這些庫將來自各個領(lǐng)域的先進算法組合成強大的處理管道。

然而，即使每個庫中的函數(shù)都經(jīng)過精心優(yōu)化，我們?nèi)匀话l(fā)現(xiàn)它們?nèi)鄙俣说蕉说膬?yōu)化，在組合使用這些庫時會嚴重影響整體性能。例如，多次調(diào)用經(jīng)過優(yōu)化的 BLAS 函數(shù)(使用了 NumPy)要比使用 C 語言實現(xiàn)單次跨函數(shù)優(yōu)化(如管道化)慢 23 倍。

鑒于這種性能差距，我們最近提出了 Weld，一種用于分析工作負載的通用并行運行時。Weld 旨在實現(xiàn)跨多個庫和函數(shù)的端到端優(yōu)化，而無需改變庫的 API。對于庫開發(fā)人員來說，Weld 既可以實現(xiàn)庫函數(shù)的自動并行化，也可以實現(xiàn)強大的跨函數(shù)優(yōu)化，例如循環(huán)融合(loop fusion)。對于用戶而言，Weld 可以在不修改現(xiàn)有管道代碼的情況下帶來數(shù)量級的速度提升，也就是說數(shù)據(jù)分析師可以繼續(xù)使用 Pandas 和 NumPy 等流行庫的 API。

Weld 為開發(fā)人員提供了三個主要組件，用于與其他庫集成：

• 庫開發(fā)人員使用 Weld 的函數(shù)中間表示(Intermediate Representation，IR)來表達他們函數(shù)(例如映射操作或聚合)中的計算數(shù)據(jù)并行結(jié)構(gòu)。
• 然后，使用 Weld 的庫使用延遲評估運行時 API 將 Weld IR 片段提交給系統(tǒng)。Weld 將使用 IR 片段來自動跟蹤和調(diào)度對其他函數(shù)的調(diào)用。
• 當(dāng)用戶想要計算結(jié)果(例如將它寫入磁盤或顯示它)時，Weld 將使用優(yōu)化編譯器對組合程序的 IR 進行優(yōu)化和 JIT 編譯，這樣可以生成更快的并行機器代碼，然后基于應(yīng)用程序內(nèi)存中的數(shù)據(jù)執(zhí)行這些代碼。

在大多數(shù)情況下，用戶可以通過 import 語句切換到啟用了 Weld 的庫。

我們在 CIDR 2017 論文中描述了最初的 Weld 原型。通過在 IR 上應(yīng)用手動優(yōu)化，Weld 在合成工作負載上表現(xiàn)出了數(shù)量級的速度提升，這些工作負載包含了來自單個庫和多個庫的函數(shù)。

VLDB 2018：Weld 的自動優(yōu)化

這個原型有一個很顯著的限制，IR 的優(yōu)化是手動進行的，需要預(yù)先知道數(shù)據(jù)的相關(guān)屬性，例如聚合基數(shù)。簡單地說就是系統(tǒng)缺少自動優(yōu)化器。為此，我們在 VLDB 2018 上發(fā)表的***論文介紹了優(yōu)化器的設(shè)計和實現(xiàn)，這個優(yōu)化器可自動優(yōu)化 Weld 程序。

因為 Weld 試圖優(yōu)化來自不同獨立庫的函數(shù)，所以我們發(fā)現(xiàn)，與實現(xiàn)傳統(tǒng)的數(shù)據(jù)庫優(yōu)化器相比，在設(shè)計新的優(yōu)化器時存在一些獨特的挑戰(zhàn)：

• 計算高度冗余。與人工編寫的 SQL 查詢或程序不同，Weld 程序通常由不同的庫和函數(shù)生成。因此，消除由庫組合產(chǎn)生的冗余是至關(guān)重要的。例如，可以對中間結(jié)果進行管道化或緩存昂貴的公共子表達計算結(jié)果，避免多次計算。
• Weld 在進行數(shù)據(jù)依賴決策時不能依賴預(yù)先計算的統(tǒng)計數(shù)據(jù)。因此，Weld 需要在不依賴目錄或其他輔助信息的情況下優(yōu)化 ad-hoc 分析。此外，我們發(fā)現(xiàn)，在沒有任何統(tǒng)計數(shù)據(jù)的情況下進行的優(yōu)化可能會導(dǎo)致速度減慢 3 倍，這說明做出自適應(yīng)的決策是多么重要。

為了應(yīng)對這些挑戰(zhàn)，我們的優(yōu)化器采用了雙管齊下的設(shè)計，結(jié)合了靜態(tài)的基于規(guī)則的優(yōu)化(旨在消除冗余，以生成高效的 Weld IR)和自適應(yīng)優(yōu)化(在運行時確定是啟用還是禁用某些優(yōu)化)。

使用新優(yōu)化器的評估結(jié)果是很喜人的：在 10 個真實的工作負載上使用常用庫(如 NumPy 和 Pandas)，Weld 可在單個線程上實現(xiàn)高達 20 倍的加速，并通過自動并行化實現(xiàn)進一步的加速。在評估 Weld 時，我們還分析了哪些優(yōu)化對工作負載樣本產(chǎn)生的影響***，我們希望這對該領(lǐng)域的進一步研究有所幫助。

基于規(guī)則的優(yōu)化：從循環(huán)融合到向量化

Weld 的自動優(yōu)化器首先會應(yīng)用一組靜態(tài)的基于規(guī)則的優(yōu)化。基于規(guī)則的優(yōu)化從 Weld IR 輸入中查找特定模式，并用更有效的模式替換這些模式。Weld 基于規(guī)則的優(yōu)化器在其閉合的 IR 上運行，這意味著每個優(yōu)化的輸入和輸出都是相同的 IR。這種設(shè)計可以允許組合不同的規(guī)則并以不同的方式重新運行。

優(yōu)化器包含了很多用于生成高效代碼的規(guī)則，從折疊常量到合并并行循環(huán)。其他一些***影響力的基于規(guī)則的優(yōu)化：

• 循環(huán)融合，通過合并兩個循環(huán)來實現(xiàn)值的管道化，其中第二個循環(huán)直接消費***個循環(huán)的輸入。管道化改進了 CPU 緩存中的數(shù)據(jù)位置，因為合并循環(huán)每次只從輸入中加載一個元素。
• 向量化，它通過修改 IR 來生成顯式的 SIMD 向量化代碼。CPU 中的 SIMD 指令允許 CPU 在單個周期內(nèi)完成更多工作，從而提高吞吐量。
• 尺寸推斷，它通過分析 IR 來預(yù)先分配內(nèi)存而不是動態(tài)增長緩沖區(qū)。這個優(yōu)化避免了昂貴的庫調(diào)用，如 malloc。

Weld 應(yīng)用了其他額外的優(yōu)化，在這篇論文中有描述 http://www.vldb.org/pvldb/vol11/p1002-palkar.pdf。

自適應(yīng)優(yōu)化：從預(yù)測到自適應(yīng)哈希表

在使用基于規(guī)則的優(yōu)化器轉(zhuǎn)換 IR 之后，Weld 進行了一系列自適應(yīng)優(yōu)化。自適應(yīng)優(yōu)化器不是直接替換 IR 中的模式，而是將 Weld 程序變成在運行時動態(tài)選擇是否應(yīng)該應(yīng)用優(yōu)化。

其中的一個示例是決定是否要預(yù)測一個分支。預(yù)測會將分支表達式(即 if 語句)轉(zhuǎn)換為無條件計算 true 和 false 表達式的代碼，然后根據(jù)條件選擇正確的選項。盡管預(yù)測代碼會做更多的工作(因為同時計算了兩個表達式)，但它也可以使用 SIMD 運算符進行向量化，這與分支代碼不同。請看下面的示例：

使用預(yù)測優(yōu)化是否值得取決于兩個因素：運行 foo 的性能成本(例如 CPU 周期)和條件 x 的選擇性。如果 foo 計算很昂貴并且 x 很少是 true，那么無條件地計算 foo(即使使用了向量指令)可能導(dǎo)致比使用默認分支代碼更差的性能。在其他情況下，使用 SIMD 并行化可以大幅提升速度。這里的數(shù)據(jù)相關(guān)因子就是 x 的選擇性：這個參數(shù)在編譯時是未知的。

Weld 的自適應(yīng)優(yōu)化器為預(yù)測生成代碼，用于對 x 進行采樣，以便在運行時獲得選擇性的近似。然后，根據(jù)獲得的測量值，將在運行時使用設(shè)置了閾值的成本模型來選擇是否進行預(yù)測。下面的代碼展示了自適應(yīng)預(yù)測轉(zhuǎn)換：

Weld 的自適應(yīng)優(yōu)化器還提供了一些其他的轉(zhuǎn)換：例如，在構(gòu)建哈希表時，它可以選擇是否使用線程本地或原子全局數(shù)據(jù)結(jié)構(gòu)，具體取決于鍵的分布和預(yù)期的內(nèi)存占用。在我們的論文中有更多相關(guān)內(nèi)容。

Weld 在數(shù)據(jù)科學(xué)工作負載方面的表現(xiàn)

我們基于 10 個真實的數(shù)據(jù)科學(xué)工作負載對優(yōu)化器進行評估，包括使用 NumPy 計算用于股票定價的 Black Scholes 方程、使用 Pandas 分析嬰兒名稱、使用 NumPy 和 TensorFlow 來增白圖像并基于它們訓(xùn)練模型、使用 Pandas 和 NumPy 根據(jù)犯罪情況對城市進行評分，等等。結(jié)果如下：Weld 可以穩(wěn)定地提升單個線程的性能，并自動并行化本機單線程庫。從下圖可以看出，Weld 的自動優(yōu)化器可以有效地最小化因組合單個函數(shù)調(diào)用帶來的效率損失和生成快速的機器代碼。

每種優(yōu)化究竟有多重要?

為了研究每個優(yōu)化對工作負載有多大的影響，我們還進行了一項消融研究，我們逐個關(guān)閉每種優(yōu)化，并測量對性能的影響。下面的圖表總結(jié)了我們分別在一個和八個線程上測試得到的結(jié)果。每個框中的數(shù)字表示禁用優(yōu)化后的減速，因此數(shù)字越大意味著優(yōu)化會產(chǎn)生更大的影響。實線下方的數(shù)字顯示了帶有合成參數(shù)(例如高選擇性與低選擇性)的工作負載，用以說明自適應(yīng)優(yōu)化的影響。***，“CLO”列顯示了跨庫優(yōu)化或跨庫函數(shù)優(yōu)化的影響。

總的

來說，我們發(fā)現(xiàn)許多優(yōu)化至少對一個工作負載具有中等以上的影響。此外，跨庫優(yōu)化具有相當(dāng)大的影響，即使在 Weld 對庫應(yīng)用了優(yōu)化之后，仍然可以將性能提高 3 倍之多。我們的研究還表明，一些優(yōu)化非常重要：比如，循環(huán)融合和向量化對很多工作負載具有很大的影響。

總結(jié)Weld 是一種新的方法，用于對結(jié)合了數(shù)據(jù)科學(xué)庫和函數(shù)的現(xiàn)有工作負載進行優(yōu)化，而無需用戶修改代碼。我們的自動優(yōu)化器得出了一些可喜的結(jié)果：我們可以通過在 Weld IR 上自動應(yīng)用轉(zhuǎn)換來實現(xiàn)工作負載數(shù)量級的加速。我們的消融研究表明，循環(huán)融合等優(yōu)化具有非常大的影響。

Weld 是開源的，由 Stanford DAWN 負責(zé)開發(fā)，我們在評估中使用的代碼(weld-numpy 和 Grizzly，是 Pandas-on-Weld 的一部分)也是開源的，可在 PyPi 上獲得。這些包可以使用 pip 安裝：

重要鏈接：

• Weld 官網(wǎng)：https://www.weld.rs/
• 評估代碼 weld-numpy：https://www.weld.rs/weldnumpy
• 評估代碼 Grizzly：https://www.weld.rs/grizzly
• CIDR 2017 論文：https://cs.stanford.edu/~matei/papers/2017/cidr_weld.pdf
• VLDB 2018 論文：http://www.vldb.org/pvldb/vol11/p1002-palkar.pdf