[發明專利]一種基于OpenCL的紅黑樹加速方法

有效

• 申請號: 201410266098.5
• 申請日: 2014-06-16
• 公開（公告）號: CN104036141B
• 公開（公告）日: 2017-02-15
• 發明（設計）人: 余小清;熊瑋;萬旺根;楊超;丁玉樸;段石石
• 申請（專利權）人: 上海大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海上大專利事務所(普通合伙)31205
• 代理人: 何文欣

技術領域

本發明涉及基于GPU的并行計算領域，具體涉及一種基于OpenCL的紅黑樹加速算法。?

背景技術

紅黑樹是一種自平衡二叉查找樹，典型的用途是實現關聯數組，也可用于大數據的檢索。它是復雜的，但它的操作有著良好的最壞情況運行時間，并且在實踐中是高效的：它可以在O(log?n)時間內做查找，插入和刪除，這里的n是樹中元素的數目。紅黑樹是每個節點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。它的統計性能要好于平衡二叉樹，因此，紅黑樹在很多地方都有應用。在C++?STL中，很多部分(目前包括set,?multiset,?map,?multimap)應用了紅黑樹的變體。?

本發明采用的是基于OpenCL的紅黑樹加速算法，OpenCL是一種為異構平臺編寫程序的框架，此異構平臺可由CPU，GPU或其他類型的處理器組成。OpenCL提供若干用于定義和控制平臺的接口函數組成，能夠有效地利用多種設備的并行計算能力來進行算法的加速。?

對于大數據檢索中的應用，關建是需要先運算出其紅黑樹模型，而以往的方法需要耗費大量的運算時間，本發明就是利用OpenCL的異構平臺框架，解決建立紅黑樹耗時的問題而提出的。?

發明內容

本發明的目的是提供了一種基于OpenCL的紅黑樹加速方法，利用建立紅黑樹過成中眾多運算可以并行化處理的特點，運用OpenCL異構平臺，實現了在大數據的情況下快速建立紅黑樹模型。?

為達到上述目的，本發明的構思是：在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:?

性質1.?節點是紅色或黑色。

性質2.?根節點是黑色。?

性質3.?每個葉節點（NIL節點，空節點）是黑色的。?

性質4.?每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)?

性質5.?從任一節點到其每個葉節點的所有路徑都包含相同數目的黑色節點。

這些約束強制了紅黑樹的關鍵性質:?從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。?

根據上述構思，本發明采用的技術方案為：將準備操作的數據分為多個數據塊，利用GPU多個核心同時進行數據插入操作。在同步完成各個GPU的運算后，最后做紅黑樹的合并操作，完成整個紅黑樹建立過程。其總的發明方法示意圖如圖2所示。?

本發明解決其技術問題采用的技術方案還可以進一步完善。其具體的實現步驟如圖1所示，可分為4步實現：?

步驟1：CPU數據輸入，GPU設備初始化：尋找支持OpenCL的硬件設備、創建程序執行所需的內存對象、根據設備支持核心數分配線程等操作。

步驟2：數據分塊：根據GPU上分配好的線程將原有海量數據進行分塊，如硬件支持線程數目為n，數據量為m，則每個線程單獨分配數據量為m/n。?

步驟3：將分塊數據分配給每個線程，并進行如下操作：?

1)??????將待插入的數據值直接插入樹尾。

2)??????將表示此數據的節點顏色屬性標記為紅色。?

3)??????調整樹的顏色性質，分為以下三種情況：?

a)??????若當前節點的“叔父”節點是紅色：在這種情況下，將父、叔節點都標記為黑色，再將子樹根節點著為紅色，那么子樹的黑高度沒有發生改變，而且紅黑性質得得到了調整。此時，再將當前節點指向子樹的根節點，向上遞歸恢復紅黑特性，如圖二所示。

其中結點E直系上層結點C為其父節點，與結點C父節點同一層節點A，B，D均為其叔父節點。?

b)??????若當前節點的“叔父”節點是黑色的，當前節點是父節點的左子節點：則將當前節點的父節點與祖節點（即當前節點的父節點的父節點）進行一次右旋，并把父節點著黑色，原來的祖節點著紅色。這些子樹的紅黑特性得到了恢復，而且子樹的黑高度沒有變化。另外，由于子樹根節點已經是黑色了（這個節點不會出現父子同為紅色的問題了），所以不必再向上遞歸了，此時整個樹的紅黑特性都已經是正確的了。?

c)??????若當前節點的“叔父”節點是黑色的，當前節點是父節點的右子節點：則將當前節點本身與其父節點進行一次左旋，讓當前節點指向原來的父節點，就可以到上面情況b)，再根據情況b)的解決方式進行操作。?