云環(huán)境下多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)索引

陶建平，曹 霞

(華中科技大學(xué)網(wǎng)絡(luò)與計(jì)算中心，湖北武漢430074)

1 引言

多核處理器也屬于片上多處理器，也被稱為單芯片多處理器，多核結(jié)構(gòu)思想與原型出自于1996年美國(guó)斯坦福大學(xué)，首個(gè)商用多核處理器源于2001年IBM，目前在云環(huán)境下，多核處理器的使用十分常見，其使用范圍觸及到多媒體運(yùn)算、嵌入式設(shè)備、個(gè)人計(jì)算機(jī)、高性能計(jì)算機(jī)、仿真平臺(tái)等多個(gè)領(lǐng)域[1]。多個(gè)處理器可把多個(gè)完全功能的核心集成在一個(gè)芯片之中，在云環(huán)境中仿真平臺(tái)中引入多核處理器后，實(shí)驗(yàn)平臺(tái)的運(yùn)行速度將大大提升，且應(yīng)用成本較小，可讓仿真平臺(tái)服務(wù)器并行處理任務(wù)。但云環(huán)境中多核仿真平臺(tái)中，多核處理器在執(zhí)行虛擬任務(wù)時(shí)，虛擬任務(wù)數(shù)據(jù)的數(shù)據(jù)量具有爆炸式、海量式[2]。高效率管理虛擬任務(wù)數(shù)據(jù)的必備條件即為虛擬任務(wù)數(shù)據(jù)索引設(shè)計(jì)，一個(gè)合適的索引方法，可對(duì)虛擬任務(wù)數(shù)據(jù)實(shí)施合理的組織與管理，為云端用戶提供便捷的操作服務(wù)，數(shù)據(jù)索引的使用可讓云環(huán)境下多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)管理時(shí)，不必遍歷全部數(shù)據(jù)節(jié)點(diǎn)，優(yōu)化了平臺(tái)虛擬任務(wù)數(shù)據(jù)的管理效果。在研究關(guān)于數(shù)據(jù)索引設(shè)計(jì)問題之時(shí)，對(duì)文獻(xiàn)[3]、文獻(xiàn)[4]兩個(gè)文獻(xiàn)進(jìn)行了深入研究，其分別提出了面向DEM構(gòu)建的點(diǎn)云四叉樹和R樹混合索引方法、基于HBase的多維索引查詢機(jī)制的優(yōu)化方法，這兩種方法應(yīng)用后，可提升數(shù)據(jù)管理效率，本文也以優(yōu)化數(shù)據(jù)管理效率為目標(biāo)，提出云環(huán)境下多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)索引設(shè)計(jì)方法，以期為云環(huán)境下多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)管理問題提供可參考資料。

2 多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)索引

2.1 基于分形維數(shù)的選擇性聚類融合算法

基于分形維數(shù)的選擇性聚類融合算法核心思想是：使用改進(jìn)的基于分形維數(shù)的聚類算法確定聚類成員，使用基于互信息的選擇策略，選取部分聚類成員進(jìn)行融合后采用基于加權(quán)共協(xié)矩陣的單鏈接算法，完成部分聚類成員的融合，以此獲取多核仿真平臺(tái)中，各類虛擬任務(wù)數(shù)據(jù)的聚類結(jié)果[5]。

算法的應(yīng)用流程是：

1)將云環(huán)境下多核仿真平臺(tái)各類虛擬任務(wù)數(shù)據(jù)集F實(shí)施循環(huán)隨機(jī)抽樣，獲取多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)子集{Yj}，然后對(duì)各個(gè)子集Yj通過k-means聚類建立k個(gè)簇，記載k個(gè)聚類中心，再通過k個(gè)聚類中心將數(shù)據(jù)集F里的數(shù)據(jù)實(shí)施重新分配，得到整個(gè)數(shù)據(jù)集中初始聚類集αj，將數(shù)據(jù)集F實(shí)施M次聚類，獲取存在M次聚類結(jié)果的集合α={α1，α2，…，αM}。

2)此步驟是把沒有聚類的多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)點(diǎn)導(dǎo)進(jìn)已經(jīng)聚類的簇集里，完成整個(gè)數(shù)據(jù)集聚類[6-8]。先運(yùn)算初始聚類里各個(gè)簇的分形維數(shù)Fj，把沒有分配的數(shù)據(jù)點(diǎn)依次導(dǎo)進(jìn)各個(gè)簇里，之后運(yùn)算加入數(shù)據(jù)點(diǎn)后的分形維數(shù)F′j，運(yùn)算分形影響度oj=|Fj-F′j|，在其中獲取最小分形影響度oj相應(yīng)的簇Bj，設(shè)置閾值β，如果oj不大于閾值β，把此數(shù)據(jù)點(diǎn)導(dǎo)進(jìn)Bj里，反之，此數(shù)據(jù)點(diǎn)是離群點(diǎn)。

(1)

其中，o-10，j、o2，j、o10，j依次是數(shù)據(jù)點(diǎn)在不同簇中的分形影響度。

4)如果某個(gè)聚類成員的權(quán)值?j小于權(quán)重閾值ε，那么此聚類成員可刪除；反之便可加入對(duì)應(yīng)的簇中。

5)運(yùn)算加權(quán)共協(xié)矩陣設(shè)置，設(shè)置相似度閾值是r，數(shù)據(jù)點(diǎn)對(duì)加權(quán)共協(xié)矩陣Da(i，j)大于相似度閾值r，那么這兩個(gè)數(shù)據(jù)點(diǎn)屬于一簇，如果兩個(gè)數(shù)據(jù)點(diǎn)的簇存在差異，便對(duì)其合并；如果數(shù)據(jù)點(diǎn)對(duì)的加權(quán)共協(xié)矩陣Da(i，j)不大于相似度閾值r，代表兩個(gè)數(shù)據(jù)點(diǎn)不可以劃成一簇，孤立的數(shù)據(jù)點(diǎn)將獨(dú)自一簇。對(duì)比全部數(shù)據(jù)點(diǎn)和閾值的關(guān)系，得到最后的聚類結(jié)果。

2.2 云環(huán)境下多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)索引機(jī)制構(gòu)建方法

先設(shè)計(jì)多核仿真平臺(tái)虛擬任務(wù)各類型數(shù)據(jù)聚類中心的覆蓋網(wǎng)絡(luò)拓?fù)?，再使用前綴二叉樹PBT與金字塔技術(shù)建立數(shù)據(jù)索引。

2.2.1 覆蓋網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)

覆蓋網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)見圖1。

圖1 覆蓋網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

把虛擬任務(wù)各類型數(shù)據(jù)節(jié)點(diǎn)Mj在邏輯功能中看做兩種節(jié)點(diǎn)：存儲(chǔ)節(jié)點(diǎn)RMj、索引節(jié)點(diǎn)LMj，存儲(chǔ)節(jié)點(diǎn)RMj可保存分配至節(jié)點(diǎn)Mj的虛擬任務(wù)數(shù)據(jù)，索引節(jié)點(diǎn)LMj可管理存儲(chǔ)節(jié)點(diǎn)RMj中各類型數(shù)據(jù)的元數(shù)據(jù)信息。云環(huán)境下，多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)中心使用Chord協(xié)議把索引節(jié)點(diǎn)LMj構(gòu)建成環(huán)狀覆蓋網(wǎng)絡(luò)，且在各個(gè)索引節(jié)點(diǎn)LMj中建立多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)索引(簡(jiǎn)稱多維數(shù)據(jù)索引M-Index)、仿真平臺(tái)本地?cái)?shù)據(jù)索引L-Index。多維數(shù)據(jù)索引屬于全局索引，可把虛擬任務(wù)各類型數(shù)據(jù)信息索引為主鍵，然后按照一致性機(jī)制把數(shù)據(jù)均勻的引入每個(gè)存儲(chǔ)節(jié)點(diǎn)中[9]。本地?cái)?shù)據(jù)索引屬于數(shù)據(jù)在節(jié)點(diǎn)Mj內(nèi)部的本地索引，可在索引節(jié)點(diǎn)LMj中建立索引結(jié)構(gòu)，以此管理保存在存儲(chǔ)節(jié)點(diǎn)RMj中的數(shù)據(jù)。因?yàn)楫?dāng)下關(guān)于本地?cái)?shù)據(jù)索引方面的研究較多，所以本文以多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)索引為研究核心。在所構(gòu)建拓?fù)淅?，多維數(shù)據(jù)索引只需維護(hù)數(shù)據(jù)在覆蓋網(wǎng)絡(luò)里轉(zhuǎn)發(fā)的路由信息，但與元數(shù)據(jù)信息存在關(guān)聯(lián)的數(shù)據(jù)需要轉(zhuǎn)交至本地?cái)?shù)據(jù)索引管理，此方法可提升多核仿真平臺(tái)的存儲(chǔ)空間[10，11]。

在覆蓋網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)里，虛擬任務(wù)數(shù)據(jù)的傳輸步驟是：多核仿真平臺(tái)先通過多維數(shù)據(jù)索引把虛擬任務(wù)數(shù)據(jù)的多維數(shù)據(jù)變換為一維主鍵，然后按照一維主鍵判斷虛擬任務(wù)數(shù)據(jù)在覆蓋網(wǎng)絡(luò)拓?fù)淅锏乃谖恢谩?/p>

2.2.2 索引機(jī)制

云端用戶上傳的數(shù)據(jù)在多核仿真平臺(tái)里存在多維元數(shù)據(jù)的特征，本文把數(shù)據(jù)統(tǒng)一抽象為一組二元鍵值對(duì)E，詳情是

E=〈bi，ui〉

(2)

其中，bi、ui依次是各類虛擬任務(wù)數(shù)據(jù)屬性類型、屬性值。

在一致性處理時(shí)，各類虛擬任務(wù)數(shù)據(jù)的主鍵僅存在一維元數(shù)據(jù)，此時(shí)多核仿真平臺(tái)便不支持多維虛擬任務(wù)數(shù)據(jù)查詢。本文處理的方法是使用金字塔技術(shù)建立多維數(shù)據(jù)索引，把描述元數(shù)據(jù)的e維向量N變成一維索引jeu。多維數(shù)據(jù)索引在降維時(shí)，可保證各類虛擬任務(wù)數(shù)據(jù)查詢結(jié)果不存在缺失情況。

多維數(shù)據(jù)索引把e維向量N設(shè)成e維空間中的數(shù)據(jù)點(diǎn)U，把e維向量降維后所獲取的一維索引設(shè)成數(shù)據(jù)點(diǎn)U和點(diǎn)Q的距離。因?yàn)樵诮稻S時(shí)或許會(huì)存在多個(gè)數(shù)據(jù)點(diǎn)和中心點(diǎn)一維距離一致的狀態(tài)。此狀態(tài)影響下，各類虛擬任務(wù)數(shù)據(jù)后續(xù)應(yīng)用中會(huì)存在不良結(jié)果，所以，多維數(shù)據(jù)索引在不一樣的金字塔中使用不一樣的距離函數(shù)[12]。詳細(xì)流程如規(guī)則1：

規(guī)則1：多維數(shù)據(jù)索引把多維數(shù)據(jù)N降維成一維索引jeu的步驟是：

1)歸一化

(3)

2)判斷數(shù)據(jù)點(diǎn)U所在的金字塔編碼

因?yàn)槎嗑S數(shù)據(jù)索引在具有差異的金字塔中距離函數(shù)也存在差異，所以在運(yùn)算一維距離之前必須先判斷數(shù)據(jù)點(diǎn)U所在的金字塔編碼j

(4)

式中，imax是數(shù)據(jù)點(diǎn)U坐標(biāo)差值中最顯著的一維向量；e是維度數(shù)值。

3)運(yùn)算點(diǎn)U和點(diǎn)Q在第j或第j-e維的坐標(biāo)差值

ku=|0.5-ujor(j-e)mod e|

(5)

其中，ujor(j-e)mod e是點(diǎn)U和點(diǎn)Q在第j-e維的坐標(biāo)。

多維數(shù)據(jù)索引在規(guī)則1里把各類虛擬任務(wù)索引為一維索引jeu后，能夠在云環(huán)境下，支持多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)多維管理。在此基礎(chǔ)之上，為了實(shí)現(xiàn)數(shù)據(jù)的區(qū)間管理，多維數(shù)據(jù)索引把jeu索引為主鍵h，h可表示數(shù)據(jù)在仿真平臺(tái)中覆蓋網(wǎng)絡(luò)結(jié)構(gòu)中的位置。

3 實(shí)驗(yàn)分析

實(shí)驗(yàn)使用仿真測(cè)試本文所提方法的應(yīng)用效果。仿真工具是Planet Sim，此工具使用Chord協(xié)議，以此模擬數(shù)據(jù)中心索引節(jié)點(diǎn)建立的覆蓋網(wǎng)絡(luò)。本文把虛擬任務(wù)數(shù)據(jù)節(jié)點(diǎn)規(guī)模設(shè)成2000，數(shù)據(jù)總量設(shè)成105×M，M是虛擬任務(wù)數(shù)據(jù)節(jié)點(diǎn)數(shù)量，數(shù)據(jù)集的元數(shù)據(jù)維數(shù)最大值是6，元數(shù)據(jù)值范圍是[0，2]。

3.1 正常環(huán)境下虛擬任務(wù)數(shù)據(jù)查詢效率測(cè)試

路由長(zhǎng)度是判斷數(shù)據(jù)查詢效率的核心指標(biāo)，在覆蓋網(wǎng)絡(luò)里路由長(zhǎng)度是查詢請(qǐng)求傳輸?shù)穆酚晒?jié)點(diǎn)跳數(shù)。實(shí)驗(yàn)主要在不同查詢請(qǐng)求、不同數(shù)據(jù)中心規(guī)模、不同查詢請(qǐng)求維數(shù)、不同查詢區(qū)間條件下，分析本文方法的應(yīng)用效果。平均路由長(zhǎng)度值較小，表示查詢效率較高。

3.1.1 不同查詢請(qǐng)求條件下應(yīng)用效果測(cè)試

設(shè)置虛擬任務(wù)數(shù)據(jù)不同查詢請(qǐng)求為A1、A2、A3、A4，A3、A4的維數(shù)設(shè)成4，A1、A2的虛擬任務(wù)數(shù)據(jù)節(jié)點(diǎn)選擇率設(shè)成0.06%。測(cè)試本文方法使用后，虛擬任務(wù)數(shù)據(jù)的查詢效率，結(jié)果如圖2所示。

圖2 復(fù)雜查詢模式中虛擬任務(wù)數(shù)據(jù)查詢效率

分析圖2可知，A3、A1的查詢效率具有高度一致性，A3、A1的查詢效率高于A2、A4，但此次測(cè)試結(jié)果中，不同查詢請(qǐng)求條件下，本文方法應(yīng)用后，虛擬任務(wù)數(shù)據(jù)查詢效率還是較為顯著的，后文將對(duì)本文方法的應(yīng)用效果進(jìn)行對(duì)比測(cè)試。

3.1.2 不同數(shù)據(jù)中心規(guī)模條件中應(yīng)用效果測(cè)試

以文獻(xiàn)[3]、文獻(xiàn)[4]所提方法為對(duì)比方法，在不同數(shù)據(jù)中心規(guī)模條件中，測(cè)試本文方法、面向DEM構(gòu)建的點(diǎn)云四叉樹和R樹混合索引方法、基于HBase的多維索引查詢機(jī)制的優(yōu)化方法應(yīng)用后，虛擬任務(wù)數(shù)據(jù)查詢效率，結(jié)果如圖3所示。

圖3 三種方法應(yīng)用效果測(cè)試

分析圖3可知，本文方法使用后，多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)查詢的平均路徑長(zhǎng)度值最小，虛擬任務(wù)數(shù)據(jù)查詢效率顯著優(yōu)于面向DEM構(gòu)建的點(diǎn)云四叉樹和R樹混合索引方法、基于HBase的多維索引查詢機(jī)制的優(yōu)化方法。當(dāng)虛擬任務(wù)數(shù)據(jù)節(jié)點(diǎn)規(guī)模出現(xiàn)變化時(shí)，本文方法應(yīng)用下，平均路徑長(zhǎng)度變化幅度最慢，但另外兩種方法應(yīng)用下，平均路徑長(zhǎng)度變化幅度不存在規(guī)律性，本文方法使用效果最佳。

3.1.1與3.1.2實(shí)驗(yàn)說明，在差異的數(shù)據(jù)中心規(guī)模條件中，本文方法都有較好的應(yīng)用效果，多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)數(shù)模逐漸變大時(shí)，本文方法應(yīng)用下，虛擬任務(wù)數(shù)據(jù)查詢的平均路徑長(zhǎng)度增長(zhǎng)速度最慢，平均路徑長(zhǎng)度最小，所以本文方法存在顯著的擴(kuò)展性，適用于云環(huán)境下多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)管理之中。

3.1.3 不同維數(shù)條件應(yīng)用效果測(cè)試

虛擬任務(wù)數(shù)據(jù)節(jié)點(diǎn)維數(shù)依次設(shè)成1000、2000，在不同數(shù)據(jù)維數(shù)條件中，測(cè)試本文方法、面向DEM構(gòu)建的點(diǎn)云四叉樹和R樹混合索引方法、基于HBase的多維索引查詢機(jī)制的優(yōu)化方法應(yīng)用效果。測(cè)試結(jié)果如圖4所示。

圖4 不同維數(shù)條件應(yīng)用效果測(cè)試結(jié)果

分析圖4可知，當(dāng)維數(shù)變化時(shí)，本文方法應(yīng)用下，多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)查詢的平均路徑長(zhǎng)度值最小，虛擬任務(wù)數(shù)據(jù)查詢效率變化最不顯著，原因是本文方法在使用金字塔技術(shù)處理多維數(shù)據(jù)時(shí)，對(duì)維數(shù)變化不存在敏感性。但另外兩種方法應(yīng)用下，虛擬任務(wù)數(shù)據(jù)查詢效率變化幅度顯著，多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)查詢的平均路徑長(zhǎng)度值較大，查詢效率較低。由此可知，本文方法應(yīng)用效果最佳。

3.1.4 不同查詢區(qū)間條件中應(yīng)用效果測(cè)試

將虛擬任務(wù)數(shù)據(jù)查詢請(qǐng)求維數(shù)設(shè)成4，虛擬任務(wù)數(shù)據(jù)節(jié)點(diǎn)數(shù)設(shè)成1500，在不同查詢區(qū)間條件中，測(cè)試本文方法、面向DEM構(gòu)建的點(diǎn)云四叉樹和R樹混合索引方法、基于HBase的多維索引查詢機(jī)制的優(yōu)化方法應(yīng)用效果，結(jié)果如圖5所示。

圖5 不同查詢區(qū)間條件中應(yīng)用效果測(cè)試結(jié)果

分析圖5可知，當(dāng)查詢區(qū)間變大，本文方法應(yīng)用后，虛擬任務(wù)數(shù)據(jù)查詢的平均路徑長(zhǎng)度值最小，虛擬任務(wù)數(shù)據(jù)查詢效率變大。原因是區(qū)間變大時(shí)，虛擬任務(wù)數(shù)據(jù)查詢請(qǐng)求將覆蓋多個(gè)有效數(shù)據(jù)節(jié)點(diǎn)，此時(shí)將會(huì)出現(xiàn)多個(gè)查詢鍵值，鍵值的同時(shí)運(yùn)行，將增加查詢時(shí)間。但相比之下，本文方法應(yīng)用后，虛擬任務(wù)數(shù)據(jù)查詢效率最顯著，另外兩種方法所受到的負(fù)面影響更為顯著。

綜上所述，當(dāng)數(shù)據(jù)中心規(guī)模、查詢請(qǐng)求維數(shù)、查詢區(qū)間出現(xiàn)變化時(shí)，本文方法應(yīng)用效果最佳，最適用于云環(huán)境下多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)的查詢應(yīng)用之中。

3.2 并發(fā)環(huán)境中虛擬任務(wù)數(shù)據(jù)查詢效率測(cè)試

將并發(fā)用戶人數(shù)依次設(shè)成20人、40人、60人、80人，測(cè)試本文方法、面向DEM構(gòu)建的點(diǎn)云四叉樹和R樹混合索引方法、基于HBase的多維索引查詢機(jī)制的優(yōu)化方法應(yīng)用效果，結(jié)果如圖6所示。

圖6 不同并發(fā)用戶人數(shù)條件下查詢效率測(cè)試結(jié)果

分析圖6可知，在不同并發(fā)用戶人數(shù)條件下，本文方法應(yīng)用后，虛擬任務(wù)數(shù)據(jù)查詢效率最顯著，和面向DEM構(gòu)建的點(diǎn)云四叉樹和R樹混合索引方法、基于HBase的多維索引查詢機(jī)制的優(yōu)化方法相比，本文方法使用價(jià)值最高。

4 結(jié)論

本文提出了云環(huán)境下多核仿真平臺(tái)虛擬任務(wù)數(shù)據(jù)索引設(shè)計(jì)方法。

1)該方法在使用基于分形維數(shù)的選擇性聚類融合算法，實(shí)現(xiàn)虛擬任務(wù)數(shù)據(jù)聚類后，設(shè)計(jì)多維數(shù)據(jù)索引機(jī)制M-Index。

2)通過金字塔技術(shù)把多維元數(shù)據(jù)進(jìn)行降維處理，變成一維索引，再通過前綴二叉樹把一維索引值域分為多個(gè)子區(qū)間，并將其所屬區(qū)間的前綴設(shè)成數(shù)據(jù)在實(shí)驗(yàn)平臺(tái)中的主鍵。

3)虛擬任務(wù)數(shù)據(jù)按照主鍵指示便可掌握數(shù)據(jù)的所在位置。經(jīng)過仿真結(jié)果表明，平均路由長(zhǎng)度值在5左右，虛擬任務(wù)數(shù)據(jù)查詢效率最顯著，證明本文方法存在較好的應(yīng)用效果。