This source file includes following definitions.
- tm_free_solution
- distance
- display_sol_sum_com
- display_sol_max_com
- display_sol_hop_byte
- display_sol
- tm_display_solution
- tm_display_other_heuristics
- in_tab
- map_Packed
- map_RR
- hash_asc
- generate_random_sol
- eval_sol
- exchange
- gain_exchange
- select_max
- compute_gain
- map_MPIPP
1 #include <ctype.h>
2 #include <float.h>
3 #include "tm_solution.h"
4 #include "tm_mt.h"
5 #include "tm_topology.h"
6
7 typedef struct {
8 int val;
9 long key;
10 } hash_t;
11
12
13
14 void tm_free_solution(tm_solution_t *sol);
15 int distance(tm_topology_t *topology,int i, int j);
16 double display_sol_sum_com(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, int *sigma);
17 double display_sol(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, int *sigma, tm_metric_t metric);
18 double tm_display_solution(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, tm_solution_t *sol,
19 tm_metric_t metric);
20 void tm_display_other_heuristics(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, tm_metric_t metric);
21 int in_tab(int *tab, int n, int val);
22 void map_Packed(tm_topology_t *topology, int N, int *sigma);
23 void map_RR(tm_topology_t * topology, int N, int *sigma);
24 int hash_asc(const void* x1,const void* x2);
25 int *generate_random_sol(tm_topology_t *topology,int N, int seed);
26 double eval_sol(int *sol,int N,double **comm, double **arch);
27 void exchange(int *sol,int i,int j);
28 double gain_exchange(int *sol,int l,int m,double eval1,int N,double **comm, double **arch);
29 void select_max(int *l,int *m,double **gain,int N,int *state);
30 void compute_gain(int *sol,int N,double **gain,double **comm, double **arch);
31 void map_MPIPP(tm_topology_t *topology,int nb_seed,int N,int *sigma,double **comm, double **arch);
32
33
34 void tm_free_solution(tm_solution_t *sol){
35 int i,n;
36
37 n = sol->k_length;
38
39 if(sol->k)
40 for(i=0 ; i<n ; i++)
41 FREE(sol->k[i]);
42
43 FREE(sol->k);
44 FREE(sol->sigma);
45 FREE(sol);
46 }
47
48
49
50
51
52
53
54
55
56
57 int distance(tm_topology_t *topology,int i, int j)
58 {
59 int level = 0;
60 int arity;
61 int f_i, f_j ;
62 int vl = tm_get_verbose_level();
63 int depth = topology->nb_levels-1;
64
65 f_i = topology->node_rank[i];
66 f_j = topology->node_rank[j];
67
68 if(vl >= DEBUG)
69 printf("i=%d, j=%d Level = %d f=(%d,%d)\n",i ,j, level, f_i, f_j);
70
71
72 do{
73 level++;
74 arity = topology->arity[level];
75 if( arity == 0 )
76 arity = 1;
77 f_i = f_i/arity;
78 f_j = f_j/arity;
79 } while((f_i!=f_j) && (level < depth));
80
81 if(vl >= DEBUG)
82 printf("distance(%d,%d):%d\n",topology->node_rank[i], topology->node_rank[j], level);
83
84 return level;
85 }
86
87 double display_sol_sum_com(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, int *sigma)
88 {
89 double a,c,sol;
90 int i,j;
91 double *cost = topology->cost;
92 double **mat = aff_mat->mat;
93 int N = aff_mat->order;
94 int depth = topology->nb_levels - 1;
95
96
97 sol = 0;
98 for ( i = 0 ; i < N ; i++ )
99 for ( j = i+1 ; j < N ; j++){
100 c = mat[i][j];
101
102
103
104
105
106 a = cost[depth-distance(topology,sigma[i],sigma[j])];
107 if(tm_get_verbose_level() >= DEBUG)
108 printf("T_%d_%d %f*%f=%f\n",i,j,c,a,c*a);
109 sol += c*a;
110 }
111
112 for (i = 0; i < N; i++) {
113 printf("%d", sigma[i]);
114 if(i<N-1)
115 printf(",");
116 }
117 printf(" : %g\n",sol);
118
119 return sol;
120 }
121
122
123 static double display_sol_max_com(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, int *sigma)
124 {
125 double a,c,sol;
126 int i,j;
127 double *cost = topology->cost;
128 double **mat = aff_mat->mat;
129 int N = aff_mat->order;
130 int vl = tm_get_verbose_level();
131 int depth = topology->nb_levels - 1;
132
133 sol = 0;
134 for ( i = 0 ; i < N ; i++ )
135 for ( j = i+1 ; j < N ; j++){
136 c = mat[i][j];
137
138
139
140
141
142 a = cost[depth-distance(topology,sigma[i],sigma[j])];
143 if(vl >= DEBUG)
144 printf("T_%d_%d %f*%f=%f\n",i,j,c,a,c*a);
145 if(c*a > sol)
146 sol = c*a;
147 }
148
149 for (i = 0; i < N; i++) {
150 printf("%d", sigma[i]);
151 if(i<N-1)
152 printf(",");
153 }
154 printf(" : %g\n",sol);
155
156 return sol;
157 }
158
159 static double display_sol_hop_byte(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, int *sigma)
160 {
161 double c,sol;
162 int nb_hops;
163 int i,j;
164 double **mat = aff_mat->mat;
165 int N = aff_mat->order;
166
167 sol = 0;
168 for ( i = 0 ; i < N ; i++ )
169 for ( j = i+1 ; j < N ; j++){
170 c = mat[i][j];
171 nb_hops = 2*distance(topology,sigma[i],sigma[j]);
172 if(tm_get_verbose_level() >= DEBUG)
173 printf("T_%d_%d %f*%d=%f\n",i,j,c,nb_hops,c*nb_hops);
174 sol += c*nb_hops;
175 }
176
177 for (i = 0; i < N; i++) {
178 printf("%d", sigma[i]);
179 if(i<N-1)
180 printf(",");
181 }
182 printf(" : %g\n",sol);
183
184 return sol;
185 }
186
187
188
189 double display_sol(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, int *sigma, tm_metric_t metric){
190 switch (metric){
191 case TM_METRIC_SUM_COM:
192 return display_sol_sum_com(topology, aff_mat, sigma);
193 case TM_METRIC_MAX_COM:
194 return display_sol_max_com(topology, aff_mat, sigma);
195 case TM_METRIC_HOP_BYTE:
196 return display_sol_hop_byte(topology, aff_mat, sigma);
197 default:
198 if(tm_get_verbose_level() >= ERROR){
199 fprintf(stderr,"Error printing solution: metric %d not implemented\n",metric);
200 return -1;
201 }
202 }
203 return -1;
204 }
205
206 double tm_display_solution(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, tm_solution_t *sol,
207 tm_metric_t metric){
208
209 int i,j;
210 int **k = sol->k;
211
212
213 if(tm_get_verbose_level() >= DEBUG){
214 printf("k: \n");
215 for( i = 0 ; i < nb_processing_units(topology) ; i++ ){
216 if(k[i][0] != -1){
217 printf("\tProcessing unit %d: ",i);
218 for (j = 0 ; j<topology->oversub_fact; j++){
219 if( k[i][j] == -1)
220 break;
221 printf("%d ",k[i][j]);
222 }
223 printf("\n");
224 }
225 }
226 }
227
228
229 return display_sol(topology, aff_mat, sol->sigma, metric);
230 }
231
232 void tm_display_other_heuristics(tm_topology_t *topology, tm_affinity_mat_t *aff_mat, tm_metric_t metric)
233 {
234 int *sigma = NULL;
235 int N = aff_mat->order;
236
237 sigma = (int*)MALLOC(sizeof(int)*N);
238
239 map_Packed(topology, N, sigma);
240 printf("Packed: ");
241 display_sol(topology, aff_mat, sigma, metric);
242
243 map_RR(topology, N, sigma);
244 printf("RR: ");
245 display_sol(topology, aff_mat, sigma, metric);
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271 FREE(sigma);
272 }
273
274
275 int in_tab(int *tab, int n, int val){
276 int i;
277 for( i = 0; i < n ; i++)
278 if(tab[i] == val)
279 return 1;
280
281 return 0;
282 }
283
284 void map_Packed(tm_topology_t *topology, int N, int *sigma)
285 {
286 size_t i;
287 int j = 0,depth;
288 int vl = tm_get_verbose_level();
289
290 depth = topology->nb_levels-1;
291
292 for( i = 0 ; i < topology->nb_nodes[depth] ; i++){
293
294 if((!topology->constraints) || (in_tab(topology->constraints, topology->nb_constraints, topology->node_id[i]))){
295 if(vl >= DEBUG)
296 printf ("%lu: %d -> %d\n", i, j, topology->node_id[i]);
297 sigma[j++]=topology->node_id[i];
298 if(j == N)
299 break;
300 }
301 }
302 }
303
304 void map_RR(tm_topology_t *topology, int N,int *sigma)
305 {
306 int i;
307 int vl = tm_get_verbose_level();
308
309 for( i = 0 ; i < N ; i++ ){
310 if(topology->constraints)
311 sigma[i]=topology->constraints[i%topology->nb_constraints];
312 else
313 sigma[i]=i%topology->nb_proc_units;
314 if(vl >= DEBUG)
315 printf ("%d -> %d (%d)\n",i,sigma[i],topology->nb_proc_units);
316 }
317 }
318
319 int hash_asc(const void* x1,const void* x2)
320 {
321 hash_t *e1 = NULL,*e2 = NULL;
322
323 e1 = ((hash_t*)x1);
324 e2 = ((hash_t*)x2);
325
326 return (e1->key < e2->key) ? -1 : 1;
327 }
328
329
330 int *generate_random_sol(tm_topology_t *topology,int N, int seed)
331 {
332 hash_t *hash_tab = NULL;
333 int *sol = NULL;
334 int *nodes_id= NULL;
335 int i;
336
337 nodes_id = topology->node_id;
338
339 hash_tab = (hash_t*)MALLOC(sizeof(hash_t)*N);
340 sol = (int*)MALLOC(sizeof(int)*N);
341
342 init_genrand(seed);
343
344 for( i = 0 ; i < N ; i++ ){
345 hash_tab[i].val = nodes_id[i];
346 hash_tab[i].key = genrand_int32();
347 }
348
349 qsort(hash_tab,N,sizeof(hash_t),hash_asc);
350 for( i = 0 ; i < N ; i++ )
351 sol[i] = hash_tab[i].val;
352
353 FREE(hash_tab);
354 return sol;
355 }
356
357
358 double eval_sol(int *sol,int N,double **comm, double **arch)
359 {
360 double a,c,res;
361 int i,j;
362
363 res = 0;
364 for ( i = 0 ; i < N ; i++ )
365 for ( j = i+1 ; j < N ; j++ ){
366 c = comm[i][j];
367 a = arch[sol[i]][sol[j]];
368 res += c/a;
369 }
370
371 return res;
372 }
373
374 void exchange(int *sol,int i,int j)
375 {
376 int tmp;
377 tmp = sol[i];
378 sol[i] = sol[j];
379 sol[j] = tmp;
380 }
381
382 double gain_exchange(int *sol,int l,int m,double eval1,int N,double **comm, double **arch)
383 {
384 double eval2;
385 if( l == m )
386 return 0;
387 exchange(sol,l,m);
388 eval2 = eval_sol(sol,N,comm,arch);
389 exchange(sol,l,m);
390
391 return eval1-eval2;
392 }
393
394 void select_max(int *l,int *m,double **gain,int N,int *state)
395 {
396 double max;
397 int i,j;
398
399 max = -DBL_MAX;
400
401 for( i = 0 ; i < N ; i++ )
402 if(!state[i])
403 for( j = 0 ; j < N ; j++ )
404 if( (i != j) && (!state[j]) ){
405 if(gain[i][j] > max){
406 *l = i;
407 *m = j;
408 max=gain[i][j];
409 }
410 }
411 }
412
413
414 void compute_gain(int *sol,int N,double **gain,double **comm, double **arch)
415 {
416 double eval1;
417 int i,j;
418
419 eval1 = eval_sol(sol,N,comm,arch);
420 for( i = 0 ; i < N ; i++ )
421 for( j = 0 ; j <= i ; j++)
422 gain[i][j] = gain[j][i] = gain_exchange(sol,i,j,eval1,N,comm,arch);
423 }
424
425
426
427
428
429
430
431
432 void map_MPIPP(tm_topology_t *topology,int nb_seed,int N,int *sigma,double **comm, double **arch)
433 {
434 int *sol = NULL;
435 int *state = NULL;
436 double **gain = NULL;
437 int **history = NULL;
438 double *temp = NULL;
439 int i,j,t,l=0,m=0,seed=0;
440 double max,sum,best_eval,eval;
441
442 gain = (double**)MALLOC(sizeof(double*)*N);
443 history = (int**)MALLOC(sizeof(int*)*N);
444 for( i = 0 ; i < N ; i++){
445 gain[i] = (double*)MALLOC(sizeof(double)*N);
446 history[i] = (int*)MALLOC(sizeof(int)*3);
447 }
448
449 state = (int*)MALLOC(sizeof(int)*N);
450 temp = (double*)MALLOC(sizeof(double)*N);
451
452 sol = generate_random_sol(topology, N, seed++);
453 for( i = 0 ; i < N ; i++)
454 sigma[i] = sol[i];
455
456 best_eval = DBL_MAX;
457 while(seed <= nb_seed){
458 do{
459 for( i = 0 ; i < N ; i++ ){
460 state[i] = 0;
461
462 }
463
464 compute_gain(sol,N,gain,comm,arch);
465
466
467
468
469 for( i = 0 ; i < N/2 ; i++ ){
470 select_max(&l,&m,gain,N,state);
471
472 state[l] = 1;
473 state[m] = 1;
474 exchange(sol,l,m);
475 history[i][1] = l;
476 history[i][2] = m;
477 temp[i] = gain[l][m];
478 compute_gain(sol,N,gain,comm,arch);
479 }
480
481 t = -1;
482 max = 0;
483 sum = 0;
484 for(i = 0 ; i < N/2 ; i++ ){
485 sum += temp[i];
486 if( sum > max ){
487 max = sum;
488 t = i;
489 }
490 }
491
492
493 for( j = t+1 ; j < N/2 ; j++ ){
494 exchange(sol,history[j][1],history[j][2]);
495
496 }
497
498
499
500
501
502
503 eval = eval_sol(sol,N,comm,arch);
504 if(eval < best_eval){
505 best_eval = eval;
506 for(i = 0 ; i < N ; i++)
507 sigma[i] = sol[i];
508
509 }
510 }while( max > 0 );
511 FREE(sol);
512 sol=generate_random_sol(topology, N, seed++);
513 }
514
515
516 FREE(sol);
517 FREE(temp);
518 FREE(state);
519 for( i = 0 ; i < N ; i++){
520 FREE(gain[i]);
521 FREE(history[i]);
522 }
523 FREE(gain);
524 FREE(history);
525 }