《天津大学博士研究生毕业答辩》由会员分享，可在线阅读，更多相关《天津大学博士研究生毕业答辩（33页珍藏版）》请在金锄头文库上搜索。
1、面向海量数据的 高效天文交叉证认的研究答辩人：赵青指导老师：孙济洲 教授天津大学计算机学院 Email: 天津大学博士研究生毕业答辩主要内容 研究背景及意义 面向多核环境的并行交叉证认方法 面向分布式集群环境的交叉证认方法 面向HEALPix和HTM索引的快速邻域编码计算 算法 总结与展望研究背景及意义 天文多波段交叉证认的概念 基于位置信息的交叉证认 主要面临挑战： 天文观测设备的日新月异所带来的天文数据 的海量性：TB乃至PB量级，且呈类摩尔定 律增长 LAMOST 望远镜， 全称：大 天区面积 多目标光 纤光谱天 文望远镜 2008年10 月建成， 每夜能观 测上万个 天体的光 谱，世界
2、 上威力最 大，最重 要的天文 望远镜之 一 国家“十一五” 开始提出并已开 始建设的世界最 大的单口径射电 望远镜 500米口径球面 射电天文望远镜 （FAST）。 美国LSST望远镜，8.4米口径大尺度概要巡天 望远镜，每晚将产生数据量高达18TB，相当 于28000张普通光盘的容量。 关键是解决交叉证认的高效性需求与海 量的天文观测数据量之间的矛盾，因此 交叉证认是典型的数据密集型、I/O密集 型计算难题！ 研究意义 虚拟天文台项目数据访问服务的核心模块 LAMOST望远镜大科学工程三大子课题之一 中国科学院天文科学主题库索引层建设的必 要技术 统计分析、数据挖掘的基础多核环境下的并行交
3、叉证认的研究 研究意义： 当今处理器芯片已经步入多核时代，多核计算资源 的普及所带来的强大的计算能力为天文学中很多大 规模计算难题的解决提供了新的途径 画框：降低计算复杂度 基于伪二维球面索引的划分方法HEALPixHTM 使用伪二维球面索引的好处 嵌套的层次编号方式: 临近块的ID编码只区别在低位 ，且如果Q1区域包含Q2区域，则Q2的编码以Q1的 编码为前缀。 适合B-tree索引，物理上相近的块 其块号在数值上也连续 或相近，自然地实现了临近区域的聚类，适合于一切SQL 系统。 一次索引，可进行多级精度上的计算，便于选取最合适索 引块和计算块的级数。不同密度、速度的星体可选择不同 距离阈
4、值。 等面积 与简单网格天区划分方式相比，省去了对赤经的修正 (spherical-polar distortion problem )，避免了复杂的球面坐 标 任务分配方式简单，容易实现负载平衡 通用性 边界漏源问题的解决快速相邻块编码计算算法简单网格天区划分方式 并行方法设计 实验结果及分析 Aladin 可视化结果：方法星表A来源星表A数据 量星表B来源星表B数据 量运行总耗时Parallel HEALPix-index function ( )SDSS100,106,811 2MASS470,992,970 32分钟Parallel HEALPix-index function ( )
5、SDSS100,106,8112MASS470,992,970 25分钟Parallel HEALPix-index function ( )SDSS100,106,8112MASS470,992,970 57分钟Parallel HTM-index function ( )SDSS100,106,8112MASS470,992,97040分钟赤纬单维 索引方法SDSS100,106,8112MASS470,992,97073小时简单 网格天区划分方法SDSS100,106,8112MASS470,992,97078分钟高丹（KD-tree+HTM）Part of GSC 2.3 295,83
6、2 Generat from GSC2.3 295,832 5.8分钟 分析 与原高丹的方法相比，效率提高显著 计算耗时与查询数据耗时间的平衡：划分粒度过细 ，边缘数据的比例升高， B-tree索引特性决定非连 续数据查询效率较低；划分粒度过粗，则计算量较 高。 HTM索引与HEALPix索引相比： 相同面积下正三角形的周长大于正方形的边长Versionnumber of blocks bordering one compute- block HealPix4*2n+41HTM3*2(n+1)+61.5基于Boundary Growing Model的改进方法 数据库B-tree索引特性的利用
7、 数据加载计算流程：Boundary Growing Model 减少I/O读取耗时，抑制内存填充速度解决最主要性能瓶颈：频繁的I/O操作耗时 最大生长块概念 自顶向下的最大生长块快速确定方式增强Boundary Growing Model效果自适应于天体密度过滤空白区域 并行算法设计 实验结果及分析 实验一：稀疏数据集上的实验SDSS DR6星表（约1亿条数据）、2MASS星表（约4.7亿条数据）原始方法与改进方法的对比：计算块分 块数量SDSS数 据库查 询2MASS数据库 查询 （中心块）2MASS数据库查 询(边界块)距离 计算其他总用 时307s59s335s580s40s1321s
8、317s40s639s151s44s1191s427s54s1177s51s72s1781s计算块分块数 量SDSS数据库查 询2MASS数据库查 询距离计算其他总用时120s78s2489s48s2735s127s79s690s58s954s191s102s199s57s549s374s239s58s67s738s 实验二：非稀疏数据集上的实验 数据集：SDSS：47949212条记录、2MASS：35476377条记录 原始方法与改进方法的对比： 计算 块分 块数SDSS数据库 查询2MASS数据库查 询 （中心块）2MASS数据库查 询(边界块)距离计 算其他总用时33s17s124s9
9、6s16s286s33s19s191s24s16s283s43s28s403s11s22s507s计算块分块数SDSS数据库查询2MASS数据库查询距离计算其他总用时32s19s421s27s499s36s20s130s27s213s46s27s39s31s143s107s60s11s32s210s面向HTM索引的可行性分析 优化边界问题的解决方法 限制生长模型基于MapReduce分布式模型的交叉证认 意义： 数据急速增长，长期考虑，多核单机环境并 不现实 突破关系数据库在处理海量数据时的瓶颈 利用大规模集群获得更强大的计算能力，进 一步提高效率，为实现在线实时交叉证认和 联合查询打下基础M
10、apReduce模型 概念： MapReduce是Google在2004年提出的一个编程模 型，并已于2010年年初正式申请获批该项技术的专 利。它主要用以进行大规模数据集上的并行运算， 其主要概念“Map（映射）”和“Reduce（规约）”最 初借鉴于函数式编程语言。 优点： 适合处理海量数据，尤其适合于数据间存在较强独 立性的应用； 成本低廉，使原本必须借助于非常高昂的超级计算 机才能获得的计算能力可以在大量廉价机器上同样 实现； 易于编程，将任务分发、任务调度、数据分布、容 错处理、负载平衡等并行计算中不可避免的复杂控 制细节隐藏于系统的运行时后台处理中Step1:数据分布式存放（Map
11、+Reduce）输入星 表数据MapMapMapMapMapMapReduceReduceShuffle/SortChop/replicate（块号+来源，属性） （块号+来源，属性） （块号+来源，属性）（块号+来源，属性） （块号+来源，属性） （块号+来源，属性）（块号+来源，属性） （块号+来源，属性） （块号+来源，属性）（块号+来源，属性） （块号+来源，属性） （块号+来源，属性）（块号+来源，属性） （块号+来源，属性） （块号+来源，属性）Reduce数据块头部 星表A记录组 星表B记录组 数据块头部 星表A记录组 星表B记录组数据块头部 星表A记录组 星表B记录组 数据块头
12、部 星表A记录组 星表B记录组数据块头部 星表A记录组 星表B记录组 数据块头部 星表A记录组 星表B记录组Step2: 证认计算（Map）数据块头部 星表A记录组 星表B记录组 数据块头部 星表A记录组 星表B记录组数据块头部 星表A记录组 星表B记录组 数据块头部 星表A记录组 星表B记录组数据块头部 星表A记录组 星表B记录组 数据块头部 星表A记录组 星表B记录组MapMapMapMapMapResultResultResultResultResult证认结果实验 实验结果： 证认部分耗时：25秒 达到接近线性的加速比 意义： 确认了文件数据库在处理海量数据方面的优势 大幅度缩短大星表
13、交叉证认计算用时，为最终实现 实时联合查询服务提供了条件 充分利用了廉价的计算资源，对于快速增长的天文 数据量具有良好的可扩展性，为今后天文数据处理 提供了一种可行的方案。面向HEALPix和HTM索引的快速邻域编码计算算法 研究意义 各种交叉证认方法得以高效实现的必要前提 在各种天文数据查询、数据处理上有着广泛 的应用空间，如“锥形检索服务”r （ ， ）HEALPix索引下的邻接块编码计算算法异或运算之第二操作数求解规则： 如果最终目标是求东北方向的共边邻接块，即图中标志为“2”的邻接块，则其 异或运算符右侧的第二操作数的确定方式为：对原块编码从低位向高位寻找 第一次出现的“00”或“10
14、”，从该位开始直到最后一位间的每两位均变成“01”， 而更高位上均为“0”； 如果最终目标是求西南方向的共边邻接块，即图中标志为“6”的邻接块，则其 异或运算符右侧的第二操作数的确定方式为：对原块编码从低位向高位寻找 第一次出现的“00”或“01”，从该位开始直到最后一位间的每两位均变成“01”， 而更高位上均为“0”； 如果最终目标是求东南方向的共边邻接块，即图中标志为“4”的邻接块，则其 异或运算符右侧的第二操作数的确定方式为：对原块编码从低位向高位寻找 第一次出现的“11”或“10”，从该位开始直到最后一位间的每两位均变成“10”， 而更高位上均为“0”； 如果最终目标是求西北方向的共边
15、邻接块，即图中标志为“8”的邻接块，则其 异或运算符右侧的第二操作数的确定方式为：对原块编码从低位向高位寻找 第一次出现的“00”或“01”，从该位开始直到最后一位间的每两位均变成“10”， 而更高位上均为“0”； 块“2”编码： 块“4”编码： 块“6”编码： 块“8”编码： 块“1”编码： 块“3”编码： 块“5”编码： 块“7”编码： HTM索引下的邻接块编码计算算法异或运算之第二操作数求解规则： 如果最终目标是求1号角对边方向的邻接三角形编码，即标记为“1”的邻接块 ，则其异或运算符右侧的第二操作数的确定方式为：对原块编码从低位向高 位寻找第一次出现的“01”或“11”位，如果找到的是“01”，则从该位开始直到最 后一位间的每两位均为“11”，如果找到的是“11”，则从该位开始直到最后一位 间的每两位均为“10”，而更高位上均为“0”； 如果最终目标是求0号角对边方向的邻接三角形编码，即标记为“0”的邻接块 ，则其异或运算符右侧的第二操作数的确定方式为：对原块编码从低位向高 位寻找第一次出现的“00”或“11”位，无论找到的是“00”还是“11”，都从该位开 始直到最后一位间的每两位均设定为“11”，而更高位上均为“0”； 如果最终目标是求2号角对边方向的邻接三角形编码，即标记为“2”的邻接块 ，则其异或运算符右
