[發(fā)明專利]對多線程應(yīng)用的雜湊表執(zhí)行并行的重雜湊

有效

• 申請?zhí)枺?/td>: 200980159762.3
• 申請日: 2009-04-08
• 公開（公告）號: CN102460392A
• 公開（公告）日: 2012-05-16
• 發(fā)明（設(shè)計(jì)）人: A.A.馬拉霍夫
• 申請（專利權(quán)）人: 英特爾公司
• 主分類號: G06F9/46
• 分類號: G06F9/46
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 張濤;蔣駿

背景技術(shù)

雜湊表是在諸如數(shù)據(jù)庫、搜索引擎、統(tǒng)計(jì)處理和動態(tài)腳本語言的多種應(yīng)用中的基本構(gòu)成塊。雜湊表是一族將鍵（key）與值相關(guān)聯(lián)的容器。雜湊表使用其雜湊值以及容器的當(dāng)前容量來計(jì)算存儲在表的條目中的項(xiàng)目的放置位置，所述條目即桶（bucket）。然而，容器通常需要動態(tài)增加容量，這意味著附加存儲塊的重新分配或分配。所以，增加的容量導(dǎo)致了項(xiàng)目放置的無效并且需要項(xiàng)目被移動到新的地方，這通常被稱作重雜湊（rehashing）。

對于雜湊表的已知并行算法而言，在線程決定重新設(shè)定容器的大小時(shí)，該線程阻止（即，臨時(shí)停止）對該表的一些（或者甚至全部）并行操作，直至該線程完成了重新設(shè)定大小和重雜湊的處理二者。這導(dǎo)致了并行性的降低，并且因此導(dǎo)致了性能降低。另一個(gè)問題在于，具有重新設(shè)定大小的操作的運(yùn)行時(shí)間和復(fù)雜度明顯不同于沒有重新設(shè)定大小的相同操作。

附圖說明

圖1是依據(jù)本發(fā)明一個(gè)實(shí)施例的用于更新雜湊表的方法的流程圖。

圖2A是依據(jù)本發(fā)明一個(gè)實(shí)施例的桶的框圖。

圖2B是圖示依據(jù)本發(fā)明一個(gè)實(shí)施例的新桶分配的框圖。

圖2C是圖示依據(jù)本發(fā)明一個(gè)實(shí)施例的新桶分配的框圖。

圖3是依據(jù)本發(fā)明實(shí)施例的用于執(zhí)行查找/重雜湊的方法的流程圖。

圖4是依據(jù)本發(fā)明一個(gè)實(shí)施例的系統(tǒng)的框圖。

具體實(shí)施方式

實(shí)施例可以被用來對并行的雜湊表執(zhí)行并行的重新設(shè)定大小以及根據(jù)需要按桶進(jìn)行的重雜湊，所述并行的雜湊表是由可以在多處理器系統(tǒng)的一個(gè)或多個(gè)核心上執(zhí)行的一個(gè)或多個(gè)線程所訪問的共享存儲器，所述多處理器系統(tǒng)諸如具有一個(gè)或多個(gè)多核處理器的系統(tǒng)?？蓱?yīng)用于雜湊表的是，其中桶可以存儲一組項(xiàng)目。為了簡明，假設(shè)表的初始容量是2的冪。項(xiàng)目的雜湊值除以容量的余數(shù)給出了存儲該項(xiàng)目的桶的索引。在一些實(shí)施例中經(jīng)過簡化，桶的索引也可以通過以下公式來計(jì)算

?????等式（1）

其中hash是通過雜湊計(jì)算所獲得的雜湊值，在所述雜湊計(jì)算中，鍵被應(yīng)用于生成該雜湊值的雜湊函數(shù)，并且“&”表示二進(jìn)制表示的逐比特的與（AND）。在一個(gè)實(shí)施例中，容量可以以雜湊表的桶的數(shù)量為單位，但是本發(fā)明的范圍并不局限于此。

為了增加容量，依據(jù)本發(fā)明實(shí)施例的算法可以分配像現(xiàn)有桶那么多的桶并且保留舊桶，因此使得桶數(shù)加倍。每個(gè)新桶被邏輯映射到一個(gè)現(xiàn)有桶（母桶）上，除了最高位保持為值1之外，所述現(xiàn)有桶具有包括與新桶索引中相同的值（即，比特集）的索引。例如，如果一個(gè)桶的索引為二進(jìn)制表示的00101101，則母桶的相應(yīng)索引為00001101。也就是說，母桶的索引可以如下獲得：

????等式（2）

其中<<表示將二進(jìn)制的左側(cè)操作數(shù)移位由右側(cè)操作數(shù)所指定的比特?cái)?shù)。

在許多實(shí)現(xiàn)中，特定的新桶可以具有其它新桶作為母桶。如以下所描述的，導(dǎo)致它的分配在一些實(shí)現(xiàn)中可以被組合為單個(gè)存儲器請求。

現(xiàn)在參見圖1，示出了依據(jù)本發(fā)明一個(gè)實(shí)施例的用于更新雜湊表的方法的流程圖。如圖1所示，方法10可以通過確定雜湊表中所需要增加的空間來開始（框20）。雖然本發(fā)明的范圍并不局限于此，但是可以基于所述表的負(fù)載因數(shù)來進(jìn)行這樣的確定，例如在當(dāng)雜湊表中所存儲的數(shù)據(jù)量達(dá)到預(yù)定閾值時(shí)出現(xiàn)針對新數(shù)據(jù)對的插入操作時(shí)由系統(tǒng)軟件進(jìn)行，所述預(yù)定閾值例如是總表量的特定百分比。當(dāng)然，可以在其它實(shí)施例中使用確定所需要增加的空間的其它方式。例如，用戶可以在對保留操作的調(diào)用中指定一定數(shù)量的桶。

一旦進(jìn)行了這樣的確定，控制進(jìn)行至框30，在那里可以分配一定數(shù)量的新桶。更具體地，可以對應(yīng)于雜湊表中桶的當(dāng)前數(shù)量而分配一定數(shù)量的桶。以這種方式，分配給所述表的桶的數(shù)量被加倍。在一個(gè)實(shí)施例中，調(diào)用分配器以獲得所需的存儲器量并且將桶初始化為新的空桶。接著，可以公布該新的空間（框40）。雖然本發(fā)明的范圍并不局限于此，但是公布可以經(jīng)由對包含容量值的變量的更新來進(jìn)行。在一個(gè)實(shí)施例中，該更新可以經(jīng)由帶有針對“容量”變量的釋放操作（或原子寫）的存儲來進(jìn)行。可替換地，這樣的更新可以針對與容量值減1相對應(yīng)的掩碼（mask）。因此，通過分配新桶并且公布該新空間，完成分配而無需將存在于原始桶中的數(shù)據(jù)完全重雜湊到新桶中。也就是說，分配是獨(dú)立于重雜湊進(jìn)行的并且通過公布新空間而完成。新公布的空間中的每個(gè)桶最初被標(biāo)記為未重雜湊（non-rehashed）。