ReplicatedObject

//******************************************************************************
//
// File:    ReplicatedObject.java
// Package: edu.rit.pj.replica
// Unit:    Class edu.rit.pj.replica.ReplicatedObject
//
// This Java source file is copyright (C) 2008 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.replica;

import java.io.IOException;
import java.util.concurrent.atomic.AtomicReference;

import edu.rit.mp.ObjectBuf;
import edu.rit.mp.buf.ObjectItemBuf;
import edu.rit.pj.Comm;
import edu.rit.pj.reduction.ObjectOp;

/**
 * Class ReplicatedObject provides a replicated, shared reduction variable for a
 * value of type T (a nonprimitive type).
 * <P>
 * A replicated, shared reduction variable is intended to be used in a cluster
 * or hybrid parallel program for a data item shared among all the processes in
 * the program and all the threads in each process. To use a replicated, shared
 * reduction variable, do the following in each process of the parallel program:
 * <OL TYPE=1>
 * <LI>
 * Construct an instance of class ReplicatedObject, specifying the reduction
 * operator (class {@linkplain edu.rit.pj.reduction.Op}) to use when performing
 * updates, and specifying the communicator (class {@linkplain edu.rit.pj.Comm})
 * and the message tag to use for sending updates among the processes. At this
 * point a <I>replica</I> of the variable exists in each process.
 *
 * <LI>
 * To read the variable, call the <code>get()</code> method. The current value of
 * the local process's replicated variable is returned.
 *
 * <LI>
 * To update the variable, call the <code>reduce()</code> method, specifying a new
 * value. The <code>reduce()</code> method performs an <I>atomic reduction</I>
 * (described below) on the local process's replicated variable with the new
 * value. If the variable changed as a result of the reduction, the variable's
 * (updated) value is flooded to all the processes in the communicator. Finally,
 * the <code>reduce()</code> method returns the variable's value.
 * <P>
 * Whenever one of the aforementioned flooded messages arrives, a separate
 * thread performs an atomic reduction on the local process's variable with the
 * received value.
 * <P>
 * An atomic reduction consists of these steps, performed atomically: Call the
 * reduction operator's <code>op()</code> method, passing in the current value of
 * the local process's replicated variable and the new value (either the new
 * value specified as an argument of <code>reduce()</code>, or the new value
 * received in a flooded message). Then store the <code>op()</code> method's return
 * value back into the local process's replicated variable.
 * </OL>
 * <P>
 * Class ReplicatedObject does not itself guarantee consistency of the replicas'
 * values. This is to avoid the message passing overhead of a distributed state
 * update protocol. Instead, the parallel program must be written to operate
 * correctly when the variable is updated as described above. Note that the
 * value of a process's local replica can change asynchronously at any time,
 * either because a thread in the current process updated the variable, or
 * because a flooded message updated the variable.
 * <P>
 * Class ReplicatedObject is multiple thread safe. The methods use lock-free
 * atomic compare-and-set.
 * <P>
 * <I>Note:</I> Class ReplicatedObject is implemented using class
 * java.util.concurrent.atomic.AtomicReference.
 *
 * @param <T> Object data type.
 * @author Alan Kaminsky
 * @version 13-Sep-2008
 */
public class ReplicatedObject<T> {

// Hidden data members.
    private ObjectOp<T> myOp;
    private AtomicReference<T> myValue;
    private int myTag;
    private Comm myComm;
    private Receiver myReceiver;

// Hidden helper classes.
    /**
     * Class Receiver receives and processes flooded messages to update this
     * replicated, shared reduction variable.
     *
     * @author Alan Kaminsky
     * @version 13-Sep-2008
     */
    private class Receiver
            extends Thread {

        public void run() {
            ObjectItemBuf<T> buf = ObjectBuf.buffer();

            try {
                for (;;) {
                    // Receive a flooded message.
                    myComm.floodReceive(myTag, buf);

                    // Do an atomic reduction.
                    T oldvalue, newvalue;
                    do {
                        oldvalue = myValue.get();
                        newvalue = myOp.op(oldvalue, buf.item);
                    } while (!myValue.compareAndSet(oldvalue, newvalue));
                }
            } catch (Throwable exc) {
                exc.printStackTrace(System.err);
            }
        }
    }

// Exported constructors.
    /**
     * Construct a new replicated, shared object reduction variable with the
     * given reduction operator. The initial value is null. A message tag of 0
     * is used. The world communicator is used.
     *
     * @param op Reduction operator.
     * @exception NullPointerException (unchecked exception) Thrown if
     * <code>op</code> is null.
     */
    public ReplicatedObject(ObjectOp<T> op) {
        this(op, null, 0, Comm.world());
    }

    /**
     * Construct a new replicated, shared object reduction variable with the
     * given reduction operator and initial value. A message tag of 0 is used.
     * The world communicator is used.
     *
     * @param op Reduction operator.
     * @param initialValue Initial value.
     * @exception NullPointerException (unchecked exception) Thrown if
     * <code>op</code> is null.
     */
    public ReplicatedObject(ObjectOp<T> op,
            T initialValue) {
        this(op, initialValue, 0, Comm.world());
    }

    /**
     * Construct a new replicated, shared object reduction variable with the
     * given reduction operator, initial value, and message tag. The world
     * communicator is used.
     *
     * @param op Reduction operator.
     * @param initialValue Initial value.
     * @param tag Message tag.
     * @exception NullPointerException (unchecked exception) Thrown if
     * <code>op</code> is null. Thrown if
     * <code>comm</code> is null.
     */
    public ReplicatedObject(ObjectOp<T> op,
            T initialValue,
            int tag) {
        this(op, initialValue, tag, Comm.world());
    }

    /**
     * Construct a new replicated, shared object reduction variable with the
     * given reduction operator, initial value, message tag, and communicator.
     *
     * @param op Reduction operator.
     * @param initialValue Initial value.
     * @param tag Message tag.
     * @param comm Communicator.
     * @exception NullPointerException (unchecked exception) Thrown if
     * <code>op</code> is null. Thrown if
     * <code>comm</code> is null.
     */
    public ReplicatedObject(ObjectOp<T> op,
            T initialValue,
            int tag,
            Comm comm) {
        if (op == null) {
            throw new NullPointerException("ReplicatedObject(): op is null");
        }
        if (comm == null) {
            throw new NullPointerException("ReplicatedObject(): comm is null");
        }
        myOp = op;
        myValue = new AtomicReference<T>(initialValue);
        myTag = tag;
        myComm = comm;
        myReceiver = new Receiver();
        myReceiver.setDaemon(true);
        myReceiver.start();
    }

// Exported operations.
    /**
     * Returns this replicated, shared reduction variable's current value.
     *
     * @return Current value.
     */
    public T get() {
        return myValue.get();
    }

    /**
     * Update this replicated, shared reduction variable's current value. This
     * variable is combined with the given value using the reduction operation
     * specified to the constructor (<I>op</I>). The result is stored back into
     * this variable and is returned; the result may also be flooded to all
     * processes in the communicator.
     *
     * @param value Value.
     * @return (This variable) <I>op</I> (<code>value</code>).
     * @exception IOException Thrown if an I/O error occurred.
     * @throws java.io.IOException if any.
     */
    public T reduce(T value)
            throws IOException {
        // Do an atomic reduction.
        T oldvalue, newvalue;
        do {
            oldvalue = myValue.get();
            newvalue = myOp.op(oldvalue, value);
        } while (!myValue.compareAndSet(oldvalue, newvalue));

        // If value changed, send a flooded message.
        if (newvalue != oldvalue) {
            myComm.floodSend(myTag, ObjectBuf.buffer(newvalue));
        }

        // Return updated value.
        return newvalue;
    }

    /**
     * Returns a string version of this reduction variable.
     *
     * @return String version.
     */
    public String toString() {
        return myValue.toString();
    }

}