作者 | Shoumik Palkar 等
譯者 | 無(wú)明

導(dǎo)讀：Weld 是斯坦福大學(xué) DAWN 實(shí)驗(yàn)室的一個(gè)開(kāi)源項(xiàng)目，在 CIDR 2017 論文中描述了它的初始原型。Weld 用于對(duì)結(jié)合了數(shù)據(jù)科學(xué)庫(kù)和函數(shù)的現(xiàn)有工作負(fù)載進(jìn)行優(yōu)化，而無(wú)需用戶(hù)修改代碼。我們?cè)?VLDB 2018 論文中提出了 Weld 的自適應(yīng)優(yōu)化器，并得出了一些可喜的結(jié)果：通過(guò)在 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ì)使用多種軟件庫(kù)和函數(shù)，比如使用 Pandas 操作表，使用 NumPy 處理數(shù)字，使用 TensorFlow 進(jìn)行機(jī)器學(xué)習(xí)。開(kāi)發(fā)人員通過(guò)使用這些庫(kù)將來(lái)自各個(gè)領(lǐng)域的先進(jìn)算法組合成強(qiáng)大的處理管道。

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

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

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

• 庫(kù)開(kāi)發(fā)人員使用 Weld 的函數(shù)中間表示(Intermediate Representation，IR)來(lái)表達(dá)他們函數(shù)(例如映射操作或聚合)中的計(jì)算數(shù)據(jù)并行結(jié)構(gòu)。

• 然后，使用 Weld 的庫(kù)使用延遲評(píng)估運(yùn)行時(shí) API 將 Weld IR 片段提交給系統(tǒng)。Weld 將使用 IR 片段來(lái)自動(dòng)跟蹤和調(diào)度對(duì)其他函數(shù)的調(diào)用。

• 當(dāng)用戶(hù)想要計(jì)算結(jié)果(例如將它寫(xiě)入磁盤(pán)或顯示它)時(shí)，Weld 將使用優(yōu)化編譯器對(duì)組合程序的 IR 進(jìn)行優(yōu)化和 JIT 編譯，這樣可以生成更快的并行機(jī)器代碼，然后基于應(yīng)用程序內(nèi)存中的數(shù)據(jù)執(zhí)行這些代碼。

 

 

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

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

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

這個(gè)原型有一個(gè)很顯著的限制，IR 的優(yōu)化是手動(dòng)進(jìn)行的，需要預(yù)先知道數(shù)據(jù)的相關(guān)屬性，例如聚合基數(shù)。簡(jiǎn)單地說(shuō)就是系統(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)化來(lái)自不同獨(dú)立庫(kù)的函數(shù)，所以我們發(fā)現(xiàn)，與實(shí)現(xiàn)傳統(tǒng)的數(shù)據(jù)庫(kù)優(yōu)化器相比，在設(shè)計(jì)新的優(yōu)化器時(shí)存在一些獨(dú)特的挑戰(zhàn)：

• 計(jì)算高度冗余。與人工編寫(xiě)的 SQL 查詢(xún)或程序不同，Weld 程序通常由不同的庫(kù)和函數(shù)生成。因此，消除由庫(kù)組合產(chǎn)生的冗余是至關(guān)重要的。例如，可以對(duì)中間結(jié)果進(jìn)行管道化或緩存昂貴的公共子表達(dá)計(jì)算結(jié)果，避免多次計(jì)算。

• Weld 在進(jìn)行數(shù)據(jù)依賴(lài)決策時(shí)不能依賴(lài)預(yù)先計(jì)算的統(tǒng)計(jì)數(shù)據(jù)。因此，Weld 需要在不依賴(lài)目錄或其他輔助信息的情況下優(yōu)化 ad-hoc 分析。此外，我們發(fā)現(xiàn)，在沒(méi)有任何統(tǒng)計(jì)數(shù)據(jù)的情況下進(jìn)行的優(yōu)化可能會(huì)導(dǎo)致速度減慢 3 倍，這說(shuō)明做出自適應(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ù)載上使用常用庫(kù)(如 NumPy 和 Pandas)，Weld 可在單個(gè)線(xiàn)程上實(shí)現(xiàn)高達(dá) 20 倍的加速，并通過(guò)自動(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)融合，通過(guò)合并兩個(gè)循環(huán)來(lái)實(shí)現(xiàn)值的管道化，其中第二個(gè)循環(huán)直接消費(fèi)第一個(gè)循環(huán)的輸入。管道化改進(jìn)了 CPU 緩存中的數(shù)據(jù)位置，因?yàn)楹喜⒀�環(huán)每次只從輸入中加載一個(gè)元素。

• 向量化，它通過(guò)修改 IR 來(lái)生成顯式的 SIMD 向量化代碼。CPU 中的 SIMD 指令允許 CPU 在單個(gè)周期內(nèi)完成更多工作，從而提高吞吐量。

• 尺寸推斷，它通過(guò)分析 IR 來(lái)預(yù)先分配內(nèi)存而不是動(dòng)態(tài)增長(zhǎng)緩沖區(qū)。這個(gè)優(yōu)化避免了昂貴的庫(kù)調(diào)用，如 malloc。

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

自適應(yīng)優(yōu)化：從預(yù)測(cè)到自適應(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ù)測(cè)一個(gè)分支。預(yù)測(cè)會(huì)將分支表達(dá)式(即 if 語(yǔ)句)轉(zhuǎn)換為無(wú)條件計(jì)算 true 和 false 表達(dá)式的代碼，然后根據(jù)條件選擇正確的選項(xiàng)。盡管預(yù)測(cè)代碼會(huì)做更多的工作(因?yàn)橥瑫r(shí)計(jì)算了兩個(gè)表達(dá)式)，但它也可以使用 SIMD 運(yùn)算符進(jìn)行向量化，這與分支代碼不同。請(qǐng)看下面的示例：

 

 

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

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

 

 

Weld 的自適應(yīng)優(yōu)化器還提供了一些其他的轉(zhuǎn)換：例如，在構(gòu)建哈希表時(shí)，它可以選擇是否使用線(xiàn)程本地或原子全局?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 分析嬰兒名稱(chēng)、使用 NumPy 和 TensorFlow 來(lái)增白圖像并基于它們訓(xùn)練模型、使用 Pandas 和 NumPy 根據(jù)犯罪情況對(duì)城市進(jìn)行評(píng)分，等等。結(jié)果如下：Weld 可以穩(wěn)定地提升單個(gè)線(xiàn)程的性能，并自動(dòng)并行化本機(jī)單線(xiàn)程庫(kù)。從下圖可以看出，Weld 的自動(dòng)優(yōu)化器可以有效地最小化因組合單個(gè)函數(shù)調(diào)用帶來(lái)的效率損失和生成快速的機(jī)器代碼。

 

 

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

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

 

 

總的

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

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

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

 

 

重要鏈接：

• Weld 官網(wǎng)：https://www.weld.rs/

• 評(píng)估代碼 weld-numpy：https://www.weld.rs/weldnumpy

• 評(píng)估代碼 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

英文原文：http://dawn.cs.stanford.edu/2018/07/30/weldopt/

標(biāo)簽： 代碼 數(shù)據(jù)分析 數(shù)據(jù)庫(kù)

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。