用于处理非结构化网格数据的方法、装置、设备和介质

摘要

一种用于处理非结构化网格数据的方法、装置、设备和介质。该方法包括：获取待处理网格数据，其中，待处理网格数据包括多个元素；基于数据分块尺寸，对待处理网格数据进行分块，以得到至少一个数据块，其中，数据分块尺寸是根据计算设备的处理器缓存的容量确定的，并且数据分块尺寸小于处理器缓存的容量，并且其中，至少一个数据块中的每一个数据块包括多个块内元素，多个块内元素为多个元素中的至少一部分元素；在至少一个数据块中确定待处理数据块；以及将待处理数据块加载到处理器缓存中，其中，在对待处理数据块的处理完成前，待处理数据块所包括的多个块内元素全部被保留在处理器缓存中。

说明书

技术领域

本公开涉及计算机领域，特别是涉及一种用于处理非结构化网格数据的方法、装置、电子设备、非瞬时计算机可读存储介质和计算机程序产品。

背景技术

网格(Mesh)是一种用于数据离散化的常用格式。依据网格的形状，我们通常可以把网格分为结构化网格(Structured Mesh)和非结构化网格(Unstructured Mesh)。结构化网格指的是网格内所有的内部点都拥有完全相同的形状，常见的结构化网格包含四边形(二维)和六面体网格(三维)。这种网格的数值特性优秀，数据访问也简单。但是这种网格通常只能被用来表示规则的图形。对于结构非规则的图形，结构化网格很难精确描述其表面结构。与结构化网格相反，非结构化网格的内部点可以拥有不同的网格形状，可以精确表示大部分的非规则图形。由于非结构化网格在表达能力上的优越性，其被广泛地使用于有限元仿真和几何处理等视觉计算应用之中。顾名思义，非结构化网格没有规则的拓扑关系，其拓扑关系一般需要被显式维持。

在此部分中描述的方法不一定是之前已经设想到或采用的方法。除非另有指明，否则不应假定此部分中描述的任何方法仅因其包括在此部分中就被认为是现有技术。类似地，除非另有指明，否则此部分中提及的问题不应认为在任何现有技术中已被公认。

发明内容

提供一种缓解、减轻或甚至消除上述问题中的一个或多个的机制将是有利的。

根据本公开的一方面，提供了一种用于处理非结构化网格数据的方法，包括：获取待处理网格数据，其中，待处理网格数据包括多个元素；基于数据分块尺寸，对待处理网格数据进行分块，以得到至少一个数据块，其中，数据分块尺寸是根据计算设备的处理器缓存的容量确定的，并且数据分块尺寸小于处理器缓存的容量，并且其中，至少一个数据块中的每一个数据块包括多个块内元素，多个块内元素为多个元素中的至少一部分元素；在至少一个数据块中确定待处理数据块；以及将待处理数据块加载到处理器缓存中，其中，在对待处理数据块的处理完成前，待处理数据块所包括的多个块内元素全部被保留在处理器缓存中。

根据本公开的另一方面，提供了一种用于处理非结构化网格数据的装置，包括：获取模块，被配置为获取待处理网格数据，其中，待处理网格数据包括多个元素；分块模块，被配置为基于数据分块尺寸，对待处理网格数据进行分块，以得到至少一个数据块，其中，数据分块尺寸是根据计算设备的处理器缓存的容量确定的，并且数据分块尺寸小于处理器缓存的容量，并且其中，至少一个数据块中的每一个数据块包括多个块内元素，多个块内元素为多个元素中的至少一部分元素；第一确定模块，被配置为在至少一个数据块中确定待处理数据块；以及加载模块，被配置为将待处理数据块加载到处理器缓存中，其中，在对待处理数据块的处理完成前，待处理数据块所包括的多个块内元素全部被保留在处理器缓存中。

根据本公开的又另一方面，提供了一种电子设备，包括：至少一个处理器，其中，至少一个处理器中的每一个处理器包括：处理器缓存；以及与至少一个处理器通信连接的存储器，其中存储器存储有可被至少一个处理器执行的指令，指令被至少一个处理器执行，以使至少一个处理器能够执行上述用于处理非结构化网格数据的方法。

根据本公开的再另一方面，提供了一种存储有计算机指令的非瞬时计算机可读存储介质，其中，计算机指令用于使计算机执行上述用于处理非结构化网格数据的方法。

根据本公开的再另一方面，提供了一种计算机程序产品，包括计算机程序，其中，计算机程序在被处理器执行时实现用于处理非结构化网格数据的方法。

根据本公开的一个或多个实施例，通过基于根据计算设备的处理器缓存的容量所确定的分块尺寸对待处理的非结构化网格数据进行分块，能够得到至少一个数据块。这些数据块中的每一个的具有不大于处理器缓存容量的尺寸，并且包括多个块内元素(例如，待处理网格中的点、边、面、或更高维度的元素诸如四面体)。在得到这些数据块之后，可以在其中确定待处理数据块，进而将其加载在处理器缓存中并在待处理数据块处理完成前将其保留在处理器缓存中，使得在对待处理数据块的处理过程中，可以直接从处理器缓存中读取到块内元素，避免待处理数据块中的块内元素被缓存释放后需要从内存乃至数据存储单元中重新进行读取和加载所带来的额外耗时。由此，能够最大化利用处理器缓存，提升缓存利用率，同时减少对内存的读写开销，提高对非结构化网格数据的处理效率。

根据在下文中所描述的实施例，本公开的这些和其它方面将是清楚明白的，并且将参考在下文中所描述的实施例而被阐明。

附图说明

在下面结合附图对于示例性实施例的描述中，本公开的更多细节、特征和优点被公开。所示出的实施例仅出于例示的目的，并不限制权利要求的范围。在所有附图中，相同的附图标记指代类似但不一定相同的要素。

图1是图示出根据示例性实施例的用于处理非结构化网格数据的方法的流程图；

图2是图示出根据示例性实施例的对待处理网格数据进行分块的流程图；

图3是图示出根据示例性实施例的待执行指令的示意图；

图4是图示出根据示例性实施例的用于处理非结构化网格数据的方法的流程图；

图5是图示出根据示例性实施例的用于处理非结构化网格数据的方法的流程图；

图6是图示出根据示例性实施例的用于处理非结构化网格数据的方法的流程图；

图7是图示出根据示例性实施例的用于处理非结构化网格数据的装置的示意性框图；

图8是图示出根据示例性实施例的分块模块的示意性框图；

图9是图示出根据示例性实施例的用于处理非结构化网格数据的装置的示意性框图；

图10是图示出根据示例性实施例的用于处理非结构化网格数据的装置的示意性框图；

图11是图示出根据示例性实施例的用于处理非结构化网格数据的装置的示意性框图；并且

图12是图示出能够应用于示例性实施例的示例性计算机设备的框图。

具体实施方式

以下结合附图对本公开的示范性实施例做出说明，其中包括本公开实施例的各种细节以助于理解，应当将它们认为仅仅是示范性的。因此，本领域普通技术人员应当认识到，可以对这里描述的实施例做出各种改变和修改，而不会背离本公开的范围。同样，为了清楚和简明，以下的描述中省略了对公知功能和结构的描述。

在本公开中，除非另有说明，否则使用术语“第一”、“第二”等来描述各种要素不意图限定这些要素的位置关系、时序关系或重要性关系，这种术语只是用于将一个元件与另一元件区分开。在一些示例中，第一要素和第二要素可以指向该要素的同一实例，而在某些情况下，基于上下文的描述，它们也可以指代不同实例。

在本公开中对各种所述示例的描述中所使用的术语只是为了描述特定示例的目的，而并非旨在进行限制。除非上下文另外明确地表明，如果不特意限定要素的数量，则该要素可以是一个也可以是多个。如本文使用的，术语“多个”意指两个或更多，并且术语“基于”应解释为“至少部分地基于”。此外，术语“和/或”以及“……中的至少一个”涵盖所列出的项目中的任何一个以及全部可能的组合方式。

下面结合附图详细描述本公开的示例性实施例。

图1是图示出根据示例性实施例的用于处理非结构化网格数据的方法100的流程图。

参考图1，在步骤102，获取待处理网格数据。

根据一些实施例，待处理网格数据可以用于描述非结构化的待处理网格。待处理网格可以表示特定二维、三维、或其他维度的物体的拓扑和几何结构。待处理网格是由多个具有特定维度的多个网格元素(Mesh element)构成的，而待处理网格数据中包括与这些网格元素一一对应的多个元素数据。常见的网格元素包括零维元素、一维元素、二维元素和三维元素，分别对应点(Vertex)、边(Edge)、面(Face)和体(Cell)。

为便于表述，本公开中的“元素”既可以指代网格元素，也可以指代与网格元素对应的元素数据，并且相应地，在“元素”指代元素数据时，“元素”的维度可以指代与该元素数据对应的网格元素的维度，在此不做限定。

根据一些实施例，待处理网格数据所包括的多个元素可以具有相同的维度。在一个示例性实施例中，描述二维待处理网格的待处理网格数据可以仅包括二维元素。在另一个示例性实施例中，描述三维待处理网格的待处理网格数据可以仅包括三维元素。可以理解的是，也可以使用低维度的元素描述高维度的待处理网格，例如仅使用二维元素描述三维待处理网格，在此不做限定。

根据一些实施例，待处理网格数据所包括的多个元素也可以具有不同的维度。在一些实施例中，对于任何满足0≤n≤N的任意整数n，多个元素包括多个n维元素，N为预设的不小于2的整数。也就是说，多个元素中包括多个点、多个边、多个面。在N大于2的实施例中，多个元素还可以包括更高维的元素，例如多个体，在此不做限定。

根据一些实施例，多个元素中的每一个k维元素包括k+1个k-1维元素，k为满足0＜k≤N的任意整数。换句话说，每一个边包括两个点，每一个面包括三个边，以及可选择地，每一个体包括四个面。需要注意的是，每一个k维元素所包括的k+1个k-1维元素限定了该k维元素的边界，即每一个边所包括的两个点为相应的边的两个端点，每一个面所包括的三个边为形成相应的面的三个边，以此类推。在这样的实施例中，每一个面为三角形，以及可选择地，每一个体为四面体(Tetrahedron)。

根据一些实施例，每一个k维元素可以进一步包括更低维的元素。在一些示例性实施例中，每一个面可以进一步包括由该面所包括三个边所共享的三个点，以及可选择的，每一个体可以进一步包括由该体所包括的四个面所共享的六个边和由这六个边共享的四个点。可以理解的是，在N大于3的实施例中，上述内容对于更高维的元素同样成立，在此不做限定。通过这样的方式，每个元素包括恒定数量的更低维度的元素，这在数据存储与处理时具有优势，而通过将每个元素所包括的元素均存储在待处理网格数据中，能够提升对待处理数据进行处理的效率。

根据一些实施例，上述N可以设定为3，即待处理网格数据所包括的多个元素包括多个三维元素。由此，通过使用本公开的方法能够对“体”上的信息进行三维物体仿真。为便于表述，本公开的实施例中以N设定为3作为示例，但这样的示例仅为示例性的，本领域技术人员可以将本公开的方法应用于任何将N设定为不小于2的整数的情景中，这样的适应性应用在本公开的保护范围内。

根据一些实施例，元素之间可以具有相邻关系。针对多个元素中的不同的两个元素，当以下条件中的任一项得到满足时，这两个元素可以互为邻居：

条件A、这两个元素的维度均为k，并且这两个元素均包括同一个k-1维元素，其中，k为整数且满足0＜k≤N；

条件B、这两个元素之间具有完全包含关系；以及

条件C、这两个元素为多个元素中的一个1维元素所包括的两个0维元素。

在一个弹簧质点系统示例中，共享一个端点(零维元素)的两个弹簧(一维元素)为邻居；一个弹簧所包括的两个端点均为该弹簧的邻居，并且这两个端点互为邻居；连接到一个端点的所有弹簧均为该端点的邻居。

在步骤104，基于数据分块尺寸，对待处理网格数据进行分块，以得到至少一个数据块。

根据一些实施例，数据分块尺寸是根据计算设备的处理器缓存的容量确定的，并且数据分块尺寸小于处理器缓存的容量。需要注意的是，本公开并不限定计算设备的处理器类型。在一些实施例中，可以使用中央处理器(Central Processing Unit,CPU)执行对待处理网格数据的处理，则处理器缓存可以为CPU中的上层缓存，例如L1缓存、L2缓存等。在另一些实施例中，可以使用图形处理器(Graphics Processing Unit,GPU)执行对待处理网格数据的处理，则处理器缓存可以为GPU中的共享内存。

在一些处理器中，处理器缓存的容量也可以在一定范围内进行调整。在一个示例中，在CUDA(Compute Unified Device Architecture，统一计算设备架构)后台存在数据分块尺寸和线程块(即，后文所描述的处理器中的处理单元)数量之间的权衡。更大处理器缓存可以容纳下更大的数据块，从而提升数据局部性。然而，在如后文所描述的包括多个处理单元的处理器中，提升每一个处理单元的处理器缓存的容量会降低处理单元的数量，并且降低对待处理网格数据进行处理的并发性，如下文将要描述的。可以理解的是，在一些其他处理器中，也存在类似的情况。在一个示例性实施例中，可以根据待执行指令对所需要进行缓存的数据量进行评估，进而确定处理器缓存的容量和数据分块尺寸中的至少一个。

根据一些实施例，数据分块尺寸可以根据待执行指令确定。在一些实施例中，用户可以通过指令指定或修改数据分块尺寸的值。在一些实施例中，针对特定的处理器(例如，特定的GPU)，可以向用户提供一些默认的数据分块尺寸的值，用户可以在这些默认值中确定数据分块尺寸。

根据一些实施例，对待处理网格数据进行分块而得到的每一个数据块可以包括待处理网格数据中的至少一部分元素，这些元素可以被称为相应的数据块的块内元素(ownedelement)。对待处理网格数据进行分块例如可以是基于待处理网格的结构进行的。在一些实施例中，多个块内元素中的每一个块内元素可以和多个块内元素中的其他元素中的至少一个元素相邻。换句话说，每一个数据块都是待处理网格的一个连续子集。通过这样的方式，在对待处理数据进行处理时，同一数据块内的元素数据和元素间关系能够以更好的数据局部性被频繁读取，从而提升数据处理的速度。

根据一些实施例，对待处理网格数据进行分块而得到的每一个数据块可以不大于数据分块尺寸，并且可以尽可能的接近数据分块尺寸，以实现对处理器缓存的充分利用。这些数据块之间可以具有较小的方差，以进一步实现对处理器缓存的充分利用，并且更小的方差使得能够以更高的效率对这些数据块进行并行处理，如下文将要描述的。

可以理解的是，本领域技术人员可以使用任意分块算法或根据需求自行设计分块算法，以对待处理网格数据进行分块，在此不做限定。

根据一些实施例，对待处理网格数据进行分块时，可以先对待处理网格数据所包括的最高维度的元素进行分块，再将这些最高维度的元素的所包括的较低维度的元素添加到对应的最高维度的元素所在的数据块中。在一些实施例中，通过分块得到的至少一个数据块中的任意两个数据块可以不包含相同的块内元素，即待处理数据块所包括的每一个元素可以仅属于一个数据块。在一个示例性实施例中，可以为每一个最高维度的元素唯一地分配一个数据块，而当一个较低维度的元素由多个不同的数据块中的较高维度的元素共享时，可以在这些数据块中为该较低维度的元素随机分配一个数据块。

根据一些实施例，每一个元素在待处理网格数据中可以具有唯一的全局索引。将待处理网格数据被转换为多个数据块后，为进一步提升数据局部性，数据块内的元素可以以连续的方式被缓存。因此，可以对数据块内的元素进行局部索引，以对缓存了的数据块的连续数据进行读取。根据一些实施例，如图2所示，步骤104，对待处理网格数据进行分块可以包括：步骤202，针对至少一个数据块中的每一个数据块，为该数据块所包括的多个块内元素中的每一个块内元素确定局部索引；以及步骤204，确定多个块内元素各自的局部索引与多个块内元素各自在待处理网格数据中的全局索引之间的索引映射关系。

在获取数据块中位于边缘的块内元素的相关数据时，有很大概率需要访问其他数据块中的元素，因此确定数据块的邻域元素(ribbon element)可以在对数据块进行处理时提供便利，如下文将要描述的。

根据一些实施例，步骤104，对待处理网格数据进行分块还可以包括：步骤206，针对至少一个数据块中的每一个数据块，将与该数据块所包括的多个块内元素中的每一个块内元素相邻且不属于该数据块的元素确定为该数据块的邻域元素。这样的邻域元素可以被视为数据块的一环邻居。在一些实施例中，还可以将块内元素的二环邻居(即，块内元素的邻居的邻居)或更高环的邻居确定为对应的数据块的邻域元素，在此不作限定。可以理解的是，每一个元素作为块内元素可以仅属于一个数据块，但作为邻域元素可能属于多个不同的数据块，因此，可以将一个元素作为块内元素时所在的数据块确定为该元素所在的数据块。

根据一些实施例，可以采用使每一个数据块具有更少的邻域元素的分块方式。邻域元素越少，数据块中的块内元素的占比就越高，对缓存的利用率也就越高。

根据一些实施例，为进一步提升数据局部性，可以对数据块的邻域元素进行局部索引。根据一些实施例，步骤104，对待处理网格数据进行分块还可以包括：步骤208，针对至少一个数据块中的每一个数据块，为该数据块的邻域元素确定局部索引；以及步骤210，确定邻域元素的局部索引与邻域元素在待处理网格数据中的全局索引之间的索引映射关系。由此，数据块内的块内元素和邻域元素均具备了局部索引。

根据一些实施例，可以对块内元素和邻域元素的局部索引进行区分。在一些实施例中，在确定块内元素和邻域元素的索引时，可以将较小值的索引分配给块内元素，将较大值的索引分配给邻域元素。在一个示例性实施例中，可以使用“num_owned”和“num_total”两个变量来监控每个数据块中的块内元素和邻域元素的数量，并且可以使用这两个变量判断某个元素是否为对应的数据块中的块内元素或邻域元素。

在步骤106，在至少一个数据块中确定待处理数据块。

根据一些实施例，确定待处理数据块例如可以是基于待执行指令确定的。待执行指令可以是由用户输入的指令，也可以是由机器生成的指令，还可以是存储在存储介质中的指令，在此不做限定。在一些实施例中，可以将待执行指令所指示的元素数据所在的数据块作为待处理数据块。

根据一些实施例，步骤106，在至少一个数据块中确定待处理数据块可以包括：响应于接收到查询循环指令，将查询循环指令所查询的目标元素所在的数据块确定为待处理数据块。查询循环指令例如用于查询满足预设条件的目标元素，并且用于指示对于目标元素执行与查询循环指令对应的数据处理指令。查询循环指令与Taichi编程语言(例如，Taichi 0.8.0版本)中用于遍历体素(Voxel)的结构-for(struct-for)循环以及对索引的范围-for(range-for)循环类似，并且可以对满足特定预设条件的网格元素进行查询，因此也可以称作网格-for(mesh-for)循环。预设条件可以从查询循环指令中读取，通常用于指示与特定的元素、网格具有相邻、包含或其他关系的一系列目标元素，这些目标元素通常具有相同的维度，如下文将要描述的。

在一个示例性实施例中，如图3所示的示例待执行指令，第一行为对名为bunny的待处理网格中的所有点进行查询(或，遍历)的查询循环指令。在这个mesh-for中，预设条件通过表述“bunny.vertices”来指示，即bunny中的所有点。第二至七行为与第一行的mesh-for对应的用于对于bunny中的每一个点执行的数据处理指令。具体地，第二行为对相应的点的受力进行运算的指令，第三行为对与连接到点u(第一行的mesh-for所查询到的元素)的所有边进行查询(或，遍历)的查询循环指令。在第三行的mesh-for中，预设条件通过表述“u.edges”来指示，即表示与连接到点u的所有边。第四到七行为与第三行的mesh-for对应的用于对于连接到点u的每一个边执行的数据处理指令。具体地，第四行为对边e(第三行的mesh-for所查找到的元素)的除点u外的另一端点v进行查询的指令，第五行为求点u和点v的坐标的差的指令，第六行为对所得的差进行归一化的指令，第七行为进一步计算点u的受力的指令。

在步骤108，将待处理数据块加载到处理器缓存中。

根据一些实施例，在对待处理数据块的处理完成前，待处理数据块所包括的多个块内元素可以全部被保留在处理器缓存中。在一些实施例中，对待处理数据块的处理完成例如可以是指示对待处理数据块所包括的元素进行数据处理的指令全部执行完成。在执行待执行指令之前，可以先对待执行指令进行分析，以确定需要进行数据处理的待处理数据块，再在待执行指令中确定对待处理数据块或其中的元素进行处理的指令，并在这些处理指令执行结束前将待处理数据块保留在处理器缓存中。可以理解的是，在待执行指令中，对待处理数据块或其中的元素直接进行处理的指令可能不是连续的，因此可以在最后一条处理指令执行结束前将待处理数据块保留在处理器缓存中。在一个示例性实施例中，如图3所示的示例指令中，第五行的指令是对中间运算结果的进一步计算而并没有对待处理数据块或其中的元素直接进行处理，但由于之后的第七行为对待处理数据块中的元素进行处理的指令，因此可以在第七行执行完成前将相应的待处理数据块保留在处理器缓存中。

根据一些实施例，步骤108，将待处理数据块加载到处理器缓存中可以包括：将待处理数据块的邻域元素加载到处理器缓存中。如前文所述，由于在获取数据块中位于边缘的块内元素的相关数据时，有很大概率需要访问邻域元素，因此通过将邻域元素加载并保留在处理器缓存中，使得能够快速访问邻域元素，从而提高对待处理数据块进行处理的效率。

在一个示例性实施例中，在查询循环指令执行结束前，待处理数据块所包括的多个块内元素可以全部被保留在处理器缓存中。在此期间，待处理数据块的邻域元素也可以被保留在处理器缓存中。由于查询循环指令能够用于指示对于目标元素执行与查询循环指令对应的数据处理指令，而在数据处理指令执行期间，通常需要对目标元素及与其有关联的元素进行读取，因此通过将目标元素所在的数据块作为待处理数据块，并在数据处理指令执行结束前将待处理数据块保留在处理器缓存中，能够提升处理器缓存的利用率，避免了待处理数据块中的元素被缓存释放后需要从内存乃至数据存储单元中重新进行读取和加载所带来的额外耗时。

可以理解的是，查询循环指令执行结束可以是对于当前正在处理的目标元素的数据处理指令执行结束，也可以是对于所查询的所有目标元素的数据处理指令执行结束，在此不作限定。

在对待处理网格数据进行处理的过程中，根据数据处理任务的不同，特定的元素间拓扑关系会被频繁访问。这些拓扑关系中，最常被访问的一个或多个关系可以被称为主要关系。通过确定主要关系，可以在待处理网格数据中的多个元素间确定满足主要关系的元素关系，进而可以优化对这些元素关系的读取，从而提升对待处理网格数据进行处理的效率，如下文将要描述的。

参考图4，方法400中的步骤402-步骤408的操作与方法100中的步骤102-步骤108的操作类似，在此不做赘述。

在步骤410，响应于接收到查询循环指令，至少基于查询循环指令所查询的目标元素的维度确定主要关系。

根据一些实施例，主要关系可以指示具有第一维度的第一元素对于与第一元素相邻的具有第二维度的第二元素的关联关系。第一元素可以被称为主要关系的“起始端”(from-end)，第二元素可以被称为主要关系的“到达端”(to-end)。在一些实施例中，例如可以将目标元素的维度作为第一维度，并进一步确定第二维度。在一个示例性实施例中，目标元素为点，则主要关系例如可以为“点-点”关系、“点-边”关系、“点-面”关系和“点-体”关系中的至少一个。在另一些实施例中，例如可以将目标元素的维度作为第二维度，并进一步确定第一维度。在另一个示例性实施例中，目标元素为点，则主要关系例如可以为“点-点”关系、“边-点”关系、“面-点”关系和“体-点”关系中的至少一个。可以理解的是，本领域技术人员还可以通过其他方式基于目标元素的维度确定主要关系，在此不做限定。还需要注意的是，第一维度和第二维度可以相同，也可以不同，在此不作限定。

根据一些实施例，步骤410，确定主要关系可以包括：将目标元素的维度确定为第一维度；以及将数据处理指令中的第一个查询所查询的元素的维度确定为第二维度。通常mesh-for中的第一对拓扑关系(即，mesh-for所查询的目标元素对数据处理指令中的第一个查询所查询的元素的关系)为最常被访问的关系，因此将该关系确定为主要关系能够进一步提升对满足主要关系的元素关系进行读取的优化。

数据查询指令中的第一个查询例如可以是对与目标元素相关的特定元素的查询，通常是对与目标元素相邻的特定元素的查询。在一个示例性实施例中，查询循环指令所查询的目标元素为边e，对应的数据查询指令中的第一个查询可以为“v＝e.vertices[0]”，即对与目标元素e相邻的(即，所包括的)特定点的查询，则主要关系可以确定为“边-点”关系。替代地或附加地，数据查询指令中的第一个查询例如也可以是对与目标元素相关的特定元素的查询循环指令。在另一个示例性实施例中，查询循环指令所查询的目标元素为点u，对应的数据查询指令中的第一个查询可以为查询循环“for e in u.edges”，即对与目标元素u相邻的(即，连接到u的)边的查询(或，遍历)，则主要关系可以确定为“点-边”关系。

根据一些实施例，查询循环指令可以为具有嵌套关系的多个查询循环指令中的最外层的查询循环指令。在一个示例性实施例中，如图3所示的示例指令，第一行的mesh-for和第三行的mesh-for构成嵌套关系，则可以基于最外层的查询循环指令(即，第一行的查询循环指令)确定主要关系并进行相应优化。如前文所描述的，通常最外层的查询循环指令中的第一对拓扑关系为最常被访问的关系，而被嵌套的内层查询循环指令中的拓扑关系相对而言会较少被访问。因此，相比于对所有基于查询循环指令所确定的主要关系进行优化，对基于最外层的查询循环指令所确定的主要关系进行优化可能会更高效。

在步骤412，在多个元素和与多个元素各自相邻的元素之间确定满足主要关系的多个元素关系。

根据一些实施例，步骤412在多个元素和与多个元素各自相邻的元素之间确定满足主要关系的多个元素关系可以包括：在目标元素所在的数据块所包括的多个块内元素和与多个块内元素各自相邻的元素之间确定多个元素关系。在对目标元素所在的待处理数据块进行处理时，对元素和元素间关系的访问在绝大多数情况是在待处理数据块内部进行的。因此通过在待处理数据块内确定元素关系能够降低需要对读取进行优化的元素关系的数量，并且不会对优化效果带来较大影响。

在步骤414，将多个元素关系加载到处理器缓存中。

根据一些实施例，在查询循环指令执行结束前，多个元素关系可以被保留在处理器缓存中。如前文所描述的，通过将这些元素关系保留在处理器缓存中，使得在查询循环指令及其对应的数据处理指令执行期间，这些元素关系能够被快速读取，从而提升了对待处理数据块以及对待处理网格数据的处理速度。

根据一些实施例，除了主要关系外，还可以将mesh-for中的其他关系确定为次要关系，并确定满足次要关系的次要元素关系。次要元素关系也可以被加载并保留在处理器缓存中，但由于次要元素关系被读取的频率相对较低，因此将次要元素关系缓存能够带来的提升有限。在一些实施例中，可以将其作为相应的元素(例如，次要关系中的到达端)的运算数据进行处理，使得当该元素的运算数据被缓存时，该元素作为到达端的次要元素关系也会被缓存。

在对待处理数据块进行处理时，可以根据数据处理指令确定频繁读取的运算数据，并将这些运算数据加载到缓存中，以避免后续从内存或外部数据存储单元读取这些运算数据的严重耗时。

在步骤416，基于数据处理指令，确定与多个元素关系相关联的运算数据。

根据一些实施例，运算数据例如可以为与多个元素关系中的第二元素相关联的运算数据。在一个mesh-for中，主要关系中的第一元素(通常为被查询的元素)可能只被访问一次，而第二元素可能被访问很多次。因此将与第二元素相关联的运算数据进行缓存能够提升数据局部性。可以理解的是，如果第一元素也被访问很多次，那么也可以将与第一元素相关联的运算数据进行缓存，在此不做限定。

在一个示例性实施例中，在主要关系为“点-面”关系时，运算数据例如可以为相应的面的法向。在另一个示例性实施例中，在主要关系为“体-点”关系时，运算数据例如可以为相应的点的位置、速度等。

在步骤418，将运算数据加载到处理器缓存中。

根据一些实施例，在查询循环指令执行结束前，运算数据在处理器缓存中具有高于缺省优先级的第一优先级。缺省优先级可以是一般数据被加载到处理器缓存时所具有的默认优先级。当处理器缓存释放缓存时，低优先级的数据可能被优先释放，因此，在数据处理期间，具有更高优先级的运算数据不太可能被具有缺省优先级的数据从处理器缓存中挤掉。由此，运算数据可以长期缓存在处理器缓存中以供读取。

根据一些实施例，可以在处理器缓存中为需要保留在处理器缓存中的数据分配专用区域，并将需要保留在处理器缓存的数据加载到专用区域中。专用区域也可以供具有缺省优先级的数据使用，但在加载具有更高优先级的数据时，这些具有缺省优先级的数据会被释放。而在专用区域已经全部被需要保留在处理器缓存中的数据占用的情况下，需要被加载并保留在处理器缓存中的新数据可以将处理器缓存中具有相同或更低优先级的数据挤掉。可以理解的是，本领域技术人员可以根据需求设置专用区域的静态容量，或设计动态调整专用区域的方案，也可以采用其他方式处理多种需要加载并保留在处理器缓存中的数据之间、具有缺省优先级的数据和需要加载并保留在处理器缓存中的数据之间的冲突，在此不做限定。

在步骤420，响应于接收到数据处理指令中的数据缓存指令，将数据缓存指令指示的目标数据加载到处理器缓存中。

根据一些实施例，数据缓存指令例如可以是用户输入的指令，用以将指示的目标数据加载到处理器缓存中。根据一些实施例，在查询循环指令执行结束前，目标数据在处理器缓存中具有高于缺省优先级的第二优先级。由此，目标数据可以长期缓存在处理器缓存中以供读取。

根据一些实施例，第二优先级可以高于第一优先级。也就是说，数据缓存指令指示的目标数据具有比根据数据处理指令所确定的运算数据更高的优先级，从而保证的例如用户指定的数据不会被通过其他方式所确定的运算数据而被挤掉。可以理解的是，第二优先级也可以等于第一优先级，或者低于第一优先级，在此不做限定。

参考图5，方法500中的步骤502-步骤516的操作与方法400中的步骤402-步骤416的操作类似，在此不做赘述。

在步骤518，确定运算数据中被进行原子写入操作(atomic write operation)的至少一部分运算数据。

原子操作(atomic operation)为不会被线程调度机制打断的操作，这种操作一旦开始，就一直运行到结束，中间不会切换到其他线程。原子写入操作可以为用于写入数据的原子操作。根据一些实施例，原子写入操作例如可以包括“+＝”，即将“+＝”右侧的值与左侧的运算数据进行相加，再写入左侧的运算数据中。可以理解的是，原子写入操作还可以包括其他的操作，在此不做限定。

在步骤520，将至少一部分运算数据加载到处理器缓存中。

根据一些实施例，在查询循环指令执行结束前，至少一部分运算数据在处理器缓存中可以具有高于缺省优先级的优先级。被进行原子写入操作的运算数据通常会被频繁访问，因此可以将这些运算数据加载到处理器缓存中，并设置高于缺省优先级的优先级。

根据一些实施例，步骤408，将待处理数据块加载到处理器缓存中可以包括：将多个块内元素各自的索引映射关系加载到处理器缓存中。在对待处理数据块的处理完成前，多个块内元素各自的索引映射关系可以被保留在处理器缓存中。由此，通过将块内元素的索引映射关系加载并保留在处理器缓存中，可以进一步增加数据局部性。在一些实施例中，待处理网格数据中的每一个元素作为块内元素的局部索引和全局索引之间具有唯一对应关系，则元素的全局索引可以被表示为其作为块内元素时在对应的数据块中的局部索引加上偏移量(offset)。因此，可以使用这样的偏移量作为索引映射关系。

根据一些实施例，索引映射关系可以包括局部至全局(local-to-global)索引映射关系，还可以包括全局至局部(global-to-local)索引映射关系。在一个示例性实施例中，可以生成局部至全局索引映射关系和全局至局部索引映射关系两者，并将局部至全局映射关系加载并保留在处理器缓存中。

根据一些实施例，步骤408，将待处理数据块加载到处理器缓存中还可以包括：将待处理数据块的邻域元素的索引映射关系加载到处理器缓存中，其中，在对待处理数据块的处理完成前，待处理数据块的邻域元素的索引映射关系被保留在处理器缓存中。由此，通过将邻域元素的索引映射关系加载并保留在处理器缓存中，可以进一步增加数据局部性。

根据一些实施例，前文描述的包括待处理数据块、多个元素关系、运算数据、目标数据、待处理数据块所包括的多个块内元素各自的索引映射关系、待处理数据块的邻域元素、以及待处理数据块的邻域元素的索引映射关系的数据量总和可以小于处理器缓存的容量。在一些实施例中，处理器缓存中为这些数据分配有专用区域，则这些数据的总数据量可以小于专用区域的容量。

综上所述，通过基于根据计算设备的处理器缓存的容量所确定的分块尺寸对待处理的非结构化网格数据进行分块，能够得到至少一个数据块。这些数据块中的每一个的具有不大于处理器缓存容量的尺寸，并且包括多个块内元素(例如，待处理网格中的点、边、面、或更高维度的元素诸如四面体)。在得到这些数据块之后，可以在其中确定待处理数据块，进而将其加载在处理器缓存中并在待处理数据块处理完成前将其保留在处理器缓存中，使得在对待处理数据块的处理过程中，可以直接从处理器缓存中读取到块内元素，避免待处理数据块中的块内元素被缓存释放后需要从内存乃至数据存储单元中重新进行读取和加载所带来的额外耗时。由此，能够最大化利用处理器缓存，提升缓存利用率，同时减少对内存的读写开销，提高对非结构化网格数据的处理效率。

如前文所述，各种类型的处理器均可以用于执行对待处理网格数据的处理，而这些处理器(例如，CPU、GPU等)中的每一个可能包括多个处理单元，并且包括与这些处理单元对应的多个处理单元缓存。在一个示例性实施例中，处理器为GPU，包括多个线程块(Block)(即，处理单元)，每一个线程块包括由多个线程(Thread)共用的共享内存(Shared Memory)(即，处理单元缓存)。

本公开对利用这样的具有多个处理单元的处理器执行对待处理网格数据的处理进行了进一步优化，实现了对查询循环指令的并行执行，如下文将要描述的。

根据一些实施例，数据分块尺寸可以小于处理单元缓存的容量，使得数据块可以被完整加载到处理单元缓存中。可以理解的是，前文对处理器缓存的描述可以直接应用于处理单元缓存，例如相应的元素关系、运算数据、目标数据等可以加载到相应的处理单元缓存中，这些需要被加载并保留在处理器缓存上的数据可以被加载并保留在相应的处理单元缓存中等等，在此不做赘述。

根据一些实施例，查询循环指令可以查询到多个目标元素，并且多个目标元素可以属于至少一个待处理数据块。在一个示例性实施例中，多个目标元素中的部分目标元素可能属于同一个待处理数据块。在另一个示例性实施例中，多个目标元素分别属于多个待处理数据块。

根据一些实施例，至少一个待处理数据块中的每一个待处理数据块可以被唯一地加载到至少一个处理单元中的一个处理单元缓存中。由此，同一个待处理数据块不会被加载到多个处理单元的处理单元缓存中，从而节省了缓存空间。

参考图6，方法600中的步骤602-步骤608的操作与方法100中的步骤102-步骤108的操作类似，在此不做赘述。

根据一些实施例，步骤608，将待处理数据块加载到处理器缓存中可以包括：将至少一个待处理数据块加载到多个处理单元缓存中的至少一个处理单元缓存中。

在步骤610，利用与至少一个处理单元缓存对应的至少一个处理单元，并行执行查询循环指令。

由此，通过将至少一个待处理数据块加载到至少一个处理单元缓存中，使得每一个处理单元在对相应的待处理数据块进行处理时，能够从相应的处理单元缓存快速读取相应的待处理数据块中的块内元素，从而实现了对至少一个待处理数据块的并行处理，并且能够利用处理单元缓存对每一个待处理数据块的处理进行加速。

并利用与至少一个处理单元缓存对应的至少一个处理单元中的每一个处理单元对于相应的待处理数据块中的目标元素执行与查询循环指令对应的数据处理指令，实现了对查询循环指令的并行执行，提升了对待处理网格数据的处理效率。

根据一些实施例，步骤610，并行执行查询循环指令可以包括：针对至少一个处理单元中的每一个处理单元，利用该处理单元对于多个目标元素中的至少一部分目标元素执行数据处理指令。至少一部分目标元素可以为该处理单元对应的处理单元缓存中加载的待处理数据块所包括的目标元素。

由此，通过利用处理单元对于对应的处理单元缓存中加载的待处理数据块中的每一个目标元素执行数据处理指令，使得在对于待处理数据块所包括的多个目标元素执行数据处理指令期间，只需要将待处理数据块加载到处理单元缓存中一次，从而进一步提升了缓存利用率，并降低了将数据块频繁写入缓存所带来的耗时。

由于至少一个处理单元需要并行处理每一个待处理数据块中的目标元素，假定每一个待处理数据块中目标元素的占比相近，那么不同的待处理数据块的尺寸的方差越小，对至少一个待处理数据块的总处理时间越短。因此，在对待处理网格数据进行分块时，可以尽可能降低数据块之间的方差大小，以提升对待处理网格数据进行处理的效率。

根据一些实施例，步骤610，并行执行查询循环指令还可以包括：利用该处理单元所包括的多个线程对于相应的待处理数据块中的目标元素并行执行数据处理指令。

由此，通过利用处理单元内的多个线程对于待处理数据块中的目标元素并行执行数据处理指令，能够进一步提升对待处理数据块以及对待处理网格数据的处理效率。

图7是图示出根据示例性实施例的用于处理非结构化网格数据的装置700的示意性框图。参考图7，装置700包括：获取模块702，被配置为获取待处理网格数据，其中，待处理网格数据包括多个元素；分块模块704，被配置为基于数据分块尺寸，对待处理网格数据进行分块，以得到至少一个数据块，其中，数据分块尺寸是根据计算设备的处理器缓存的容量确定的，并且数据分块尺寸小于处理器缓存的容量，并且其中，至少一个数据块中的每一个数据块包括多个块内元素，多个块内元素为多个元素中的至少一部分元素；第一确定模块706，被配置为在至少一个数据块中确定待处理数据块；以及加载模块708，被配置为将待处理数据块加载到处理器缓存中，其中，在对待处理数据块的处理完成前，待处理数据块所包括的多个块内元素全部被保留在处理器缓存中。

由此，通过基于根据计算设备的处理器缓存的容量所确定的分块尺寸对待处理的非结构化网格数据进行分块，能够得到至少一个数据块。这些数据块中的每一个的具有不大于处理器缓存容量的尺寸，并且包括多个块内元素(例如，待处理网格中的点、边、面、或更高维度的元素诸如四面体)。在得到这些数据块之后，可以在其中确定待处理数据块，进而将其加载在处理器缓存中并在待处理数据块处理完成前将其保留在处理器缓存中，使得在对待处理数据块的处理过程中，可以直接从处理器缓存中读取到块内元素，避免待处理数据块中的块内元素被缓存释放后需要从内存乃至数据存储单元中重新进行读取和加载所带来的额外耗时。由此，能够最大化利用处理器缓存，提升缓存利用率，同时减少对内存的读写开销，提高对非结构化网格数据的处理效率。

根据一些实施例，对待处理网格数据进行分块而得到的每一个数据块可以包括待处理网格数据中的至少一部分元素，这些元素可以被称为相应的数据块的块内元素(ownedelement)。对待处理网格数据进行分块例如可以是基于待处理网格的结构进行的。在一些实施例中，多个块内元素中的每一个块内元素可以和多个块内元素中的其他元素中的至少一个元素相邻。换句话说，每一个数据块都是待处理网格的一个连续子集。通过这样的方式，在对待处理数据进行处理时，同一数据块内的元素数据和元素间关系能够以更好的数据局部性被频繁读取，从而提升数据处理的速度。

根据一些实施例，对待处理网格数据进行分块而得到的每一个数据块可以不大于数据分块尺寸，并且可以尽可能的接近数据分块尺寸，以实现对处理器缓存的充分利用。这些数据块之间可以具有较小的方差，以进一步实现对处理器缓存的充分利用，并且更小的方差使得能够以更高的效率对这些数据块进行并行处理，如下文将要描述的。

可以理解的是，本领域技术人员可以使用任意分块算法或根据需求自行设计分块算法，以对待处理网格数据进行分块，在此不做限定。

根据一些实施例，对待处理网格数据进行分块时，可以先对待处理网格数据所包括的最高维度的元素进行分块，再将这些最高维度的元素的所包括的较低维度的元素添加到对应的最高维度的元素所在的数据块中。在一些实施例中，通过分块得到的至少一个数据块中的任意两个数据块可以不包含相同的块内元素，即待处理数据块所包括的每一个元素可以仅属于一个数据块。在一个示例性实施例中，可以为每一个最高维度的元素唯一地分配一个数据块，而当一个较低维度的元素由多个不同的数据块中的较高维度的元素共享时，可以在这些数据块中为该较低维度的元素随机分配一个数据块。

根据一些实施例，每一个元素在待处理网格数据中可以具有唯一的全局索引。将待处理网格数据被转换为多个数据块后，为进一步提升数据局部性，数据块内的元素可以以连续的方式被缓存。因此，可以对数据块内的元素进行局部索引，以对缓存了的数据块的连续数据进行读取。根据一些实施例，如图8所示，分块模块800可以包括：第一局部索引子模块802，被配置为针对至少一个数据块中的每一个数据块，为该数据块所包括的多个块内元素中的每一个块内元素确定局部索引；以及第一映射生成子模块804，被配置为确定多个块内元素各自的局部索引与多个块内元素各自在待处理网格数据中的全局索引之间的索引映射关系。可以理解的是，图8中分类模块800的操作与图7中的分类模块704的操作类似，在此不做赘述。

在获取数据块中位于边缘的块内元素的相关数据时，有很大概率需要访问其他数据块中的元素，因此确定数据块的邻域元素(ribbon element)可以在对数据块进行处理时提供便利，如下文将要描述的。根据一些实施例，分块模块800还可以包括：邻域确定子模块806，被配置为针对至少一个数据块中的每一个数据块，将与该数据块所包括的多个块内元素中的每一个块内元素相邻且不属于该数据块的元素确定为该数据块的邻域元素。这样的邻域元素可以被视为数据块的一环邻居。在一些实施例中，还可以将块内元素的二环邻居(即，块内元素的邻居的邻居)或更高环的邻居确定为对应的数据块的邻域元素，在此不作限定。可以理解的是，每一个元素作为块内元素可以仅属于一个数据块，但作为邻域元素可能属于多个不同的数据块，因此，可以将一个元素作为块内元素时所在的数据块确定为该元素所在的数据块。

根据一些实施例，可以采用使每一个数据块具有更少的邻域元素的分块方式。邻域元素越少，数据块中的块内元素的占比就越高，对缓存的利用率也就越高。

根据一些实施例，为进一步提升数据局部性，可以对数据块的邻域元素进行局部索引。根据一些实施例，分块模块800还可以包括：第二局部索引子模块808，被配置为针对至少一个数据块中的每一个数据块，为该数据块的邻域元素确定局部索引；以及第二映射生成子模块810，被配置为确定邻域元素的局部索引与邻域元素在待处理网格数据中的全局索引之间的索引映射关系。由此，数据块内的块内元素和邻域元素均具备了局部索引。

根据一些实施例，可以对块内元素和邻域元素的局部索引进行区分。在一些实施例中，在确定块内元素和邻域元素的索引时，可以将较小值的索引分配给块内元素，将较大值的索引分配给邻域元素。在一个示例性实施例中，可以使用“num_owned”和“num_total”两个变量来监控每个数据块中的块内元素和邻域元素的数量，并且可以使用这两个变量判断某个元素是否为对应的数据块中的块内元素或邻域元素。

根据一些实施例，确定待处理数据块例如可以是基于待执行指令确定的。待执行指令可以是由用户输入的指令，也可以是由机器生成的指令，还可以是存储在存储介质中的指令，在此不做限定。在一些实施例中，可以将待执行指令所指示的元素数据所在的数据块作为待处理数据块。

根据一些实施例，第一确定模块706可以被进一步配置为：响应于接收到查询循环指令，将查询循环指令所查询的目标元素所在的数据块确定为待处理数据块。查询循环指令例如用于查询满足预设条件的目标元素，并且用于指示对于目标元素执行与查询循环指令对应的数据处理指令。预设条件可以从查询循环指令中读取，通常用于指示与特定的元素、网格具有相邻、包含或其他关系的一系列目标元素，这些目标元素通常具有相同的维度，如下文将要介绍的。

根据一些实施例，在对待处理数据块的处理完成前，待处理数据块所包括的多个块内元素可以全部被保留在处理器缓存中。在一些实施例中，对待处理数据块的处理完成例如可以是指示对待处理数据块所包括的元素进行数据处理的指令全部执行完成。在执行待执行指令之前，可以先对待执行指令进行分析，以确定需要进行数据处理的待处理数据块，再在待执行指令中确定对待处理数据块或其中的元素进行处理的指令，并在这些处理指令执行结束前将待处理数据块保留在处理器缓存中。可以理解的是，在待执行指令中，对待处理数据块或其中的元素直接进行处理的指令可能不是连续的，因此可以在最后一条处理指令执行结束前将待处理数据块保留在处理器缓存中。在一个示例性实施例中，如图3所示的示例指令中，第五行的指令是对中间运算结果的进一步计算而并没有对待处理数据块或其中的元素直接进行处理，但由于之后的第七行为对待处理数据块中的元素进行处理的指令，因此可以在第七行执行完成前将相应的待处理数据块保留在处理器缓存中。

根据一些实施例，加载模块708可以被进一步配置为：将待处理数据块的邻域元素加载到处理器缓存中。如前文所述，由于在获取数据块中位于边缘的块内元素的相关数据时，有很大概率需要访问邻域元素，因此通过将邻域元素加载并保留在处理器缓存中，使得能够快速访问邻域元素，从而提高对待处理数据块进行处理的效率。

在一个示例性实施例中，在查询循环指令执行结束前，待处理数据块所包括的多个块内元素可以全部被保留在处理器缓存中。由于查询循环指令能够用于指示对于目标元素执行与查询循环指令对应的数据处理指令，而在数据处理指令执行期间，通常需要对目标元素及与其有关联的元素进行读取，因此通过将目标元素所在的数据块作为待处理数据块，并在数据处理指令执行结束前将待处理数据块保留在处理器缓存中，能够提升处理器缓存的利用率，避免了待处理数据块中的元素被缓存释放后需要从内存乃至数据存储单元中重新进行读取和加载所带来的额外耗时。

可以理解的是，查询循环指令执行结束可以是对于当前正在处理的目标元素的数据处理指令执行结束，也可以是对于所查询的所有目标元素的数据处理指令执行结束，在此不作限定。

在对待处理网格数据进行处理的过程中，根据数据处理任务的不同，特定的元素间拓扑关系会被频繁访问。这些拓扑关系中，最常被访问的一个或多个关系可以被称为主要关系。通过确定主要关系，可以在待处理网格数据中的多个元素间确定满足主要关系的元素关系，进而可以优化对这些元素关系的读取，从而提升对待处理网格数据进行处理的效率，如下文将要描述的。

参考图9，用于处理非结构化网格数据的装置900中的模块902-模块908的操作与装置700中的模块702-模块708的操作类似，在此不做赘述。

根据一些实施例，如图9所示，装置900还可以包括：第二确定模块910，被配置为响应于接收到查询循环指令，至少基于查询循环指令所查询的目标元素的维度确定主要关系。

根据一些实施例，主要关系可以指示具有第一维度的第一元素对于与第一元素相邻的具有第二维度的第二元素的关联关系。在一些实施例中，例如可以将目标元素的维度作为第一维度，并进一步确定第二维度。在一个示例性实施例中，目标元素为点，则主要关系例如可以为“点-点”关系、“点-边”关系、“点-面”关系和“点-体”关系中的至少一个。在另一些实施例中，例如可以将目标元素的维度作为第二维度，并进一步确定第一维度。在另一个示例性实施例中，目标元素为点，则主要关系例如可以为“点-点”关系、“边-点”关系、“面-点”关系和“体-点”关系中的至少一个。可以理解的是，本领域技术人员还可以通过其他方式基于目标元素的维度确定主要关系，在此不做限定。

根据一些实施例，第二确定模块910可以被进一步配置为：将目标元素的维度确定为第一维度；以及将数据处理指令中的第一个查询所查询的元素的维度确定为第二维度。通常mesh-for中的第一对拓扑关系(即，mesh-for所查询的目标元素对数据处理指令中的第一个查询所查询的元素的关系)为最常被访问的关系，因此将该关系确定为主要关系能够进一步提升对满足主要关系的元素关系进行读取的优化。

数据查询指令中的第一个查询例如可以是对与目标元素相关的特定元素的查询，通常是对与目标元素相邻的特定元素的查询。在一个示例性实施例中，查询循环指令所查询的目标元素为边e，对应的数据查询指令中的第一个查询可以为“v＝e.vertices[0]”，即对与目标元素e相邻的(即，所包括的)特定点的查询。替代地或附加地，数据查询指令中的第一个查询例如可以是对与目标元素相关的特定元素的查询循环指令。在另一个示例性实施例中，查询循环指令所查询的目标元素为点u，对应的数据查询指令中的第一个查询可以为查询循环“for e in u.edges”，即对与目标元素u相邻的(即，连接到u的)边的查询(或，遍历)。

根据一些实施例，查询循环指令可以为具有嵌套关系的多个查询循环指令中的最外层的查询循环指令。如前文所描述的，通常最外层的查询循环指令中的第一对拓扑关系为最常被访问的关系，而被嵌套的内层查询循环指令中的拓扑关系相对而言会较少被访问。因此，相比于对所有基于查询循环指令所确定的主要关系进行优化，对基于最外层的查询循环指令所确定的主要关系进行优化可能会更高效。

根据一些实施例，如图9所示，装置900还可以包括第三确定模块912，被配置为在多个元素和与多个元素各自相邻的元素之间确定满足主要关系的多个元素关系。

根据一些实施例，第三确定模块912可以被进一步配置为：在目标元素所在的数据块所包括的多个块内元素和与多个块内元素各自相邻的元素之间确定多个元素关系。在对目标元素所在的待处理数据块进行处理时，对元素和元素间关系的访问在绝大多数情况是在待处理数据块内部进行的。因此通过在待处理数据块内确定元素关系能够降低需要对读取进行优化的元素关系的数量，并且不会对优化效果带来较大影响。

根据一些实施例，加载模块908可以被进一步配置为将多个元素关系加载到处理器缓存中。

根据一些实施例，在查询循环指令执行结束前，多个元素关系可以被保留在处理器缓存中。如前文所描述的，通过将这些元素关系保留在处理器缓存中，使得在查询循环指令及其对应的数据处理指令执行期间，这些元素关系能够被快速读取，从而提升了对待处理数据块以及对待处理网格数据的处理速度。

在对待处理数据块进行处理时，可以根据数据处理指令确定频繁读取的运算数据，并将这些运算数据加载到缓存中，以避免后续从内存或外部数据存储单元读取这些运算数据的严重耗时。

根据一些实施例，如图9所示，装置900还可以包括第四确定模块914，基于数据处理指令，确定与多个元素关系相关联的运算数据。

根据一些实施例，运算数据例如可以为与多个元素关系中的第二元素相关联的运算数据。在一个mesh-for中，主要关系中的第一元素(通常为被查询的元素)可能只被访问一次，而第二元素可能被访问很多次。因此将与第二元素相关联的运算数据进行缓存能够提升数据局部性。可以理解的是，如果第一元素也被访问很多次，那么也可以将与第一元素相关联的运算数据进行缓存，在此不做限定。

在一个示例性实施例中，在主要关系为“点-面”关系时，运算数据例如可以为相应的面的法向。在另一个示例性实施例中，在主要关系为“体-点”关系时，运算数据例如可以为相应的点的位置、速度等。

根据一些实施例，加载模块908可以被进一步配置为将运算数据加载到处理器缓存中。

根据一些实施例，在查询循环指令执行结束前，运算数据在处理器缓存中具有高于缺省优先级的第一优先级。缺省优先级可以是一般数据被加载到处理器缓存时所具有的默认优先级。当处理器缓存释放缓存时，低优先级的数据可能被优先释放，因此，在数据处理期间，具有更高优先级的运算数据不太可能被具有缺省优先级的数据从处理器缓存中挤掉。由此，运算数据可以长期缓存在处理器缓存中以供读取。

根据一些实施例，可以在处理器缓存中为需要保留在处理器缓存中的数据分配专用区域，并将需要保留在处理器缓存的数据加载到专用区域中。专用区域也可以供具有缺省优先级的数据使用，但在加载具有更高优先级的数据时，这些具有缺省优先级的数据会被释放。而在专用区域已经全部被需要保留在处理器缓存中的数据占用的情况下，需要被加载并保留在处理器缓存中的新数据可以将处理器缓存中具有相同或更低优先级的数据挤掉。可以理解的是，本领域技术人员可以采用其他方式处理多种需要加载并保留在处理器缓存中的数据之间、具有缺省优先级的数据和需要加载并保留在处理器缓存中的数据之间的冲突，在此不做限定。

根据一些实施例，加载模块908可以被进一步配置为响应于接收到数据处理指令中的数据缓存指令，将数据缓存指令指示的目标数据加载到处理器缓存中。

根据一些实施例，数据缓存指令例如可以是用户输入的指令，用以将指示的目标数据加载到处理器缓存中。根据一些实施例，在查询循环指令执行结束前，目标数据在处理器缓存中具有高于缺省优先级的第二优先级。由此，目标数据可以长期缓存在处理器缓存中以供读取。

根据一些实施例，第二优先级可以高于第一优先级。也就是说，数据缓存指令指示的目标数据具有比根据数据处理指令所确定的运算数据更高的优先级，从而保证的例如用户指定的数据不会被通过其他方式所确定的运算数据而被挤掉。可以理解的是，第二优先级也可以等于第一优先级，或者低于第一优先级，在此不做限定。

参考图10，用于处理非结构化网格数据的装置1000中的模块1002-模块1012的操作与装置900中的模块902-模块912的操作类似，在此不做赘述。

根据一些实施例，如图10所示，装置1000还可以包括：第五确定模块1014，被配置为基于数据处理指令，确定与多个元素关系相关联的运算数据；以及第六确定模块1016，被配置为确定运算数据中被进行原子写入操作的至少一部分运算数据。

原子操作(atomic operation)为不会被线程调度机制打断的操作，这种操作一旦开始，就一直运行到结束，中间不会切换到其他线程。原子写入操作可以为用于写入数据的原子操作。根据一些实施例，原子写入操作例如可以包括“+＝”，即将“+＝”右侧的值与左侧的运算数据进行相加，再写入左侧的运算数据中。可以理解的是，原子写入操作还可以包括其他的操作，在此不做限定。

根据一些实施例，加载模块908可以被进一步配置为将至少一部分运算数据加载到处理器缓存中。

根据一些实施例，在查询循环指令执行结束前，至少一部分运算数据在处理器缓存中可以具有高于缺省优先级的优先级。被进行原子写入操作的运算数据通常会被频繁访问，因此可以将这些运算数据加载到处理器缓存中，并设置高于缺省优先级的优先级。

根据一些实施例，加载模块908可以被进一步配置为：将多个块内元素各自的索引映射关系加载到处理器缓存中。在对待处理数据块的处理完成前，多个块内元素各自的索引映射关系可以被保留在处理器缓存中。由此，通过将块内元素的索引映射关系加载并保留在处理器缓存中，可以进一步增加数据局部性。在一些实施例中，待处理网格数据中的每一个元素作为块内元素的局部索引和全局索引之间具有唯一对应关系，则元素的全局索引可以被表示为其作为块内元素时在对应的数据块中的局部索引加上偏移量(offset)。因此，可以使用这样的偏移量作为索引映射关系。

根据一些实施例，索引映射关系可以包括局部至全局(local-to-global)索引映射关系，还可以包括全局至局部(global-to-local)索引映射关系。在一个示例性实施例中，可以生成局部至全局索引映射关系和全局至局部索引映射关系两者，并将局部至全局映射关系加载并保留在处理器缓存中。

根据一些实施例，加载模块908可以被进一步配置为：将待处理数据块的邻域元素的索引映射关系加载到处理器缓存中，其中，在对待处理数据块的处理完成前，待处理数据块的邻域元素的索引映射关系被保留在处理器缓存中。由此，通过将邻域元素的索引映射关系加载并保留在处理器缓存中，可以进一步增加数据局部性。

根据一些实施例，前文描述的包括待处理数据块、多个元素关系、运算数据、目标数据、待处理数据块所包括的多个块内元素各自的索引映射关系、待处理数据块的邻域元素、以及待处理数据块的邻域元素的索引映射关系的数据量总和可以小于处理器缓存的容量。在一些实施例中，处理器缓存中为这些数据分配有专用区域，则这些数据的总数据量可以小于专用区域的容量。

如前文所述，各种类型的处理器均可以用于执行对待处理网格数据的处理，而这些处理器(例如，CPU、GPU等)中的每一个可能包括多个处理单元，并且包括与这些处理单元对应的多个处理单元缓存。在一个示例性实施例中，处理器为GPU，包括多个线程块(Block)(即，处理单元)，每一个线程块包括由多个线程(Thread)共用的共享内存(Shared Memory)(即，处理单元缓存)。

本公开对利用这样的具有多个处理单元的处理器执行对待处理网格数据的处理进行了进一步优化，实现了对查询循环指令的并行执行，如下文将要描述的。

根据一些实施例，数据分块尺寸可以小于处理单元缓存的容量，使得数据块可以被完整加载到处理单元缓存中。可以理解的是，前文对处理器缓存的描述可以直接应用于处理单元缓存，例如相应的元素关系、运算数据、目标数据等可以加载到相应的处理单元缓存中，这些需要被加载并保留在处理器缓存上的数据可以被加载并保留在相应的处理单元缓存中等等，在此不做赘述。

根据一些实施例，查询循环指令可以查询到多个目标元素，并且多个目标元素可以属于至少一个待处理数据块。在一个示例性实施例中，多个目标元素中的部分目标元素可能属于同一个待处理数据块。在另一个示例性实施例中，多个目标元素分别属于多个待处理数据块。

根据一些实施例，至少一个待处理数据块中的每一个待处理数据块可以被唯一地加载到至少一个处理单元中的一个处理单元缓存中。由此，同一个待处理数据块不会被加载到多个处理单元的处理单元缓存中，从而节省了缓存空间。

参考图11，用于处理非结构化网格数据的装置1100中的模块1102-模块1108的操作与装置700中的模块702-模块708的操作类似，在此不做赘述。

根据一些实施例，加载模块1108被进一步配置为：将至少一个待处理数据块加载到多个处理单元缓存中的至少一个处理单元缓存中。

根据一些实施例，如图11所示，装置1100还可以包括并行执行模块1110，利用与至少一个处理单元缓存对应的至少一个处理单元，并行执行查询循环指令。

由此，通过将至少一个待处理数据块加载到至少一个处理单元缓存中，使得每一个处理单元在对相应的待处理数据块进行处理时，能够从相应的处理单元缓存快速读取相应的待处理数据块中的块内元素，从而实现了对至少一个待处理数据块的并行处理，并且能够利用处理单元缓存对每一个待处理数据块的处理进行加速。

并利用与至少一个处理单元缓存对应的至少一个处理单元中的每一个处理单元对于相应的待处理数据块中的目标元素执行与查询循环指令对应的数据处理指令，实现了对查询循环指令的并行执行，提升了对待处理网格数据的处理效率。

根据一些实施例，并行执行模块1110被进一步配置为：针对至少一个处理单元中的每一个处理单元，利用该处理单元对于多个目标元素中的至少一部分目标元素执行数据处理指令。至少一部分目标元素可以为该处理单元对应的处理单元缓存中加载的待处理数据块所包括的目标元素。

由此，通过利用处理单元对于对应的处理单元缓存中加载的待处理数据块中的每一个目标元素执行数据处理指令，使得在对于待处理数据块所包括的多个目标元素执行数据处理指令期间，只需要将待处理数据块加载到处理单元缓存中一次，从而进一步提升了缓存利用率，并降低了将数据块频繁写入缓存所带来的耗时。

根据一些实施例，并行执行模块1110被进一步配置为，并行执行查询循环指令还可以包括：利用该处理单元所包括的多个线程对于相应的待处理数据块中的目标元素并行执行数据处理指令。

由此，通过利用处理单元内的多个线程对于待处理数据块中的目标元素并行执行数据处理指令，能够进一步提升对待处理数据块以及对待处理网格数据的处理效率。

应当理解，图7中所示装置700的各个模块可以与参考图1描述的方法100中的各个步骤相对应，图9中所示装置900的各个模块可以与参考图4描述的方法400中的各个步骤相对应，图10中所示装置1000的各个模块可以与参考图5描述的方法500中的各个步骤相对应，并且图11中所示装置1100的各个模块可以与参考图6描述的方法600中的各个步骤相对应。由此，上面针对方法100描述的操作、特征和优点同样适用于装置700及其包括的模块，上面针对方法400描述的操作、特征和优点同样适用于装置900及其包括的模块，上面针对方法500描述的操作、特征和优点同样适用于装置1000及其包括的模块，并且上面针对方法600描述的操作、特征和优点同样适用于装置1100及其包括的模块。为了简洁起见，某些操作、特征和优点在此不再赘述。

虽然上面参考特定模块讨论了特定功能，但是应当注意，本文讨论的各个模块的功能可以分为多个模块，和/或多个模块的至少一些功能可以组合成单个模块。本文讨论的特定模块执行动作包括该特定模块本身执行该动作，或者替换地该特定模块调用或以其他方式访问执行该动作(或结合该特定模块一起执行该动作)的另一个组件或模块。因此，执行动作的特定模块可以包括执行动作的该特定模块本身和/或该特定模块调用或以其他方式访问的、执行动作的另一模块。如本文使用的，短语“实体A发起动作B”可以是指实体A发出执行动作B的指令，但实体A本身并不一定执行该动作B。

还应当理解，本文可以在软件硬件元件或程序模块的一般上下文中描述各种技术。上面关于图7、图9、图10、和图11描述的各个模块可以在硬件中或在结合软件和/或固件的硬件中实现。例如，这些模块可以被实现为计算机程序代码/指令，该计算机程序代码/指令被配置为在一个或多个处理器中执行并存储在计算机可读存储介质中。可替换地，这些模块可以被实现为硬件逻辑/电路。

根据本公开的一方面，提供了一种电子设备，其包括至少一个处理器以及与至少一个处理器通信连接的存储器。至少一个处理器中的每一个处理器包括处理器缓存。存储器存储有可被至少一个处理器执行的指令，指令被至少一个处理器执行，以使至少一个处理器能够执行上文描述的任一方法实施例的步骤。

根据本公开的一方面，提供了一种非暂态计算机可读存储介质，其上存储有计算机程序，该计算机程序被处理器执行时实现上文描述的任一方法实施例的步骤。

根据本公开的一方面，提供了一种存储有计算机指令的计算机程序产品，其包括计算机程序，该计算机程序被处理器执行时实现上文描述的任一方法实施例的步骤。

在下文中，结合图12描述这样的计算机设备、非暂态计算机可读存储介质和计算机程序产品的说明性示例。

图12示出了可以被用来实施本文所描述的方法的计算机设备1200的示例配置。上述装置700、装置900、装置1000、以及装置1100中的每一个也可以全部或至少部分地由计算机设备1200或类似设备或系统实现。

计算机设备1200可以是各种不同类型的设备。计算机设备1200的示例包括但不限于：台式计算机、服务器计算机、笔记本电脑或上网本计算机、移动设备(例如，平板电脑、蜂窝或其他无线电话(例如，智能电话)、记事本计算机、移动台)、可穿戴设备(例如，眼镜、手表)、娱乐设备(例如，娱乐器具、通信地耦合到显示设备的机顶盒、游戏机)、电视或其他显示设备、汽车计算机等等。

计算机设备1200可以包括能够诸如通过系统总线1214或其他适当的连接彼此通信的至少一个处理器1202、存储器1204、(多个)通信接口1206、显示设备1208、其他输入/输出(I/O)设备1210以及一个或更多大容量存储设备1212。

处理器1202可以是单个处理单元或多个处理单元，所有处理单元可以包括单个或多个计算单元或者多个核心。处理器1202可以被实施成一个或更多微处理器、微型计算机、微控制器、数字信号处理器、中央处理单元、状态机、逻辑电路和/或基于操作指令来操纵信号的任何设备。除了其他能力之外，处理器1202可以被配置成获取并且执行存储在存储器1204、大容量存储设备1212或者其他计算机可读介质中的计算机可读指令，诸如操作系统1216的程序代码、应用程序1218的程序代码、其他程序1220的程序代码等。

存储器1204和大容量存储设备1212是用于存储指令的计算机可读存储介质的示例，所述指令由处理器1202执行来实施前面所描述的各种功能。举例来说，存储器1204一般可以包括易失性存储器和非易失性存储器二者(例如RAM、ROM等等)。此外，大容量存储设备1212一般可以包括硬盘驱动器、固态驱动器、可移除介质、包括外部和可移除驱动器、存储器卡、闪存、软盘、光盘(例如CD、DVD)、存储阵列、网络附属存储、存储区域网等等。存储器1204和大容量存储设备1212在本文中都可以被统称为存储器或计算机可读存储介质，并且可以是能够把计算机可读、处理器可执行程序指令存储为计算机程序代码的非暂态介质，所述计算机程序代码可以由处理器1202作为被配置成实施在本文的示例中所描述的操作和功能的特定机器来执行。

多个程序可以存储在大容量存储设备1212上。这些程序包括操作系统1216、一个或多个应用程序1218、其他程序1220和程序数据1222，并且它们可以被加载到存储器1204以供执行。这样的应用程序或程序模块的示例可以包括例如用于实现以下部件/功能的计算机程序逻辑(例如，计算机程序代码或指令)：方法100、方法400、方法500和/或方法600(包括方法100、方法400、方法500、方法600的任何合适的步骤)、和/或本文描述的另外的实施例。

虽然在图12中被图示成存储在计算机设备1200的存储器1204中，但是模块1216、1218、1220和1222或者其部分可以使用可由计算机设备1200访问的任何形式的计算机可读介质来实施。如本文所使用的，“计算机可读介质”至少包括两种类型的计算机可读介质，也就是计算机可读存储介质和通信介质。

计算机可读存储介质包括通过用于存储信息的任何方法或技术实施的易失性和非易失性、可移除和不可移除介质，所述信息诸如是计算机可读指令、数据结构、程序模块或者其他数据。计算机可读存储介质包括而不限于RAM、ROM、EEPROM、闪存或其他存储器技术，CD-ROM、数字通用盘(DVD)、或其他光学存储装置，磁盒、磁带、磁盘存储装置或其他磁性存储设备，或者可以被用来存储信息以供计算机设备访问的任何其他非传送介质。与此相对，通信介质可以在诸如载波或其他传送机制之类的已调制数据信号中具体实现计算机可读指令、数据结构、程序模块或其他数据。本文所定义的计算机可读存储介质不包括通信介质。

一个或更多通信接口1206用于诸如通过网络、直接连接等等与其他设备交换数据。这样的通信接口可以是以下各项中的一个或多个：任何类型的网络接口(例如，网络接口卡(NIC))、有线或无线(诸如IEEE 802.11无线LAN(WLAN))无线接口、全球微波接入互操作(Wi-MAX)接口、以太网接口、通用串行总线(USB)接口、蜂窝网络接口、Bluetooth

在一些示例中，可以包括诸如监视器之类的显示设备1208，以用于向用户显示信息和图像。其他I/O设备1210可以是接收来自用户的各种输入并且向用户提供各种输出的设备，并且可以包括触摸输入设备、手势输入设备、摄影机、键盘、遥控器、鼠标、打印机、音频输入/输出设备等等。

本文描述的技术可以由计算机设备1200的这些各种配置来支持，并且不限于本文所描述的技术的具体示例。例如，该功能还可以通过使用分布式系统在“云”上全部或部分地实现。云包括和/或代表用于资源的平台。平台抽象云的硬件(例如，服务器)和软件资源的底层功能。资源可以包括在远离计算机设备1200的服务器上执行计算处理时可以使用的应用和/或数据。资源还可以包括通过因特网和/或通过诸如蜂窝或Wi-Fi网络的订户网络提供的服务。平台可以抽象资源和功能以将计算机设备1200与其他计算机设备连接。因此，本文描述的功能的实现可以分布在整个云内。例如，功能可以部分地在计算机设备1200上以及部分地通过抽象云的功能的平台来实现。

虽然在附图和前面的描述中已经详细地说明和描述了本公开，但是这样的说明和描述应当被认为是说明性的和示意性的，而非限制性的；本公开不限于所公开的实施例。通过研究附图、公开内容和所附的权利要求书，本领域技术人员在实践所要求保护的主题时，能够理解和实现对于所公开的实施例的变型。在权利要求书中，词语“包括”不排除未列出的其他元件或步骤，不定冠词“一”或“一个”不排除多个，术语“多个”是指两个或两个以上，并且术语“基于”应解释为“至少部分地基于”。在相互不同的从属权利要求中记载了某些措施的仅有事实并不表明这些措施的组合不能用来获益。