科创中国

本发明涉及并行计算应用技术领域和高性能科学计算领域，特别是涉及一种具备TB级数据处理能力的CT切片数据可视化重构的八叉树并行构造方法。其基于MPI+OpenMP并行编程模型，利用原始体数据网格剖分、八叉树节点数据没有依赖性等特点，基于“按需构造‑Branch on need Octrees，BONOs”方案，根据体数据的实际三维尺寸进行八叉树并行构造。

一种CT切片数据可视化重构的八叉树并行构造方法，其具备TB级数据规模处理能力，该方法包括以下步骤：A、按照CT切片数据组合而成的原始体数据尺寸X、Y和Z，树节点设定尺寸为x、y和z，计算获得X方向、Y方向和Z方向的剖分网格数目NX、NY和NZ，得到体数据的剖分网格数目N＝NX*NY*NZ，按照该数目构造一份线性满八叉树的索引列表，剖分网格即代表八叉树的叶子节点；B、完成索引列表各个属性字段填充，包括八叉树属性字段和树节点属性字段，按照按需构造-BONOs原则，根据实际存在的体数据进行划分：若节点内包含实际存在的体数据，则该节点被标识为存在，若节点只包含扩充的体数据，则该节点被标识为不存在；C、根据原始体数据尺寸X、Y和Z，以及设定的节点分辨率尺寸x、y和z，进行体数据预取操作，将Z方向的z个CT切片数据文件预取至所有计算节点内存中；D、将预取至内存的体数据子块，即其三维尺寸为X、Y和Z的体数据子块，在XOY平面进行X和Y方向进行等分，X方向划分，Y方向划分，将该体数据块划分为(X/x)*(Y/y)个叶子节点；E、基于MPI+OpenMP编程模型，执行叶子节点数据并行转换操作，由PN个MPI进程将N个叶子节点进行并行转换，每个进程内部启动OpenMP多线程完成数据重排，使得切片文件数据转换为八叉树叶子节点数据格式，并存储为自定义二进制文件，将该转换操作迭代执行多次，完成整个体数据由CT切片数据格式向叶子节点二进制数据格式的转换操作；F、根据线性满八叉树索引列表属性信息和MPI+OpenMP编程模型，从叶子节点所在层位开始进行自底向上八叉树并行构造，逐层向上合并构造中间节点，并将构造结果存储为自定义文件，存储路径保存至索引表中；G、完成整棵八叉树构造，获得线性满八叉树索引列表和八叉树节点数据文件，满足体数据三维可视化重构目的。

在图形图像处理应用领域中，三维可视化技术是描绘和理解三维模型的一种重要工具，而八叉树是一种用于描述三维空间的树状数据结构，其数据结构是三维可视化技术广泛应用的重要数据结构之一。科学计算领域中常用的并行编程框架包括MPI(消息传递接口)、OpenMP、CUDA等。MPI主要用于实现多进程协作的并行程序设计。由于不同进程具有独立的地址空间和资源，因此需要采用MPI提供的消息传递接口来实现进程间的相互通信。在使用MPI实现八叉树并行构造算法时，通常会对计算网格进行区域划分，不同的进程负责不同区域的计算，完成计算之后将数据存储至自定义文件中。OpenMP是一种用于共享内存的并行系统的多处理器程序设计的编译处理方案。在OpenMP的程序中，多个线程协同工作来完成计算任务，线程之间共享所在进程的内存空间，因此，线程间不需要额外的通信来交换数据。但是OpenMP不能实现跨节点并行，而且，在线程数目很大的情况下，不能实现良好的并行效率。随着数据处理规模的迅速激增，和处理时效性需求不断增加，三维可视化技术已经越来越多地利用高性能计算应用技术和并行计算应用技术来解决面临的例如单机无法处理，或处理时间无法接受，或处理效果不好等问题和挑战。八叉树构造算法是一个非常重要的应用基础算法，针对其优势和特点，结合目前数据规模逐渐达到TB级、甚至PB级，应用时效性要求高的实际情况，研究八叉树的并行构造方法有重要的实际意义和迫切的应用需求。本专利能解决以上问题。

本发明专利由国家超级计算天津中心核心团队研究开发完成。国家超级计算天津中心是由科技部2009年批准成立的首家国家级超级计算中心，现部署有中国首台计算速度世界第一的“天河一号”超级计算机和天河新一代超级计算机系统。同时，天津超算中心获批组建了首个国地联合大数据工程实验室，入围首批国家“中国制造2025”工业云示范平台、工业大数据试点示范基地，成功揭榜工信部“新一代人工智能产业创新平台”，成为我国超级计算与云计算、大数据、人工智能创新与应用转化的重大载体，引领了中国“计算驱动创新”的新阶段。

一方面减少构造过程中对计算资源、存储资源的浪费和I/O开销，另一方面通过并行计算的方式实现对TB级CT切片数据的快速八叉树数据结构构造，MPI+OpenMP并行编程技术满足TB级CT切片数据在不同分辨率要求下的八叉树数据结构体快速构造，该方法具备较好的并行加速比和并行效率。

该成果拟通过技术开发、技术许可等方式进行成果转化。