面向共享内存多核结构中线程级并行的数据优化方法及装置

摘要

本发明属于计算机多核结构并行优化技术领域，特别涉及一种面向共享内存多核结构中线程级并行的数据优化方法及装置，该方法包含：针对待优化数据，检测并判定其所有循环携带依赖是否存在私有化有利性情况；并依据检测判定结果，实施数据私有化处理。本发明针对多核硬件结构中循环并行线程，首先对数据进行私有化处理的有利性检测，然后通过数据私有化来消除循环携带依赖，进而实现程序的多线程并行；并进一步将数据私有化区分为标量私有化和数组私有化，充分利用共享存储的多核硬件结构优势，提高线程执行效率，并提高处理器乃至计算机系统性能的利用率，降低运行开销，对共享内存多核结构线程级并行处理技术具有重要的指导意义。

权利要求

1.一种面向共享内存多核结构中线程级并行的数据优化方法，其特征在于，包含：

针对待优化循环，检测并判定其所有循环携带依赖是否存在私有化有利性情况；并依据检测判定结果，实施数据私有化处理；

检测并判定所有循环携带依赖的私有化有利性情况，包含如下内容：

针对待优化数据的目标循环层，对其中每一个标量，若在该目标循环层中的每次引用均由当前迭代进行赋值，则判定该标量引起的依赖私有化处理，否则，判定该标量无需数据私有化处理；对其中每一个数组，若该数组依赖是由目标循环层内部的循环层携带，并检测每一个数组元素在目标循环层迭代中的每次引用均由当前迭代赋值，则判定该数组引起的依赖私有化处理，否则，判定该数组无需数据私有化。

2.根据权利要求1所述的面向共享内存多核结构中线程级并行的数据优化方法，其特征在于，所述私有化有利性情况是指所有循环携带依赖能否通过数据私有化进行消除。

3.根据权利要求1所述的面向共享内存多核结构中线程级并行的数据优化方法，其特征在于，依据检测判定结果，进行标量引起的依赖私有化处理，包含如下内容：针对待私有化处理的标量引起的依赖，首先遍历循环体中每条语句，查找并收集其中针对该标量的写操作，并将其加入到集合W中，若集合W为空，则无需进行标量私有化，否则，遍历集合W，针对集合中涉及到的每个标量，检测其是否为规约变量，若是，则将规约变量变换为归纳变量；遍历集合W，对集合中涉及到的每个标量进行私有化处理。

4.根据权利要求1或3所述的面向共享内存多核结构中线程级并行的数据优化方法，其特征在于，采用标量扩展数组或私有化子句修饰来对标量进行私有化处理。

5.根据权利要求1所述的面向共享内存多核结构中线程级并行的数据优化方法，其特征在于，依据检测判定结果，进行数组引起的依赖私有化处理，包含如下内容：针对待私有化处理的数组引起的依赖，首先遍历循环体中每条该数组访问语句，查找并收集其中针对数组的写操作，将其加入到集合AW中；若集合AW为空，则无需进行数组私有化，否则，遍历集合AW，针对集合中涉及到的每个数组引用，检测其是否存在规约，若存在，则将规约变换为归纳；遍历集合AW，对集合中涉及到的每个数组进行私有化处理。

6.根据权利要求1或5所述的面向共享内存多核结构中线程级并行的数据优化方法，其特征在于，采用数组维数扩展或私有化子句修饰来对数组进行私有化处理。

7.一种面向共享内存多核结构中线程级并行的数据优化装置，其特征在于，基于权利要求1的数据优化方法实现，包含测试模块和优化模块，其中，测试模块，用于针对待优化数据，检测并判定其所有循环携带依赖是否存在私有化有利性情况，依据检测判定结果将需要私有化处理的情形反馈给优化模块；

优化模块，用于依据测试模块反馈结果实施数据私有化处理。

8.根据权利要求7所述的面向共享内存多核结构中线程级并行的数据优化装置，其特征在于，测试模块包含检测子模块一和检测子模块二，其中，检测子模块一，用于针对待优化数据的目标循环层，对其中每一个标量，若在该目标循环层中的每次引用均由当前迭代进行赋值，则判定该标量引起的依赖私有化处理，否则，判定该标量无需数据私有化处理；

检测子模块二，用于针对待优化数据的目标循环层，对其中每一个数组，若该数组依赖是由目标循环层内部的循环层携带，并检测每一个数组元素在目标循环层迭代中的每次引用均由当前迭代赋值，则判定该数组引起的依赖私有化处理，否则，判定该数组无需数据私有化。

9.根据权利要求7所述的面向共享内存多核结构中线程级并行的数据优化装置，其特征在于，优化模块包含优化子模块一和优化子模块二，其中，优化子模块一，用于依据反馈结果，针对待私有化处理的标量引起的依赖，首先遍历循环体中每条语句，查找并收集其中针对该标量的写操作，并将其加入到集合W中，若集合W为空，则无需进行标量私有化，否则，遍历集合W，针对集合中涉及到的每个标量，检测其是否为规约变量，若是，则将规约变量变换为归纳变量；遍历集合W，对集合中涉及到的每个标量进行私有化处理；

优化子模块二，用于依据反馈结果，针对待私有化处理的数组引起的依赖，首先遍历循环体中每条该数组访问语句，查找并收集其中针对数组的写操作，将其加入到集合AW中；若集合AW为空，则无需进行数组私有化，否则，遍历集合AW，针对集合中涉及到的每个数组引用，检测其是否存在规约，若存在，则将规约变换为归纳；遍历集合AW，对集合中涉及到的每个数组进行私有化处理。

说明书

面向共享内存多核结构中线程级并行的数据优化方法及装置

技术领域

[0001] 本发明属于计算机多核结构并行优化技术领域，特别涉及一种面向共享内存多核结构中线程级并行的数据优化方法及装置。

背景技术

[0002] 当前，并行体系结构已经不是超级计算机的特权，现代处理器通常采用多核结构来获得更高的性能。为了充分利用这种多核结构的硬件性能，需要开发有效的线程级并行程序。OpenMP编程模型是线程级并行的有效手段。OpenMP的执行模型如图2所示，在开始执行的时候，只有主线程在运行，主线程在运行过程中，当遇到需要进行并行计算的区域，派生出(Fork，创建新线程或者唤醒已有线程)多个线程来执行并行任务，在并行执行的时候，主线程和派生线程共同工作，在并行区结束执行后，派生线程退出或者挂起，不再工作，控制流程回到单独的主线程中(Join，即多线程的汇合)。通过OpenMP可以方便地实现循环的多线程并行，即，将不同的循环迭代分配到不同的线程上去执行。由于每个线程的执行顺序是随机的，等同于打乱了原有迭代的执行顺序，这就要求各迭代之间不能存在任何的依赖，后续将迭代之间的依赖称之循环携带依赖。任何循环携带依赖的存在将阻止程序的并行化，进而影响线程执行效率、多核结构硬件运行性能和开销。

发明内容

[0003] 为此，本发明提供一种面向共享内存多核结构中线程级并行的数据优化方法及装置，充分利用多核结构的硬件性能，满足循环的多线程并行需求，实现循环数据的线程级并行执行的有效性，提高多核处理器数据执行效率。

[0004] 按照本发明所提供的设计方案，一种面向共享内存多核结构中线程级并行的数据优化方法，包含：针对待优化循环，检测并判定其所有循环携带依赖是否存在私有化有利性情况；并依据检测判定结果，实施数据私有化处理。

[0005] 上述的，所述私有化有利性情况是指所有循环携带依赖能否通过数据私有化进行消除。

[0006] 上述的，检测并判定所有循环携带依赖的私有化有利性情况，包含如下内容：

[0007] 针对待优化数据的目标循环层，对其中每一个标量，若在该目标循环层中的每次引用均由当前迭代进行赋值，则判定该标量引起的依赖私有化处理，否则，判定该标量无需数据私有化处理；对其中每一个数组，若该数组依赖是由目标循环层内部的循环层携带，并检测每一个数组元素在目标循环层迭代中的每次引用均由当前迭代赋值，则判定该数组引起的依赖私有化处理，否则，判定该数组无需数据私有化。

[0008] 优选的，依据检测判定结果，进行标量引起的依赖私有化处理，包含如下内容：

[0009] 针对待私有化处理的标量引起的依赖，首先遍历循环体中每条语句，查找并收集其中针对该标量的写操作，并将其加入到集合W中，若集合W为空，则无需进行标量私有化，否则，遍历集合W，针对集合中涉及到的每个标量，检测其是否为规约变量，若是，则将规约变量变换为归纳变量；遍历集合W，对集合中涉及到的每个标量进行私有化处理。

[0010] 更进一步，采用标量扩展数组或私有化子句修饰来对标量进行私有化处理。

[0011] 优选的，依据检测判定结果，进行数组引起的依赖私有化处理，包含如下内容：

[0012] 针对待私有化处理的数组引起的依赖，首先遍历循环体重每条该数组访问语句，查找并收集其中针对数组的写操作，将其加入到集合AW中；若集合AW为空，则无需进行数组私有化，否则，遍历集合AW，针对集合中涉及到的每个数组引用，检测其是否存在规约，若存在，则将规约变换为归纳；遍历集合AW，对集合中涉及到的每个数组进行私有化处理。

[0013] 更进一步，采用数组维数扩展或私有化子句修饰来对数组进行私有化处理。

[0014] 一种面向共享内存多核结构中线程级并行的数据优化装置，包含测试模块和优化模块，其中，

[0015] 测试模块，用于针对待优化数据，检测并判定其所有循环携带依赖是否存在私有化有利性情况，依据检测判定结果将需要私有化处理的情形反馈给优化模块；

[0016] 优化模块，用于依据测试模块反馈结果实施数据私有化处理。

[0017] 上述的装置中，测试模块包含检测子模块一和检测子模块二，其中，[0018] 检测子模块一，用于针对待优化数据的目标循环层，对其中每一个标量，若在该目标循环层中的每次引用均由当前迭代进行赋值，则判定该标量引起的依赖私有化处理，否则，判定该标量无需数据私有化处理；

[0019] 检测子模块二，用于针对待优化数据的目标循环层，对其中每一个数组，若该数组依赖是由目标循环层内部的循环层携带，并检测每一个数组元素在目标循环层迭代中的每次引用均由当前迭代赋值，则判定该数组引起的依赖私有化处理，否则，判定该数组无需数据私有化。

[0020] 上述的装置中，优化模块包含优化子模块一和优化子模块二，其中，[0021] 优化子模块一，用于依据反馈结果，针对待私有化处理的标量引起的依赖，首先遍历循环体中每条语句，查找并收集其中针对该标量的写操作，并将其加入到集合W中，若集合W为空，则无需进行标量私有化，否则，遍历集合W，针对集合中涉及到的每个标量，检测其是否为规约变量，若是，则将规约变量变换为归纳变量；遍历集合W，对集合中涉及到的每个标量进行私有化处理；

[0022] 优化子模块二，用于依据反馈结果，针对待私有化处理的数组引起的依赖，首先遍历循环体重每条该数组访问语句，查找并收集其中针对数组的写操作，将其加入到集合AW中；若集合AW为空，则无需进行数组私有化，否则，遍历集合AW，针对集合中涉及到的每个数组引用，检测其是否存在规约，若存在，则将规约变换为归纳；遍历集合AW，对集合中涉及到的每个数组进行私有化处理。

[0023] 本发明的有益效果：

[0024] 本发明针对多核硬件结构中循环并行线程，首先对数据进行私有化处理的有利性检测，然后通过数据私有化来消除循环携带依赖，进而实现程序的多线程并行；并进一步将数据私有化区分为标量私有化和数组私有化，充分利用共享存储的多核硬件结构优势，提高线程执行效率，并提高处理器乃至计算机系统性能的利用率，降低运行开销，对共享内存多核结构线程级并行处理技术具有重要的指导意义。附图说明：

[0025] 图1为实施例中数据优化方法流程示意图；

[0026] 图2为实施例中OpenMP并行执行模型示意图；

[0027] 图3为实施例中数据优化装置示意图；

[0028] 图4为实施例中测试模块示意图；

[0029] 图5为实施例中优化模块示意图。具体实施方式：

[0030] 为使本发明的目的、技术方案和优点更加清楚、明白，下面结合附图和技术方案对本发明作进一步详细的说明。

[0031] OpenMP的执行模型如图2所示，在开始执行的时候，只有主线程在运行，主线程在运行过程中，当遇到需要进行并行计算的区域，派生出(Fork，创建新线程或者唤醒已有线程)多个线程来执行并行任务，在并行执行的时候，主线程和派生线程共同工作，在并行区结束执行后，派生线程退出或者挂起，不再工作，控制流程回到单独的主线程中(Join，即多线程的汇合)。通过OpenMP可以方便地实现循环的多线程并行。在循环多线程并行中，由于每个线程执行顺序是随机的，这就要求各迭代之间不能存在循环携带依赖，否则会阻止程序的并行化，进而影响执行效率及多核处理器等的运行性能。鉴于此，本发明实施例，参见图1所示，提供一种面向共享内存多核结构中线程级并行的数据优化方法，包含如下内容：

[0032] S101、针对待优化数据，检测并判定其所有循环携带依赖是否存在私有化有利性情况；

[0033] S102、依据检测判定结果，实施数据私有化处理。

[0034] 本发明实施例中，首先进行私有化有利性测试来判断私有化时候是否可以消除所有阻碍并行的依赖，然后针对测试结果通过数据私有化实施依赖消除工作，破除迭代之间的依赖关系，实现循环的线程级并行，充分利用多核结构的硬件运行性能，提高程序执行效率。

[0035] 检测并判定所有循环携带依赖的私有化有利性情况时，本发明再一个实施例中，该检测判定过程设计为包含如下内容：

[0036] 针对待优化数据的目标循环层，对其中每一个标量，若在该目标循环层中的每次引用均由当前迭代进行赋值，则判定该标量引起的依赖私有化处理，否则，判定该标量无需数据私有化处理；对其中每一个数组，若该数组依赖是由目标循环层内部的循环层携带，并检测每一个数组元素在目标循环层迭代中的每次引用均由当前迭代赋值，则判定该数组引起的依赖私有化处理，否则，判定该数组无需数据私有化。

[0037] 因为数据私有化会消耗内存空间，并不一定带来好的效果。因此在数据私有化之前，检测是否所有的循环携带依赖都可以通过数据私有化来消除；如果可以，那么继续实施真正的数据私有化，否则，停止数据私有化处理，避免不必要的程序执行开销。测试标量引起的携带依赖测试，将待并行化的循环层称为目标循环层，对于每一个标量，如果在目标循环层迭代中的每一次引用都是由本次迭代计算出来的值，那么说明标量引起的依赖可以通过私有化来消除掉，并继续进行下一步有利性测试。对于每一个数组依赖，需要检查携带依赖的循环层，将待并行化的循环层称为目标循环层，存在三种情况：(1)依赖是由目标循环层之外的循环层携带的；(2)依赖是由目标循环层携带的；(3)依赖是由目标循环层内部的循环层携带的；对于第一种情况，由于依赖由外层循环携带，目标循环层无携带依赖，数组不需要私有化；对于第二种情况，依赖由目标循环层携带，无法通过如果该依赖是由目标循环层携带的，那么该依赖无法通过数组私有化来消除，有利性测试失败；对于第三种情况，如果是由目标循环层内部的循环层携带的，继续检测每一个数组元素，如果它在目标循环层迭代中的每一次引用的值都是由本次迭代计算出来的，那么该依赖可以通过私有化来消除，否则，不可消除，有利性测试失败。

[0038] 依据检测判定结果，进行标量引起的依赖私有化处理，本发明另一个实施例中，该标量私有化处理包含如下内容：

[0039] 针对待私有化处理的标量引起的依赖，首先遍历循环体中每条语句，查找并收集其中针对该标量的写操作，并将其加入到集合W中，若集合W为空，则无需进行标量私有化，否则，遍历集合W，针对集合中涉及到的每个标量，检测其是否为规约变量，若是，则将规约变量变换为归纳变量；遍历集合W，对集合中涉及到的每个标量进行私有化处理。

[0040] 更进一步，采用标量扩展数组或私有化子句修饰，如private等，来对标量进行私有化处理。

[0041] 依据检测判定结果，进行数组引起的依赖私有化处理，本发明另一个实施例中，该数组私有化处理包含如下内容：

[0042] 针对待私有化处理的数组引起的依赖，首先遍历循环体重每条该数组访问语句，查找并收集其中针对数组的写操作，将其加入到集合AW中；若集合AW为空，则无需进行数组私有化，否则，遍历集合AW，针对集合中涉及到的每个数组引用，检测其是否存在规约，若存在，则将规约变换为归纳；遍历集合AW，对集合中涉及到的每个数组进行私有化处理。

[0043] 更进一步，采用数组维数扩展或私有化子句修饰，如private等，来对数组进行私有化处理。

[0044] 数组检测是否为规约时，可通过判定其是否为“ARRAY[i]＝ARRAY[i]op XX”的形式，如果存在数组引起的规约，将规约变换为归纳。针对每个私有化的数组，其数组元素若在循环体中只存在读操作，则对涉及到的每个数组元素进行初始化，每个私有化的数组默认值都是0，避免可能与原值不符等的情形，进而影响程序执行效率。

[0045] 基于上述的数据优化方法，本发明实施例还提供一种面向共享内存多核结构中线程级并行的数据优化装置，参见图3所示，包含测试模块101和优化模块102，其中，[0046] 测试模块101，用于针对待优化数据，检测并判定其所有循环携带依赖是否存在私有化有利性情况，依据检测判定结果将需要私有化处理的情形反馈给优化模块；

[0047] 优化模块102，用于依据测试模块反馈结果实施数据私有化处理。

[0048] 上述的装置中，参见图4所示，测试模块101包含检测子模块一1001和检测子模块二1002，其中，

[0049] 检测子模块一1001，用于针对待优化数据的目标循环层，对其中每一个标量，若在该目标循环层中的每次引用均由当前迭代进行赋值，则判定该标量引起的依赖私有化处理，否则，判定该标量无需数据私有化处理；

[0050] 检测子模块二1002，用于针对待优化数据的目标循环层，对其中每一个数组，若该数组依赖是由目标循环层内部的循环层携带，并检测每一个数组元素在目标循环层迭代中的每次引用均由当前迭代赋值，则判定该数组引起的依赖私有化处理，否则，判定该数组无需数据私有化。

[0051] 上述的装置中，参见图5所示，优化模块102包含优化子模块一2001和优化子模块二2002，其中，

[0052] 优化子模块一2001，用于依据反馈结果，针对待私有化处理的标量引起的依赖，首先遍历循环体中每条语句，查找并收集其中针对该标量的写操作，并将其加入到集合W中，若集合W为空，则无需进行标量私有化，否则，遍历集合W，针对集合中涉及到的每个标量，检测其是否为规约变量，若是，则将规约变量变换为归纳变量；遍历集合W，对集合中涉及到的每个标量进行私有化处理；

[0053] 优化子模块二2002，用于依据反馈结果，针对待私有化处理的数组引起的依赖，首先遍历循环体重每条该数组访问语句，查找并收集其中针对数组的写操作，将其加入到集合AW中；若集合AW为空，则无需进行数组私有化，否则，遍历集合AW，针对集合中涉及到的每个数组引用，检测其是否存在规约，若存在，则将规约变换为归纳；遍历集合AW，对集合中涉及到的每个数组进行私有化处理。

[0054] 基于以上内容，本发明实施例中，进一步通过可参考伪代码内容及具体实例做进一步说明，标量、数组私有化处理伪代码设计内容及实例如下：

[0055] 标量私有化伪代码：

[0056]

[0057] 标量私有化实例：

[0058]

[0059] 数组私有化伪代码：

[0060]

[0061] 数组私有化实例如下：

[0062]

[0063] 基于上述的方法，本发明实施例还提供一种服务器，包括：一个或多个处理器；存储装置，用于存储一个或多个程序，当所述一个或多个程序被所述一个或多个处理器执行，使得所述一个或多个处理器实现上述的方法。

[0064] 基于上述的方法，本发明实施例还提供一种计算机可读介质，其上存储有计算机程序，其中，该程序被处理器执行时实现上述的方法。

[0065] 除非另外具体说明，否则在这些实施例中阐述的部件和步骤的相对步骤、数字表达式和数值并不限制本发明的范围。

[0066] 本发明实施例所提供的装置，其实现原理及产生的技术效果和前述方法实施例相同，为简要描述，装置实施例部分未提及之处，可参考前述方法实施例中相应内容。

[0067] 所属领域的技术人员可以清楚地了解到，为描述的方便和简洁，上述描述的系统和装置的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。

[0068] 在这里示出和描述的所有示例中，任何具体值应被解释为仅仅是示例性的，而不是作为限制，因此，示例性实施例的其他示例可以具有不同的值。

[0069] 应注意到：相似的标号和字母在下面的附图中表示类似项，因此，一旦某一项在一个附图中被定义，则在随后的附图中不需要对其进行进一步定义和解释。

[0070] 附图中的流程图和框图显示了根据本发明的多个实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段或代码的一部分，所述模块、程序段或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个连续的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方框的组合，可以用执行规定的功能或动作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。

[0071] 在本申请所提供的几个实施例中，应该理解到，所揭露的系统、装置和方法，可以通过其它的方式实现。以上所描述的装置实施例仅仅是示意性的，例如，所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，又例如，多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些通信接口，装置或单元的间接耦合或通信连接，可以是电性，机械或其它的形式。

[0072] 所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。

[0073] 另外，在本发明各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。

[0074] 所述功能如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个处理器可执行的非易失的计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁碟或者光盘等各种可以存储程序代码的介质。

[0075] 最后应说明的是：以上所述实施例，仅为本发明的具体实施方式，用以说明本发明的技术方案，而非对其限制，本发明的保护范围并不局限于此，尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，其依然可以对前述实施例所记载的技术方案进行修改或可轻易想到变化，或者对其中部分技术特征进行等同替换；而这些修改、变化或者替换，并不使相应技术方案的本质脱离本发明实施例技术方案的精神和范围，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应所述以权利要求的保护范围为准。