[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN105955825B - 优化天文学软件gridding的方法 - Google Patents

优化天文学软件gridding的方法 Download PDF

Info

Publication number
CN105955825B
CN105955825B CN201610303402.8A CN201610303402A CN105955825B CN 105955825 B CN105955825 B CN 105955825B CN 201610303402 A CN201610303402 A CN 201610303402A CN 105955825 B CN105955825 B CN 105955825B
Authority
CN
China
Prior art keywords
mic
cpu
memory
grid
load balancing
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN201610303402.8A
Other languages
English (en)
Other versions
CN105955825A (zh
Inventor
刘刚
郭聪
梁文栋
毛睿
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Shenzhen University
Original Assignee
Shenzhen University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Shenzhen University filed Critical Shenzhen University
Priority to CN201610303402.8A priority Critical patent/CN105955825B/zh
Publication of CN105955825A publication Critical patent/CN105955825A/zh
Application granted granted Critical
Publication of CN105955825B publication Critical patent/CN105955825B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
    • G06F9/5011—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resources being hardware resources other than CPUs, Servers and Terminals
    • G06F9/5016—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resources being hardware resources other than CPUs, Servers and Terminals the resource being the memory

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Devices For Executing Special Programs (AREA)

Abstract

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

Description

优化天文学软件gridding的方法
技术领域
本发明涉及计算机应用技术领域，尤其涉及一种优化天文学软件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等数值是根据望远镜的特性输入的确定的常量。
变量 类型 大小
samples Structure vector nSample
C Double vector C.Size()
grid Double vector gSize*gSize
samples.iu/iv/coffset Integer 1
samples.data Double 1
表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类型 区域 读写的内存块号码
1 grid_1 左上 1
2 grid_1 右上 1
3 grid_1 左下 1
4 grid_1 右下 1
5 grid_2 左上 2
6 grid_2 右上 2
7 grid_2 左下 2
8 grid_2 右下 2
9 grid_3 左上 3
10 grid_3 右上 3
11 grid_3 左下 3
12 grid_3 右下 3
13 grid_4 左上 4
14 grid_4 右上 4
15 grid_4 左下 4
16 grid_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)
0 11.15 4775.89
25 9.51 5599.5
37.5 8.77 6071.97
50 7.75 6871.12
62.5 6.96 7651.03
72 6.17 8630.66
75 5.99 8890.02
78 5.61 9492.19
81 5.91 9010.36
87.5 6.36 8372.83
100 6.17 8630.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 gridpoints per second)表示每秒grid的栅格数，越高表示程序速度执行越快。
正确性验证(L1范式)：通过程序verify计算对比gridKernel的执行结果与标准结果grid_std.dat，若L1范式差值小于1e-12则表示能够接受。
优化结果：在实验平台上对一个3200000大小的随机样本进行gridding运算，计算系统时间，并对结果进行L1范式检查，保证误差在允许的范围内。通过对优化算法的不断改进，得出以下优化结果如表4所示：
Version Time(s) Rate(million grid points/s) 优化倍数
串行 229.37 232.163 1
内存分区算法 26.17 2034.82 8.76
MIC+CPU 5.61 9492.19 40.89
表4
本发明实施例在MIC的基础上，针对SKA项目中的gridding程序进行了优化；使用了内存分区算法、数据结构和内存使用的优化、向量化，基于MIC硬件的并行算法和基于英特尔编译器的编译器级别的优化在内的诸多优化措施，最后再通过多节点进行MPI的并行化处理，使得最终平均优化效果达到40倍，这对SKA项目有重要的意义。
以上所述，仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。

Claims (6)

1.一种优化天文学软件gridding的方法，其特征在于，所述方法包括：
实现内存分区并行；
对CPU与集成众核架构MIC进行负载均衡处理；
所述实现内存分区并行，包括：
将二维网格grid分为代表不同类型的四个区域，将内存划分为多个内存块，将所述多个内存块分别分配到所述四个区域，所述grid表示一个二维向量，所述二维向量的大小是根据望远镜的特性确定的常量；
建立多个线程，将每个所述线程和所述内存块一一对应，使得一个所述线程只能读写一个所述内存块，一个内存块有且只有一个所述线程能够读写。
2.根据权利要求1所述的方法，其特征在于，采用CPU为主、MIC为辅的offload模式，以实现所述CPU与MIC之间的负载均衡。
3.根据权利要求2所述的方法，其特征在于，所述CPU运算比例为78％，所述MIC运算比例为22％。
4.根据权利要求1-3中任一项所述的方法，其特征在于，所述对CPU与集成众核架构MIC进行负载均衡，还包括：使用SSE指令集进行数据类型的优化和向量化。
5.根据权利要求1-3中任一项所述的方法，其特征在于，所述对CPU与集成众核架构MIC进行负载均衡，还包括：使用transfer语句实现异步传输。
6.根据权利要求1所述的方法，其特征在于，在所述实现内存分区并行算法之后，以及在所述对CPU与集成众核架构MIC进行负载均衡之前，所述方法还包括：数据预处理及异构处理。
CN201610303402.8A 2016-05-09 2016-05-09 优化天文学软件gridding的方法 Active CN105955825B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201610303402.8A CN105955825B (zh) 2016-05-09 2016-05-09 优化天文学软件gridding的方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201610303402.8A CN105955825B (zh) 2016-05-09 2016-05-09 优化天文学软件gridding的方法

Publications (2)

Publication Number Publication Date
CN105955825A CN105955825A (zh) 2016-09-21
CN105955825B true CN105955825B (zh) 2020-07-10

Family

ID=56914325

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201610303402.8A Active CN105955825B (zh) 2016-05-09 2016-05-09 优化天文学软件gridding的方法

Country Status (1)

Country Link
CN (1) CN105955825B (zh)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106598552A (zh) * 2016-12-22 2017-04-26 郑州云海信息技术有限公司 基于Gridding模块的数据点转换方法及装置

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103279391A (zh) * 2013-06-09 2013-09-04 浪潮电子信息产业股份有限公司 一种基于cpu与mic架构处理器协同计算的负载均衡优化方法
CN103530132A (zh) * 2013-10-29 2014-01-22 浪潮电子信息产业股份有限公司 一种cpu串行程序移植到mic平台的方法
CN104375838A (zh) * 2014-11-27 2015-02-25 浪潮电子信息产业股份有限公司 一种基于OpenMP对天文学软件Gridding的优化方法

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103279391A (zh) * 2013-06-09 2013-09-04 浪潮电子信息产业股份有限公司 一种基于cpu与mic架构处理器协同计算的负载均衡优化方法
CN103530132A (zh) * 2013-10-29 2014-01-22 浪潮电子信息产业股份有限公司 一种cpu串行程序移植到mic平台的方法
CN104375838A (zh) * 2014-11-27 2015-02-25 浪潮电子信息产业股份有限公司 一种基于OpenMP对天文学软件Gridding的优化方法

Also Published As

Publication number Publication date
CN105955825A (zh) 2016-09-21

Similar Documents

Publication Publication Date Title
JP5425541B2 (ja) マルチプロセッサ・システム上でデータ・セットを区分化およびソートするための方法および装置
Wu et al. Kernel weaver: Automatically fusing database primitives for efficient gpu computation
Bergmann et al. Algorithmic choices in WARP–A framework for continuous energy Monte Carlo neutron transport in general 3D geometries on GPUs
CN107657599B (zh) 基于混合粒度划分和动态负载分配的遥感图像融合系统并行实现方法
US20200210805A1 (en) Neural Network Generator
CN102609393A (zh) 一种线性方程组的数据处理方法及装置
CN110135569A (zh) 一种异构平台神经元定位三级流水并行方法、系统及介质
CN103177414A (zh) 一种基于结构的图节点相似度并行计算方法
CN112765094A (zh) 一种基于数据划分和计算分配的稀疏张量典范分解方法
CN108897616B (zh) 基于并行运算的非下采样轮廓波变换优化方法
CN109522127B (zh) 一种基于gpu的流体机械仿真程序异构加速方法
Jiang et al. Parallel contributing area calculation with granularity control on massive grid terrain datasets
CN111708511A (zh) 用于神经网络的数据压缩
CN105955825B (zh) 优化天文学软件gridding的方法
CN115344383A (zh) 一种基于进程并行的流线可视化并行加速方法
CN104572588B (zh) 矩阵求逆处理方法和装置
CN112035995A (zh) 基于gpu计算技术的非结构网格潮汐潮流数值模拟方法
Fan et al. Fast sparse gpu kernels for accelerated training of graph neural networks
CN111274335B (zh) 一种面向空间叠加分析的快速实现方法
Chatterjee et al. Data structures and algorithms for counting problems on graphs using gpu
CN115756605A (zh) 一种基于多gpu的浅积云对流参数化方案异构计算方法
CN106598552A (zh) 基于Gridding模块的数据点转换方法及装置
CN104156268B (zh) 一种GPU上MapReduce的负载分配和线程结构优化方法
Zhou et al. A Parallel Scheme for Large‐scale Polygon Rasterization on CUDA‐enabled GPUs
CN109558817A (zh) 一种基于fpga加速的机场跑道检测方法

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant