kmeans演算法並行化的mpi程式

来源:http://www.cnblogs.com/LCcnblogs/archive/2016/10/30/6013961.html
-Advertisement-
Play Games

用c語言寫了kmeans演算法的串列程式，再用mpi來寫並行版的，貌似參照著串列版來寫並行版，效果不是很賞心悅目~ 並行化思路： 使用主從模式。由一個節點充當主節點負責數據的劃分與分配，其他節點完成本地數據的計算，並將結果返回給主節點。大致過程如下： 1、進程0為主節點，先從文件中讀取數據集，然後將數 ...


　　用c語言寫了kmeans演算法的串列程式，再用mpi來寫並行版的，貌似參照著串列版來寫並行版，效果不是很賞心悅目~

　　

　　並行化思路：

　　使用主從模式。由一個節點充當主節點負責數據的劃分與分配，其他節點完成本地數據的計算，並將結果返回給主節點。大致過程如下：

　　1、進程0為主節點，先從文件中讀取數據集，然後將數據集劃分並傳給其他進程；

　　2、進程0選擇每個聚類的中心點，併發送給其他進程；

　　3、其他進程計算數據塊中每個點到中心點的距離，然後標出每個點所屬的聚類，並計算每個聚類所有點到其中心點的距離之和，最後將這些結果返回給進程0；

　　4、進程0計算出新的中心點併發送給其他進程，並計算其他進程傳來的聚類所有點到其中心點的距離總和；

　　5、重覆3和4直到，直到步驟4中的所有聚類的距離之和不變（即收斂）。

 

　　code:

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <math.h>
  4 #include <time.h>
  5 #include "mpi.h"
  6 
  7 int  main(int argc,char *argv[])
  8 {
  9     int i,j;
 10     MPI_Status status;
 11     float temp1,temp2;
 12     int K,N,D;  //聚類的數目，數據量，數據的維數
 13     float **data;  //存放數據
 14     int *all_in_cluster;  //進程0標記每個點屬於哪個聚類
 15     int *local_in_cluster;  //其他進程標記每個點屬於哪個聚類
 16     int *in_cluster;  //進程0標記每個點屬於哪個聚類
 17     int count=0;
 18     float *sum_diff;
 19     float *global_sum_diff;
 20     float **cluster_center;  //存放每個聚類的中心點
 21     int rank,size;
 22     float **array(int m,int n);
 23     float **loadData(int *k,int *d,int *n);
 24     float getDistance(float avector[],float bvector[],int n);
 25     void cluster(int n,int k,int d,float **data,float **cluster_center,int *local_in_cluster);
 26     float getDifference(int k,int n,int d,int *in_cluster,float **data,float **cluster_center,float *sum);
 27     void getCenter(int k,int d,int n,int *in_cluster,float **data,float **cluster_center);
 28 
 29     MPI_Init(&argc,&argv);
 30     MPI_Comm_rank(MPI_COMM_WORLD,&rank);
 31     MPI_Comm_size(MPI_COMM_WORLD,&size);
 32     if(!rank){
 33         data=loadData(&K,&D,&N);  //進程0讀入數據
 34         if(size==1||size>N||N%(size-1))    MPI_Abort(MPI_COMM_WORLD,1);  //若不滿足條件則退出
 35     }
 36     MPI_Bcast(&K,1,MPI_INT,0,MPI_COMM_WORLD);  //進程0廣播
 37     MPI_Bcast(&N,1,MPI_INT,0,MPI_COMM_WORLD);  
 38     MPI_Bcast(&D,1,MPI_INT,0,MPI_COMM_WORLD);  
 39     if(rank)    data=array(N/(size-1),D);  //其他進程分配存儲數據集的空間
 40     all_in_cluster=(int *)malloc(N/(size-1)*size*sizeof(int));  //用於進程0
 41     local_in_cluster=(int *)malloc(N/(size-1)*sizeof(int));  //用於每個進程
 42     in_cluster=(int *)malloc(N*sizeof(int));  //用於進程0
 43     sum_diff=(float *)malloc(K*sizeof(float));  //進程中每個聚類的數據點與其中心點的距離之和
 44     global_sum_diff=(float *)malloc(K*sizeof(float));
 45     for(i=0;i<K;i++)    sum_diff[i]=0.0;  //初始化
 46 
 47     if(!rank){  //進程0向其他進程分配數據集
 48         for(i=0;i<N;i+=(N/(size-1)))
 49             for(j=0;j<(N/(size-1));j++)
 50                 MPI_Send(data[i+j],D,MPI_FLOAT,(i+j)/(N/(size-1))+1,99,MPI_COMM_WORLD);  
 51         printf("Data sets:\n");
 52         for(i=0;i<N;i++)
 53             for(j=0;j<D;j++){
 54                 printf("%-8.2f",data[i][j]);
 55                 if((j+1)%D==0)    putchar('\n');
 56             }
 57            printf("-----------------------------\n");
 58     }else{  //其他進程接收進程0數據
 59         for(i=0;i<(N/(size-1));i++)
 60             MPI_Recv(data[i],D,MPI_FLOAT,0,99,MPI_COMM_WORLD,&status);
 61     }
 62     MPI_Barrier(MPI_COMM_WORLD);  //同步一下
 63     cluster_center=array(K,D);  //中心點 
 64     if(!rank){  //進程0產生隨機中心點
 65         srand((unsigned int)(time(NULL)));  //隨機初始化k個中心點
 66         for(i=0;i<K;i++)
 67             for(j=0;j<D;j++)
 68                 cluster_center[i][j]=data[(int)((double)N*rand()/(RAND_MAX+1.0))][j];
 69     }
 70     for(i=0;i<K;i++)    MPI_Bcast(cluster_center[i],D,MPI_FLOAT,0,MPI_COMM_WORLD);  //進程0向其他進程廣播中心點
 71     if(rank){
 72         cluster(N/(size-1),K,D,data,cluster_center,local_in_cluster);  //其他進程進行聚類
 73         getDifference(K,N/(size-1),D,local_in_cluster,data,cluster_center,sum_diff);
 74         for(i=0;i<N/(size-1);i++)
 75             printf("data[%d] in cluster-%d\n",(rank-1)*(N/(size-1))+i,local_in_cluster[i]+1);
 76     }
 77     MPI_Gather(local_in_cluster,N/(size-1),MPI_INT,all_in_cluster,N/(size-1),MPI_INT,0,MPI_COMM_WORLD);  //全收集於進程0
 78     MPI_Reduce(sum_diff,global_sum_diff,K,MPI_FLOAT,MPI_SUM,0,MPI_COMM_WORLD);  //歸約至進程0,進程中每個聚類的數據點與其中心點的距離之和
 79     if(!rank){  
 80         for(i=N/(size-1);i<N+N/(size-1);i++) 
 81             in_cluster[i-N/(size-1)]=all_in_cluster[i];  //處理收集的標記數組
 82         temp1=0.0;
 83         for(i=0;i<K;i++) temp1+=global_sum_diff[i];
 84         printf("The difference between data and center is: %.2f\n\n", temp1);
 85         count++;
 86     }
 87     MPI_Bcast(&temp1,1,MPI_FLOAT,0,MPI_COMM_WORLD);
 88     MPI_Barrier(MPI_COMM_WORLD);
 89 
 90     do{   //比較前後兩次迭代，若不相等繼續迭代
 91         temp1=temp2;
 92         if(!rank)    getCenter(K,D,N,in_cluster,data,cluster_center);  //更新中心點
 93         for(i=0;i<K;i++)    MPI_Bcast(cluster_center[i],D,MPI_FLOAT,0,MPI_COMM_WORLD);  //廣播中心點    
 94         if(rank){
 95             cluster(N/(size-1),K,D,data,cluster_center,local_in_cluster);  //其他進程進行聚類
 96             for(i=0;i<K;i++)    sum_diff[i]=0.0;
 97             getDifference(K,N/(size-1),D,local_in_cluster,data,cluster_center,sum_diff);
 98             for(i=0;i<N/(size-1);i++)
 99                 printf("data[%d] in cluster-%d\n",(rank-1)*(N/(size-1))+i,local_in_cluster[i]+1);
100         }
101         MPI_Gather(local_in_cluster,N/(size-1),MPI_INT,all_in_cluster,N/(size-1),MPI_INT,0,MPI_COMM_WORLD);
102         if(!rank)
103             for(i=0;i<K;i++)    global_sum_diff[i]=0.0;
104         MPI_Reduce(sum_diff,global_sum_diff,K,MPI_FLOAT,MPI_SUM,0,MPI_COMM_WORLD);
105         if(!rank){
106             for(i=N/(size-1);i<N+N/(size-1);i++) 
107                 in_cluster[i-N/(size-1)]=all_in_cluster[i];
108             temp2=0.0;
109             for(i=0;i<K;i++) temp2+=global_sum_diff[i];
110             printf("The difference between data and center is: %.2f\n\n", temp2);
111             count++;
112         }
113         MPI_Bcast(&temp2,1,MPI_FLOAT,0,MPI_COMM_WORLD);
114         MPI_Barrier(MPI_COMM_WORLD);
115     }while(fabs(temp2-temp1)!=0.0);
116     if(!rank)    printf("The total number of cluster is: %d\n\n",count);
117     MPI_Finalize();
118 }
119 
120 
121 //動態創建二維數組
122 float **array(int m,int n)
123 {
124     int i;
125     float **p;
126     p=(float **)malloc(m*sizeof(float *));
127     p[0]=(float *)malloc(m*n*sizeof(float));
128     for(i=1;i<m;i++)    p[i]=p[i-1]+n;
129     return p;
130 }
131 
132 //從data.txt導入數據，要求首行格式：K=聚類數目,D=數據維度,N=數據量
133 float **loadData(int *k,int *d,int *n)
134 {
135     float **array(int m,int n);
136     int i,j;
137     float **arraydata;
138     FILE *fp;
139     if((fp=fopen("data.txt","r"))==NULL)    fprintf(stderr,"cannot open data.txt!\n");
140     if(fscanf(fp,"K=%d,D=%d,N=%d\n",k,d,n)!=3)    fprintf(stderr,"load error!\n");
141     arraydata=array(*n,*d);  //生成數據數組
142     for(i=0;i<*n;i++)
143         for(j=0;j<*d;j++)
144             fscanf(fp,"%f",&arraydata[i][j]);  //讀取數據點
145     return arraydata;
146 }
147 
148 //計算歐幾裡得距離
149 float getDistance(float avector[],float bvector[],int n)
150 {
151     int i;
152     float sum=0.0;
153     for(i=0;i<n;i++)
154         sum+=pow(avector[i]-bvector[i],2);
155     return sqrt(sum);
156 }
157 
158 //把N個數據點聚類，標出每個點屬於哪個聚類
159 void cluster(int n,int k,int d,float **data,float **cluster_center,int *local_in_cluster)
160 {
161     int i,j;
162     float min;
163     float **distance=array(n,k);  //存放每個數據點到每個中心點的距離
164     for(i=0;i<n;++i){
165         min=9999.0;
166         for(j=0;j<k;++j){
167             distance[i][j] = getDistance(data[i],cluster_center[j],d);
168             if(distance[i][j]<min){
169             min=distance[i][j];
170             local_in_cluster[i]=j;
171         }
172        }
173     }
174     printf("-----------------------------\n");
175     free(distance);
176 }
177 
178 //計算所有聚類的中心點與其數據點的距離之和
179 float getDifference(int k,int n,int d,int *in_cluster,float **data,float **cluster_center,float *sum)
180 {
181     int i,j;
182     for(i=0;i<k;++i)
183         for(j=0;j<n;++j)
184             if(i==in_cluster[j])
185                 sum[i]+=getDistance(data[j],cluster_center[i],d);
186 }
187 
188 //計算每個聚類的中心點
189 void getCenter(int k,int d,int n,int *in_cluster,float **data,float **cluster_center)
190 {
191     float **sum=array(k,d);  //存放每個聚類中心
192     int i,j,q,count;
193     for(i=0;i<k;i++)
194         for(j=0;j<d;j++)
195             sum[i][j]=0.0;
196     for(i=0;i<k;i++){
197         count=0;  //統計屬於某個聚類內的所有數據點
198         for(j=0;j<n;j++){
199             if(i==in_cluster[j]){
200                 for(q=0;q<d;q++)
201                     sum[i][q]+=data[j][q];  //計算所屬聚類的所有數據點的相應維數之和
202                 count++;
203             }
204         }
205         for(q=0;q<d;q++)
206             cluster_center[i][q]=sum[i][q]/count;
207     }
208     printf("The new center of cluster is:\n");
209         for(i = 0; i < k; i++)
210             for(q=0;q<d;q++){
211                 printf("%-8.2f",cluster_center[i][q]);
212                 if((q+1)%d==0)    putchar('\n');
213     }
214     free(sum);
215 }

　　

 1 //生成測試數據
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<time.h>
 5 #define N 1000
 6 
 7 int main()
 8 {
 9     int i;
10     float a;
11     int k,d,n;
12     FILE *fp;
13     fprintf(stdout,"input(k d n):");
14     scanf("%d%d%d",&k,&d,&n);
15     if((fp=fopen("data.txt","w"))==NULL)    exit(1);
16     fprintf(fp,"K=%d,D=%d,N=%d\n",k,d,n);
17     srand((unsigned int)(time(NULL)));
18     for(i=1;i<=d*n;i++){
19         a=(int)(1.0+(double)N*rand()/(RAND_MAX+1.0));
20         fprintf(fp,"%.2f ",a);
21         if(i%d==0) putc('\n',fp);
22     }
23     if(fclose(fp)) exit(2);
24 }

 

　　實驗：

　　聚類數K=10，數據的維度D=2，單位(秒)：

數據量N

10000

100000

500000

串列

1

21

109

並行(2個進程)

2

25

101

並行(3個進程)

3

26

101

　　

 

 

 

 

 

　　分析：電腦配置是奔騰雙核，按照該並行程式，一個核心用作主節點以分配數據集，另一個核心作為承擔了大多數計算任務的節點。當數據量較小時，並行程式花在進程間數據通信的時間占了總體時間的很大比重，所以並行程式耗時要多於串列程式。在本電腦CPU為兩個核心的環境下，當數據量較大時，並行程式與串列程式耗時相當或者稍微偏小。在CPU核心數在3個以上時，該並行程式的優勢才突顯出來。

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 簡易版的TimSort排序演算法
    歡迎探討，如有錯誤敬請指正 如需轉載，請註明出處http://www.cnblogs.com/nullzx/ 1. 簡易版本TimSort排序演算法原理與實現 TimSort排序演算法是Python和Java針對對象數組的預設排序演算法。TimSort排序演算法的本質是歸併排序演算法，只是在歸併排序演算法上進行... ...
  • Android 進程通信機制之 AIDL
    什麼是 AIDL AIDL 全稱 Android Interface Definition Language，即 安卓介面描述語言。聽起來很深奧，其實它的本質就是生成進程間通信介面的輔助工具。它的存在形式是一種 .aidl 文件，開發者需要做的就是在該文件中定義進程間通信的介面，編譯的時候 IDE ...
  • 哈夫曼樹的數組實現
    哈夫曼樹的數組實現 （本篇博客是本人第一篇數據結構的博客，有什麼不足還望各位看官指出！！） 題目來源：SOJ 1000. Huffman Coding V1,V3 題目描述 V3： Description 對輸入的英文大寫字母序列進行統計概率，然後構建Huffman樹，得出每個字母的Huffman編 ...
  • Android單元測試與模擬測試詳解
    測試與基本規範 為什麼需要測試? 為了穩定性，能夠明確的瞭解是否正確的完成開發。 更加易於維護，能夠在修改代碼後保證功能不被破壞。 集成一些工具，規範開發規範，使得代碼更加穩定( 如通過 phabricator differential 發diff時提交需要執行的單元測試，在開發流程上就可以保證遠端 ...
  • Python內置函數(29)——help
    英文文檔： help([object]) Invoke the built-in help system. (This function is intended for interactive use.) If no argument is given, the interactive help s ...
  • springmvc 返回xml
    需求： 1、springmvc返回xml； 技術及環境： 實現： spirngxml的配置主要如下： 添加項目依賴： 實體類JavaBean 一個簡單的JavaBean，添加了JAXB 註解，spring將會根據請求判斷轉換成xml。JAXB不需要添加額外的依賴庫，已經包含在jdk中。 spring ...
  • Java的二維數組的應用及楊輝三角的編寫
    （1） 編寫一個程式，生成一個10*10的二維隨機整數數組，並將該數組的每行最大值保存於一個一維數組中，將每列平均值保存於另外一個一維數組中並分別輸出。 （2） 編程輸出楊輝三角的前10行。 找出一個，即該位置上的元素在該行上最大，在該列上最小（註：一個二維數組也可能沒有這樣的鞍點）。 /** * ...
  • [Java]簡單的JSON庫（重覆造輪子系列）
    話說好久沒更新這個博客了 都快忘記還有博客這件事了.... 因為之前在造一個簡單的HTTP框架的輪子，裡面用了JSON...當時隨便拉了個FastJSON的庫就用了，然而...嗯，毫無疑問，輪子還是要自己造才好玩，雖然不會在生產環境用，但是寫和不寫多少還是有些差距的 於是今天就造了這個簡單的JSON ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類