k-nn brute implemented
[RBC.git] / driver.cu
1 /* This file is part of the Random Ball Cover (RBC) library.
2 * (C) Copyright 2010, Lawrence Cayton [lcayton@tuebingen.mpg.de]
3 */
4
5 #include<stdio.h>
6 #include<stdlib.h>
7 #include<cuda.h>
8 #include<sys/time.h>
9 #include<math.h>
10 #include "defs.h"
11 #include "utils.h"
12 #include "utilsGPU.h"
13 #include "rbc.h"
14 #include "brute.h"
15 #include "sKernel.h"
16
17 void parseInput(int,char**);
18 void readData(char*,unint,unint,real*);
19 void readDataText(char*,unint,unint,real*);
20 void orgData(real*,unint,unint,matrix,matrix);
21
22
23 char *dataFile, *outFile;
24 unint n=0, m=0, d=0, numReps=0, s=0;
25 unint deviceNum=0;
26 int main(int argc, char**argv){
27 real *data;
28 matrix x, q;
29 unint *NNs;
30 intMatrix NNsK, NNsKCPU;
31 unint i;
32 struct timeval tvB,tvE;
33 cudaError_t cE;
34 rbcStruct rbcS;
35
36 printf("*****************\n");
37 printf("RANDOM BALL COVER\n");
38 printf("*****************\n");
39
40 parseInput(argc,argv);
41
42 cuInit(0);
43 printf("Using GPU #%d\n",deviceNum);
44 if(cudaSetDevice(deviceNum) != cudaSuccess){
45 printf("Unable to select device %d.. exiting. \n",deviceNum);
46 exit(1);
47 }
48
49 unsigned int memFree, memTot;
50 CUcontext pctx;
51 unsigned int flags=0;
52 int device;
53 cudaGetDevice(&device);
54 cuCtxCreate(&pctx,flags,device);
55 cuMemGetInfo(&memFree, &memTot);
56 printf("GPU memory free = %u/%u (MB) \n",memFree/(1024*1024),memTot/(1024*1024));
57
58 data = (real*)calloc( (n+m)*d, sizeof(*data) );
59 x.mat = (real*)calloc( PAD(n)*PAD(d), sizeof(*(x.mat)) );
60
61 //Need to allocate extra space, as each group of q will be padded later.
62 q.mat = (real*)calloc( PAD(m)*PAD(d), sizeof(*(q.mat)) );
63 x.r = n; x.c = d; x.pr = PAD(n); x.pc = PAD(d); x.ld = x.pc;
64 q.r = m; q.c = d; q.pr = PAD(m); q.pc = PAD(d); q.ld = q.pc;
65
66 NNs = (unint*)calloc( m, sizeof(*NNs) );
67 for(i=0; i<m; i++)
68 NNs[i]=DUMMY_IDX;
69
70 readData(dataFile, (n+m), d, data);
71 orgData(data, (n+m), d, x, q);
72 free(data);
73
74 for(i=0;i<m;i++)
75 NNs[i]=DUMMY_IDX;
76
77 NNsK.r=q.r; NNsK.pr=q.pr; NNsK.pc=NNsK.c=K; NNsK.ld=NNsK.pc;
78 NNsKCPU.r=q.r; NNsKCPU.pr=q.pr; NNsKCPU.pc=NNsKCPU.c=K; NNsKCPU.ld=NNsKCPU.pc;
79 NNsK.mat = (unint*)calloc(NNsK.pr*NNsK.pc, sizeof(*NNsK.mat));
80 NNsKCPU.mat = (unint*)calloc(NNsKCPU.pr*NNsKCPU.pc, sizeof(*NNsKCPU.mat));
81
82 printf("running k-brute force..\n");
83 gettimeofday(&tvB,NULL);
84 bruteK(x,q,NNsK);
85 gettimeofday(&tvE,NULL);
86 printf("\t.. time elapsed = %6.4f \n",timeDiff(tvB,tvE));
87
88 printf("running regular brute force..\n");
89 gettimeofday(&tvB,NULL);
90 bruteSearch(x,q,NNs);
91 gettimeofday(&tvE,NULL);
92 printf("\t.. time elapsed = %6.4f \n",timeDiff(tvB,tvE));
93
94
95 printf("running cpu version..\n");
96 gettimeofday(&tvB,NULL);
97 bruteKCPU(x,q,NNsKCPU);
98 gettimeofday(&tvE,NULL);
99 printf("\t.. time elapsed = %6.4f \n",timeDiff(tvB,tvE));
100
101
102 /* printf("\nrunning rbc..\n"); */
103 /* gettimeofday(&tvB,NULL); */
104 /* buildRBC(x, &rbcS, numReps, s); */
105 /* gettimeofday(&tvE,NULL); */
106 /* printf("\t.. build time for rbc = %6.4f \n",timeDiff(tvB,tvE)); */
107
108 /* gettimeofday(&tvB,NULL); */
109 /* queryRBC(q, rbcS, NNs); */
110 /* gettimeofday(&tvE,NULL); */
111 /* printf("\t.. query time for rbc = %6.4f \n",timeDiff(tvB,tvE)); */
112
113 /* destroyRBC(&rbcS); */
114 /* printf("finished \n") */;
115
116 cE = cudaGetLastError();
117 if( cE != cudaSuccess ){
118 printf("Execution failed; error type: %s \n", cudaGetErrorString(cE) );
119 }
120
121 for(i=0;i<q.r;i++){
122 int j;
123 for(j=0;j<K;j++){
124 if(NNsK.mat[IDX(i,j,NNsK.ld)] != NNsKCPU.mat[IDX(i,j,NNsKCPU.ld)])
125 printf("%d %d: (%6.2f %6.2f) ",i,j,distVec(q,x,i,NNsK.mat[IDX(i,j,NNsK.ld)]),distVec(q,x,i,NNsKCPU.mat[IDX(i,j,NNsKCPU.ld)]));
126 }
127 /* printf("\n"); */
128 }
129
130 /* printf("\nComputing error rates (this might take a while)\n"); */
131 /* real *ranges = (real*)calloc(q.pr,sizeof(*ranges)); */
132 /* for(i=0;i<q.r;i++){ */
133 /* if(NNs[i]>n) printf("error"); */
134 /* ranges[i] = distVec(q,x,i,NNs[i]) - 10e-6; */
135 /* } */
136
137 /* unint *cnts = (unint*)calloc(q.pr,sizeof(*cnts)); */
138 /* gettimeofday(&tvB,NULL); */
139 /* bruteRangeCount(x,q,ranges,cnts); */
140 /* gettimeofday(&tvE,NULL); */
141
142 /* long int nc=0; */
143 /* for(i=0;i<m;i++){ */
144 /* nc += cnts[i]; */
145 /* } */
146 /* double mean = ((double)nc)/((double)m); */
147 /* double var = 0.0; */
148 /* for(i=0;i<m;i++) { */
149 /* var += (((double)cnts[i])-mean)*(((double)cnts[i])-mean)/((double)m); */
150 /* } */
151 /* printf("\tavg rank = %6.4f; std dev = %6.4f \n\n", mean, sqrt(var)); */
152 /* printf("(range count took %6.4f) \n", timeDiff(tvB, tvE)); */
153
154
155 /* if(outFile){ */
156 /* FILE* fp = fopen(outFile, "a"); */
157 /* fprintf( fp, "%d %d %6.5f %6.5f \n", numReps, s, mean, sqrt(var) ); */
158 /* fclose(fp); */
159 /* } */
160
161 /* free(ranges); */
162 /* free(cnts); */
163 free(NNs);
164 free(NNsK.mat);
165 free(NNsKCPU.mat);
166 free(x.mat);
167 free(q.mat);
168 }
169
170
171 void parseInput(int argc, char **argv){
172 int i=1;
173 if(argc <= 1){
174 printf("\nusage: \n testRBC -f datafile (bin) -n numPts (DB) -m numQueries -d dim -r numReps -s numPtsPerRep [-o outFile] [-g GPU num]\n\n");
175 printf("\tdatafile = binary file containing the data\n");
176 printf("\tnumPts = size of database\n");
177 printf("\tnumQueries = number of queries\n");
178 printf("\tdim = dimensionailty\n");
179 printf("\tnumReps = number of representatives\n");
180 printf("\tnumPtsPerRep = number of points assigned to each representative\n");
181 printf("\toutFile = output file (optional); stored in text format\n");
182 printf("\tGPU num = ID # of the GPU to use (optional) for multi-GPU machines\n");
183 printf("\n\n");
184 exit(0);
185 }
186
187 while(i<argc){
188 if(!strcmp(argv[i], "-f"))
189 dataFile = argv[++i];
190 else if(!strcmp(argv[i], "-n"))
191 n = atoi(argv[++i]);
192 else if(!strcmp(argv[i], "-m"))
193 m = atoi(argv[++i]);
194 else if(!strcmp(argv[i], "-d"))
195 d = atoi(argv[++i]);
196 else if(!strcmp(argv[i], "-r"))
197 numReps = atoi(argv[++i]);
198 else if(!strcmp(argv[i], "-s"))
199 s = atoi(argv[++i]);
200 else if(!strcmp(argv[i], "-o"))
201 outFile = argv[++i];
202 else if(!strcmp(argv[i], "-g"))
203 deviceNum = atoi(argv[++i]);
204 else{
205 fprintf(stderr,"%s : unrecognized option.. exiting\n",argv[i]);
206 exit(1);
207 }
208 i++;
209 }
210
211 if( !n || !m || !d || !numReps || !s || !dataFile){
212 fprintf(stderr,"more arguments needed.. exiting\n");
213 exit(1);
214 }
215
216 if(numReps>n){
217 fprintf(stderr,"can't have more representatives than points.. exiting\n");
218 exit(1);
219 }
220 }
221
222
223 void readData(char *dataFile, unint rows, unint cols, real *data){
224 FILE *fp;
225 unint numRead;
226
227 fp = fopen(dataFile,"r");
228 if(fp==NULL){
229 fprintf(stderr,"error opening file.. exiting\n");
230 exit(1);
231 }
232
233 numRead = fread(data,sizeof(real),rows*cols,fp);
234 if(numRead != rows*cols){
235 fprintf(stderr,"error reading file.. exiting \n");
236 exit(1);
237 }
238 fclose(fp);
239 }
240
241
242 void readDataText(char *dataFile, unint rows, unint cols, real *data){
243 FILE *fp;
244 real t;
245
246 fp = fopen(dataFile,"r");
247 if(fp==NULL){
248 fprintf(stderr,"error opening file.. exiting\n");
249 exit(1);
250 }
251
252 for(int i=0; i<rows; i++){
253 for(int j=0; j<cols; j++){
254 if(fscanf(fp,"%f ", &t)==EOF){
255 fprintf(stderr,"error reading file.. exiting \n");
256 exit(1);
257 }
258 data[IDX( i, j, cols )]=(real)t;
259 }
260 }
261 fclose(fp);
262 }
263
264 //This function splits the data into two matrices, x and q, of
265 //their specified dimensions. The data is split randomly.
266 //It is assumed that the number of rows of data (the parameter n)
267 //is at least as large as x.r+q.r
268 void orgData(real *data, unint n, unint d, matrix x, matrix q){
269
270 unint i,fi,j;
271 unint *p;
272 p = (unint*)calloc(n,sizeof(*p));
273
274 randPerm(n,p);
275
276 for(i=0,fi=0 ; i<x.r ; i++,fi++){
277 for(j=0;j<x.c;j++){
278 x.mat[IDX(i,j,x.ld)] = data[IDX(p[fi],j,d)];
279 }
280 }
281
282 for(i=0 ; i<q.r ; i++,fi++){
283 for(j=0;j<q.c;j++){
284 q.mat[IDX(i,j,q.ld)] = data[IDX(p[fi],j,d)];
285 }
286 }
287
288 free(p);
289 }
290