[發(fā)明專利]一種基于GPU-CUDA平臺(tái)以及遺傳算法的數(shù)據(jù)流并行處理方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201310229098.3
• 申請(qǐng)日: 2013-06-09
• 公開（公告）號(hào): CN103279332A
• 公開（公告）日: 2013-09-04
• 發(fā)明（設(shè)計(jì)）人: 盧曉偉;周勇;韓君;張清
• 申請(qǐng)（專利權(quán)）人: 浪潮電子信息產(chǎn)業(yè)股份有限公司
• 主分類號(hào): G06F9/38
• 分類號(hào): G06F9/38;G06N3/12
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

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

本發(fā)明涉及計(jì)算機(jī)應(yīng)用領(lǐng)域,具體地說(shuō)是一種基于GPU-CUDA平臺(tái)以及遺傳算法的數(shù)據(jù)流并行處理方法。

背景技術(shù)

數(shù)據(jù)流實(shí)際上就是連續(xù)移動(dòng)的元素隊(duì)伍，其中的元素是由相關(guān)數(shù)據(jù)的集合組成。令t表示任一時(shí)間戳，at表示在該時(shí)間戳到達(dá)的數(shù)據(jù)，流數(shù)據(jù)可以表示成{…，at?1，at，at+1，…}.區(qū)別于傳統(tǒng)應(yīng)用模型，流數(shù)據(jù)模型具有以下4點(diǎn)共性:（1）數(shù)據(jù)實(shí)時(shí)到達(dá);（2）數(shù)據(jù)到達(dá)次序獨(dú)立，不受應(yīng)用系統(tǒng)所控制;（3）數(shù)據(jù)規(guī)模宏大且不能預(yù)知其最大值;（4）數(shù)據(jù)一經(jīng)處理，除非特意保存，否則不能被再次取出處理，或者再次提取數(shù)據(jù)代價(jià)昂貴。

滑動(dòng)窗口（sliding?window）模型：滑動(dòng)窗口對(duì)窗口起點(diǎn)和終點(diǎn)都沒(méi)有明確給定，只明確給定窗口的長(zhǎng)度W。窗口保持一定長(zhǎng)度在數(shù)據(jù)流D={?d₀,d₁?…,d_n?}上滑動(dòng)，處理的數(shù)據(jù)流范圍就由該窗口確定，隨著窗口的滑動(dòng)不斷地把得到的結(jié)果輸出。滑動(dòng)窗口SW的長(zhǎng)度既可由一個(gè)時(shí)間區(qū)間確定，也可由窗口所包含數(shù)據(jù)流元素個(gè)數(shù)確定；

嵌套子窗口模型：某時(shí)刻T?，窗口長(zhǎng)度為W的滑動(dòng)窗口SW內(nèi)最新數(shù)據(jù)集d_n落入到窗口大小為W2的嵌套子窗口S_SW中，稱窗口SW?為嵌套子窗口。

如圖1?所示，應(yīng)用滑動(dòng)窗口對(duì)動(dòng)態(tài)更新數(shù)據(jù)集進(jìn)行說(shuō)明。窗口數(shù)據(jù)集為圖1?(a)?中標(biāo)識(shí)所示。當(dāng)新增數(shù)據(jù)集到達(dá)時(shí)，滑動(dòng)窗口向前移動(dòng)一個(gè)單位，如圖1?(b)所示。

滑動(dòng)窗口的頻繁項(xiàng)集：對(duì)于當(dāng)前滑動(dòng)窗口內(nèi)數(shù)據(jù)，設(shè)I={i₁，i₂，…，i_n}是項(xiàng)的集合，事務(wù)數(shù)據(jù)集S={?s₀,s₁?…,s_n?}，其中，數(shù)據(jù)集中每個(gè)事務(wù)s?是項(xiàng)的集合，s?I。如果X?s，則稱X?是個(gè)項(xiàng)集。如果X?中有k?個(gè)元素，則稱X?為k-項(xiàng)集。對(duì)于一個(gè)項(xiàng)集X，如果其支持度大于等于用戶給定的最小支持度閾值，則X?為頻繁項(xiàng)集。

遺傳算法：一種基于隨機(jī)搜索的優(yōu)化算法，已成功應(yīng)用于函數(shù)優(yōu)化、自動(dòng)控制、生產(chǎn)調(diào)度、機(jī)器人學(xué)、圖像處理、人工生命、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域。從代表問(wèn)題可能潛在的解集的一個(gè)種群開始的，而一個(gè)種群則由經(jīng)過(guò)基因編碼的一定數(shù)目的個(gè)體組成。每個(gè)個(gè)體實(shí)際上是染色體帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個(gè)體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡(jiǎn)化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來(lái)越好的近似解，在每一代，根據(jù)問(wèn)題域中個(gè)體的適應(yīng)度大小選擇個(gè)體，并借助于自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異，產(chǎn)生出代表新的解集的種群。這個(gè)過(guò)程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過(guò)解碼，可以作為問(wèn)題近似最優(yōu)解。

遺傳算法的基本運(yùn)算過(guò)程如下，算法流程示意圖如圖2：?　　

a)初始化：設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器t=0，設(shè)置最大進(jìn)化代數(shù)T，隨機(jī)生成M個(gè)個(gè)體作為初始群體P₍₀₎。?　　

b)個(gè)體評(píng)價(jià)：計(jì)算群體P_(t)中各個(gè)個(gè)體的適應(yīng)度。?　　

c)選擇運(yùn)算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個(gè)體直接遺傳到下一代或通過(guò)配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)估基礎(chǔ)上的。?　　

d)交叉運(yùn)算：將交叉算子作用于群體。所謂交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。遺傳算法中起核心作用的就是交叉算子。?　　

e)變異運(yùn)算：將變異算子作用于群體。即是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)。群體P_(t)經(jīng)過(guò)選擇、交叉、變異運(yùn)算之后得到下一代群體P_(t?1)。?　　

f)終止條件判斷:若t=T,則以進(jìn)化過(guò)程中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出，終止計(jì)算。

CUDA是一種并行編程模型和軟件環(huán)境，?采用C?語(yǔ)言等標(biāo)準(zhǔn)編程語(yǔ)言進(jìn)行操作。該技術(shù)封裝了GPU的硬件細(xì)節(jié)，CUDA?的核心有三個(gè)重要抽象概念：線程組層次結(jié)構(gòu)、共享存儲(chǔ)器、屏蔽同步（barrier?synchronization）。