关键词:
并行计算
GPU
消色散算法
单脉冲搜索
快速折叠算法
摘要:
近年来,随着数据规模的与日俱增,对计算的需求也在不断增长。同时集成传统通用处理器(CPU)与新型协处理器(GPU、FPGA、Xeon Phi等)的异构系统成为解决各类计算问题一种途径,逐渐得到大众的认同,从学术界走向了工业界。传统通用处理器能够处理复杂的控制任务,提供通用计算;而新型协处理器以其核心数众多、高性价比等特点,能够为计算提供加速。然而由于异构系统的系统架构、指令集与编程模型与传统的计算存在着各种差异,使得基于异构系统的应用开发与调试变得越来越复杂,特别是众核GPU的出现,使得系统内部出现成百上千个计算核心,这对基于传统通用处理器的应用算法并行化提出了更高要求。因此研究基于CPU/GPU并行算法及其关键优化技术显得非常必要,通过提高算法并行度、优化算法的存储结构等手段,充分挖掘异构系统的计算潜力,利用好其众多计算核心的性能成为应用加速的有效途径。本文针对CPU/GPU并行算法及其关键优化技术进行了研究,针对脉冲星搜索数据处理流程中,不同处理步骤出现的不同问题,在异构系统环境下进行并行加速,将研究成果应用到具体项目中,取得了较好的加速效果。本文的工作与创新点主要包括:(1)研究了脉冲星搜索流程,并针对基于著名脉冲星搜寻工具PRESTO的搜索流程进行加速,对其中消耗时间占90%左右的非相干消色散步骤使用GPU进行加速,有效提升了消色散性能。通过FAST试观测阶段的相关参数模拟的脉冲星搜寻数据文件测试结果表明,在单GPU上执行相比于PC串行执行有超过10倍的加速;本文提出的并行消色散算法支持多GPU,在6块GPU上的计算加速相比于PC处理器串行执行有近60倍的加速,相比于服务器串行执行有超过200倍的加速效果。采用GPU处理2048通道的时间(816秒)与PC串行处理256通道数的时间(812秒)大致相同,而在GPU上计算2048通道的信噪比为149.4,相比在PC串行处理256通道的信噪比53.4,有近3倍的信噪比提升,从而更有利于后续脉冲星候选体的识别。对于FAST数据脉冲星搜寻处理流程中的实时快速傅里叶变换、加速搜索、折叠三个步骤,本文采用基于CPU的任务队列与线程池组合并行设计,在4核8线程的PC上测试结果表明,相比于PC串行有超过4倍的加速效果。本文分别在一台4核8线程CPU配置1块GPU的PC与一台64核128线程配置6块GPU卡的服务器上对基于FAST试观测参数模拟的一个脉冲星巡天文件进行计算,相比于PC串行执行,整体搜索有超过10倍的加速;相比于服务器串行执行,整体搜索有超过100倍的加速。(2)研究了单脉冲搜索及识别流程,对FAST超宽带数据进行了重处理,发现了7颗脉冲星候选体,其中2颗已经得到验证并公布,单脉冲共搜索到112颗脉冲星,其中45颗为FAST发现的新脉冲星。设计了一个并行化的单脉冲搜索及识别流程,对2017年8月至2018年5月之间FAST调试过程中的数据进行再处理。其中消色散由于耗时最高,在GPU上进行计算,单脉冲搜索、单脉冲候选体筛选、数据折叠3个步骤是采用CPU并行实现。对单脉冲搜索生成的单脉冲候选体文件进行分组与识别,通过后期数据分析及实验比对发现,通过减小消色散步长,加密消色散网格,可以有效提升单脉冲的识别效果。采用FFA快速折叠算法进行周期搜索,利用周期搜索到的最大信噪比所对应的周期进行数据折叠得到脉冲星候选体。利用脉冲星分类与诊断工具对色散值与信噪比分布情况进行检查判断搜到的单脉冲是否为来自于宇宙的射电辐射。建立了FAST超宽带数据单脉冲搜索数据库,对搜索到的单脉冲数据进行管理,数据库共计记录2244298个单脉冲候选体分组。将FAST单脉冲数据库与Parkes单脉冲搜索数据库做了比对,FAST在相同指向天区匹配到脉冲星21颗,其中包含4颗FAST新发现的脉冲星。经过DM值比对匹配到8颗FAST与Parkes共同探测到的已知脉冲星。(3)研究了快速折叠算法的并行策略,给出了一种基于GPU的并行快速折叠算法,算法分成块内并行与块间并行两部分。对影响GPU并行快速折叠算法性能的因素进行分析,对于在计算过程中采用双精度浮点格式的时间序列数据,其计算强度小于1/24,因此影响快速折叠算法性能的主要因素为访存带宽问题。讨论了几种增加访存带宽问题的基本策略,但是由于GPU硬件限制(全局内存、共享内存大小等),影响到了并行性的扩展。基于快速折叠算法周期搜寻工具ffancy中的第1种脉冲轮廓评估算法,给出了一种基于绝对中位差进行数据归一化以及过滤筛选的并行化脉冲轮廓评估算法。在一台4核8线程CPU配置1块GPU的PC上进行实验测试后发现,对于未进行下采样时间序列在CPU上串行周期搜寻耗时31.12秒,采用并行GPU实现耗时8.02秒,加速比约为3.88。对于目前的并行搜索算法,通过耗费比在CP