1 /*
2 * Copyright 2001, Regents of the University of Minnesota
3 *
4 * setup.c
5 *
6 * This file contains functions that setup the various communication
7 * data structures for parallel KWAY
8 *
9 * George Irene
10 */
11
12
13 #include "parmgridgen.h"
14
15 /*************************************************************************
16 * This function tests the repeated shmem_put
17 **************************************************************************/
MGridSetUp(MGridCtrlType * ctrl,MGridGraphType * graph,MGridWorkSpaceType * wspace)18 void MGridSetUp(MGridCtrlType *ctrl, MGridGraphType *graph, MGridWorkSpaceType *wspace)
19 {
20 int i, j, k, islocal, penum, gnvtxs, nvtxs, nlocal, firstvtx, lastvtx, nsend, nrecv, nnbrs, nadj;
21 int npes=ctrl->npes, mype=ctrl->mype;
22 idxtype *vtxdist, *xadj, *adjncy;
23 idxtype *peind, *recvptr, *recvind, *sendptr, *sendind;
24 idxtype *receive, *pemap, *imap, *lperm;
25 idxtype *pexadj, *peadjncy, *peadjloc, *startsind;
26 KeyValueType *recvrequests, *sendrequests, *adjpairs;
27
28 gnvtxs = graph->gnvtxs;
29 nvtxs = graph->nvtxs;
30 vtxdist = graph->vtxdist;
31 xadj = graph->xadj;
32 adjncy = graph->adjncy;
33
34 firstvtx = vtxdist[mype];
35 lastvtx = vtxdist[mype+1];
36
37 pemap = wspace->pv1;
38 idxset(npes, -1, pemap);
39
40 lperm = graph->lperm = idxmalloc(nvtxs, "SetUp: graph->lperm");
41 for (i=0; i<nvtxs; i++)
42 lperm[i] = i;
43
44 /*************************************************************
45 * Determine what you need to receive
46 *************************************************************/
47 receive = wspace->indices; /* Use the large global received array for now */
48 adjpairs = wspace->pairs;
49
50 for (nlocal = nadj = i = 0; i<nvtxs; i++) {
51 islocal = 1;
52 for (j=xadj[i]; j<xadj[i+1]; j++) {
53 k = adjncy[j];
54 if (k >= firstvtx && k < lastvtx) {
55 adjncy[j] = k-firstvtx;
56 continue; /* local vertex */
57 }
58 adjpairs[nadj].key = k;
59 adjpairs[nadj++].val = j;
60 islocal = 0;
61 }
62 if (islocal) {
63 lperm[i] = lperm[nlocal];
64 lperm[nlocal++] = i;
65 }
66 }
67
68 /* Take care the received part now */
69 ikeysort(nadj, adjpairs);
70 adjpairs[nadj].key = gnvtxs+1; /* Boundary condition */
71 for (nrecv=i=0; i<nadj; i++) {
72 adjncy[adjpairs[i].val] = nvtxs+nrecv;
73 if (adjpairs[i].key != adjpairs[i+1].key)
74 receive[nrecv++] = adjpairs[i].key;
75 }
76
77
78 /* Allocate space for the setup info attached to this level of the graph */
79 peind = graph->peind = idxmalloc(npes, "SetUp: peind");
80 recvptr = graph->recvptr = idxmalloc(npes+1, "SetUp: recvptr");
81 recvind = graph->recvind = idxmalloc(nrecv, "SetUp: recvind");
82
83 /* Take care of the received portion */
84 idxcopy(nrecv, receive, recvind); /* Copy the vertices to be received into recvind */
85
86 i = nnbrs = recvptr[0] = 0;
87 for (penum=0; penum<npes; penum++) {
88 for (j=i; j<nrecv; j++) {
89 if (recvind[j] >= vtxdist[penum+1])
90 break;
91 }
92 if (j > i) {
93 peind[nnbrs] = penum;
94 recvptr[++nnbrs] = j;
95 i = j;
96 }
97 }
98
99
100 /*************************************************************
101 * Determine what you need to send
102 *************************************************************/
103 /* Tell the other processors what they need to send you */
104 recvrequests = wspace->pepairs1;
105 sendrequests = wspace->pepairs2;
106 for (i=0; i<npes; i++)
107 recvrequests[i].key = 0;
108 for (i=0; i<nnbrs; i++) {
109 recvrequests[peind[i]].key = recvptr[i+1]-recvptr[i];
110 recvrequests[peind[i]].val = nvtxs+recvptr[i];
111 }
112 MPI_Alltoall((void *)recvrequests, 2, IDX_DATATYPE, (void *)sendrequests, 2, IDX_DATATYPE, ctrl->comm);
113
114
115 sendptr = graph->sendptr = idxmalloc(npes+1, "SetUp: sendptr");
116 startsind = wspace->pv2;
117 for (j=i=0; i<npes; i++) {
118 if (sendrequests[i].key > 0) {
119 sendptr[j] = sendrequests[i].key;
120 startsind[j] = sendrequests[i].val;
121 j++;
122 }
123 }
124 ASSERT(ctrl, nnbrs == j);
125 MAKECSR(i, j, sendptr);
126
127 nsend = sendptr[nnbrs];
128 sendind = graph->sendind = idxmalloc(nsend, "SetUp: sendind");
129
130
131 /* Issue the receives for sendind */
132 for (i=0; i<nnbrs; i++) {
133 MPI_Irecv((void *)(sendind+sendptr[i]), sendptr[i+1]-sendptr[i], IDX_DATATYPE,
134 peind[i], 1, ctrl->comm, ctrl->rreq+i);
135 }
136
137 /* Issue the sends. My recvind[penum] becomes penum's sendind[mype] */
138 for (i=0; i<nnbrs; i++) {
139 MPI_Isend((void *)(recvind+recvptr[i]), recvptr[i+1]-recvptr[i], IDX_DATATYPE,
140 peind[i], 1, ctrl->comm, ctrl->sreq+i);
141 }
142
143 MPI_Waitall(nnbrs, ctrl->rreq, ctrl->statuses);
144 MPI_Waitall(nnbrs, ctrl->sreq, ctrl->statuses);
145
146
147
148 /* Create the peadjncy data structure for sparse boundary exchanges */
149 pexadj = graph->pexadj = idxsmalloc(nvtxs+1, 0, "SetUp: pexadj");
150 peadjncy = graph->peadjncy = idxmalloc(nsend, "SetUp: peadjncy");
151 peadjloc = graph->peadjloc = idxmalloc(nsend, "SetUp: peadjloc");
152
153 for (i=0; i<nsend; i++) {
154 ASSERTP(ctrl, sendind[i] >= firstvtx && sendind[i] < lastvtx, (ctrl, "%d %d %d\n", sendind[i], firstvtx, lastvtx));
155 pexadj[sendind[i]-firstvtx]++;
156 }
157 MAKECSR(i, nvtxs, pexadj);
158
159 for (i=0; i<nnbrs; i++) {
160 for (j=sendptr[i]; j<sendptr[i+1]; j++) {
161 k = pexadj[sendind[j]-firstvtx]++;
162 peadjncy[k] = i; /* peind[i] is the actual PE number */
163 peadjloc[k] = startsind[i]++;
164 }
165 }
166 ASSERT(ctrl, pexadj[nvtxs] == nsend);
167
168 for (i=nvtxs; i>0; i--)
169 pexadj[i] = pexadj[i-1];
170 pexadj[0] = 0;
171
172
173 graph->nnbrs = nnbrs;
174 graph->nrecv = nrecv;
175 graph->nsend = nsend;
176 graph->nlocal = nlocal;
177
178
179 /* Create the inverse map from ladjncy to adjncy */
180 imap = graph->imap = idxmalloc(nvtxs+nrecv, "SetUp: imap");
181 for (i=0; i<nvtxs; i++)
182 imap[i] = firstvtx+i;
183 for (i=0; i<nrecv; i++)
184 imap[nvtxs+i] = recvind[i];
185
186
187 /* Check if wspace->nlarge is large enough for nrecv and nsend */
188 if (wspace->nlarge < nrecv+nsend) {
189 free(wspace->indices);
190 free(wspace->pairs);
191 wspace->nlarge = nrecv+nsend;
192 wspace->indices = idxmalloc(wspace->nlarge, "SetUp: wspace->indices");
193 wspace->pairs = (KeyValueType *)IMmalloc(sizeof(KeyValueType)*wspace->nlarge, "SetUp: wspace->pairs");
194 }
195
196 }
197