teshsuite/smpi/mpich3-test/rma/linked_list_fop.c

   1 /* -*- Mode: C; c-basic-offset:4 ; indent-tabs-mode:nil ; -*- */
   2 /*
   3  *
   4  *  (C) 2003 by Argonne National Laboratory.
   5  *      See COPYRIGHT in top-level directory.
   6  */
   7
   8 /*            MPI-3 distributed linked list construction example
   9  *            --------------------------------------------------
  10  *
  11  * Construct a distributed shared linked list using proposed MPI-3 dynamic
  12  * windows.  Initially process 0 creates the head of the list, attaches it to
  13  * the window, and broadcasts the pointer to all processes.  All processes then
  14  * concurrently append N new elements to the list.  When a process attempts to
  15  * attach its element to the tail of list it may discover that its tail pointer
  16  * is stale and it must chase ahead to the new tail before the element can be
  17  * attached.
  18  */
  19
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <mpi.h>
  23 #include <assert.h>
  24 #include "mpitest.h"
  25
  26 #if HAVE_UNISTD_H
  27 #include <unistd.h>
  28 #endif
  29
  30 #define NUM_ELEMS 32
  31 #define NPROBE    100
  32 #define ELEM_PER_ROW 16
  33
  34 /* Linked list pointer */
  35 typedef struct {
  36     int rank;
  37     MPI_Aint disp;
  38 } llist_ptr_t;
  39
  40 /* Linked list element */
  41 typedef struct {
  42     int value;
  43     llist_ptr_t next;
  44 } llist_elem_t;
  45
  46 static const llist_ptr_t nil = { -1, (MPI_Aint) MPI_BOTTOM };
  47
  48 static const int verbose = 0;
  49
  50 /* Allocate a new shared linked list element */
  51 static MPI_Aint alloc_elem(int value, MPI_Win win, llist_elem_t ***my_elems, int* my_elems_size, int* my_elems_count)
  52 {
  53     MPI_Aint disp;
  54     llist_elem_t *elem_ptr;
  55
  56     /* Allocate the new element and register it with the window */
  57     MPI_Alloc_mem(sizeof(llist_elem_t), MPI_INFO_NULL, &elem_ptr);
  58     elem_ptr->value = value;
  59     elem_ptr->next = nil;
  60     MPI_Win_attach(win, elem_ptr, sizeof(llist_elem_t));
  61
  62     /* Add the element to the list of local elements so we can free it later. */
  63     if (*my_elems_size == *my_elems_count) {
  64         *my_elems_size += 100;
  65         *my_elems = realloc(*my_elems, *my_elems_size * sizeof(void *));
  66     }
  67     (*my_elems)[*my_elems_count] = elem_ptr;
  68     (*my_elems_count)++;
  69
  70     MPI_Get_address(elem_ptr, &disp);
  71     return disp;
  72 }
  73
  74 int main(int argc, char **argv)
  75 {
  76     int procid, nproc, i;
  77     MPI_Win llist_win;
  78     llist_ptr_t head_ptr, tail_ptr;
  79     /* List of locally allocated list elements. */
  80     llist_elem_t **my_elems = NULL;
  81     int my_elems_size = 0;
  82     int my_elems_count = 0;
  83
  84     MPI_Init(&argc, &argv);
  85
  86     MPI_Comm_rank(MPI_COMM_WORLD, &procid);
  87     MPI_Comm_size(MPI_COMM_WORLD, &nproc);
  88
  89     MPI_Win_create_dynamic(MPI_INFO_NULL, MPI_COMM_WORLD, &llist_win);
  90
  91     /* Process 0 creates the head node */
  92     if (procid == 0)
  93         head_ptr.disp = alloc_elem(-1, llist_win, &my_elems, &my_elems_size, &my_elems_count);
  94
  95     /* Broadcast the head pointer to everyone */
  96     head_ptr.rank = 0;
  97     MPI_Bcast(&head_ptr.disp, 1, MPI_AINT, 0, MPI_COMM_WORLD);
  98     tail_ptr = head_ptr;
  99
 100     /* All processes concurrently append NUM_ELEMS elements to the list */
 101     for (i = 0; i < NUM_ELEMS; i++) {
 102         llist_ptr_t new_elem_ptr;
 103         int success;
 104
 105         /* Create a new list element and register it with the window */
 106         new_elem_ptr.rank = procid;
 107         new_elem_ptr.disp = alloc_elem(procid, llist_win, &my_elems, &my_elems_size, &my_elems_count);
 108
 109         /* Append the new node to the list.  This might take multiple attempts if
 110          * others have already appended and our tail pointer is stale. */
 111         do {
 112             llist_ptr_t next_tail_ptr = nil;
 113
 114             MPI_Win_lock(MPI_LOCK_SHARED, tail_ptr.rank, MPI_MODE_NOCHECK, llist_win);
 115
 116             MPI_Compare_and_swap((void *) &new_elem_ptr.rank, (void *) &nil.rank,
 117                                  (void *) &next_tail_ptr.rank, MPI_INT, tail_ptr.rank,
 118                                  (MPI_Aint) & (((llist_elem_t *) tail_ptr.disp)->next.rank),
 119                                  llist_win);
 120
 121             MPI_Win_unlock(tail_ptr.rank, llist_win);
 122             success = (next_tail_ptr.rank == nil.rank);
 123
 124             if (success) {
 125                 int i, flag;
 126                 MPI_Aint result;
 127
 128                 MPI_Win_lock(MPI_LOCK_SHARED, tail_ptr.rank, MPI_MODE_NOCHECK, llist_win);
 129
 130                 MPI_Fetch_and_op(&new_elem_ptr.disp, &result, MPI_AINT, tail_ptr.rank,
 131                                  (MPI_Aint) & (((llist_elem_t *) tail_ptr.disp)->next.disp),
 132                                  MPI_REPLACE, llist_win);
 133
 134                 /* Note: accumulate is faster, since we don't need the result.  Replacing with
 135                  * Fetch_and_op to create a more complete test case. */
 136                 /*
 137                  * MPI_Accumulate(&new_elem_ptr.disp, 1, MPI_AINT, tail_ptr.rank,
 138                  * (MPI_Aint) &(((llist_elem_t*)tail_ptr.disp)->next.disp), 1,
 139                  * MPI_AINT, MPI_REPLACE, llist_win);
 140                  */
 141
 142                 MPI_Win_unlock(tail_ptr.rank, llist_win);
 143                 tail_ptr = new_elem_ptr;
 144
 145                 /* For implementations that use pt-to-pt messaging, force progress for other threads'
 146                  * RMA operations. */
 147                 for (i = 0; i < NPROBE; i++)
 148                     MPI_Iprobe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &flag,
 149                                MPI_STATUS_IGNORE);
 150
 151             }
 152             else {
 153                 /* Tail pointer is stale, fetch the displacement.  May take multiple tries
 154                  * if it is being updated. */
 155                 do {
 156                     MPI_Win_lock(MPI_LOCK_SHARED, tail_ptr.rank, MPI_MODE_NOCHECK, llist_win);
 157
 158                     MPI_Fetch_and_op(NULL, &next_tail_ptr.disp, MPI_AINT, tail_ptr.rank,
 159                                      (MPI_Aint) & (((llist_elem_t *) tail_ptr.disp)->next.disp),
 160                                      MPI_NO_OP, llist_win);
 161
 162                     MPI_Win_unlock(tail_ptr.rank, llist_win);
 163                 } while (next_tail_ptr.disp == nil.disp);
 164                 tail_ptr = next_tail_ptr;
 165             }
 166         } while (!success);
 167     }
 168
 169     MPI_Barrier(MPI_COMM_WORLD);
 170
 171     /* Traverse the list and verify that all processes inserted exactly the correct
 172      * number of elements. */
 173     if (procid == 0) {
 174         int have_root = 0;
 175         int errors = 0;
 176         int *counts, count = 0;
 177
 178         counts = (int *) malloc(sizeof(int) * nproc);
 179         assert(counts != NULL);
 180
 181         for (i = 0; i < nproc; i++)
 182             counts[i] = 0;
 183
 184         tail_ptr = head_ptr;
 185
 186         /* Walk the list and tally up the number of elements inserted by each rank */
 187         while (tail_ptr.disp != nil.disp) {
 188             llist_elem_t elem;
 189
 190             MPI_Win_lock(MPI_LOCK_SHARED, tail_ptr.rank, MPI_MODE_NOCHECK, llist_win);
 191
 192             MPI_Get(&elem, sizeof(llist_elem_t), MPI_BYTE,
 193                     tail_ptr.rank, tail_ptr.disp, sizeof(llist_elem_t), MPI_BYTE, llist_win);
 194
 195             MPI_Win_unlock(tail_ptr.rank, llist_win);
 196
 197             tail_ptr = elem.next;
 198
 199             /* This is not the root */
 200             if (have_root) {
 201                 assert(elem.value >= 0 && elem.value < nproc);
 202                 counts[elem.value]++;
 203                 count++;
 204
 205                 if (verbose) {
 206                     int last_elem = tail_ptr.disp == nil.disp;
 207                     printf("%2d%s", elem.value, last_elem ? "" : " -> ");
 208                     if (count % ELEM_PER_ROW == 0 && !last_elem)
 209                         printf("\n");
 210                 }
 211             }
 212
 213             /* This is the root */
 214             else {
 215                 assert(elem.value == -1);
 216                 have_root = 1;
 217             }
 218         }
 219
 220         if (verbose)
 221             printf("\n\n");
 222
 223         /* Verify the counts we collected */
 224         for (i = 0; i < nproc; i++) {
 225             int expected = NUM_ELEMS;
 226
 227             if (counts[i] != expected) {
 228                 printf("Error: Rank %d inserted %d elements, expected %d\n", i, counts[i],
 229                        expected);
 230                 errors++;
 231             }
 232         }
 233
 234         printf("%s\n", errors == 0 ? " No Errors" : "FAIL");
 235         free(counts);
 236     }
 237
 238     MPI_Win_free(&llist_win);
 239
 240     /* Free all the elements in the list */
 241     for (; my_elems_count > 0; my_elems_count--)
 242         MPI_Free_mem(my_elems[my_elems_count - 1]);
 243
 244     MPI_Finalize();
 245     return 0;
 246 }