并行環(huán)境下高效率交叉證認(rèn)的研究和實(shí)現(xiàn)課件

1、并行環(huán)境下高效率交叉證認(rèn)的研究和實(shí)現(xiàn)趙青國(guó)家天文臺(tái)天津大學(xué)天文信息技術(shù)聯(lián)合實(shí)驗(yàn)室 內(nèi)容交叉證認(rèn)在VO中的重要性及所面臨的挑戰(zhàn)PHIXmatch具體方法PHIXmatch實(shí)驗(yàn)結(jié)果及分析對(duì)比當(dāng)前各國(guó)做法PHIXmatch后續(xù)研究計(jì)劃內(nèi)容交叉證認(rèn)在VO中的重要性及所面臨的挑戰(zhàn)PHIXmatch具體方法PHIXmatch實(shí)驗(yàn)結(jié)果及分析對(duì)比當(dāng)前各國(guó)做法PHIXmatch后續(xù)研究計(jì)劃重要性&挑戰(zhàn)符合VO的重要使命使廣泛分布的天文數(shù)字存檔資源更加容易獲得、更具可理解性和互操作性，以提高天文學(xué)家科學(xué)新發(fā)現(xiàn)的潛能是科學(xué)家進(jìn)行更加深入的數(shù)據(jù)挖掘的基礎(chǔ)根據(jù)位置信息交叉證認(rèn)是基礎(chǔ)（又稱Fuzzy Join/ Grea

2、t Circle Join）挑戰(zhàn)：data avalanchepetabyte, next 10-yearshigh-degreed decentralized data diversities ：formats, naming schemas, data structures, etc內(nèi)容交叉證認(rèn)在VO中的重要性及所面臨的挑戰(zhàn)PHIXmatch具體方法PHIXmatch實(shí)驗(yàn)結(jié)果及分析對(duì)比當(dāng)前各國(guó)做法PHIXmatch后續(xù)研究計(jì)劃Our FunctionPHIXmatchPHIXmatch Paralleled Healpix-Indexing Xmatch實(shí)驗(yàn)任務(wù)：SDSS(1億)2MASS

3、（4.7億） 目標(biāo)結(jié)果：一對(duì)一、一對(duì)多、一對(duì)無(wú)SDSS_IDTwomass_IDDistance58773151261727136402595905+00002005.243e-0558773151261727136502595905+00002006.55e-0558773151315407682802593768+00122193.2e-0558773151315407726902593768+00122190.0025043169復(fù)雜度：n*n unacceptable解決辦法：畫(huà)框 (by GaoDan)并行化：消息傳遞型并行編程MPI建立高效索引，過(guò)濾范圍：Healpix（Hiera

4、rchical Equal Area isoLatitude Pixelization of a sphere ）針對(duì)索引方式，優(yōu)化一些函數(shù)PHIXmatch程序流程HEALPIXHEALPix Hierarchical Equal Area isoLatitude Pixelization of a sphere.功能強(qiáng)大，應(yīng)用廣泛，其中一個(gè)主要應(yīng)用為Cosmic Microwave Background (CMB) 的數(shù)據(jù)處理和數(shù)值模擬Healpix編碼方式方法一：Rings方法一：Nested為什么使用HEALPIX劃分方式？嵌套的層次編號(hào)方式: 臨近塊的ipnest只區(qū)別在低位，且ip

5、nest(Q1) is a prefix of ipnest(Q2) iff Q1 contains Q2.適合D-tree索引，物理上相近的塊 其塊號(hào)在數(shù)值上也連續(xù)或相近，自然地實(shí)現(xiàn)了臨近區(qū)域的聚類，適合于一切SQL系統(tǒng) 一次索引，可進(jìn)行多級(jí)精度上的計(jì)算，便于選取最合適索引塊和計(jì)算塊的級(jí)數(shù)。不同密度、速度的星體可選擇不同距離閾值等面積省去了對(duì)赤經(jīng)的修正(spherical-polar distortion problem )，避免了復(fù)雜的球面坐標(biāo)任務(wù)分配方式簡(jiǎn)單，容易實(shí)現(xiàn)負(fù)載平衡分塊成網(wǎng)格狀，拓?fù)湫螤钌线m合交叉證認(rèn)，false positive較少，周邊數(shù)據(jù)只有8塊（HTM有12塊）HEAL

6、PIX也適合Cone Search等常用查詢建索引速度快，與HTM對(duì)比，快一個(gè)數(shù)量級(jí)（by Wim OMullane et al）如何計(jì)算2MASS余邊塊索引號(hào)？Function1: 使用Healpix庫(kù)函數(shù) call neighbours（）Function2: 自己設(shè)計(jì)函數(shù)，根據(jù)情況執(zhí)行位運(yùn)算，效率高內(nèi)容交叉證認(rèn)在VO中的重要性及所面臨的挑戰(zhàn)PHIXmatch具體方法PHIXmatch實(shí)驗(yàn)結(jié)果及分析對(duì)比當(dāng)前各國(guó)做法PHIXmatch后續(xù)研究計(jì)劃結(jié)果及性能評(píng)價(jià)數(shù)據(jù)量：SDSS 100,106,811條記錄 2MASS 470,992,970條記錄索引級(jí)數(shù)： ，塊數(shù) ，每塊邊長(zhǎng)約為C語(yǔ)言MPI

7、MySQL計(jì)算塊數(shù)： ，則每計(jì)算塊包含 塊索引小塊硬件設(shè)備：4核服務(wù)器一臺(tái)（2G內(nèi)存），4進(jìn)程（3計(jì)算進(jìn)程）結(jié)果及性能評(píng)價(jià)校驗(yàn)上一對(duì)一結(jié)果：2017萬(wàn)結(jié)果及性能評(píng)價(jià)方法A表數(shù)據(jù)來(lái)源A表數(shù)據(jù)量B表數(shù)據(jù)來(lái)源B表數(shù)據(jù)量證認(rèn)耗時(shí)每秒完成證認(rèn)數(shù)PHIXmatch functionSDSS100,106,8112MASS470,992,97032分鐘52,139(按sdss統(tǒng)計(jì))Dec-1d-indexing function 無(wú)優(yōu)化法SDSS100,106,8112MASS470,992,9703天左右386 (按sdss統(tǒng)計(jì))(Dec,Ra)-indexing function無(wú)優(yōu)化法SDSS100,

8、106,8112MASS470,992,9703天左右386 (按sdss統(tǒng)計(jì))GaoDans FunctionGSC2.3部分295,832加入位置星等噪聲295,8325.6分鐘880Astrogrids Spatial Joins with Postgres1XMM56,000Northern section of 2MASS約2億4秒14,000(A)5000,000(B)獲得了較大的性能提升，使本地大規(guī)模交叉證認(rèn)成為可能內(nèi)容交叉證認(rèn)在VO中的重要性及所面臨的挑戰(zhàn)PHIXmatch具體方法PHIXmatch實(shí)驗(yàn)結(jié)果及分析對(duì)比當(dāng)前各國(guó)做法PHIXmatch后續(xù)研究計(jì)劃對(duì)比當(dāng)前各國(guó)做法索引

9、方式選擇One-dimensional IndexingTrue Multi-dimentional indexingR-tree, G-tree, Kdb-tree 不成熟，不通用很少的DBMS(Oracle, Postgres)內(nèi)置了spatial indexing方法，各種tree在查找、插入、刪除等操作上性能遠(yuǎn)不如D-tree，仍是一個(gè)研究課題球面的特殊性使平面卡迪爾坐標(biāo)下的空間索方法不完全適合，存在distorted scale問(wèn)題及赤經(jīng)的環(huán)繞問(wèn)題Mapping 2-d to 1-d functionHTM, Healpix等他們都不能滿足最高位跳躍（high-order bit f

10、lips）問(wèn)題，映射為線性空間不可避免地引入了不必要的數(shù)據(jù)對(duì)比當(dāng)前各國(guó)做法 NVO：not only for XmatchPoint-near-point, Point-in-region, regions-containing-pointregions：空間-時(shí)間-光譜多坐標(biāo)下的多邊形三種方法：HTM方法：table-valued function in SQL serverZone方法： SQL commands only突邊形的布爾代數(shù)法全部SQL批處理，減少了link時(shí)間，方法復(fù)雜SkyQuery是最先支持分布式數(shù)據(jù)空間聯(lián)合查詢的系統(tǒng)Web Services interfaces (S

11、OAP and WSDL) .NET infrastructure and C# language對(duì)比當(dāng)前各國(guó)做法Astrogrid多種嘗試R-tree spatial indexing選用Postgres數(shù)據(jù)庫(kù)進(jìn)行（Ra,Dec）二維索引下的Xmatch，并嘗試用此方法實(shí)現(xiàn)分布式交叉證認(rèn)、數(shù)據(jù)訪問(wèn)服務(wù)缺點(diǎn)：對(duì)數(shù)據(jù)庫(kù)要求嚴(yán)格，缺少可擴(kuò)展性Map 2-d to 1-d一個(gè)實(shí)驗(yàn)：1）對(duì)每條record計(jì)算pcode值（可能多個(gè)，預(yù)先計(jì)算了邊緣數(shù)據(jù)塊id并保存）2）預(yù)先根據(jù)pcode值建立usno到gsc映射表3）完全SQL指令交叉證認(rèn)USNO-GSC：3,000,000records. 純交叉證認(rèn)

12、過(guò)程快，但前期預(yù)計(jì)算耗時(shí)多，分塊細(xì)致，邊緣數(shù)據(jù)比例大，實(shí)現(xiàn)分布式服務(wù)時(shí)，數(shù)據(jù)副本比例大內(nèi)容交叉證認(rèn)在VO中的重要性及所面臨的挑戰(zhàn)PHIXmatch具體方法PHIXmatch實(shí)驗(yàn)結(jié)果及分析對(duì)比當(dāng)前各國(guó)做法PHIXmatch后續(xù)研究計(jì)劃PHIXmatch后續(xù)計(jì)劃完善算法，優(yōu)化性能調(diào)整計(jì)算塊大小、預(yù)先存儲(chǔ)部分中間結(jié)果，如臨近塊映射表、邊緣數(shù)據(jù)影射表嘗試數(shù)據(jù)庫(kù)端驅(qū)動(dòng)的交叉證認(rèn)擴(kuò)展研究，研究常用天文查詢的基于Healpix索引的高效解決方案包括Point-near-point、Point-in-region、Regions-containing-point等由空間向空間-時(shí)間-光譜多維擴(kuò)展，研究其高效存

13、儲(chǔ)、訪問(wèn)方案實(shí)現(xiàn)高效分布式在線交叉證認(rèn)及數(shù)據(jù)訪問(wèn)系統(tǒng)在線交叉證認(rèn)服務(wù)設(shè)計(jì)圖在線交叉證認(rèn)服務(wù)系統(tǒng)工作流程任務(wù)調(diào)度服務(wù)器接收、解析用戶提交的聯(lián)合查詢?nèi)蝿?wù)，解析為需要進(jìn)行交叉證認(rèn)的索引塊ipnest值，通過(guò)查詢所維護(hù)的ipnest-server列表，檢查緩存是否命中如果命中，則發(fā)送任務(wù)（包括此次任務(wù)涉及的ipnest值列表）到集群各個(gè)節(jié)點(diǎn)，啟動(dòng)集群節(jié)點(diǎn)的查詢計(jì)算任務(wù)如果不命中，則分配任務(wù)（ipnest值）給各個(gè)節(jié)點(diǎn)，再由各個(gè)節(jié)點(diǎn)并行向原始數(shù)據(jù)庫(kù)查詢、獲取指定ipnest的數(shù)據(jù)塊，計(jì)算并根據(jù)緩存替換算法決定是否保存數(shù)據(jù)塊于本機(jī)數(shù)據(jù)庫(kù)如果部分命中，則命中的塊先進(jìn)交叉證認(rèn)計(jì)算，同時(shí)各個(gè)節(jié)點(diǎn)啟動(dòng)向原始數(shù)據(jù)請(qǐng)求、傳輸數(shù)據(jù)的任務(wù)，以做到計(jì)算、傳輸盡可能重疊每個(gè)節(jié)點(diǎn)完成證認(rèn)后將結(jié)果返回給總服務(wù)器在線交叉證認(rèn)服務(wù)系統(tǒng)系統(tǒng)優(yōu)點(diǎn)盡量減少了查詢證認(rèn)過(guò)程中的數(shù)據(jù)傳輸雖然集群系統(tǒng)存儲(chǔ)量有限，但當(dāng)用戶查詢存在一定熱點(diǎn)時(shí)，緩存可以大大加快系統(tǒng)