1 //******************************************************************************
2 //
3 // File: IntegerStrideForLoop.java
4 // Package: edu.rit.pj
5 // Unit: Class edu.rit.pj.IntegerStrideForLoop
6 //
7 // This Java source file is copyright (C) 2007 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;
41
42 /**
43 * Class IntegerStrideForLoop is the abstract base class for one variation of a
44 * parallel for loop that is executed inside a {@linkplain ParallelRegion}. The
45 * loop index data type is <code>int</code>. The loop stride is explicitly
46 * specified.
47 * <P>
48 * To execute a parallel for loop, create a {@linkplain ParallelRegion} object;
49 * create an instance of a concrete subclass of class IntegerStrideForLoop; and
50 * pass this instance to the parallel region's <code>execute()</code> method. Either
51 * every parallel team thread must call the parallel region's <code>execute()</code>
52 * method with identical arguments, or every thread must not call the
53 * <code>execute()</code> method. You can do all this using an anonymous inner
54 * class; for example:
55 * <PRE>
56 * new ParallelRegion()
57 * {
58 * . . .
59 * public void run()
60 * {
61 * . . .
62 * execute (0, 98, 2, new IntegerStrideForLoop()
63 * {
64 * // Thread local variable declarations
65 * . . .
66 * public void start()
67 * {
68 * // Per-thread pre-loop initialization code
69 * . . .
70 * }
71 * public void run (int first, int last, int stride)
72 * {
73 * // Loop code
74 * . . .
75 * }
76 * public void finish()
77 * {
78 * // Per-thread post-loop finalization code
79 * . . .
80 * }
81 * });
82 * }
83 * . . .
84 * }
85 * </PRE>
86 * <P>
87 * The parallel region's <code>execute()</code> method does the following. Each
88 * parallel team thread calls the parallel for loop's <code>start()</code> method
89 * once before beginning any loop iterations. The range of loop indexes is
90 * divided into "chunks" and the chunks are apportioned among the threads, in a
91 * manner determined by the parallel for loop's schedule as returned by the
92 * <code>schedule()</code> method. Each thread repeatedly calls the parallel for
93 * loop's <code>run()</code> method, passing in a different chunk on each call,
94 * until all the chunks assigned to that thread have been performed. When a
95 * thread has finished calling <code>run()</code>, the thread calls the parallel for
96 * loop's <code>finish()</code> method. Then the thread waits at an implicit
97 * barrier. When all the threads have reached the barrier, the
98 * <code>execute()</code> method returns.
99 * <P>
100 * Note that each parallel team thread actually creates its own instance of the
101 * parallel for loop class and passes that instance to the parallel region's
102 * <code>execute()</code> method. Thus, any fields declared in the parallel for loop
103 * class will <I>not</I> be shared by all the threads, but instead will be
104 * private to each thread.
105 * <P>
106 * The <code>start()</code> method is intended for performing per-thread
107 * initialization before starting the loop iterations. If no such initialization
108 * is needed, omit the <code>start()</code> method.
109 * <P>
110 * The <code>run()</code> method contains the code for the loop. The first and last
111 * indexes for a chunk of loop iterations are passed in as arguments. The loop
112 * stride, which is always positive, is also explicitly specified as an
113 * argument. The parallel for loop's <code>run()</code> method must be coded this
114 * way:
115 * <PRE>
116 * public void run (int first, int last, int stride)
117 * {
118 * for (int i = first; i <= last; i += stride)
119 * {
120 * // Loop body code
121 * . . .
122 * }
123 * }
124 * </PRE> with the loop indexes running from <code>first</code> to <code>last</code>
125 * inclusive and increasing by <code>stride</code> on each iteration.
126 * <P>
127 * The <code>finish()</code> method is intended for performing per-thread
128 * finalization after finishing the loop iterations. If no such finalization is
129 * needed, omit the <code>finish()</code> method.
130 * <P>
131 * Sometimes a portion of a parallel for loop has to be executed sequentially in
132 * the order of the loop indexes, while the rest of the parallel for loop can be
133 * executed concurrently. For example, the loop body is performing some
134 * computation that can be executed in parallel for different loop indexes, but
135 * the results of each computation must be written to a file sequentially in the
136 * order of the loop indexes. The <code>ordered()</code> method is provided for this
137 * purpose. A call to the <code>ordered()</code> method may appear once in the
138 * parallel for loop's <code>run()</code> method, like so:
139 * <PRE>
140 * public void run (int first, int last, int stride)
141 * {
142 * for (int i = first; i <= last; i += stride)
143 * {
144 * // This portion executed concurrently
145 * . . .
146 * ordered (new ParallelSection()
147 * {
148 * public void run()
149 * {
150 * // This portion executed sequentially
151 * // in the order of the loop indexes
152 * . . .
153 * }
154 * });
155 * // This portion executed concurrently again
156 * . . .
157 * }
158 * }
159 * </PRE> When called, the <code>ordered()</code> method waits until the
160 * <code>ordered()</code>
161 * method has been called and has returned in all loop iterations prior to the
162 * current loop iteration. Then the <code>ordered()</code> method calls the given
163 * parallel section's <code>run()</code> method. When the parallel section's
164 * <code>run()</code> method returns, the <code>ordered()</code> method returns. If the
165 * parallel section's <code>run()</code> method throws an exception, the
166 * <code>ordered()</code> method throws that same exception.
167 * <P>
168 * It is possible to stop a parallel for loop using the <code>stopLoop()</code>
169 * method, like this:
170 * <PRE>
171 * public void run (int first, int last, int stride)
172 * {
173 * for (int i = first; i <= last; i += stride)
174 * {
175 * // Loop body
176 * . . .
177 * if (/*time to stop the loop*/)
178 * {
179 * stopLoop();
180 * break;
181 * }
182 * // More loop body
183 * . . .
184 * }
185 * }
186 * </PRE> Once <code>stopLoop()</code> is called, after each parallel team thread
187 * finishes executing its current chunk of iterations, each thread will execute
188 * no further chunks and will proceed to finish the parallel for loop. Note well
189 * that stopping a parallel for loop is not the same as executing a
190 * <code>break</code> statement in a regular for loop. The parallel for loop does
191 * not stop until each thread, <I>including the thread that called
192 * <code>stopLoop()</code></I>, has finished its current <I>chunk</I> of iterations.
193 * Thus, depending on the parallel for loop's schedule, additional iterations
194 * may be executed after <code>stopLoop()</code> is called. (The <code>break</code>
195 * statement in the above example causes the thread that called
196 * <code>stopLoop()</code> to finish its chunk of iterations early.)
197 * <P>
198 * Normally, at the end of the parallel for loop, the parallel team threads wait
199 * for each other at a barrier. To eliminate this barrier wait, include
200 * {@link edu.rit.pj.BarrierAction#NO_WAIT BarrierAction.NO_WAIT} in the <code>execute()</code>
201 * method call:
202 * <PRE>
203 * new ParallelRegion()
204 * {
205 * . . .
206 * public void run()
207 * {
208 * . . .
209 * execute (0, 98, 2, new IntegerStrideForLoop()
210 * {
211 * . . .
212 * },
213 * BarrierAction.NO_WAIT);
214 * . . .
215 * }
216 * }
217 * </PRE> To execute a section of code in a single thread as part of the barrier
218 * synchronization, include an instance of class {@linkplain BarrierAction} in
219 * the <code>execute()</code> method call. The barrier action object's
220 * <code>run()</code> method contains the code to be executed in a single thread
221 * while the other threads wait:
222 * <PRE>
223 * new ParallelRegion()
224 * {
225 * . . .
226 * public void run()
227 * {
228 * . . .
229 * execute (0, 98, 2, new IntegerStrideForLoop()
230 * {
231 * . . .
232 * },
233 * new BarrierAction()
234 * {
235 * public void run()
236 * {
237 * // Single-threaded code goes here
238 * . . .
239 * }
240 * });
241 * . . .
242 * }
243 * }
244 * </PRE> For further information, see class {@linkplain BarrierAction}.
245 * <P>
246 * If the parallel for loop's <code>start()</code>, <code>run()</code>, or
247 * <code>finish()</code> method throws an exception in one of the threads, then that
248 * thread executes no further code in the loop, and the parallel region's
249 * <code>execute()</code> method throws that same exception in that thread.
250 * Furthermore, the other threads in the parallel team also execute no further
251 * code in the loop after finishing their current chunks. Thus, if one thread
252 * throws an exception, the whole parallel for loop exits with some (perhaps
253 * none) of the iterations unperformed.
254 *
255 * @author Alan Kaminsky
256 * @version 11-Nov-2007
257 */
258 public abstract class IntegerStrideForLoop
259 extends ParallelForLoop {
260
261 // Hidden data members.
262 // Parallel for loop schedule.
263 IntegerSchedule mySchedule;
264
265 // Loop index and stride for ordered() construct.
266 int myOrderedIndex;
267 int myStride;
268
269 // Exported constructors.
270 /**
271 * Construct a new parallel for loop.
272 */
273 public IntegerStrideForLoop() {
274 super();
275 }
276
277 // Exported operations.
278 /**
279 * Determine this parallel for loop's schedule. The schedule determines how
280 * the loop iterations are apportioned among the parallel team threads. For
281 * further information, see class {@linkplain IntegerSchedule}.
282 * <P>
283 * The <code>schedule()</code> method may be overridden in a subclass to return
284 * the desired schedule. If not overridden, the default is a runtime
285 * schedule (see {@link edu.rit.pj.IntegerSchedule#runtime()}).
286 *
287 * @return Schedule for this parallel for loop.
288 */
289 public IntegerSchedule schedule() {
290 return IntegerSchedule.runtime();
291 }
292
293 /**
294 * Perform per-thread initialization actions before starting the loop
295 * iterations.
296 * <P>
297 * The <code>start()</code> method may be overridden in a subclass. If not
298 * overridden, the <code>start()</code> method does nothing.
299 *
300 * @exception Exception The <code>start()</code> method may throw any exception.
301 * @throws java.lang.Exception if any.
302 */
303 public void start()
304 throws Exception {
305 }
306
307 /**
308 * Execute one chunk of iterations of this parallel for loop. The
309 * <code>run()</code> method must perform the loop body for indexes
310 * <code>first</code> through <code>last</code> inclusive, increasing the loop index
311 * by <code>stride</code> after each iteration.
312 * <P>
313 * The <code>run()</code> method must be overridden in a subclass.
314 *
315 * @param first First loop index.
316 * @param last Last loop index.
317 * @param stride Loop index stride, always positive.
318 * @exception Exception The <code>run()</code> method may throw any exception.
319 * @throws java.lang.Exception if any.
320 */
321 public abstract void run(int first,
322 int last,
323 int stride)
324 throws Exception;
325
326 /**
327 * Perform per-thread finalization actions after finishing the loop
328 * iterations.
329 * <P>
330 * The <code>finish()</code> method may be overridden in a subclass. If not
331 * overridden, the <code>finish()</code> method does nothing.
332 *
333 * @exception Exception The <code>finish()</code> method may throw any
334 * exception.
335 * @throws java.lang.Exception if any.
336 */
337 public void finish()
338 throws Exception {
339 }
340
341 /**
342 * Execute the given section of code in order of the loop indexes. A call to
343 * the <code>ordered()</code> method may appear in this parallel for loop's
344 * <code>run()</code> method. When called, the <code>ordered()</code> method waits
345 * until the <code>ordered()</code> method has been called and has returned in
346 * all loop iterations prior to the current loop iteration. Then the
347 * <code>ordered()</code> method calls the <code>run()</code> method of
348 * <code>theParallelSection</code>. When the parallel section's <code>run()</code>
349 * method returns, the <code>ordered()</code> method returns. If the parallel
350 * section's <code>run()</code> method throws an exception, the
351 * <code>ordered()</code> method throws that same exception.
352 * <P>
353 * The <code>ordered()</code> method is used when a portion of a parallel for
354 * loop has to be executed sequentially in the order of the loop indexes,
355 * while the rest of the parallel for loop can be executed concurrently.
356 * <P>
357 * <I>Note:</I> Either the <code>ordered()</code> method must be called exactly
358 * once during each call of the parallel for loop's <code>run()</code> method,
359 * or the <code>ordered()</code> method must not be called at all.
360 *
361 * @param theSection Parallel section to execute in order.
362 * @exception NullPointerException (unchecked exception) Thrown if
363 * <code>theSection</code> is null.
364 * @exception IllegalStateException (unchecked exception) Thrown if no
365 * parallel team is executing this parallel for loop.
366 * @exception Exception Thrown if <code>theSection</code>'s <code>run()</code>
367 * method throws an exception.
368 * @throws java.lang.Exception if any.
369 */
370 public final void ordered(ParallelSection theSection)
371 throws Exception {
372 // Verify preconditions.
373 if (theSection == null) {
374 throw new IllegalStateException("IntegerStrideForLoop.ordered(): Parallel section is null");
375 }
376 if (myTeam == null) {
377 throw new IllegalStateException("IntegerStrideForLoop.ordered(): No parallel team executing");
378 }
379
380 // Wait until the ordered() construct has finished for all previous
381 // iterations.
382 if (mySchedule.myOrderedIndex != this.myOrderedIndex) {
383 Spinner spinner = new Spinner();
384 while (mySchedule.myOrderedIndex != this.myOrderedIndex) {
385 spinner.spin();
386 }
387 }
388
389 // Execute parallel section. Propagate any exception.
390 theSection.myTeam = this.myTeam;
391 try {
392 theSection.run();
393 } finally {
394 theSection.myTeam = null;
395
396 // Notify that the ordered construct has finished for this
397 // iteration.
398 this.myOrderedIndex += this.myStride;
399 mySchedule.myOrderedIndex = this.myOrderedIndex;
400 }
401 }
402
403 /**
404 * Stop this parallel for loop. Once <code>stopLoop()</code> is called, after
405 * each parallel team thread finishes executing its current chunk of
406 * iterations, each thread will execute no further chunks and will proceed
407 * to finish this parallel for loop.
408 *
409 * @exception IllegalStateException (unchecked exception) Thrown if no
410 * parallel team is executing this parallel for loop.
411 */
412 public final void stopLoop() {
413 if (myTeam == null) {
414 throw new IllegalStateException("ParallelForLoop.stopLoop(): No parallel team executing");
415 }
416 mySchedule.myBreak = true;
417 }
418
419 // Hidden operations.
420 /**
421 * Execute one chunk of iterations of this parallel for loop. This method
422 * performs common processing, then calls the <code>run()</code> method.
423 *
424 * @param first First loop index.
425 * @param last Last loop index.
426 * @param stride Loop index stride, always positive.
427 *
428 * @exception Exception This method may throw any exception.
429 */
430 void commonRun(int first,
431 int last,
432 int stride)
433 throws Exception {
434 myOrderedIndex = first;
435 myStride = stride;
436 run(first, last, stride);
437 }
438
439 // Kludge to avert false sharing in multithreaded programs.
440 // Padding fields.
441 volatile long p0 = 1000L;
442 volatile long p1 = 1001L;
443 volatile long p2 = 1002L;
444 volatile long p3 = 1003L;
445 volatile long p4 = 1004L;
446 volatile long p5 = 1005L;
447 volatile long p6 = 1006L;
448 volatile long p7 = 1007L;
449 volatile long p8 = 1008L;
450 volatile long p9 = 1009L;
451 volatile long pa = 1010L;
452 volatile long pb = 1011L;
453 volatile long pc = 1012L;
454 volatile long pd = 1013L;
455 volatile long pe = 1014L;
456 volatile long pf = 1015L;
457
458 // Method to prevent the JDK from optimizing away the padding fields.
459 long preventOptimization() {
460 return p0 + p1 + p2 + p3 + p4 + p5 + p6 + p7 +
461 p8 + p9 + pa + pb + pc + pd + pe + pf;
462 }
463
464 }