refine failure generator
[charm.git] / doc / fem / idxl.tex
1 \section{IDXL Communication}
2
3 The FEM framework's communication layer is called IDXL. This small library handles sending and receiving data to and from a sparse subset of 1D indices into a user array.  The sparse index subset is called an "Index List", hence the name of the library.
4
5
6 \subsection{Index Lists}
7 \label{sec:IDXL}
8 An Index List is the fundamental data structure of the IDXL library---for example, the list of shared nodes is an Index List.  IDXL includes routines for building, combining, and sending and receiving Index Lists.
9
10 An Index List, as you might expect, is a list of indices that need to be sent and received.  An Index List includes both the indices that need to be sent, as well as the indices to be received, from each chunk.
11
12 Consider two chunks $a$ and $b$ where $b$ needs some information $a$ has, such as if $b$ has ghosts of real elements on $a$.  $a$'s Index List thus has a send portion with the $a$-local indices for the elements $a$ sends; and $b$'s Index List contains a receive portion with the $b$-local indices for the elements $b$ receives.  Thus across processors, the corresponding send and receive portions of $a$ and $b$'s Index Lists match, as shown in Figure~\ref{fig:indexlists}.
13
14
15 \begin{figure}[h]
16 \begin{center}
17 \includegraphics[width=5in]{fig/indexlists}
18 \end{center}
19 \caption{Illustrating how Index Lists match up $a$'s source elements with $b$'s ghost elements.}
20 \label{fig:indexlists}
21 \end{figure}
22
23
24
25 %%%%%%%%%%%%%%%%%%% Index Lists %%%%%%%%%%%%%%%%%%%%
26 \subsubsection{Index List Calls}
27
28 You refer to an Index List via an opaque handle---in C, the integer typedef \kw{IDXL\_t}; in Fortran, a bare INTEGER.  
29
30
31 \prototype{FEM\_Comm\_shared}
32 \function{IDXL\_t FEM\_Comm\_shared(int mesh,int entity);}
33 \function{INTEGER function FEM\_Comm\_shared(mesh,entity)}
34   \args{INTEGER, INTENT(IN)  :: mesh,entity}
35
36 Return a read-only copy of the Index List of shared nodes.  The send and receive portions of this list are identical, because each shared node is both sent and received.  Shared nodes are most often used with the \kw{send/sum} communication pattern.
37
38 Must be called from driver.  \kw{mesh} must be a reading mesh. \kw{entity} must be \kw{FEM\_NODE}.  You may not call \kw{IDXL\_Destroy} on the returned list.
39
40
41 \prototype{FEM\_Comm\_ghost}
42 \function{IDXL\_t FEM\_Comm\_ghost(int mesh,int entity);}
43 \function{INTEGER function FEM\_Comm\_ghost(mesh,entity)}
44   \args{INTEGER, INTENT(IN)  :: mesh,entity}
45
46 Return a read-only copy of the Index List of ghost entities.  The send portion of this list contains real, interior entities, which are sent away; the receive portion of the list contains the ghost entites, which are received. Ghosts are most often used with the \kw{send/recv} communication pattern.
47
48 Elements to be sent out are listed starting at zero (one in Fortran); but ghost elements to be received are also listed starting at zero (one in Fortran).  If real and ghost elements are kept in separate arrays, this is usable as-is; but if ghosts and real elements are kept together, you will need to shift the ghost indices using \kw{IDXL\_Combine} or \kw{IDXL\_Shift}. 
49
50 This routine must be called from driver.  \kw{mesh} must be a reading mesh. \kw{entity} must not include \kw{FEM\_GHOST}--ghosts are already included.  You may not call \kw{IDXL\_Destroy} on the returned list.
51
52
53 \prototype{IDXL\_Create}
54 \function{IDXL\_t IDXL\_Create(void);}
55 \function{INTEGER function IDXL\_Create()}
56
57 Create a new, empty Index List. This list can then be filled up using \kw{IDXL\_Copy} or \kw{IDXL\_Combine}.
58
59 Must be called from driver.  You must eventually call \kw{IDXL\_Destroy} on the returned list.
60
61
62 \prototype{IDXL\_Combine}
63 \function{void IDXL\_Combine(IDXL\_t dest,IDXL\_t src,int startSend,int startRecv);}
64 \function{SUBROUTINE IDXL\_Combine(dest,src,startSend,startRecv)}
65   \args{INTEGER, INTENT(IN)  :: dest,src,startSend,startRecv}
66
67 Add the shifted contents of the src Index List to dest.  The send portion of src is shifted so the first index sent will be startSend; for a ghost index list this is the index of the first sent real entity. The receive portion of src is similarly shifted so the first index received will be startRecv; for a ghost index list this is the index of the first received ghost entity.  
68
69 This routine does not check for duplicates---if an index originally appears in dest and the also in the shifted src, it will be listed twice.
70
71
72 \subsubsection{Advanced Index List Calls}
73
74 \prototype{IDXL\_Destroy}
75 \function{void IDXL\_Destroy(IDXL\_t l);}
76 \function{SUBROUTINE IDXL\_Destroy(l)}
77   \args{INTEGER, INTENT(IN)  :: l}
78
79 Destroy this Index List, and free the list storage allocated by the framework.  Only call this routine with lists you created using \kw{IDXL\_Create}; not lists obtained directly from the FEM framework.
80
81 \prototype{IDXL\_Print}
82 \function{void IDXL\_Print(IDXL\_t l);}
83 \function{SUBROUTINE IDXL\_Print(l)}
84   \args{INTEGER, INTENT(IN)  :: l}
85
86 Print out the contents of this Index List.  This routine shows both the send and receive indices on the list, for each chunk we communicate with.
87
88
89 \prototype{IDXL\_Copy}
90 \function{void IDXL\_Copy(IDXL\_t dest,IDXL\_t src);}
91 \function{SUBROUTINE IDXL\_Print(dest,src)}
92   \args{INTEGER, INTENT(IN)  :: dest,src}
93
94 Copy the contents of the source Index List into the destination Index List, which should be empty.
95
96 \prototype{IDXL\_Shift}
97 \function{void IDXL\_Shift(IDXL\_t l,int startSend,int startRecv);}
98 \function{SUBROUTINE IDXL\_Shift(l,startSend,startRecv)}
99   \args{INTEGER, INTENT(IN)  :: l,startSend,startRecv}
100
101 Like \kw{IDXL\_Combine}, but only shifts the indices within a single list.
102
103
104 \prototype{IDXL\_Add\_entity}
105 \function{void IDXL\_Add\_entity(int newIdx,int nBetween,int *between);}
106 \function{SUBROUTINE IDXL\_Add\_node(newIdx,nBetween,between)}
107     \args{INTEGER, INTENT(IN) :: newIdx,nBetween}
108     \args{INTEGER, INTENT(IN) :: between(nBetween)}
109
110 This call adds a new entity, with local index \kw{newIdx}, to this Index List.  The new entity is sent or received by each chunk that sends or receives all the entites listed in the between array.  For example, when adding a new node along an edge, nBetween is 2 and between lists the endpoints of the edge; this way if the edge is shared with some chunk, the new node will be shared with that chunk.
111
112 This routine only affects the current chunk-- no other chunks are affected.  To ensure the communication lists match, \kw{IDXL\_Add\_entity} must be called on all the chunks that send or receive the entity, to create the local copies of the entity.
113
114 \kw{IDXL\_Add\_entity} adds the new entity to the end of the communication list, and so must be called in the same order on all the chunks that share the new entity.  For example, if two new nodes $x$ and $y$ are added between chunks $a$ and $b$, if chunk $a$ calls \kw{IDXL\_Add\_entity} with its local number for $x$ before it calls \kw{IDXL\_Add\_entity} with its local number for $y$, chunk $b$ must also add its copy of node $x$ before adding $y$.
115
116 % FIXME: implement, and document, IDXL\_Sort\_2d and IDXL\_Sort\_3d
117
118 %%%%%%%%%%%%%%%%%%% Layout %%%%%%%%%%%%%%%%%%%%
119 \subsection{Data Layout}
120 \label{sec:IDXLLayout}
121 IDXL is designed to send and receive data directly out of your arrays, with no intermediate copying.  This means IDXL needs a completely general method for specifying how you store your data in your arrays.  Since you probably don't change your storage layout at runtime, you can create a ``data layout'' once at the beginning of your program, then use it repeatedly for communication.
122
123 IDXL Layouts are normally used to describe arrays of data associated with nodes or elements.  The layout abstraction allows you to use IDXL routines to communicate any sort of data, stored in a variety of formats.
124
125 Like Index Lists, Layouts are referred to via an opaque handle---in a C program via the integer typedef IDXL\_Layout\_t, and in Fortran via a bare integer.
126
127 \subsubsection{Layout Routines}
128
129 In most programs, the data to be communicated is a dense array of data of one type.  In this case, there is only one layout routine you need to know:
130
131 \prototype{IDXL\_Layout\_create}
132 \function{IDXL\_Layout\_t IDXL\_Layout\_create(int type,int width);}
133 \function{INTEGER function IDXL\_Layout\_create(type,width)}
134     \args{INTEGER, INTENT(IN) :: type,width}
135
136 The simplest data layout to describe---a dense array of this IDXL datatype, indexed by entity number, with \kw{width} pieces of data per entity. Note that the number of entities is not stored with the layout--the number of entities to be communicated depends on the communication routine.
137
138 The IDXL datatypes are:
139 \begin{center}
140 \begin{tabular}{|l|l|l|}\hline
141 IDXL Datatype & C Datatypes & Fortran Datatypes \\\hline
142 \kw{IDXL\_BYTE} & unsigned char & INTEGER*1 \\
143                & char & LOGICAL*1 \\
144 \kw{IDXL\_INT} & int & INTEGER \\
145 \kw{IDXL\_REAL} & float & SINGLE PRECISION \\
146                 &  & REAL*4 \\
147 \kw{IDXL\_DOUBLE} & double & DOUBLE PRECISION \\
148                   &  & REAL*8 \\
149 \hline
150 \end{tabular}
151 \end{center}
152
153 For example, if you keep a dense array with 3 doubles of force per node, you'd call this routine as:
154
155 \begin{alltt}
156 // C++ version:
157      double *force=new double[3*n];
158      IDXL\_Layout\_t force\_layout=IDXL\_Layout\_create(IDXL\_DOUBLE,3);
159
160 ! F90 Version
161      double precision, allocatable :: force(:,:)
162      integer :: force\_layout
163      ALLOCATE(force(3,n)) ! (could equivalently use force(3*n) )
164      force\_layout=IDXL\_Layout\_create(IDXL\_DOUBLE,3)
165
166 \end{alltt}
167
168 This routine was once called \kw{FEM\_Create\_simple\_field}.
169
170
171 \subsubsection{Advanced Layout Routines}
172 \label{sec:IDXLLayoutoffset}
173
174 These advanced routines are only needed if you want to exchange data stored in an array of user-defined types.  Most programs only need \kw{IDXL\_Layout\_create}.
175
176 \prototype{IDXL\_Layout\_offset}
177 \function{IDXL\_Layout\_t IDXL\_Layout\_offset(int type, int width, int offsetBytes, int distanceBytes,int skewBytes);}
178 \function{INTEGER function IDXL\_Layout\_offset(type,width,offsetBytes,distanceBytes,skewBytes)}
179     \args{INTEGER, INTENT(IN) :: type,width,offsetBytes,distanceBytes,skewBytes}
180
181 The most general data layout--an array indexed by entity, containing \kw{width} pieces of data per entity.  This routine expands on \kw{IDXL\_Layout\_create} by adding support for user-defined types or other unusual data layouts.  You describe your layout by giving various in-memory byte offsets that describe the data is stored. Again, the number of entities is not stored with the layout--the number of entities to be communicated depends on the communication routine.
182
183 \begin{itemize}
184   \item \kw{offsetBytes} The number of bytes from the start of the array to the start of the data.
185   \item \kw{distanceBytes} The number of bytes taken by one entity.
186   \item \kw{skewBytes} The number of bytes between each piece of data.  Since this can almost always be determined from the size of the base data type, this parameter can be left as zero.
187 \end{itemize}
188
189 \begin{figure}[h]
190 \begin{center}
191 \includegraphics[width=5in]{fig/layout}
192 \end{center}
193 \caption{Describing a complex data layout.}
194 \label{fig:layout}
195 \end{figure}
196
197 For example, if your node data is all stored in a struct (in fortran, a named TYPE), offsetBytes gives the distance between the start of the struct and the force; and distanceBytes gives the size in bytes of the struct.  
198
199 In C, the offsetof and sizeof keywords are useful for finding these values.  In Fortran, we provide a special routine called \kw{foffsetof} that returns the distance, in bytes, between its two arguments.
200
201 \begin{alltt}
202 // C++ version:
203      typedef struct \{
204         double d[3], v[3], force[3], a[3];
205         double m;
206      \} node;
207      node *nodes=new node[n];
208      IDXL\_Layout\_t force\_layout=IDXL\_Layout\_offset(IDXL\_DOUBLE,3,
209               offsetof(node,force),sizeof(node),0);
210
211 ! F90 Version
212      TYPE node 
213         DOUBLE PRECISION :: d(3), v(3), force(3), a(3)
214         DOUBLE PRECISION :: m
215      END TYPE
216      integer :: force\_layout
217      ALLOCATE(nodes(n))
218      force\_layout=IDXL\_Layout\_create(IDXL\_DOUBLE,3,
219    &          foffsetof(nodes(1),nodes(1)\%force),
220    &          foffsetof(nodes(1),nodes(2)),0)
221 \end{alltt}
222
223
224 \prototype{IDXL\_Layout\_destroy}
225 \function{void IDXL\_Layout\_destroy(IDXL\_Layout\_t layout);}
226 \function{SUBROUTINE IDXL\_Layout\_destroy(layout)}
227   \args{INTEGER, INTENT(IN)  :: layout}
228
229 Destroy this Layout.  You only need call this routine if you repeatedly create layouts.
230
231 \prototype{IDXL\_Get\_layout\_type}
232 \function{int IDXL\_Get\_layout\_type(IDXL\_Layout\_t layout);}
233 \function{INTEGER function IDXL\_Get\_layout\_type(layout)}
234
235 Return the IDXL datatype for this layout.
236
237 \prototype{IDXL\_Get\_layout\_width}
238 \function{int IDXL\_Get\_layout\_width(IDXL\_Layout\_t layout);}
239 \function{INTEGER function IDXL\_Get\_layout\_width(layout)}
240
241 Return the layout width---the number of data items that are communicated
242 per entity.
243
244 \prototype{IDXL\_Get\_layout\_distance}
245 \function{int IDXL\_Get\_layout\_distance(IDXL\_Layout\_t layout);}
246 \function{INTEGER function IDXL\_Get\_layout\_distance(layout)}
247
248 Return the layout distance---the number of bytes between successive
249 entity's data items.
250
251
252
253 \subsubsection{Layout Compatability Routines}
254
255 Before IDXL was made a separate library, FEM included these routines,
256 which are still preserved for backward compatability.
257
258 \prototype{FEM\_Create\_simple\_field}
259 \function{IDXL\_Layout\_t FEM\_Create\_simple\_field(int type,int width);}
260 \function{INTEGER function FEM\_Create\_simple\_field(type,width)}
261   \args{INTEGER, INTENT(IN)  :: type,width}
262
263 This routine is completely interchangable to \kw{IDXL\_Layout\_create}.
264
265
266 \prototype{FEM\_Create\_field}
267 \function{int FEM\_Create\_field(int type,int width,int offset,int distance);}
268 \function{INTEGER function FEM\_Create\_field(type, width, offset, distance)}
269   \args{INTEGER, INTENT(IN)  :: type, width, offset, distance}
270
271 This routine is like a call to \kw{IDXL\_Layout\_offset} with the rarely
272 used \kw{skewBytes} set to zero.
273
274
275
276 %%%%%%%%%%%%%%%%%%% Communication %%%%%%%%%%%%%%%%%%%%
277 \subsection{IDXL Communication}
278 \label{sec:IDXLComm}
279 This section brings together all the pieces of IDXL: Index Lists are used to determine what to send and what to receive and Layouts are used to determine where to get and put the communicated data.
280
281
282 \subsubsection{Communication Routines}
283
284 \prototype{IDXL\_Comm\_sendsum}
285 \function{void IDXL\_Comm\_sendsum(IDXL\_Comm\_t comm,IDXL\_t indices,IDXL\_Layout\_t layout,void *data);}
286 \function{SUBROUTINE IDXL\_Comm\_sendsum(comm,indices,layout,data)}
287   \args{INTEGER, INTENT(IN)  :: comm,indices,layout}
288   \args{varies, INTENT(INOUT) :: data}
289
290 Sum these \kw{indices} of shared entites across all chunks that share them.
291 The user \kw{data} array is interpreted according to the given \kw{layout}.
292
293 If \kw{comm} is zero, this routine is blocking and finishes the communication immediately.
294 If \kw{comm} is not zero, this routine is non-blocking and equivalent to a call to 
295 \kw{IDXL\_Comm\_send} followed by a call to \kw{IDXL\_Comm\_sum}.
296
297 This routine is typically used to sum up partial values on shared nodes.
298 It is a more general version of the old FEM routine \kw{FEM\_Update\_field}.
299 For example, to sum up the shared-node values in a 3d \uw{force} vector indexed 
300 by node, you would use:
301
302 \begin{alltt}
303 // C++ version:
304      double *force=new double[3*nNodes];
305      IDXL\_Layout\_t force\_layout=IDXL\_Layout\_create(IDXL\_DOUBLE,3);
306      IDXL\_t shared\_indices=FEM_Comm_shared(mesh,FEM_NODE);
307      
308      ... in the time loop ...
309          IDXL_Comm_sendsum(0,shared_indices,force_layout,force);
310
311 ! F90 Version
312      double precision, allocatable :: force(:,:)
313      integer :: force\_layout, shared_indices
314      ALLOCATE(force(3,nNodes)) ! (could equivalently use force(3*nNodes) )
315      force\_layout=IDXL\_Layout\_create(IDXL\_DOUBLE,3)
316      shared_indices=FEM_Comm_shared(mesh,FEM_NODE)
317      
318      ... in the time loop ...
319          CALL IDXL_Comm_sendsum(0,shared_indices,force_layout,force)
320
321 \end{alltt}
322
323
324 \prototype{IDXL\_Comm\_sendrecv}
325 \function{void IDXL\_Comm\_sendrecv(IDXL\_Comm\_t comm,IDXL\_t indices,IDXL\_Layout\_t layout,void *data);}
326 \function{SUBROUTINE IDXL\_Comm\_sendrecv(comm,indices,layout,data)}
327   \args{INTEGER, INTENT(IN)  :: comm,indices,layout}
328   \args{varies, INTENT(INOUT) :: data}
329
330 Send these (typically real) send \kw{indices} and copy in these 
331 (typically ghost) receive \kw{indices}.
332 The user \kw{data} array is interpreted according to the given \kw{layout}.
333
334 If \kw{comm} is zero, this routine is blocking and finishes the communication immediately.
335 If \kw{comm} is not zero, this routine is non-blocking and equivalent to a call to 
336 \kw{IDXL\_Comm\_send} followed by a call to \kw{IDXL\_Comm\_sum}.
337
338 This routine is typically used to obtain the values of ghost entities.
339 It is a more general version of the old FEM routine \kw{FEM\_Update\_ghost\_field}.
340 For example, to obtain 7 solution values per ghost element, storing \uw{gElem}
341 ghosts in the array just after the \uw{nElem} regular elements, we could:
342
343 \begin{alltt}
344 // C++ version:
345      double *elem=new double[7*(nElem+gElem)];
346      IDXL\_Layout\_t elem\_layout=IDXL\_Layout\_create(IDXL\_DOUBLE,7);
347      IDXL\_t ghost\_original=FEM_Comm_ghost(mesh,FEM_ELEM+1);
348      IDXL\_t ghost\_shifted=IDXL_Create(); // ghosts start at nElem
349      IDXL_Combine(ghost_shifted,ghost_original,0,nElem);
350      
351      ... in the time loop ...
352          IDXL_Comm_sendrecv(0,ghost_shifted,elem_layout,elem);
353
354 ! F90 Version
355      double precision, allocatable :: elem(:,:)
356      integer :: elem\_layout, ghost_original,ghost_shifted
357      ALLOCATE(elem(7,nElem+gElem))
358      elem\_layout=IDXL\_Layout\_create(IDXL\_DOUBLE,7)
359      ghost\_original=FEM_Comm_ghost(mesh,FEM_ELEM+1)
360      ghost\_shifted=IDXL_Create() ! ghosts start at nElem+1
361      CALL IDXL_Combine(ghost_shifted,ghost_original,1,nElem+1)
362      
363      ... in the time loop ...
364          CALL IDXL_Comm_sendrecv(0,ghost_shifted,elem_layout,elem)
365
366 \end{alltt}
367
368
369 \subsubsection{Advanced Communication Routines}
370
371 \prototype{IDXL\_Comm\_begin}
372 \function{IDXL\_Comm\_t IDXL\_Comm\_begin(int tag,int context);}
373 \function{INTEGER function IDXL\_Comm\_begin(tag,context)}
374   \args{INTEGER, INTENT(IN)  :: tag,context}
375
376 Start a non-blocking communication operation with this (user-defined) tag and communication context (0, or an AMPI communicator).  
377
378 Every call to this routine must eventually be matched by a call to \kw{IDXL\_Comm\_wait}.  Warning: for now, tag and context are ignored, and there can be only one outstanding communication operation.
379
380
381 \prototype{IDXL\_Comm\_send}
382 \function{void IDXL\_Comm\_send(IDXL\_Comm\_t comm,IDXL\_t indices,IDXL\_Layout\_t layout,const void *data);}
383 \function{SUBROUTINE IDXL\_Comm\_send(comm,indices,layout,data)}
384   \args{INTEGER, INTENT(IN)  :: comm,indices,layout}
385   \args{varies, INTENT(IN) :: data}
386
387 When \kw{comm} is flushed, send these send \kw{indices}, with
388 this \kw{layout}, from this \kw{data} array.
389
390 This routine is always non-blocking; as the \kw{data} array passed in
391 will not be copied out until the call to \kw{IDXL\_Comm\_flush}.
392
393
394 \prototype{IDXL\_Comm\_recv}
395 \function{void IDXL\_Comm\_recv(IDXL\_Comm\_t comm,IDXL\_t indices,IDXL\_Layout\_t layout,void *data);}
396 \function{SUBROUTINE IDXL\_Comm\_recv(comm,indices,layout,data)}
397   \args{INTEGER, INTENT(IN)  :: comm,indices,layout}
398   \args{varies, INTENT(OUT) :: data}
399
400 When \kw{comm} is finished, copy in these receive \kw{indices}, with
401 this \kw{layout}, into this \kw{data} array.
402
403 This routine is always non-blocking; as the \kw{data} array passed in
404 will not be copied into until the call to \kw{IDXL\_Comm\_wait}.
405
406
407 \prototype{IDXL\_Comm\_sum}
408 \function{void IDXL\_Comm\_sum(IDXL\_Comm\_t comm,IDXL\_t indices,IDXL\_Layout\_t layout,void *data);}
409 \function{SUBROUTINE IDXL\_Comm\_sum(comm,indices,layout,data)}
410   \args{INTEGER, INTENT(IN)  :: comm,indices,layout}
411   \args{varies, INTENT(INOUT) :: data}
412
413 When \kw{comm} is finished, add in the values for these receive \kw{indices}, 
414 with this \kw{layout}, into this \kw{data} array.
415
416 This routine is always non-blocking; as the \kw{data} array passed in
417 will not be added to until the call to \kw{IDXL\_Comm\_wait}.
418
419
420 \prototype{IDXL\_Comm\_flush}
421 \function{void IDXL\_Comm\_flush(IDXL\_Comm\_t comm);}
422 \function{SUBROUTINE IDXL\_Comm\_flush(comm)}
423   \args{INTEGER, INTENT(IN)  :: comm}
424
425 Send all outgoing data listed on this \kw{comm}.  This routine exists because there may be many calls to \kw{IDXL\_Comm\_send}, and sending one large message is more efficient than sending many small messages.
426
427 This routine is typically non-blocking, and may only be issued at most once per \kw{IDXL\_Comm\_begin}.
428
429
430 \prototype{IDXL\_Comm\_wait}
431 \function{void IDXL\_Comm\_wait(IDXL\_Comm\_t comm);}
432 \function{SUBROUTINE IDXL\_Comm\_wait(comm)}
433   \args{INTEGER, INTENT(IN)  :: comm}
434
435 Finish this communication operation. This call must be issued exactly once per \kw{IDXL\_Comm\_begin}.  This call inclues \kw{IDXL\_Comm\_flush} if it has not yet been called.
436
437 This routine always blocks until all incoming data is received, and is the last call that can be made on this \kw{comm}.
438