MPI并行K-means算法代码性能优化方案咨询

针对你的MPI并行K-means代码，以下是具体的性能优化策略，重点解决点对点通信的开销问题：

一、用集合通信替代点对点循环通信 #

MPI集合通信（如广播、聚集）专为多进程批量数据传输设计，比循环调用MPI_Send/MPI_Recv效率更高，能减少通信次数和延迟。

1. 广播聚类中心替代循环发送 #

原代码中master进程循环给每个slave发送centroids，可替换为MPI_Bcast：

• Master端：删除循环发送的代码，替换为：

  MPI_Bcast(centroidi, nCentroidi, MPI_PUNTO, 0, MPI_COMM_WORLD);
  

• Slave端：删除MPI_Recv(centroidi,...)，替换为同样的MPI_Bcast调用。

2. 聚集聚类结果替代循环接收 #

由于最后一个slave处理的点数比其他多（含resto），使用MPI_Gatherv适配不均等数据分发：

• Master端：先准备接收计数和偏移数组，再调用聚集：

  // 提前初始化recvcounts和displs（放在循环外）
  int *recvcounts = malloc(size * sizeof(int));
  int *displs = malloc(size * sizeof(int));
  recvcounts[0] = 0;
  displs[0] = 0;
  for (int i=1; i<size; i++) {
      recvcounts[i] = (i == size-1 && resto != 0) ? nPuntiSlave + resto : nPuntiSlave;
      displs[i] = (i-1)*nPuntiSlave;
  }
  
  // 替换循环recv
  MPI_Gatherv(MPI_IN_PLACE, 0, MPI_INT, suddivisione_attuale, recvcounts, displs, MPI_INT, 0, MPI_COMM_WORLD);
  

• Slave端：删除MPI_Send(suddivisione_attuale,...)，替换为：

  MPI_Gatherv(suddivisione_attuale, nPunti, MPI_INT, NULL, NULL, NULL, MPI_INT, 0, MPI_COMM_WORLD);
  

3. 广播终止标志替代循环发送 #

原master循环发送flag的代码，替换为：

MPI_Bcast(&flag, 1, MPI_INT, 0, MPI_COMM_WORLD);

Slave端同样用MPI_Bcast接收flag，替代原来的MPI_Recv。

二、优化初始数据分发 #

原代码循环发送初始点给slave，用MPI_Scatterv一次性完成数据分发：

• Master端：复用上面的recvcounts和displs数组，替换循环Send：

  MPI_Scatterv(punti, recvcounts, displs, MPI_PUNTO, NULL, 0, MPI_PUNTO, 0, MPI_COMM_WORLD);
  

• Slave端：删除循环接收的代码，替换为：

  MPI_Scatterv(NULL, NULL, NULL, MPI_PUNTO, punti, nPunti, MPI_PUNTO, 0, MPI_COMM_WORLD);
  

三、计算逻辑优化（间接降低通信延迟） #

减少计算耗时能让进程更快进入通信阶段，避免通信等待：

1. 移除冗余的距离缩放：原代码中距离计算的*100缩放不影响聚类结果（仅需相对比较），可直接删除，同时用乘法替代pow函数提升计算速度：
   将：

   double distanza_minima = (pow((punti[i].x-centroidi[0].x)*100,2)+pow((punti[i].y-centroidi[0].y)*100,2));
   

   修改为：

   double dx = punti[i].x - centroidi[0].x;
   double dy = punti[i].y - centroidi[0].y;
   double distanza_minima = dx*dx + dy*dy;
   

   内层循环的距离计算同理修改。

2. 避免重复内存分配：Master端每次循环中malloc(popolazione)可移到循环外，每次迭代仅重置数组值为0即可，减少内存分配开销。

四、修复MPI自定义类型的错误 #

原代码中MPI_PUNTO类型定义存在偏移错误，正确的自定义类型应使用offsetof获取结构体成员的偏移量：

MPI_Datatype MPI_PUNTO;
MPI_Datatype types[] = {MPI_DOUBLE, MPI_DOUBLE};
int blocklen[] = {1, 1};
MPI_Aint disp[] = {offsetof(Punto, x), offsetof(Punto, y)};
MPI_Type_create_struct(2, blocklen, disp, types, &MPI_PUNTO);
MPI_Type_commit(&MPI_PUNTO);

这样能确保数据传输的正确性。

补充优化：内存泄漏修复 #

代码中多处malloc的内存未释放，需在程序结束前添加free操作，例如：

• Master端：free(punti); free(centroidi); free(nuovi_centroidi); free(suddivisione_attuale); free(ex_suddivisione); free(recvcounts); free(displs);
• Slave端：free(punti); free(centroidi); free(suddivisione_attuale);

内容的提问来源于stack exchange，提问作者Roberto