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

有效

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

1.一種基于OpenCL的紅黑樹加速算法，其實現(xiàn)的具體步驟如下：

步驟1：CPU數(shù)據(jù)輸入，GPU設(shè)備初始化：尋找支持OpenCL的硬件設(shè)備、創(chuàng)建程序執(zhí)行所需的內(nèi)存對象、根據(jù)設(shè)備支持核心數(shù)分配線程等操作；

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

步驟3：將分塊數(shù)據(jù)分配給每個線程，并進行如下操作：

1)??????將待插入的數(shù)據(jù)值直接插入樹尾；

2)??????將表示此數(shù)據(jù)的節(jié)點顏色屬性標記為紅色；

3)??????調(diào)整樹的顏色性質(zhì)，分為以下三種情況：

a)??????若當前節(jié)點的“叔父”節(jié)點是紅色：在這種情況下，將父、叔節(jié)點都標記為黑色，再將子樹根節(jié)點著為紅色，那么子樹的黑高度沒有發(fā)生改變，而且紅黑性質(zhì)得得到了調(diào)整；此時，再將當前節(jié)點指向子樹的根節(jié)點，向上遞歸恢復紅黑特性，如圖二所示；其中結(jié)點E直系上層結(jié)點C為其父節(jié)點，與結(jié)點C父節(jié)點同一層節(jié)點A，B，D均為其叔父節(jié)點；

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

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

4)??????對調(diào)整完畢后的紅黑樹進行數(shù)據(jù)查找操作：從樹的根節(jié)點開始進行查找，如果待查找數(shù)據(jù)小于當前節(jié)點，則向左子樹繼續(xù)進行查找；如果待查找數(shù)據(jù)大于當前節(jié)點，則向右子樹繼續(xù)進行查找；否則查找完成；如果在達到葉子節(jié)點（葉子節(jié)點即為樹中最底層的節(jié)點，不存在子節(jié)點，圖2中與節(jié)點E同層的節(jié)點均為葉子節(jié)點）時仍未返回結(jié)果，則認為此次查找失敗；

步驟4：合并子樹：在線程為每個子樹完成顏色調(diào)整之后，將GPU計算結(jié)果傳回CPU內(nèi)存單元，然后在cpu端進行樹的合并，在合并的過程中，合并樹需要滿足以下性質(zhì)：a,根節(jié)點為黑色；b，每個葉節(jié)點（NIL節(jié)點，空節(jié)點）均為黑色；c，每個紅色節(jié)點的兩個子節(jié)點（某節(jié)點向下映射出的節(jié)點為該節(jié)點的子節(jié)點,如圖2中節(jié)點E為節(jié)點C的子節(jié)點）都為黑色；d，從任一節(jié)點到其每個葉節(jié)點的所有路徑都包含相同數(shù)目的黑色節(jié)點；

步驟5：將分類合并后所建成的紅黑樹輸出和存儲。