View Category

Subdivide A Problem To A Pool Of Workers (No Shared Data)

Take a hard to compute problem and split it up between multiple worker threads. In your solution, try to fully utilize available cores or processors. (I'm looking at you, Python!)

Note: In this question, there should be no need for shared state between worker threads while the problem is being solved. Only after every thread completes computation are the answers recombined into a single output.

Example:

-Input-

(In python syntax)

["ab", "we", "tfe", "aoj"]

In other words, a list of random strings.

-Output-

(In python syntax)

[ ["ab", "ba", "aa", "bb", "a", "b"], ["we", "ew", "ww", "ee", "w", "e"], ...

In other words, all possible permutations of each input string are computed.
java
public class ParallelPermutations {

final AtomicInteger cnt = new AtomicInteger(0);

final List<Set<String>> permutations = new ArrayList<Set<String>>();

public static void main(String[] args) {
new ParallelPermutations(Arrays.asList(args));
}

public ParallelPermutations(List<String> words) {
for (final String word : words) {
new Thread(new Runnable() {
public void run() {
cnt.incrementAndGet() ;
Set<String> permutationSet = new HashSet<String>();
for (int i = 0; i < word.length(); i++)
for (int j = i + 1; j <= word.length(); j++)
permutations("", word.substring(i, j),
permutationSet);
permutations.add(permutationSet);
if (cnt.decrementAndGet() == 0)
synchronized (ParallelPermutations.this) {
ParallelPermutations.this.notify();
}
}
private void permutations(String prefix, String word, Set<String> permutations) {
int N = word.length();
if (N == 0)
permutations.add(prefix);
else
for (int i = 0; i < N; i++)
permutations(
prefix + word.charAt(i),
word.substring(0, i) + word.substring(i + 1, N),
permutations);
}
}).start();
}

synchronized (this) {
try {
wait();
} catch (InterruptedException e) {
Thread.currentThread().isInterrupted();
}
}

System.out.println(permutations);
}

}
public class ParallelPermutations {
public static void main(String[] words) throws Exception {
if(words.length==0)
words = new String[] {"ab", "we", "tfe", "aoj"};

ParallelPermutations permutations = new ParallelPermutations();
Map<String,Set<String>> wordPermutationSet =
permutations.calculate(words);

for(Map.Entry<String,Set<String>> e : wordPermutationSet.entrySet())
System.out.println(e.getKey()+" > "+e.getValue());

System.out.println(permutations.getNumberOfJobSpawned ()+" job(s) have been spawned");
}

private AtomicInteger jobSpawnedCounter = new AtomicInteger();
private ExecutorService workers ;
private ConcurrentLinkedQueue<Future<PermutationTask>> jobSpawned = newQueue();

public ParallelPermutations () {
int availableProcessors = Runtime.getRuntime().availableProcessors();
// create a thread pool according to the number of proc.
workers = Executors.newFixedThreadPool(availableProcessors);
}

private void spawn(PermutationTask task) {
Future<PermutationTask> spawned = workers.submit(task);
jobSpawnedCounter.incrementAndGet();
jobSpawned.add(spawned);
}
public int getNumberOfJobSpawned () {
return jobSpawnedCounter.get();
}

public Map<String,Set<String>> calculate (String[] words)
throws InterruptedException, ExecutionException
{
// submit all tasks, they will spawn sub-tasks by themselves
for(String word:words)
spawn(new PermutationTask(word));

Map<String,Set<String>> wordPermutationSet = newMap ();
Future<PermutationTask> spawned;
while( (spawned=jobSpawned.poll()) != null) {
// this will wait until the result is available
// this should also handle the fact that a sub-task is spawn
// and then added in the 'jobSpawned' before its parent is done
PermutationTask task = spawned.get();

String word = task.getWord();
Set<String> founds = task.getPermutationSet();
Set<String> alreadyFounds = wordPermutationSet.get(word);
if(alreadyFounds!=null)
alreadyFounds.addAll(founds);
else
wordPermutationSet.put(word, founds);
}
return wordPermutationSet;
}

private class PermutationTask implements Callable<PermutationTask> {
private final Set<String> permutationSet = new HashSet<String>();
private final String word;
private final int initialPos;
private final Stack<Integer> indicesUsed;
public PermutationTask(String word) {
this(word, 0, new Stack<Integer>());
}

/** sub task entry point */
public PermutationTask(String word,
int initialPos,
Stack<Integer> indicesUsed) {
this.word = word;
this.initialPos = 0;
this.indicesUsed = indicesUsed;
}

/** the word this task is working on*/
public String getWord() {
return word;
}

/** permutations set of this task */
public Set<String> getPermutationSet() {
return permutationSet;
}

/**
* perform the task specific calculation
* @see Callable
*/
public PermutationTask call() throws Exception {
calculatePermutation(initialPos, indicesUsed);
return this;
}

/**
* The algorithm part of the problem. The main interest is the sub-task
* spawning. When Java 7 will be available there would be a better
* alternative with the built-in fork/join framework.
*/
private void calculatePermutation(int currentPos, Stack<Integer> indicesUsed) {
final int maxLetterPerWord = word.length();
if(indicesUsed.size()>=maxLetterPerWord) {
return;
}

final StringBuilder builder = new StringBuilder();
for (int i = 0, length = word.length(); i < length; i++) {
if(indicesUsed.contains(i) && distinctIndices)
continue;
indicesUsed.push(i);
if(indicesUsed.size()>=MIN_LETTER_PER_WORD) {
builder.setLength(0);
for(Integer index: indicesUsed)
builder.append(word.charAt(index));
permutationSet.add(builder.toString());
}
// spawn a sub task to perform the next pos. calculation
spawn(new PermutationTask(word, currentPos+1, copy(indicesUsed)));
indicesUsed.pop();
}
}
}

/* algorithm parameters : the minimum number of letter per word */
private static int MIN_LETTER_PER_WORD = 1;
/* allow duplicated letters in the word found */
private static boolean distinctIndices = true;

/* factory method */
private static <T> ConcurrentLinkedQueue<T> newQueue () {
return new ConcurrentLinkedQueue<T>();
}
/* factory method */
private static <K,V> Map<K,V> newMap () {
return new HashMap<K,V>();
}
/* factory method */
private static Stack<Integer> copy(Stack<Integer> stack) {
Stack<Integer> copy = new Stack<Integer>();
copy.addAll(stack);
return copy;
}
}

Subdivide A Problem To A Pool Of Workers (Shared Data)

Take a hard to compute problem and split it up between multiple worker threads. In your solution, try to fully utilize available cores or processors. (I'm looking at you, Python!)

Note: In this question, there should be a need for shared state between worker threads while the problem is being solved.

Example:

-Conway Game of Life-

From Wikipedia:

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead. Every cell interacts with its eight neighbors, which are the cells that are directly horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

1. Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
2. Any live cell with more than three live neighbours dies, as if by overcrowding.
3. Any live cell with two or three live neighbours lives on to the next generation.
4. Any dead cell with exactly three live neighbours becomes a live cell.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths happen simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the one before). The rules continue to be applied repeatedly to create further generations.


--However, for our purposes, we will assign a size to the game "board": 2^k * 2^k . That is, the board should be easy to subdivide.

Notice that in this problem, at each step or "tick", each thread/process will need to share data with its neighborhood.
java
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class Life {
private static final int K = 4;
private static final int ITERATIONS = 10;

private static final boolean ALIVE = true;
private static final boolean DEAD = false;

private static final Board SEED = new Board(new boolean[][] {
{ DEAD, DEAD, DEAD, DEAD, DEAD, ALIVE, DEAD, ALIVE },
{ DEAD, ALIVE, ALIVE, DEAD, DEAD, DEAD, ALIVE, ALIVE },
{ DEAD, ALIVE, ALIVE, DEAD, DEAD, DEAD, ALIVE, DEAD },
{ DEAD, DEAD, DEAD, DEAD, ALIVE, DEAD, DEAD, DEAD },
{ DEAD, DEAD, DEAD, DEAD, ALIVE, ALIVE, DEAD, DEAD },
{ DEAD, DEAD, DEAD, DEAD, DEAD, ALIVE, ALIVE, ALIVE },
{ DEAD, DEAD, DEAD, DEAD, ALIVE, ALIVE, DEAD, DEAD },
{ DEAD, DEAD, DEAD, DEAD, ALIVE, DEAD, DEAD, DEAD } });

public static void main(String[] args) {
Life life = new Life(K, SEED);

System.out.println(life);

for (int i = 0; i < ITERATIONS; i++) {
life.tick();
System.out.println(life);
}
}

private final Board board, oldBoard;

public Life(int k, Board seed) {
int width = 1 << k;
int height = 1 << k;
board = new Board(width, height);
oldBoard = new Board(width, height);

seed.copyTo(board);
}

private void tick() {
board.copyTo(oldBoard);

ExecutorService executor = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());

for (int y = 0; y < board.height; y++)
for (int x = 0; x < board.width; x++)
executor.execute(new Evaluator(x, y));

executor.shutdown();

try {
executor.awaitTermination(30, TimeUnit.SECONDS);
} catch (InterruptedException e) {
e.printStackTrace();
}
}

public Board getBoard() {
return board;
}

@Override
public String toString() {
return getBoard().toString();
}

private class Evaluator implements Runnable {
private final int x, y;

Evaluator(int x, int y) {
this.x = x;
this.y = y;
}

@Override
public void run() {
boolean state = DEAD;

int neighbors = oldBoard.countNeighbors(x, y);

switch (neighbors) {
case 2:
if (oldBoard.get(x, y) == DEAD)
break;
case 3:
state = ALIVE;
}

board.set(x, y, state);
}
}

public static class Board {
private final boolean[][] data;
private final int width, height;

public Board(boolean[][] data) {
this.data = data;
height = data.length;
width = data[0].length;
}

public Board(int width, int height) {
this.width = width;
this.height = height;
data = new boolean[height][width];
clear();
}

public void clear() {
for (int y = 0; y < height; y++)
for (int x = 0; x < width; x++)
set(x, y, DEAD);
}

public void copyTo(Board target) {
int yo = (target.height - height) / 2;
int xo = (target.width - width) / 2;

for (int y = 0; y < height; y++)
for (int x = 0; x < width; x++) {
int dx = x + xo;
int dy = y + yo;

if (0 <= dx && dx < target.width && 0 <= dy && dy < target.height)
target.set(dx, dy, get(x, y));
}
}

public void set(int x, int y, boolean state) {
data[y][x] = state;
}

public boolean get(int x, int y) {
return data[y][x];
}

public int countNeighbors(int x, int y) {
int count = 0;

for (int y1 = Math.max(y - 1, 0), y2 = Math.min(y + 1, height - 1); y1 <= y2; y1++)
for (int x1 = Math.max(x - 1, 0), x2 = Math.min(x + 1, width - 1); x1 <= x2; x1++)
if (((y1 != y) || (x1 != x)) && get(x1, y1) == ALIVE)
count++;

return count;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();

for (int x = 0; x < width + 2; x++)
sb.append('#');

sb.append('\n');

for (int y = 0; y < height; y++) {
sb.append('#');

for (int x = 0; x < width; x++)
sb.append(get(x, y) == ALIVE ? '*' : ' ');

sb.append("#\n");
}

for (int x = 0; x < width + 2; x++)
sb.append('#');

return sb.toString();
}

public int getWidth() {
return width;
}

public int getHeight() {
return height;
}
}
}

Create a multithreaded "Hello World"

Create a program which outputs the string "Hello World" to the console, multiple times, using separate threads or processes.

Example:

-Output-

Thread one says Hello World!
Thread two says Hello World!
Thread four says Hello World!
Thread three says Hello World!

-Notice that the threads can print in any order.
java
for (int i = 0; i < 4; i++) {
final int nr = i ;
new Thread(new Runnable() {
public void run() {
System.out.println("Thread " + new String[] { "one", "two", "three", "four" }[nr] + " says Hello World!");
}
}).start();
}

Create read/write lock on a shared resource.

Create multiple threads or processes who are either readers or writers. There should be more readers then writers.

(From Wikipedia):

Multiple readers can read the data in parallel but an exclusive lock is needed while writing the data. When a writer is writing the data, readers will be blocked until the writer is finished writing.

Example:

-Output-

Thread one says that the value is 8.
Thread three says that the value is 8.
Thread two is taking the lock.
Thread four tried to read the value, but could not.
Thread five tried to write to the value, but could not.
Thread two is changing the value to 9.
Thread two is releasing the lock.
Thread four says that the value is 9.
...

--Notice that when a needed resource is locked, a thread can set a timer and try again in the future, or wait to be notified that the resource is no longer locked.
java
public class ParallelPermutations {

Lock lock = new ReentrantLock();

Integer value = 8;

public static void main(String[] args) {
new ParallelPermutations(Arrays.asList(args));
}

public ParallelPermutations(List<String> words) {
for (int i = 0; i < 20; i++) {
final Integer cnt = i ;
if ( i % 3 == 0) {
new Thread(new Runnable() {
public void run() {
if ( ! lock.tryLock() ) {
System.out.println("Thread " + cnt + " tried to write the value, but could not.") ;
lock.lock();
}
value = (int) (Math.random() * 10);
System.out.println("Thread " + cnt + " is changing the value to " + value ) ;
lock.unlock();
System.out.println("Thread " + cnt + " is releasing the lock.") ;
}
}).start();
} else {
new Thread(new Runnable() {
public void run() {
if ( ! lock.tryLock() ) {
System.out.println("Thread " + cnt + " tried to read the value, but could not.") ;
lock.lock() ;
}
System.out.println("Thread " + cnt + " says that the value is " + value + ".") ;
lock.unlock();
}
}).start();
}
}
}
}

Separate user interaction and computation.

Allow your program to accept user interaction while conducting a long running computation.

Example:

Hello user! Please input a string to permute: (input thread)
abcdef
Passing on abcdef... (input thread)
Please input another string to permute: (input thread)
lol
Passing on lol... (input thread)
Done Work On abcdef! (worker thread)
["abcdef", "abcefd", ... ] (worker thread)
Please input another string to permute: (input thread)
EXIT
Quitting, I'll let my worker thread know... (input thread)
We'
re quitting! Alright! (worker thread)

--Notice, that this could be accomplished on the command line or within a GUI. The point is that computation and user interaction should take place on separate threads of control.
java
public class BackgroundComputation {

final protected Queue<Thread> threads = new ConcurrentLinkedQueue<Thread>() ;

public BackgroundComputation() {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
try {
while (true) {
System.out.print("Enter string to permutate: ");
final String word = r.readLine();
if ("EXIT".equals(word) ) {
System.out.println("I'll let my worker thread know... (input thread)") ;
while (! threads.isEmpty())
threads.poll().stop(new ThreadDeath()) ;
break ;
}
Thread t = new Thread(new Runnable() {
public void run() {
try {
Set<String> permutationSet = new HashSet<String>();
for (int i = 0; i < word.length(); i++)
for (int j = i + 1; j <= word.length(); j++)
permutations("", word.substring(i, j), permutationSet);
System.out.println();
System.out.println("Received results: " + permutationSet);
System.out.print("Enter string to permutate: ");
} catch (ThreadDeath e) {
System.out.println("We're quitting! Alright!");
}
}

private void permutations(String prefix, String word, Set<String> permutations) {
int N = word.length();
if (N == 0)
permutations.add(prefix);
else
for (int i = 0; i < N; i++)
permutations(
prefix + word.charAt(i),
word.substring(0, i) + word.substring(i + 1, N),
permutations
);
}
});
t.start();
threads.add(t);
}
} catch (IOException ioe) {
System.out.println("IO error trying to read your name!");
System.exit(1);
}
}


public static void main(String[] args) {
new BackgroundComputation() ;
}
}