ParallelIteration

//******************************************************************************
//
// File:    ParallelIteration.java
// Package: edu.rit.pj
// Unit:    Class edu.rit.pj.ParallelIteration
//
// 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.
//
// Linking this library statically or dynamically with other modules is making a
// combined work based on this library. Thus, the terms and conditions of the GNU
// General Public License cover the whole combination.
//
// As a special exception, the copyright holders of this library give you
// permission to link this library with independent modules to produce an
// executable, regardless of the license terms of these independent modules, and
// to copy and distribute the resulting executable under terms of your choice,
// provided that you also meet, for each linked independent module, the terms
// and conditions of the license of that module. An independent module is a module
// which is not derived from or based on this library. If you modify this library,
// you may extend this exception to your version of the library, but you are not
// obligated to do so. If you do not wish to do so, delete this exception
// statement from your version.
//
// 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 ParallelIteration is the abstract base class for a parallel iteration
 * that is executed inside a {@linkplain ParallelRegion}. The parallel iteration
 * lets you iterate over a group of items, with a separate parallel team thread
 * processing each item. The generic type parameter T specifies the items' data
 * type. The items can be the elements of an array, the items obtained from an
 * {@linkplain java.util.Iterator Iterator}, or the items contained in an
 * {@linkplain java.lang.Iterable Iterable} collection.
 * <P>
 * To execute a parallel iteration, create a {@linkplain ParallelRegion} object;
 * create an instance of a concrete subclass of class ParallelIteration; and
 * pass this instance to the parallel region's <code>execute()</code> method. Either
 * every parallel team thread must call the parallel region's <code>execute()</code>
 * method with identical arguments, or every thread must not call the
 * <code>execute()</code> method. You can do all this using an anonymous inner
 * class; for example:
 * <PRE>
 *     new ParallelRegion()
 *         {
 *         ArrayList&lt;String&gt; list = new ArrayList&lt;String&gt;();
 *         . . .
 *         public void run()
 *             {
 *             . . .
 *             execute (list, new ParallelIteration&lt;String&gt;()
 *                 {
 *                 // Thread local variable declarations
 *                 . . .
 *                 public void start()
 *                     {
 *                     // Per-thread pre-loop initialization code
 *                     . . .
 *                     }
 *                 public void run (String item)
 *                     {
 *                     // Loop body code
 *                     . . .
 *                     }
 *                 public void finish()
 *                     {
 *                     // Per-thread post-loop finalization code
 *                     . . .
 *                     }
 *                 });
 *             }
 *         . . .
 *         }
 * </PRE>
 * <P>
 * The parallel region's <code>execute()</code> method does the following. One of
 * the parallel team threads sets up the source of the items to be iterated over
 * -- either an array's elements, an iterator's items, or an iterable
 * collection's contents. (Note that only <I>one</I> thread does this setup; but
 * because all threads must call the parallel region's <code>execute()</code> method
 * with identical arguments, it doesn't matter which thread does the setup.)
 * Each parallel team thread calls the parallel iteration's <code>start()</code>
 * method once before beginning any loop iterations. Each thread repeatedly
 * calls the parallel iteration's <code>run()</code> method, passing in a different
 * item on each call, until all the items have been processed. When a thread has
 * finished calling <code>run()</code>, the thread calls the parallel iteration's
 * <code>finish()</code> method. Then the thread waits at a barrier. When all the
 * threads have reached the barrier, the <code>execute()</code> method returns.
 * <P>
 * Note that each parallel team thread actually creates its own instance of the
 * parallel iteration class and passes that instance to the parallel region's
 * <code>execute()</code> method. Thus, any fields declared in the parallel
 * iteration class will <I>not</I> be shared by all the threads, but instead
 * will be private to each thread.
 * <P>
 * The <code>start()</code> method is intended for performing per-thread
 * initialization before starting the loop iterations. If no such initialization
 * is needed, omit the <code>start()</code> method.
 * <P>
 * The <code>run()</code> method contains the code for the loop body. It does
 * whatever processing is needed on the one item passed in as an argument. Note
 * that, unlike a parallel for loop (class {@linkplain ParallelForLoop}), a
 * parallel iteration is not "chunked;" each parallel team thread always
 * processes just one item at a time.
 * <P>
 * The <code>finish()</code> method is intended for performing per-thread
 * finalization after finishing the loop iterations. If no such finalization is
 * needed, omit the <code>finish()</code> method.
 * <P>
 * Sometimes a portion of a parallel iteration has to be executed sequentially
 * in the same order as the items' iteration order, while the rest of the
 * parallel iteration can be executed concurrently. For example, the loop body
 * is performing some computation that can be executed in parallel for different
 * items, but the results of each computation must be written to a file
 * sequentially in the items' iteration order. The <code>ordered()</code> method is
 * provided for this purpose. A call to the <code>ordered()</code> method may appear
 * once in the parallel iteration's <code>run()</code> method, like so:
 * <PRE>
 *     public void run (String item)
 *         {
 *         // This portion executed concurrently
 *         . . .
 *         ordered (new ParallelSection()
 *             {
 *             public void run()
 *                 {
 *                 // This portion executed sequentially
 *                 // in the items' iteration order
 *                 . . .
 *                 }
 *             });
 *         // This portion executed concurrently again
 *         . . .
 *         }
 * </PRE> When called, the <code>ordered()</code> method waits until the
 * <code>ordered()</code>
 * method has been called and has returned for all items prior to the current
 * item. Then the <code>ordered()</code> method calls the given parallel section's
 * <code>run()</code> method. When the parallel section's <code>run()</code> method
 * returns, the <code>ordered()</code> method returns. If the parallel section's
 * <code>run()</code> method throws an exception, the <code>ordered()</code> method
 * throws that same exception.
 * <P>
 * It is possible to stop a parallel iteration using the <code>stopLoop()</code>
 * method, like this:
 * <PRE>
 *     public void run (String item)
 *         {
 *         // Loop body
 *         . . .
 *         if (/&#42;time to stop the loop&#42;/)
 *             {
 *             stopLoop();
 *             return;
 *             }
 *         // More loop body
 *         . . .
 *         }
 * </PRE> Once <code>stopLoop()</code> is called, after each parallel team thread
 * finishes processing its current item, each thread will process no further
 * items and will proceed to finish the parallel iteration. Note well that
 * stopping a parallel iteration is not the same as executing a <code>break</code>
 * statement in a regular loop. The parallel iteration does not stop until each
 * thread,
 * <I>including the thread that called <code>stopLoop()</code></I>, has finished
 * processing its current item. Thus, processing may continue for a while after
 * <code>stopLoop()</code> is called. (The <code>return</code> statement in the above
 * example causes the thread that called <code>stopLoop()</code> to stop its
 * processing early.)
 * <P>
 * Normally, at the end of the parallel iteration, the parallel team threads
 * wait for each other at a barrier. To eliminate this barrier wait, include
 * {@link edu.rit.pj.BarrierAction#NO_WAIT BarrierAction.NO_WAIT} in the <code>execute()</code>
 * method call:
 * <PRE>
 *     new ParallelRegion()
 *         {
 *         . . .
 *         public void run()
 *             {
 *             . . .
 *             execute (list, new ParallelIteration&lt;String&gt;()
 *                 {
 *                 . . .
 *                 },
 *             BarrierAction.NO_WAIT);
 *             . . .
 *             }
 *         }
 * </PRE> 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 <code>execute()</code> method call. The barrier action object's
 * <code>run()</code> method contains the code to be executed in a single thread
 * while the other threads wait:
 * <PRE>
 *     new ParallelRegion()
 *         {
 *         . . .
 *         public void run()
 *             {
 *             . . .
 *             execute (list, new ParallelIteration&lt;String&gt;()
 *                 {
 *                 . . .
 *                 },
 *             new BarrierAction()
 *                 {
 *                 public void run()
 *                     {
 *                     // Single-threaded code goes here
 *                     . . .
 *                     }
 *                 });
 *             . . .
 *             }
 *         }
 * </PRE> For further information, see class {@linkplain BarrierAction}.
 * <P>
 * If the parallel iteration's <code>start()</code>, <code>run()</code>, or
 * <code>finish()</code> method throws an exception in one of the threads, then that
 * thread executes no further code in the loop, and the parallel region's
 * <code>execute()</code> method throws that same exception in that thread.
 * Furthermore, the other threads in the parallel team also process no further
 * items after finishing their current items. Thus, if one thread throws an
 * exception, the whole parallel iteration exits with some (perhaps none) of the
 * iterations unperformed.
 *
 * @param <T> Data type of the items iterated over.
 * @author Alan Kaminsky
 * @version 11-Nov-2007
 */
public abstract class ParallelIteration<T>
        extends ParallelConstruct {

// Hidden data members.
    // Item generator, used to obtain the items, to break this parallel
    // iteration, and to implement the ordered() construct.
    ItemGenerator<T> myItemGenerator;

    // Iteration index for the ordered() construct.
    int myOrderedIndex;

// Exported constructors.
    /**
     * Construct a new parallel iteration.
     */
    public ParallelIteration() {
        super();
    }

// Exported operations.
    /**
     * Perform per-thread initialization actions before starting the loop
     * iterations.
     * <P>
     * The <code>start()</code> method may be overridden in a subclass. If not
     * overridden, the <code>start()</code> method does nothing.
     *
     * @exception Exception The <code>start()</code> method may throw any exception.
     * @throws java.lang.Exception if any.
     */
    public void start()
            throws Exception {
    }

    /**
     * Process one item in this parallel iteration. The <code>run()</code> method
     * must perform the loop body for the given item.
     * <P>
     * The <code>run()</code> method must be overridden in a subclass.
     *
     * @param item Item.
     * @exception Exception The <code>run()</code> method may throw any exception.
     * @throws java.lang.Exception if any.
     */
    public abstract void run(T item)
            throws Exception;

    /**
     * Perform per-thread finalization actions after finishing the loop
     * iterations.
     * <P>
     * The <code>finish()</code> method may be overridden in a subclass. If not
     * overridden, the <code>finish()</code> method does nothing.
     *
     * @exception Exception The <code>finish()</code> method may throw any
     * exception.
     * @throws java.lang.Exception if any.
     */
    public void finish()
            throws Exception {
    }

    /**
     * Execute the given section of code in the items' iteration order. A call
     * to the <code>ordered()</code> method may appear in this parallel iteration's
     * <code>run()</code> method. When called, the <code>ordered()</code> method waits
     * until the <code>ordered()</code> method has been called and has returned for
     * all items prior to the current item. Then the <code>ordered()</code> method
     * calls the <code>run()</code> method of <code>theParallelSection</code>. When the
     * parallel section's <code>run()</code> method returns, the <code>ordered()</code>
     * method returns. If the parallel section's <code>run()</code> method throws an
     * exception, the <code>ordered()</code> method throws that same exception.
     * <P>
     * The <code>ordered()</code> method is used when a portion of a parallel
     * iteration has to be executed sequentially in the items' iteration order,
     * while the rest of the parallel iteration can be executed concurrently.
     * <P>
     * <I>Note:</I> Either the <code>ordered()</code> method must be called exactly
     * once during each call of the parallel iteration's <code>run()</code> method,
     * or the <code>ordered()</code> method must not be called at all.
     *
     * @param theSection Parallel section to execute in order.
     * @exception NullPointerException (unchecked exception) Thrown if
     * <code>theSection</code> is null.
     * @exception IllegalStateException (unchecked exception) Thrown if no
     * parallel team is executing this parallel iteration.
     * @exception Exception Thrown if <code>theSection</code>'s <code>run()</code>
     * method throws an exception.
     * @throws java.lang.Exception if any.
     */
    public final void ordered(ParallelSection theSection)
            throws Exception {
        // Verify preconditions.
        if (theSection == null) {
            throw new IllegalStateException("ParallelIteration.ordered(): Parallel section is null");
        }
        if (myTeam == null) {
            throw new IllegalStateException("ParallelIteration.ordered(): No parallel team executing");
        }

        // Wait until the ordered() construct has finished for all previous
        // iterations.
        if (myItemGenerator.myOrderedIndex != this.myOrderedIndex) {
            Spinner spinner = new Spinner();
            while (myItemGenerator.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;
            myItemGenerator.myOrderedIndex = this.myOrderedIndex;
        }
    }

    /**
     * Stop this parallel iteration. Once <code>stopLoop()</code> is called, after
     * each parallel team thread finishes processing its current item, each
     * thread will process no further items and will proceed to finish this
     * parallel iteration.
     *
     * @exception IllegalStateException (unchecked exception) Thrown if no
     * parallel team is executing this parallel iteration.
     */
    public final void stopLoop() {
        if (myTeam == null) {
            throw new IllegalStateException("ParallelIteration.stopLoop(): No parallel team executing");
        }
        myItemGenerator.myBreak = true;
    }

// Hidden operations.
    /**
     * Execute one chunk of iterations of this parallel for loop. This method
     * performs common processing, then calls the <code>run()</code> method.
     *
     * @param index Iteration index.
     * @param item Item.
     *
     * @exception Exception This method may throw any exception.
     */
    void commonRun(int index,
            T item)
            throws Exception {
        myOrderedIndex = index;
        run(item);
    }

}