Debian Codegraph @

armci/examples/features/aggregation/sparse_matvecmul/sparse_matvecmul.c

raw
1 #if HAVE_CONFIG_H
2 # include "config.h"
3 #endif
4
5 /* $Id$ */
6
7 #if HAVE_STDIO_H
8 # include <stdio.h>
9 #endif
10 #if HAVE_STDLIB_H
11 # include <stdlib.h>
12 #endif
13 #if HAVE_UNISTD_H
14 # include <unistd.h>
15 #elif HAVE_WINDOWS_H
16 # include <windows.h>
17 # define sleep(x) Sleep(1000*(x))
18 #endif
19 #if HAVE_ASSERT_H
20 # include <assert.h>
21 #endif
22
23 #include "armci.h"
24 #include "message.h"
25
26 #define DIM1 5
27 #define DIM2 3
28 #ifdef __sun
29 /* Solaris has shared memory shortages in the default system configuration */
30 # define DIM3 6
31 # define DIM4 5
32 # define DIM5 4
33 #elif defined(__alpha__)
34 # define DIM3 8
35 # define DIM4 5
36 # define DIM5 6
37 #else
38 # define DIM3 8
39 # define DIM4 9
40 # define DIM5 7
41 #endif
42 #define DIM6 3
43 #define DIM7 2
44
45
46 #define OFF 1
47 #define EDIM1 (DIM1+OFF)
48 #define EDIM2 (DIM2+OFF)
49 #define EDIM3 (DIM3+OFF)
50 #define EDIM4 (DIM4+OFF)
51 #define EDIM5 (DIM5+OFF)
52 #define EDIM6 (DIM6+OFF)
53 #define EDIM7 (DIM7+OFF)
54
55 #define DIMS 4
56 #define MAXDIMS 7
57 #define MAX_DIM_VAL 50
58 #define LOOP 200
59
60 #define BASE 100.
61 #define MAXPROC 128
62 #define TIMES 100
63
64 # define ELEMS 200
65
66 /***************************** macros ************************/
67 #define COPY(src, dst, bytes) memcpy((dst),(src),(bytes))
68 #define ARMCI_MAX(a,b) (((a) >= (b)) ? (a) : (b))
69 #define ARMCI_MIN(a,b) (((a) <= (b)) ? (a) : (b))
70 #define ARMCI_ABS(a) (((a) <0) ? -(a) : (a))
71
72 #define ROW 65536
73 #define COL ROW /* square matrices only for the time being */
74
75 /***************************** global data *******************/
76 int me, nproc;
77 short int fortran_indexing=0;
78 static int proc_row_list[MAXPROC];/*no of rows owned by each process - accumulated*/
79 static int proc_nz_list[MAXPROC]; /*no of non-zeros owned by each process */
80
81 void create_array(void *a[], int elem_size, int ndim, int dims[])
82 {
83 int bytes=elem_size, i, rc;
84
85 assert(ndim<=MAXDIMS);
86 for(i=0;i<ndim;i++)bytes*=dims[i];
87
88 rc = ARMCI_Malloc(a, bytes);
89 assert(rc==0);
90
91 assert(a[me]);
92
93 }
94
95 void destroy_array(void *ptr[])
96 {
97 int check;
98
99 armci_msg_barrier();
100 check = !ARMCI_Free(ptr[me]);
101 assert(check);
102 }
103
104 static void verify_list(int *proc_row_list) {
105 int i;
106 printf("\nVERIFY: %d: No of rows = %d\n\n", 0, proc_row_list[0]);
107 for(i=1; i<nproc; i++)
108 printf("\nVERIFY: %d: No of rows = %d\n\n", i, proc_row_list[i]-proc_row_list[i-1]);
109 fflush(stdout);
110 }
111
112 static void load_balance(int n, int non_zero, int *row_ind_tmp) {
113
114 int proc_id, i, local_nz, local_nz_acc, A, B;
115
116 local_nz = local_nz_acc = non_zero/nproc;
117
118 /* number of rows owned by each process is stored in proc_row_list. This
119 is supposed to be well load balanced, so that each process has almost
120 same number of non-zero elements */
121 proc_id = 0;
122 if(me==0) printf("local_nz = %d\n", local_nz);
123 for(i=0; i<n; i++) { /* as # of entries in row_ind_tmp = n+1 */
124 if(row_ind_tmp[i] < local_nz_acc && row_ind_tmp[i+1] >= local_nz_acc) {
125 proc_row_list[proc_id++] = i+1;
126 local_nz_acc = local_nz*(proc_id+1);
127 if(proc_id == nproc-1) local_nz_acc = non_zero;
128 if(me==0 && proc_id<nproc) printf("local_nz = %d\n", local_nz_acc);
129 }
130 }
131
132 proc_row_list[nproc-1] = n;
133
134 for(i=0; i<nproc; i++) {
135 A = (i==0) ? 0: proc_row_list[i-1];/* # of entries in row_ind_tmp is n+1*/
136 B = proc_row_list[i];
137 proc_nz_list[i] = row_ind_tmp[B]-row_ind_tmp[A];
138 }
139
140 if(proc_id != nproc)
141 ARMCI_Error("Error while preparing Process Row list", proc_id-1);
142
143 #if 1
144 if(me==0) verify_list(proc_row_list);
145 #endif
146
147 }
148
149 static int sparse_initialize(int *n, int *non_zero, int **row_ind,
150 int **col_ind, double **values, double **vec,
151 double **svec) {
152
153 int i, j, rc, max, *row_ind_tmp=NULL, *tmp_indices=NULL;
154 double *tmp_values=NULL;
155 unsigned long len;
156 FILE *fp=NULL;
157
158 /* Broadcast order of matrix */
159 if(me==0) {
160 if((fp=fopen("Sparse-MPI/av41092.rua.data", "r")) == NULL)
161 ARMCI_Error("Error: Input file not found", me);
162 fortran_indexing = 1; /* This is 1 for Harwell-Boeing format matrices */
163 fscanf(fp, "%d", n);
164 if(*n%nproc)
165 ARMCI_Error("# of rows is not divisible by # of processors", nproc);
166 if(*n > ROW)
167 ARMCI_Error("order is greater than defined variable ROW", ROW);
168 }
169 len = sizeof(int);
170 armci_msg_brdcst(n, len, 0);
171
172 /* Broad cast number of non_zeros */
173 if(me==0) fscanf(fp, "%d", non_zero);
174 armci_msg_brdcst(non_zero, len, 0);
175
176 /* Broadcast row indices */
177 len = (*n+1)*sizeof(int);
178 row_ind_tmp = (int *)malloc(len);
179 if(me==0)for(i=0; i<*n+1; i++) {
180 fscanf(fp, "%d", &row_ind_tmp[i]);
181 if(fortran_indexing) --row_ind_tmp[i];
182 }
183 armci_msg_brdcst(row_ind_tmp, len, 0);
184
185 load_balance(*n, *non_zero, row_ind_tmp);
186
187 /* find how much temporary storage is needed at the maximum */
188 if(me==0) {
189 for(max=-1,j=0;j<nproc;j++) if(max<proc_nz_list[j]) max=proc_nz_list[j];
190 if(max<0) ARMCI_Error(" max cannot be negative", max);
191 }
192
193 /* Broadcast the maximum number of elements */
194 len = sizeof(int);
195 armci_msg_brdcst(&max, len, 0);
196
197 /* create the Sparse MAtrix Array */
198 if(me==0) printf(" Creating ValueArray (CompressedSparseMatrix) ...\n\n");
199 create_array((void**)col_ind, sizeof(int), 1, &max);
200
201 /* create the column subscript array */
202 if(me==0) printf(" Creating Column Subscript Array ... \n\n");
203 create_array((void**)values, sizeof(double), 1, &max);
204
205 /* create the x-vector and the solution vector */
206 if(me==0) printf(" Creating Vectors ... \n\n");
207 create_array((void**)vec, sizeof(double),1, &max);
208 create_array((void**)svec, sizeof(double),1, &max);
209 armci_msg_barrier();
210
211
212 /* Process 0 distributes the column indices and non_zero values to
213 respective processors*/
214 if(me == 0) {
215 tmp_indices = (int *)malloc(max*sizeof(int));
216 tmp_values = (double *)malloc(max*sizeof(double));
217
218 for(j=0; j<nproc; j++) {
219 for(i=0; i<proc_nz_list[j]; i++) {
220 fscanf(fp, "%d", &tmp_indices[i]);
221 if(fortran_indexing) --tmp_indices[i];
222 }
223 /* rc = fread(tmp_indices, sizeof(int), proc_nz_list[j], fp); */
224 if((rc=ARMCI_Put(tmp_indices, col_ind[j], proc_nz_list[j]*sizeof(int), j)))
225 ARMCI_Error("armci_nbput failed\n",rc);
226 }
227 for(j=0; j<nproc; j++) {
228 for(i=0; i<proc_nz_list[j]; i++) fscanf(fp, "%lf", &tmp_values[i]);
229 if((rc=ARMCI_Put(tmp_values, values[j], proc_nz_list[j]*sizeof(double), j)))
230 ARMCI_Error("armci_nbput failed\n",rc);
231 }
232 }
233 ARMCI_AllFence(); armci_msg_barrier();ARMCI_AllFence();
234
235 /* initializing x-vector */
236 if(me==0) for(i=0;i<proc_nz_list[me]; i++) vec[me][i] = (i+1);
237 else for(i=0;i<proc_nz_list[me];i++) vec[me][i]=me*proc_nz_list[me-1]+(i+1);
238
239 #if 0
240 if(me==0) {
241 printf("max = %d\n", max);
242 for(i=0; i<max; i++) printf("%.1f ", values[me][i]);
243 printf("\n");
244 }
245 #endif
246
247 *row_ind = row_ind_tmp;
248 if(me==0) {
249 free(tmp_indices);
250 free(tmp_values);
251 fclose(fp);
252 }
253 return 0;
254 }
255
256 static int compare(const void *p1, const void *p2) {
257 int i = *((int *)p1);
258 int j = *((int *)p2);
259
260 if (i > j) return (1);
261 if (i < j) return (-1);
262 return (0);
263 }
264
265 static int count = -1;
266 static armci_hdl_t gHandle[MAXPROC];
267 static int prev_proc = -1;
268
269 static void get_data(int n, int start, int end, double *vec_local,
270 double **vec) {
271 int i, j, rc, bytes, offset;
272 int proc_start, proc_end, idx_start, idx_end;
273
274 proc_start = proc_end = -1;
275 for(i=0; i<nproc; i++) {
276 if(proc_start<0 && proc_row_list[i]>start) proc_start = i;
277 if(proc_end<0 && proc_row_list[i]>end) proc_end = i;
278 }
279 if(proc_start<0 || proc_end<0) ARMCI_Error("Invalid Process Ids", -1);
280
281 for(i=proc_start; i<=proc_end; i++) {
282 if(i==proc_start) idx_start = start;
283 else { if(i==0) idx_start=0; else idx_start = proc_row_list[i-1];}
284 if(i==proc_end) idx_end = end;
285 else idx_end = proc_row_list[i]-1;
286
287 if(i!=prev_proc) {
288 ++count; prev_proc = i;
289 ARMCI_INIT_HANDLE(&gHandle[count]);
290 ARMCI_SET_AGGREGATE_HANDLE(&gHandle[count]);
291 }
292
293 if(i==0) offset=0; else offset = proc_row_list[i-1];
294 if(i==me) { /* local */
295 for(j=idx_start; j<=idx_end; j++) vec_local[j] = vec[me][j-offset];
296 }
297 else { /* remote */
298 bytes = (idx_end-idx_start+1)*sizeof(double);
299 vec_local[idx_start] = -1;
300 #if 0
301 if((rc=ARMCI_Get(&vec[i][idx_start-offset], &vec_local[idx_start],
302 bytes, i)))
303 #else
304 if((rc=ARMCI_NbGet(&vec[i][idx_start-offset], &vec_local[idx_start],
305 bytes, i, &gHandle[count])))
306 #endif
307 ARMCI_Error("armci_nbget failed\n",rc);
308 }
309 }
310 }
311
312 static void sparse_multiply(int n, int non_zero, int *row_ind, int **col_ind,
313 double **values, double **vec, double **svec) {
314
315 int i, j, k, num_elements, offset, *tmp_indices;
316 double start_time, comm_time, comp_time, v, vec_local[COL];
317 int start, end, prev, nrows, idx;
318
319 #if 0
320 /* ---- Sequential Case ---- */
321 for(i=0; i<n; i++) {
322 svec[me][i] = 0;
323 for(k=row_ind[i]; k<row_ind[i+1]; k++) {
324 j = col_ind[me][k];
325 v = values[me][k];
326 svec[me][i] += v*vec[me][j];
327 printf("%.1f %.1f\n", v, vec[me][j]);
328 }
329 }
330 for(i=0; i<n; i++) printf("%.1f ", svec[me][i]);
331 printf("\n");
332 #else
333
334 num_elements = proc_nz_list[me];
335 printf("num_elements = %d\n", num_elements);
336 tmp_indices = (int *)malloc(num_elements*sizeof(int));
337 for(i=0; i<num_elements; i++) tmp_indices[i] = col_ind[me][i];
338 qsort(tmp_indices, num_elements, sizeof(int), compare);
339
340 start_time = armci_timer();
341
342 /* get the required portion of vector you need to local array */
343 start = prev = tmp_indices[0];
344 for(i=1; i<num_elements; i++) {
345 if(tmp_indices[i]>prev+1) {
346 end = prev;
347 get_data(n, start, end, vec_local, vec);
348 start = prev = tmp_indices[i];
349 }
350 else prev = tmp_indices[i];
351 }
352 get_data(n, start, prev, vec_local, vec);
353
354 #if 1
355 if(count>=0) for(i=0; i<=count; i++) ARMCI_Wait(&gHandle[i]);
356 #endif
357
358 comm_time = armci_timer() - start_time;
359 start_time = armci_timer();
360
361 /* Perform Matrix-Vector multiply and store the result in
362 solution vector - "svec[]" */
363
364 if(me==0) { nrows = proc_row_list[me]; offset = row_ind[0]; }
365 else {
366 nrows = proc_row_list[me]-proc_row_list[me-1];
367 offset = row_ind[proc_row_list[me-1]];
368 }
369 /* printf("%d: My total Work = %d\n", me, nrows); */
370
371 for(i=0; i<nrows; i++) { /* loop over rows owned by me */
372 svec[me][i] = 0;
373 if(me==0) idx = i; else idx = proc_row_list[me-1] + i;
374 for(k=row_ind[idx]; k<row_ind[idx+1]; k++) {
375 j = col_ind[me][k-offset];
376 v = values[me][k-offset];
377 svec[me][i] += v*vec_local[j];
378 }
379 }
380 comp_time = armci_timer()-start_time;
381 printf("%d: %f + %f = %f (count = %d)\n", me, comm_time, comp_time,
382 comm_time+comp_time, count+1);
383 #endif
384 }
385
386 static void gather_solution_vector(double **svec) {
387 #if 0
388 double y[COL];
389 if((rc=ARMCI_Get(&vec[i][idx_start-offset], &vec_local[idx_start],
390 bytes, i)))
391 ARMCI_Error("armci_nbget failed\n",rc);
392 #endif
393 }
394
395 static void test_sparse() {
396
397 int *col_ind[MAXPROC];
398 double *values[MAXPROC], *vec[MAXPROC], *svec[MAXPROC]/*, start_time*/;
399 int n, non_zero, *row_ind;
400
401 sparse_initialize(&n, &non_zero, &row_ind, col_ind, values, vec, svec);
402 armci_msg_barrier();
403
404 /*start_time = armci_timer();*/
405 sparse_multiply(n, non_zero, row_ind, col_ind, values, vec, svec);
406 /* printf("%d: Timetaken = %f\n", me, armci_timer()-start_time); */
407 armci_msg_barrier();
408
409 if(me==0) gather_solution_vector(svec);
410
411 if(me==0){printf("O.K.\n"); fflush(stdout);}
412 destroy_array((void **)vec);
413 }
414
415
416 int main(int argc, char* argv[])
417 {
418
419 armci_msg_init(&argc, &argv);
420 nproc = armci_msg_nproc();
421 me = armci_msg_me();
422
423 /* printf("nproc = %d, me = %d\n", nproc, me);*/
424
425 if(nproc>MAXPROC && me==0)
426 ARMCI_Error("Test works for up to %d processors\n",MAXPROC);
427
428 if(me==0){
429 printf("ARMCI test program (%d processes)\n",nproc);
430 fflush(stdout);
431 sleep(1);
432 }
433
434 ARMCI_Init();
435
436 if(me==0){
437 printf("\n Performing Sparse Matrix-Vector Multiplication ...\n\n");
438 fflush(stdout);
439 }
440 test_sparse();
441
442 ARMCI_AllFence();
443 armci_msg_barrier();
444 if(me==0){printf("\nSuccess!!\n"); fflush(stdout);}
445 sleep(2);
446
447 armci_msg_barrier();
448 ARMCI_Finalize();
449 armci_msg_finalize();
450 return(0);
451 }