| 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
ConcurrentContext.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 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:[code]
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.enter();
try {
ConcurrentContext.execute(ac);
ConcurrentContext.execute(bd);
ConcurrentContext.execute(abcd);
} finally {
ConcurrentContext.exit(); // Waits for all concurrent threads to complete.
}
// 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;
}
};[/code]
Here is a concurrent/recursive quick/merge sort using anonymous inner
classes (the same method is used for
benchmark):[code]
private void quickSort(final FastTable 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 t1 = FastTable.newInstance();
final FastTable 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);
}
}[/code]
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.
ConcurrentContext.getConcurrency() Concurrency can be
LocalContext locally adjusted. For example:[code]
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();
}[/code]
It should be noted that the concurrency cannot be increased above the
configurable
ConcurrentContext.MAXIMUM_CONCURRENCY maximum concurrency .
In other words, if the maximum concurrency is 0,
concurrency is disabled regardless of local concurrency settings.
author:
Jean-Marie Dautelle
version:
5.1, July 2, 2007 |
