1 //******************************************************************************
2 //
3 // File: SharedLongMatrix.java
4 // Package: edu.rit.pj.reduction
5 // Unit: Class edu.rit.pj.reduction.SharedLongMatrix
6 //
7 // This Java source file is copyright (C) 2010 by Alan Kaminsky. All rights
8 // reserved. For further information, contact the author, Alan Kaminsky, at
9 // ark@cs.rit.edu.
10 //
11 // This Java source file is part of the Parallel Java Library ("PJ"). PJ is free
12 // software; you can redistribute it and/or modify it under the terms of the GNU
13 // General Public License as published by the Free Software Foundation; either
14 // version 3 of the License, or (at your option) any later version.
15 //
16 // PJ is distributed in the hope that it will be useful, but WITHOUT ANY
17 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
18 // A PARTICULAR PURPOSE. See the GNU General Public License for more details.
19 //
20 // Linking this library statically or dynamically with other modules is making a
21 // combined work based on this library. Thus, the terms and conditions of the GNU
22 // General Public License cover the whole combination.
23 //
24 // As a special exception, the copyright holders of this library give you
25 // permission to link this library with independent modules to produce an
26 // executable, regardless of the license terms of these independent modules, and
27 // to copy and distribute the resulting executable under terms of your choice,
28 // provided that you also meet, for each linked independent module, the terms
29 // and conditions of the license of that module. An independent module is a module
30 // which is not derived from or based on this library. If you modify this library,
31 // you may extend this exception to your version of the library, but you are not
32 // obligated to do so. If you do not wish to do so, delete this exception
33 // statement from your version.
34 //
35 // A copy of the GNU General Public License is provided in the file gpl.txt. You
36 // may also obtain a copy of the GNU General Public License on the World Wide
37 // Web at http://www.gnu.org/licenses/gpl.html.
38 //
39 //******************************************************************************
40 package edu.rit.pj.reduction;
41
42 import java.util.concurrent.atomic.AtomicLongArray;
43
44 /**
45 * Class SharedLongMatrix provides a matrix reduction variable with elements of
46 * type <code>long</code>.
47 * <P>
48 * Class SharedLongMatrix is multiple thread safe. The methods use lock-free
49 * atomic compare-and-set.
50 * <P>
51 * <I>Note:</I> Class SharedLongMatrix is implemented using class
52 * java.util.concurrent.atomic.AtomicLongArray.
53 *
54 * @author Alan Kaminsky
55 * @version 12-Feb-2010
56 */
57 public class SharedLongMatrix {
58
59 // Hidden data members.
60 private AtomicLongArray[] myMatrix;
61
62 // Exported constructors.
63 /**
64 * Construct a new long matrix reduction variable with the given number of
65 * rows and columns. Each matrix element is initially 0.
66 *
67 * @param rows Number of rows.
68 * @param cols Number of columns.
69 * @exception NegativeArraySizeException (unchecked exception) Thrown if
70 * <code>rows</code> < 0 or <code>cols</code>
71 * < 0.
72 */
73 public SharedLongMatrix(int rows,
74 int cols) {
75 myMatrix = new AtomicLongArray[rows];
76 for (int r = 0; r < rows; ++r) {
77 myMatrix[r] = new AtomicLongArray(cols);
78 }
79 }
80
81 /**
82 * Construct a new long matrix reduction variable whose elements are copied
83 * from the given matrix. It is assumed that all rows of the
84 * <code>matrix</code> have the same number of columns.
85 *
86 * @param matrix Matrix to copy.
87 * @exception NullPointerException (unchecked exception) Thrown if
88 * <code>matrix</code> is null or any row of
89 * <code>matrix</code> is null.
90 */
91 public SharedLongMatrix(long[][] matrix) {
92 myMatrix = new AtomicLongArray[matrix.length];
93 for (int r = 0; r < matrix.length; ++r) {
94 myMatrix[r] = new AtomicLongArray(matrix[r]);
95 }
96 }
97
98 // Exported operations.
99 /**
100 * Returns the number of rows in this matrix reduction variable.
101 *
102 * @return Rows.
103 */
104 public int rows() {
105 return myMatrix.length;
106 }
107
108 /**
109 * Returns the number of columns in this matrix reduction variable.
110 *
111 * @return Columns.
112 */
113 public int cols() {
114 return myMatrix[0].length();
115 }
116
117 /**
118 * Returns this matrix reduction variable's current value at the given row
119 * and column.
120 *
121 * @param r Row index.
122 * @param c Column index.
123 * @return Current value.
124 */
125 public long get(int r,
126 int c) {
127 return myMatrix[r].get(c);
128 }
129
130 /**
131 * Set this matrix reduction variable at the given row and column to the
132 * given value.
133 *
134 * @param r Row index.
135 * @param c Column index.
136 * @param value New value.
137 */
138 public void set(int r,
139 int c,
140 long value) {
141 myMatrix[r].set(c, value);
142 }
143
144 /**
145 * Set this matrix reduction variable at the given row and column to the
146 * given value and return the previous value.
147 *
148 * @param r Row index.
149 * @param c Column index.
150 * @param value New value.
151 * @return Previous value.
152 */
153 public long getAndSet(int r,
154 int c,
155 long value) {
156 return myMatrix[r].getAndSet(c, value);
157 }
158
159 /**
160 * Atomically set this matrix reduction variable at the given row and column
161 * to the given updated value if the current value equals the expected
162 * value.
163 *
164 * @param r Row index.
165 * @param c Column index.
166 * @param expect Expected value.
167 * @param update Updated value.
168 * @return True if the update happened, false otherwise.
169 */
170 public boolean compareAndSet(int r,
171 int c,
172 long expect,
173 long update) {
174 return myMatrix[r].compareAndSet(c, expect, update);
175 }
176
177 /**
178 * Atomically set this matrix reduction variable at the given row and column
179 * to the given updated value if the current value equals the expected
180 * value. May fail spuriously.
181 *
182 * @param r Row index.
183 * @param c Column index.
184 * @param expect Expected value.
185 * @param update Updated value.
186 * @return True if the update happened, false otherwise.
187 */
188 @SuppressWarnings("deprecation")
189 public boolean weakCompareAndSet(int r,
190 int c,
191 long expect,
192 long update) {
193 return myMatrix[r].weakCompareAndSet(c, expect, update);
194 }
195
196 /**
197 * Add one to this matrix reduction variable at the given row and column and
198 * return the previous value.
199 *
200 * @param r Row index.
201 * @param c Column index.
202 * @return Previous value.
203 */
204 public long getAndIncrement(int r,
205 int c) {
206 return myMatrix[r].getAndIncrement(c);
207 }
208
209 /**
210 * Subtract one from this matrix reduction variable at the given row and
211 * column and return the previous value.
212 *
213 * @param r Row index.
214 * @param c Column index.
215 * @return Previous value.
216 */
217 public long getAndDecrement(int r,
218 int c) {
219 return myMatrix[r].getAndDecrement(c);
220 }
221
222 /**
223 * Add the given value to this matrix reduction variable at the given row
224 * and column and return the previous value.
225 *
226 * @param r Row index.
227 * @param c Column index.
228 * @param value Value to add.
229 * @return Previous value.
230 */
231 public long getAndAdd(int r,
232 int c,
233 long value) {
234 return myMatrix[r].getAndAdd(c, value);
235 }
236
237 /**
238 * Add one to this matrix reduction variable at the given row and column and
239 * return the new value.
240 *
241 * @param r Row index.
242 * @param c Column index.
243 * @return New value.
244 */
245 public long incrementAndGet(int r,
246 int c) {
247 return myMatrix[r].incrementAndGet(c);
248 }
249
250 /**
251 * Subtract one from this matrix reduction variable at the given row and
252 * column and return the new value.
253 *
254 * @param r Row index.
255 * @param c Column index.
256 * @return New value.
257 */
258 public long decrementAndGet(int r,
259 int c) {
260 return myMatrix[r].decrementAndGet(c);
261 }
262
263 /**
264 * Add the given value to this matrix reduction variable at the given row
265 * and column and return the new value.
266 *
267 * @param r Row index.
268 * @param c Column index.
269 * @param value Value to add.
270 * @return New value.
271 */
272 public long addAndGet(int r,
273 int c,
274 long value) {
275 return myMatrix[r].addAndGet(c, value);
276 }
277
278 /**
279 * Combine this matrix reduction variable at the given row and column with
280 * the given value using the given operation. (This matrix <code>[r,c]</code>)
281 * is set to (this matrix <code>[r,c]</code>) <I>op</I> (<code>value</code>), then
282 * (this matrix <code>[r,c]</code>) is returned.
283 *
284 * @param r Row index.
285 * @param c Column index.
286 * @param value Value.
287 * @param op Binary operation.
288 * @return (This matrix <code>[r,c]</code>) <I>op</I> (<code>value</code>).
289 */
290 public long reduce(int r,
291 int c,
292 long value,
293 LongOp op) {
294 AtomicLongArray myMatrix_r = myMatrix[r];
295 for (;;) {
296 long oldvalue = myMatrix_r.get(c);
297 long newvalue = op.op(oldvalue, value);
298 if (myMatrix_r.compareAndSet(c, oldvalue, newvalue)) {
299 return newvalue;
300 }
301 }
302 }
303
304 /**
305 * Combine this matrix reduction variable with the given matrix using the
306 * given operation. For every row <code>r</code> and column <code>c</code> in this
307 * matrix, (this matrix <code>[r,c]</code>) is set to (this matrix
308 * <code>[r,c]</code>) <I>op</I> (<code>src[r,c]</code>).
309 * <P>
310 * The <code>reduce()</code> method is multiple thread safe <I>on a per-element
311 * basis.</I> Each individual matrix element is updated atomically, but the
312 * matrix as a whole is not updated atomically.
313 *
314 * @param src Source matrix.
315 * @param op Binary operation.
316 * @exception NullPointerException (unchecked exception) Thrown if
317 * <code>src</code> is null. Thrown if
318 * <code>op</code> is null.
319 * @exception IndexOutOfBoundsException (unchecked exception) Thrown if any
320 * matrix index would be out of bounds.
321 */
322 public void reduce(long[][] src,
323 LongOp op) {
324 reduce(0, 0, src, 0, 0, rows(), cols(), op);
325 }
326
327 /**
328 * Combine a portion of this matrix reduction variable with a portion of the
329 * given matrix using the given operation. For each row index <code>r</code>
330 * from 0 to <code>rowlen-1</code> inclusive, and for each column index
331 * <code>c</code> from 0 to <code>collen-1</code> inclusive, (this matrix
332 * <code>[dstrow+r,dstcol+c]</code>) is set to (this matrix
333 * <code>[dstrow+r,dstcol+c]</code>) <I>op</I>
334 * (<code>src[srcrow+r,srccol+c]</code>).
335 * <P>
336 * The <code>reduce()</code> method is multiple thread safe <I>on a per-element
337 * basis.</I> Each individual matrix element is updated atomically, but the
338 * matrix as a whole is not updated atomically.
339 *
340 * @param dstrow Row index of first element to update in this matrix.
341 * @param dstcol Column index of first element to update in this matrix.
342 * @param src Source matrix.
343 * @param srcrow Row index of first element to update from in the source
344 * matrix.
345 * @param srccol Column index of first element to update from in the source
346 * matrix.
347 * @param rowlen Number of rows to update.
348 * @param collen Number of columns to update.
349 * @param op Binary operation.
350 * @exception NullPointerException (unchecked exception) Thrown if
351 * <code>src</code> is null. Thrown if
352 * <code>op</code> is null.
353 * @exception IndexOutOfBoundsException (unchecked exception) Thrown if
354 * <code>rowlen</code> < 0. Thrown if
355 * <code>collen</code> < 0. Thrown if any matrix index would be out of
356 * bounds.
357 */
358 public void reduce(int dstrow,
359 int dstcol,
360 long[][] src,
361 int srcrow,
362 int srccol,
363 int rowlen,
364 int collen,
365 LongOp op) {
366 if (rowlen < 0
367 || collen < 0
368 || dstrow < 0 || dstrow + rowlen > rows()
369 || dstcol < 0 || dstcol + collen > cols()
370 || srcrow < 0 || srcrow + rowlen > src.length
371 || srccol < 0 || srccol + collen > src[0].length) {
372 throw new IndexOutOfBoundsException();
373 }
374
375 for (int r = 0; r < rowlen; ++r) {
376 AtomicLongArray myMatrix_r = myMatrix[dstrow + r];
377 long[] src_r = src[srcrow + r];
378 for (int c = 0; c < collen; ++c) {
379 int dstcol_c = dstcol + c;
380 long src_r_c = src_r[srccol + c];
381 updateLoop:
382 for (;;) {
383 long oldvalue = myMatrix_r.get(dstcol_c);
384 long newvalue = op.op(oldvalue, src_r_c);
385 if (myMatrix_r.compareAndSet(dstcol_c, oldvalue, newvalue)) {
386 break updateLoop;
387 }
388 }
389 }
390 }
391 }
392
393 }