root/orte/test/system/binom.c

DEFINITIONS

1. construct
2. destruct
3. down_search
4. main

   1 /* -*- C -*-
   2  *
   3  * $HEADER$
   4  *
   5  * The most basic of MPI applications
   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     /* is this me? */
  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                     /* this is a direct child - add it to my list */
  62                     opal_list_append(children, &child->super);
  63                     (*num_children)++;
  64                     /* setup the relatives bitmap */
  65                     opal_bitmap_init(&child->relatives, num_procs);
  66                     /* point to the relatives */
  67                     relations = &child->relatives;
  68                 } else {
  69                     /* we are recording someone's relatives - set the bit */
  70                     opal_bitmap_set_bit(relatives, peer);
  71                     /* point to this relations */
  72                     relations = relatives;
  73                 }
  74                 /* search for this child's relatives */
  75                 down_search(0, 0, peer, num_procs, NULL, NULL, relations);
  76             }
  77         }
  78         return parent;
  79     }
  80 
  81     /* find the children of this rank */
  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             /* execute compute on this child */
  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 }