This source file includes following definitions.
- tm_set_greedy_flag
- tm_get_greedy_flag
- com_mat_to_scotch_graph
- check_partition
- kpartition_scotch
- allocate_vertex
- eval_cost
- kpartition_greedy
- kpartition
- split_constraints
- split_com_mat
- split_vertices
- free_tab_com_mat
- free_tab_local_vertices
- free_const_tab
- check_com_mat
- print_tab
- display_partition
- kpartition_build_level_topology
- kpartition_build_tree_from_topology
1 #include "tm_mapping.h"
2 #include "tm_mt.h"
3 #include "tm_kpartitioning.h"
4 #include "k-partitioning.h"
5 #include <stdlib.h>
6 #include <stdio.h>
7 #include "config.h"
8
9 #if defined(HAVE_LIBSCOTCH)
10 #include <scotch.h>
11 #endif
12
13
14 #define USE_KL_KPART 0
15 #define KL_KPART_GREEDY_TRIALS 0
16
17 static int verbose_level = ERROR;
18
19 #define MAX_TRIALS 10
20 #define USE_KL_STRATEGY 1
21
22
23 #define MIN(a,b) ((a)<(b)?(a):(b))
24
25
26 int fill_tab(int **,int *,int,int,int,int);
27 void complete_obj_weight(double **,int,int);
28
29 void allocate_vertex(int,int *,com_mat_t *,int,int *,int);
30 double eval_cost(int *, com_mat_t *);
31 int *kpartition_greedy(int, com_mat_t *,int,int *,int);
32 constraint_t *split_constraints (int *,int,int,tm_topology_t *,int, int);
33 com_mat_t **split_com_mat(com_mat_t *,int,int,int *);
34 int **split_vertices(int *,int,int,int *);
35 void free_tab_com_mat(com_mat_t **,int);
36 void free_tab_local_vertices(int **,int);
37 void free_const_tab(constraint_t *,int);
38 void kpartition_build_level_topology(tm_tree_t *,com_mat_t *,int,int,tm_topology_t *,
39 int *,int *,int,double *,double *);
40
41 static int greedy_flag = 0;
42
43 void tm_set_greedy_flag(int new_val){
44 greedy_flag = new_val;
45 }
46
47 int tm_get_greedy_flag(){
48 return greedy_flag;
49 }
50
51
52 #if defined(HAVE_LIBSCOTCH)
53
54 SCOTCH_Graph* com_mat_to_scotch_graph(com_mat_t *com_mat, int n){
55 double **mat = com_mat->comm;
56 SCOTCH_Num vertnbr = n;
57 SCOTCH_Num edgenbr = vertnbr*vertnbr;
58
59 SCOTCH_Num *verttab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * (vertnbr+1));
60
61
62
63 SCOTCH_Num *edgetab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * edgenbr);
64
65 SCOTCH_Num *edlotab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * edgenbr);
66 SCOTCH_Graph *graphptr = SCOTCH_graphAlloc();
67
68 int edgeNum = 0;
69 int i,j;
70
71
72 for(i = 0; i < com_mat->n ; i++) {
73 verttab[i] = edgeNum;
74 for(j = 0; j < i; j++) {
75 if(mat[i][j]){
76 edgetab[edgeNum] = j;
77 edlotab[edgeNum] = (SCOTCH_Num)mat[i][j];
78 edgeNum++;
79 }
80 }
81
82 for(j = i+1 ; j < com_mat->n ; j++) {
83 if(mat[i][j]){
84 edgetab[edgeNum] = j;
85 edlotab[edgeNum] = (SCOTCH_Num)mat[i][j];
86 edgeNum++;
87 }
88 }
89 }
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105 for(i = com_mat->n ; i<vertnbr ; i++) {
106 verttab[i] = edgeNum;
107 }
108
109 verttab[i] = edgeNum;
110
111 if(tm_get_verbose_level() >=DEBUG){
112 printf("Graph converted to Scotch format: edgeNum=%d, edgenbr = %lld, vertnbr = %lld\n",edgeNum, (long long int)edgenbr, (long long int)vertnbr);
113 }
114
115 assert(edgeNum <= edgenbr);
116 edgenbr = edgeNum;
117
118 SCOTCH_graphInit(graphptr);
119 SCOTCH_graphBuild(graphptr, 0, vertnbr, verttab, verttab+1, NULL, NULL, edgenbr, edgetab, edlotab);
120
121 return graphptr;
122 }
123
124
125
126 int check_partition(SCOTCH_Num *parttab, int k, int n){
127 int *count = CALLOC(sizeof(int), k);
128 int i;
129 for(i=0; i<n; i++){
130 count[parttab[i]]++;
131 }
132
133 int target= n/k;
134
135 for(i = 0; i<k ; i++){
136 if(count[i] != target){
137 if(tm_get_verbose_level()>=INFO)
138 fprintf(stdout, "Error in partition: %d vertices in partition %d while expecting %d vertices\n",count[i], i, target);
139 FREE(count);
140 return 0;
141 }
142 }
143
144 FREE(count);
145 return 1;
146 }
147
148
149
150
151 int *kpartition_scotch(int k, com_mat_t *com_mat, int n, int *constraints, int nb_constraints){
152 SCOTCH_Num partnbr = (SCOTCH_Num) k;
153 SCOTCH_Graph* graphptr;
154 SCOTCH_Strat strat;
155 SCOTCH_Num straval;
156 SCOTCH_Num *parttab = (SCOTCH_Num *)MALLOC(sizeof(SCOTCH_Num) * n);
157 int *partition = (int *)MALLOC(sizeof(int) * n);
158 int i, j;
159 int *nb_dumb = (int *)MALLOC(sizeof(int) * k);
160 int dumb_id, min_nb_dumb = n, sum_dumb = 0, p;
161
162
163
164
165
166
167
168 for(i=0;i<n;i++)
169 parttab[i] = -1;
170
171
172
173
174 if (nb_constraints){
175 int end, start = 0;
176 for( i = 0 ; i < k ; i ++){
177 int max_val = (i+1)* (n/k);
178 end = start;
179 while( end < nb_constraints){
180 if(constraints[end] >= max_val)
181 break;
182 end++;
183 }
184
185
186
187
188 nb_dumb[i] = n/k - (end-start);
189 sum_dumb += nb_dumb[i];
190 if(nb_dumb[i] < min_nb_dumb){
191 min_nb_dumb = nb_dumb[i];
192 }
193 start=end;
194 }
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216 dumb_id = n - sum_dumb;
217 for(i = 0 ; i < k ; i++){
218 for( j = 0; j < nb_dumb[i] - min_nb_dumb; j ++ ){
219 parttab[dumb_id] = i;
220 dumb_id++;
221 }
222 }
223 p = dumb_id;
224 for(i = 0 ; i < k ; i++){
225 for( j = 0 ; j < min_nb_dumb ; j ++ ){
226 parttab[dumb_id] = i;
227 dumb_id++;
228 }
229 }
230 }else{
231 p=n;
232 }
233
234
235 graphptr = com_mat_to_scotch_graph(com_mat, p);
236
237 SCOTCH_stratInit (&strat);
238 straval = SCOTCH_STRATBALANCE;
239 if(k>4)
240 straval = SCOTCH_STRATSPEED;
241 SCOTCH_stratGraphMapBuild (&strat, straval, partnbr, 0);
242
243
244 if(tm_get_verbose_level()>=DEBUG){
245 printf("Before Scotch (p=%d, n=%d): \n", p, n);
246 for(i = 0 ; i < n; i++){
247 printf("%d ",(int)parttab[i]);
248 }
249 printf("\n");
250 }
251
252 if(SCOTCH_graphPartFixed(graphptr, partnbr, &strat, parttab) == 0){
253 if(tm_get_verbose_level()>=DEBUG){
254 printf("After Scotch: \n");
255 for(i = 0 ; i < n; i++){
256 printf("%d ",(int)parttab[i]);
257 }
258 printf("\n");
259 }
260 }else{
261 if(tm_get_verbose_level()>=CRITICAL){
262 fprintf(stderr,"Scotch Partitionning failed\n");
263 }
264 exit(-1);
265 }
266
267 if(!check_partition(parttab, partnbr, n)){
268 if(tm_get_verbose_level()>=INFO){
269 printf("falling from Scotch to greedy partionning\n");
270 }
271 FREE(partition);
272 partition = kpartition_greedy(k, com_mat, n, constraints, nb_constraints);
273 }else{
274 for(i=0;i<n;i++)
275 partition[i] = parttab [i];
276 }
277
278 SCOTCH_stratExit (&strat);
279 SCOTCH_graphExit(graphptr);
280 SCOTCH_memFree(graphptr);
281 FREE(parttab);
282 FREE(nb_dumb);
283
284 return partition;
285 }
286
287 #endif
288
289
290 void allocate_vertex(int u, int *res, com_mat_t *com_mat, int n, int *size, int max_size)
291 {
292 int i,best_part=0;
293 double cost, best_cost = -1;
294
295
296
297 if(u>=com_mat->n){
298 for( i = 0 ; i < n ; i++)
299 if (( res[i] != -1 ) && ( size[res[i]] < max_size )){
300 best_part = res[i];
301 break;
302 }
303
304 }else{
305 for( i = 0 ; i < n ; i++){
306 if (( res[i] != -1 ) && ( size[res[i]] < max_size )){
307 cost = (((i)<com_mat->n)) ?com_mat->comm[u][i]:0;
308
309
310
311 if (( cost > best_cost)){
312 best_cost = cost;
313 best_part = res[i];
314 }
315 }
316 }
317 }
318
319
320
321
322
323 res[u] = best_part;
324 size[best_part]++;
325 }
326
327 double eval_cost(int *partition, com_mat_t *com_mat)
328 {
329 double cost = 0;
330 int i,j;
331
332 for( i = 0 ; i < com_mat->n ; i++ )
333 for( j = i+1 ; j < com_mat->n ; j++ )
334 if(partition[i] != partition[j])
335 cost += com_mat->comm[i][j];
336
337 return cost;
338 }
339
340 int *kpartition_greedy(int k, com_mat_t *com_mat, int n, int *constraints, int nb_constraints)
341 {
342 int *partition = NULL, *best_partition=NULL, *size = NULL;
343 int i,j,nb_trials;
344 int max_size, max_val;
345 double cost, best_cost = -1;
346 int start, end;
347 int dumb_id, nb_dumb;
348 int vl = tm_get_verbose_level();
349
350
351 if(nb_constraints > n){
352 if(vl >= ERROR){
353 fprintf(stderr,"Error more constraints (%d) than the problem size (%d)!\n",nb_constraints, n);
354 }
355 return NULL;
356 }
357
358 max_size = n/k;
359
360 if(vl >= DEBUG){
361 printf("max_size = %d (n=%d,k=%d)\ncom_mat->n-1=%d\n",max_size,n,k,com_mat->n-1);
362 printf("nb_constraints = %d\n",nb_constraints);
363
364 if(n<=16){
365 printf("Constraints: ");print_1D_tab(constraints,nb_constraints);
366 }
367 }
368
369
370
371
372
373 for( nb_trials = 0 ; nb_trials < MAX_TRIALS ; nb_trials++ ){
374 partition = (int *)MALLOC(sizeof(int)*n);
375 for ( i = 0 ; i < n ; i ++ )
376 partition[i] = -1;
377
378 size = (int *)CALLOC(k,sizeof(int));
379
380
381
382
383
384 if (nb_constraints){
385 start = 0;
386 dumb_id = n-1;
387 for( i = 0 ; i < k ; i ++){
388 max_val = (i+1)* (n/k);
389 end = start;
390 while( end < nb_constraints){
391 if(constraints[end] >= max_val)
392 break;
393 end++;
394 }
395
396
397
398
399 nb_dumb = n/k - (end-start);
400
401
402
403
404
405 for( j = 0; j < nb_dumb; j ++ ){
406 partition[dumb_id] = i;
407 dumb_id--;
408 }
409
410 size[i] += nb_dumb;
411 start=end;
412 }
413 }
414
415
416
417
418
419
420 for ( i = 0 ; i < k ; i ++ ){
421
422 if(size[i] >= max_size)
423 continue;
424
425 do{
426
427 j = genrand_int32() % n;
428 } while ( partition[j] != -1 );
429
430 partition[j] = i;
431
432
433
434 size[i]++;
435 }
436
437
438 for( i = 0 ; i < n ; i ++)
439 if( partition[i] == -1)
440 allocate_vertex(i, partition, com_mat, n, size, max_size);
441
442 cost = eval_cost(partition,com_mat);
443
444
445
446
447 if((cost<best_cost) || (best_cost == -1)){
448 best_cost=cost;
449 FREE(best_partition);
450 best_partition=partition;
451 }else
452 FREE(partition);
453
454 FREE(size);
455 }
456
457
458
459
460 return best_partition;
461 }
462
463 int *kpartition(int k, com_mat_t *com_mat, int n, int *constraints, int nb_constraints)
464 {
465 int *res= NULL;
466
467 if( n%k != 0){
468 if(verbose_level >= ERROR)
469 fprintf(stderr,"Error: Cannot partition %d elements in %d parts\n",n,k);
470 return NULL;
471 }
472
473
474
475
476
477
478 #if defined(HAVE_LIBSCOTCH)
479 if(!greedy_flag){
480 if(verbose_level >= DEBUG)
481 printf("Using Scotch\n");
482 res = kpartition_scotch(k, com_mat, n, constraints, nb_constraints);
483 }else{
484 if(verbose_level >= DEBUG)
485 printf("Using greedy partitionning\n");
486 res = kpartition_greedy(k, com_mat, n, constraints, nb_constraints);
487 }
488 #else
489 if(verbose_level >= DEBUG)
490 printf("Using greedy partitionning\n");
491 res = kpartition_greedy(k, com_mat, n, constraints, nb_constraints);
492 #endif
493 return res;
494 }
495
496 constraint_t *split_constraints (int *constraints, int nb_constraints, int k, tm_topology_t *topology, int depth, int N)
497 {
498 constraint_t *const_tab = NULL;
499 int nb_leaves, start, end;
500 int i;
501 int vl = tm_get_verbose_level();
502
503 const_tab = (constraint_t *)CALLOC(k,sizeof(constraint_t));
504
505
506
507
508 nb_leaves = compute_nb_leaves_from_level( depth + 1, topology );
509
510
511
512
513 start = 0;
514
515 for( i = 0; i < k; i++ ){
516
517
518 end = fill_tab(&(const_tab[i].constraints), constraints, nb_constraints,start, (i+1) * nb_leaves, i * nb_leaves);
519 const_tab[i].length = end-start;
520 if(vl>=DEBUG){
521 printf("Step %d\n",i);
522 printf("\tConstraint: "); print_1D_tab(constraints, nb_constraints);
523 printf("\tSub constraint: "); print_1D_tab(const_tab[i].constraints, end-start);
524 }
525
526 if(end-start > N/k){
527 if(vl >= ERROR){
528 fprintf(stderr, "Error in spliting constraint at step %d. N=%d k= %d, length = %d\n", i, N, k, end-start);
529 }
530 FREE(const_tab);
531 return NULL;
532 }
533 const_tab[i].id = i;
534 start = end;
535 }
536
537 return const_tab;
538 }
539
540
541
542 com_mat_t **split_com_mat(com_mat_t *com_mat, int n, int k, int *partition)
543 {
544 com_mat_t **res = NULL, *sub_com_mat;
545 double **sub_mat = NULL;
546 int *perm = NULL;
547 int cur_part, i, ii, j, jj, m = n/k, s;
548
549 res = (com_mat_t**)MALLOC(k*sizeof(com_mat_t *));
550
551
552 if(verbose_level >= DEBUG){
553 printf("Partition: "); print_1D_tab(partition,n);
554 display_tab(com_mat->comm,com_mat->n);
555 printf("m=%d,n=%d,k=%d\n",m,n,k);
556 printf("perm=%p\n", (void *)perm);
557 }
558
559 perm = (int*)MALLOC(sizeof(int)*m);
560 for( cur_part = 0 ; cur_part < k ; cur_part ++ ){
561
562
563 s = 0;
564
565
566
567
568 for( j = 0; j < com_mat->n; j ++)
569 if ( partition[j] == cur_part )
570 perm[s++] = j;
571
572 if(s>m){
573 if(verbose_level >= CRITICAL){
574 fprintf(stderr,"Partition: "); print_1D_tab(partition,n);
575 display_tab(com_mat->comm,com_mat->n);
576 fprintf(stderr,"too many elements of the partition for the permuation (s=%d>%d=m). n=%d, k=%d, cur_part= %d\n",s,m,n,k, cur_part);
577 }
578 exit(-1);
579 }
580
581
582 sub_mat = (double **) MALLOC(sizeof(double *) * s);
583 for( i = 0 ; i < s ; i++)
584 sub_mat[i] = (double *) MALLOC(sizeof(double ) * s);
585
586
587 for ( i = 0 ; i < s ; i ++){
588 ii = perm[i];
589 for( j = i ; j < s ; j ++){
590 jj = perm[j];
591 sub_mat[i][j] = com_mat->comm[ii][jj];
592 sub_mat[j][i] = sub_mat[i][j];
593 }
594 }
595
596 sub_com_mat = (com_mat_t *)MALLOC(sizeof(com_mat_t));
597 sub_com_mat -> n = s;
598 sub_com_mat -> comm = sub_mat;
599
600
601
602
603
604 res[cur_part] = sub_com_mat;
605 }
606
607 FREE(perm);
608
609 return res;
610 }
611
612 int **split_vertices( int *vertices, int n, int k, int *partition)
613 {
614 int **res = NULL, *sub_vertices = NULL;
615 int m = n/k;
616 int i, j, cur_part;
617
618
619 res = (int**) MALLOC(sizeof(int*) * k);
620
621
622 if(verbose_level >= DEBUG){
623 printf("Partition: ");print_1D_tab(partition,n);
624 printf("Vertices id: ");print_1D_tab(vertices,n);
625 }
626
627
628 for( cur_part = 0; cur_part < k ; cur_part ++){
629 sub_vertices = (int*) MALLOC(sizeof(int) * m);
630 i = 0;
631 for( j = 0; j < n; j ++)
632 if ( partition[j] == cur_part )
633 sub_vertices[i++] = vertices[j];
634 res[cur_part] = sub_vertices;
635 if(verbose_level >= DEBUG){
636 printf("partition %d: ",cur_part);print_1D_tab(sub_vertices,m);
637 }
638 }
639
640 return res;
641 }
642
643 void free_tab_com_mat(com_mat_t **mat,int k)
644 {
645 int i,j;
646 if( !mat )
647 return;
648
649 for ( i = 0 ; i < k ; i ++){
650 for ( j = 0 ; j < mat[i]->n ; j ++)
651 FREE( mat[i]->comm[j] );
652 FREE( mat[i]->comm );
653 FREE(mat[i]);
654
655 }
656 FREE(mat);
657 }
658
659 void free_tab_local_vertices(int **mat, int k)
660 {
661 int i;
662 if( !mat )
663 return;
664
665 for ( i = 0 ; i < k ; i ++){
666 FREE( mat[i] );
667 }
668 FREE(mat);
669 }
670
671
672 void free_const_tab(constraint_t *const_tab, int k)
673 {
674 int i;
675
676 if( !const_tab )
677 return;
678
679 for(i = 0; i < k; i++){
680 if(const_tab[i].length)
681 FREE(const_tab[i].constraints);
682 }
683
684 FREE(const_tab);
685 }
686
687 #if 0
688 static void check_com_mat(com_mat_t *com_mat){
689 int i,j;
690
691 for( i = 0 ; i < com_mat->n ; i++ )
692 for( j = 0 ; j < com_mat->n ; j++ )
693 if(com_mat->comm[i][j]<0){
694 printf("com_mat->comm[%d][%d]= %f\n",i,j,com_mat->comm[i][j]);
695 exit(-1);
696 }
697 }
698 #endif
699
700 static void print_tab(int n){
701 for(;n;n--)
702 fprintf(stdout,"\t");
703 }
704
705 static void display_partition(int *partition, int *local_vertices, int n, int depth, int k){
706 int cur_part, j;
707 print_tab(depth);fprintf(stdout,"Partitions at depth=%d\n",depth);
708 for( cur_part = 0; cur_part < k ; cur_part ++){
709 print_tab(depth); fprintf(stdout,"%d :",cur_part);
710 for( j = 0; j < n; j ++){
711 if ( partition[j] == cur_part ){
712 if(local_vertices[j]!=-1)
713 fprintf(stdout,"%d ",local_vertices[j]);
714 }
715 }
716 fprintf(stdout,"\n");
717 }
718 }
719
720 void kpartition_build_level_topology(tm_tree_t *cur_node, com_mat_t *com_mat, int N, int depth,
721 tm_topology_t *topology, int *local_vertices,
722 int *constraints, int nb_constraints,
723 double *obj_weight, double *comm_speed)
724 {
725 com_mat_t **tab_com_mat = NULL;
726 int k = topology->arity[depth];
727 tm_tree_t **tab_child = NULL;
728 int *partition = NULL;
729 int **tab_local_vertices = NULL;
730 constraint_t *const_tab = NULL;
731 int i;
732 verbose_level = tm_get_verbose_level();
733
734
735
736 if ( depth == topology->nb_levels - 1 ){
737 if(verbose_level>=DEBUG)
738 printf("id : %d, com_mat= %p\n",local_vertices[0], (void *)com_mat->comm);
739 set_node(cur_node,NULL, 0, NULL, local_vertices[0], 0, NULL, depth);
740 return;
741 }
742
743
744 if(verbose_level >= DEBUG){
745 printf("Partitionning Matrix of size %d (problem size= %d) in %d partitions\n", com_mat->n, N, k);
746 }
747
748
749
750
751 partition = kpartition(k, com_mat, N, constraints, nb_constraints);
752
753 if(verbose_level>=INFO)
754 display_partition(partition, local_vertices, N, depth, k);
755
756
757
758 tab_com_mat = split_com_mat( com_mat, N, k, partition);
759
760
761 tab_local_vertices = split_vertices( local_vertices, N, k, partition);
762
763
764 const_tab = split_constraints (constraints, nb_constraints, k, topology, depth, N);
765
766
767 tab_child = (tm_tree_t **) CALLOC (k,sizeof(tm_tree_t*));
768 for( i = 0 ; i < k ; i++){
769 tab_child[i] = (tm_tree_t *) MALLOC(sizeof(tm_tree_t));
770 }
771
772
773 for( i = 0 ; i < k ; i++){
774 tab_child[i]->id = i;
775 kpartition_build_level_topology ( tab_child[i], tab_com_mat[i], N/k, depth + 1,
776 topology, tab_local_vertices[i],
777 const_tab[i].constraints, const_tab[i].length,
778 obj_weight, comm_speed);
779 tab_child[i]->parent = cur_node;
780 }
781
782
783 set_node( cur_node, tab_child, k, NULL, cur_node->id, 0, NULL, depth);
784
785
786 FREE(partition);
787 free_tab_com_mat(tab_com_mat,k);
788 free_tab_local_vertices(tab_local_vertices,k);
789 free_const_tab(const_tab,k);
790 }
791
792
793 tm_tree_t *kpartition_build_tree_from_topology(tm_topology_t *topology,double **comm,int N, int *constraints, int nb_constraints, double *obj_weight, double *com_speed)
794 {
795 int depth,i, K;
796 tm_tree_t *root = NULL;
797 int *local_vertices = NULL;
798 int nb_cores;
799 com_mat_t com_mat;
800
801 verbose_level = tm_get_verbose_level();
802
803
804 nb_cores=nb_processing_units(topology)*topology->oversub_fact;
805
806
807 if(verbose_level>=INFO)
808 printf("Number of constraints: %d, N=%d, nb_cores = %d, K=%d\n", nb_constraints, N, nb_cores, nb_cores-N);
809
810 if((constraints == NULL) && (nb_constraints != 0)){
811 if(verbose_level>=ERROR)
812 fprintf(stderr,"size of constraint table not zero while constraint tab is NULL\n");
813 return NULL;
814 }
815
816 if((constraints != NULL) && (nb_constraints > nb_cores)){
817 if(verbose_level>=ERROR)
818 fprintf(stderr,"size of constraint table (%d) is greater than the number of cores (%d)\n", nb_constraints, nb_cores);
819 return NULL;
820 }
821
822 depth = 0;
823
824
825 if((K=nb_cores - N)>0){
826
827 complete_obj_weight(&obj_weight,N,K);
828 } else if( K < 0){
829 if(verbose_level>=ERROR)
830 fprintf(stderr,"Not enough cores!\n");
831 return NULL;
832 }
833
834 com_mat.comm = comm;
835 com_mat.n = N;
836
837
838
839
840
841
842
843
844
845
846
847
848 local_vertices = (int*) MALLOC (sizeof(int) * (K+N));
849
850 for( i = 0 ; i < MIN(N,nb_constraints) ; i++)
851 local_vertices[i] = i;
852 for( i = MIN(N,nb_constraints) ;i < N + K ; i++)
853 local_vertices[i] = -1;
854
855
856
857 root = (tm_tree_t*) MALLOC (sizeof(tm_tree_t));
858 root -> id = 0;
859
860
861
862 kpartition_build_level_topology(root, &com_mat, N+K, depth, topology, local_vertices,
863 constraints, nb_constraints, obj_weight, com_speed);
864
865
866 if(verbose_level>=INFO)
867 printf("Build (bottom-up) tree done!\n");
868
869
870
871 FREE(local_vertices);
872
873
874
875 root->constraint = 1;
876
877 return root;
878 }
879
880