Tpetra parallel linear algebra Version of the Day
Loading...
Searching...
No Matches
Tpetra_Distribution2D.hpp
1// @HEADER
2// ***********************************************************************
3//
4// Tpetra: Templated Linear Algebra Services Package
5// Copyright (2008) Sandia Corporation
6//
7// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
8// the U.S. Government retains certain rights in this software.
9//
10// Redistribution and use in source and binary forms, with or without
11// modification, are permitted provided that the following conditions are
12// met:
13//
14// 1. Redistributions of source code must retain the above copyright
15// notice, this list of conditions and the following disclaimer.
16//
17// 2. Redistributions in binary form must reproduce the above copyright
18// notice, this list of conditions and the following disclaimer in the
19// documentation and/or other materials provided with the distribution.
20//
21// 3. Neither the name of the Corporation nor the names of the
22// contributors may be used to endorse or promote products derived from
23// this software without specific prior written permission.
24//
25// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
26// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
29// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
31// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36//
37// Questions? Contact Michael A. Heroux (maherou@sandia.gov)
38//
39// ************************************************************************
40// @HEADER
41
42// 2D matrix distribution
43// Assumes square matrix
44// Karen Devine, SNL
45//
46
47#ifndef __TPETRA_DISTRIBUTION2D_HPP
48#define __TPETRA_DISTRIBUTION2D_HPP
49
50namespace Tpetra
51{
52
54template <typename gno_t, typename scalar_t>
55class Distribution2D : public Distribution<gno_t,scalar_t> {
56// Processors will be laid out logically first down columns then
57// across rows. For example, assume np = 8, npRows=2, npCols=4.
58// Then the processors will be laid out in 2D as
59// 0 2 4 6
60// 1 3 5 7
61//
62// The matrix will be distributed using np=8 row blocks:
63// 0 2 4 6
64// 1 3 5 7
65// 0 2 4 6
66// 1 3 5 7
67// 0 2 4 6
68// 1 3 5 7
69// 0 2 4 6
70// 1 3 5 7
71//
72// The vector will be distributed linearly or randomly. The row and
73// column maps will be built to allow only row- or column-based
74// communication in the matvec.
75
76public:
77 using Distribution<gno_t,scalar_t>::me;
78 using Distribution<gno_t,scalar_t>::np;
79 using Distribution<gno_t,scalar_t>::comm;
80 using Distribution<gno_t,scalar_t>::nrows;
81 using Distribution<gno_t,scalar_t>::Mine;
82
83 Distribution2D(size_t nrows_,
84 const Teuchos::RCP<const Teuchos::Comm<int> > &comm_,
85 const Teuchos::ParameterList &params) :
86 Distribution<gno_t,scalar_t>(nrows_, comm_, params),
87 npRows(-1), npCols(-1)
88 {
89
90 {
91 const Teuchos::ParameterEntry *pe = params.getEntryPtr("nProcessorRows");
92 if (pe != NULL)
93 npRows = pe->getValue<int>(&npRows);
94 }
95
96 {
97 const Teuchos::ParameterEntry *pe = params.getEntryPtr("nProcessorCols");
98 if (pe != NULL)
99 npCols = pe->getValue<int>(&npCols);
100 }
101
102 // Compute the processor configuration npRows * npCols
103
104 if (npRows == -1 && npCols == -1) { // Compute both npRows and npCols
105 // First guess
106 npRows = (int)(sqrt(np));
107 npCols = np / npRows;
108 // Adjust npRows so that npRows * npCols == np
109 while (npRows * npCols != np) {
110 npRows++;
111 npCols = np / npRows;
112 }
113 }
114 else { // User specified either npRows or npCols
115 if (npRows == -1) // npCols specified; compute npRows
116 npRows = np / npCols;
117 else if (npCols == -1) // npRows specified; compute npCols
118 npCols = np / npRows;
119
120 if (npCols * npRows != np) {
121 TEUCHOS_TEST_FOR_EXCEPTION(npRows * npCols != np, std::logic_error,
122 "nProcessorCols " << npCols <<
123 " * nProcessorRows " << npRows <<
124 " = " << npCols * npRows <<
125 " must equal nProcessors " << np <<
126 " for 2D distribution");
127 }
128 }
129 if (me == 0)
130 std::cout << "\n2D Distribution: "
131 << "\n npRows = " << npRows
132 << "\n npCols = " << npCols
133 << "\n np = " << np << std::endl;
134
135 mypCol = this->TWODPCOL(me);
136 mypRow = this->TWODPROW(me);
137 }
138
139 virtual ~Distribution2D() {};
140
141protected:
142
143 // Return the processor row for rank p
144 inline int TWODPROW(int p) {return (p % npRows);}
145
146 // Return the processor column for rank p
147 inline int TWODPCOL(int p) {return (p / npRows);}
148
149 // Return the rank for processor row i and processor column j
150 inline int TWODPRANK(int i, int j) {return (j * npRows + (j+i) % npRows);}
151
152 int npRows; // Number of processor rows
153 int npCols; // Number of processor columns
154 int mypRow; // This rank's processor row
155 int mypCol; // This rank's processor column
156};
157
159template <typename gno_t, typename scalar_t>
160class Distribution2DLinear : public Distribution2D<gno_t,scalar_t> {
161
162public:
163 using Distribution<gno_t,scalar_t>::me;
164 using Distribution<gno_t,scalar_t>::np;
165 using Distribution<gno_t,scalar_t>::nrows;
166 using Distribution2D<gno_t,scalar_t>::npRows;
167 using Distribution2D<gno_t,scalar_t>::npCols;
168 using Distribution2D<gno_t,scalar_t>::mypRow;
169 using Distribution2D<gno_t,scalar_t>::mypCol;
170
171 Distribution2DLinear(size_t nrows_,
172 const Teuchos::RCP<const Teuchos::Comm<int> > &comm_,
173 const Teuchos::ParameterList &params) :
174 Distribution2D<gno_t,scalar_t>(nrows_, comm_, params)
175 {
176 // Build vector describing distribution of vector entries across ranks
177 entries.assign(np+1, nrows / np);
178 int nExtraEntries = nrows % np;
179
180 // Distribute the extra entries evenly among processors.
181 // To evenly distribute them extra entries among processor rows and
182 // columns, we distribute them along diagonals of the matrix distribution.
183 // For our example, assume we have seven extra values (the max possible
184 // with np=8). Then we give one extra entry each to ranks
185 // [0, 3, 4, 7, 1, 2, 5]. For fewer extra entries, we follow the same
186 // order of assignment, and just stop early.
187
188 for (int cnt = 0, i = 0; (cnt < nExtraEntries) && (i < npRows); i++) {
189 for (int j = 0; (cnt < nExtraEntries) && (j < npCols); cnt++, j++) {
190 int rankForExtra = Distribution2D<gno_t,scalar_t>::TWODPRANK(i, j);
191 entries[rankForExtra+1]++; // Store in rankForExtra+1 to simplify
192 // prefix sum.
193 }
194 }
195
196 // Perform prefix sum of entries.
197 entries[0] = 0;
198 for (int i = 1; i <= np; i++)
199 entries[i] = entries[i-1] + entries[i];
200 // Now entries contains the first vector entry for each rank.
201
202 // Column map: Easy; consecutive entries for all ranks in column.
203 int firstRank = mypCol * npRows; // First rank in my column
204 myFirstCol = entries[firstRank];
205
206 gno_t nMyCols = 0;
207 for (int i = firstRank; i < firstRank + npRows; i++)
208 nMyCols += entries[i+1] - entries[i];
209 myLastCol = myFirstCol + nMyCols - 1;
210 }
211
212 inline enum DistributionType DistType() { return TwoDLinear; }
213
214 bool Mine(gno_t i, gno_t j) {
215 int idx = int(float(i) * float(np) / float(nrows));
216 while (i < entries[idx]) idx--;
217 while (i >= entries[idx+1]) idx++;
218 return ((mypRow == Distribution2D<gno_t,scalar_t>::TWODPROW(idx)) // RowMine
219 && (j >= myFirstCol && j <= myLastCol)); // ColMine
220 }
221 inline bool Mine(gno_t i, gno_t j, int p) {return Mine(i,j);}
222
223 inline bool VecMine(gno_t i) {
224 return(i >= entries[me] && i < entries[me+1]);
225 }
226
227
228private:
229 std::vector<gno_t> entries; // Describes vector entries' distribution to ranks
230 // Organized like vtxdist
231 gno_t myFirstCol; // First column owned by this rank
232 gno_t myLastCol; // Last column owned by this rank
233};
234
236template <typename gno_t, typename scalar_t>
237class Distribution2DRandom : public Distribution2D<gno_t,scalar_t> {
238
239public:
240 using Distribution<gno_t,scalar_t>::me;
241 using Distribution2D<gno_t,scalar_t>::mypRow;
242 using Distribution2D<gno_t,scalar_t>::mypCol;
243
244 Distribution2DRandom(size_t nrows_,
245 const Teuchos::RCP<const Teuchos::Comm<int> > &comm_,
246 const Teuchos::ParameterList &params) :
247 Distribution2D<gno_t,scalar_t>(nrows_, comm_, params)
248 { if (me == 0) std::cout << " randomize = true" << std::endl; }
249
250 inline enum DistributionType DistType() { return TwoDRandom; }
251
252 inline bool Mine(gno_t i, gno_t j) {
253 return ((mypRow == this->TWODPROW(this->HashToProc(i))) && // RowMine
254 (mypCol == this->TWODPCOL(this->HashToProc(j)))); // ColMine
255 }
256 inline bool Mine(gno_t i, gno_t j, int p) {return Mine(i,j);}
257
258 inline bool VecMine(gno_t i) { return (me == this->HashToProc(i)); }
259
260};
261
263
264template <typename gno_t, typename scalar_t>
265class Distribution2DVec : public Distribution2D<gno_t,scalar_t>
266{
267// Distribute non-zeros in a 2D manner based on the vector distribution
268// and the nprows x npcols configuration;
269// rows are assigned to same process owning the vector entry.
270public:
271 using Distribution<gno_t,scalar_t>::me;
272 using Distribution<gno_t,scalar_t>::np;
273 using Distribution<gno_t,scalar_t>::comm;
274 using Distribution<gno_t,scalar_t>::nrows;
275 using Distribution2D<gno_t,scalar_t>::npRows;
276 using Distribution2D<gno_t,scalar_t>::npCols;
277
278 Distribution2DVec(size_t nrows_,
279 const Teuchos::RCP<const Teuchos::Comm<int> > &comm_,
280 const Teuchos::ParameterList &params,
281 std::string &distributionfile) :
282 Distribution2D<gno_t,scalar_t>(nrows_, comm_, params)
283 {
284 if (me == 0) std::cout << "\n 2DVec Distribution: "
285 << "\n np = " << np << std::endl;
286 std::ifstream fpin;
287 if (me == 0) {
288 fpin.open(distributionfile.c_str(), std::ios::in);
289 if (!fpin.is_open()) {
290 std::cout << "Error: distributionfile " << distributionfile
291 << " not found" << std::endl;
292 exit(-1);
293 }
294 }
295
296 // Read the vector part assignment and broadcast it to all processes.
297 // Broadcast in chunks of bcastsize values.
298 // TODO: Make the vector part assignment more scalable instead of
299 // TODO: storing entire vector on every process.
300
301 vecpart = new int[nrows];
302
303 const int bcastsize = 1000000;
304
305 gno_t start = 0;
306 int cnt = 0;
307 for (size_t i = 0; i < nrows; i++) {
308 if (me == 0) fpin >> vecpart[i];
309 cnt++;
310 if (cnt == bcastsize || i == nrows-1) {
311 Teuchos::broadcast(*comm, 0, cnt, &(vecpart[start]));
312 start += cnt;
313 cnt = 0;
314 }
315 }
316
317 if (me == 0) fpin.close();
318 }
319
320 ~Distribution2DVec() {delete [] vecpart;}
321
322 inline enum DistributionType DistType() { return TwoDVec; }
323
324 bool Mine(gno_t i, gno_t j) {
325 return (me == (vecpart[i] % npRows + (vecpart[j] / npRows) * npRows));
326 }
327 inline bool Mine(gno_t i, gno_t j, int p) {return Mine(i,j);}
328
329 inline bool VecMine(gno_t i) { return(vecpart[i] == me); }
330
331private:
332 int *vecpart;
333
334};
335
336}
337#endif
Namespace Tpetra contains the class and methods constituting the Tpetra library.