[發(fā)明專利]一種基于GPU流的快速并行字符串匹配方法和系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 202110222110.2
• 申請(qǐng)日: 2021-02-28
• 公開（公告）號(hào): CN112883245B
• 公開（公告）日: 2022-05-10
• 發(fā)明（設(shè)計(jì)）人: 陳海軍;唐卓;曹嶸暉;劉妮;葉暉
• 申請(qǐng)（專利權(quán)）人: 湖南工商大學(xué)
• 主分類號(hào): G06F16/903
• 分類號(hào): G06F16/903;G06F16/245
• 代理公司: 武漢臻誠專利代理事務(wù)所(普通合伙) 42233
• 代理人: 宋業(yè)斌

本發(fā)明公開了一種基于GPU流的快速并行字符串匹配方法，其通過優(yōu)化后的基于GPU流的并行字符串匹配加速，實(shí)現(xiàn)內(nèi)核級(jí)的任務(wù)并行。本發(fā)明首先將大數(shù)據(jù)任務(wù)分割成沒有依賴關(guān)系的小數(shù)據(jù)任務(wù)，然后將小數(shù)據(jù)任務(wù)調(diào)度到每個(gè)GPU設(shè)備上運(yùn)行。字符串?dāng)?shù)據(jù)集存儲(chǔ)在低速的全局內(nèi)存中，模式串具有較高的訪問頻率，存放在高速的共享內(nèi)存中。通過根據(jù)應(yīng)用需求和資源狀態(tài)啟動(dòng)合適的CUDA流數(shù)量，使得所有的任務(wù)能夠異步并發(fā)執(zhí)行。本發(fā)明能夠解決現(xiàn)有BF算法由于采用全部遍歷字符的暴力檢索導(dǎo)致計(jì)算過程存在許多無意義的匹配計(jì)算的技術(shù)問題，以及現(xiàn)有BK算法計(jì)算過程的時(shí)間復(fù)雜度高的技術(shù)問題，以及現(xiàn)有KMP算法移動(dòng)策略不佳、速度較慢的技術(shù)問題。

技術(shù)領(lǐng)域

本發(fā)明屬于互聯(lián)網(wǎng)技術(shù)領(lǐng)域，更具體地，涉及一種基于GPU流的快速并行字符串匹配方法和系統(tǒng)。

背景技術(shù)

作為眾多科學(xué)計(jì)算領(lǐng)域的基礎(chǔ)，字符串匹配問題目前得到了廣泛和深入的研究。字符串匹配在入侵檢測、分子生物學(xué)、信息過濾、病毒檢測、拼寫檢查、語言翻譯、數(shù)字壓縮、搜索引擎等諸多問題中得到廣泛應(yīng)用。

現(xiàn)有的字符串匹配算法主要包括：暴力檢索(Brute Force，簡稱BF)算法、哈希檢索(Robin-Karp，簡稱RK)算法、Knuth-Morria-Pratt(簡稱KMP)算法、Boyer Moore(簡稱BM)算法；其中，BF算法主要是通過暴力檢索所有的字符匹配結(jié)果，直到匹配成功或匹配結(jié)束；RK算法是對(duì)BF算法的改進(jìn)，其主要通過首先通過對(duì)比子串的hash值篩選子串，然后再對(duì)子串執(zhí)行BF算法；KMP算法相比BF算法有比較大的改進(jìn)，主要是通過消除主串指針的回溯提高算法效率；BM算法主要通過壞字符和好后綴規(guī)則加速字符移動(dòng)效率，相比KMP速度快3-5倍。

然而，上述現(xiàn)有的字符串匹配方法，均存在一些不可忽略的缺陷：第一、上述BF算法采用全部遍歷字符的暴力檢索，計(jì)算過程存在許多無意義的匹配計(jì)算；第二、上述BK算法首先遍歷所有可能匹配的子串的hash值，且大數(shù)據(jù)集計(jì)算的時(shí)間復(fù)雜度高；第三、上述KMP算法使用移位策略加速模式串的移動(dòng)，但移動(dòng)策略不是最優(yōu)，速度較慢；第四、上述BM算法無法面向大數(shù)據(jù)集實(shí)現(xiàn)數(shù)據(jù)劃分和基于GPU高并發(fā)設(shè)備的并行計(jì)算。

發(fā)明內(nèi)容

針對(duì)現(xiàn)有技術(shù)的以上缺陷或改進(jìn)需求，本發(fā)明提供了一種基于GPU流的快速并行字符串匹配方法和系統(tǒng)。其目的在于，解決現(xiàn)有BF算法由于采用全部遍歷字符的暴力檢索導(dǎo)致計(jì)算過程存在許多無意義的匹配計(jì)算的技術(shù)問題，以及現(xiàn)有BK算法計(jì)算過程的時(shí)間復(fù)雜度高的技術(shù)問題，以及現(xiàn)有KMP算法移動(dòng)策略不佳、速度較慢的技術(shù)問題，以及現(xiàn)有BM算法無法面向大數(shù)據(jù)集實(shí)現(xiàn)數(shù)據(jù)劃分和基于GPU高并發(fā)設(shè)備的并行計(jì)算的技術(shù)問題。

為實(shí)現(xiàn)上述目的，按照本發(fā)明的一個(gè)方面，提供了一種基于GPU流的快速并行字符串匹配方法，是應(yīng)用在包括一個(gè)主節(jié)點(diǎn)和多個(gè)從節(jié)點(diǎn)的分布式計(jì)算系統(tǒng)中，所述方法包括以下步驟：

(1)主節(jié)點(diǎn)接收用戶提交的應(yīng)用程序，對(duì)該應(yīng)用程序進(jìn)行解析，以得到DAG圖；

(2)主節(jié)點(diǎn)對(duì)步驟(1)中DAG圖中任務(wù)所對(duì)應(yīng)的數(shù)據(jù)進(jìn)行分割處理，以得到分割后的多個(gè)數(shù)據(jù)塊；

(3)主節(jié)點(diǎn)將步驟(2)得到的分割后的數(shù)據(jù)塊發(fā)送到從節(jié)點(diǎn)。

(4)從節(jié)點(diǎn)判斷每個(gè)數(shù)據(jù)塊中是否存在多個(gè)分割點(diǎn)。如果是則轉(zhuǎn)入步驟(5)，否則轉(zhuǎn)入步驟(6)；

(5)從節(jié)點(diǎn)按照分割點(diǎn)對(duì)步驟(2)得到的每個(gè)數(shù)據(jù)塊進(jìn)行分割，以得到多個(gè)分割后的數(shù)據(jù)塊，并創(chuàng)建k個(gè)GPU執(zhí)行流，并將分割后的數(shù)據(jù)塊平均分配給k個(gè)GPU執(zhí)行流進(jìn)行處理，以得到k個(gè)并行執(zhí)行的任務(wù)執(zhí)行流，其中k為小于等于64的整數(shù)；

(6)從節(jié)點(diǎn)對(duì)步驟(2)得到的每個(gè)數(shù)據(jù)塊按照前55％和后55％兩部分進(jìn)行分割，以得到獨(dú)立的兩個(gè)數(shù)據(jù)塊，并將分割后的兩個(gè)數(shù)據(jù)塊分配給兩個(gè)GPU執(zhí)行流處理，以得到2個(gè)并行執(zhí)行的任務(wù)執(zhí)行流；