[發明專利]基于CPU-GPU架構的彩虹鏈表的處理方法及系統

在審

• 申請號: 201710972354.6
• 申請日: 2017-10-18
• 公開（公告）號: CN108038382A
• 公開（公告）日: 2018-05-15
• 發明（設計）人: 姜海;王忠儒;李海磊
• 申請（專利權）人: 北京丁牛科技有限公司
• 主分類號: G06F21/60
• 分類號: G06F21/60;G06F21/62;H04L9/32
• 代理公司: 北京林達劉知識產權代理事務所(普通合伙) 11277
• 代理人: 劉新宇

1.一種基于CPU-GPU架構的彩虹鏈表的生成方法，其特征在于，包括：

多個GPU從CPU接收彩虹鏈表的各鏈首；

各GPU根據收到的鏈首生成對應的鏈尾；

各GPU將各鏈尾及其對應的鏈首組成彩虹鏈；

各GPU將各彩虹鏈發送至CPU。

2.根據權利要求1所述的方法，其特征在于，各GPU根據收到的鏈首生成對應的鏈尾，包括：

各GPU根據收到的鏈首、預設的哈希函數和循環規約函數生成對應的鏈尾。

3.根據權利要求1或2所述的方法，其特征在于，還包括：CPU對各所述彩虹鏈進行去重處理，具體包括：

在兩條彩虹鏈的鏈尾相同的情況下，CPU根據所述兩條彩虹鏈的鏈首、預設的哈希函數和循環規約函數分別計算得到對應的兩條彩虹鏈的各個節點；

如果所述兩條彩虹鏈中具有相同的節點，則保留兩條彩虹鏈中不同節點數量較多的一條。

4.根據權利要求1或2所述的方法，其特征在于，還包括：CPU對各所述彩虹鏈進行分類存儲，具體包括：

根據ASCII可顯示字符生成具有多級目錄的文件存儲結構，其中，所述多級目錄是根據隨機獲取的三個ASCII可顯示字符的值來生成的；

根據所述彩虹鏈的鏈尾的前三位字符的ASCII值查找文件存儲結構中對應的文件，其中，所述彩虹鏈的鏈尾在前鏈首在后；

將所述彩虹鏈的第一剩余字符存儲在查找到的對應的文件中，所述第一剩余字符為所述彩虹鏈去除了前三位字符之后的字符。

5.一種基于CPU-GPU架構的彩虹鏈表的查找方法，其特征在于，還包括：

多個GPU從CPU獲取多個哈希值；

GPU根據多個哈希值，計算得到各哈希值對應的所有的待查鏈尾；

GPU按照每次計算過程中所用的哈希函數和規約函數，對各待查鏈尾進行分類存儲；

GPU將分類存儲后的文件發送到CPU，由CPU將收到的各文件存儲到存儲空間；

CPU根據收到的文件在預存的文件存儲結構中，查找各待查鏈尾對應的鏈首，再根據查找到的鏈首、所用的哈希函數和規約函數計算各哈希值對應的明文。

6.根據權利要求5所述的方法，其特征在于，還包括：CPU根據收到的文件在預存的文件存儲結構中，查找各待查鏈尾對應的鏈首，具體包括：

CPU根據各待查鏈尾中前三位字符的ASCII值在預存的文件存儲結構中查找對應的文件；

CPU按照所述待查鏈尾的第二剩余字符，在查找到的對應的文件中，查找匹配的彩虹鏈，所述第二剩余字符為所述待查鏈尾去除了前三位字符之后的字符；

CPU根據匹配的彩虹鏈確定對應的鏈首。

7.一種基于CPU-GPU架構的彩虹鏈表的生成系統，其特征在于，包括：

CPU，用于向多個GPU發送彩虹鏈表的各鏈首；

多個GPU，每個GPU用于根據從CPU收到的鏈首生成對應的鏈尾，將各鏈尾及其對應的鏈首組成彩虹鏈，并將各彩虹鏈發送至CPU。

8.根據權利要求7所述的系統，其特征在于，所述GPU還用于根據收到的鏈首、預設的哈希函數和循環規約函數生成對應的鏈尾。

9.根據權利要求7或8所述的系統，其特征在于，所述CPU還用于對各所述彩虹鏈進行去重處理，具體用于：

在兩條彩虹鏈的鏈尾相同的情況下，根據所述兩條彩虹鏈的鏈首、預設的哈希函數和循環規約函數分別計算得到對應的兩條彩虹鏈的各個節點；

如果所述兩條彩虹鏈中具有相同的節點，則保留兩條彩虹鏈中不同節點數量較多的一條。