對多線程應用的雜湊表執行並行的重雜湊的製作方法
2023-10-10 06:00:54 2
專利名稱：對多線程應用的雜湊表執行並行的重雜湊的製作方法
對多線程應用的雜湊表執行並行的重雜湊
背景技術：
雜湊表是在諸如資料庫、搜尋引擎、統計處理和動態腳本語言的多種應用中的基本構成塊。雜湊表是一族將鍵(key)與值相關聯的容器。雜湊表使用其雜湊值以及容器的當前容量來計算存儲在表的條目中的項目的放置位置，所述條目即桶(bucket)。然而，容器通常需要動態增加容量，這意味著附加存儲塊的重新分配或分配。所以，增加的容量導致了項目放置的無效並且需要項目被移動到新的地方，這通常被稱作重雜湊(rehashing)。對於雜湊表的已知並行算法而言，在線程決定重新設定容器的大小時，該線程阻止(即，臨時停止)對該表的一些(或者甚至全部)並行操作，直至該線程完成了重新設定大小和重雜湊的處理二者。這導致了並行性的降低，並且因此導致了性能降低。另一個問題在於，具有重新設定大小的操作的運行時間和複雜度明顯不同於沒有重新設定大小的相同操作。
圖1是依據本發明一個實施例的用於更新雜湊表的方法的流程圖。圖2A是依據本發明一個實施例的桶的框圖。圖2B是圖示依據本發明一個實施例的新桶分配的框圖。圖2C是圖示依據本發明一個實施例的新桶分配的框圖。圖3是依據本發明實施例的用於執行查找/重雜湊的方法的流程圖。圖4是依據本發明一個實施例的系統的框圖。
具體實施例方式實施例可以被用來對並行的雜湊表執行並行的重新設定大小以及根據需要按桶進行的重雜湊，所述並行的雜湊表是由可以在多處理器系統的一個或多個核心上執行的一個或多個線程所訪問的共享存儲器，所述多處理器系統諸如具有一個或多個多核處理器的系統。可應用於雜湊表的是，其中桶可以存儲一組項目。為了簡明，假設表的初始容量是2 的冪。項目的雜湊值除以容量的餘數給出了存儲該項目的桶的索引。在一些實施例中經過簡化，桶的索引也可以通過以下公式來計算
bIidcetJdx = hash & (capacity - 1) 等式(1)
其中hash是通過雜湊計算所獲得的雜湊值，在所述雜湊計算中，鍵被應用於生成該雜湊值的雜湊函數，並且「&」表示二進位表示的逐比特的與(AND)。在一個實施例中，容量可以以雜湊表的桶的數量為單位，但是本發明的範圍並不局限於此。為了增加容量，依據本發明實施例的算法可以分配像現有桶那麼多的桶並且保留舊桶，因此使得桶數加倍。每個新桶被邏輯映射到一個現有桶(母桶)上，除了最高位保持為值1之外，所述現有桶具有包括與新桶索引中相同的值(即，比特集)的索引。例如，如果一個桶的索引為二進位表示的00101101，則母桶的相應索引為00Q01101。也就是說，母桶的索引可以如下獲得
權利要求
1.一種方法，包括為同時被多個線程所共享的雜湊表分配第二數量的桶，所述雜湊表具有第一數量的桶，桶的第二數量至少等於桶的第一數量並且第二數量的桶中的每一個被邏輯映射到第一或第二數量的桶中對應的一個母桶；並且公布包括第一和第二數量的桶的雜湊表的更新容量，其中所述分配通過公布所述更新容量而完成而不對所述第一數量的桶的內容執行任何重雜湊。
2.如權利要求1所述的方法，進一步包括執行檢查而並不閉鎖桶以確定是否需要重雜湊。
3.如權利要求1所述的方法，進一步包括隨後在對存在於第一數量的桶的第一桶中的數據對執行查找操作時，將該第一桶的內容重雜湊到第二數量的桶的第二桶。
4.如權利要求1所述的方法，進一步包括使用所述更新容量計算桶索引，使用所述桶索引訪問桶，確定該桶沒有被重雜湊，並且使用所述更新容量遞歸地計算母桶的母桶索引， 直至找到該桶被邏輯映射到的、被重雜湊的根桶。
5.如權利要求4所述的方法，進一步包括在搜索查找請求的數據對時或之前將被重雜湊的根桶的內容的至少一部分重雜湊到所述桶中。
6.如權利要求5所述的方法，進一步包括在根桶僅有一部分內容被重雜湊時對部分重雜湊指示符進行置位。
7.如權利要求4所述的方法，進一步包括在桶中搜索查找請求的數據對並返回該數據對，並且不對桶的內容進行重雜湊。
8.如權利要求1所述的方法，進一步包括響應於由第一線程進行的查找操作，在所述第一數量的桶的第一桶中沒有找到所請求的數據對，將雜湊表容量的當前值與在針對該查找操作確定桶索引時所使用的雜湊表容量的值相比較，並且如果當前值和該值不同，則計算最接近的繼承桶的索引，訪問最接近的繼承桶並且確定該最接近的繼承桶的重雜湊狀態。
9.如權利要求8所述的方法，進一步包括如果重雜湊狀態沒有指示新的(未重雜湊)狀態則重新開始查找操作。
10.如權利要求1所述的方法，進一步包括將多次分配組合為針對第二數量的桶的單次分配。
11.如權利要求1所述的方法，進一步包括公布多次分配並且一次性公布針對該多次分配的更新容量。
12.一種包括機器可讀存儲介質的物品，所述機器可讀存儲介質包括指令，所述指令在被機器執行的情況下使得該機器能夠執行一種方法，所述方法包括對同時被多個線程所共享的雜湊表執行查找操作，包括使用該雜湊表的第一容量值計算該雜湊表的第一桶的桶索引，使用所述桶索引訪問所述第一桶，並且確定所述第一桶不包括所述查找操作的數據對；將所述雜湊表容量的當前容量值與第一容量值進行比較，並且如果當前容量值和第一值不同，則使用當前容量值計算更新的桶索引；並且如果更新的桶索引和所述桶索引不同，則計算下一個桶索引，訪問對應於所述更新的桶索引的下一個桶，並且確定該下一個桶的重雜湊狀態。
13.如權利要求12所述的物品，其中所述方法進一步包括如果重雜湊狀態沒有指示新的狀態則重新開始查找操作。
14.如權利要求12所述的物品，其中所述方法進一步包括在查找操作期間訪問雜湊表的桶的同時對該桶進行重雜湊。
15.如權利要求12所述的物品，其中所述查找操作由第一線程執行，並且所述雜湊表在第一線程獲得用於計算的第一容量值並且第三線程在第一線程訪問第一桶之前開始對第一桶進行重雜湊之後由第二線程進行擴展。
16.一種系統，包括微處理器，其包括均執行一個或多個線程的第一核心和第二核心，其中第一線程用於向同時被多個線程所共享的雜湊表分配第二數量的桶，所述雜湊表之前具有第一數量的桶，所述桶的第二數量至少等於桶的第一數量，其中第二數量的桶中的每一個被邏輯映射到第一數量的桶中對應的一個母桶或第二數量的桶中對應的一個母桶；並且公布包括第一和第二數量的桶的雜湊表的更新容量，其中第一線程用於通過公布所述更新容量而完成所述分配而不對所述第一數量的桶的內容執行任何重雜湊，並且第二線程用於對第一數量的桶的第一桶執行查找操作而不檢查閉鎖變量以確定是否需要重雜湊；和共享存儲器，其耦合到所述微處理器以存儲所述雜湊表，所述雜湊表要被所述多個線程中的至少一些同時訪問。
17.如權利要求16所述的系統，其中第三線程用於在針對所述第一桶中所存在的數據對執行查找操作時將第一數量的桶的第一桶的內容重雜湊到第二數量的桶的第二桶中。
18.如權利要求16所述的系統，其中第二線程用於使用更新容量計算第二數量的桶中的桶的桶索引，使用所述桶索引訪問該桶，確定該桶沒有被重雜湊，並且遞歸地計算所述桶被邏輯映射到的母桶的母桶索引，直至找到被重雜湊的根桶。
19.如權利要求18所述的系統，其中所述第二線程用於在搜索查找請求的數據對時或之前將被重雜湊的根桶的內容的至少一部分重雜湊到所述桶中。
20.如權利要求19所述的系統，其中所述第二線程用於在根桶僅有一部分內容被重雜湊時對根桶的部分重雜湊指示符進行置位。
全文摘要
在一個實施例中，本發明包括一種用於為同時被多個線程所共享的雜湊表分配第二數量的桶的方法，其中所述第二數量的桶被邏輯映射到第一數量的桶中對應的一個母桶，並且公布雜湊表的更新容量以完成所述分配，而並不執行任何重雜湊，以使得該重雜湊能夠在稍後根據需要以每個桶為基礎來執行。描述並要求保護了其它的實施例。
文檔編號G06F9/46GK102460392SQ200980159762
公開日2012年5月16日 申請日期2009年4月8日 優先權日2009年4月8日
發明者A. 馬拉霍夫 A. 申請人:英特爾公司