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

   1 /* -*- Mode: C; c-basic-offset:4 ; indent-tabs-mode:nil ; -*- */
   2 /*
   3  *  (C) 2003 by Argonne National Laboratory.
   4  *      See COPYRIGHT in top-level directory.
   5  */
   6
   7 /*            MPI-3 distributed linked list construction example
   8  *            --------------------------------------------------
   9  *
  10  * Construct a distributed shared linked list using proposed MPI-3 dynamic
  11  * windows.  Initially process 0 creates the head of the list, attaches it to
  12  * the window, and broadcasts the pointer to all processes.  Each process p then
  13  * appends N new elements to the list when the tail reaches process p-1.
  14  */
  15
  16 #include <stdio.h>
  17 #include <stdlib.h>
  18 #include <mpi.h>
  19 #include <assert.h>
  20 #include "mpitest.h"
  21
  22 #ifdef HAVE_UNISTD_H
  23 #include <unistd.h>
  24 #endif
  25
  26 #define NUM_ELEMS 1000
  27 #define MAX_NPROBE nproc
  28 #define MIN_NPROBE 1
  29 #define ELEM_PER_ROW 16
  30
  31 #define MIN(X,Y) ((X < Y) ? (X) : (Y))
  32 #define MAX(X,Y) ((X > Y) ? (X) : (Y))
  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 static const int verbose = 0;
  48 static const int print_perf = 0;
  49
  50 /* List of locally allocated list elements. */
  51 static llist_elem_t **my_elems = NULL;
  52 static int my_elems_size  = 0;
  53 static int my_elems_count = 0;
  54
  55 /* Allocate a new shared linked list element */
  56 MPI_Aint alloc_elem(int value, MPI_Win win) {
  57     MPI_Aint disp;
  58     llist_elem_t *elem_ptr;
  59
  60     /* Allocate the new element and register it with the window */
  61     MPI_Alloc_mem(sizeof(llist_elem_t), MPI_INFO_NULL, &elem_ptr);
  62     elem_ptr->value = value;
  63     elem_ptr->next  = nil;
  64     MPI_Win_attach(win, elem_ptr, sizeof(llist_elem_t));
  65
  66     /* Add the element to the list of local elements so we can free it later. */
  67     if (my_elems_size == my_elems_count) {
  68         my_elems_size += 100;
  69         my_elems = realloc(my_elems, my_elems_size*sizeof(void*));
  70     }
  71     my_elems[my_elems_count] = elem_ptr;
  72     my_elems_count++;
  73
  74     MPI_Get_address(elem_ptr, &disp);
  75     return disp;
  76 }
  77
  78 int main(int argc, char **argv) {
  79     int           procid, nproc, i, j, my_nelem;
  80     int           pollint = 0;
  81     double        time;
  82     MPI_Win       llist_win;
  83     llist_ptr_t   head_ptr, tail_ptr;
  84
  85     MPI_Init(&argc, &argv);
  86
  87     MPI_Comm_rank(MPI_COMM_WORLD, &procid);
  88     MPI_Comm_size(MPI_COMM_WORLD, &nproc);
  89
  90     MPI_Win_create_dynamic(MPI_INFO_NULL, MPI_COMM_WORLD, &llist_win);
  91
  92     /* Process 0 creates the head node */
  93     if (procid == 0)
  94         head_ptr.disp = alloc_elem(procid, llist_win);
  95
  96     /* Broadcast the head pointer to everyone */
  97     head_ptr.rank = 0;
  98     MPI_Bcast(&head_ptr.disp, 1, MPI_AINT, 0, MPI_COMM_WORLD);
  99     tail_ptr = head_ptr;
 100
 101     /* All processes append NUM_ELEMS elements to the list; rank 0 has already
 102      * appended an element. */
 103     if (procid == 0)
 104         i = 1;
 105     else
 106         i = 0;
 107
 108     my_nelem = NUM_ELEMS/nproc;
 109     if (procid < NUM_ELEMS % nproc)
 110         my_nelem++;
 111
 112     MPI_Barrier(MPI_COMM_WORLD);
 113     time = MPI_Wtime();
 114
 115     for ( ; i < my_nelem; i++) {
 116         llist_ptr_t new_elem_ptr;
 117         int success = 0;
 118
 119         /* Create a new list element and register it with the window */
 120         new_elem_ptr.rank = procid;
 121         new_elem_ptr.disp = alloc_elem(procid, llist_win);
 122
 123         /* Append the new node to the list.  This might take multiple attempts if
 124            others have already appended and our tail pointer is stale. */
 125         do {
 126             int flag;
 127
 128             /* The tail is at my left neighbor, append my element. */
 129             if (tail_ptr.rank == (procid + nproc-1) % nproc)
 130             {
 131                 if (verbose)
 132                     printf("%d: Appending to <%d, %p>\n", procid, tail_ptr.rank, (void*) tail_ptr.disp);
 133
 134 #ifdef USE_MODE_NOCHECK
 135                 MPI_Win_lock(MPI_LOCK_SHARED, tail_ptr.rank, MPI_MODE_NOCHECK, llist_win);
 136 #else
 137                 MPI_Win_lock(MPI_LOCK_SHARED, tail_ptr.rank, 0, llist_win);
 138 #endif
 139                 MPI_Accumulate(&new_elem_ptr, sizeof(llist_ptr_t), MPI_BYTE, tail_ptr.rank,
 140                                (MPI_Aint) &(((llist_elem_t*)tail_ptr.disp)->next), sizeof(llist_ptr_t),
 141                                MPI_BYTE, MPI_REPLACE, llist_win);
 142                 MPI_Win_unlock(tail_ptr.rank, llist_win);
 143
 144                 success = 1;
 145                 tail_ptr = new_elem_ptr;
 146             }
 147
 148             /* Otherwise, chase the tail. */
 149             else
 150             {
 151                 llist_ptr_t next_tail_ptr;
 152
 153 #ifdef USE_MODE_NOCHECK
 154                 MPI_Win_lock(MPI_LOCK_SHARED, tail_ptr.rank, MPI_MODE_NOCHECK, llist_win);
 155 #else
 156                 MPI_Win_lock(MPI_LOCK_SHARED, tail_ptr.rank, 0, llist_win);
 157 #endif
 158                 MPI_Get_accumulate( NULL, 0, MPI_DATATYPE_NULL, &next_tail_ptr,
 159                                     sizeof(llist_ptr_t), MPI_BYTE, tail_ptr.rank,
 160                                     (MPI_Aint) &(((llist_elem_t*)tail_ptr.disp)->next),
 161                                     sizeof(llist_ptr_t), MPI_BYTE, MPI_NO_OP, llist_win);
 162                 MPI_Win_unlock(tail_ptr.rank, llist_win);
 163
 164                 if (next_tail_ptr.rank != nil.rank) {
 165                     if (verbose)
 166                         printf("%d: Chasing to <%d, %p>\n", procid, next_tail_ptr.rank, (void*) next_tail_ptr.disp);
 167                     tail_ptr = next_tail_ptr;
 168                     pollint = MAX(MIN_NPROBE, pollint/2);
 169                 }
 170                 else {
 171                     for (j = 0; j < pollint; j++)
 172                         MPI_Iprobe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &flag, MPI_STATUS_IGNORE);
 173
 174                     pollint = MIN(MAX_NPROBE, pollint*2);
 175                 }
 176             }
 177         } while (!success);
 178     }
 179
 180     MPI_Barrier(MPI_COMM_WORLD);
 181     time = MPI_Wtime() - time;
 182
 183     /* Traverse the list and verify that all processes inserted exactly the correct
 184        number of elements. */
 185     if (procid == 0) {
 186         int  errors    = 0;
 187         int *counts, count = 0;
 188
 189         counts = (int*) malloc(sizeof(int) * nproc);
 190         assert(counts != NULL);
 191
 192         for (i = 0; i < nproc; i++)
 193             counts[i] = 0;
 194
 195         tail_ptr = head_ptr;
 196
 197         MPI_Win_lock_all(0, llist_win);
 198
 199         /* Walk the list and tally up the number of elements inserted by each rank */
 200         while (tail_ptr.disp != nil.disp) {
 201             llist_elem_t elem;
 202
 203             MPI_Get(&elem, sizeof(llist_elem_t), MPI_BYTE,
 204                     tail_ptr.rank, tail_ptr.disp, sizeof(llist_elem_t), MPI_BYTE, llist_win);
 205
 206             MPI_Win_flush(tail_ptr.rank, llist_win);
 207
 208             tail_ptr = elem.next;
 209
 210             assert(elem.value >= 0 && elem.value < nproc);
 211             counts[elem.value]++;
 212             count++;
 213
 214             if (verbose) {
 215                 int last_elem = tail_ptr.disp == nil.disp;
 216                 printf("%2d%s", elem.value, last_elem ? "" : " -> ");
 217                 if (count % ELEM_PER_ROW == 0 && !last_elem)
 218                     printf("\n");
 219             }
 220         }
 221
 222         MPI_Win_unlock_all(llist_win);
 223
 224         if (verbose)
 225           printf("\n\n");
 226
 227         /* Verify the counts we collected */
 228         for (i = 0; i < nproc; i++) {
 229             int expected;
 230
 231             expected = NUM_ELEMS/nproc;
 232             if (i < NUM_ELEMS % nproc)
 233                 expected++;
 234
 235             if (counts[i] != expected) {
 236                 printf("Error: Rank %d inserted %d elements, expected %d\n", i, counts[i], expected);
 237                 errors++;
 238             }
 239         }
 240
 241         printf("%s\n", errors == 0 ? " No Errors" : "FAIL");
 242         free(counts);
 243     }
 244
 245     if (print_perf) {
 246         double max_time;
 247
 248         MPI_Reduce(&time, &max_time, 1, MPI_DOUBLE, MPI_MAX, 0, MPI_COMM_WORLD);
 249
 250         if (procid == 0) {
 251             printf("Total time = %0.2f sec, elem/sec = %0.2f, sec/elem = %0.2f usec\n", max_time, NUM_ELEMS/max_time, max_time/NUM_ELEMS*1.0e6);
 252         }
 253     }
 254
 255     MPI_Win_free(&llist_win);
 256
 257     /* Free all the elements in the list */
 258     for ( ; my_elems_count > 0; my_elems_count--)
 259         MPI_Free_mem(my_elems[my_elems_count-1]);
 260
 261     MPI_Finalize();
 262     return 0;
 263 }