MPI BMP 图像比较更高效

Question

我做了一个简单的程序，我在其中逐个像素地比较两个图像并确定图片是否相同。我正在尝试使其适应 MPI，但我担心通信花费的时间太长，使其效率低于顺序通信。我尝试过使用非常大分辨率的图像，结果是一样的：顺序代码比并行代码更有效。有没有办法让它更有效率？

顺序代码：

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

    unsigned char* BMP(char* filename,int* sizes)
    {
        int i;
        FILE* f = fopen(filename, "rb");
        unsigned char info[54];
        fread(info, sizeof(unsigned char), 54, f);

        int ancho = *(int*)&info[18];
        int alto = *(int*)&info[22];

        int size = 3 * ancho * alto;
        *sizes = size;
        unsigned char* data = new unsigned char[size];
        fread(data, sizeof(unsigned char), size, f);
        fclose(f);
        for(i = 0; i < size; i += 3)
        {
                unsigned char tmp = data[i];
                data[i] = data[i+2];
                data[i+2] = tmp;
        }

        return data;
    }

    int main(int argc,char **argv){
      int sizes,i,bol;
      clock_t t1,t2;
      double tiemp;
      t1 = clock();
      bol=1;
      unsigned char* data1= BMP(argv[1],&sizes);
      unsigned char* data2= BMP(argv[2],&sizes);
      for (i =0; i<sizes; i += 3)
      {
        if(data1[i]!=data2[i]){
          printf("The images are not the same\n");
          bol=0;
          break;}
        }

      if(bol==1)
       printf("The images are the same\n");

       t2 = clock();
       tiemp = ((double) (t2 - t1)) / (CLOCKS_PER_SEC);
       printf("%f\n",tiemp );
      return 0;
     }

MPI 计数器部分

    #include <stdio.h>
    #include <stdlib.h>
    #include <mpi.h>
    #include <time.h>

    unsigned char* BMP(char* filename,int* sizes)
    {
        int i;

        FILE* f = fopen(filename, "rb");
        unsigned char info[54];
        fread(info, sizeof(unsigned char), 54, f);

        int ancho = *(int*)&info[18];
        int alto = *(int*)&info[22];

        int size = 3 * ancho * alto;
        *sizes = size;
        unsigned char* data = new unsigned char[size];
        fread(data, sizeof(unsigned char), size, f);
        fclose(f);
        for(i = 0; i < size; i += 3)
        {
                unsigned char tmp = data[i];
                data[i] = data[i+2];
                data[i+2] = tmp;
        }

        return data;
    }

    int main(int argc,char **argv){
      int sizes,i,world_rank,world_size;
      clock_t t1,t2;
      double tiemp;
      t1 = clock();

      MPI_Init(&argc, &argv);
      MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
      MPI_Comm_size(MPI_COMM_WORLD, &world_size);
      unsigned char* data1;
      unsigned char* data2;
      int root = 0;
      if(world_rank==0){
      data1= BMP(argv[1],&sizes);
      data2= BMP(argv[2],&sizes);
      printf("%d",sizes);
      }
      MPI_Bcast(&sizes,1,MPI_INT,root,MPI_COMM_WORLD);
      int num_elements_por_proc = sizes/world_size;
      unsigned char* subdata2=new unsigned char[num_elements_por_proc];
      unsigned char* subdata1=new unsigned char[num_elements_por_proc];
      MPI_Scatter( data1, num_elements_por_proc, MPI_UNSIGNED_CHAR, subdata1, num_elements_por_proc, MPI_UNSIGNED_CHAR, root, MPI_COMM_WORLD );
      MPI_Scatter( data2, num_elements_por_proc, MPI_UNSIGNED_CHAR, subdata2, num_elements_por_proc, MPI_UNSIGNED_CHAR, root, MPI_COMM_WORLD );
      int bol = 0;
      if(world_rank!=0){


        for(i=0;i<=num_elements_por_proc;i++){
          if(subdata1[i]!=subdata2[i]){
            bol = 1;
            break;
          }
         }
     }
     int bolls;
     MPI_Reduce(&bol,&bolls,1, MPI_INT, MPI_SUM, 0,MPI_COMM_WORLD);

     if(world_rank==0){
      if(bolls !=0){
        printf("The images are not the samen");}
      else{
        printf("The images are the same \n" );}

     t2 = clock();
     tiemp = ((double) (t2 - t1)) / (CLOCKS_PER_SEC);
     printf("%f\n",tiemp );
     }
     MPI_Finalize();
     return 0;
     }

Answer 1

此代码不适合并行化。您的瓶颈很可能只是读取文件。即使文件已经在根进程的内存中，发送数据然后只查看每个数据元素（实际上只有其中的 1/3）一次，也不会比在根进程本身上更快。

这里利用并行性的唯一方法是存储分布式文件，并分布式读取它们。然后你可以计算每个节点上的哈希值并进行比较。

补充几点：

考虑使用 MPI_LOR（逻辑或）来减少而不是加法
std::swap 而不是 tmp
即使在示例代码中，也要将每个新建与删除配对。
正确格式化您的代码。为了您自己，也为了必须在这里阅读它的人们。如果你很懒，可以使用像 clang-format.

Answer 2

除了如@Zulan 所解释的 I/O 绑定之外，您的算法有一个基本的属性，这使得它不适合并行化。要理解为什么，请看下面专门构造的极端案例。

您有两张图片，它们仅在第一个（线性化时）像素不同，其他方面相同。你现在把图像分成 N 个部分，并将它们分配到 N 个等级进行比较。第一列立即发现差异，打破循环，进入 MPI_Reduce 调用，但其他 N-1 列必须遍历其整个迭代范围才能得出图像部分相同的结论. MPI_Reduce 是一项集体行动，只有在所有参与队伍都调用后才会完成，换句话说，在 N-1 队伍完全检查他们的图像片段之前不会完成。

串行程序会在第一次迭代时发现差异并立即中断循环。这是一个明显的例子，并行版本根本不能更快，相反要慢得多。它还说明了 负载不平衡 的示例 - 不同的进程执行不同数量的工作，较快的进程必须等待较慢的进程完成。您可以实施某种通知机制，并让第一名完成通知其他人，以便他们可以打破他们的比较循环。这更适合在具有 OpenMP 等范例的共享内存系统上实现，尽管后者的取消机制是有代价的。

另一个极端，如果图像相同，那么并行程序会比串行程序快运行 N 倍。如果图像的第 (length/N) 个像素不同，则并行版本将花费与串行版本相同的时间。

并行加速因此非常不可预测并且对实际输入非常敏感。

MPI BMP 图像比较更高效

MPI BMP Image comparison more efficient

c++

image

mpi