斯坦福開源Weld：高效實(shí)現(xiàn)數(shù)據(jù)分析的端到端優(yōu)化

作者：無明譯 2018-08-13 21:19:07

Weld 是斯坦福大學(xué) DAWN 實(shí)驗(yàn)室的一個(gè)開源項(xiàng)目，在 CIDR 2017 論文中描述了它的初始原型。Weld 用于對(duì)結(jié)合了數(shù)據(jù)科學(xué)庫和函數(shù)的現(xiàn)有工作負(fù)載進(jìn)行優(yōu)化，而無需用戶修改代碼。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

循環(huán)融合，通過合并兩個(gè)循環(huán)來實(shí)現(xiàn)值的管道化，其中第二個(gè)循環(huán)直接消費(fèi)***個(gè)循環(huán)的輸入。管道化改進(jìn)了 CPU 緩存中的數(shù)據(jù)位置，因?yàn)楹喜⒀h(huán)每次只從輸入中加載一個(gè)元素。
向量化，它通過修改 IR 來生成顯式的 SIMD 向量化代碼。CPU 中的 SIMD 指令允許 CPU 在單個(gè)周期內(nèi)完成更多工作，從而提高吞吐量。
尺寸推斷，它通過分析 IR 來預(yù)先分配內(nèi)存而不是動(dòng)態(tài)增長緩沖區(qū)。這個(gè)優(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 進(jìn)行了一系列自適應(yīng)優(yōu)化。自適應(yīng)優(yōu)化器不是直接替換 IR 中的模式，而是將 Weld 程序變成在運(yùn)行時(shí)動(dòng)態(tài)選擇是否應(yīng)該應(yīng)用優(yōu)化。

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

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

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

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

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

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

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

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

總的

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

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

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