javolution.context

Class ConcurrentContext

java.lang.Object

javolution.context.Context

javolution.context.ConcurrentContext

All Implemented Interfaces:

java.io.Serializable, XMLSerializable

public abstract class ConcurrentContext
extends Context

This class represents a context to take advantage of concurrent algorithms on multi-processors systems.

When a thread enters a concurrent context, it may performs concurrent executions by calling the execute(Runnable) static method. The logic is then executed by a concurrent thread or by the current thread itself if there is no concurrent thread immediately available (the number of concurrent threads is limited, see Javolution Configuration for details).

Only after all concurrent executions are completed, is the current thread allowed to exit the scope of the concurrent context (internal synchronization).

Concurrent logics always execute within the same Context as the calling thread. For example, if the main thread runs in a StackContext, concurrent executions are performed in the same StackContext as well.

Concurrent contexts ensure the same behavior whether or not the execution is performed by the current thread or a concurrent thread. Any exception raised during the concurrent logic executions is propagated to the current thread.

Concurrent contexts are easy to use, and provide automatic load-balancing between processors with almost no overhead. Here is an example of concurrent/recursive implementation of the Karatsuba multiplication for large integers:

     public LargeInteger multiply(LargeInteger that) {
         if (that._size <= 1) {
             return multiply(that.longValue()); // Direct multiplication.
         } else { // Karatsuba multiplication in O(n^log2(3))
             int bitLength = this.bitLength();
             int n = (bitLength >> 1) + (bitLength & 1);

             // this = a + 2^n b,   that = c + 2^n d
             LargeInteger b = this.shiftRight(n);
             LargeInteger a = this.minus(b.shiftLeft(n));
             LargeInteger d = that.shiftRight(n);
             LargeInteger c = that.minus(d.shiftLeft(n));
             Multiply ac = Multiply.valueOf(a, c);
             Multiply bd = Multiply.valueOf(b, d);
             Multiply abcd = Multiply.valueOf(a.plus(b), c.plus(d));
             ConcurrentContext.execute(ac, bd, abcd);
             // a*c + ((a+b)*(c+d)-a*c-b*d) 2^n + b*d 2^2n
             return  ac.value().plus(
                 abcd.value().minus(ac.value().plus(bd.value())).shiftWordLeft(n)).plus(
                 bd.value().shiftWordLeft(n << 1));
         }
     }
     private static class Multiply implements Runnable {
         LargeInteger _left, _right, _value;
         static Multiply valueOf(LargeInteger left, LargeInteger right) {
             Multiply multiply = new Multiply(); // Or use an ObjectFactory (to allow stack allocation).
             multiply._left = left;
             multiply._right = right;
             return multiply;
         }
         public void run() {
             _value = _left.times(_right); // Recursive.
         }
         public LargeInteger value() {
             return _result;
         }
     };

Here is a concurrent/recursive quick/merge sort using anonymous inner classes (the same method is used for benchmark):

    private void quickSort(final FastTable<? extends Comparable> table) {
        final int size = table.size();
        if (size < 100) {
            table.sort(); // Direct quick sort.
        } else {
            // Splits table in two and sort both part concurrently.
            final FastTable<? extends Comparable> t1 = FastTable.newInstance();
            final FastTable<? extends Comparable> t2 = FastTable.newInstance();
            ConcurrentContext.enter();
            try {
                ConcurrentContext.execute(new Runnable() {
                    public void run() {
                        t1.addAll(table.subList(0, size / 2));
                        quickSort(t1); // Recursive.
                    }
                });
                ConcurrentContext.execute(new Runnable() {
                    public void run() {
                        t2.addAll(table.subList(size / 2, size));
                        quickSort(t2); // Recursive.
                    }
                });
            } finally {
                ConcurrentContext.exit();
            }
            // Merges results.
            for (int i=0, i1=0, i2=0; i < size; i++) {
                if (i1 >= t1.size()) {
                    table.set(i, t2.get(i2++));
                } else if (i2 >= t2.size()) {
                    table.set(i, t1.get(i1++));
                } else {
                    Comparable o1 = t1.get(i1);
                    Comparable o2 = t2.get(i2);
                    if (o1.compareTo(o2) < 0) {
                        table.set(i, o1);
                        i1++;
                    } else {
                        table.set(i, o2);
                        i2++;
                    }
                }
            }
            FastTable.recycle(t1);
            FastTable.recycle(t2);
        }
     }

Concurrency can be locally adjusted. For example:

         LocalContext.enter();
         try { // Do not use more than half of the processors during analysis.
             ConcurrentContext.setConcurrency((Runtime.getRuntime().availableProcessors() / 2) - 1);
             runAnalysis(); // Use concurrent contexts internally.
         } finally {
             LocalContext.exit();
         }

It should be noted that the concurrency cannot be increased above the configurable maximum concurrency. In other words, if the maximum concurrency is 0, concurrency is disabled regardless of local concurrency settings.

Version:

5.1, July 2, 2007

Author:

Jean-Marie Dautelle

See Also:

Serialized Form

Field Summary

Fields

Modifier and Type	Field and Description
static Configurable<java.lang.Class<? extends ConcurrentContext>>	DEFAULT Holds the default implementation.
static Configurable<java.lang.Integer>	MAXIMUM_CONCURRENCY Holds the maximum number of concurrent executors (see Javolution Configuration for details).

Fields inherited from class javolution.context.Context

ROOT

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	ConcurrentContext() Default constructor.

Method Summary

Modifier and Type	Method and Description
static void	enter() Enters a concurrent context (instance of DEFAULT).
static void	enter(boolean condition) Enters a concurrent context only if the specified condition is verified.
static void	execute(java.lang.Runnable... logics) Executes the specified logics concurrently.
static void	execute(java.lang.Runnable logic) Executes the specified logic by a concurrent thread if one available; otherwise the logic is executed by the current thread.
protected abstract void	executeAction(java.lang.Runnable logic) Executes the specified logic concurrently if possible.
static void	exit() Exits the current concurrent context.
static void	exit(boolean condition) Exits a concurrent context only if the specified condition is verified.
static int	getConcurrency() Returns the local concurrency.
static void	setConcurrency(int concurrency) Set the local concurrency.

Methods inherited from class javolution.context.Context

enter, enter, enterAction, exit, exit, exitAction, getCurrentContext, getOuter, getOwner, setConcurrentContext, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

MAXIMUM_CONCURRENCY

public static final Configurable<java.lang.Integer> MAXIMUM_CONCURRENCY

Holds the maximum number of concurrent executors (see Javolution Configuration for details).

DEFAULT

public static final Configurable<java.lang.Class<? extends ConcurrentContext>> DEFAULT

Holds the default implementation. Concurrent executions are performed in the same memory area and at the same priority as the calling thread. This implementation uses javax.realtime.RealtimeThread for concurrent threads. Alternative (RTSJ) implementations could also use javax.realtime.NoHeapRealtimeThread.

Constructor Detail

ConcurrentContext

protected ConcurrentContext()

Default constructor.

Method Detail

enter

public static void enter()

Enters a concurrent context (instance of DEFAULT).

enter

public static void enter(boolean condition)

Enters a concurrent context only if the specified condition is verified.

Parameters:

condition - true to enter a concurrent context; false otherwise.

exit

public static void exit()

Exits the current concurrent context.

Throws:

java.lang.ClassCastException - if the context is not a concurrent context.

exit

public static void exit(boolean condition)

Exits a concurrent context only if the specified condition is verified.

Parameters:

condition - true to exit a concurrent context; false otherwise.

setConcurrency

public static void setConcurrency(int concurrency)

Set the local concurrency. Concurrency is hard limited by MAXIMUM_CONCURRENCY.

Parameters:

concurrency - the new concurrency (0 or negative number to disable concurrency).

getConcurrency

public static int getConcurrency()

Returns the local concurrency.

Returns:

the maximum number of concurrent thread.

execute

public static void execute(java.lang.Runnable logic)

Executes the specified logic by a concurrent thread if one available; otherwise the logic is executed by the current thread. Any exception or error occurring during concurrent executions is propagated to the current thread upon exit() of the concurrent context.

Parameters:

logic - the logic to execute concurrently if possible.

Throws:

java.lang.ClassCastException - if the current context is not a ConcurrentContext.

execute

public static void execute(java.lang.Runnable... logics)

Executes the specified logics concurrently. This method is equivalent to:

     ConcurrentContext.enter();
     try {
         ConcurrentContext.execute(logics[0]);
         ConcurrentContext.execute(logics[1]);
         ...
     } finally {
         ConcurrentContext.exit();
     }
 

Parameters:

logics - the logics to execute concurrently if possible.

executeAction

protected abstract void executeAction(java.lang.Runnable logic)

Executes the specified logic concurrently if possible.

Parameters:

logic - the logic to execute.