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