熊聰聰 付立艷 趙 青

(天津科技大學(xué)人工智能學(xué)院 天津 300457)

0 引 言

時(shí)序數(shù)據(jù)生成是天文學(xué)家進(jìn)行天體時(shí)域分析的基礎(chǔ)，所謂時(shí)序數(shù)據(jù)生成是將來自不同拍攝時(shí)間、不同星表中數(shù)據(jù)，通過交叉證認(rèn)方法對(duì)確定為同一星體的數(shù)據(jù)，按照時(shí)間順序排序生成每個(gè)天體時(shí)間序列數(shù)據(jù)[1]的過程。

時(shí)序數(shù)據(jù)的生成的難點(diǎn)主要包括兩點(diǎn)：(1) 隨著時(shí)域觀測(cè)設(shè)備的發(fā)展，數(shù)據(jù)的采集能力越來越強(qiáng)，具有在時(shí)間軸上頻繁采樣的特點(diǎn)，這導(dǎo)致數(shù)據(jù)量巨大[2]。如南極AST3望遠(yuǎn)鏡，其每天數(shù)據(jù)采集量高達(dá)360 GB。再如興建中的寬視場(chǎng)瞬變?cè)囱蔡煸O(shè)備地面廣角相機(jī)陣[3](GWAC)，每15 s產(chǎn)生1.1 GB數(shù)據(jù)，每個(gè)觀測(cè)夜入庫(kù)僅星表數(shù)據(jù)高達(dá)2 TB。面對(duì)龐大的數(shù)據(jù)量，高效的時(shí)序數(shù)據(jù)生成方法成為難點(diǎn)，數(shù)據(jù)的存儲(chǔ)、查詢、證認(rèn)計(jì)算等方面均需要優(yōu)化設(shè)計(jì)[4]。(2) 時(shí)序數(shù)據(jù)生成需要對(duì)時(shí)間軸上每?jī)纱斡^測(cè)的數(shù)據(jù)進(jìn)行證認(rèn)計(jì)算，計(jì)算量高于普通天體交叉證認(rèn)計(jì)算。為了實(shí)現(xiàn)大規(guī)模星表的交叉證認(rèn)，高丹[5]提出了基于HTM索引和kd-tree的交叉證認(rèn)方法，文獻(xiàn)[6-7]針對(duì)漏源問題，采用基于HTM和HEALPix兩種分區(qū)的混合證認(rèn)計(jì)算算法，Zhao等[8-9]提出了基于MPI的多核并行交叉證認(rèn)算法，通過基于位運(yùn)算的快速相鄰塊編碼推導(dǎo)算法高效地取得誤差半徑范圍內(nèi)全部需證認(rèn)數(shù)據(jù)，解決了邊緣漏源問題，但仍然無法滿足批量多星表間的證認(rèn)需求。徐洋等[10-11]提出基于等經(jīng)緯分區(qū)二維空間網(wǎng)格的方法，萬萌等[12]采用列存儲(chǔ)內(nèi)存數(shù)據(jù)庫(kù)MonetDB提高數(shù)據(jù)訪問性能，在關(guān)系型數(shù)據(jù)庫(kù)方法中取得了較好的效率。徐洋等在面向GWAC的小天區(qū)數(shù)據(jù)上實(shí)現(xiàn)了實(shí)時(shí)交叉證認(rèn)，實(shí)時(shí)性良好，但仍難以解決千萬條以上星表數(shù)據(jù)的證認(rèn)問題。趙青等[13]實(shí)現(xiàn)了海量數(shù)據(jù)的并行天文交叉證認(rèn)，但時(shí)序數(shù)據(jù)生成的過程中的交叉證認(rèn)計(jì)算不同于傳統(tǒng)多波段交叉證認(rèn)計(jì)算，需要對(duì)時(shí)間軸上每?jī)纱斡^測(cè)的數(shù)據(jù)進(jìn)行證認(rèn)計(jì)算，計(jì)算量增加[5]，效率要求更高。因此，在數(shù)據(jù)預(yù)處理、分布式算法設(shè)計(jì)等方面需要更精準(zhǔn)的優(yōu)化。

綜合以上問題，本文提出一種面向海量星表數(shù)據(jù)的高效的時(shí)序數(shù)據(jù)生成方法ETSDGM(Efficient Time Series Data Generation Method)，其整體的設(shè)計(jì)框架圖如圖1所示。

圖1 ETSDGM整體的框架圖

本文方法的設(shè)計(jì)重點(diǎn)分為兩個(gè)階段：

第一階段為預(yù)處理期間的訪存優(yōu)化設(shè)計(jì)，重點(diǎn)在于基于“最大均衡層”的HEALPix數(shù)據(jù)劃分[14-15]以及分布式系統(tǒng)中的階段性“靜態(tài)+動(dòng)態(tài)”加權(quán)輪詢?nèi)蝿?wù)分配算法的設(shè)計(jì)。預(yù)處理階段的設(shè)計(jì)保證索引的均衡性，實(shí)現(xiàn)數(shù)據(jù)的快速定位和集群中各節(jié)點(diǎn)負(fù)載均衡性以及節(jié)點(diǎn)的高度并發(fā)性，為后續(xù)實(shí)現(xiàn)快速證認(rèn)計(jì)算提供一定的支持。

第二階段為證認(rèn)計(jì)算算法優(yōu)化，包括HEALPix數(shù)據(jù)過濾策略以縮減證認(rèn)數(shù)據(jù)的范圍和基于傳輸與計(jì)算重疊的邊緣數(shù)據(jù)處理方法，以減少數(shù)據(jù)通信耗時(shí)。圖2為ETSDGM整體的設(shè)計(jì)內(nèi)容及意義。

圖2 ETSDGM整體的設(shè)計(jì)內(nèi)容及意義

1 原始星表數(shù)據(jù)預(yù)處理階段的訪存優(yōu)化研究

在海量的天文數(shù)據(jù)面前，當(dāng)只有數(shù)據(jù)的一個(gè)子集對(duì)天文學(xué)家的特定研究工作真正有用時(shí)，處理整個(gè)數(shù)據(jù)既耗時(shí)又浪費(fèi)空間。通過訪存優(yōu)化，快速提取時(shí)空子集，為實(shí)現(xiàn)指定區(qū)域高效時(shí)序生成條件。圖3給出了此階段的整體步驟。原始星表文件中每一行代表一個(gè)星體，提取證認(rèn)計(jì)算需要的幾列信息定義一個(gè)適合生成時(shí)序數(shù)據(jù)的元數(shù)據(jù)文件格式。

圖3 原始星表文件的預(yù)處理過程

1.1 基于“最大均衡層”的HEALPix數(shù)據(jù)劃分策略

基于“最大均衡層”的HEALPix數(shù)據(jù)劃分方法，保證索引的均衡性，從而實(shí)現(xiàn)時(shí)空數(shù)據(jù)的快速提取。數(shù)據(jù)劃分將原本復(fù)雜度為N×N的證認(rèn)計(jì)算，通過分塊將其局限在同一位置分塊內(nèi)，降低了算法復(fù)雜度；同時(shí)實(shí)現(xiàn)分布式并行計(jì)算，充分利用集群高性價(jià)比的存儲(chǔ)和計(jì)算能力，提高證認(rèn)計(jì)算的效率，當(dāng)用戶請(qǐng)求特定的時(shí)空范圍內(nèi)的時(shí)序重構(gòu)數(shù)據(jù)時(shí)，合理的分塊布局可以使集群中的各個(gè)計(jì)算節(jié)點(diǎn)負(fù)載均衡地提供所需的數(shù)據(jù)查詢、證認(rèn)計(jì)算服務(wù)。

選擇HEALPix[16]偽球面索引方式，HEALPix在不同層級(jí)(Nside)下的網(wǎng)格劃分圖如圖4所示。其具有層次化結(jié)構(gòu)、等面積劃分、等緯度分布的特點(diǎn)。初始層級(jí)被劃分為12個(gè)面積相等的基準(zhǔn)球面四邊形，后續(xù)層級(jí)在此層級(jí)上進(jìn)行遞歸四等分。

圖4 HEALPix天球分區(qū)示意圖

HEALPix索引方式的劃分具有等面積性，考慮到星體數(shù)據(jù)分布不均勻，即在同一層級(jí)中有些編碼塊中星體數(shù)據(jù)量很大，有些則很小，容易導(dǎo)致索引結(jié)構(gòu)失衡，進(jìn)而使查詢效率低下[17]。為了解決這一問題，本文采用“最大均衡層”下的HEALPix數(shù)據(jù)劃分策略，保證每個(gè)存儲(chǔ)塊文件中數(shù)據(jù)量盡可能均衡。具體的計(jì)算方法如下：

(1) 計(jì)算不同層級(jí)k下的包含數(shù)據(jù)的總塊數(shù)n以及相同HEALPix編碼的星體個(gè)數(shù)Xi(即每塊星體數(shù)，i=1,2,…，n)。

(3) 計(jì)算每層中HEALPix編碼個(gè)數(shù)的標(biāo)準(zhǔn)差SK：

(4) 根據(jù)平均值和標(biāo)準(zhǔn)差計(jì)算變異系數(shù)CVK，CVK最小的為最大均衡層:

1.2 階段性“靜態(tài)+動(dòng)態(tài)”加權(quán)輪詢?nèi)蝿?wù)分配算法

原始星表文件經(jīng)過預(yù)處理之后，需要利用分布式計(jì)算來提高時(shí)序數(shù)據(jù)的生成性能。天文星表數(shù)據(jù)量往往達(dá)到了TB甚至PB級(jí)，交叉證認(rèn)計(jì)算屬于典型的數(shù)據(jù)密集型計(jì)算任務(wù)。這里數(shù)據(jù)量分配的多少直接決定任務(wù)量。

為了保證分布式系統(tǒng)中各節(jié)點(diǎn)任務(wù)量均衡性。采用加權(quán)輪詢?nèi)蝿?wù)分配算法。該算法根據(jù)服務(wù)器的不同處理能力為之分配不同權(quán)值，使其能夠接受相應(yīng)權(quán)值數(shù)的服務(wù)請(qǐng)求，但由于該算法是一種靜態(tài)平衡算法，需要人為設(shè)置權(quán)值，難以反應(yīng)服務(wù)器的實(shí)時(shí)性能，這導(dǎo)致負(fù)載不均衡。但如果采用純動(dòng)態(tài)輪詢分配方法，每次分配后都計(jì)算當(dāng)前負(fù)載，時(shí)間消耗較大，效率不高，考慮到集群節(jié)點(diǎn)的異構(gòu)情況以及應(yīng)用的實(shí)際情況，提出一種階段性“靜態(tài)+動(dòng)態(tài)”加權(quán)輪詢算法。即在階段內(nèi)采用“靜態(tài)”輪詢的思想，階段與階段之前引入“動(dòng)態(tài)”性，修改各節(jié)點(diǎn)權(quán)值，增強(qiáng)算法對(duì)集群當(dāng)前狀態(tài)的適應(yīng)性。

1.2.1算法思想

(1) 根據(jù)實(shí)際的情況找初始化到各節(jié)點(diǎn)的初始權(quán)值SWi。

(2) 根據(jù)初始權(quán)重SWi對(duì)第一批存儲(chǔ)塊文件進(jìn)行靜態(tài)輪詢分配。

(3) 當(dāng)?shù)谝慌鎯?chǔ)塊文件執(zhí)行完成時(shí)，計(jì)算當(dāng)前節(jié)點(diǎn)的實(shí)時(shí)剩余性能率Wi。

(4) 計(jì)算每個(gè)階段完成后的實(shí)時(shí)權(quán)值WWi。

(5) 根據(jù)實(shí)時(shí)權(quán)值，對(duì)下一批存儲(chǔ)塊的數(shù)據(jù)進(jìn)行靜態(tài)分配，重復(fù)以上步驟，直到數(shù)據(jù)分配完成。

1.2.2算法具體過程

1) 初始權(quán)重的計(jì)算。

Ci、Di、Mi、Bi(i=1,2,…,n表示節(jié)點(diǎn)個(gè)數(shù))分別為各節(jié)點(diǎn)初始狀態(tài)下CPU的剩余性能、磁盤IO的剩余性能、內(nèi)存的剩余性能、網(wǎng)絡(luò)帶寬的剩余性能。集群中的所有節(jié)點(diǎn)的初始狀態(tài)剩余性能總和為：

SWi表示各節(jié)點(diǎn)的初始化的權(quán)重：

式中：KC、KD、KM、KB分別表示的是CPU、磁盤IO、內(nèi)存、網(wǎng)絡(luò)帶寬的權(quán)值，且滿足KC+KD+KM+KB=1。

2) 靜態(tài)加權(quán)輪詢分配過程。

根據(jù)初始權(quán)重開始對(duì)第一批存儲(chǔ)塊進(jìn)行靜態(tài)分配：

(2) 節(jié)點(diǎn)當(dāng)前權(quán)重會(huì)一直變化，CWi=CWi+EWi，CWi等于EWi初始狀態(tài)下的選出所有節(jié)點(diǎn)中CWi最大的一個(gè)節(jié)點(diǎn)作為選中節(jié)點(diǎn)。

由表8可知，定芽數(shù)3、4、2之間無顯著性差異，但它們與定芽數(shù)5和定芽數(shù)1之間存在顯著性差異，定芽數(shù)5和定芽數(shù)1之間也存在顯著性差異。其中定芽數(shù)3均值最高。

(3) 選中節(jié)點(diǎn)的CWi=CWi-TW。

例如：假設(shè)有三個(gè)節(jié)點(diǎn){A,B,C},初始權(quán)重{EW1=3,EW2=4,EW3=2},TW=3+4+2=9，現(xiàn)在請(qǐng)求7次的分配情況如表1所示。

表1 靜態(tài)分配實(shí)例表

具體解釋：

第一次請(qǐng)求：A=3+3(EW1)=6,B=4+4(EW2)=8,C=2+2(EW3)=4,當(dāng)前權(quán)重最大的B節(jié)點(diǎn)，所以B=8-9(TW)=-1。第二次請(qǐng)求：A=6+3(EW1)=9,B=-1+4(EW2)=3,C=4+2(EW3)=6，A節(jié)點(diǎn)為當(dāng)前權(quán)重最大的點(diǎn)，所以A=9-9=0;以此類推。

3) 當(dāng)前節(jié)點(diǎn)實(shí)時(shí)權(quán)重計(jì)算。

分配到節(jié)點(diǎn)的存儲(chǔ)塊進(jìn)行計(jì)算任務(wù)，當(dāng)計(jì)算任務(wù)快完成時(shí)計(jì)算當(dāng)前節(jié)點(diǎn)的實(shí)時(shí)剩余性能率，根據(jù)計(jì)算出的實(shí)時(shí)權(quán)值WWi，對(duì)下一批存儲(chǔ)塊文件進(jìn)行第二步處理，以此類推直達(dá)數(shù)據(jù)全部分配完成。

各節(jié)點(diǎn)的剩余性能率為：

各節(jié)點(diǎn)使用過程中的實(shí)時(shí)權(quán)重為：

WWi=Wi×SWi

2 證認(rèn)計(jì)算算法優(yōu)化

2.1 HEALPix數(shù)據(jù)過濾策略提取時(shí)空子集

為了生成時(shí)序數(shù)據(jù)，需要交叉證認(rèn)來確定兩條星體是否為同一星體的數(shù)據(jù)，其原理可以概括為:星表中有兩個(gè)天體A和B。A的坐標(biāo)為(ɡ1,β1)，B的坐標(biāo)為(ɡ2,β2)。它們之間的角距離d為：

d=arcos(sinβ1sinβ2+cosβ1cosβ2cos(g1-g2))

(1)

(2)

式中：r1和r2是兩個(gè)星表的誤差半徑。當(dāng)A與B之間的角距離d滿足式(2)時(shí)，即證認(rèn)成功。本實(shí)驗(yàn)是同源星表不同拍攝時(shí)間數(shù)據(jù)間的證認(rèn)，沿時(shí)間軸進(jìn)行兩兩星表間的證認(rèn)計(jì)算，計(jì)算量更大。為了解決這個(gè)問題，在布局算法完成時(shí)設(shè)計(jì)了存儲(chǔ)在內(nèi)存中位置索引表，如表2所示，使用基于存儲(chǔ)塊文件的HEALPix數(shù)據(jù)過濾策略，快速定位、提取所需時(shí)空子集，減少兩兩距離計(jì)算的數(shù)據(jù)范圍，提高整個(gè)交叉證認(rèn)過程的效率。

表2 索引表的結(jié)構(gòu)

基于存儲(chǔ)塊文件的數(shù)據(jù)過濾具體步驟如下：

(1) 用戶給出檢索圓點(diǎn)與檢索半徑。

(2) 確定圓點(diǎn)在最大均衡層層級(jí)下的HEALPix編碼塊。

(3) 根據(jù)編碼塊的長(zhǎng)度大小找到略大于檢索半徑的向外擴(kuò)展的區(qū)塊對(duì)應(yīng)的HEALPix編碼。

(4) 根據(jù)HEALPix編碼和內(nèi)置的索引表定位到數(shù)據(jù)。

(5) 提取數(shù)據(jù)，進(jìn)行錐形驗(yàn)證。即計(jì)算每條數(shù)據(jù)與圓點(diǎn)的角距離，找到小于等于檢索半徑的數(shù)據(jù)即為提取的時(shí)空子集。數(shù)據(jù)量的減少和數(shù)據(jù)重新布局有利于計(jì)算效率的提升。

圖5為數(shù)據(jù)過濾的原理，假設(shè)索引的區(qū)域的半徑SR=4，這一層的每塊邊長(zhǎng)大概為2，索引區(qū)域的經(jīng)緯度(Ra,Dec)為錐形圓點(diǎn)(即圖中塊1所在中心大黑點(diǎn))，找到圓點(diǎn)所在的HEALPix塊號(hào)(圖中整個(gè)方格區(qū)塊)，驗(yàn)證數(shù)據(jù)。

圖5 數(shù)據(jù)過濾原理

2.2 基于傳輸與計(jì)算重疊的邊緣處理方法

由于望遠(yuǎn)鏡觀測(cè)誤差的存在，不同時(shí)間拍攝的同一個(gè)星體的數(shù)據(jù)可能會(huì)落入相鄰的兩個(gè)不同塊中，所以在進(jìn)行證認(rèn)計(jì)算時(shí)，為了提高證認(rèn)計(jì)算的準(zhǔn)確度，必須考慮邊緣漏源問題。邊緣漏源問題中面臨的就是數(shù)據(jù)傳輸問題，常用的解決方法是數(shù)據(jù)冗余，以空間存儲(chǔ)量的增加換取通信時(shí)間的減少?？紤]到數(shù)據(jù)的海量性，本文提出一種基于傳輸與計(jì)算重疊的邊緣數(shù)據(jù)處理方法，此方法可以減少數(shù)據(jù)之間的跨節(jié)點(diǎn)傳輸，還可以使數(shù)據(jù)傳輸時(shí)間盡量與計(jì)算時(shí)間重疊，減少證認(rèn)計(jì)算過程中等待傳輸數(shù)據(jù)的系統(tǒng)空閑時(shí)間，提高證認(rèn)計(jì)算的速率與準(zhǔn)確度。

實(shí)驗(yàn)中設(shè)計(jì)兩種塊:一種是存儲(chǔ)塊，即最大均衡層對(duì)應(yīng)的存儲(chǔ)塊；另一種即計(jì)算塊，計(jì)算塊就是交叉證認(rèn)計(jì)算的塊單位，即在同一個(gè)計(jì)算塊內(nèi)的星體數(shù)據(jù)都需要進(jìn)行兩兩交叉證認(rèn)計(jì)算。數(shù)據(jù)存儲(chǔ)是以存儲(chǔ)塊為單位進(jìn)行存儲(chǔ)，證認(rèn)計(jì)算是以計(jì)算塊為基礎(chǔ)進(jìn)行計(jì)算，根據(jù)HEALPix四叉樹結(jié)構(gòu)，當(dāng)計(jì)算塊的層級(jí)足夠大時(shí)，一個(gè)存儲(chǔ)塊中會(huì)包含很多的計(jì)算塊，使得許多計(jì)算塊與其邊緣塊在同一個(gè)節(jié)點(diǎn)上，無須跨節(jié)點(diǎn)傳輸，減少節(jié)點(diǎn)間的數(shù)據(jù)傳輸。

存儲(chǔ)塊與計(jì)算塊的結(jié)合使用，減少了跨節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)量，只有部分邊緣數(shù)據(jù)需要跨節(jié)點(diǎn)傳輸，為了減少數(shù)據(jù)傳輸所需時(shí)間占比，提高總體證認(rèn)速度，提出了傳輸時(shí)間與計(jì)算時(shí)間重疊的邊緣處理方法。也就是說當(dāng)計(jì)算塊內(nèi)的數(shù)據(jù)證認(rèn)計(jì)算完成時(shí)節(jié)點(diǎn)間的數(shù)據(jù)傳輸也已經(jīng)完成了，繼續(xù)進(jìn)行邊緣塊的證認(rèn)計(jì)算。通過對(duì)不同層級(jí)下邊緣數(shù)據(jù)傳輸時(shí)間以及不同劃分力度下的計(jì)算塊證認(rèn)計(jì)算的對(duì)比，找到證認(rèn)計(jì)算時(shí)間略大于邊緣塊數(shù)據(jù)傳輸時(shí)間的層級(jí)，即為HEALPix計(jì)算塊層，進(jìn)行證認(rèn)計(jì)算。

圖6為存儲(chǔ)塊與計(jì)算塊之間的關(guān)系，整個(gè)圖6是兩個(gè)不同拍攝時(shí)間的同一個(gè)存儲(chǔ)塊，整個(gè)存儲(chǔ)塊被劃分為許多小的計(jì)算塊，白色計(jì)算塊的所有邊緣塊都包含在此存儲(chǔ)塊中，即在同一個(gè)節(jié)點(diǎn)上，只有灰色計(jì)算塊的邊緣塊上的數(shù)據(jù)需要跨節(jié)點(diǎn)傳輸，同樣顯示了由于觀測(cè)誤差的存在，同一星體A落于不同計(jì)算塊中的情況。

圖6 計(jì)算塊與存儲(chǔ)塊的關(guān)系圖

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

3.1 軟硬件環(huán)境

本文實(shí)驗(yàn)的數(shù)據(jù)選取了中國(guó)虛擬天文臺(tái)網(wǎng)站上公開的AST3上的一部分?jǐn)?shù)據(jù)集，用來驗(yàn)證TSDGM方法的性能。數(shù)據(jù)大小為24.1 GB，包含4千萬條星體信息。實(shí)驗(yàn)中，使用了一臺(tái)Intel Core i5-4790 3.60 GHz的計(jì)算機(jī)作為Master CPU，它有8 GB內(nèi)存；3臺(tái)Intel Core i5-4590 3.30 GHz的計(jì)算機(jī)作為Worker CPU，內(nèi)存為4 GB。操作系統(tǒng)是Ubuntu 14.04 LTS(64位)，Linux內(nèi)核為4.4.0-31-generic。基于MPI技術(shù)實(shí)現(xiàn)分布式集群系統(tǒng)。

3.2 預(yù)處理階段訪存優(yōu)化提取時(shí)空子集的測(cè)試

最大均衡層保證存儲(chǔ)塊中數(shù)據(jù)量相對(duì)均勻分布，保證索引結(jié)構(gòu)均衡性和查詢效率，實(shí)現(xiàn)時(shí)空子集的快速提取。本文實(shí)驗(yàn)的原始數(shù)據(jù)是從AST3數(shù)據(jù)集中提取的，經(jīng)過對(duì)原始文件的預(yù)處理得到了按最大均衡層HEALPix編碼排序的存儲(chǔ)塊文件，利用階段性的“靜態(tài)+動(dòng)態(tài)”輪詢式任務(wù)分配算法存入各節(jié)點(diǎn)。根據(jù)1.1節(jié)給出的實(shí)驗(yàn)方法，通過對(duì)原始數(shù)據(jù)每層塊內(nèi)星體數(shù)據(jù)量平均值和標(biāo)準(zhǔn)差的計(jì)算，根據(jù)圖7變異系數(shù)CV的顯示，整體數(shù)據(jù)量分布最好的為8層，所以實(shí)驗(yàn)測(cè)定第8層作為“最大均衡層”是最優(yōu)的選擇。

圖7 不同層級(jí)下對(duì)應(yīng)的變異系數(shù)

圖8中三條曲線分別為不同層級(jí)下當(dāng)搜索半徑等于0.2 rad、0.1 rad、0.05 rad下經(jīng)過10次實(shí)驗(yàn)提取時(shí)空子集的平均時(shí)間，提取時(shí)空子集的時(shí)間等于相鄰HEALPix編碼計(jì)算時(shí)間、數(shù)據(jù)定位提取時(shí)間與錐形檢索驗(yàn)證時(shí)間之和。當(dāng)錐形檢索半徑弧度等于0.2時(shí)，第8層提取時(shí)空子集時(shí)間最少，原因是第8層的編碼塊長(zhǎng)度略大于檢索半徑0.2 rad，只需要提取錐形圓點(diǎn)相鄰一圈的HEALPix編碼塊進(jìn)行錐形檢索驗(yàn)證即可。對(duì)于第8層以前的層級(jí)，編碼塊的長(zhǎng)度是8層編碼塊的長(zhǎng)度的兩倍，即與第8層一樣只需要提取周圍一圈編碼塊，即相鄰的HEALPix編碼的計(jì)算時(shí)間相近，但是，根據(jù)HEALPix四叉樹結(jié)構(gòu)，上一層級(jí)的編碼塊面積是下一層級(jí)的4倍，同樣提取錐形圓點(diǎn)一圈周圍編碼塊，提取區(qū)域面積增加了4倍多，數(shù)據(jù)量相對(duì)也增加4倍多，導(dǎo)致數(shù)據(jù)定位提取時(shí)間和錐形驗(yàn)證時(shí)間增加。8層以后的層級(jí)，編碼塊長(zhǎng)度小于檢索半徑的長(zhǎng)度，導(dǎo)致提取相鄰編碼塊的計(jì)算時(shí)間增加，層級(jí)劃分越細(xì)，每次數(shù)據(jù)量相差不大，所以提取的數(shù)據(jù)和檢索驗(yàn)證時(shí)間不會(huì)發(fā)生太大的變化。當(dāng)檢索半徑弧度等于0.1 rad時(shí)，9層邊長(zhǎng)略大于檢索半徑，為提取時(shí)空子集時(shí)間最少的層級(jí)。當(dāng)檢索半徑弧度等于0.05 rad時(shí)，10層邊長(zhǎng)略大于檢索半徑，為提取時(shí)空子集時(shí)間最少的層級(jí)。還可以看出，在最大均衡層(第8層)時(shí)，搜索區(qū)域越大，相對(duì)的搜索時(shí)間卻相對(duì)減少，即在最大均衡層下每個(gè)存儲(chǔ)塊文件的數(shù)據(jù)均衡分布，根據(jù)索引表進(jìn)行數(shù)據(jù)定位時(shí)較好地實(shí)現(xiàn)了快速定位并進(jìn)行數(shù)據(jù)提取的目的。

圖8 不同層級(jí)下提取時(shí)空子集的時(shí)間

3.3 證認(rèn)計(jì)算優(yōu)化的測(cè)試

存儲(chǔ)塊與計(jì)算塊的結(jié)合使用直接提取邊緣數(shù)據(jù)，邊緣數(shù)據(jù)總的傳輸時(shí)間等于邊緣數(shù)據(jù)的提取時(shí)間與數(shù)據(jù)的傳輸時(shí)間的總和，圖9為不同HEALPix層級(jí)下計(jì)算塊的邊緣數(shù)據(jù)的傳輸完成時(shí)間，圖10為不同層級(jí)下的計(jì)算塊證認(rèn)時(shí)間與邊緣數(shù)據(jù)傳輸時(shí)間對(duì)比，實(shí)驗(yàn)結(jié)果顯示第11層時(shí)計(jì)算塊的證認(rèn)計(jì)算時(shí)間略大于數(shù)據(jù)傳輸時(shí)間。即選取11層為計(jì)算塊層，存儲(chǔ)塊與計(jì)算塊結(jié)合使用直接提取邊緣數(shù)據(jù)，不會(huì)出現(xiàn)多余的節(jié)點(diǎn)之間的通信時(shí)間，節(jié)點(diǎn)不會(huì)出現(xiàn)空閑的時(shí)間等待數(shù)據(jù)傳輸，減少了時(shí)間消耗，提高了證認(rèn)速度。

圖9 不同層級(jí)下一個(gè)計(jì)算塊邊緣數(shù)據(jù)傳輸完成時(shí)間

圖10 不同層級(jí)下計(jì)算塊證認(rèn)時(shí)間與邊緣數(shù)據(jù)傳輸時(shí)間

3.4 綜合測(cè)試

時(shí)序數(shù)據(jù)生成傳統(tǒng)方法是將FITS文件導(dǎo)入數(shù)據(jù)庫(kù)，并在此過程中對(duì)不同時(shí)間的數(shù)據(jù)通過交叉證認(rèn)的結(jié)果對(duì)天體記錄進(jìn)行matchID標(biāo)記，再?gòu)臄?shù)據(jù)庫(kù)中找到具有相同匹配ID的記錄，并將它們導(dǎo)入到文件中。最后可以根據(jù)這些文件中生成時(shí)序數(shù)據(jù)。為了顯示ETSDGM方法的性能，選取了AST3拍攝的HD88500、HD117688、HD136485文件中數(shù)據(jù)量分別為2.30 GB、6.38 GB、8.30 GB的數(shù)據(jù)，采用一個(gè)節(jié)點(diǎn)的情況下，與傳統(tǒng)時(shí)序數(shù)據(jù)生成時(shí)間進(jìn)行了對(duì)比測(cè)試。結(jié)果如表3所示。

表3 ETSDGM方法和一般方法的時(shí)間比較

表3中的時(shí)間是形成時(shí)序數(shù)據(jù)的總時(shí)間，可以看出即使在一個(gè)節(jié)點(diǎn)的情況下，TSDGM方法形成時(shí)序數(shù)據(jù)也比傳統(tǒng)方法更加有效，數(shù)據(jù)量越大TSDGM方法效果越明顯。在一個(gè)節(jié)點(diǎn)的情況下，不用考慮任務(wù)分配算法，在預(yù)處理階段，最大均衡層的設(shè)計(jì)讓存儲(chǔ)塊文件中的數(shù)據(jù)量均衡分布與HEALPix區(qū)塊過濾策略，確保了索引結(jié)構(gòu)的合理性，快速定位提取時(shí)空子集，計(jì)算階段存儲(chǔ)塊與計(jì)算塊文件的結(jié)合使用，減少了跨節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù)量，減少了系統(tǒng)等待數(shù)據(jù)傳輸?shù)目臻g時(shí)間，兩個(gè)階段的結(jié)合提高證認(rèn)速度，減少了時(shí)序數(shù)據(jù)總的生成時(shí)間。

圖11為對(duì)不同節(jié)點(diǎn)下生成時(shí)序數(shù)據(jù)的時(shí)間測(cè)試。圖12為不同節(jié)點(diǎn)下不同數(shù)據(jù)量的加速比。

圖11 不同節(jié)點(diǎn)下ETSDGM運(yùn)行時(shí)間

圖12 不同節(jié)點(diǎn)下加速比

4 結(jié) 語

本文設(shè)計(jì)一種面向海量星表數(shù)據(jù)的高效時(shí)序數(shù)據(jù)生成方法ETSDGM，整體分為兩個(gè)階段，預(yù)處理階段的訪存優(yōu)化設(shè)計(jì)與證認(rèn)計(jì)算算法的優(yōu)化設(shè)計(jì)。其中第一階段對(duì)原始星表文件進(jìn)行了訪存優(yōu)化，主要是進(jìn)行數(shù)據(jù)劃分和集群中任務(wù)均衡分配，實(shí)現(xiàn)數(shù)據(jù)的快速提??；第二階段主要是針對(duì)證認(rèn)計(jì)算過程優(yōu)化傳輸與計(jì)算耗時(shí)，進(jìn)一步提高證認(rèn)計(jì)算速率。實(shí)驗(yàn)結(jié)果表明，與以往的工作相比，ETSDGM可以實(shí)現(xiàn)更好的性能改進(jìn)，特別是在數(shù)據(jù)量較大的情況下。本文設(shè)計(jì)的高效時(shí)序數(shù)據(jù)生成方法對(duì)加快天文學(xué)家進(jìn)行時(shí)域分析具有良好的應(yīng)用價(jià)值。