論文名稱：PIM-tree: A Skew-resistant Index for Processing-in-Memory

摘要

當今的內(nèi)存索引性能受到內(nèi)存延遲/帶寬瓶頸的限制。Processing-in-memory (PIM) 是一種新興的方法，可能通過實現(xiàn)低延遲內(nèi)存訪問，其聚合內(nèi)存帶寬隨 PIM 節(jié)點數(shù)量擴展，來緩解這種瓶頸。然而，在工作負載偏斜的情況下，PIM 系統(tǒng)在最小化節(jié)點間通信和實現(xiàn)負載平衡之間存在固有的張力。本文介紹了 PIM-tree，一種針對 PIM 系統(tǒng)的有序索引，它通過在數(shù)據(jù)和查詢中實現(xiàn)加載平衡，實現(xiàn)了低通信成本和高負載平衡。我們的抗偏移索引基于主機 CPU 和 PIM 節(jié)點之間的勞動分工，利用各自的優(yōu)勢。我們引入了推-拉搜索，它可以根據(jù)工作負載的偏移程度動態(tài)地決定是將查詢推送到 PIM-tree 節(jié)點還是將節(jié)點的鍵拉回到 CPU。結(jié)合其他 PIM-friendly 優(yōu)化（如陰影子樹和分塊跳表），我們的 PIM-tree 可以為點查詢、更新和范圍掃描提供高吞吐量、（保證的）低通信成本和（保證的）高負載平衡。我們在最新的UPMEM PIM 系統(tǒng)上實現(xiàn)了 PIM-tree，除了先前提議的 PIM 索引外，該系統(tǒng)具有32個 CPU 核心和 2048 個 PIM 節(jié)點。在具有 5 億個鍵和 100 萬個查詢批次的工作負載下，使用 PIM-tree 的吞吐量比兩個最佳的先前基于 PIM 的方法高達 69.7× 和 59.1×。據(jù)我們所知，這是第一次在真正的 PIM 系統(tǒng)上實現(xiàn)有序索引。

1 引言

CPU 速度和內(nèi)存速度之間的不匹配（即“內(nèi)存墻”）使得內(nèi)存訪問成為當今數(shù)據(jù)密集型應(yīng)用程序中的主要成本。傳統(tǒng)的架構(gòu)使用多級緩存來減少 CPU 和內(nèi)存之間的數(shù)據(jù)移動，但如果應(yīng)用程序表現(xiàn)出有限的局部性，大多數(shù)數(shù)據(jù)訪問仍然由內(nèi)存服務(wù)。這種過度的數(shù)據(jù)移動會產(chǎn)生巨大的能量成本，并且性能受到高內(nèi)存延遲和/或有限內(nèi)存帶寬的限制。處理-in-memory (PIM) [25, 30]，也稱為近數(shù)據(jù)處理，正在成為減少昂貴數(shù)據(jù)移動的關(guān)鍵技術(shù)。通過將計算資源集成在內(nèi)存模塊中，PIM 可以使數(shù)據(jù)密集計算在啟用 PIM 的內(nèi)存模塊中執(zhí)行，而不是將所有數(shù)據(jù)移動到 CPU 來進行處理。最近的研究表明，對于高數(shù)據(jù)密度和低緩存局部性的程序，PIM 可以通過減少數(shù)據(jù)移動來提高性能并降低功耗 [14, 15]。盡管處理-in-memory/processing-in-storage的提議可追溯至至少1970年[29]，包括數(shù)據(jù)庫社區(qū)在主動磁盤[26]中的嘗試，但由于3D堆疊內(nèi)存[18, 22]的進步以及最近商業(yè)PIM系統(tǒng)原型的可用性[30]，PIM正在成為一種關(guān)鍵技術(shù)。典型的利用現(xiàn)代PIM體系結(jié)構(gòu)的應(yīng)用程序包括神經(jīng)網(wǎng)絡(luò)[3, 21, 23, 32]、圖形處理[1, 17, 35]、數(shù)據(jù)庫[6, 7]、稀疏矩陣乘法[13, 33]和基因組分析[2, 34]。

PIM 系統(tǒng)通常組織為一個主機（多核）CPU，它將計算任務(wù)推送到一組 PIM 模塊（增強計算內(nèi)存模塊），并收集結(jié)果。因此，需要移動任務(wù)描述符和數(shù)據(jù)，這兩個成本之和是 CPU 和 PIM 模塊之間的通信成本。主機 CPU 可以是任何商品多核處理器，通常比 PIM 模塊內(nèi)的微小 CPU 更強大。因此，PIM 系統(tǒng)的一個有趣特征是潛在地利用兩組資源（CPU 端和 PIM 端）。

在本文中，我們專注于為內(nèi)存數(shù)據(jù)設(shè)計一種適合 PIM 的有序索引。有序索引（例如 B 樹[11]）是數(shù)據(jù)庫/數(shù)據(jù)存儲的支柱組件之一，支持高效的搜索查詢、范圍掃描、插入和刪除。以前針對 PIM [10, 24] 的工作提出了基于范圍劃分的有序索引：將鍵空間劃分為 ?? 個相等鍵數(shù)的子范圍，每個 ?? PIM 模塊存儲一個子范圍。每個 PIM 模塊在其子范圍內(nèi)維護一個本地索引，而主機 CPU 則維護索引頂部直到局部索引的 ?? 個根。這種方法適用于具有均勻隨機鍵的數(shù)據(jù)和查詢，即這些工作所研究的設(shè)置，但在數(shù)據(jù)或查詢偏斜下容易出現(xiàn)負載不平衡。在更實際的工作負載中，查詢/更新批次可能集中在少量分區(qū)的數(shù)據(jù)上，壓倒了這些 PIM 模塊，而其他模塊處于空閑狀態(tài)。在極端情況下，只有一個 PIM 模塊處理查詢，其余的模塊處于空閑狀態(tài)，在單個（微弱的）處理器上完全串行化整個查詢批次。該方法還需要為保持分區(qū)（大致）平衡的所有數(shù)據(jù)移動付出代價。在最近的一篇論文[19]中，我們設(shè)計了一種 PIM-friendly 跳表，它在漸進意義下實現(xiàn)了負載平衡（詳見第2.4節(jié)），但該解決方案不實用（如下所述）。

為了解決查詢和數(shù)據(jù)偏斜的挑戰(zhàn)，我們提出了 PIM-tree，一種實用的面向 PIM 的有序索引，它可以實現(xiàn)在數(shù)據(jù)和查詢的任何偏斜程度下實現(xiàn)低通信成本和高負載平衡。我們的抗偏移索引基于主機 CPU 和 PIM 節(jié)點之間的新穎勞動分工，利用各自的優(yōu)勢。此外，它結(jié)合了 B+-樹和跳表的特點來實現(xiàn)其目標。我們專注于以批處理同步的方式實現(xiàn)高吞吐量，處理查詢批次。PIM-tree 支持廣泛的批并行操作，包括點查詢（Get，Predecessor）、更新（Insert，Delete）和范圍掃描。

2 背景

2.1 PIM 系統(tǒng)架構(gòu)和模型

處理內(nèi)存中的模型。我們使用處理內(nèi)存中的模型（PIM Model）（首次描述于[19]）作為通用 PIM 系統(tǒng)的抽象。它包括一個主機 CPU 前端（CPU 側(cè)）和一組 ?? 個 PIM 模塊（PIM 側(cè)）。CPU 側(cè)是一個標準的多核處理器，具有 ?? 個字的片上緩存。每個 PIM 模塊由一個 DRAM 存儲器（本地 PIM 存儲器）、一臺片上處理器（PIM 處理器）和 Θ(??/??) 個字的本地存儲器（其中 ?? 表示問題的規(guī)模）組成。PIM 處理器簡單但通用（例如，能夠運行 C 代碼的單一按順序核心）。主機 CPU 可以向 PIM 模塊發(fā)送代碼、啟動代碼，并檢測代碼完成的情況。它還可以向 PIM 存儲器發(fā)送數(shù)據(jù)并接收來自 PIM 存儲器的數(shù)據(jù)。該模型假設(shè)沒有直接的 PIM 對 PIM 通信，盡管在支持此類通信的 PIM 系統(tǒng)上我們可以利用這種通信。

由于 PIM 模型結(jié)合了共享內(nèi)存?zhèn)龋–PU 和其緩存）和分布式側(cè)（PIM 模塊），因此算法使用共享內(nèi)存指標（工作量、深度）和分布式指標（本地工作量、通信時間）進行分析。在 CPU 側(cè)，該模型考慮了 CPU 工作量（所有核心的總工作量）和 CPU 深度（關(guān)鍵路徑上的所有工作）。在 PIM 側(cè)，該模型考慮了 PIM 時間，即任一 PIM 核上的最大本地工作量，以及 IO 時間，即任一 PIM 模塊發(fā)送/接收的最大消息數(shù)。程序以批量同步輪次執(zhí)行[31]，算法的整體復(fù)雜度指標是每一輪復(fù)雜度指標的總和。本文重點關(guān)注 IO 時間和 IO 輪次。

編程接口。為了具體起見，我們假設(shè)了我們通用 PIM 系統(tǒng)的以下編程接口，盡管我們的技術(shù)也可以與其他接口一起使用。程序由兩部分組成：在主機 CPU 上執(zhí)行的主機程序和在 PIM 模塊上執(zhí)行的 PIM 程序。主機程序具有附加功能（下文討論），用于與 PIM 側(cè)進行通信，包括調(diào)用 PIM 模塊上的 PIM 程序和向 PIM 模塊傳輸數(shù)據(jù)/從 PIM 模塊接收數(shù)據(jù)的功能。PIM 程序是一個傳統(tǒng)程序，在由主機程序啟動時在所有 PIM 處理器上執(zhí)行。它使用模塊的本地存儲器執(zhí)行，對 CPU 側(cè)或其他 PIM 模塊沒有可見性。具體函數(shù)為（命名為 MPI 風格[16]）：

• PIM_Load(PIM_Program_Binary)：將二進制文件加載到 PIM 模塊。
• PIM_Launch()：在所有 PIM 上啟動加載的 PIM 程序。
• PIM_Status()：檢查 PIM 程序在所有 PIM 上是否已完成。
• PIM_Broadcast(src, length, PIM_Local_Address)：將固定長度的緩沖區(qū)復(fù)制到每個 PIM 的相同本地存儲器地址。
• PIM_Scatter(srcs[], length[], PIM_Local_Address)：類似于 PIM_Broadcast，但每個 PIM 模塊都有一個獨立的緩沖區(qū)。?
• PIM_Gather(dsts[], length[], PIM_Local_Address)：與 PIM_Scatter 的相反操作，將讀入緩沖區(qū)數(shù)組 dsts[]。

基于這個接口，我們的 PIM-friendly 有序索引以批量同步輪次處理操作批，如[28]中的步驟一樣，使用算法1中的步驟。如第5節(jié)所討論的，當實現(xiàn)我們的 PIM-friendly 程序時，我們使用流水線技術(shù)重疊 CPU 的步驟1和 PIM 模塊的步驟3。

具體案例：UPMEM。我們在 UPMEM 的最新 PIM 系統(tǒng)[30]上評估了我們的技術(shù)。UPMEM 的架構(gòu)（圖1）是實例化 PIM 模型的一種方式。它的 PIM 模塊是即插即用的 DRAM DIMM 替代品，因此可以配置為各種傳統(tǒng) DRAM 存儲器和 PIM 設(shè)備的比例（目前最大可用配置有2560個 PIM 模塊）。CPU 可以訪問主存儲器（傳統(tǒng) DRAM）和所有 PIM 存儲器，但每個 PIM 處理器只能訪問其本地存儲器。每個 PIM 模塊具有高達628 MB/s的本地 DRAM 帶寬，因此配備2560個 PIM 模塊的機器可以提供高達1.6 TB/s的總帶寬[15]。為了在 PIM 模塊之間傳輸數(shù)據(jù)，CPU 從源讀取并寫入目標。UPMEM 的 SDK 支持上述編程接口函數(shù)，但有一個限制，即散射/聚集函數(shù)必須傳輸相同長度的緩沖區(qū)到/從所有 PIM 模塊（即，緩沖區(qū)被填充到相等長度）。UPMEM 的主存儲器（PIM 模型中沒有的一個組件）能夠運行具有 CPU 側(cè)內(nèi)存占用超過 ?? 個字的程序，但這些額外的內(nèi)存訪問帶來了另一種類型的通信，即在 PIM 模型中不存在的 CPU-DRAM 通信。因此，對于主機程序來說，緩存效率非常重要。我們在 PIM-tree 中的解決方案是僅使用少量的 CPU 側(cè)內(nèi)存：Θ(??) < ?? 個字，用于 ?? 個操作的批處理。

UPMEM PIM系統(tǒng)的架構(gòu)，這是我們通用PIM系統(tǒng)架構(gòu)的一個具體例子。PIM模塊被打包到通過普通內(nèi)存通道連接到主機CPU的內(nèi)存內(nèi)存中。CPU端還包括傳統(tǒng)的DRAM模塊，這不是PIM模型的一部分。

2.2 負載平衡初步 PIM

系統(tǒng)面臨的主要挑戰(zhàn)之一是保持 PIM 模塊之間的負載平衡，我們將其定義如下：

定義 2.1. 如果每個 PIM 程序執(zhí)行的工作量（單位時間指令）為??(?? /??)，并且每個 PIM 模塊發(fā)送/接收的通信量為 ??(??/??)，則程序?qū)崿F(xiàn)了負載平衡，其中 ?? 和 ?? 分別是所有??個 PIM 模塊的工作量和通信的總和。對于具有多個批量同步輪次的程序，如果每個輪次都實現(xiàn)了負載平衡，則程序?qū)崿F(xiàn)了負載平衡。

實現(xiàn)負載平衡的挑戰(zhàn)在于必須限制具有最大工作量或通信的 PIM 模塊。需要注意的是，隨機化并不直接導致負載平衡，例如，對相等工作量和通信的??個任務(wù)進行隨機散布到??個 PIM 模塊不能實現(xiàn)負載平衡。這是因為其中一個 PIM 模塊在?? [5]中以很高的概率接收 Θ(log ??/log log ??) 個任務(wù)，導致該模塊的工作量和通信量是平衡量的 Θ(log ??/log log ??) 倍。

我們使用“球進箱子引理”來證明負載平衡，其中箱子是一個 PIM 模塊，權(quán)重為??的球?qū)?yīng)于具有??工作量或??通信的任務(wù)。我們將使用以下引理：

引理 2.2 ([19, 27])。將總重量為?? = 且每個???? < ?? /(?? log ??)的加權(quán)球均勻隨機地放入??個箱子中，則每個箱子中的重量均為??(?? /??)，幾乎肯定發(fā)生。

2.3 PIM 上索引的先前工作

有幾項關(guān)于 PIM 系統(tǒng)上索引的先前工作。兩項先前工作[10, 24]提出了 PIM-friendly 跳表。它們的跳表基于范圍劃分：它們通過不相交的鍵范圍對跳表進行劃分，并在每個部分上本地維護一個 PIM 模塊。如第1節(jié)所述，這種范圍劃分在數(shù)據(jù)和查詢傾斜的情況下可能會遇到嚴重的負載不平衡問題。

范圍劃分有序索引的負載不平衡問題在傳統(tǒng)的分布式環(huán)境中也受到研究。Ziegler 等人[36]討論了其他選擇的基于樹狀有序索引，以避免負載不平衡問題，其中包括：(i) 按鍵的哈希值進行劃分，(ii) 隨機分布所有索引節(jié)點的精細劃分，(iii) 在葉子節(jié)點進行精細劃分，在內(nèi)部節(jié)點進行范圍劃分的混合方法。他們還在一個8臺機器的集群上進行了實驗評估。然而，在具有數(shù)千個 PIM 模塊的 PIM 系統(tǒng)中，這些選擇每一種都在某種程度上存在問題：(i) 通過哈希進行劃分會使范圍操作成本增加，因為它們必須由所有 PIM 模塊處理，(ii) 精細劃分會導致太多的通信，因為所有訪問都將是非本地的，(iii) 混合方法在其范圍劃分部分存在負載平衡問題。

2.4 先前工作：PIM 平衡跳表

最近的一篇論文[19]中，我們提出了第一個在 PIM 模型下對敵控工作負載具有可證明的負載平衡的批處理并行跳表索引，即 PIM 平衡跳表。一個關(guān)鍵的洞察是利用 CPU 端來解決負載平衡問題。PIM 平衡跳表將跳表水平分割為兩部分，一個上部和一個下部，將上部在所有 PIM 模塊中復(fù)制，并將下部節(jié)點隨機分配給 PIM。如圖 2 所示，不同 PIM 模塊中的節(jié)點具有不同的顏色，復(fù)制的上部部分明確地繪制為多個副本。對于一個具有 ?? 個 PIM 模塊的系統(tǒng)，下部為 log ?? 層。我們可以復(fù)制（僅）頂部部分，因為 (i) 相對于跳表的其余部分來說它很小，而且 (ii) 它相對不經(jīng)常更新（回憶一下，在跳表中插入關(guān)鍵字到達高度 ? 的概率為 1/2^?）。

在一個4個PIM模塊的系統(tǒng)上，使用上部部分復(fù)制的PIM平衡跳表[19]。不同PIM模塊上的節(jié)點是不同的顏色。PIM指針為虛線。下部分是log??層。

查詢通過在跳表節(jié)點“樹”中進行指針追蹤來執(zhí)行。首先將批處理的查詢均勻分成若干份發(fā)送到所有 PIM 模塊，每個模塊在本地處理上部部分。然后跳表通過將查詢逐個發(fā)送到搜索路徑上每個下部節(jié)點的主機 PIM 模塊來處理下部部分，直到達到葉子節(jié)點。我們稱之為推送方法，因為查詢被“推送”到 PIM 模塊來執(zhí)行。

僅使用推送執(zhí)行一批并行查詢可能導致嚴重的不平衡，盡管下部節(jié)點是隨機分布的。對于傾斜的工作負載，許多查詢可能共享搜索路徑上的一個通用節(jié)點，這意味著它們都被發(fā)送到該節(jié)點的主機 PIM 模塊，導致負載不平衡。這些節(jié)點被稱為爭用點。一個例子是當多個非重復(fù)的 Predecessor 查詢返回相同的關(guān)鍵字時，搜索路徑上的所有節(jié)點都成為爭用點。

PIM 平衡跳表[19]通過避免爭用點來解決這個問題，基于一個關(guān)鍵觀察：一旦關(guān)鍵字 ?? 和 ?? 的搜索路徑共享下部節(jié)點 ??，搜索任何關(guān)鍵字 ?? ∈ [??, ??] 也會到達節(jié)點 ??。因此，對于 ?? 的搜索可以直接從這兩個路徑的最低公共祖先（LCA）開始。我們稱之為跳推方法。跳推搜索具有一個預(yù)處理階段來記錄搜索路徑。它是一個多輪樣本搜索，從一個樣本開始：在每一輪中，它將樣本大小加倍，并使用前幾輪記錄的搜索路徑來決定本輪樣本查詢的起始節(jié)點。這種方法限制了每個節(jié)點上的爭用，并避免了負載不平衡。

然而，預(yù)處理成本很高。對于??個 PIM 模塊和一個批量為 ?? log2?? 的操作，需要 ??(log ??) 個采樣輪次，每個輪次需要 ??(log ??) 步的模塊間指針追蹤來搜索下部部分。相比之下，主要階段只需要 ??(log ??) 步。此外，預(yù)處理階段需要記錄整個搜索路徑，這也是 CPU 端的另一個開銷。 我們的新有序索引（PIM 樹）使用了與這項工作相同的一些思想，但包括了關(guān)鍵的新思想，使其在理論上和實踐上更簡單、更高效。

3 PIM-樹設(shè)計

概述。PIM-樹是為 PIM 系統(tǒng)設(shè)計的批處理并行抗傾斜有序索引。它支持基本的鍵-值操作，包括 Get(key)、Update(key, value)、Predecessor(key)、Insert(key, value)、Delete(key) 和 Scan(Lkey, Rkey)。它以相同類型的原子批次并行執(zhí)行操作，類似于[28]。因此，該數(shù)據(jù)結(jié)構(gòu)避免了不同類型操作引起的沖突。我們從 §2.4 中討論的結(jié)構(gòu)開始設(shè)計它。

在本節(jié)中，我們通過研究我們的技術(shù)/優(yōu)化對 Predecessor 操作的影響來描述 PIM-樹的設(shè)計。我們詳細回顧了 §2.4 中討論的基本數(shù)據(jù)結(jié)構(gòu)設(shè)計，然后介紹我們的三個關(guān)鍵技術(shù)/優(yōu)化，并最終分析由此產(chǎn)生的通信成本和負載平衡。稍后在第 4 節(jié)中，我們將描述 PIM-樹的其他操作的設(shè)計。

符號。我們將 PIM 模塊數(shù)量表示為 ??，索引中元素的總數(shù)表示為 ??，批處理大小表示為 ??，PIM-樹節(jié)點的預(yù)期分支度表示為 ??。 關(guān)鍵思想。我們觀察到 PIM 架構(gòu)的兩個組成部分，即 CPU 端和 PIM 端，偏好不同的工作負載。分布式的 PIM 端偏好均勻隨機的工作負載，并且受到高度傾斜工作負載引起的負載不平衡的影響。與此同時，共享的 CPU 端偏好傾斜的工作負載，因為我們可以在這些工作負載中探索空間和時間的局部性，從而實現(xiàn)更好的緩存效率。這種差異顯示了共享內(nèi)存計算和分布式計算的互補性，以及它們在 PIM 架構(gòu)中的共存激發(fā)了我們的混合方法：我們設(shè)計了一種動態(tài)勞動分工策略，自動在 CPU 端和 PIM 端之間切換使用更理想的平臺。這種策略稱為推拉搜索，是 PIM-樹的核心技術(shù)。

通過推拉搜索實現(xiàn)負載平衡后，我們進一步提出了另外兩種優(yōu)化，稱為影子子樹和分塊，以減少通信。這些優(yōu)化分別由兩個基本思想驅(qū)動：在 PIM 模塊上緩存遠程訪問以構(gòu)建本地快捷方式（從而消除通信），以及將節(jié)點分塊（以獲得更好的局部性）。我們將展示這些“傳統(tǒng)”技術(shù)如何與推拉搜索優(yōu)化相結(jié)合，將通信的漸近降低從??(log ??) 降低到 ??(log?? log?? ??)（?? 是分塊節(jié)點的預(yù)期分支度），并且吞吐量增加高達 69.7 倍，與 §2.4 的 PIM 友好型跳表相比。

3.1 基本結(jié)構(gòu) PIM

PIM 平衡跳躍表是一種分布式跳躍表，水平地分成三個部分：上部、下部和數(shù)據(jù)節(jié)點（圖 2）。數(shù)據(jù)節(jié)點是隨機分布到 PIM 模塊的鍵值對，以支持基于哈希的一輪查找和??(1) 通信。每個上部節(jié)點都在所有 PIM 模塊中進行復(fù)制，每個下部節(jié)點都存儲在一個隨機的 PIM 模塊中。托遠指針稱為 PIM 指針，由（PIM ID，地址）對組成。圖 2 中，PIM 指針由虛線箭頭表示，而傳統(tǒng)的（即 intra-PIM）指針則由實線箭頭表示。為了在搜索過程中節(jié)省通信量，每個下部節(jié)點都存儲相同層級的下一個跳躍表節(jié)點的鍵（稱為右鍵）。每個鍵都有一個在最低層的節(jié)點，并且一個節(jié)點加入跳躍表下一個更高層次的概率被設(shè)置為 1/2。上部被復(fù)制以便在 PIM 模塊上進行本地查詢，但是復(fù)制帶來了??的開銷，同時也增加了空間復(fù)雜性和更新成本。為了減輕這種開銷，下部高度被設(shè)置為 ??low = log ??，這樣只有 1/2log ?? = 1/?? 的鍵才會到達上部。通過復(fù)制上部，Predecessor 查詢所需的遠程訪問次數(shù)從 ??(log??) 降低到 ??(log ??)。

在接下來的章節(jié)中，我們稱上部為 L3，下部為 L2。在應(yīng)用陰影子樹優(yōu)化（§3.3）后，我們將進一步將下部水平分成兩部分，稱為 L2 和 L1。

3.2 推拉搜索

推拉搜索是我們提出的搜索方法，它可以在工作負載不均衡的情況下保證負載平衡。在推方法中，CPU 將查詢發(fā)送到沿著搜索路徑的下一個節(jié)點的主機 PIM 模塊，PIM 模塊運行查詢，然后 CPU 拉取結(jié)果；在拉方法中，CPU 檢索沿路徑的下一個節(jié)點返回到 CPU 端，自己運行查詢。推拉搜索通過計算每個節(jié)點的查詢數(shù)量來選擇推或拉：當對一個節(jié)點的查詢數(shù)量超過特定閾值（以下稱為 ??）時，選擇拉，否則推。 更具體地說，推拉搜索在三個階段內(nèi)對 §3.1 中提到的基本結(jié)構(gòu)執(zhí)行多輪指針跟蹤，其中 CPU 在整個過程中將每個查詢的下一個指針記錄為 PIM 指針數(shù)組。

1. 使用復(fù)制的上部遍歷 L3。CPU 平均分配查詢給 PIM 模塊。每個 PIM 模塊使用其本地副本運行其查詢，直到到達 L2 節(jié)點的指針。CPU 檢索這些指針（使用 PIM_Gather）。
2. 使用感知競爭的推拉遍歷 L2。CPU 執(zhí)行多個推拉輪。在每一輪中，CPU 計算在每個 L2 節(jié)點上的查詢數(shù)量。如果對一個節(jié)點的查詢超過了 ??，則選擇拉，通過向 PIM 端發(fā)送任務(wù)將該節(jié)點檢索到 CPU 端，然后根據(jù)檢索到的節(jié)點的指針在 CPU 端上并行地根據(jù) PIM IDs 對查詢進行分區(qū)。否則，選擇推，向 PIM 發(fā)送查詢?nèi)蝿?wù)并檢索查詢的下一個指針。
3. 當搜索到達數(shù)據(jù)節(jié)點時，返回數(shù)據(jù)。

我們可以記錄 CPU 端查詢路徑上所有節(jié)點的地址，以獲取每個查詢的搜索跟蹤。請注意，在執(zhí)行更新時（在 §4 中），將使用這些跟蹤。對于§3.1中提到的基本結(jié)構(gòu)，我們選擇 ?? = 1，因為它可以最小化大小恒定的節(jié)點的通信量。

討論。推拉搜索最有趣的部分是它基于集成分布式計算和共享內(nèi)存計算兩種基本方法來實現(xiàn)可證明的負載平衡和低成本（見§3.5分析）。我們觀察到推方法是一種分布式計算技術(shù)，因為它使用 CPU 作為路由器并始終在 PIM 模塊上運行查詢。同時，拉方法是一種共享內(nèi)存技術(shù)，將 PIM 模塊視為標準內(nèi)存模塊，并在 CPU 上運行查詢。正如 §3 中所討論的，將這兩種基本方法相結(jié)合起來是有效的，因為 CPU 端和 PIM 端在負載平衡問題上具有互補性：引起爭用的工作負載（因此不適合 PIM）與友好的 CPU 工作負載同時存在。作為解決負載平衡問題的解決方案，推拉搜索在最壞情況下的邊界與僅采用推或拉方法相比沒有漸近改進。我們的優(yōu)化，陰影子樹和分塊，提供了這樣的改進，我們將在接下來介紹。

3.3 影子子樹

影子子樹是L2中的輔助數(shù)據(jù)結(jié)構(gòu)，作為快捷方式來縮短每個查詢的通信從??(log ??)到??(log log ??)，同時確?？臻g復(fù)雜度仍為??(??)。影子子樹優(yōu)化基于跳表定義的搜索樹的思想，跳表是由合并跳表的所有可能搜索路徑生成的虛擬樹。它包含跳表的所有節(jié)點和所有邊緣，除了一些水平邊緣。每個節(jié)點的影子子樹是存儲在該節(jié)點中的其搜索子樹的影子副本。通過使用影子子樹，PIM模塊可以通過L2本地運行查詢。雖然影子子樹和復(fù)制樹的頂部都涉及將節(jié)點在不同的PIM模塊之間復(fù)制以減少通信，但它們實際上是非常不同的。當復(fù)制頂部時，單個樹被復(fù)制??次穿過模塊。在影子子樹中，每個節(jié)點的每個祖先都有該節(jié)點的副本作為其影子子樹的一部分（在我們的情況下僅在L2中的祖先）。

在所有（??(??)) L2節(jié)點上構(gòu)建影子子樹將需要??(?? log ??)的空間。為了保持??(??)的空間，我們僅在一小部分L2節(jié)點上構(gòu)建它們。特別地，我們將L2分成兩層，將上層稱為新的L2，將下層稱為L1。我們僅在新的L2上構(gòu)建影子子樹。我們將L1的高度設(shè)置為??L1 = log log ??，因此僅有（1/log ??）的節(jié)點（??(??/log ??)節(jié)點）位于新的L2中，并且所有影子子樹的空間復(fù)雜度總和為??(??)。因此，PIM樹現(xiàn)在具有三個層：完全復(fù)制的L3，具有影子子樹的L2以及沒有任何復(fù)制的隨機分布的L1。每個層都需要??(??)的空間，因此總空間復(fù)雜度為??(??)。這在圖3中顯示。我們將原始樹節(jié)點及其指針稱為物理節(jié)點（指針），并用黑色標記它們。我們將影子樹節(jié)點及其指針稱為影子節(jié)點和指針，并用紅色標記它們。

引入影子子樹后，L2和L1的結(jié)構(gòu)。 影子節(jié)點和影子指針用紅色標記。請注意，藍色的1沒有3的影子樹節(jié)點，因為節(jié)點3不在其搜索子樹中。右鍵被省略。我們還省略了從影子節(jié)點到物理節(jié)點的指針，除了節(jié)點A。 L1部分（L2部分）分別為對數(shù)對數(shù) ?? 層（對數(shù) ?? - 對數(shù)對數(shù) ?? 層）。

使用影子子樹加速Predecessor。影子子樹增強了Push-Pull搜索的Push側(cè)：單個Push輪可以通過運行影子子樹上的查詢將查詢發(fā)送到整個L2，而不僅僅是向前移動一級。因此，對于均勻隨機工作負載，搜索過程僅需要??(log log ??)輪：在L3中進行一次Push，L2中進行一次Push和L1中的??(??L1) = ??(log log ??)次Push-Pull輪。但是，對于偏斜的工作負載，我們不能簡單地通過L2執(zhí)行單個Push輪，因為多個查詢?nèi)钥赡鼙煌扑偷絃2中的爭用點并導致負載不平衡。我們通過Pull再次解決這個問題，通過引入多輪Pull過程來消除爭用點。

更詳細地說，在L2中的Push-Pull搜索有兩個階段：我們首先執(zhí)行最多??(??L2) Pull輪以處理至少具有??個查詢的節(jié)點，直到不存在這樣的節(jié)點為止，其中??L2 = log ?? - log log ??表示新L2的高度，然后執(zhí)行一輪“Push”以通過L2發(fā)送所有查詢。我們將閾值??設(shè)置為?? = ??L2而不是1，因為現(xiàn)在“Push”更強大，我們傾向于更多地使用它。這兩個階段每個查詢需要??(1)的平衡通信。這在引理3.2中部分證明，在完整的論文[20]中完全證明。

在實踐中，我們使用另一種優(yōu)化來減少Pull輪數(shù)。請注意，盡管爭用點是負載不平衡的唯一來源，但在消除所有爭用點之前，我們可能已經(jīng)達到了合理的負載平衡水平。因此，為避免不必要的Pull輪，開始Pull輪之前，我們通過計算將發(fā)送到每個PIM模塊的查詢數(shù)量來衡量跨PIMs的負載平衡；如果具有最多查詢的模塊低于平均負載的3倍，則停止Pull輪并開始Push。

復(fù)制和空間/平衡權(quán)衡。與用于 L3 的完全復(fù)制和 (ii) 用于相關(guān)工作中不執(zhí)行復(fù)制的范圍分區(qū)相比，影子子樹是一種新穎的方案，它通過改善分布式有序索引的本地性來支持具有 ??(1) 通信的查詢。具體而言，影子子樹是一種選擇性復(fù)制方法，介于這兩種先前的方案之間。如果我們將節(jié)點不僅復(fù)制到其 L2 祖先，而是復(fù)制到所有 PIM 模塊，我們就會獲得完全復(fù)制。另一方面，如果我們只保留 L2 根的影子子樹，則會獲得范圍分區(qū)方案。

影子子樹的成本和偏移抵消也介于其他兩個方案之間。表1顯示了將不同方案應(yīng)用于高度為 log ??，大小為 ?? 的跳表時的界限。在完全復(fù)制方案中，我們可以以完美的負載平衡運行查詢，但它會給空間復(fù)雜度和更新成本帶來一個超額因子 ??。另一方面，對于分區(qū)方案，每個查詢只能由一個 PIM 模塊執(zhí)行。我們?nèi)匀豢梢詧?zhí)行 Push-Pull 以避免與閾值 ?? = ?? 的爭用：當查詢數(shù)量超過整個部分的大小時，我們將選擇僅拉取整個樹。可能存在負載不平衡，因為某些部分最多有 ?? 個查詢，而其他部分則沒有。對于這種方法，空間復(fù)雜度和更新都沒有超額。最后，使用影子子樹，超額因子為 ??(log ??)，因為每個節(jié)點都在其所有 L2 搜索樹祖先中復(fù)制，根據(jù)我們對 Push-Pull 閾值 ?? = ??L2 的選擇，最大查詢數(shù)為 log ??。

因此，影子子樹在兩種方案之間提供了一個平衡的折衷，為超額和偏移抵消提供了一個甜蜜的點。

3.4 塊狀跳表

塊狀或“阻塞”是一種經(jīng)典思想，在本地感知數(shù)據(jù)結(jié)構(gòu)中廣泛使用，例如 B 樹和 B+ 樹。為了改善本地性，我們應(yīng)用類似的塊狀方法來改善 PIM 計算的訪問粒度，同時降低樹高度。由于塊狀增加了訪問粒度，因此每個 PIM 處理器獲得更大的本地內(nèi)存帶寬，從而獲得更好的性能。[15]詳細討論了 PIM 中訪問粒度的影響。

我們將塊狀應(yīng)用于 PIM 樹的所有層。在 L3 中，我們使用批量并行多線程 B+-樹 [28] 替換了多線程跳表。在 L2 和 L1 中，我們對跳表中的節(jié)點進行分塊以獲得塊狀跳表。我們首先將水平非樞軸節(jié)點（其鍵不進入上層）合并為單個塊，然后刪除冗余的影子子樹。在 Figure 3 上應(yīng)用這個兩步過程首先給出 Figure 4 作為中間狀態(tài)，最后給出 Figure 5 中的 PIM 樹。

帶有影子子樹的結(jié)果看起來類似于 B+-樹。不同之處在于，當較低層節(jié)點溢出時，B+-樹會將節(jié)點發(fā)送到上層，而塊狀跳表使用在插入期間生成的隨機高度，因此扇出期望保持不變。我們將跳表中達到下一層的概率從 1/2 減少到 1/??，因此預(yù)期的扇出為 ??。L3、L2 和 L1 中選擇相同的塊大小 ?? 是為了簡化，但每個部分可以使用不同的因子。正如 §4.2 中討論的那樣，在 L2 中使用塊狀跳表而不是傳統(tǒng)的 B+-樹可以使批量并行分布式插入和刪除更簡單、更有效。在 L3 中使用 B+-樹是因為該結(jié)構(gòu)不是分布式的，使得批量并行插入和刪除更容易。

塊狀減少了所有層的樹高度，從而改善了我們設(shè)計的多個方面。我們將新的 L2（L1）高度表示為 ??' L2（??' L1）。到每個節(jié)點的 L2 部分搜索路徑從 ??(??L2) = ??(log ??) 減少到 ??' L2 = log???? - log??log????，因為不再有水平指針追蹤過程。因此，影子子樹的空間和復(fù)制開銷從 ??(??L2) 減少到 ??' L2，因為每個節(jié)點僅在其 L2 祖先中復(fù)制。此外，較低的開銷使我們能夠?qū)???' L1 降低到 log??log????。在實踐中，??' L1 在實踐中有效地為 1，因為我們選擇 ?? = 16，要超過 1019 個 PIM 模塊才能使 ??' L1 超過 1。

因此，在實踐中，L2 的高度減少到 2 層，L1 的高度減少到 1 層。一個鍵達到 L3 的概率為 1/4096 < 1/??，到達 L2 的概率為 1/16 < log16 ??。

實現(xiàn) Chunking 后的 Predecessor。Chunking 對搜索過程只做了一個修改：將 Push-Pull 閾值 ?? 從 ??L2 改變?yōu)??? · ??'L2，因為我們現(xiàn)在“Pull” 預(yù)期大小為 ??(??) 的塊，而不是 ??(1)。詳細算法解釋見 §3.5。

Chunking 也改善了 Predecessor 的通信成本。首先，由于 L1 的高度從 log log ?? 降低到 log?? log?? ??，每次查詢僅導致 L1 中的通信量為 ??(log?? log?? ??)。其次，Chunking 將 L2 中 Pull-only 輪次的最大可能數(shù)量從 ??(??L2) = ??(log ??) 減少到完全為 ??'L2，即 log?? ?? ? log?? log?? ??。這有助于在工作負載傾斜情況下減少通信輪次的數(shù)量。

3.5 Predecessor 算法和界限

接下來，我們描述 Predecessor 的完整算法，并討論其成本復(fù)雜度。我們?yōu)?Predecessor 查詢的通信成本和負載平衡提供證明。為簡便起見，在本文中，我們的成本分析假設(shè)哈希函數(shù)提供均勻隨機映射到 PIM 模塊，這樣 §2.2 中的引理可以被應(yīng)用。算法 2 總結(jié)了搜索過程。我們在圖 5 中展示了一個在 PIM 樹上進行四個查詢的 Predecessor 批處理的迷你逐步示例（請注意，真實批處理應(yīng)在此樹上有更多查詢以實現(xiàn)負載平衡）。這些查詢請求鍵為 1、3、4 和 7 的 Predecessors。PIM 樹首先均勻分配了四個 PIM 模塊中的每個模塊的一個查詢來搜索 L3，返回三個查詢落入 L2 節(jié)點 [?∞, 3]，一個落入節(jié)點 [5, 7]。由于黃色掩碼的 PIM 模塊存在較大爭用，節(jié)點 [?∞, 3] 的上下文將被從該模塊拉到 CPU，鍵 1、3 和 4 在 L2 上的指針追蹤搜索將在 CPU 端執(zhí)行。之后，查詢 1、查詢 (3, 4) 和查詢 7 將被推送到包含藍色掩碼節(jié)點 [?∞, 1]、綠色掩碼節(jié)點 [3] 和綠色掩碼節(jié)點 [5, 7] 的 PIM 模塊上的本地陰影子樹中搜索 L2。最后，所有查詢將以類似的 Push-Pull 方式執(zhí)行，從 L1 和數(shù)據(jù)節(jié)點返回結(jié)果。

定理 3.1。一批 Predecessor 查詢可以在 ??(log?? ??) 通信輪次內(nèi)執(zhí)行，每個操作總體的通信成本為 ??(log?? log?? ??)，并且如果批處理大小 ?? = Ω(?? log ?? · ?? · ??'L2) = Ω(?? log ?? · ?? · log?? ??)，則執(zhí)行是負載平衡的。CPU 端內(nèi)存占用為 ??(??)。我們在這里提供部分證明，并在完整論文 [20] 中給出所有細節(jié)的完整證明。關(guān)鍵挑戰(zhàn)在于證明通信界限和負載平衡，我們通過為算法 2 的每個階段分別證明來實現(xiàn)這一點。我們以引理 3.2，L2 Push 階段（第3階段）的證明為例。

引理 3.2（L2 的 Push 輪）。使用陰影子樹進行 Push（第3階段）需要 1 輪，每個查詢的通信成本為 ??(1)，并且是負載平衡的。

證明。在這個階段，我們將每個查詢作為任務(wù)發(fā)送到相應(yīng)的 PIM 模塊，每個查詢產(chǎn)生 ??(1) 的通信成本，總共 1 輪。對于負載平衡，我們將其分析為一個加權(quán)球放入箱子的游戲，其中將目標節(jié)點視為球，目標節(jié)點上的查詢數(shù)量視為權(quán)重，PIMs 視為箱子。根據(jù)假設(shè)，權(quán)重限制為 ?? = ?? · ??'L2，因為每個節(jié)點最多獲得 ?? 個查詢，并且權(quán)重總和最多為 ??。應(yīng)用引理 2.2，每個 PIM 模塊產(chǎn)生 ??(??/??) 的通信成本。

4 PIM-TREE: 其他操作

在第3節(jié)中描述了PIM-tree數(shù)據(jù)結(jié)構(gòu)的設(shè)計，以Predecessor操作為運行示例，我們現(xiàn)在簡要介紹其他PIM-tree操作的實現(xiàn)方式。更多細節(jié)請參考全文 [20]。

4.1 哈希獲取和更新

Get 和 Update 是根據(jù)給定鍵進行的操作。這些操作也不會修改數(shù)據(jù)結(jié)構(gòu)的形態(tài)。因此，我們通過基于哈希的方法解決這些操作，每次操作耗費 ??(1) 的通信。首先使用固定的哈希函數(shù)將鍵映射到PIM模塊，然后在每個PIM模塊上構(gòu)建本地哈希表，將鍵映射到其數(shù)據(jù)節(jié)點的本地內(nèi)存地址。

由于數(shù)據(jù)節(jié)點是由哈希函數(shù)分布的，即使工作負載傾斜，我們也能實現(xiàn)良好的負載平衡，假設(shè)沒有重復(fù)操作指向相同的鍵。如果存在這樣的冗余操作，我們可以通過預(yù)處理在CPU端組合操作，使用用戶定義的組合機制來解決這個問題。在實踐中，我們在PIM端使用線性探測哈希表，但也可以使用其他哈希表變體。

4.2 插入

Insert(key,value) 操作將鍵插入到其搜索路徑上的節(jié)點中，主要挑戰(zhàn)在于避免多個批量插入操作同時到達相同節(jié)點時的爭用和沖突。我們通過預(yù)處理來解決這個問題：并行進行搜索，并記錄每次搜索的軌跡，然后使用這些軌跡來檢測和處理爭用點。我們的算法分為三個階段：（1）執(zhí)行搜索以記錄搜索軌跡，（2）根據(jù)搜索軌跡修改物理跳表，（3）更新影子子樹。

更新物理跳表。在獲得每次插入的搜索軌跡之后，我們根據(jù)在更新PIM-tree之前生成的隨機高度，將其插入這些節(jié)點。圖6是我們解決爭用的策略示例。根據(jù)它們預(yù)生成的高度，3的插入是進入黃色節(jié)點，6和8的插入將會分裂該節(jié)點。插入分為三步：在(b)中，我們將節(jié)點的右側(cè)部分提取到CPU端，并在隨機PIM模塊中生成空的新節(jié)點；在(c)中，我們在CPU端確定要插入到每個節(jié)點的正確元素；最后在(d)中，我們將它們插入。

選擇跳表而不是B+-樹作為L1和L2的基礎(chǔ)有助于減少輪數(shù)，因為我們可以并行地向所有節(jié)點插入，而不是像B+-樹那樣從葉子節(jié)點逐層自底向上插入。向L3插入也與L2的插入并行執(zhí)行，通過將達到L3的插入廣播到所有PIM來執(zhí)行。

更新影子子樹。為了保持影子子樹是搜索子樹的副本這一不變性，我們在更新物理跳表后更新影子子樹。有三種類型的更新：（1）為新節(jié)點構(gòu)建新的影子子樹，（2）將新節(jié)點插入到其祖先的影子子樹中，（3）在節(jié)點分裂后修剪影子子樹。

我們的影子子樹更新技術(shù)很簡單。對于構(gòu)建，我們提取L2搜索樹并將其發(fā)送到新節(jié)點。對于插入和修剪，我們觀察到只有搜索軌跡上的節(jié)點的影子子樹需要更新，所以我們將新插入的節(jié)點發(fā)送到所有這些節(jié)點。

討論：插入中的負載平衡。在我們的影子子樹更新算法中存在負載平衡問題：為了保持影子子樹的最新狀態(tài)，一個L2節(jié)點可能需要大小為 ??(??/log?? ??) 的更新。例如，一個新的L2根需要構(gòu)建其預(yù)期大小為 ??(??/log?? ??) 的影子子樹（給定 ?? ′ ??2 = log?? ?? ? log?? log?? ??）。這種爭用因子 ??(??/log?? ??) 會隨著 ?? 的增長比 Predecessor 的因子 ?? = ?? · log?? ?? 增長得更快。目前這種爭用影響較小，但我們提出了一個算法來解決這個問題（目前尚未實施）。

解決方法不是保持所有影子子樹的最新狀態(tài)，而是將一些節(jié)點標記為未完成，在將來的輪數(shù)逐漸更新它們的影子子樹，并避免在其最新狀態(tài)之前使用影子子樹。這有助于平衡負載。當這些節(jié)點的數(shù)量低于一個閾值時，Predecessor的界限仍然成立，我們通過額外的更新輪數(shù)來實現(xiàn)這一點，當這些節(jié)點的數(shù)量很多時，負載也是平衡的。

定理 4.1. 一批插入操作可以在 ??(log?? ??) 的IO輪中執(zhí)行，每個操作產(chǎn)生 ??(log?? log?? ??) 的通信。如果批量大小 ?? = Ω(?? log ?? · ?? · ?? ′ L2) = Ω(?? log ?? · ?? · log?? ??)，則執(zhí)行是負載平衡的。CPU端的內(nèi)存占用為 ??(??)。

Delete的實現(xiàn)。我們處理刪除與插入類似：首先獲得搜索軌跡，然后從搜索軌跡上的節(jié)點中刪除鍵，最后對影子子樹應(yīng)用更新。當插入導致節(jié)點分裂時，刪除會導致在從節(jié)點中移除樞紐鍵時節(jié)點合并。詳情請見全文 [20]。

4.3 掃描

Scan(LKey, Rkey) 操作（又稱范圍查詢）返回所有鍵值對，其鍵落入[Lkey, Rkey]范圍內(nèi)。其算法類似于Predecessor。

在運行一批掃描查詢時，我們首先在CPU上將所有批處理的重疊范圍合并為不相交范圍組。然后PIM樹為每個范圍的兩個邊界節(jié)點（樹的當前搜索層上Lkey和Rkey的前驅(qū)）標記為SearchReqired，并將所有中間節(jié)點標記為FetchAll。FetchAll 節(jié)點需要返回它們所有的葉子數(shù)據(jù)節(jié)點。需要注意的是所有范圍都是不相交的，因此在FetchAll節(jié)點中不存在爭用。所有FetchAll節(jié)點被推送到PIM，并遞歸地返回所有子節(jié)點。與此同時，每個范圍的SearchReqired節(jié)點在每個級別上都類似于Predecessor進行維護，使用推拉式搜索來處理潛在的爭用。這可能會生成新的FetchAll節(jié)點。詳細內(nèi)容請參見完整論文[20]。

5 實現(xiàn)

CPU-PIM 管道。到目前為止，我們介紹了CPU和PIM在每一輪以同步的tick-tock方式運行的算法，如算法1所示。該方法的總執(zhí)行時間包括三個不重疊的組件：僅CPU時間、僅PIM時間和通信時間。通信需要CPU和PIM，但其他兩個組件只利用系統(tǒng)的一部分，這提供了通過對CPU和PIM的管道化來減少執(zhí)行時間的機會。

對于管道化，我們考慮在PIM樹中并行運行多個批次的執(zhí)行。如圖7所示，“CPU”代表僅CPU執(zhí)行所花費的時間，“IO & PIM”代表在CPU-PIM通信和PIM程序中花費的時間。在我們的UPMEM系統(tǒng)上，CPU-PIM通信需要獨占PIM端的控制，并且對PIM端的任何并發(fā)使用都會導致硬件故障。因此，一個批次需要等待PIM端完成當前的執(zhí)行任務(wù)。在我們的實驗中，我們只對查詢進行了管道化，因為更新批次無法同時進行。對于混合操作，我們通過讀寫鎖保護PIM樹，以防止更新批次與其他批次同時運行。

PIM程序。PIM樹的PIM程序是從CPU發(fā)送的緩沖區(qū)中任務(wù)的并行執(zhí)行器。它設(shè)計用于解決UPMEM當前PIM處理器的兩個特性。首先，PIM處理器是一個細粒度的多線程計算單元[15]，需要至少11個線程來填充管道，因此我們以12個線程的形式編寫PIM程序。其次，UPMEM的系統(tǒng)僅支持指令少于4K的PIM程序，但PIM-tree的實現(xiàn)超過了這一限制。為了繞過這一限制，我們將PIM程序編寫為多個獨立的模塊，并在需要時加載每個模塊。只有插入和刪除操作需要交換模塊；目前，程序加載大約占執(zhí)行時間的25%。在PIM樹上的其余操作符合4K指令限制。

6 評估

在本節(jié)中，我們在UPMEM提供的PIM設(shè)備上評估了我們的新的PIM優(yōu)化索引，并在性能相似的計算機上評估了兩種傳統(tǒng)的最新索引。

我們總結(jié)了本節(jié)的實驗結(jié)果如下： （1）在偏斜工作負載下，PIM-tree在吞吐量、內(nèi)存總線通信和能耗方面優(yōu)于范圍分區(qū)跳表。 （2）與沒有PIM的傳統(tǒng)索引相比，PIM-tree在內(nèi)存總線上引起較低的通信。 （3）所有優(yōu)化，包括Push-Pull搜索、影子子樹、分塊跳表和CPU-PIM管道化，都使（某些）PIM-tree操作的性能提高。

6.1 實驗設(shè)置

UPMEM 的 PIM 平臺。我們在由 UPMEM 提供的一臺裝備有 PIM 技術(shù)的服務(wù)器上測試 PIM-tree。該服務(wù)器配備兩個 Intel(R) Xeon(R) Silver 4126 CPU，每個 CPU 都有 16 個核心，主頻為 2.10 GHz，緩存為 22 MB。每個插槽都有 6 個內(nèi)存通道：其中 2 個通道實現(xiàn)了 4 個傳統(tǒng) DRAM DIMM，而另外 4 個通道則使用了 8 個 UPMEM DIMM。每個 UPMEM DIMM 都有 2 個 rank，每個 rank 有 8 個芯片，每個芯片有 8 個 PIM 模塊。總共有2048 個 PIM 模塊。

不帶 PIM 的傳統(tǒng)機器。我們在一臺具有兩個 Intel(R) Xeon(R) CPU E5-2630 v4 CPU 的機器上評估傳統(tǒng)索引，每個 CPU 都有 10 個核心，主頻為 2.20 GHz，緩存為 25 MB。每個插槽有 4 個內(nèi)存通道。沒有帶 PIM 的 DIMM。我們不能在 UPMEM 的服務(wù)器上評估傳統(tǒng)索引，因為其 2/3 的內(nèi)存通道被 PIM 帶的 DIMM 使用，這些 DIMM 不能用作主內(nèi)存。直接在服務(wù)器上運行傳統(tǒng)索引將導致主存帶寬不公平。在我們的實驗中，我們選擇了最先進的二叉搜索樹[8]和（a，b）樹[9]作為競爭對手。這兩種實現(xiàn)都來自于 SetBench[4]。

基于范圍劃分和 Jump-Push 的基準線。我們實現(xiàn)了一種基于范圍劃分的有序 PIM 索引作為我們的基準線，其中數(shù)據(jù)節(jié)點和索引節(jié)點都基于關(guān)鍵字的范圍分配到 PIM 模塊上[10, 24]。我們在 CPU 端記錄范圍拆分，并使用這些拆分來找到每個操作的目標 PIM 模塊。點操作被發(fā)送到相應(yīng)的 PIM 模塊并在其上執(zhí)行。掃描操作的運行方式類似，只是在將任務(wù)發(fā)送到 PIMs 之前，需要根據(jù)范圍拆分在查詢中運行額外的拆分。我們還在所有 PIM 模塊上構(gòu)建了一個本地哈希表，用于獲取。我們還實現(xiàn)了§2.4 中描述的 PIM 平衡跳表[19]作為另一個基準線。在討論本文中提出的優(yōu)化的影響時，我們在圖 11 中通過稱為“Jump-Push based”的算法實驗評估了這種方法。

測試框架。我們在 PIM-tree、我們實現(xiàn)的基于范圍劃分的跳表和最先進的傳統(tǒng)索引上運行多種類型的操作。在所有實驗中，我們首先通過運行初始化集來插入鍵值對，然后通過評估集合內(nèi)的多個操作來評估索引。所有操作都從預(yù)生成的測試文件中加載。PIM 算法（PIM-tree 和基于范圍劃分）以批處理方式運行操作，而傳統(tǒng)索引則直接使用多線程并行運行它們。在所有實驗中，鍵和值的大小都設(shè)置為 8 個字節(jié)。

為了研究算法，我們測量了時間和內(nèi)存總線流量。內(nèi)存總線通信是通過添加 CPU-PIM 和 CPU-DRAM 通信來測量的，前者是通過每次調(diào)用 PIM 函數(shù)（例如 PIM_Broadcast）增加計數(shù)器來測量的，后者是通過 PAPI 測量緩存未命中來測量的。我們將程序綁定到單個 NUMA 節(jié)點，并在測量緩存未命中時禁用 CPU-PIM 管道，以獲得準確的流量測量。由于 PIM 帶的機器的每個 CPU 都有兩個 NUMA 節(jié)點，因此在此設(shè)置下，PIM 算法的有效緩存被減少到 11 MB，即完整緩存的一半。時間是以全互鎖方式測量的。

目前的 PIM 硬件性能不穩(wěn)定。我們在實驗中觀察到，上述測量指標的波動大約為 ±15%。

6.2 微基準測試

工作負載設(shè)置。每個測試首先通過插入 5 億個均勻隨機的鍵-值對來預(yù)熱索引；然后進行以下測試：(i) 執(zhí)行 1 億個點操作或 (ii) 執(zhí)行 100 萬次掃描操作，每次期望檢索 100 個元素。點操作使用批處理大小 ?? = 100 萬，掃描操作使用批處理大小 ?? = 1 萬。

我們使用 Zipfian 分布生成偏斜的工作負載 [37]。然而，通過 Zipfian 分布生成的偏斜工作負載并不適合評估批處理并行有序索引，因為這種偏斜可以在 CPU 端的預(yù)處理中輕松處理，通過將相同鍵的操作合并為一次操作。為了更好地表示空間偏差，在某些范圍內(nèi)的鍵更可能在同一批次中被訪問，我們稍微修改了生成 Zipfian 工作負載的方式，具體如下：(i) 我們將鍵空間均勻地分成 ?? = 2048 部分；(ii) 對于每個操作，我們首先根據(jù) Zipfian 分布選擇一個部分，然后在該部分中選擇一個均勻隨機的元素。對于現(xiàn)有鍵的操作（Get、Delete），我們將鍵空間劃分并從索引中當前存在的鍵中進行選擇；對于任意鍵的操作（Predecessor、Insert、Scan），鍵空間由所有 64 位整數(shù)組成。我們周期性地重新洗牌 Zipfian 分布的每個部分的概率。這有助于緩解但無法消除由于 Insert 在高概率部分累積導致的基于范圍分區(qū)的基準線的 PIM 內(nèi)存溢出問題。PIM 樹不會受益于這種洗牌。為了展示不同程度偏斜的結(jié)果，我們評估了 Zipfian 分布中不同 ?? 值下的算法，范圍從 0（均勻隨機）到 1.2。通過這種偏斜生成方法，在最偏斜的情況下（?? = 1.2），小于 10% 的操作由于重復(fù)鍵而被消除。

性能。圖 8 展示了基于范圍分區(qū)的跳表和 PIM 樹在微基準測試中的吞吐量。當查詢偏斜增加時，基于范圍分區(qū)的基準線性能急劇下降，而 PIM 樹則表現(xiàn)出對查詢偏斜的強大抵抗力。事實上，在所有操作中，觀察到 PIM 樹基本不受數(shù)據(jù)偏斜的影響，在 ?? = 0 和 ?? = 1.2 時獲得類似的運行時間。對于 ?? = 1.2，PIM 樹的性能優(yōu)于基于范圍分區(qū)的基準線 3.87–59.1 倍。

觀察到 Get 操作明顯更簡單且吞吐量更高，因為使用散列表作為快捷方式（對于 Update 操作也是如此），而 Predecessor 和 Scan 操作必須遍歷整個有序索引。在圖 8(c) 中，基于范圍分區(qū)的基準線在 ?? = 1.2 時插入操作崩潰，因為偏斜的插入導致 PIM 模塊數(shù)據(jù)不平衡分布，進而導致某些 PIM 模塊的本地內(nèi)存溢出。盡管這個問題可以通過重新平衡方案解決，重新平衡過程本身會導致負載不均衡，因為它需要將溢出的 PIM 模塊的數(shù)據(jù)發(fā)送到負載較輕的 PIM 模塊。觀察到即使對基準線進行了這種改進（文獻中現(xiàn)有的范圍分區(qū)解決方案未配備此功能），PIM 樹的吞吐量仍然明顯大于范圍分區(qū)，因為這將是基準線在執(zhí)行過程中必須執(zhí)行的額外工作。

圖 9 展示了 PIM 樹在我們的工作負載下與最先進的二叉搜索樹 [8] 和 (a,b)-tree [9] 的性能對比。在所有測試案例中，PIM 樹都優(yōu)于傳統(tǒng)索引，除了 Predecessor 的吞吐量比 (a,b)-tree 低外。

執(zhí)行分解。圖 10 展示了第 5 節(jié)提到的每個組件花費的時間比例。這些結(jié)果是在關(guān)閉我們的流水線優(yōu)化的情況下得出的，因為流水線會導致不同組件的重疊。我們選取基于范圍分區(qū)的跳表和 PIM 樹上 Predecessor 和 Insert 的吞吐量，對均勻隨機工作負載和 ?? = 0.6 的 Zipfian 偏斜工作負載進行了典型示例。在其他 ?? 值的情況下，類似的結(jié)果也存在。

對于基于范圍分區(qū)的跳表，PIM 執(zhí)行和 CPU-PIM 通信主要占據(jù)了偏斜工作負載的時間成本，主要是因為整個執(zhí)行的瓶頸——最繁忙的 PIM 模塊——正在接收越來越多的任務(wù)。

對于均勻隨機工作負載，PIM 執(zhí)行僅占總時間成本的一小部分，盡管幾乎所有比較都是在 PIM 模塊中執(zhí)行的。我們推斷，在這種情況下，當大量的 PIM 模塊參與時，已充分利用了并行性。我們相信這意味著基于 PIM 的系統(tǒng)是并行索引結(jié)構(gòu)的理想平臺。 在執(zhí)行過程中，PIM 樹插入花費時間加載 PIM 程序模塊，因為完整程序大小超過了旨在存儲 PIM 程序的 PIM 的指令內(nèi)存的當前大小。有關(guān)此限制的討論請參見第 5 節(jié)。

優(yōu)化效果。圖 11 展示了不同優(yōu)化對我們的有序索引的影響。在這里，我們從我們的 Jump-Push 基準線開始（參見 [19] 中的 PIM 平衡跳表）。將 Jump-Push 替換為 Push-Pull 在所有測試案例中提供了高達 6.8 倍的吞吐量改進。添加 Chunking 提供了最大的改進，跨所有測試案例高達 9.0 倍，同時添加 shadow subtrees 對無偏斜的 Predecessor 有所裨益。（Insert 獲得了較小的好處，因為它需要維護這種輔助數(shù)據(jù)結(jié)構(gòu)。）最后，添加流水線——實現(xiàn)完整的 PIM 樹算法——為 Predecessor 提供了額外的好處。（對于 Insert，并不支持我們的實現(xiàn)中不支持交錯的插入批處理。）與 Jump-Push 基準線相比，在研究的設(shè)置中，PIM 樹的吞吐量高達 69.7 倍。

內(nèi)存總線通信。圖 12 展示了 PIM 樹、基于范圍分區(qū)的跳表和傳統(tǒng)非 PIM 索引的平均通信量。PIM 樹的通信量比所有傳統(tǒng)索引都少。在均勻隨機工作負載下，基于范圍分區(qū)的跳表在通信量上勝過所有競爭對手，但在偏斜工作負載下表現(xiàn)得更差。

另一個觀察結(jié)果是，雖然 PIM 樹存儲所有數(shù)據(jù)并在 PIM 模塊中執(zhí)行大多數(shù)比較，但大部分內(nèi)存總線流量是在 CPU 和 DRAM 之間。這是因為盡管 PIM 樹算法對于一批操作需要 ??(??) 的 CPU 端內(nèi)存，但 11 MB 緩存的可用設(shè)置對于一百萬次操作的批處理來說太小了。因此，CPU 端數(shù)據(jù)溢出到 DRAM 并導致顯著的 CPU-DRAM 通信。為了展示這種溢出的影響，圖 13 中我們研究了隨著批處理大小從 1M 減小到 50K，我們運行 1 億次均勻隨機的 Predecessor 操作時 CPU 端通信的效果。結(jié)果顯示，隨著批處理大小的減小，CPU-DRAM 通信減少了 67%。我們不能直接使用較小的批處理大小，因為需要負載平衡，但這個結(jié)果暗示了當在具有更大緩存大小的機器上運行 PIM 樹時，我們可以獲得更少的 CPU-DRAM 通信。

推拉閾值選擇 我們研究了在不同推拉閾值下 PIM 樹的前趨性能。在我們的微基準測試中，當 ?? = 1 時，我們發(fā)現(xiàn)選擇較低的閾值會導致吞吐量下降約 10%，CPU-PIM 通信增加高達 28%。較高的閾值帶來輕微性能提升。更多細節(jié)請參考完整論文 [20]。

能量評估。與基于范圍分區(qū)的基準 PIM 相比，在偏斜情況下，PIM 樹的能耗大約降低了 5×–10×。詳細信息請參考本文的完整版本 [20]。

YCSB 工作負載。與基于范圍分區(qū)的基準 PIM 相比，在偏斜情況下，PIM 樹的吞吐量大約提高了 9.5×–32×。詳細信息請參考本文的完整版本 [20]。

6.3 現(xiàn)實世界偏斜工作負載

在本節(jié)中，我們使用公開可用的維基百科數(shù)據(jù)集 [12] 對 PIM 樹進行了在具有真實世界偏斜性的工作負載上的測試，該數(shù)據(jù)集是來自維基百科的一組文檔。為了在我們的測試框架中使用這個數(shù)據(jù)集，我們需要將其轉(zhuǎn)換為一組 8 字節(jié)的鍵值對，然后對其進行操作。具體來說，我們首先從每個文檔中提取單詞，并將它們轉(zhuǎn)換為小寫形式，然后將 (單詞，文檔 ID) 對作為鍵，隨機生成一個 8 字節(jié)整數(shù)作為值。由于我們的索引只支持 8 字節(jié)整數(shù)鍵，因此我們需要將 (單詞，文檔 ID) 對轉(zhuǎn)換為 8 字節(jié)整數(shù)。轉(zhuǎn)換過程如圖 14 所示。我們使用 40 位來表示單詞，23 位來存儲文檔 ID（因為文檔數(shù)量少于 2^23）。在單詞部分，我們使用前 5 個字母中的每個字母的 5 位，然后在接下來的 15 位中存儲整個單詞的哈希值，以避免沖突。經(jīng)過這種轉(zhuǎn)換，生成的整數(shù)保留了英語單詞的兩種偏斜性：(i) 單詞頻率偏斜（某些單詞比其他單詞更常用）和 (ii) 在字典順序空間中的單詞分布偏斜（具有某些前綴的單詞更常用）。在這個測試中，我們選擇了前 12 億個鍵：前 10 億個單詞用于初始化，接下來的 2 億個用于評估。這些鍵涵蓋了前 510 萬個文檔，占數(shù)據(jù)集的 63%。有 390 萬個唯一單詞，將單詞和文檔 ID 進行配對生成了 5.29 億個唯一鍵。我們僅對相同單詞在同一文檔中生成重復(fù)鍵。由于鍵的重復(fù)率約為 2??，我們還將 PIM 樹的批處理大小增加到 兩百萬。結(jié)果如圖 15 所示，吞吐量顯示為柱狀圖，通信（每次操作傳輸?shù)淖止?jié)數(shù)）顯示為標記點。在這個工作負載中，所有索引的吞吐量都比微基準測試中更高，通信量更低，這是因為存在復(fù)制的鍵。比較不同的索引得到了與微基準測試類似的結(jié)果：PIM 樹的前趨吞吐量低于 (a,b)-樹，但在所有其他指標上均優(yōu)于傳統(tǒng)索引。

7 討論

在大多數(shù)情況下，PIM 樹在吞吐量上優(yōu)于傳統(tǒng)索引，但在某些情況下卻不能勝過，比如我們論文中與 (a,b)-樹的前趨性能相比。我們在這里解釋了當前 PIM 系統(tǒng)的三個硬件限制，并描述了未來對硬件的改進將為 PIM 優(yōu)化的數(shù)據(jù)結(jié)構(gòu)帶來更好性能。

第一個因素是 UPMEM 新開發(fā)的硬件上 CPU-PIM 帶寬有限。在執(zhí)行 50% 讀取 - 50% 寫入任務(wù)時，UPMEM 機器上獲得的帶寬為 16GB/s，比我們在相同工作負載下使用的具有 31GB/s 帶寬的共享內(nèi)存機器慢 1.9×。即使在如此顯著的帶寬限制下，PIM 樹仍然比僅使用 DRAM 的索引實現(xiàn)了更好或相當?shù)男阅?，主要是因為它大大減少了模塊間通信。設(shè)計硬件以改善 CPU-PIM 帶寬因此是一個重要方向，我們期待未來的改進。因此，我們相信 PIM 樹將來將在吞吐量方面在所有情況下勝過傳統(tǒng)索引。

另一個問題是 PIM 程序的有限大小限制了我們進行更復(fù)雜設(shè)計。目前的解決方法——動態(tài)程序加載——成本太高。我們相信未來的硬件將通過更大的指令內(nèi)存來解決這個問題。

最后一個限制是不足的 CPU 緩存，正如第 6.2 節(jié)所述。由于緩存溢出造成的 CPU-DRAM 通信占據(jù)了大部分內(nèi)存總線通信，通過更大的緩存可以緩解這一問題。我們認為充分的緩存在未來的 PIM 系統(tǒng)中將是重要的。

8 結(jié)論

本文介紹了 PIM 樹，這是 PIM 系統(tǒng)中第一個有序索引，能夠在數(shù)據(jù)和查詢偏斜存在的情況下實現(xiàn)低通信和高負載平衡。我們對真實 PIM 系統(tǒng)上的有序索引進行了首次實驗評估，表明其吞吐量比前兩種最佳 PIM 方法高出 69.7× 和 59.1×，通信量比兩種最先進的傳統(tǒng)索引低至 0.3×。關(guān)鍵思想包括推拉搜索和影子子樹——這些技術(shù)可能對 PIM 系統(tǒng)上的其他應(yīng)用有用，因為它們在降低通信成本和管理偏斜方面非常有效。我們未來的工作將探索這些應(yīng)用（例如基于基數(shù)的索引、圖分析）。文章來源地址http://www.zghlxwxcb.cn/news/detail-831335.html

到了這里，關(guān)于論文閱讀-PIM-tree：一種面向內(nèi)存處理的抗偏移索引的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！