优化天文学软件gridding的方法

摘要

本发明公开了一种优化天文学软件gridding的方法，所述方法包括：实现内存分区并行；对CPU与集成众核架构MIC进行负载均衡处理。本发明实施例的方法大幅提高了SKA项目中gridding的运行效率，这对SKA项目有重要的意义。

说明书

技术领域

本发明涉及计算机应用技术领域，尤其涉及一种优化天文学软件gridding的方法。

背景技术

英特尔公司提出集成众核架构(MIC，Many Integrated Core Architecture)，不同于其他的加速平台，MIC是一种通用的多核的协处理器，它使用的是共享内存的架构，这使得MIC易于编程。

gridding是平方公里射电望远镜阵列(SKA，Square Kilometer Array)数据处理过程中非常重要的一个步骤，也是最好使的步骤之一。为了生成天空图像，需要对射电望远镜采集的数据进行一系列的操作，但望远镜产生的数据是不规则的，需要被映射到规整的二维网格上，随后才能进行傅里叶变化，这个映射的过程即gridding，这是SKA数据处理部分最复杂的过程之一。目前，gridding的串行处理版本速度无法达到理想状态。

发明内容

为解决现有存在的技术问题，本发明实施例提供一种优化gridding的方法。

为达到上述目的，本发明实施例的技术方案是这样实现的：

一种优化天文学软件gridding的方法，所述方法包括：

实现内存分区并行；

对CPU与集成众核架构MIC进行负载均衡处理。

其中，所述实现内存分区并行，包括：将二维网格grid分为代表不同类型的四个区域，将内存划分为多个内存块，将所述多个内存块分别分配到所述四个区域，所述grid表示一个二维向量，所述二维向量的大小是根据望远镜的特性确定的常量；建立多个线程，将每个所述线程和所述内存块一一对应，使得一个所述线程只能读写一个所述内存块，一个内存块有且只有一个所述线程能够读写。

其中，采用CPU为主、MIC为辅的offload模式，以实现所述CPU与MIC之间的负载均衡。

其中，所述CPU运算比例为78％，所述MIC运算比例为22％。

其中，所述对CPU与集成众核架构MIC进行负载均衡，还包括：使用SSE指令集进行数据类型的优化和向量化。

其中，所述对CPU与集成众核架构MIC进行负载均衡，还包括：使用transfer语句实现异步传输。

其中，在所述实现内存分区并行算法之后，以及在所述对CPU与集成众核架构MIC进行负载均衡之前，所述方法还包括：数据预处理及异构处理。

本发明实施例提供了一种基于MIC对gridding进行优化的方法，在MIC的基础上，针对SKA项目中的gridding程序进行了优化；使用了内存分区算法、数据结构和内存使用的优化、向量化，基于MIC硬件的并行算法和基于英特尔编译器的编译器级别的优化在内的诸多优化措施，使得最终平均优化效果达到40倍，大幅提高了SKA项目中gridding的运行效率，这对SKA项目有重要的意义。

附图说明

在附图(其不一定是按比例绘制的)中，相似的附图标记可在不同的视图中描述相似的部件。具有不同字母后缀的相似附图标记可表示相似部件的不同示例。附图以示例而非限制的方式大体示出了本文中所讨论的各个实施例。

图1为本发明实施例gridding优化方法的流程示意图；

图2为本发明实施例grid函数功能的示意图；

图3为本发明实施例内存分区的示例示意图；

图4为图3示例的数据竞争现象示意图。

具体实施方式

本发明实施例的主要思想是：基于MIC从内存分区并行、以及CPU&MIC的负载平衡两个方面对gridding进行优化。

如图1所示，本发明实施例基于MIC优化gridding的方法，主要可以包括如下步骤：

步骤101：实现内存分区并行；

步骤102：对CPU与MIC进行负载均衡处理。

其中，步骤101中，针对gridding程序进行内存分区，消除数据竞争，控制边界效应，并实现多线程的并行读写处理。该步骤中实现内存分区并行的过程包括：消除数据竞争、内存冗余划分以及进程与内存分区对应，实现并行。具体地，将二维网格grid分为代表不同类型的四个区域，将内存划分为多个内存块，将所述多个内存块分别分配到所述四个区域，所述grid表示一个二维向量，所述二维向量的大小是根据望远镜的特性确定的常量；建立多个线程，将每个所述线程和所述内存块一一对应，使得一个所述线程只能读写一个所述内存块，一个内存块有且只有一个所述线程能够读写。

其中，步骤102中，采用CPU&MIC异构化设计，基于MIC进行异步传输和数据向量化，并控制CPU和MIC之间的负载平衡。具体可以包括：使用MIC的Offload模式实现；使用transfer语句实现异步传输；以及，使用SSE指令集进行数据类型的优化和向量化。实际应用中，采用CPU为主、MIC为辅的offload模式，以实现所述CPU与MIC之间的负载均衡。

进一步地，在步骤101之后、步骤102之前，所述方法还可以包括：数据预处理及异构处理的步骤。具体地，预处理包括数据类型及形式转换。类型转换，例如将STL complex数据转换成double才能进行数据传输。形式转换：例如将数组转为指针等。数据预处理还可以包括数据预取(缓存优化)、内存对齐等等。

进一步地，上述的数据预处理和异构处理还可以包括：建立数据结构。

下面针对本发明实施例优化Gridding方法的具体实现过程进行详细说明。

本发明实施例中建立数据结构的过程如下：

具体可以按照下表1设置数据结构，具体可以包括五个数据类型：samples、立方体C、二维网格(grid)、samples.iu/iv/coffset、以及samples.data。其中，立方体C表示一个五维向量，grid代表一个gSize*gSize的二维向量，sSize、gSize等数值是根据望远镜的特性输入的确定的常量。

变量类型大小samplesStructure vectornSampleCDouble vectorC.Size()gridDouble vectorgSize*gSizesamples.iu/iv/coffsetInteger1samples.dataDouble1

表1

其中，将实际大小为[129,129,8,8,33]的五维向量，视为一个立方体C，该立方体C底面为sSize*sSize(129*129)，高度为8*8*33。grid代表一个gSize*gSize的二维向量，可视做一个平面。

设置gind(index of grid)和cind(index of C)两个头指针，gind是一块gSize*gSize正方形区域的头指针，cind是立方体C中一个sSize*sSize平面的头指针，通过这两个头指针将立方体C中一个平面的正方形内存区域通过乘d累加到grid里面的正方形内存区域。这里，grid即为规整的二维网格，其函数功能如图2所示，其中，double*gptr＝&grid[gind]；double*cptr＝&C[cind]；gptr(pointer of grid)，cptr(pointer of C)为指针。其中，sSize、gSize等数值是根据望远镜的特性输入的确定的常量。

本发明实施例中内存分区并行算法的具体实现过程如下：

为了解决数据竞争的问题，本发明实施例内存分区并行算法的基本思想是，将一个grid分为代表不同类型的四个区域，假设将内存分为16个内存块，所述内存块分别对应所述四个区域，内存的分配方式如图3所示。其中，第1小块是第一类，假如gind点落入右边界和下边界附近时，那其gind对应的sSize*sSize小方块则有部分必然落在2-4小块，如图4所示。此时，第2-4小块中的深灰色部分不能进行读写，否则会有可能导致内存被不同线程同时读写，出现数据竞争现象。

本发明实施例中，为避免数据竞争，本发明实施例的内存分区并行算法还包括：将每个线程和唯一的内存块一一对应，使得一个线程只能读写一个内存块，一个内存块有且只有一个线程能够读写。例如，图3所示左上区域由1号进程读写第1内存块，图3所示右上区域由2号进程读写第1内存块，则可称此grid为第一类型grid_1，如此，实现了内存冗余算法，也能够保证第二、三、四类型grid_2、grid_3、grid_4的读写。实际应用时，优选划分四个grid大小的内存即可。

如下表2所示，为线程和内存分配的示例：

线程号grid类型区域读写的内存块号码1grid_1左上12grid_1右上13grid_1左下14grid_1右下15grid_2左上26grid_2右上27grid_2左下28grid_2右下29grid_3左上310grid_3右上311grid_3左下312grid_3右下313grid_4左上414grid_4右上415grid_4左下416grid_4右下4

表2

本发明实施例中，一个grid可以进行多个进程的读写，并且不会有数据竞争的问题，从而实现并行化。实际应用中，此种内存分区方法需要预先建立并保存线程号和内存块的对应关系，最后还需要有一个累加合并的过程。

本发明实施例中，数据预处理及异构处理的步骤，具体实现过程如下：将原本的算法移植到MIC中，同时使用offload_transfer语句异步传输，将一部分应传入MIC的数据提前进行处理，继而实现异步传输。实际应用中，MIC&CPU并行(target if语句)可以运用if语句使MIC&CPU异构运行。

本发明实施例中，CPU&MIC负载平衡处理的具体实现过程如下：

通过CPU为主，MIC为辅的offload模式，利用MIC提高并行效率。同时通过测试，以取得最佳的静态负载平衡，最大发挥CPU和MIC的性能，得出最佳优化效果。如表3所示为测试结果。

CPU运算率(％)Time(s)Rate(milliongrid points/s)011.154775.89259.515599.537.58.776071.97507.756871.1262.56.967651.03726.178630.66755.998890.02785.619492.19815.919010.3687.56.368372.831006.178630.66

表3

通过多次统计，发现静态负载平衡点在CPU运算比例为78％左右。因此，本发明实施例中，优选CPU运算比例为78％、MIC运算比例为22％，以达到最佳的静态负载平衡。

本发明实施例中，在负载均衡的处理中，还需要进行数据类型的优化和向量化。从上述数据结构可知，主要数据类型是复数型，当其运用向量化时变得异常困难。因为其特殊的数据结构导致自动向量化不可行，利用SIMD语句进行向量化时，需要将复数的实部和虚部提出来保存到相应double数组中，继而进行含有4个double乘法的向量化。本发明实施例中，优选使用SSE指令集进行数据类型的优化和向量化。

本发明实施例优化过程的算例如下：

nSamples＝3200000(样本总数，决定第一层循环的次数)；wSize＝33；nChan＝1；gSize＝4096；baseline＝2000；cellSize＝5.000000。这五个变量影响了cind、gind等函数变量的值，以上前三个值可以任意修改。

测试结果表示方法：time(s)表示gridKernel执行时间；Rate(million grid pointsper second)表示每秒grid的栅格数，越高表示程序速度执行越快。

正确性验证(L1范式)：通过程序verify计算对比gridKernel的执行结果与标准结果grid_std.dat，若L1范式差值小于1e-12则表示能够接受。

优化结果：在实验平台上对一个3200000大小的随机样本进行gridding运算，计算系统时间，并对结果进行L1范式检查，保证误差在允许的范围内。通过对优化算法的不断改进，得出以下优化结果如表4所示：

VersionTime(s)Rate(million grid points/s)优化倍数串行229.37232.1631内存分区算法26.172034.828.76MIC+CPU5.619492.1940.89

表4

本发明实施例在MIC的基础上，针对SKA项目中的gridding程序进行了优化；使用了内存分区算法、数据结构和内存使用的优化、向量化，基于MIC硬件的并行算法和基于英特尔编译器的编译器级别的优化在内的诸多优化措施，最后再通过多节点进行MPI的并行化处理，使得最终平均优化效果达到40倍，这对SKA项目有重要的意义。

以上所述，仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。