09:45

自编教材分享：第九章—负载均衡优化

1011

0

负载均衡优化

OpenMP能够以较低的成本开发多线程程序，是将大量串行程序快速并行的有效方法，但并行执行过程中的调度开销、线程创建开销、以及同步开销等造成的负载失衡都会影响OpenMP程序的性能，而合理利用调度策略以及线程数设置等方式可以很好地实现负载均衡，提升程序的性能。

循环嵌套合并调度

子句collapse只能用于循环嵌套，它的具体语法格式为collapse(n)，其中参数n是一个整数，是指将与collapse子句最相邻的n层循环的迭代压缩合并在一起组成更大的任务调度空间，从而增加线程组调度空间中的循环总数，可调度迭代次数的增加有助于解决负载不均衡问题。

添加指导语句#pragma omp parallel for对循环嵌套进行并行，往往只能对紧邻指导语句的循环进行多线程任务划分，而其内层的循环只能在一个线程上执行。如果外层循环的迭代次数过少，而内层循环的迭代次数很多，仅对外层循环进行任务划分就容易造成负载不均衡的情况，OpenMP规范中提供的collapse子句可用于解决此问题。

 #pragma omp parallel for private(i,j,k) shared(A,B,C) num_threads(4)     	for(i=0;i<N;i++)         
   for(j=0;j<N;j++)             
     for(k=0;k<N;k++)                 
       C[i][j]+=A[i][k]*B[k][j]; 

线程调度配置策略

选择合适的线程调度策略，即对循环迭代采取静态或动态的方式分配到各个线程上并行执行，使得各个线程的工作量相当，以提升程序的性能。

#pragma omp for schedule(schedule_name , chunk_size)

• 静态调度 static：将所有的循环迭代划分为大小相等的调度块，使得迭代次数在线程上尽可能地均分。

• 动态调度 dynamic：使用“先来先服务的排队申请策略”，当某个线程执行完当前调度块的任务时，就为其从调度块队列中分配一个新的调度块。

• 指导调度 guided：强调的是任务分块动态变化，调度块的大小开始比较大，但会随程序的执行会按指数关系逐渐变小。

• 运行时调度 runtime：指在运行时使用环境变量OMP_SCHDULE来确定上述三种调度策略的某一种。

• 规则循环结构：如矩阵乘法程序，建议使用带参数的静态调度以取得较好的性能。

• 递增型循环结构：建议使用带参数的静态调度策略可在一定程度上缓解循环各迭代之间的计算量差距，以获得较好的性能。

• 递减循环结构：首先使用指导调度，判断在开始时是否会因调度块较大会导致负载极为不均衡，若是则推荐使用动态调度，使得各线程调度的迭代块大小相当，从而实现有效的负载均衡。

• 随机循环结构：推荐优先使用动态调度。

线程数设置优化

串并行切换

串并行切换：OpenMP提供有if子句来自动切换程序的并行和串行，即在指导命令后增加if（N>Number）子句，其中当程序的计算量N大于阈值Number时，并行执行，否则串行执行。在本例中，阈值Number需要根据运行环境和线程设置数量等，不断调整矩阵规模N测试进行寻找。

#pragma omp parallel for private(i,j,k) shared(A,B,C) num_threads(8)// if(N>86) 
    for(i=0;i<N;i++)
        for(j=0;j<N;j++)
            for(k=0;k<N;k++)
                C[i][j]+=A[i][k]*B[k][j]; 

选择合适的线程数

OpenMP程序设置的线程数量一定程度上影响了程序的性能，增加线程可以在特定时间段内完成更多的任务，但不断增加线程数量可能会使线程间同步等开销增加反而导致程序的性能降低，OpenMP提供的线程设置模式，帮助开发人员选择程序的并行线程数量。

omp_set_dynamic(1)；
omp_set_num_threads(8);
#pragma omp parallel for private(i,j,k) shared(A,B,C)//if(N>86)
for(i=0;i<N;i++)
	for(j=0;j<N;j++)
		for(k=0;k<N;k++)
			C[i][j]+=A[i][k]*B[k][j];

• 静态模式：由优化人员确定并行区中线程的数量

        omp_set_num_threads()

        添加子句num_threads

        使用环境变量OMP_NUM_THREADS

• 动态模式：

        采用默认模式（不指定线程数）

        omp_set_dynamic() 设定并行区内线程的数目上限

• 嵌套模式：函数omp_set_nested()启动或禁用嵌套并行，即在并行区中构建另一个并行区

• 条件模式：利用子句if切换程序串行并行

在实际应用中，并行程序可能会进行程序优化调整或发生运行环境改变，由于不同程序的最优性能对应的线程数是不同的，需要重新设置线程数以达到性能最优，因此根据程序特征和运行环境来设置合适的线程数十分重要。

#pragma omp parallel for private(i,j,k) shared(A,B,C) if(N>86) num_threads(12)  	
for (int ii = 0; ii < N; ii += BLOCK_SIZE) 		
  for (int jj = 0; jj < N; jj += BLOCK_SIZE) 			
    for (int kk = 0; kk < N; kk+=BLOCK_SIZE) 				
      for (i = ii; i < min(ii+BLOCK_SIZE,N); i++) 					
        for (k = kk; k < min(kk+BLOCK_SIZE,N); k++){ 						
          int s=A[i][k]; 						
          for ( j = jj; j < min(jj+BLOCK_SIZE,N); j++){ 	
            C[i][j]+= s*B[k][j]; 						
          } 					
        }