并行区重构

OpenMP是一种用于共享内存并行编程的多线程程序设计方案，适合在共享内存编程下的多核系统上进行并行程序设计。程序员在完成程序功能开发的基础上，只需添加指导语句#pragma即可自动将串行执行转换为并行处理，当编译器不支持OpenMP时，程序会忽略#pragma语句，按照串行顺序执行。OpenMP的使用降低了多核并行编程的难度，优化人员可以更多地考虑算法本身，而非具体的并行实现细节。

OpenMP Fork-Join模式程序运行过程中线程的创建和合并比较频繁，在并行性表达上处于一种低效状态。并行区重构是结合数据和计算划分等信息，通过改变原并行区的结构，降低串并行程序之间切换以及其他开销。并行区重构包括并行区扩张和并行区合并两种方式。

并行区扩张

循环结构并行区扩张针对的是包含整个循环结构的并行区，将此并行区扩张到循环之外，若该循环迭代次数为N，则并行区扩张后线程的创建和合并次数将减少N-1次。

并行区扩张后j层循环对应的并行区扩张到i层循环之外，并行区构建和合并由扩张前的2000次减少为扩张之后的1次，减少了1999次。对并行区扩张前后的代码进行测试后结果如下，计算对比发现并行区扩张后加速比达到了1.38，进一步提升了程序的性能。

函数结构并行区扩张是指将函数结构内部的并行区扩张到整个函数结构的外部，并行区扩张后能够将函数结构内部的全部语句包含在并行区中，进一步获得更多的并行区合并机会。函数结构并行区扩张可以改善程序的并行结构，增大并行计算的粒度。但是函数结构并行区扩张会彻底改变线程的堆栈结构，而且这种做法隐含着对函数结构内局部变量的数据属性进行私有化处理。为了保证并行区扩张不修改原程序语义，必须保证函数结构内局部变量私有化的合法性，因此函数结构并行区扩张要求优化人员清楚地理解函数的实现细节。

并行区合并

并行区合并不仅仅是将原有程序的多个并行区改写至一个#pragma omp parallel区域，往往还需要考虑到并行区合并是否会修改原程序语义等问题。

为了确保并行区合并不修改原程序语义，就需要保证合并后各个子线程间数据更新顺序和执行顺序与原程序保持一致性，前者可以通过指导语句flush来实现，后者可以通过指导语句barrier进行同步来实现。

除此之外，还需要考虑合并过程中的变量数据属性冲突以及并行区之间串行语句的处理等问题。

并行区合并操作经常会遇到变量的数据属性冲突问题，并行区1中声明k为共享变量，并行区2中声明k为私有变量，变量k存在数据属性冲突问题将导致并行区1和2无法直接进行合并。

针对这一问题，可以采用子句firstprivate修改共享变量的数据属性后再合并。子句firstprivate将其参数列表中的变量属性声明为私有变量，并在每个线程创建私有变量副本时，初始化私有变量副本的值，使其与进入并行区前串行区内同名变量的值一致。由于代码共享变量k在并行区1中引用，而k已经在并行区1先前的程序段中被初始化，因此在并行区1需要对变量k进行私有化处理，在引用前将初始化值传入到并行区1中，可以使用firstprivate子句来实现，然后再将两个并行区进行合并。

在实际开发过程中建议尽可能合并小的并行区，当达到一定数量时会带来程序性能提升。此外需要注意对变量进行私有化处理会屏蔽掉并行区中变量原有的初始化值，程序之间的引用关系有可能会改变。因此为了维持共享变量私有化之前程序之间的关系，需要保证进行私有化处理的共享变量在并行区中没有被初始化。

并行区合并后如代码中，变量k为私有变量，其值在每个线程上都需要加1，因此不需要添加指导语句，由于sum2赋初值只需要执行一次，添加指导语句single更为合适，最后的printf打印语句，添加指导语句master处理。