This source file includes following definitions.
- construct
- destruct
- down_search
- main
1
2
3
4
5
6
7
8 #include "orte_config.h"
9
10 #include <stdio.h>
11 #include <unistd.h>
12
13
14
15 #include "opal/util/bit_ops.h"
16 #include "opal/class/opal_list.h"
17 #include "opal/class/opal_bitmap.h"
18
19 #include "orte/util/proc_info.h"
20 #include "orte/runtime/runtime.h"
21
22 typedef struct {
23 opal_list_item_t super;
24 orte_vpid_t vpid;
25 opal_bitmap_t relatives;
26 } orte_routed_tree_t;
27
28 static void construct(orte_routed_tree_t *rt)
29 {
30 rt->vpid = ORTE_VPID_INVALID;
31 OBJ_CONSTRUCT(&rt->relatives, opal_bitmap_t);
32 }
33 static void destruct(orte_routed_tree_t *rt)
34 {
35 OBJ_DESTRUCT(&rt->relatives);
36 }
37 OBJ_CLASS_INSTANCE(orte_routed_tree_t, opal_list_item_t,
38 construct, destruct);
39
40
41 int down_search(int rank, int parent, int me, int num_procs,
42 int *num_children, opal_list_t *children, opal_bitmap_t *relatives)
43 {
44 int i, bitmap, peer, hibit, mask, found;
45 orte_routed_tree_t *child;
46 opal_bitmap_t *relations;
47
48
49 if (me == rank) {
50 bitmap = opal_cube_dim(num_procs);
51
52 hibit = opal_hibit(rank, bitmap);
53 --bitmap;
54
55 for (i = hibit + 1, mask = 1 << i; i <= bitmap; ++i, mask <<= 1) {
56 peer = rank | mask;
57 if (peer < num_procs) {
58 child = OBJ_NEW(orte_routed_tree_t);
59 child->vpid = peer;
60 if (NULL != children) {
61
62 opal_list_append(children, &child->super);
63 (*num_children)++;
64
65 opal_bitmap_init(&child->relatives, num_procs);
66
67 relations = &child->relatives;
68 } else {
69
70 opal_bitmap_set_bit(relatives, peer);
71
72 relations = relatives;
73 }
74
75 down_search(0, 0, peer, num_procs, NULL, NULL, relations);
76 }
77 }
78 return parent;
79 }
80
81
82 bitmap = opal_cube_dim(num_procs);
83
84 hibit = opal_hibit(rank, bitmap);
85 --bitmap;
86
87 for (i = hibit + 1, mask = 1 << i; i <= bitmap; ++i, mask <<= 1) {
88 peer = rank | mask;
89 if (peer < num_procs) {
90
91 if (0 <= (found = down_search(peer, rank, me, num_procs, num_children, children, relatives))) {
92 return found;
93 }
94 }
95 }
96 return -1;
97 }
98
99 int main(int argc, char* argv[])
100 {
101 int i, j;
102 int found;
103 opal_list_t children;
104 opal_list_item_t *item;
105 int num_children;
106 int num_procs;
107 orte_routed_tree_t *child;
108 opal_bitmap_t *relations;
109
110 if (2 != argc) {
111 printf("usage: binom x, where x=number of procs\n");
112 exit(1);
113 }
114
115 orte_init(&argc, &argv, ORTE_PROC_TOOL);
116
117 num_procs = atoi(argv[1]);
118
119 for (i=0; i < num_procs; i++) {
120 OBJ_CONSTRUCT(&children, opal_list_t);
121 num_children = 0;
122 printf("i am %d:", i);
123 found = down_search(0, 0, i, num_procs, &num_children, &children, NULL);
124 printf("\tparent %d num_children %d\n", found, num_children);
125 while (NULL != (item = opal_list_remove_first(&children))) {
126 child = (orte_routed_tree_t*)item;
127 printf("\tchild %d\n", child->vpid);
128 for (j=0; j < num_procs; j++) {
129 if (opal_bitmap_is_set_bit(&child->relatives, j)) {
130 printf("\t\trelation %d\n", j);
131 }
132 }
133 OBJ_RELEASE(item);
134 }
135 OBJ_DESTRUCT(&children);
136 }
137
138 orte_finalize();
139 }