【CUDA并行编程之六】KNN算法的并行实现-蒲公英云

之前写了两篇文章一个是KNN算法的C++串行实现，另一个是CUDA计算向量的欧氏距离。那么这篇文章就可以说是前两篇文章的一个简单的整合。在看这篇文章之前可以先阅读前两篇文章。

一、生成数据集

现在需要生成一个N个D维的数据，没在一组数据都有一个类标，这个类标根据第一维的正负来进行标识样本数据的类标：Positive and Negative。

[python] view plain copy

#!/usr/bin/python
import re
import sys
import random
import os
filename = “input.txt”
if(os.path.exists(filename)):
print(“%s exists and del” % filename)
os.remove(filename)
fout = open(filename,”w”)
for i in range( 0,int(sys.argv[1]) ): #str to int
x = []
for j in range(0,int(sys.argv[2])):
x.append( “%4f” % random.uniform(-1,1) ) #generate random data and limit the digits into 4
fout.write(“%s\t” % x[j])
#fout.write(x) : TypeError:expected a character buffer object
if(x[0][0] == ‘-‘):
fout.write(“ Negative”+“\n”)
else:
fout.write(“ Positive”+“\n”)
fout.close()

运行程序，生成4000个维度为8的数据：

SouthEast

生成了文件”input.txt”：

SouthEast 1

二、串行代码：

这个代码和之前的文章的代码一致，我们选择400个数据进行作为测试数据，3600个数据进行训练数据。

KNN_2.cc：

[cpp] view plain copy

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef string tLabel;
typedef double tData;
typedef pair<int,double> PAIR;
const int MaxColLen = 10;
const int MaxRowLen = 10000;
ifstream fin;
class KNN
{
private:
tData dataSet[MaxRowLen][MaxColLen];
tLabel labels[MaxRowLen];
tData testData[MaxColLen];
int rowLen;
int colLen;
int k;
int test_data_num;
map<int,double> map_index_dis;
map map_label_freq;
double get_distance(tData *d1,tData *d2);
public:
KNN(int k , int rowLen , int colLen , char *filename);
void get_all_distance();
tLabel get_max_freq_label();
void auto_norm_data();
void get_error_rate();
struct CmpByValue
{
bool operator() (const PAIR& lhs,const PAIR& rhs)
{
return lhs.second < rhs.second;
}
};
~KNN();
};
KNN::~KNN()
{
fin.close();
map_index_dis.clear();
map_label_freq.clear();
}
KNN::KNN(int k , int row ,int col , char *filename)
{
this->rowLen = row;
this->colLen = col;
this->k = k;
test_data_num = 0;
fin.open(filename);
if( !fin )
{
cout<<”can not open the file”<<endl;
exit(0);
}
//read data from file
for(int i=0;i<rowLen;i++)
{
for(int j=0;j<colLen;j++)
{
fin>>dataSet[i][j];
}
fin>>labels[i];
}
}
void KNN:: get_error_rate()
{
int i,j,count = 0;
tLabel label;
cout<<”please input the number of test data : “<<endl;
cin>>test_data_num;
for(i=0;i<test_data_num;i++)
{
for(j=0;j<colLen;j++)
{
testData[j] = dataSet[i][j];
}
get_all_distance();
label = get_max_freq_label();
if( label!=labels[i] )
count++;
map_index_dis.clear();
map_label_freq.clear();
}
cout<<”the error rate is = “<<(double)count/(double)test_data_num<<endl;
}
double KNN:: get_distance(tData *d1,tData *d2)
{
double sum = 0;
for(int i=0;i<colLen;i++)
{
sum += pow( (d1[i]-d2[i]) , 2 );
}
//cout<<”the sum is = “<<sum<<endl;
return sqrt(sum);
}
//get distance between testData and all dataSet
void KNN:: get_all_distance()
{
double distance;
int i;
for(i=test_data_num;i<rowLen;i++)
{
distance = get_distance(dataSet[i],testData);
map_index_dis[i] = distance;
}
}
tLabel KNN:: get_max_freq_label()
{
vector vec_index_dis( map_index_dis.begin(),map_index_dis.end() );
sort(vec_index_dis.begin(),vec_index_dis.end(),CmpByValue());
for(int i=0;i<k;i++)
{
/*
cout<<”the index = “<<vec_index_dis[i].first<<” the distance = “<<vec_index_dis[i].second<<” the label = “<<labels[ vec_index_dis[i].first ]<<” the coordinate ( “;
int j;
for(j=0;j<colLen-1;j++)
{
cout<<dataSet[ vec_index_dis[i].first ][j]<<”,”;
}
cout<<dataSet[ vec_index_dis[i].first ][j]<<” )”<<endl;
*/
map_label_freq[ labels[ vec_index_dis[i].first ] ]++;
}
map::const_iterator map_it = map_label_freq.begin();
tLabel label;
int max_freq = 0;
while( map_it != map_label_freq.end() )
{
if( map_it->second > max_freq )
{
max_freq = map_it->second;
label = map_it->first;
}
map_it++;
}
//cout<<”The test data belongs to the “<<label<<” label”<<endl;
return label;
}
void KNN::auto_norm_data()
{
tData maxa[colLen] ;
tData mina[colLen] ;
tData range[colLen] ;
int i,j;
for(i=0;i<colLen;i++)
{
maxa[i] = max(dataSet[0][i],dataSet[1][i]);
mina[i] = min(dataSet[0][i],dataSet[1][i]);
}
for(i=2;i<rowLen;i++)
{
for(j=0;j<colLen;j++)
{
if( dataSet[i][j]>maxa[j] )
{
maxa[j] = dataSet[i][j];
}
else if( dataSet[i][j]<mina[j] )
{
mina[j] = dataSet[i][j];
}
}
}
for(i=0;i<colLen;i++)
{
range[i] = maxa[i] - mina[i] ;
//normalize the test data set
testData[i] = ( testData[i] - mina[i] )/range[i] ;
}
//normalize the training data set
for(i=0;i<rowLen;i++)
{
for(j=0;j<colLen;j++)
{
dataSet[i][j] = ( dataSet[i][j] - mina[j] )/range[j];
}
}
}
int main(int argc , char** argv)
{
int k,row,col;
char *filename;
if( argc!=5 )
{
cout<<”The input should be like this : ./a.out k row col filename”<<endl;
exit(1);
}
k = atoi(argv[1]);
row = atoi(argv[2]);
col = atoi(argv[3]);
filename = argv[4];
KNN knn(k,row,col,filename);
knn.auto_norm_data();
knn.get_error_rate();
return 0;
}

makefile：

[cpp] view plain copy

target:
g++ KNN_2.cc
./a.out 7 4000 8 input.txt
cu:
nvcc KNN.cu
./a.out 7 4000 8 input.txt

运行结果：

SouthEast 2

三、并行实现

并行实现的过程就是将没一个测试样本到N个训练样本的距离进行并行化，如果串行计算的话，时间复杂度为：O(N*D)，如果串行计算的话，时间复杂度为O(D)，其实D为数据的维度。

KNN.cu：

[cpp] view plain copy 在CODE上查看代码片派生到我的代码片

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef string tLabel;
typedef float tData;
typedef pair<int,double> PAIR;
const int MaxColLen = 10;
const int MaxRowLen = 10010;
const int test_data_num = 400;
ifstream fin;
class KNN
{
private:
tData dataSet[MaxRowLen][MaxColLen];
tLabel labels[MaxRowLen];
tData testData[MaxColLen];
tData trainingData[3600][8];
int rowLen;
int colLen;
int k;
map<int,double> map_index_dis;
map map_label_freq;
double get_distance(tData *d1,tData *d2);
public:
KNN(int k , int rowLen , int colLen , char *filename);
void get_all_distance();
tLabel get_max_freq_label();
void auto_norm_data();
void get_error_rate();
void get_training_data();
struct CmpByValue
{
bool operator() (const PAIR& lhs,const PAIR& rhs)
{
return lhs.second < rhs.second;
}
};
~KNN();
};
KNN::~KNN()
{
fin.close();
map_index_dis.clear();
map_label_freq.clear();
}
KNN::KNN(int k , int row ,int col , char *filename)
{
this->rowLen = row;
this->colLen = col;
this->k = k;
fin.open(filename);
if( !fin )
{
cout<<”can not open the file”<<endl;
exit(0);
}
for(int i=0;i<rowLen;i++)
{
for(int j=0;j<colLen;j++)
{
fin>>dataSet[i][j];
}
fin>>labels[i];
}
}
void KNN:: get_training_data()
{
for(int i=test_data_num;i<rowLen;i++)
{
for(int j=0;j<colLen;j++)
{
trainingData[i-test_data_num][j] = dataSet[i][j];
}
}
}
void KNN:: get_error_rate()
{
int i,j,count = 0;
tLabel label;
cout<<”the test data number is : “<<test_data_num<<endl;
get_training_data();
//get testing data and calculate
for(i=0;i<test_data_num;i++)
{
for(j=0;j<colLen;j++)
{
testData[j] = dataSet[i][j];
}
get_all_distance();
label = get_max_freq_label();
if( label!=labels[i] )
count++;
map_index_dis.clear();
map_label_freq.clear();
}
cout<<”the error rate is = “<<(double)count/(double)test_data_num<<endl;
}
//global function
__global__ void cal_dis(tData *train_data,tData *test_data,tData* dis,int pitch,int N , int D)
{
int tid = blockIdx.x;
if(tid<N)
{
tData temp = 0;
tData sum = 0;
for(int i=0;i<D;i++)
{
temp = *( (tData*)( (char*)train_data+tid*pitch )+i ) - test_data[i];
sum += temp * temp;
}
dis[tid] = sum;
}
}
//Parallel calculate the distance
void KNN:: get_all_distance()
{
int height = rowLen - test_data_num;
tData *distance = new tData[height];
tData *d_train_data,*d_test_data,*d_dis;
size_t pitch_d ;
size_t pitch_h = colLen * sizeof(tData);
//allocate memory on GPU
cudaMallocPitch( &d_train_data,&pitch_d,colLen*sizeof(tData),height);
cudaMalloc( &d_test_data,colLen*sizeof(tData) );
cudaMalloc( &d_dis, height*sizeof(tData) );
cudaMemset( d_train_data,0,height*colLen*sizeof(tData) );
cudaMemset( d_test_data,0,colLen*sizeof(tData) );
cudaMemset( d_dis , 0 , height*sizeof(tData) );
//copy training and testing data from host to device
cudaMemcpy2D( d_train_data,pitch_d,trainingData,pitch_h,colLen*sizeof(tData),height,cudaMemcpyHostToDevice);
cudaMemcpy( d_test_data,testData,colLen*sizeof(tData),cudaMemcpyHostToDevice);
//calculate the distance
cal_dis<<>>( d_train_data,d_test_data,d_dis,pitch_d,height,colLen );
//copy distance data from device to host
cudaMemcpy( distance,d_dis,height*sizeof(tData),cudaMemcpyDeviceToHost);
int i;
for( i=0;i<rowLen-test_data_num;i++ )
{
map_index_dis[i+test_data_num] = distance[i];
}
}
tLabel KNN:: get_max_freq_label()
{
vector vec_index_dis( map_index_dis.begin(),map_index_dis.end() );
sort(vec_index_dis.begin(),vec_index_dis.end(),CmpByValue());
for(int i=0;i<k;i++)
{
/*
cout<<”the index = “<<vec_index_dis[i].first<<” the distance = “<<vec_index_dis[i].second<<” the label = “<<labels[ vec_index_dis[i].first ]<<” the coordinate ( “;
int j;
for(j=0;j<colLen-1;j++)
{
cout<<dataSet[ vec_index_dis[i].first ][j]<<”,”;
}
cout<<dataSet[ vec_index_dis[i].first ][j]<<” )”<<endl;
*/
map_label_freq[ labels[ vec_index_dis[i].first ] ]++;
}
map::const_iterator map_it = map_label_freq.begin();
tLabel label;
int max_freq = 0;
while( map_it != map_label_freq.end() )
{
if( map_it->second > max_freq )
{
max_freq = map_it->second;
label = map_it->first;
}
map_it++;
}
cout<<”The test data belongs to the “<<label<<” label”<<endl;
return label;
}
void KNN::auto_norm_data()
{
tData maxa[colLen] ;
tData mina[colLen] ;
tData range[colLen] ;
int i,j;
for(i=0;i<colLen;i++)
{
maxa[i] = max(dataSet[0][i],dataSet[1][i]);
mina[i] = min(dataSet[0][i],dataSet[1][i]);
}
for(i=2;i<rowLen;i++)
{
for(j=0;j<colLen;j++)
{
if( dataSet[i][j]>maxa[j] )
{
maxa[j] = dataSet[i][j];
}
else if( dataSet[i][j]<mina[j] )
{
mina[j] = dataSet[i][j];
}
}
}
for(i=0;i<colLen;i++)
{
range[i] = maxa[i] - mina[i] ;
//normalize the test data set
testData[i] = ( testData[i] - mina[i] )/range[i] ;
}
//normalize the training data set
for(i=0;i<rowLen;i++)
{
for(j=0;j<colLen;j++)
{
dataSet[i][j] = ( dataSet[i][j] - mina[j] )/range[j];
}
}
}
int main(int argc , char** argv)
{
int k,row,col;
char *filename;
if( argc!=5 )
{
cout<<”The input should be like this : ./a.out k row col filename”<<endl;
exit(1);
}
k = atoi(argv[1]);
row = atoi(argv[2]);
col = atoi(argv[3]);
filename = argv[4];
KNN knn(k,row,col,filename);
knn.auto_norm_data();
knn.get_error_rate();
return 0;
}