作业题目

提交内容一

解释SplitStencil_opt1.c

程序功能

SplitStencil_opt1.c程序使用多线程来执行一个分割式计算模板（Stencil）的优化算法，主要用于数值模拟中的数组数据处理。程序通过OpenMP实现并行化，加速数组的初始化、数据清洗（flushing），以及模板计算。

程序流程

  • 初始化：使用多线程初始化一个二维数组，设置特定区域的初始值。

  • 清洗数据：对一个辅助数组进行循环的数据清洗操作。

  • 模板计算：执行核心的模板计算，涉及到数组的读取和更新。

  • 性能监控：记录并输出程序的初始化、清洗和模板计算的时间。

主要函数说明

  • main()：程序入口，负责数组的分配、并行区域的定义和执行，以及性能统计。
  • SplitStencil()：核心的模板计算函数，处理数组的更新。
  • malloc2D()：辅助函数，用于分配二维数组的空间。
  • cpu_timer_start() 和 cpu_timer_stop()：计时函数，用于监控各部分的执行时间。

程序注释

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

#include "malloc2D.h"
#include "timer.h"

void SplitStencil(double **a, int imax, int jmax);
// 定义宏，分别用于计算两个值的最小值和最大值
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MAX(a,b) ((a) > (b) ? (a) : (b))

int main(int argc, char *argv[])
{
   // 启用OpenMP并行区域
   #pragma omp parallel
      // 如果是第0个线程
      if (omp_get_thread_num() == 0)
         // 打印线程数
         printf("Running with %d thread(s)\n",omp_get_num_threads());

   struct timespec tstart_init, tstart_flush, tstart_stencil, tstart_total;
   double init_time, flush_time, stencil_time, total_time;
   // 定义数组的尺寸
   int imax=2002, jmax = 2002;
   char string[60];
   // 分配二维数组a
   double** a = malloc2D(jmax, imax);
   // 分配flush数组
   int *flush = (int *)malloc(jmax*imax*sizeof(int)*4);
   // 总时间计时开始
   cpu_timer_start(&tstart_total);
#pragma omp parallel
   {
      // 获取当前线程ID
      int thread_id = omp_get_thread_num();
      // 获取线程总数
      int nthreads = omp_get_num_threads();
      // 计算每个线程处理的行范围
      int jltb = 1 + (jmax-2) * ( thread_id     ) / nthreads;
      int jutb = 1 + (jmax-2) * ( thread_id + 1 ) / nthreads;
      // 计算每个线程处理的flush数组范围
      int ifltb = (jmax*imax*4) * ( thread_id     ) / nthreads;
      int ifutb = (jmax*imax*4) * ( thread_id + 1 ) / nthreads;
       
      // 确保边界条件处理正确
      int jltb0 = jltb;
      if (thread_id == 0) jltb0--;
      int jutb0 = jutb;
      if (thread_id == nthreads-1) jutb0++;

      // 计算核心处理区域
      int kmin = MAX(jmax/2-5,jltb);
      int kmax = MIN(jmax/2+5,jutb);

      if (thread_id == 0) cpu_timer_start(&tstart_init);
      for (int j = jltb0; j < jutb0; j++){
         for (int i = 0; i < imax; i++){
            // 初始化数组a
            a[j][i] = 5.0;
         }
      }

      for (int j = kmin; j < kmax; j++){
         for (int i = imax/2 - 5; i < imax/2 -1; i++){
            // 在核心处理区域内设置更高的初始值
            a[j][i] = 400.0;
         }
      }
// 确保所有线程完成初始化
#pragma omp barrier
      // 记录初始化时间
      if (thread_id == 0) init_time += cpu_timer_stop(tstart_init);
      // 进行100次迭代
      for (int iter = 0; iter < 100; iter++){
         if (thread_id == 0) cpu_timer_start(&tstart_flush);
         for (int l = ifltb; l < ifutb; l++){
            // 清洗flush数组
            flush[l] = 1.0;
         }
         if (thread_id == 0){
            // 记录清洗时间
            flush_time += cpu_timer_stop(tstart_flush);
            // 格式化输出
            sprintf(string,"flush %d\n",flush[5]);
            cpu_timer_start(&tstart_stencil);
         }
         // 调用模板计算函数
         SplitStencil(a, imax, jmax);
         if (thread_id == 0){
            // 记录模板计算时间
            stencil_time += cpu_timer_stop(tstart_stencil);
            // 格式化输出数组a的一个值
            sprintf(string,"a %lf\n",a[5][5]);
            // 每1000次迭代打印一次
            if (iter%1000 == 0) printf("Iter %d\n",iter);
         }
      }
   } // 结束并行区域
   // 总时间计时结束
   total_time += cpu_timer_stop(tstart_total);
   // 输出时间统计结果
   printf("Timing is init %f flush %f stencil %f total %f\n",
          init_time,flush_time,stencil_time,total_time);
   // 释放数组a
   free(a);
   // 释放数组flush
   free(flush);
}

void SplitStencil(double **a, int imax, int jmax)
{
   int thread_id = omp_get_thread_num();
   int nthreads = omp_get_num_threads();

   // 每个线程处理的行范围
   int jltb = 1 + (jmax-2) * thread_id / nthreads;
   int jutb = 1 + (jmax-2) * (thread_id + 1) / nthreads;

   int jfltb = jltb;
   int jfutb = jutb;
   if (thread_id == 0) jfltb--;

   // 分配边界面数组
   double** xface = (double **)malloc2D(jutb-jltb, imax-1);
   static double** yface;
   if (thread_id == 0) yface = (double **)malloc2D(jmax+2, imax);
   #pragma omp barrier
   // 计算x方向和y方向边界面值
   for (int j = jltb; j < jutb; j++) {
      for (int i = 0; i < imax-1; i++) {
         xface[j-jltb][i] = (a[j][i+1] + a[j][i]) / 2.0;
      }
   }
   for (int j = jfltb; j < jfutb; j++) {
      for (int i = 1; i < imax-1; i++) {
         yface[j][i] = (a[j+1][i] + a[j][i]) / 2.0;
      }
   }
   #pragma omp barrier
   // 根据边界面更新数组值
   for (int j = jltb; j < jutb; j++) {
      for (int i = 1; i < imax-1; i++) {
         a[j][i] = (a[j][i] + xface[j-jltb][i] + xface[j-jltb][i-1] +
                            yface[j][i] + yface[j-1][i]) / 5.0;
      }
   }
   free(xface);
   #pragma omp barrier
   // 释放内存
   if (thread_id == 0) free(yface); 
}

记录run.sh输出的时间数据

  • 进入build文件夹进行cmake

  • 进行make

  • 运行run.sh

提交内容二

解释prime_task”任务”并行原理

prime_task.cpp通过任务并行化，有效地将一个大的问题（检查20000000以内的数字有多少个质数）分解成规模更小的子问题，并利用多核处理器的并行处理能力来加速计算。这样的分解减少了线程间的依赖，允许更高效的并行执行。它的详细工作原理如下：

  • OpenMP 库和指令

首先，程序包含了 OpenMP 库 <omp.h>，这是进行并行编程的关键。通过使用 OpenMP 的指令（如 #pragma omp），程序能够在多个处理器上并行执行。

  • 主要的并行结构

在 main 函数中，通过使用 #pragma omp parallel，创建了一个并行区域，在该区域内的代码将会被多个线程并行执行。

#pragma omp parallel 
{
    // 并行区域的代码
}
  • 创建并行任务

在并行区域内部，使用 #pragma omp single nowait 指定一个线程来执行接下来的循环，并且这个指令允许其他线程不必等待这个线程完成循环即可继续执行：

#pragma omp single nowait
{
    for (i = 2; i <= ITER ; i+=1000) {
        // 创建任务的代码
    }
}
  • 任务划分

循环内部，每次循环迭代都定义了一个从 num_start 到 num_end 的区间，每个区间长度大约是1000。对于每个这样的区间，使用 #pragma omp task 创建一个新的任务来执行 check_prime 函数：

#pragma omp task
check_prime(num_start,num_end);

这里，每个任务都是独立的，并在不同的线程上并行执行，这样可以同时检查多个数区间内的质数。

  • 等待所有任务完成

所有的任务创建之后，使用 #pragma omp taskwait 来确保所有任务完成之前，不会继续执行后面的代码。这保证了在输出最终的质数数量和时间统计之前，所有的质数检查任务都已完成。

#pragma omp taskwait
  • 统计和输出

最后，统计所有检查出的质数数量（由全局变量 sum 维护），并计算整个并行任务所消耗的时间，然后输出。

记录程序输出的时间数据

  • 编译prime_task

  • 修改run.sh

  • 运行run.sh

自评分及理由

自评分

  • 10分

评分理由

  • 完成提交内容一：编写SplitStencil_opt1.c的代码说明文档，说明程序流程，简要注释代码；记录SplitStencil_opt1.c在1,2,4线程运行时的时间数据(7分)
  • 完成提交内容二：说明prime_task.cpp的并行原理；记录prime_task在1,2,4线程运行时的时间数据(3分)