This source file includes following definitions.
- hwloc_internal_distances_init
- hwloc_internal_distances_prepare
- hwloc_internal_distances_free
- hwloc_internal_distances_destroy
- hwloc_internal_distances_dup_one
- hwloc_internal_distances_dup
- hwloc_distances_remove
- hwloc_distances_remove_by_depth
- hwloc_internal_distances__add
- hwloc_internal_distances_add_by_index
- hwloc_internal_distances_add
- hwloc_distances_add
- hwloc_find_obj_by_type_and_gp_index
- hwloc_internal_distances_restrict
- hwloc_internal_distances_refresh_one
- hwloc_internal_distances_refresh
- hwloc_internal_distances_invalidate_cached_objs
- hwloc_distances_release
- hwloc_distances_get_one
- hwloc__distances_get
- hwloc_distances_get
- hwloc_distances_get_by_depth
- hwloc_report_user_distance_error
- hwloc_compare_values
- hwloc__find_groups_by_min_distance
- hwloc__check_grouping_matrix
- hwloc__groups_by_distances
1
2
3
4
5
6
7
8 #include <private/autogen/config.h>
9 #include <hwloc.h>
10 #include <private/private.h>
11 #include <private/debug.h>
12 #include <private/misc.h>
13
14 #include <float.h>
15 #include <math.h>
16
17
18
19
20
21
22 void hwloc_internal_distances_init(struct hwloc_topology *topology)
23 {
24 topology->first_dist = topology->last_dist = NULL;
25 topology->next_dist_id = 0;
26 }
27
28
29 void hwloc_internal_distances_prepare(struct hwloc_topology *topology)
30 {
31 char *env;
32 hwloc_localeswitch_declare;
33
34 topology->grouping = 1;
35 if (topology->type_filter[HWLOC_OBJ_GROUP] == HWLOC_TYPE_FILTER_KEEP_NONE)
36 topology->grouping = 0;
37 env = getenv("HWLOC_GROUPING");
38 if (env && !atoi(env))
39 topology->grouping = 0;
40
41 if (topology->grouping) {
42 topology->grouping_next_subkind = 0;
43
44 HWLOC_BUILD_ASSERT(sizeof(topology->grouping_accuracies)/sizeof(*topology->grouping_accuracies) == 5);
45 topology->grouping_accuracies[0] = 0.0f;
46 topology->grouping_accuracies[1] = 0.01f;
47 topology->grouping_accuracies[2] = 0.02f;
48 topology->grouping_accuracies[3] = 0.05f;
49 topology->grouping_accuracies[4] = 0.1f;
50 topology->grouping_nbaccuracies = 5;
51
52 hwloc_localeswitch_init();
53 env = getenv("HWLOC_GROUPING_ACCURACY");
54 if (!env) {
55
56 topology->grouping_nbaccuracies = 1;
57 } else if (strcmp(env, "try")) {
58
59 topology->grouping_nbaccuracies = 1;
60 topology->grouping_accuracies[0] = (float) atof(env);
61 }
62 hwloc_localeswitch_fini();
63
64 topology->grouping_verbose = 0;
65 env = getenv("HWLOC_GROUPING_VERBOSE");
66 if (env)
67 topology->grouping_verbose = atoi(env);
68 }
69 }
70
71 static void hwloc_internal_distances_free(struct hwloc_internal_distances_s *dist)
72 {
73 free(dist->indexes);
74 free(dist->objs);
75 free(dist->values);
76 free(dist);
77 }
78
79
80 void hwloc_internal_distances_destroy(struct hwloc_topology * topology)
81 {
82 struct hwloc_internal_distances_s *dist, *next = topology->first_dist;
83 while ((dist = next) != NULL) {
84 next = dist->next;
85 hwloc_internal_distances_free(dist);
86 }
87 topology->first_dist = topology->last_dist = NULL;
88 }
89
90 static int hwloc_internal_distances_dup_one(struct hwloc_topology *new, struct hwloc_internal_distances_s *olddist)
91 {
92 struct hwloc_tma *tma = new->tma;
93 struct hwloc_internal_distances_s *newdist;
94 unsigned nbobjs = olddist->nbobjs;
95
96 newdist = hwloc_tma_malloc(tma, sizeof(*newdist));
97 if (!newdist)
98 return -1;
99
100 newdist->type = olddist->type;
101 newdist->nbobjs = nbobjs;
102 newdist->kind = olddist->kind;
103 newdist->id = olddist->id;
104
105 newdist->indexes = hwloc_tma_malloc(tma, nbobjs * sizeof(*newdist->indexes));
106 newdist->objs = hwloc_tma_calloc(tma, nbobjs * sizeof(*newdist->objs));
107 newdist->objs_are_valid = 0;
108 newdist->values = hwloc_tma_malloc(tma, nbobjs*nbobjs * sizeof(*newdist->values));
109 if (!newdist->indexes || !newdist->objs || !newdist->values) {
110 assert(!tma || !tma->dontfree);
111 hwloc_internal_distances_free(newdist);
112 return -1;
113 }
114
115 memcpy(newdist->indexes, olddist->indexes, nbobjs * sizeof(*newdist->indexes));
116 memcpy(newdist->values, olddist->values, nbobjs*nbobjs * sizeof(*newdist->values));
117
118 newdist->next = NULL;
119 newdist->prev = new->last_dist;
120 if (new->last_dist)
121 new->last_dist->next = newdist;
122 else
123 new->first_dist = newdist;
124 new->last_dist = newdist;
125
126 return 0;
127 }
128
129
130 int hwloc_internal_distances_dup(struct hwloc_topology *new, struct hwloc_topology *old)
131 {
132 struct hwloc_internal_distances_s *olddist;
133 int err;
134 new->next_dist_id = old->next_dist_id;
135 for(olddist = old->first_dist; olddist; olddist = olddist->next) {
136 err = hwloc_internal_distances_dup_one(new, olddist);
137 if (err < 0)
138 return err;
139 }
140 return 0;
141 }
142
143
144
145
146
147 int hwloc_distances_remove(hwloc_topology_t topology)
148 {
149 if (!topology->is_loaded) {
150 errno = EINVAL;
151 return -1;
152 }
153 hwloc_internal_distances_destroy(topology);
154 return 0;
155 }
156
157 int hwloc_distances_remove_by_depth(hwloc_topology_t topology, int depth)
158 {
159 struct hwloc_internal_distances_s *dist, *next;
160 hwloc_obj_type_t type;
161
162 if (!topology->is_loaded) {
163 errno = EINVAL;
164 return -1;
165 }
166
167
168 type = hwloc_get_depth_type(topology, depth);
169 if (type == (hwloc_obj_type_t)-1) {
170 errno = EINVAL;
171 return -1;
172 }
173
174 next = topology->first_dist;
175 while ((dist = next) != NULL) {
176 next = dist->next;
177 if (dist->type == type) {
178 if (next)
179 next->prev = dist->prev;
180 else
181 topology->last_dist = dist->prev;
182 if (dist->prev)
183 dist->prev->next = dist->next;
184 else
185 topology->first_dist = dist->next;
186 hwloc_internal_distances_free(dist);
187 }
188 }
189
190 return 0;
191 }
192
193
194
195
196
197 static void
198 hwloc__groups_by_distances(struct hwloc_topology *topology, unsigned nbobjs, struct hwloc_obj **objs, uint64_t *values, unsigned long kind, unsigned nbaccuracies, float *accuracies, int needcheck);
199
200
201
202
203 static int
204 hwloc_internal_distances__add(hwloc_topology_t topology,
205 hwloc_obj_type_t type, unsigned nbobjs, hwloc_obj_t *objs, uint64_t *indexes, uint64_t *values,
206 unsigned long kind)
207 {
208 struct hwloc_internal_distances_s *dist = calloc(1, sizeof(*dist));
209 if (!dist)
210 goto err;
211
212 dist->type = type;
213 dist->nbobjs = nbobjs;
214 dist->kind = kind;
215
216 if (!objs) {
217 assert(indexes);
218
219 dist->indexes = indexes;
220 dist->objs = calloc(nbobjs, sizeof(hwloc_obj_t));
221 if (!dist->objs)
222 goto err_with_dist;
223 dist->objs_are_valid = 0;
224
225 } else {
226 unsigned i;
227 assert(!indexes);
228
229 dist->objs = objs;
230 dist->objs_are_valid = 1;
231 dist->indexes = malloc(nbobjs * sizeof(*dist->indexes));
232 if (!dist->indexes)
233 goto err_with_dist;
234 if (dist->type == HWLOC_OBJ_PU || dist->type == HWLOC_OBJ_NUMANODE) {
235 for(i=0; i<nbobjs; i++)
236 dist->indexes[i] = objs[i]->os_index;
237 } else {
238 for(i=0; i<nbobjs; i++)
239 dist->indexes[i] = objs[i]->gp_index;
240 }
241 }
242
243 dist->values = values;
244
245 dist->id = topology->next_dist_id++;
246
247 if (topology->last_dist)
248 topology->last_dist->next = dist;
249 else
250 topology->first_dist = dist;
251 dist->prev = topology->last_dist;
252 dist->next = NULL;
253 topology->last_dist = dist;
254 return 0;
255
256 err_with_dist:
257 free(dist);
258 err:
259 free(objs);
260 free(indexes);
261 free(values);
262 return -1;
263 }
264
265 int hwloc_internal_distances_add_by_index(hwloc_topology_t topology,
266 hwloc_obj_type_t type, unsigned nbobjs, uint64_t *indexes, uint64_t *values,
267 unsigned long kind, unsigned long flags)
268 {
269 if (nbobjs < 2) {
270 errno = EINVAL;
271 goto err;
272 }
273
274
275
276
277 if (flags & HWLOC_DISTANCES_ADD_FLAG_GROUP) {
278 errno = EINVAL;
279 goto err;
280 }
281
282 return hwloc_internal_distances__add(topology, type, nbobjs, NULL, indexes, values, kind);
283
284 err:
285 free(indexes);
286 free(values);
287 return -1;
288 }
289
290 int hwloc_internal_distances_add(hwloc_topology_t topology,
291 unsigned nbobjs, hwloc_obj_t *objs, uint64_t *values,
292 unsigned long kind, unsigned long flags)
293 {
294 if (nbobjs < 2) {
295 errno = EINVAL;
296 goto err;
297 }
298
299 if (topology->grouping && (flags & HWLOC_DISTANCES_ADD_FLAG_GROUP)) {
300 float full_accuracy = 0.f;
301 float *accuracies;
302 unsigned nbaccuracies;
303
304 if (flags & HWLOC_DISTANCES_ADD_FLAG_GROUP_INACCURATE) {
305 accuracies = topology->grouping_accuracies;
306 nbaccuracies = topology->grouping_nbaccuracies;
307 } else {
308 accuracies = &full_accuracy;
309 nbaccuracies = 1;
310 }
311
312 if (topology->grouping_verbose) {
313 unsigned i, j;
314 int gp = (objs[0]->type != HWLOC_OBJ_NUMANODE && objs[0]->type != HWLOC_OBJ_PU);
315 fprintf(stderr, "Trying to group objects using distance matrix:\n");
316 fprintf(stderr, "%s", gp ? "gp_index" : "os_index");
317 for(j=0; j<nbobjs; j++)
318 fprintf(stderr, " % 5d", (int)(gp ? objs[j]->gp_index : objs[j]->os_index));
319 fprintf(stderr, "\n");
320 for(i=0; i<nbobjs; i++) {
321 fprintf(stderr, " % 5d", (int)(gp ? objs[i]->gp_index : objs[i]->os_index));
322 for(j=0; j<nbobjs; j++)
323 fprintf(stderr, " % 5lld", (long long) values[i*nbobjs + j]);
324 fprintf(stderr, "\n");
325 }
326 }
327
328 hwloc__groups_by_distances(topology, nbobjs, objs, values,
329 kind, nbaccuracies, accuracies, 1 );
330 }
331
332 return hwloc_internal_distances__add(topology, objs[0]->type, nbobjs, objs, NULL, values, kind);
333
334 err:
335 free(objs);
336 free(values);
337 return -1;
338 }
339
340 #define HWLOC_DISTANCES_KIND_FROM_ALL (HWLOC_DISTANCES_KIND_FROM_OS|HWLOC_DISTANCES_KIND_FROM_USER)
341 #define HWLOC_DISTANCES_KIND_MEANS_ALL (HWLOC_DISTANCES_KIND_MEANS_LATENCY|HWLOC_DISTANCES_KIND_MEANS_BANDWIDTH)
342 #define HWLOC_DISTANCES_KIND_ALL (HWLOC_DISTANCES_KIND_FROM_ALL|HWLOC_DISTANCES_KIND_MEANS_ALL)
343 #define HWLOC_DISTANCES_ADD_FLAG_ALL (HWLOC_DISTANCES_ADD_FLAG_GROUP|HWLOC_DISTANCES_ADD_FLAG_GROUP_INACCURATE)
344
345
346
347 int hwloc_distances_add(hwloc_topology_t topology,
348 unsigned nbobjs, hwloc_obj_t *objs, uint64_t *values,
349 unsigned long kind, unsigned long flags)
350 {
351 hwloc_obj_type_t type;
352 unsigned i;
353 uint64_t *_values;
354 hwloc_obj_t *_objs;
355 int err;
356
357 if (nbobjs < 2 || !objs || !values || !topology->is_loaded) {
358 errno = EINVAL;
359 return -1;
360 }
361 if ((kind & ~HWLOC_DISTANCES_KIND_ALL)
362 || hwloc_weight_long(kind & HWLOC_DISTANCES_KIND_FROM_ALL) != 1
363 || hwloc_weight_long(kind & HWLOC_DISTANCES_KIND_MEANS_ALL) != 1
364 || (flags & ~HWLOC_DISTANCES_ADD_FLAG_ALL)) {
365 errno = EINVAL;
366 return -1;
367 }
368
369
370
371 type = objs[0]->type;
372 if (type == HWLOC_OBJ_GROUP) {
373
374 errno = EINVAL;
375 return -1;
376 }
377
378 for(i=1; i<nbobjs; i++)
379 if (!objs[i] || objs[i]->type != type) {
380 errno = EINVAL;
381 return -1;
382 }
383
384
385 _objs = malloc(nbobjs*sizeof(hwloc_obj_t));
386 _values = malloc(nbobjs*nbobjs*sizeof(*_values));
387 if (!_objs || !_values)
388 goto out_with_arrays;
389
390 memcpy(_objs, objs, nbobjs*sizeof(hwloc_obj_t));
391 memcpy(_values, values, nbobjs*nbobjs*sizeof(*_values));
392 err = hwloc_internal_distances_add(topology, nbobjs, _objs, _values, kind, flags);
393 if (err < 0)
394 goto out;
395
396
397 hwloc_topology_reconnect(topology, 0);
398
399 return 0;
400
401 out_with_arrays:
402 free(_values);
403 free(_objs);
404 out:
405 return -1;
406 }
407
408
409
410
411
412 static hwloc_obj_t hwloc_find_obj_by_type_and_gp_index(hwloc_topology_t topology, hwloc_obj_type_t type, uint64_t gp_index)
413 {
414 hwloc_obj_t obj = hwloc_get_obj_by_type(topology, type, 0);
415 while (obj) {
416 if (obj->gp_index == gp_index)
417 return obj;
418 obj = obj->next_cousin;
419 }
420 return NULL;
421 }
422
423 static void
424 hwloc_internal_distances_restrict(struct hwloc_internal_distances_s *dist,
425 hwloc_obj_t *objs,
426 unsigned disappeared)
427 {
428 unsigned nbobjs = dist->nbobjs;
429 unsigned i, newi;
430 unsigned j, newj;
431
432 for(i=0, newi=0; i<nbobjs; i++)
433 if (objs[i]) {
434 for(j=0, newj=0; j<nbobjs; j++)
435 if (objs[j]) {
436 dist->values[newi*(nbobjs-disappeared)+newj] = dist->values[i*nbobjs+j];
437 newj++;
438 }
439 newi++;
440 }
441
442 for(i=0, newi=0; i<nbobjs; i++)
443 if (objs[i]) {
444 objs[newi] = objs[i];
445 dist->indexes[newi] = dist->indexes[i];
446 newi++;
447 }
448
449 dist->nbobjs -= disappeared;
450 }
451
452 static int
453 hwloc_internal_distances_refresh_one(hwloc_topology_t topology,
454 struct hwloc_internal_distances_s *dist)
455 {
456 hwloc_obj_type_t type = dist->type;
457 unsigned nbobjs = dist->nbobjs;
458 hwloc_obj_t *objs = dist->objs;
459 uint64_t *indexes = dist->indexes;
460 unsigned disappeared = 0;
461 unsigned i;
462
463 if (dist->objs_are_valid)
464 return 0;
465
466 for(i=0; i<nbobjs; i++) {
467 hwloc_obj_t obj;
468
469
470
471 if (type == HWLOC_OBJ_PU)
472 obj = hwloc_get_pu_obj_by_os_index(topology, (unsigned) indexes[i]);
473 else if (type == HWLOC_OBJ_NUMANODE)
474 obj = hwloc_get_numanode_obj_by_os_index(topology, (unsigned) indexes[i]);
475 else
476 obj = hwloc_find_obj_by_type_and_gp_index(topology, type, indexes[i]);
477 objs[i] = obj;
478 if (!obj)
479 disappeared++;
480 }
481
482 if (nbobjs-disappeared < 2)
483
484 return -1;
485
486 if (disappeared)
487 hwloc_internal_distances_restrict(dist, objs, disappeared);
488
489 dist->objs_are_valid = 1;
490 return 0;
491 }
492
493
494 void
495 hwloc_internal_distances_refresh(hwloc_topology_t topology)
496 {
497 struct hwloc_internal_distances_s *dist, *next;
498
499 for(dist = topology->first_dist; dist; dist = next) {
500 next = dist->next;
501
502 if (hwloc_internal_distances_refresh_one(topology, dist) < 0) {
503 assert(!topology->tma || !topology->tma->dontfree);
504 if (dist->prev)
505 dist->prev->next = next;
506 else
507 topology->first_dist = next;
508 if (next)
509 next->prev = dist->prev;
510 else
511 topology->last_dist = dist->prev;
512 hwloc_internal_distances_free(dist);
513 continue;
514 }
515 }
516 }
517
518 void
519 hwloc_internal_distances_invalidate_cached_objs(hwloc_topology_t topology)
520 {
521 struct hwloc_internal_distances_s *dist;
522 for(dist = topology->first_dist; dist; dist = dist->next)
523 dist->objs_are_valid = 0;
524 }
525
526
527
528
529
530 void
531 hwloc_distances_release(hwloc_topology_t topology __hwloc_attribute_unused,
532 struct hwloc_distances_s *distances)
533 {
534 free(distances->values);
535 free(distances->objs);
536 free(distances);
537 }
538
539 static struct hwloc_distances_s *
540 hwloc_distances_get_one(hwloc_topology_t topology __hwloc_attribute_unused,
541 struct hwloc_internal_distances_s *dist)
542 {
543 struct hwloc_distances_s *distances;
544 unsigned nbobjs;
545
546 distances = malloc(sizeof(*distances));
547 if (!distances)
548 return NULL;
549
550 nbobjs = distances->nbobjs = dist->nbobjs;
551
552 distances->objs = malloc(nbobjs * sizeof(hwloc_obj_t));
553 if (!distances->objs)
554 goto out;
555 memcpy(distances->objs, dist->objs, nbobjs * sizeof(hwloc_obj_t));
556
557 distances->values = malloc(nbobjs * nbobjs * sizeof(*distances->values));
558 if (!distances->values)
559 goto out_with_objs;
560 memcpy(distances->values, dist->values, nbobjs*nbobjs*sizeof(*distances->values));
561
562 distances->kind = dist->kind;
563 return distances;
564
565 out_with_objs:
566 free(distances->objs);
567 out:
568 free(distances);
569 return NULL;
570 }
571
572 static int
573 hwloc__distances_get(hwloc_topology_t topology,
574 hwloc_obj_type_t type,
575 unsigned *nrp, struct hwloc_distances_s **distancesp,
576 unsigned long kind, unsigned long flags __hwloc_attribute_unused)
577 {
578 struct hwloc_internal_distances_s *dist;
579 unsigned nr = 0, i;
580
581
582
583
584
585
586 if (flags) {
587 errno = EINVAL;
588 return -1;
589 }
590
591
592
593
594
595
596
597
598
599 hwloc_internal_distances_refresh(topology);
600
601 for(dist = topology->first_dist; dist; dist = dist->next) {
602 unsigned long kind_from = kind & HWLOC_DISTANCES_KIND_FROM_ALL;
603 unsigned long kind_means = kind & HWLOC_DISTANCES_KIND_MEANS_ALL;
604
605 if (type != HWLOC_OBJ_TYPE_NONE && type != dist->type)
606 continue;
607
608 if (kind_from && !(kind_from & dist->kind))
609 continue;
610 if (kind_means && !(kind_means & dist->kind))
611 continue;
612
613 if (nr < *nrp) {
614 struct hwloc_distances_s *distances = hwloc_distances_get_one(topology, dist);
615 if (!distances)
616 goto error;
617 distancesp[nr] = distances;
618 }
619 nr++;
620 }
621
622 for(i=nr; i<*nrp; i++)
623 distancesp[i] = NULL;
624 *nrp = nr;
625 return 0;
626
627 error:
628 for(i=0; i<nr; i++)
629 hwloc_distances_release(topology, distancesp[i]);
630 return -1;
631 }
632
633 int
634 hwloc_distances_get(hwloc_topology_t topology,
635 unsigned *nrp, struct hwloc_distances_s **distancesp,
636 unsigned long kind, unsigned long flags)
637 {
638 if (flags || !topology->is_loaded) {
639 errno = EINVAL;
640 return -1;
641 }
642
643 return hwloc__distances_get(topology, HWLOC_OBJ_TYPE_NONE, nrp, distancesp, kind, flags);
644 }
645
646 int
647 hwloc_distances_get_by_depth(hwloc_topology_t topology, int depth,
648 unsigned *nrp, struct hwloc_distances_s **distancesp,
649 unsigned long kind, unsigned long flags)
650 {
651 hwloc_obj_type_t type;
652
653 if (flags || !topology->is_loaded) {
654 errno = EINVAL;
655 return -1;
656 }
657
658
659 type = hwloc_get_depth_type(topology, depth);
660 if (type == (hwloc_obj_type_t)-1) {
661 errno = EINVAL;
662 return -1;
663 }
664
665 return hwloc__distances_get(topology, type, nrp, distancesp, kind, flags);
666 }
667
668
669
670
671
672 static void hwloc_report_user_distance_error(const char *msg, int line)
673 {
674 static int reported = 0;
675
676 if (!reported && !hwloc_hide_errors()) {
677 fprintf(stderr, "****************************************************************************\n");
678 fprintf(stderr, "* hwloc %s has encountered what looks like an error from user-given distances.\n", HWLOC_VERSION);
679 fprintf(stderr, "*\n");
680 fprintf(stderr, "* %s\n", msg);
681 fprintf(stderr, "* Error occurred in topology.c line %d\n", line);
682 fprintf(stderr, "*\n");
683 fprintf(stderr, "* Please make sure that distances given through the interface or environment\n");
684 fprintf(stderr, "* variables do not contradict any other topology information.\n");
685 fprintf(stderr, "****************************************************************************\n");
686 reported = 1;
687 }
688 }
689
690 static int hwloc_compare_values(uint64_t a, uint64_t b, float accuracy)
691 {
692 if (accuracy != 0.0f && fabsf((float)a-(float)b) < (float)a * accuracy)
693 return 0;
694 return a < b ? -1 : a == b ? 0 : 1;
695 }
696
697
698
699
700
701 static unsigned
702 hwloc__find_groups_by_min_distance(unsigned nbobjs,
703 uint64_t *_values,
704 float accuracy,
705 unsigned *groupids,
706 int verbose)
707 {
708 uint64_t min_distance = UINT64_MAX;
709 unsigned groupid = 1;
710 unsigned i,j,k;
711 unsigned skipped = 0;
712
713 #define VALUE(i, j) _values[(i) * nbobjs + (j)]
714
715 memset(groupids, 0, nbobjs*sizeof(*groupids));
716
717
718 for(i=0; i<nbobjs; i++)
719 for(j=0; j<nbobjs; j++)
720 if (i != j && VALUE(i, j) < min_distance)
721 min_distance = VALUE(i, j);
722 hwloc_debug(" found minimal distance %llu between objects\n", (unsigned long long) min_distance);
723
724 if (min_distance == UINT64_MAX)
725 return 0;
726
727
728 for(i=0; i<nbobjs; i++) {
729 unsigned size;
730 unsigned firstfound;
731
732
733 if (groupids[i])
734 continue;
735
736
737 groupids[i] = groupid;
738 size = 1;
739 firstfound = i;
740
741 while (firstfound != (unsigned)-1) {
742
743
744
745
746 unsigned newfirstfound = (unsigned)-1;
747 for(j=firstfound; j<nbobjs; j++)
748 if (groupids[j] == groupid)
749 for(k=0; k<nbobjs; k++)
750 if (!groupids[k] && !hwloc_compare_values(VALUE(j, k), min_distance, accuracy)) {
751 groupids[k] = groupid;
752 size++;
753 if (newfirstfound == (unsigned)-1)
754 newfirstfound = k;
755 if (i == j)
756 hwloc_debug(" object %u is minimally connected to %u\n", k, i);
757 else
758 hwloc_debug(" object %u is minimally connected to %u through %u\n", k, i, j);
759 }
760 firstfound = newfirstfound;
761 }
762
763 if (size == 1) {
764
765 groupids[i] = 0;
766 skipped++;
767 continue;
768 }
769
770
771 groupid++;
772 if (verbose)
773 fprintf(stderr, " Found transitive graph with %u objects with minimal distance %llu accuracy %f\n",
774 size, (unsigned long long) min_distance, accuracy);
775 }
776
777 if (groupid == 2 && !skipped)
778
779 return 0;
780
781
782 return groupid-1;
783 }
784
785
786 static int
787 hwloc__check_grouping_matrix(unsigned nbobjs, uint64_t *_values, float accuracy, int verbose)
788 {
789 unsigned i,j;
790 for(i=0; i<nbobjs; i++) {
791 for(j=i+1; j<nbobjs; j++) {
792
793 if (hwloc_compare_values(VALUE(i, j), VALUE(j, i), accuracy)) {
794 if (verbose)
795 fprintf(stderr, " Distance matrix asymmetric ([%u,%u]=%llu != [%u,%u]=%llu), aborting\n",
796 i, j, (unsigned long long) VALUE(i, j), j, i, (unsigned long long) VALUE(j, i));
797 return -1;
798 }
799
800 if (hwloc_compare_values(VALUE(i, j), VALUE(i, i), accuracy) <= 0) {
801 if (verbose)
802 fprintf(stderr, " Distance to self not strictly minimal ([%u,%u]=%llu <= [%u,%u]=%llu), aborting\n",
803 i, j, (unsigned long long) VALUE(i, j), i, i, (unsigned long long) VALUE(i, i));
804 return -1;
805 }
806 }
807 }
808 return 0;
809 }
810
811
812
813
814 static void
815 hwloc__groups_by_distances(struct hwloc_topology *topology,
816 unsigned nbobjs,
817 struct hwloc_obj **objs,
818 uint64_t *_values,
819 unsigned long kind,
820 unsigned nbaccuracies,
821 float *accuracies,
822 int needcheck)
823 {
824 HWLOC_VLA(unsigned, groupids, nbobjs);
825 unsigned nbgroups = 0;
826 unsigned i,j;
827 int verbose = topology->grouping_verbose;
828
829 if (nbobjs <= 2)
830 return;
831
832 if (!(kind & HWLOC_DISTANCES_KIND_MEANS_LATENCY))
833
834
835 return;
836
837 for(i=0; i<nbaccuracies; i++) {
838 if (verbose)
839 fprintf(stderr, "Trying to group %u %s objects according to physical distances with accuracy %f\n",
840 nbobjs, hwloc_obj_type_string(objs[0]->type), accuracies[i]);
841 if (needcheck && hwloc__check_grouping_matrix(nbobjs, _values, accuracies[i], verbose) < 0)
842 continue;
843 nbgroups = hwloc__find_groups_by_min_distance(nbobjs, _values, accuracies[i], groupids, verbose);
844 if (nbgroups)
845 break;
846 }
847 if (!nbgroups)
848 return;
849
850 {
851 HWLOC_VLA(hwloc_obj_t, groupobjs, nbgroups);
852 HWLOC_VLA(unsigned, groupsizes, nbgroups);
853 HWLOC_VLA(uint64_t, groupvalues, nbgroups*nbgroups);
854 unsigned failed = 0;
855
856
857 memset(&(groupsizes[0]), 0, sizeof(groupsizes[0]) * nbgroups);
858 for(i=0; i<nbgroups; i++) {
859
860 hwloc_obj_t group_obj, res_obj;
861 group_obj = hwloc_alloc_setup_object(topology, HWLOC_OBJ_GROUP, HWLOC_UNKNOWN_INDEX);
862 group_obj->cpuset = hwloc_bitmap_alloc();
863 group_obj->attr->group.kind = HWLOC_GROUP_KIND_DISTANCE;
864 group_obj->attr->group.subkind = topology->grouping_next_subkind;
865 for (j=0; j<nbobjs; j++)
866 if (groupids[j] == i+1) {
867
868 hwloc_obj_add_other_obj_sets(group_obj, objs[j]);
869 groupsizes[i]++;
870 }
871 hwloc_debug_1arg_bitmap("adding Group object with %u objects and cpuset %s\n",
872 groupsizes[i], group_obj->cpuset);
873 res_obj = hwloc__insert_object_by_cpuset(topology, NULL, group_obj,
874 (kind & HWLOC_DISTANCES_KIND_FROM_USER) ? hwloc_report_user_distance_error : hwloc_report_os_error);
875
876 if (!res_obj)
877 failed++;
878
879 groupobjs[i] = res_obj;
880 }
881 topology->grouping_next_subkind++;
882
883 if (failed)
884
885 return;
886
887
888 memset(&(groupvalues[0]), 0, sizeof(groupvalues[0]) * nbgroups * nbgroups);
889 #undef VALUE
890 #define VALUE(i, j) _values[(i) * nbobjs + (j)]
891 #define GROUP_VALUE(i, j) groupvalues[(i) * nbgroups + (j)]
892 for(i=0; i<nbobjs; i++)
893 if (groupids[i])
894 for(j=0; j<nbobjs; j++)
895 if (groupids[j])
896 GROUP_VALUE(groupids[i]-1, groupids[j]-1) += VALUE(i, j);
897 for(i=0; i<nbgroups; i++)
898 for(j=0; j<nbgroups; j++) {
899 unsigned groupsize = groupsizes[i]*groupsizes[j];
900 GROUP_VALUE(i, j) /= groupsize;
901 }
902 #ifdef HWLOC_DEBUG
903 hwloc_debug("%s", "generated new distance matrix between groups:\n");
904 hwloc_debug("%s", " index");
905 for(j=0; j<nbgroups; j++)
906 hwloc_debug(" % 5d", (int) j);
907 hwloc_debug("%s", "\n");
908 for(i=0; i<nbgroups; i++) {
909 hwloc_debug(" % 5d", (int) i);
910 for(j=0; j<nbgroups; j++)
911 hwloc_debug(" %llu", (unsigned long long) GROUP_VALUE(i, j));
912 hwloc_debug("%s", "\n");
913 }
914 #endif
915
916 hwloc__groups_by_distances(topology, nbgroups, groupobjs, groupvalues, kind, nbaccuracies, accuracies, 0 );
917 }
918 }