Logo AND Algorithmique Numérique Distribuée

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