//******************************************************************************
//
// File: IntegerStrideForLoop.java
// Package: edu.rit.pj
// Unit: Class edu.rit.pj.IntegerStrideForLoop
//
// This Java source file is copyright (C) 2007 by Alan Kaminsky. All rights
// reserved. For further information, contact the author, Alan Kaminsky, at
// ark@cs.rit.edu.
//
// This Java source file is part of the Parallel Java Library ("PJ"). PJ is free
// software; you can redistribute it and/or modify it under the terms of the GNU
// General Public License as published by the Free Software Foundation; either
// version 3 of the License, or (at your option) any later version.
//
// PJ is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
// A PARTICULAR PURPOSE. See the GNU General Public License for more details.
//
// A copy of the GNU General Public License is provided in the file gpl.txt. You
// may also obtain a copy of the GNU General Public License on the World Wide
// Web at http://www.gnu.org/licenses/gpl.html.
//
//******************************************************************************
package edu.rit.pj;
/**
* Class IntegerStrideForLoop is the abstract base class for one variation of a
* parallel for loop that is executed inside a {@linkplain ParallelRegion}. The
* loop index data type is int. The loop stride is explicitly
* specified.
*
* To execute a parallel for loop, create a {@linkplain ParallelRegion} object;
* create an instance of a concrete subclass of class IntegerStrideForLoop; and
* pass this instance to the parallel region's execute() method. Either
* every parallel team thread must call the parallel region's execute()
* method with identical arguments, or every thread must not call the
* execute() method. You can do all this using an anonymous inner
* class; for example:
*
* new ParallelRegion()
* {
* . . .
* public void run()
* {
* . . .
* execute (0, 98, 2, new IntegerStrideForLoop()
* {
* // Thread local variable declarations
* . . .
* public void start()
* {
* // Per-thread pre-loop initialization code
* . . .
* }
* public void run (int first, int last, int stride)
* {
* // Loop code
* . . .
* }
* public void finish()
* {
* // Per-thread post-loop finalization code
* . . .
* }
* });
* }
* . . .
* }
*
*
* The parallel region's execute() method does the following. Each
* parallel team thread calls the parallel for loop's start() method
* once before beginning any loop iterations. The range of loop indexes is
* divided into "chunks" and the chunks are apportioned among the threads, in a
* manner determined by the parallel for loop's schedule as returned by the
* schedule() method. Each thread repeatedly calls the parallel for
* loop's run() method, passing in a different chunk on each call,
* until all the chunks assigned to that thread have been performed. When a
* thread has finished calling run(), the thread calls the parallel for
* loop's finish() method. Then the thread waits at an implicit
* barrier. When all the threads have reached the barrier, the
* execute() method returns.
*
* Note that each parallel team thread actually creates its own instance of the
* parallel for loop class and passes that instance to the parallel region's
* execute() method. Thus, any fields declared in the parallel for loop
* class will not be shared by all the threads, but instead will be
* private to each thread.
*
* The start() method is intended for performing per-thread
* initialization before starting the loop iterations. If no such initialization
* is needed, omit the start() method.
*
* The run() method contains the code for the loop. The first and last
* indexes for a chunk of loop iterations are passed in as arguments. The loop
* stride, which is always positive, is also explicitly specified as an
* argument. The parallel for loop's run() method must be coded this
* way:
*
* public void run (int first, int last, int stride)
* {
* for (int i = first; i <= last; i += stride)
* {
* // Loop body code
* . . .
* }
* }
*
* with the loop indexes running from first to last inclusive
* and increasing by stride on each iteration.
*
* The finish() method is intended for performing per-thread
* finalization after finishing the loop iterations. If no such finalization is
* needed, omit the finish() method.
*
* Sometimes a portion of a parallel for loop has to be executed sequentially in
* the order of the loop indexes, while the rest of the parallel for loop can be
* executed concurrently. For example, the loop body is performing some
* computation that can be executed in parallel for different loop indexes, but
* the results of each computation must be written to a file sequentially in the
* order of the loop indexes. The ordered() method is provided for this
* purpose. A call to the ordered() method may appear once in the
* parallel for loop's run() method, like so:
*
* public void run (int first, int last, int stride)
* {
* for (int i = first; i <= last; i += stride)
* {
* // This portion executed concurrently
* . . .
* ordered (new ParallelSection()
* {
* public void run()
* {
* // This portion executed sequentially
* // in the order of the loop indexes
* . . .
* }
* });
* // This portion executed concurrently again
* . . .
* }
* }
*
* When called, the ordered() method waits until the ordered()
* method has been called and has returned in all loop iterations prior to the
* current loop iteration. Then the ordered() method calls the given
* parallel section's run() method. When the parallel section's
* run() method returns, the ordered() method returns. If the
* parallel section's run() method throws an exception, the
* ordered() method throws that same exception.
*
* It is possible to stop a parallel for loop using the stopLoop()
* method, like this:
*
* public void run (int first, int last, int stride)
* {
* for (int i = first; i <= last; i += stride)
* {
* // Loop body
* . . .
* if (/*time to stop the loop*/)
* {
* stopLoop();
* break;
* }
* // More loop body
* . . .
* }
* }
*
* Once stopLoop() is called, after each parallel team thread finishes
* executing its current chunk of iterations, each thread will execute no
* further chunks and will proceed to finish the parallel for loop. Note well
* that stopping a parallel for loop is not the same as executing a
* break statement in a regular for loop. The parallel for loop does
* not stop until each thread, including the thread that called
* stopLoop(), has finished its current chunk of iterations.
* Thus, depending on the parallel for loop's schedule, additional iterations
* may be executed after stopLoop() is called. (The break
* statement in the above example causes the thread that called
* stopLoop() to finish its chunk of iterations early.)
*
* Normally, at the end of the parallel for loop, the parallel team threads
* wait for each other at a barrier. To eliminate this barrier wait, include
* {@link BarrierAction#NO_WAIT BarrierAction.NO_WAIT} in the execute()
* method call:
*
* new ParallelRegion()
* {
* . . .
* public void run()
* {
* . . .
* execute (0, 98, 2, new IntegerStrideForLoop()
* {
* . . .
* },
* BarrierAction.NO_WAIT);
* . . .
* }
* }
*
* To execute a section of code in a single thread as part of the barrier
* synchronization, include an instance of class {@linkplain BarrierAction} in
* the execute() method call. The barrier action object's
* run() method contains the code to be executed in a single thread
* while the other threads wait:
*
* new ParallelRegion()
* {
* . . .
* public void run()
* {
* . . .
* execute (0, 98, 2, new IntegerStrideForLoop()
* {
* . . .
* },
* new BarrierAction()
* {
* public void run()
* {
* // Single-threaded code goes here
* . . .
* }
* });
* . . .
* }
* }
*
* For further information, see class {@linkplain BarrierAction}.
*
* If the parallel for loop's start(), run(), or
* finish() method throws an exception in one of the threads, then that
* thread executes no further code in the loop, and the parallel region's
* execute() method throws that same exception in that thread.
* Furthermore, the other threads in the parallel team also execute no further
* code in the loop after finishing their current chunks. Thus, if one thread
* throws an exception, the whole parallel for loop exits with some (perhaps
* none) of the iterations unperformed.
*
* @author Alan Kaminsky
* @version 11-Nov-2007
*/
public abstract class IntegerStrideForLoop
extends ParallelForLoop
{
// Hidden data members.
// Parallel for loop schedule.
IntegerSchedule mySchedule;
// Loop index and stride for ordered() construct.
int myOrderedIndex;
int myStride;
// Exported constructors.
/**
* Construct a new parallel for loop.
*/
public IntegerStrideForLoop()
{
super();
}
// Exported operations.
/**
* Determine this parallel for loop's schedule. The schedule determines how
* the loop iterations are apportioned among the parallel team threads. For
* further information, see class {@linkplain IntegerSchedule}.
*
* The schedule() method may be overridden in a subclass to return
* the desired schedule. If not overridden, the default is a runtime
* schedule (see {@link IntegerSchedule#runtime()}).
*
* @return Schedule for this parallel for loop.
*/
public IntegerSchedule schedule()
{
return IntegerSchedule.runtime();
}
/**
* Perform per-thread initialization actions before starting the loop
* iterations.
*
* The start() method may be overridden in a subclass. If not
* overridden, the start() method does nothing.
*
* @exception Exception
* The start() method may throw any exception.
*/
public void start()
throws Exception
{
}
/**
* Execute one chunk of iterations of this parallel for loop. The
* run() method must perform the loop body for indexes
* first through last inclusive, increasing the loop index
* by stride after each iteration.
*
* The run() method must be overridden in a subclass.
*
* @param first First loop index.
* @param last Last loop index.
* @param stride Loop index stride, always positive.
*
* @exception Exception
* The run() method may throw any exception.
*/
public abstract void run
(int first,
int last,
int stride)
throws Exception;
/**
* Perform per-thread finalization actions after finishing the loop
* iterations.
*
* The finish() method may be overridden in a subclass. If not
* overridden, the finish() method does nothing.
*
* @exception Exception
* The finish() method may throw any exception.
*/
public void finish()
throws Exception
{
}
/**
* Execute the given section of code in order of the loop indexes. A call to
* the ordered() method may appear in this parallel for loop's
* run() method. When called, the ordered() method waits
* until the ordered() method has been called and has returned in
* all loop iterations prior to the current loop iteration. Then the
* ordered() method calls the run() method of
* theParallelSection. When the parallel section's run()
* method returns, the ordered() method returns. If the parallel
* section's run() method throws an exception, the
* ordered() method throws that same exception.
*
* The ordered() method is used when a portion of a parallel for
* loop has to be executed sequentially in the order of the loop indexes,
* while the rest of the parallel for loop can be executed concurrently.
*
* Note: Either the ordered() method must be called exactly
* once during each call of the parallel for loop's run() method,
* or the ordered() method must not be called at all.
*
* @param theSection Parallel section to execute in order.
*
* @exception NullPointerException
* (unchecked exception) Thrown if theSection is null.
* @exception IllegalStateException
* (unchecked exception) Thrown if no parallel team is executing this
* parallel for loop.
* @exception Exception
* Thrown if theSection's run() method throws an
* exception.
*/
public final void ordered
(ParallelSection theSection)
throws Exception
{
// Verify preconditions.
if (theSection == null)
{
throw new IllegalStateException
("IntegerStrideForLoop.ordered(): Parallel section is null");
}
if (myTeam == null)
{
throw new IllegalStateException
("IntegerStrideForLoop.ordered(): No parallel team executing");
}
// Wait until the ordered() construct has finished for all previous
// iterations.
if (mySchedule.myOrderedIndex != this.myOrderedIndex)
{
Spinner spinner = new Spinner();
while (mySchedule.myOrderedIndex != this.myOrderedIndex)
{
spinner.spin();
}
}
// Execute parallel section. Propagate any exception.
theSection.myTeam = this.myTeam;
try
{
theSection.run();
}
finally
{
theSection.myTeam = null;
// Notify that the ordered construct has finished for this
// iteration.
this.myOrderedIndex += this.myStride;
mySchedule.myOrderedIndex = this.myOrderedIndex;
}
}
/**
* Stop this parallel for loop. Once stopLoop() is called, after
* each parallel team thread finishes executing its current chunk of
* iterations, each thread will execute no further chunks and will proceed
* to finish this parallel for loop.
*
* @exception IllegalStateException
* (unchecked exception) Thrown if no parallel team is executing this
* parallel for loop.
*/
public final void stopLoop()
{
if (myTeam == null)
{
throw new IllegalStateException
("ParallelForLoop.stopLoop(): No parallel team executing");
}
mySchedule.myBreak = true;
}
// Hidden operations.
/**
* Execute one chunk of iterations of this parallel for loop. This method
* performs common processing, then calls the run() method.
*
* @param first First loop index.
* @param last Last loop index.
* @param stride Loop index stride, always positive.
*
* @exception Exception
* This method may throw any exception.
*/
void commonRun
(int first,
int last,
int stride)
throws Exception
{
myOrderedIndex = first;
myStride = stride;
run (first, last, stride);
}
}
Ads help maintain this website.