mã C song song cho tính toán khoảng cách

Question

Tôi có mã C tính toán khoảng cách giữa hai bộ nút (ba tọa độ mỗi), mặc dù mã của tôi đã đủ nhanh nhưng tôi muốn tăng thêm một chút bằng cách sử dụng tính toán song song. Tôi đã tìm thấy một số thông tin về openMP và tôi đang cố gắng sử dụng nó ngay bây giờ, nhưng có một chút gì đó kỳ lạ. Nếu không có omp mã cpu thời gian là 20s, thêm hai dòng pragma phải mất 160s! Làm thế nào nó có thể xảy ra?

tôi thêm mã của tôi xuống đây

float computedist(float **vG1, float **vG2, int ncft, int ntri2, int jump, float *dist){ 
    int k = 0, i, j; 
    float min = 0; 
    float max = 0; 
    float avg = 0; 
    float *d = malloc(3*sizeof(float)); 
    float diff; 

    #pragma omp parallel 
    for(i=0;i<ncft;i+=jump){ 
     #pragma omp parallel 
     for(j=0;j<ntri2;j++){ 
      d[0] = vG1[i][0] - vG2[j][0]; 
      d[1] = vG1[i][1] - vG2[j][1]; 
      d[2] = vG1[i][2] - vG2[j][2]; 
      diff = sqrt(pow(d[0],2) + pow(d[1],2) + pow(d[2],2)); 
      if(j==0) 
       dist[k] = diff; 
      else 
       if(diff<dist[k]) 
        dist[k] = diff; 

     } 
     avg += dist[k]; 
     if(dist[k]>max) 
      max = dist[k]; 
     k++; 
    } 

    printf("max distance: %f\n",max); 
    printf("average distance: %f\n",avg/(int)(ncft/jump)); 

    free(d); 

    return max; 
} 

Cảm ơn bạn rất nhiều vì đã giúp đỡ bất kỳ

Answer 1

(Câu trả lời dưới đây đề cập đến mã ban đầu trong câu hỏi, mà kể từ đó đã được cải thiện với việc áp dụng những gợi ý)

---

Bạn cần phải đọc thêm về cách sử dụng OpenMP. Thông số kỹ thuật có sẵn tại http://www.openmp.org; và có các liên kết đến các hướng dẫn và các tài nguyên khác.

Tôi sẽ chỉ ra một số vấn đề trong mã của bạn và đưa ra đề xuất cách khắc phục những vấn đề đó.

float *d = malloc(3*sizeof(float)); 
    float diff; 

d được sử dụng như là một biến tạm thời, vì vậy nên được đánh dấu là private trong #pragma omp parallel for (xem bên dưới) để tránh các cuộc đua dữ liệu. Trong khi đó, thay vì phân bổ động, tôi sẽ chỉ sử dụng 3 float riêng biệt. diff cũng giữ giá trị tạm thời, vì vậy cũng phải là private.

#pragma omp parallel 
    for(i=0;i<ncft;i+=jump){ 
     #pragma omp parallel 
     for(j=0;j<ntri2;j++){ 

Bạn tạo ra một khu vực song song nơi mà mỗi thread thực thi toàn bộ vòng lặp (vì khu vực này không chứa bất kỳ cấu trúc chia sẻ công việc), và bên trong nó, bạn tạo ra một khu vực lồng nhau với một mới (!) Tập hợp các chủ đề, cũng từng thực hiện toàn bộ vòng lặp bên trong. Nó cho biết thêm rất nhiều chi phí và tính toán không cần thiết cho chương trình của bạn. Những gì bạn cần là #pragma omp parallel for và chỉ áp dụng cho vòng lặp bên ngoài.

  d[0] = vG1[i][0] - vG2[j][0]; 
      d[1] = vG1[i][1] - vG2[j][1]; 
      d[2] = vG1[i][2] - vG2[j][2]; 
      diff = sqrt(pow(d[0],2) + pow(d[1],2) + pow(d[2],2)); 

Không liên quan đến song song, nhưng tại sao gọi pow chỉ để tính toán hình vuông? Một phép nhân cũ tốt sẽ dễ đọc và nhanh hơn.

  if(j==0) 
       dist[k] = diff; 
      else 
       if(diff<dist[k]) 
        dist[k] = diff; 

Kể từ khi hành động là như nhau (dist[k]=diff;), các mã có thể được đơn giản hóa bằng cách kết hợp hai điều kiện với || (logic hay).

 } 
     avg += dist[k]; 
     if(dist[k]>max) 
      max = dist[k]; 

Tại đây bạn tính giá trị tổng hợp trên vòng ngoài.Trong OpenMP, điều này được thực hiện với mệnh đề reduction của #pragma omp for.

 k++; 
    } 

Hiện tại, bạn tăng k tại mỗi lần lặp, do đó tạo ra một sự phụ thuộc không cần thiết giữa lặp dẫn đến một cuộc chạy đua dữ liệu trong mã song song. Theo mã của bạn, k chỉ là một "bí danh" thuận tiện cho i/jump - vì vậy chỉ cần gán nó như vậy ở đầu lặp lại và tạo private.

Answer 2

Bạn sử dụng rất nhiều đồng bộ hóa khi bạn thêm #pragma omp parallel trên cả hai vòng ngoài và vòng trong.

Khi sử dụng #pragma omp parallel, có barrier sau vòng lặp, vì vậy tất cả các chuỗi chờ cho đến khi chuỗi cuối cùng kết thúc.
Trong trường hợp của bạn, bạn phải chờ cho tất cả các chủ đề cả trong vòng lặp bên trong và cả trong vòng ngoài, do đó bạn nhận được rất nhiều chi phí cho việc sử dụng đồng bộ hóa.

Thường tốt nhất là chỉ sử dụng #pragma omp parallel trên vòng ngoài [giả sử có đủ công việc để thực hiện ...] để giảm thiểu số lượng rào cản.

Answer 3

Trong mã của bạn, bạn viết vào một mảng chung cho tất cả các chủ đề, dist. Có lẽ bạn đang gặp sự cố chia sẻ sai ở đó. Cố gắng phân bổ mảng đó bằng đệm.