Actual source code: vscat.c

  1: #include <petsc/private/sfimpl.h>
  2: #include <../src/vec/is/sf/impls/basic/sfbasic.h>
  3: #include <../src/vec/is/sf/impls/basic/sfpack.h>
  4: #include <petsc/private/vecimpl.h>

  6: PETSC_SINGLE_LIBRARY_INTERN PetscErrorCode PetscGatherNumberOfMessages_Private(MPI_Comm, const PetscMPIInt[], const PetscInt[], PetscMPIInt *);
  7: PETSC_SINGLE_LIBRARY_INTERN PetscErrorCode PetscGatherMessageLengths_Private(MPI_Comm, PetscMPIInt, PetscMPIInt, const PetscInt[], PetscMPIInt **, PetscInt **);

  9: typedef enum {
 10:   IS_INVALID,
 11:   IS_GENERAL,
 12:   IS_BLOCK,
 13:   IS_STRIDE
 14: } ISTypeID;

 16: static inline PetscErrorCode ISGetTypeID_Private(IS is, ISTypeID *id)
 17: {
 18:   PetscBool same;

 20:   PetscFunctionBegin;
 21:   *id = IS_INVALID;
 22:   PetscCall(PetscObjectTypeCompare((PetscObject)is, ISGENERAL, &same));
 23:   if (same) {
 24:     *id = IS_GENERAL;
 25:     goto functionend;
 26:   }
 27:   PetscCall(PetscObjectTypeCompare((PetscObject)is, ISBLOCK, &same));
 28:   if (same) {
 29:     *id = IS_BLOCK;
 30:     goto functionend;
 31:   }
 32:   PetscCall(PetscObjectTypeCompare((PetscObject)is, ISSTRIDE, &same));
 33:   if (same) {
 34:     *id = IS_STRIDE;
 35:     goto functionend;
 36:   }
 37: functionend:
 38:   PetscFunctionReturn(PETSC_SUCCESS);
 39: }

 41: /* This is a temporary workaround to guarantee the correctness of the execution.
 42:    It must be removed once the Kokkos execution space supports dynamic creation out of every current context */
 43: PetscErrorCode VecScatterSynchronizeKokkos_Private(VecScatter sf, Vec x, Vec y, PetscBool before)
 44: {
 45: #if PetscDefined(HAVE_KOKKOS)
 46:   PetscBool xkokkos, ykokkos;

 48:   PetscFunctionBegin;
 49:   PetscCall(PetscObjectTypeCompareAny((PetscObject)x, &xkokkos, VECSEQKOKKOS, VECMPIKOKKOS, ""));
 50:   PetscCall(PetscObjectTypeCompareAny((PetscObject)y, &ykokkos, VECSEQKOKKOS, VECMPIKOKKOS, ""));
 51:   if (xkokkos || ykokkos) PetscCall(PetscSFSynchronizeKokkos_Private(sf, before));
 52: #else
 53:   PetscFunctionBegin;
 54:   (void)sf;
 55:   (void)x;
 56:   (void)y;
 57:   (void)before;
 58: #endif
 59:   PetscFunctionReturn(PETSC_SUCCESS);
 60: }

 62: static PetscErrorCode VecScatterBegin_Internal(VecScatter sf, Vec x, Vec y, InsertMode addv, ScatterMode mode)
 63: {
 64:   PetscSF      wsf = NULL; /* either sf or its local part */
 65:   MPI_Op       mop = MPI_OP_NULL;
 66:   PetscMPIInt  size;
 67:   PetscMemType xmtype = PETSC_MEMTYPE_HOST, ymtype = PETSC_MEMTYPE_HOST;

 69:   PetscFunctionBegin;
 70:   if (x != y) PetscCall(VecLockReadPush(x));
 71:   PetscCall(VecGetArrayReadAndMemType(x, &sf->vscat.xdata, &xmtype));
 72:   PetscCall(VecGetArrayAndMemType(y, &sf->vscat.ydata, &ymtype));
 73:   PetscCall(VecLockWriteSet(y, PETSC_TRUE));

 75:   /* SCATTER_FORWARD_LOCAL indicates ignoring inter-process communication */
 76:   PetscCallMPI(MPI_Comm_size(PetscObjectComm((PetscObject)sf), &size));
 77:   if ((mode & SCATTER_FORWARD_LOCAL) && size > 1) { /* Lazy creation of sf->vscat.lsf since SCATTER_FORWARD_LOCAL is uncommon */
 78:     if (!sf->vscat.lsf) PetscCall(PetscSFCreateLocalSF_Private(sf, &sf->vscat.lsf));
 79:     wsf = sf->vscat.lsf;
 80:   } else {
 81:     wsf = sf;
 82:   }

 84:   /* Note xdata/ydata is always recorded on sf (not lsf) above */
 85:   if (addv == INSERT_VALUES) mop = MPI_REPLACE;
 86:   else if (addv == ADD_VALUES) mop = MPIU_SUM; /* PETSc defines its own MPI datatype and SUM operation for __float128 etc. */
 87:   else if (addv == MAX_VALUES) mop = MPIU_MAX;
 88:   else if (addv == MIN_VALUES) mop = MPIU_MIN;
 89:   else SETERRQ(PetscObjectComm((PetscObject)sf), PETSC_ERR_SUP, "Unsupported InsertMode %d in VecScatterBegin/End", addv);

 91:   PetscCall(VecScatterSynchronizeKokkos_Private(wsf, x, y, PETSC_TRUE));
 92:   if (mode & SCATTER_REVERSE) { /* REVERSE indicates leaves to root scatter. Note that x and y are swapped in input */
 93:     PetscCall(PetscSFReduceWithMemTypeBegin(wsf, sf->vscat.unit, xmtype, sf->vscat.xdata, ymtype, sf->vscat.ydata, mop));
 94:   } else { /* FORWARD indicates x to y scatter, where x is root and y is leaf */
 95:     PetscCall(PetscSFBcastWithMemTypeBegin(wsf, sf->vscat.unit, xmtype, sf->vscat.xdata, ymtype, sf->vscat.ydata, mop));
 96:   }
 97:   PetscFunctionReturn(PETSC_SUCCESS);
 98: }

100: static PetscErrorCode VecScatterEnd_Internal(VecScatter sf, Vec x, Vec y, InsertMode addv, ScatterMode mode)
101: {
102:   PetscSF     wsf = NULL;
103:   MPI_Op      mop = MPI_OP_NULL;
104:   PetscMPIInt size;

106:   PetscFunctionBegin;
107:   /* SCATTER_FORWARD_LOCAL indicates ignoring inter-process communication */
108:   PetscCallMPI(MPI_Comm_size(PetscObjectComm((PetscObject)sf), &size));
109:   wsf = ((mode & SCATTER_FORWARD_LOCAL) && size > 1) ? sf->vscat.lsf : sf;

111:   if (addv == INSERT_VALUES) mop = MPI_REPLACE;
112:   else if (addv == ADD_VALUES) mop = MPIU_SUM;
113:   else if (addv == MAX_VALUES) mop = MPIU_MAX;
114:   else if (addv == MIN_VALUES) mop = MPIU_MIN;
115:   else SETERRQ(PetscObjectComm((PetscObject)sf), PETSC_ERR_SUP, "Unsupported InsertMode %d in VecScatterBegin/End", addv);

117:   if (mode & SCATTER_REVERSE) { /* reverse scatter sends leaves to roots. Note that x and y are swapped in input */
118:     PetscCall(PetscSFReduceEnd(wsf, sf->vscat.unit, sf->vscat.xdata, sf->vscat.ydata, mop));
119:   } else { /* forward scatter sends roots to leaves, i.e., x to y */
120:     PetscCall(PetscSFBcastEnd(wsf, sf->vscat.unit, sf->vscat.xdata, sf->vscat.ydata, mop));
121:   }

123:   PetscCall(VecScatterSynchronizeKokkos_Private(wsf, x, y, PETSC_FALSE));
124:   PetscCall(VecRestoreArrayReadAndMemType(x, &sf->vscat.xdata));
125:   if (x != y) PetscCall(VecLockReadPop(x));
126:   PetscCall(VecRestoreArrayAndMemType(y, &sf->vscat.ydata));
127:   PetscCall(VecLockWriteSet(y, PETSC_FALSE));
128:   PetscFunctionReturn(PETSC_SUCCESS);
129: }

131: /* VecScatterRemap provides a light way to slightly modify a VecScatter. Suppose the input sf scatters
132:    x[i] to y[j], tomap gives a plan to change vscat to scatter x[tomap[i]] to y[j]. Note that in SF,
133:    x is roots. That means we need to change incoming stuffs such as bas->irootloc[].
134:  */
135: static PetscErrorCode VecScatterRemap_Internal(VecScatter sf, const PetscInt *tomap, const PetscInt *frommap)
136: {
137:   PetscInt       i, bs = sf->vscat.bs;
138:   PetscMPIInt    size;
139:   PetscBool      ident = PETSC_TRUE, isbasic, isneighbor;
140:   PetscSFType    type;
141:   PetscSF_Basic *bas = NULL;

143:   PetscFunctionBegin;
144:   /* check if it is an identity map. If it is, do nothing */
145:   if (tomap) {
146:     for (i = 0; i < sf->nroots * bs; i++) {
147:       if (i != tomap[i]) {
148:         ident = PETSC_FALSE;
149:         break;
150:       }
151:     }
152:     if (ident) PetscFunctionReturn(PETSC_SUCCESS);
153:   }
154:   PetscCheck(!frommap, PETSC_COMM_SELF, PETSC_ERR_SUP, "Unable to remap the FROM in scatters yet");
155:   if (!tomap) PetscFunctionReturn(PETSC_SUCCESS);

157:   PetscCallMPI(MPI_Comm_size(PetscObjectComm((PetscObject)sf), &size));

159:   /* Since the indices changed, we must also update the local SF. But we do not do it since
160:      lsf is rarely used. We just destroy lsf and rebuild it on demand from updated sf.
161:   */
162:   PetscCall(PetscSFDestroy(&sf->vscat.lsf));

164:   PetscCall(PetscSFGetType(sf, &type));
165:   PetscCall(PetscObjectTypeCompare((PetscObject)sf, PETSCSFBASIC, &isbasic));
166:   PetscCall(PetscObjectTypeCompare((PetscObject)sf, PETSCSFNEIGHBOR, &isneighbor));
167:   PetscCheck(isbasic || isneighbor, PetscObjectComm((PetscObject)sf), PETSC_ERR_SUP, "VecScatterRemap on SF type %s is not supported", type);

169:   PetscCall(PetscSFSetUp(sf)); /* to build sf->irootloc if SetUp is not yet called */

171:   /* Root indices are going to be remapped. This is tricky for SF. Root indices are used in sf->rremote,
172:     sf->remote and bas->irootloc. The latter one is cheap to remap, but the former two are not.
173:     To remap them, we have to do a bcast from roots to leaves, to let leaves know their updated roots.
174:     Since VecScatterRemap is supposed to be a cheap routine to adapt a vecscatter by only changing where
175:     x[] data is taken, we do not remap sf->rremote, sf->remote. The consequence is that operations
176:     accessing them (such as PetscSFCompose) may get stale info. Considering VecScatter does not need
177:     that complicated SF operations, we do not remap sf->rremote, sf->remote, instead we destroy them
178:     so that code accessing them (if any) will crash (instead of get silent errors). Note that BcastAndOp/Reduce,
179:     which are used by VecScatter and only rely on bas->irootloc, are updated and correct.
180:   */
181:   sf->remote = NULL;
182:   PetscCall(PetscFree(sf->remote_alloc));
183:   /* Not easy to free sf->rremote since it was allocated with PetscMalloc4(), so just give it crazy values */
184:   for (i = 0; i < sf->roffset[sf->nranks]; i++) sf->rremote[i] = PETSC_INT_MIN;

186:   /* Indices in tomap[] are for each individual vector entry. But indices in sf are for each
187:      block in the vector. So before the remapping, we have to expand indices in sf by bs, and
188:      after the remapping, we have to shrink them back.
189:    */
190:   bas = (PetscSF_Basic *)sf->data;
191:   for (i = 0; i < bas->ioffset[bas->niranks]; i++) bas->irootloc[i] = tomap[bas->irootloc[i] * bs] / bs;
192: #if PetscDefined(HAVE_DEVICE)
193:   /* Free the irootloc copy on device. We allocate a new copy and get the updated value on demand. See PetscSFLinkGetRootPackOptAndIndices() */
194:   for (i = 0; i < 2; i++) PetscCall(PetscSFFree(sf, PETSC_MEMTYPE_DEVICE, bas->irootloc_d[i]));
195: #endif
196:   /* Destroy and then rebuild root packing optimizations since indices are changed */
197:   PetscCall(PetscSFResetPackFields(sf));
198:   PetscCall(PetscSFSetUpPackFields(sf));
199:   PetscFunctionReturn(PETSC_SUCCESS);
200: }

202: /*
203:   Given a parallel VecScatter context, return number of procs and vector entries involved in remote (i.e., off-process) communication

205:   Input Parameters:
206: + sf   - the context (must be a parallel vecscatter)
207: - send  - true to select the send info (i.e., todata), otherwise to select the recv info (i.e., fromdata)

209:   Output parameters:
210: + num_procs   - number of remote processors
211: - num_entries - number of vector entries to send or recv

213:   Notes:
214:   Sometimes PETSc internally needs to use the matrix-vector-multiply vecscatter context for other purposes. The client code
215:   usually only uses MPI_Send/Recv. This group of subroutines provides info needed for such uses.

217: .seealso: [](sec_scatter), `VecScatterGetRemote_Private()`, `VecScatterGetRemoteOrdered_Private()`
218:  */
219: PetscErrorCode VecScatterGetRemoteCount_Private(VecScatter sf, PetscBool send, PetscInt *num_procs, PetscInt *num_entries)
220: {
221:   PetscMPIInt        nranks, remote_start;
222:   PetscMPIInt        rank;
223:   const PetscInt    *offset;
224:   const PetscMPIInt *ranks;

226:   PetscFunctionBegin;
227:   PetscCall(PetscSFSetUp(sf));
228:   PetscCallMPI(MPI_Comm_rank(PetscObjectComm((PetscObject)sf), &rank));

230:   /* This routine is mainly used for MatMult's Mvctx. In Mvctx, we scatter an MPI vector x to a sequential vector lvec.
231:      Remember x is roots and lvec is leaves. 'send' means roots to leaves communication. If 'send' is true, we need to
232:      get info about which ranks this processor needs to send to. In other words, we need to call PetscSFGetLeafRanks().
233:      If send is false, we do the opposite, calling PetscSFGetRootRanks().
234:   */
235:   if (send) PetscCall(PetscSFGetLeafRanks(sf, &nranks, &ranks, &offset, NULL));
236:   else PetscCall(PetscSFGetRootRanks(sf, &nranks, &ranks, &offset, NULL, NULL));
237:   if (nranks) {
238:     remote_start = (rank == ranks[0]) ? 1 : 0;
239:     if (num_procs) *num_procs = nranks - remote_start;
240:     if (num_entries) *num_entries = offset[nranks] - offset[remote_start];
241:   } else {
242:     if (num_procs) *num_procs = 0;
243:     if (num_entries) *num_entries = 0;
244:   }
245:   PetscFunctionReturn(PETSC_SUCCESS);
246: }

248: /* Given a parallel VecScatter context, return a plan that represents the remote communication.
249:    Any output parameter can be NULL.

251:   Input Parameters:
252: + sf   - the context
253: - send  - true to select the send info (i.e., todata), otherwise to select the recv info (i.e., fromdata)

255:   Output parameters:
256: + n        - number of remote processors
257: . starts   - starting point in indices for each proc. ATTENTION: starts[0] is not necessarily zero.
258:              Therefore, expressions like starts[i+1]-starts[i] and indices[starts[i]+j] work as
259:              expected for a CSR structure but buf[starts[i]+j] may be out of range if buf was allocated
260:              with length starts[n]-starts[0]. One should use buf[starts[i]-starts[0]+j] instead.
261: . indices  - indices of entries to send/recv
262: . procs    - ranks of remote processors
263: - bs       - block size

265: .seealso: `VecScatterRestoreRemote_Private()`, `VecScatterGetRemoteOrdered_Private()`
266:  */
267: PetscErrorCode VecScatterGetRemote_Private(VecScatter sf, PetscBool send, PetscMPIInt *n, const PetscInt **starts, const PetscInt **indices, const PetscMPIInt **procs, PetscInt *bs)
268: {
269:   PetscMPIInt        nranks, remote_start;
270:   PetscMPIInt        rank;
271:   const PetscInt    *offset, *location;
272:   const PetscMPIInt *ranks;

274:   PetscFunctionBegin;
275:   PetscCall(PetscSFSetUp(sf));
276:   PetscCallMPI(MPI_Comm_rank(PetscObjectComm((PetscObject)sf), &rank));

278:   if (send) PetscCall(PetscSFGetLeafRanks(sf, &nranks, &ranks, &offset, &location));
279:   else PetscCall(PetscSFGetRootRanks(sf, &nranks, &ranks, &offset, &location, NULL));

281:   if (nranks) {
282:     remote_start = (rank == ranks[0]) ? 1 : 0;
283:     if (n) *n = nranks - remote_start;
284:     if (starts) *starts = &offset[remote_start];
285:     if (indices) *indices = location; /* not &location[offset[remote_start]]. Starts[0] may point to the middle of indices[] */
286:     if (procs) *procs = &ranks[remote_start];
287:   } else {
288:     if (n) *n = 0;
289:     if (starts) *starts = NULL;
290:     if (indices) *indices = NULL;
291:     if (procs) *procs = NULL;
292:   }

294:   if (bs) *bs = 1;
295:   PetscFunctionReturn(PETSC_SUCCESS);
296: }

298: /* Given a parallel VecScatter context, return a plan that represents the remote communication. Ranks of remote
299:    processors returned in procs must be sorted in ascending order. Any output parameter can be NULL.

301:   Input Parameters:
302: + sf   - the context
303: - send  - true to select the send info (i.e., todata), otherwise to select the recv info (i.e., fromdata)

305:   Output parameters:
306: + n        - number of remote processors
307: . starts   - starting point in indices for each proc. ATTENTION: starts[0] is not necessarily zero.
308:              Therefore, expressions like starts[i+1]-starts[i] and indices[starts[i]+j] work as
309:              expected for a CSR structure but buf[starts[i]+j] may be out of range if buf was allocated
310:              with length starts[n]-starts[0]. One should use buf[starts[i]-starts[0]+j] instead.
311: . indices  - indices of entries to send/recv
312: . procs    - ranks of remote processors
313: - bs       - block size

315:   Notes:
316:   Output parameters like starts, indices must also be adapted according to the sorted ranks.

318: .seealso: `VecScatterRestoreRemoteOrdered_Private()`, `VecScatterGetRemote_Private()`
319:  */
320: PetscErrorCode VecScatterGetRemoteOrdered_Private(VecScatter sf, PetscBool send, PetscMPIInt *n, const PetscInt **starts, const PetscInt **indices, const PetscMPIInt **procs, PetscInt *bs)
321: {
322:   PetscFunctionBegin;
323:   PetscCall(VecScatterGetRemote_Private(sf, send, n, starts, indices, procs, bs));
324:   if (PetscUnlikelyDebug(n && procs)) {
325:     PetscMPIInt i;
326:     /* from back to front to also handle cases *n=0 */
327:     for (i = *n - 1; i > 0; i--) PetscCheck((*procs)[i - 1] <= (*procs)[i], PETSC_COMM_SELF, PETSC_ERR_PLIB, "procs[] are not ordered");
328:   }
329:   PetscFunctionReturn(PETSC_SUCCESS);
330: }

332: /* Given a parallel VecScatter context, restore the plan returned by VecScatterGetRemote_Private. This gives a chance for
333:    an implementation to free memory allocated in the VecScatterGetRemote_Private call.

335:   Input Parameters:
336: + sf   - the context
337: - send  - true to select the send info (i.e., todata), otherwise to select the recv info (i.e., fromdata)

339:   Output parameters:
340: + n        - number of remote processors
341: . starts   - starting point in indices for each proc
342: . indices  - indices of entries to send/recv
343: . procs    - ranks of remote processors
344: - bs       - block size

346: .seealso: `VecScatterGetRemote_Private()`
347:  */
348: PetscErrorCode VecScatterRestoreRemote_Private(VecScatter sf, PetscBool send, PetscMPIInt *n, const PetscInt **starts, const PetscInt **indices, const PetscMPIInt **procs, PetscInt *bs)
349: {
350:   PetscFunctionBegin;
351:   if (starts) *starts = NULL;
352:   if (indices) *indices = NULL;
353:   if (procs) *procs = NULL;
354:   PetscFunctionReturn(PETSC_SUCCESS);
355: }

357: /* Given a parallel VecScatter context, restore the plan returned by VecScatterGetRemoteOrdered_Private. This gives a chance for
358:    an implementation to free memory allocated in the VecScatterGetRemoteOrdered_Private call.

360:   Input Parameters:
361: + sf   - the context
362: - send  - true to select the send info (i.e., todata), otherwise to select the recv info (i.e., fromdata)

364:   Output parameters:
365: + n        - number of remote processors
366: . starts   - starting point in indices for each proc
367: . indices  - indices of entries to send/recv
368: . procs    - ranks of remote processors
369: - bs       - block size

371: .seealso: `VecScatterGetRemoteOrdered_Private()`
372:  */
373: PetscErrorCode VecScatterRestoreRemoteOrdered_Private(VecScatter sf, PetscBool send, PetscMPIInt *n, const PetscInt **starts, const PetscInt **indices, const PetscMPIInt **procs, PetscInt *bs)
374: {
375:   PetscFunctionBegin;
376:   PetscCall(VecScatterRestoreRemote_Private(sf, send, n, starts, indices, procs, bs));
377:   PetscFunctionReturn(PETSC_SUCCESS);
378: }

380: /*@
381:   VecScatterSetUp - Sets up the `VecScatter` to be able to actually scatter information between vectors

383:   Collective

385:   Input Parameter:
386: . sf - the scatter context

388:   Level: intermediate

390: .seealso: [](sec_scatter), `VecScatter`, `VecScatterCreate()`, `VecScatterCopy()`
391: @*/
392: PetscErrorCode VecScatterSetUp(VecScatter sf)
393: {
394:   PetscFunctionBegin;
395:   PetscCall(PetscSFSetUp(sf));
396:   PetscFunctionReturn(PETSC_SUCCESS);
397: }

399: /*@
400:   VecScatterSetType - Builds a vector scatter, for a particular vector scatter implementation.

402:   Collective

404:   Input Parameters:
405: + sf   - The `VecScatter` object
406: - type - The name of the vector scatter type

408:   Options Database Key:
409: . -sf_type type - Sets the `VecScatterType`

411:   Level: intermediate

413:   Note:
414:   Use `VecScatterDuplicate()` to form additional vectors scatter of the same type as an existing vector scatter.

416: .seealso: [](sec_scatter), `VecScatter`, `VecScatterType`, `VecScatterGetType()`, `VecScatterCreate()`
417: @*/
418: PetscErrorCode VecScatterSetType(VecScatter sf, VecScatterType type)
419: {
420:   PetscFunctionBegin;
421:   PetscCall(PetscSFSetType(sf, type));
422:   PetscFunctionReturn(PETSC_SUCCESS);
423: }

425: /*@
426:   VecScatterGetType - Gets the vector scatter type name (as a string) from the `VecScatter`.

428:   Not Collective

430:   Input Parameter:
431: . sf - The vector scatter

433:   Output Parameter:
434: . type - The vector scatter type name

436:   Level: intermediate

438: .seealso: [](sec_scatter), `VecScatter`, `VecScatterType`, `VecScatterSetType()`, `VecScatterCreate()`
439: @*/
440: PetscErrorCode VecScatterGetType(VecScatter sf, VecScatterType *type)
441: {
442:   PetscFunctionBegin;
443:   PetscCall(PetscSFGetType(sf, type));
444:   PetscFunctionReturn(PETSC_SUCCESS);
445: }

447: /*@
448:   VecScatterRegister -  Adds a new vector scatter component implementation

450:   Not Collective

452:   Input Parameters:
453: + sname    - The name of a new user-defined creation routine
454: - function - The creation routine

456:   Level: advanced

458: .seealso: [](sec_scatter), `VecScatter`, `VecScatterType`, `VecRegister()`
459: @*/
460: PetscErrorCode VecScatterRegister(const char sname[], PetscErrorCode (*function)(VecScatter))
461: {
462:   PetscFunctionBegin;
463:   PetscCall(PetscSFRegister(sname, function));
464:   PetscFunctionReturn(PETSC_SUCCESS);
465: }

467: /*@
468:   VecScatterGetMerged - Returns true if the scatter is completed in the `VecScatterBegin()`
469:   and the `VecScatterEnd()` does nothing

471:   Not Collective

473:   Input Parameter:
474: . sf - scatter context created with `VecScatterCreate()`

476:   Output Parameter:
477: . flg - `PETSC_TRUE` if the `VecScatterBegin()`/`VecScatterEnd()` are all done during the `VecScatterBegin()`

479:   Level: developer

481: .seealso: [](sec_scatter), `VecScatter`, `VecScatterCreate()`, `VecScatterEnd()`, `VecScatterBegin()`
482: @*/
483: PetscErrorCode VecScatterGetMerged(VecScatter sf, PetscBool *flg)
484: {
485:   PetscFunctionBegin;
487:   if (flg) *flg = sf->vscat.beginandendtogether;
488:   PetscFunctionReturn(PETSC_SUCCESS);
489: }
490: /*@
491:   VecScatterDestroy - Destroys a scatter context created by `VecScatterCreate()`

493:   Collective

495:   Input Parameter:
496: . sf - the scatter context

498:   Level: intermediate

500: .seealso: [](sec_scatter), `VecScatter`, `VecScatterCreate()`, `VecScatterCopy()`
501: @*/
502: PetscErrorCode VecScatterDestroy(VecScatter *sf)
503: {
504:   PetscFunctionBegin;
505:   PetscCall(PetscSFDestroy(sf));
506:   PetscFunctionReturn(PETSC_SUCCESS);
507: }

509: /*@
510:   VecScatterCopy - Makes a copy of a scatter context.

512:   Collective

514:   Input Parameter:
515: . sf - the scatter context

517:   Output Parameter:
518: . newsf - the context copy

520:   Level: advanced

522: .seealso: [](sec_scatter), `VecScatter`, `VecScatterType`, `VecScatterCreate()`, `VecScatterDestroy()`
523: @*/
524: PetscErrorCode VecScatterCopy(VecScatter sf, VecScatter *newsf)
525: {
526:   PetscFunctionBegin;
527:   PetscAssertPointer(newsf, 2);
528:   PetscCall(PetscSFDuplicate(sf, PETSCSF_DUPLICATE_GRAPH, newsf));
529:   PetscCall(PetscSFSetUp(*newsf));
530:   PetscFunctionReturn(PETSC_SUCCESS);
531: }

533: /*@
534:   VecScatterViewFromOptions - View a `VecScatter` object based on values in the options database

536:   Collective

538:   Input Parameters:
539: + sf   - the scatter context
540: . obj  - optional object that provides the prefix for the option names, pass `NULL` to use the options prefix of `sf`
541: - name - command line option

543:   Options Database Key:
544: . -name viewer_specification - See `PetscOptionsCreateViewer()` for the values of `viewer_specification`

546:   Level: intermediate

548:   Note:
549:   This checks the options database, creates the viewer on-the-fly, uses it and then destroys it. Hence it should not be called in heavily used routines,
550:   rather `PetscOptionsCreateViewer()` should be used to construct the viewer once which can then be utilized in the heavily used routine.

552: .seealso: [](sec_scatter), `VecScatter`, `VecScatterView()`, `PetscObjectViewFromOptions()`, `VecScatterCreate()`, `PetscOptionsCreateViewer()`
553: @*/
554: PetscErrorCode VecScatterViewFromOptions(VecScatter sf, PetscObject obj, const char name[])
555: {
556:   PetscFunctionBegin;
558:   PetscCall(PetscObjectViewFromOptions((PetscObject)sf, obj, name));
559:   PetscFunctionReturn(PETSC_SUCCESS);
560: }

562: /*@
563:   VecScatterView - Views a vector scatter context.

565:   Collective

567:   Input Parameters:
568: + sf     - the scatter context
569: - viewer - the viewer for displaying the context

571:   Level: intermediate

573: .seealso: [](sec_scatter), `VecScatter`, `PetscViewer`, `VecScatterViewFromOptions()`, `PetscObjectViewFromOptions()`, `VecScatterCreate()`
574: @*/
575: PetscErrorCode VecScatterView(VecScatter sf, PetscViewer viewer)
576: {
577:   PetscFunctionBegin;
578:   PetscCall(PetscSFView(sf, viewer));
579:   PetscFunctionReturn(PETSC_SUCCESS);
580: }

582: /*@
583:   VecScatterRemap - Remaps the "from" and "to" indices in a
584:   vector scatter context.

586:   Collective

588:   Input Parameters:
589: + sf      - vector scatter context
590: . tomap   - remapping plan for "to" indices (may be `NULL`).
591: - frommap - remapping plan for "from" indices (may be `NULL`)

593:   Level: developer

595:   Notes:
596:   In the parallel case the todata contains indices from where the data is taken
597:   (and then sent to others)! The fromdata contains indices from where the received
598:   data is finally put locally.

600:   In the sequential case the todata contains indices from where the data is put
601:   and the fromdata contains indices from where the data is taken from.
602:   This is backwards from the parallel case!

604: .seealso: [](sec_scatter), `VecScatter`, `VecScatterCreate()`
605: @*/
606: PetscErrorCode VecScatterRemap(VecScatter sf, PetscInt tomap[], PetscInt frommap[])
607: {
608:   PetscFunctionBegin;
609:   if (tomap) PetscAssertPointer(tomap, 2);
610:   if (frommap) PetscAssertPointer(frommap, 3);
611:   PetscCall(VecScatterRemap_Internal(sf, tomap, frommap));
612:   PetscCheck(!frommap, PETSC_COMM_SELF, PETSC_ERR_SUP, "Unable to remap the FROM in scatters yet");
613:   /* Mark then vector lengths as unknown because we do not know the lengths of the remapped vectors */
614:   sf->vscat.from_n = -1;
615:   sf->vscat.to_n   = -1;
616:   PetscFunctionReturn(PETSC_SUCCESS);
617: }

619: /*@
620:   VecScatterSetFromOptions - Configures the vector scatter from values in the options database.

622:   Collective

624:   Input Parameter:
625: . sf - The vector scatter

627:   Notes:
628:   To see all options, run your program with the -help option, or consult the users manual.

630:   Must be called before `VecScatterSetUp()` and before the vector scatter is used.

632:   Level: beginner

634: .seealso: [](sec_scatter), `VecScatter`, `VecScatterCreate()`, `VecScatterDestroy()`, `VecScatterSetUp()`
635: @*/
636: PetscErrorCode VecScatterSetFromOptions(VecScatter sf)
637: {
638:   PetscFunctionBegin;
640:   PetscObjectOptionsBegin((PetscObject)sf);

642:   sf->vscat.beginandendtogether = PETSC_FALSE;
643:   PetscCall(PetscOptionsBool("-vecscatter_merge", "Use combined (merged) vector scatter begin and end", "VecScatterCreate", sf->vscat.beginandendtogether, &sf->vscat.beginandendtogether, NULL));
644:   if (sf->vscat.beginandendtogether) PetscCall(PetscInfo(sf, "Using combined (merged) vector scatter begin and end\n"));
645:   PetscOptionsEnd();
646:   PetscFunctionReturn(PETSC_SUCCESS);
647: }

649: /*@
650:   VecScatterCreate - Creates a vector scatter `VecScatter` context that is used to communicate entries between two vectors `Vec`

652:   Collective

654:   Input Parameters:
655: + x  - a vector that defines the shape (parallel data layout of the vector) of vectors from which we scatter
656: . y  - a vector that defines the shape (parallel data layout of the vector) of vectors to which we scatter
657: . ix - the indices of `x` to scatter (if `NULL` scatters all values)
658: - iy - the indices of `y` to hold results (if `NULL` fills entire vector `yin` in order)

660:   Output Parameter:
661: . newsf - location to store the new scatter context

663:   Options Database Key:
664: . -vecscatter_merge (true|false) - `VecScatterBegin()` handles all of the communication, `VecScatterEnd()` is a nop
665:                                    eliminates the chance for overlap of computation and communication

667:   Level: intermediate

669:   Notes:
670:   If both `x` and `y` are parallel, their communicator must be on the same
671:   set of processes, but their process order can be different.
672:   In calls to the scatter options you can use different vectors than the `x` and
673:   `y` you used above; BUT they must have the same parallel data layout, for example,
674:   they could be obtained from `VecDuplicate()`.
675:   A `VecScatter` context CANNOT be used in two or more simultaneous scatters;
676:   that is you cannot call a second `VecScatterBegin()` with the same scatter
677:   context until the `VecScatterEnd()` has been called on the first `VecScatterBegin()`.
678:   In this case a separate `VecScatter` is needed for each concurrent scatter.

680:   Both `ix` and `iy` cannot be `NULL` at the same time.

682:   Use `VecScatterCreateToAll()` to create a `VecScatter` that copies an MPI vector to sequential vectors on all MPI processes.
683:   Use `VecScatterCreateToZero()` to create a `VecScatter` that copies an MPI vector to a sequential vector on MPI process 0.
684:   These special `VecScatter` have better performance than general ones.

686:   Developer Note:
687:   The implementations of most the `VecScatter` are done using `PetscSF`.

689: .seealso: [](sec_scatter), `VecScatter`, `VecScatterDestroy()`, `VecScatterCreateToAll()`, `VecScatterCreateToZero()`, `PetscSFCreate()`,
690:           `VecScatterType`, `InsertMode`, `ScatterMode`, `VecScatterBegin()`, `VecScatterEnd()`, `VecScatterViewFromOptions()`, `VecScatterView()`
691: @*/
692: PetscErrorCode VecScatterCreate(Vec x, IS ix, Vec y, IS iy, VecScatter *newsf)
693: {
694:   MPI_Comm        xcomm, ycomm, bigcomm;
695:   Vec             xx, yy;
696:   IS              ix_old = ix, iy_old = iy, ixx, iyy;
697:   PetscMPIInt     xcommsize, ycommsize, rank, result;
698:   PetscInt        i, n, N, nroots, nleaves, *ilocal, xstart, ystart, ixsize, iysize, xlen, ylen;
699:   const PetscInt *xindices, *yindices;
700:   PetscSFNode    *iremote;
701:   PetscLayout     xlayout, ylayout;
702:   ISTypeID        ixid, iyid;
703:   PetscInt        bs, bsx, bsy, min, max, m[2], mg[2], ixfirst, ixstep, iyfirst, iystep;
704:   PetscBool       can_do_block_opt = PETSC_FALSE;
705:   PetscSF         sf;

707:   PetscFunctionBegin;
708:   PetscAssertPointer(newsf, 5);
709:   PetscCheck(ix || iy, PetscObjectComm((PetscObject)x), PETSC_ERR_SUP, "Cannot pass default in for both input and output indices");

711:   /* Get comm from x and y */
712:   PetscCall(PetscObjectGetComm((PetscObject)x, &xcomm));
713:   PetscCallMPI(MPI_Comm_size(xcomm, &xcommsize));
714:   PetscCall(PetscObjectGetComm((PetscObject)y, &ycomm));
715:   PetscCallMPI(MPI_Comm_size(ycomm, &ycommsize));
716:   if (xcommsize > 1 && ycommsize > 1) {
717:     PetscCallMPI(MPI_Comm_compare(xcomm, ycomm, &result));
718:     PetscCheck(result != MPI_UNEQUAL, PETSC_COMM_SELF, PETSC_ERR_ARG_NOTSAMECOMM, "VecScatterCreate: parallel vectors x and y must have identical/congruent/similar communicators");
719:   }
720:   bs = 1; /* default, no blocking */

722:   /*
723:    Let P and S stand for parallel and sequential vectors respectively. There are four combinations of vecscatters: PtoP, PtoS,
724:    StoP and StoS. The assumption of VecScatterCreate(Vec x,IS ix,Vec y,IS iy,VecScatter *newctx) is: if x is parallel, then ix
725:    contains global indices of x. If x is sequential, ix contains local indices of x. Similarly for y and iy.

727:    SF builds around concepts of local leaves and remote roots. We treat source vector x as roots and destination vector y as
728:    leaves. A PtoS scatter can be naturally mapped to SF. We transform PtoP and StoP to PtoS, and treat StoS as trivial PtoS.
729:   */

731:   /* NULL ix or iy in VecScatterCreate(x,ix,y,iy,newctx) has special meaning. Recover them for these cases */
732:   if (!ix) {
733:     if (xcommsize > 1 && ycommsize == 1) { /* PtoS: null ix means the whole x will be scattered to each seq y */
734:       PetscCall(VecGetSize(x, &N));
735:       PetscCall(ISCreateStride(PETSC_COMM_SELF, N, 0, 1, &ix));
736:     } else { /* PtoP, StoP or StoS: null ix means the whole local part of x will be scattered */
737:       PetscCall(VecGetLocalSize(x, &n));
738:       PetscCall(VecGetOwnershipRange(x, &xstart, NULL));
739:       PetscCall(ISCreateStride(PETSC_COMM_SELF, n, xstart, 1, &ix));
740:     }
741:   }

743:   if (!iy) {
744:     if (xcommsize == 1 && ycommsize > 1) { /* StoP: null iy means the whole y will be scattered to from each seq x */
745:       PetscCall(VecGetSize(y, &N));
746:       PetscCall(ISCreateStride(PETSC_COMM_SELF, N, 0, 1, &iy));
747:     } else { /* PtoP, StoP or StoS: null iy means the whole local part of y will be scattered to */
748:       PetscCall(VecGetLocalSize(y, &n));
749:       PetscCall(VecGetOwnershipRange(y, &ystart, NULL));
750:       PetscCall(ISCreateStride(PETSC_COMM_SELF, n, ystart, 1, &iy));
751:     }
752:   }

754:   /* Do error checking immediately after we have non-empty ix, iy */
755:   PetscCall(ISGetLocalSize(ix, &ixsize));
756:   PetscCall(ISGetLocalSize(iy, &iysize));
757:   PetscCall(VecGetSize(x, &xlen));
758:   PetscCall(VecGetSize(y, &ylen));
759:   PetscCheck(ixsize == iysize, PETSC_COMM_SELF, PETSC_ERR_ARG_SIZ, "Scatter sizes of ix and iy don't match locally ix=%" PetscInt_FMT " iy=%" PetscInt_FMT, ixsize, iysize);
760:   PetscCall(ISGetMinMax(ix, &min, &max));
761:   PetscCheck(min >= 0 && max < xlen, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Scatter indices in ix are out of range: found [%" PetscInt_FMT ",%" PetscInt_FMT "), expected in [0,%" PetscInt_FMT ")", min, max, xlen);
762:   PetscCall(ISGetMinMax(iy, &min, &max));
763:   PetscCheck(min >= 0 && max < ylen, PETSC_COMM_SELF, PETSC_ERR_ARG_OUTOFRANGE, "Scatter indices in iy are out of range: found [%" PetscInt_FMT ",%" PetscInt_FMT "), expected in [0,%" PetscInt_FMT ")", min, max, ylen);

765:   /* Extract info about ix, iy for further test */
766:   PetscCall(ISGetTypeID_Private(ix, &ixid));
767:   PetscCall(ISGetTypeID_Private(iy, &iyid));
768:   if (ixid == IS_BLOCK) PetscCall(ISGetBlockSize(ix, &bsx));
769:   else if (ixid == IS_STRIDE) PetscCall(ISStrideGetInfo(ix, &ixfirst, &ixstep));

771:   if (iyid == IS_BLOCK) PetscCall(ISGetBlockSize(iy, &bsy));
772:   else if (iyid == IS_STRIDE) PetscCall(ISStrideGetInfo(iy, &iyfirst, &iystep));

774:   /* Check if a PtoS is special ToAll/ToZero scatters, which can be results of VecScatterCreateToAll/Zero.
775:      ToAll means a whole MPI vector is copied to a seq vector on every process. ToZero means a whole MPI
776:      vector is copied to a seq vector on rank 0 and other processes do nothing(i.e.,they input empty ix,iy).

778:      We can optimize these scatters with MPI collectives. We can also avoid costly analysis used for general scatters.
779:   */
780:   if (xcommsize > 1 && ycommsize == 1) { /* Ranks do not diverge at this if-test */
781:     PetscInt    pattern[2] = {0, 0};     /* A boolean array with pattern[0] for allgather-like (ToAll) and pattern[1] for gather-like (ToZero) */
782:     PetscLayout map;

784:     PetscCallMPI(MPI_Comm_rank(xcomm, &rank));
785:     PetscCall(VecGetLayout(x, &map));
786:     if (rank == 0) {
787:       if (ixid == IS_STRIDE && iyid == IS_STRIDE && ixsize == xlen && ixfirst == 0 && ixstep == 1 && iyfirst == 0 && iystep == 1) {
788:         /* Rank 0 scatters the whole mpi x to seq y, so it is either a ToAll or a ToZero candidate in its view */
789:         pattern[0] = pattern[1] = 1;
790:       }
791:     } else {
792:       if (ixid == IS_STRIDE && iyid == IS_STRIDE && ixsize == xlen && ixfirst == 0 && ixstep == 1 && iyfirst == 0 && iystep == 1) {
793:         /* Other ranks also scatter the whole mpi x to seq y, so it is a ToAll candidate in their view */
794:         pattern[0] = 1;
795:       } else if (ixsize == 0) {
796:         /* Other ranks do nothing, so it is a ToZero candidate */
797:         pattern[1] = 1;
798:       }
799:     }

801:     /* One stone (the expensive allreduce) two birds: pattern[] tells if it is ToAll or ToZero */
802:     PetscCallMPI(MPIU_Allreduce(MPI_IN_PLACE, pattern, 2, MPIU_INT, MPI_LAND, xcomm));

804:     if (pattern[0] || pattern[1]) {
805:       PetscCall(PetscSFCreate(xcomm, &sf));
806:       PetscCall(PetscSFSetFromOptions(sf));
807:       PetscCall(PetscSFSetGraphWithPattern(sf, map, pattern[0] ? PETSCSF_PATTERN_ALLGATHER : PETSCSF_PATTERN_GATHER));
808:       goto functionend; /* No further analysis needed. What a big win! */
809:     }
810:   }

812:   /* Continue ...
813:      Do block optimization by taking advantage of high level info available in ix, iy.
814:      The block optimization is valid when all of the following conditions are met:
815:      1) ix, iy are blocked or can be blocked (i.e., strided with step=1);
816:      2) ix, iy have the same block size;
817:      3) all processors agree on one block size;
818:      4) no blocks span more than one process;
819:    */
820:   bigcomm = (xcommsize == 1) ? ycomm : xcomm;

822:   /* Processors could go through different path in this if-else test */
823:   m[0] = PETSC_INT_MAX;
824:   m[1] = PETSC_INT_MIN;
825:   if (ixid == IS_BLOCK && iyid == IS_BLOCK) {
826:     m[0] = PetscMin(bsx, bsy);
827:     m[1] = PetscMax(bsx, bsy);
828:   } else if (ixid == IS_BLOCK && iyid == IS_STRIDE && iystep == 1 && iyfirst % bsx == 0) {
829:     m[0] = bsx;
830:     m[1] = bsx;
831:   } else if (ixid == IS_STRIDE && iyid == IS_BLOCK && ixstep == 1 && ixfirst % bsy == 0) {
832:     m[0] = bsy;
833:     m[1] = bsy;
834:   }
835:   /* Get max and min of bsx,bsy over all processes in one allreduce */
836:   PetscCall(PetscGlobalMinMaxInt(bigcomm, m, mg));

838:   /* Since we used allreduce above, all ranks will have the same min and max. min==max
839:      implies all ranks have the same bs. Do further test to see if local vectors are dividable
840:      by bs on ALL ranks. If they are, we are ensured that no blocks span more than one processor.
841:    */
842:   if (mg[0] == mg[1] && mg[0] > 1) {
843:     PetscCall(VecGetLocalSize(x, &xlen));
844:     PetscCall(VecGetLocalSize(y, &ylen));
845:     m[0] = xlen % mg[0];
846:     m[1] = ylen % mg[0];
847:     PetscCallMPI(MPIU_Allreduce(MPI_IN_PLACE, m, 2, MPIU_INT, MPI_LOR, bigcomm));
848:     if (!m[0] && !m[1]) can_do_block_opt = PETSC_TRUE;
849:   }

851:   /* If can_do_block_opt, then shrink x, y, ix and iy by bs to get xx, yy, ixx and iyy, whose indices
852:      and layout are actually used in building SF. Suppose blocked ix representing {0,1,2,6,7,8} has
853:      indices {0,2} and bs=3, then ixx = {0,2}; suppose strided iy={3,4,5,6,7,8}, then iyy={1,2}.

855:      xx is a little special. If x is seq, then xx is the concatenation of seq x's on ycomm. In this way,
856:      we can treat PtoP and StoP uniformly as PtoS.
857:    */
858:   if (can_do_block_opt) {
859:     const PetscInt *indices;

861:     /* Shrink x and ix */
862:     bs = mg[0];
863:     PetscCall(VecCreateMPIWithArray(bigcomm, 1, xlen / bs, PETSC_DECIDE, NULL, &xx)); /* We only care xx's layout */
864:     if (ixid == IS_BLOCK) {
865:       PetscCall(ISBlockGetIndices(ix, &indices));
866:       PetscCall(ISBlockGetLocalSize(ix, &ixsize));
867:       PetscCall(ISCreateGeneral(PETSC_COMM_SELF, ixsize, indices, PETSC_COPY_VALUES, &ixx));
868:       PetscCall(ISBlockRestoreIndices(ix, &indices));
869:     } else { /* ixid == IS_STRIDE */
870:       PetscCall(ISGetLocalSize(ix, &ixsize));
871:       PetscCall(ISCreateStride(PETSC_COMM_SELF, ixsize / bs, ixfirst / bs, 1, &ixx));
872:     }

874:     /* Shrink y and iy */
875:     PetscCall(VecCreateMPIWithArray(ycomm, 1, ylen / bs, PETSC_DECIDE, NULL, &yy));
876:     if (iyid == IS_BLOCK) {
877:       PetscCall(ISBlockGetIndices(iy, &indices));
878:       PetscCall(ISBlockGetLocalSize(iy, &iysize));
879:       PetscCall(ISCreateGeneral(PETSC_COMM_SELF, iysize, indices, PETSC_COPY_VALUES, &iyy));
880:       PetscCall(ISBlockRestoreIndices(iy, &indices));
881:     } else { /* iyid == IS_STRIDE */
882:       PetscCall(ISGetLocalSize(iy, &iysize));
883:       PetscCall(ISCreateStride(PETSC_COMM_SELF, iysize / bs, iyfirst / bs, 1, &iyy));
884:     }
885:   } else {
886:     ixx = ix;
887:     iyy = iy;
888:     yy  = y;
889:     if (xcommsize == 1) PetscCall(VecCreateMPIWithArray(bigcomm, 1, xlen, PETSC_DECIDE, NULL, &xx));
890:     else xx = x;
891:   }

893:   /* Now it is ready to build SF with preprocessed (xx, yy) and (ixx, iyy) */
894:   PetscCall(ISGetIndices(ixx, &xindices));
895:   PetscCall(ISGetIndices(iyy, &yindices));
896:   PetscCall(VecGetLayout(xx, &xlayout));

898:   if (ycommsize > 1) {
899:     /* PtoP or StoP */

901:     /* Below is a piece of complex code with a very simple goal: move global index pairs (xindices[i], yindices[i]),
902:        to owner process of yindices[i] according to ylayout, i = 0..n.

904:        I did it through a temp sf, but later I thought the old design was inefficient and also distorted log view.
905:        We want to map one VecScatterCreate() call to one PetscSFCreate() call. The old design mapped to three
906:        PetscSFCreate() calls. This code is on critical path of VecScatterSetUp and is used by every VecScatterCreate.
907:        So I commented it out and did another optimized implementation. The commented code is left here for reference.
908:      */
909: #if 0
910:     const PetscInt *degree;
911:     PetscSF        tmpsf;
912:     PetscInt       inedges=0,*leafdata,*rootdata;

914:     PetscCall(VecGetOwnershipRange(xx,&xstart,NULL));
915:     PetscCall(VecGetLayout(yy,&ylayout));
916:     PetscCall(VecGetOwnershipRange(yy,&ystart,NULL));

918:     PetscCall(VecGetLocalSize(yy,&nroots));
919:     PetscCall(ISGetLocalSize(iyy,&nleaves));
920:     PetscCall(PetscMalloc2(nleaves,&iremote,nleaves*2,&leafdata));

922:     for (i=0; i<nleaves; i++) {
923:       PetscCall(PetscLayoutFindOwnerIndex(ylayout,yindices[i],&iremote[i].rank,&iremote[i].index));
924:       leafdata[2*i]   = yindices[i];
925:       leafdata[2*i+1] = (xcommsize > 1)? xindices[i] : xindices[i] + xstart;
926:     }

928:     PetscCall(PetscSFCreate(ycomm,&tmpsf));
929:     PetscCall(PetscSFSetGraph(tmpsf,nroots,nleaves,NULL,PETSC_USE_POINTER,iremote,PETSC_USE_POINTER));

931:     PetscCall(PetscSFComputeDegreeBegin(tmpsf,&degree));
932:     PetscCall(PetscSFComputeDegreeEnd(tmpsf,&degree));

934:     for (i=0; i<nroots; i++) inedges += degree[i];
935:     PetscCall(PetscMalloc1(inedges*2,&rootdata));
936:     PetscCall(PetscSFGatherBegin(tmpsf,MPIU_2INT,leafdata,rootdata));
937:     PetscCall(PetscSFGatherEnd(tmpsf,MPIU_2INT,leafdata,rootdata));

939:     PetscCall(PetscFree2(iremote,leafdata));
940:     PetscCall(PetscSFDestroy(&tmpsf));

942:     /* rootdata contains global index pairs (i, j). j's are owned by the current process, but i's can point to anywhere.
943:        We convert j to local, and convert i to (rank, index). In the end, we get an PtoS suitable for building SF.
944:      */
945:     nleaves = inedges;
946:     PetscCall(VecGetLocalSize(xx,&nroots));
947:     PetscCall(PetscMalloc1(nleaves,&ilocal));
948:     PetscCall(PetscMalloc1(nleaves,&iremote));

950:     for (i=0; i<inedges; i++) {
951:       ilocal[i] = rootdata[2*i] - ystart; /* convert y's global index to local index */
952:       PetscCall(PetscLayoutFindOwnerIndex(xlayout,rootdata[2*i+1],&iremote[i].rank,&iremote[i].index)); /* convert x's global index to (rank, index) */
953:     }
954:     PetscCall(PetscFree(rootdata));
955: #else
956:     PetscInt        j, k, n, disp, rlentotal, *sstart, *xindices_sorted, *yindices_sorted;
957:     const PetscInt *yrange;
958:     PetscMPIInt     nsend, nrecv, nreq, yrank, *sendto, *recvfrom, tag1, tag2;
959:     PetscInt       *slens, *rlens, count;
960:     PetscInt       *rxindices, *ryindices;
961:     MPI_Request    *reqs, *sreqs, *rreqs;

963:     /* Sorting makes code simpler, faster and also helps getting rid of many O(P) arrays, which hurt scalability at large scale
964:        yindices_sorted - sorted yindices
965:        xindices_sorted - xindices sorted along with yindces
966:      */
967:     PetscCall(ISGetLocalSize(ixx, &n)); /*ixx, iyy have the same local size */
968:     PetscCall(PetscMalloc2(n, &xindices_sorted, n, &yindices_sorted));
969:     PetscCall(PetscArraycpy(xindices_sorted, xindices, n));
970:     PetscCall(PetscArraycpy(yindices_sorted, yindices, n));
971:     PetscCall(PetscSortIntWithArray(n, yindices_sorted, xindices_sorted));
972:     PetscCall(VecGetOwnershipRange(xx, &xstart, NULL));
973:     if (xcommsize == 1) {
974:       for (i = 0; i < n; i++) xindices_sorted[i] += xstart;
975:     } /* Convert to global indices */

977:     /*
978:              Calculate info about messages I need to send
979:        nsend    - number of non-empty messages to send
980:        sendto   - [nsend] ranks I will send messages to
981:        sstart   - [nsend+1] sstart[i] is the start index in xsindices_sorted[] I send to rank sendto[i]
982:        slens    - [ycommsize] I want to send slens[i] entries to rank i.
983:      */
984:     PetscCall(VecGetLayout(yy, &ylayout));
985:     PetscCall(PetscLayoutGetRanges(ylayout, &yrange));
986:     PetscCall(PetscCalloc1(ycommsize, &slens)); /* The only O(P) array in this algorithm */

988:     i = j = nsend = 0;
989:     while (i < n) {
990:       if (yindices_sorted[i] >= yrange[j + 1]) { /* If i-th index is out of rank j's bound */
991:         do {
992:           j++;
993:         } while (yindices_sorted[i] >= yrange[j + 1] && j < ycommsize); /* Increase j until i-th index falls in rank j's bound */
994:         PetscCheck(j != ycommsize, PETSC_COMM_SELF, PETSC_ERR_PLIB, "Index %" PetscInt_FMT " not owned by any process, upper bound %" PetscInt_FMT, yindices_sorted[i], yrange[ycommsize]);
995:       }
996:       i++;
997:       if (!slens[j]++) nsend++;
998:     }

1000:     PetscCall(PetscMalloc2(nsend + 1, &sstart, nsend, &sendto));

1002:     sstart[0] = 0;
1003:     for (i = j = 0; i < ycommsize; i++) {
1004:       if (slens[i]) {
1005:         PetscCall(PetscMPIIntCast(i, &sendto[j]));
1006:         sstart[j + 1] = sstart[j] + slens[i];
1007:         j++;
1008:       }
1009:     }

1011:     /*
1012:       Calculate the reverse info about messages I will recv
1013:        nrecv     - number of messages I will recv
1014:        recvfrom  - [nrecv] ranks I recv from
1015:        rlens     - [nrecv] I will recv rlens[i] entries from rank recvfrom[i]
1016:        rlentotal - sum of rlens[]
1017:        rxindices - [rlentotal] recv buffer for xindices_sorted
1018:        ryindices - [rlentotal] recv buffer for yindices_sorted
1019:      */
1020:     PetscCall(PetscGatherNumberOfMessages_Private(ycomm, NULL, slens, &nrecv));
1021:     PetscCall(PetscGatherMessageLengths_Private(ycomm, nsend, nrecv, slens, &recvfrom, &rlens));
1022:     PetscCall(PetscFree(slens)); /* Free the O(P) array ASAP */
1023:     rlentotal = 0;
1024:     for (i = 0; i < nrecv; i++) rlentotal += rlens[i];

1026:     /*
1027:       Communicate with processors in recvfrom[] to populate rxindices and ryindices
1028:     */
1029:     PetscCall(PetscCommGetNewTag(ycomm, &tag1));
1030:     PetscCall(PetscCommGetNewTag(ycomm, &tag2));
1031:     PetscCall(PetscMalloc2(rlentotal, &rxindices, rlentotal, &ryindices));
1032:     PetscCall(PetscMPIIntCast((nsend + nrecv) * 2, &nreq));
1033:     PetscCall(PetscMalloc1(nreq, &reqs));
1034:     sreqs = reqs;
1035:     rreqs = PetscSafePointerPlusOffset(reqs, nsend * 2);

1037:     for (i = disp = 0; i < nrecv; i++) {
1038:       count = rlens[i];
1039:       PetscCallMPI(MPIU_Irecv(rxindices + disp, count, MPIU_INT, recvfrom[i], tag1, ycomm, rreqs + i));
1040:       PetscCallMPI(MPIU_Irecv(ryindices + disp, count, MPIU_INT, recvfrom[i], tag2, ycomm, rreqs + nrecv + i));
1041:       disp += rlens[i];
1042:     }

1044:     for (i = 0; i < nsend; i++) {
1045:       count = sstart[i + 1] - sstart[i];
1046:       PetscCallMPI(MPIU_Isend(xindices_sorted + sstart[i], count, MPIU_INT, sendto[i], tag1, ycomm, sreqs + i));
1047:       PetscCallMPI(MPIU_Isend(yindices_sorted + sstart[i], count, MPIU_INT, sendto[i], tag2, ycomm, sreqs + nsend + i));
1048:     }
1049:     PetscCallMPI(MPI_Waitall(nreq, reqs, MPI_STATUSES_IGNORE));

1051:     /* Transform VecScatter into SF */
1052:     nleaves = rlentotal;
1053:     PetscCall(PetscMalloc1(nleaves, &ilocal));
1054:     PetscCall(PetscMalloc1(nleaves, &iremote));
1055:     PetscCallMPI(MPI_Comm_rank(ycomm, &yrank));
1056:     for (i = disp = 0; i < nrecv; i++) {
1057:       for (j = 0; j < rlens[i]; j++) {
1058:         k         = disp + j;                                                                  /* k-th index pair */
1059:         ilocal[k] = ryindices[k] - yrange[yrank];                                              /* Convert y's global index to local index */
1060:         PetscCall(PetscLayoutFindOwnerIndex(xlayout, rxindices[k], &rank, &iremote[k].index)); /* Convert x's global index to (rank, index) */
1061:         iremote[k].rank = rank;
1062:       }
1063:       disp += rlens[i];
1064:     }

1066:     PetscCall(PetscFree2(sstart, sendto));
1067:     PetscCall(PetscFree(rlens));
1068:     PetscCall(PetscFree(recvfrom));
1069:     PetscCall(PetscFree(reqs));
1070:     PetscCall(PetscFree2(rxindices, ryindices));
1071:     PetscCall(PetscFree2(xindices_sorted, yindices_sorted));
1072: #endif
1073:   } else {
1074:     /* PtoS or StoS */
1075:     PetscCall(ISGetLocalSize(iyy, &nleaves));
1076:     PetscCall(PetscMalloc1(nleaves, &ilocal));
1077:     PetscCall(PetscMalloc1(nleaves, &iremote));
1078:     PetscCall(PetscArraycpy(ilocal, yindices, nleaves));
1079:     for (i = 0; i < nleaves; i++) {
1080:       PetscCall(PetscLayoutFindOwnerIndex(xlayout, xindices[i], &rank, &iremote[i].index));
1081:       iremote[i].rank = rank;
1082:     }
1083:   }

1085:   /* MUST build SF on xx's comm, which is not necessarily identical to yy's comm.
1086:      In SF's view, xx contains the roots (i.e., the remote) and iremote[].rank are ranks in xx's comm.
1087:      yy contains leaves, which are local and can be thought as part of PETSC_COMM_SELF. */
1088:   PetscCall(PetscSFCreate(PetscObjectComm((PetscObject)xx), &sf));
1089:   sf->allow_multi_leaves = PETSC_TRUE;
1090:   PetscCall(PetscSFSetFromOptions(sf));
1091:   PetscCall(VecGetLocalSize(xx, &nroots));
1092:   PetscCall(PetscSFSetGraph(sf, nroots, nleaves, ilocal, PETSC_OWN_POINTER, iremote, PETSC_OWN_POINTER)); /* Give ilocal/iremote to PETSc and no need to free them here */

1094:   /* Free memory no longer needed */
1095:   PetscCall(ISRestoreIndices(ixx, &xindices));
1096:   PetscCall(ISRestoreIndices(iyy, &yindices));
1097:   if (can_do_block_opt) {
1098:     PetscCall(VecDestroy(&xx));
1099:     PetscCall(VecDestroy(&yy));
1100:     PetscCall(ISDestroy(&ixx));
1101:     PetscCall(ISDestroy(&iyy));
1102:   } else if (xcommsize == 1) {
1103:     PetscCall(VecDestroy(&xx));
1104:   }

1106: functionend:
1107:   sf->vscat.bs = bs;
1108:   if (sf->vscat.bs > 1) {
1109:     PetscMPIInt ibs;

1111:     PetscCall(PetscMPIIntCast(sf->vscat.bs, &ibs));
1112:     PetscCallMPI(MPI_Type_contiguous(ibs, MPIU_SCALAR, &sf->vscat.unit));
1113:     PetscCallMPI(MPI_Type_commit(&sf->vscat.unit));
1114:   } else {
1115:     sf->vscat.unit = MPIU_SCALAR;
1116:   }
1117:   PetscCall(VecGetLocalSize(x, &sf->vscat.from_n));
1118:   PetscCall(VecGetLocalSize(y, &sf->vscat.to_n));
1119:   if (!ix_old) PetscCall(ISDestroy(&ix)); /* We created helper ix, iy. Free them */
1120:   if (!iy_old) PetscCall(ISDestroy(&iy));

1122:   /* Set default */
1123:   PetscCall(VecScatterSetFromOptions(sf));
1124:   PetscCall(PetscSFSetUp(sf));

1126:   *newsf = sf;
1127:   PetscFunctionReturn(PETSC_SUCCESS);
1128: }

1130: /*@
1131:   VecScatterCreateToAll - Creates a vector and a scatter context that copies all
1132:   vector values to each processor

1134:   Collective

1136:   Input Parameter:
1137: . vin - an `MPIVEC`

1139:   Output Parameters:
1140: + ctx  - scatter context
1141: - vout - output `SEQVEC` that is large enough to scatter into

1143:   Level: intermediate

1145:   Example Usage:
1146: .vb
1147:   VecScatterCreateToAll(vin, &ctx, &vout);

1149:   // scatter as many times as you need
1150:   VecScatterBegin(ctx, vin, vout, INSERT_VALUES, SCATTER_FORWARD);
1151:   VecScatterEnd(ctx, vin, vout, INSERT_VALUES, SCATTER_FORWARD);

1153:   // destroy scatter context and local vector when no longer needed
1154:   VecScatterDestroy(&ctx);
1155:   VecDestroy(&vout);
1156: .ve

1158:   Notes:
1159:   `vout` may be `NULL` [`PETSC_NULL_VEC` from Fortran] if you do not
1160:   need to have it created

1162:   Do NOT create a vector and then pass it in as the final argument `vout`! `vout` is created by this routine
1163:   automatically (unless you pass `NULL` in for that argument if you do not need it).

1165: .seealso: [](sec_scatter), `VecScatter`, `VecScatterCreate()`, `VecScatterCreateToZero()`, `VecScatterBegin()`, `VecScatterEnd()`
1166: @*/
1167: PetscErrorCode VecScatterCreateToAll(Vec vin, VecScatter *ctx, Vec *vout)
1168: {
1169:   PetscInt  N;
1170:   IS        is;
1171:   Vec       tmp;
1172:   Vec      *tmpv;
1173:   PetscBool tmpvout = PETSC_FALSE;
1174:   VecType   roottype;

1176:   PetscFunctionBegin;
1179:   PetscAssertPointer(ctx, 2);
1180:   if (vout) {
1181:     PetscAssertPointer(vout, 3);
1182:     tmpv = vout;
1183:   } else {
1184:     tmpvout = PETSC_TRUE;
1185:     tmpv    = &tmp;
1186:   }

1188:   /* Create seq vec on each proc, with the same size of the original vec */
1189:   PetscCall(VecGetSize(vin, &N));
1190:   PetscCall(VecGetRootType_Private(vin, &roottype));
1191:   PetscCall(VecCreate(PETSC_COMM_SELF, tmpv));
1192:   PetscCall(VecSetSizes(*tmpv, N, PETSC_DECIDE));
1193:   PetscCall(VecSetType(*tmpv, roottype));
1194:   /* Create the VecScatter ctx with the communication info */
1195:   PetscCall(ISCreateStride(PETSC_COMM_SELF, N, 0, 1, &is));
1196:   PetscCall(VecScatterCreate(vin, is, *tmpv, is, ctx));
1197:   PetscCall(ISDestroy(&is));
1198:   if (tmpvout) PetscCall(VecDestroy(tmpv));
1199:   PetscFunctionReturn(PETSC_SUCCESS);
1200: }

1202: /*@
1203:   VecScatterCreateToZero - Creates an output vector and a scatter context used to
1204:   copy all vector values into the output vector on the zeroth processor

1206:   Collective

1208:   Input Parameter:
1209: . vin - `Vec` of type `MPIVEC`

1211:   Output Parameters:
1212: + ctx  - scatter context
1213: - vout - output `SEQVEC` that is large enough to scatter into on processor 0 and
1214:           of length zero on all other processors

1216:   Level: intermediate

1218:   Example Usage:
1219: .vb
1220:   VecScatterCreateToZero(vin, &ctx, &vout);

1222:   // scatter as many times as you need
1223:   VecScatterBegin(ctx, vin, vout, INSERT_VALUES, SCATTER_FORWARD);
1224:   VecScatterEnd(ctx, vin, vout, INSERT_VALUES, SCATTER_FORWARD);

1226:   // destroy scatter context and local vector when no longer needed
1227:   VecScatterDestroy(&ctx);
1228:   VecDestroy(&vout);
1229: .ve

1231:   Notes:
1232:   vout may be `NULL` [`PETSC_NULL_VEC` from Fortran] if you do not
1233:   need to have it created

1235:   Do NOT create a vector and then pass it in as the final argument `vout`! `vout` is created by this routine
1236:   automatically (unless you pass `NULL` in for that argument if you do not need it).

1238: .seealso: [](sec_scatter), `VecScatter`, `VecScatterCreate()`, `VecScatterCreateToAll()`, `VecScatterBegin()`, `VecScatterEnd()`
1239: @*/
1240: PetscErrorCode VecScatterCreateToZero(Vec vin, VecScatter *ctx, Vec *vout)
1241: {
1242:   PetscInt    N;
1243:   PetscMPIInt rank;
1244:   IS          is;
1245:   Vec         tmp;
1246:   Vec        *tmpv;
1247:   PetscBool   tmpvout = PETSC_FALSE;
1248:   VecType     roottype;

1250:   PetscFunctionBegin;
1253:   PetscAssertPointer(ctx, 2);
1254:   if (vout) {
1255:     PetscAssertPointer(vout, 3);
1256:     tmpv = vout;
1257:   } else {
1258:     tmpvout = PETSC_TRUE;
1259:     tmpv    = &tmp;
1260:   }

1262:   /* Create vec on each proc, with the same size of the original vec all on process 0 */
1263:   PetscCall(VecGetSize(vin, &N));
1264:   PetscCallMPI(MPI_Comm_rank(PetscObjectComm((PetscObject)vin), &rank));
1265:   if (rank) N = 0;
1266:   PetscCall(VecGetRootType_Private(vin, &roottype));
1267:   PetscCall(VecCreate(PETSC_COMM_SELF, tmpv));
1268:   PetscCall(VecSetSizes(*tmpv, N, PETSC_DECIDE));
1269:   PetscCall(VecSetType(*tmpv, roottype));
1270:   /* Create the VecScatter ctx with the communication info */
1271:   PetscCall(ISCreateStride(PETSC_COMM_SELF, N, 0, 1, &is));
1272:   PetscCall(VecScatterCreate(vin, is, *tmpv, is, ctx));
1273:   PetscCall(ISDestroy(&is));
1274:   if (tmpvout) PetscCall(VecDestroy(tmpv));
1275:   PetscFunctionReturn(PETSC_SUCCESS);
1276: }

1278: /*@
1279:   VecScatterBegin - Begins a generalized scatter from one vector to
1280:   another. Complete the scattering phase with `VecScatterEnd()`.

1282:   Neighbor-wise Collective

1284:   Input Parameters:
1285: + sf   - scatter context generated by `VecScatterCreate()`
1286: . x    - the vector from which we scatter
1287: . y    - the vector to which we scatter
1288: . addv - either `ADD_VALUES`, `MAX_VALUES`, `MIN_VALUES` or `INSERT_VALUES`, with `INSERT_VALUES` mode any location
1289:          not scattered to retains its old value; i.e. the vector is NOT first zeroed.
1290: - mode - the scattering mode, usually `SCATTER_FORWARD`.  The available modes are: `SCATTER_FORWARD` or `SCATTER_REVERSE`

1292:   Level: intermediate

1294:   Notes:
1295:   The vectors `x` and `y` need not be the same vectors used in the call
1296:   to `VecScatterCreate()`, but `x` must have the same parallel data layout
1297:   as that passed in as the `x` to `VecScatterCreate()`, similarly for the `y`.
1298:   Most likely they have been obtained from `VecDuplicate()`.

1300:   You cannot change the values in the input vector between the calls to `VecScatterBegin()`
1301:   and `VecScatterEnd()`.

1303:   If you use `SCATTER_REVERSE` the two arguments `x` and `y` should be reversed, from
1304:   the `SCATTER_FORWARD`.

1306: .vb
1307:   y[iy[i]] = x[ix[i]], for i=0,...,ni-1
1308: .ve

1310:   This scatter is far more general than the conventional
1311:   scatter, since it can be a gather or a scatter or a combination,
1312:   depending on the indices ix and iy.  If x is a parallel vector and y
1313:   is sequential, `VecScatterBegin()` can serve to gather values to a
1314:   single processor.  Similarly, if `y` is parallel and `x` sequential, the
1315:   routine can scatter from one processor to many processors.

1317: .seealso: [](sec_scatter), `VecScatter`, `VecScatterCreate()`, `VecScatterEnd()`, `InsertMode`, `ScatterMode`
1318: @*/
1319: PetscErrorCode VecScatterBegin(VecScatter sf, Vec x, Vec y, InsertMode addv, ScatterMode mode)
1320: {
1321:   PetscInt to_n, from_n;

1323:   PetscFunctionBegin;
1327:   if (PetscDefined(USE_DEBUG)) {
1328:     /*
1329:      Error checking to make sure these vectors match the vectors used
1330:      to create the vector scatter context. -1 in the from_n and to_n indicate the
1331:      vector lengths are unknown (for example with mapped scatters) and thus
1332:      no error checking is performed.
1333:      */
1334:     if (sf->vscat.from_n >= 0 && sf->vscat.to_n >= 0) {
1335:       PetscCall(VecGetLocalSize(x, &from_n));
1336:       PetscCall(VecGetLocalSize(y, &to_n));
1337:       if (mode & SCATTER_REVERSE) {
1338:         PetscCheck(to_n == sf->vscat.from_n, PETSC_COMM_SELF, PETSC_ERR_ARG_SIZ, "Vector wrong size %" PetscInt_FMT " for scatter %" PetscInt_FMT " (scatter reverse and vector to != sf from size)", to_n, sf->vscat.from_n);
1339:         PetscCheck(from_n == sf->vscat.to_n, PETSC_COMM_SELF, PETSC_ERR_ARG_SIZ, "Vector wrong size %" PetscInt_FMT " for scatter %" PetscInt_FMT " (scatter reverse and vector from != sf to size)", from_n, sf->vscat.to_n);
1340:       } else {
1341:         PetscCheck(to_n == sf->vscat.to_n, PETSC_COMM_SELF, PETSC_ERR_ARG_SIZ, "Vector wrong size %" PetscInt_FMT " for scatter %" PetscInt_FMT " (scatter forward and vector to != sf to size)", to_n, sf->vscat.to_n);
1342:         PetscCheck(from_n == sf->vscat.from_n, PETSC_COMM_SELF, PETSC_ERR_ARG_SIZ, "Vector wrong size %" PetscInt_FMT " for scatter %" PetscInt_FMT " (scatter forward and vector from != sf from size)", from_n, sf->vscat.from_n);
1343:       }
1344:     }
1345:   }

1347:   sf->vscat.logging = PETSC_TRUE;
1348:   PetscCall(PetscLogEventBegin(VEC_ScatterBegin, sf, x, y, 0));
1349:   PetscCall(VecScatterBegin_Internal(sf, x, y, addv, mode));
1350:   if (sf->vscat.beginandendtogether) PetscCall(VecScatterEnd_Internal(sf, x, y, addv, mode));
1351:   PetscCall(PetscLogEventEnd(VEC_ScatterBegin, sf, x, y, 0));
1352:   sf->vscat.logging = PETSC_FALSE;
1353:   PetscFunctionReturn(PETSC_SUCCESS);
1354: }

1356: /*@
1357:   VecScatterEnd - Ends a generalized scatter from one vector to another. Call
1358:   after first calling `VecScatterBegin()`.

1360:   Neighbor-wise Collective

1362:   Input Parameters:
1363: + sf   - scatter context generated by `VecScatterCreate()`
1364: . x    - the vector from which we scatter
1365: . y    - the vector to which we scatter
1366: . addv - one of `ADD_VALUES`, `MAX_VALUES`, `MIN_VALUES` or `INSERT_VALUES`
1367: - mode - the scattering mode, usually `SCATTER_FORWARD`.  The available modes are: `SCATTER_FORWARD`, `SCATTER_REVERSE`

1369:   Level: intermediate

1371:   Notes:
1372:   If you use `SCATTER_REVERSE` the arguments `x` and `y` should be reversed, from the `SCATTER_FORWARD`.

1374:   y[iy[i]] = x[ix[i]], for i=0,...,ni-1

1376: .seealso: [](sec_scatter), `VecScatter`, `VecScatterBegin()`, `VecScatterCreate()`
1377: @*/
1378: PetscErrorCode VecScatterEnd(VecScatter sf, Vec x, Vec y, InsertMode addv, ScatterMode mode)
1379: {
1380:   PetscFunctionBegin;
1384:   if (!sf->vscat.beginandendtogether) {
1385:     sf->vscat.logging = PETSC_TRUE;
1386:     PetscCall(PetscLogEventBegin(VEC_ScatterEnd, sf, x, y, 0));
1387:     PetscCall(VecScatterEnd_Internal(sf, x, y, addv, mode));
1388:     PetscCall(PetscLogEventEnd(VEC_ScatterEnd, sf, x, y, 0));
1389:     sf->vscat.logging = PETSC_FALSE;
1390:   }
1391:   PetscFunctionReturn(PETSC_SUCCESS);
1392: }