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)
In other words, a list of random strings.
-Output-
(In python syntax)
In other words, all possible permutations of each input string are computed.
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.
scala
// as per Java answer, doesn't duplicate chars from input string, i.e. no 'aa'
// future detaches a computation whose result can
// be applied for at a later time
import scala.actors.Futures.future
def perm(s: String): IndexedSeq[String] =
if (s.length == 1)
IndexedSeq(s)
else
s map { c =>
future {
val subperms = perm(s filter (c !=))
(subperms map (c +)) ++ subperms
}
} flatMap (_ apply ())
def perms(l: Traversable[String]) =
l map (s => future(perm(s))) map (_ apply ())
val args = Seq("ab", "we", "tfe", "aoj")
println(perms(args))
// future detaches a computation whose result can
// be applied for at a later time
import scala.actors.Futures.future
def perm(s: String): IndexedSeq[String] =
if (s.length == 1)
IndexedSeq(s)
else
s map { c =>
future {
val subperms = perm(s filter (c !=))
(subperms map (c +)) ++ subperms
}
} flatMap (_ apply ())
def perms(l: Traversable[String]) =
l map (s => future(perm(s))) map (_ apply ())
val args = Seq("ab", "we", "tfe", "aoj")
println(perms(args))
cpp
vector<string> input;
input.push_back("ab");
input.push_back("we");
input.push_back("tfe");
input.push_back("aoj");
// Make the capacity for 'output' the same as 'input'
vector<set<string> > output(input.size());
#pragma omp parallel for
for (int i = 0; i < input.size(); ++i) {
set<string> perms;
generate_perms(input[i], perms);
#pragma omp critical
// Must use operator[]() and not push_back() since this line
// might be called in any order with respect to 'i'
output[i] = perms;
}
cout << output << endl;
input.push_back("ab");
input.push_back("we");
input.push_back("tfe");
input.push_back("aoj");
// Make the capacity for 'output' the same as 'input'
vector<set<string> > output(input.size());
#pragma omp parallel for
for (int i = 0; i < input.size(); ++i) {
set<string> perms;
generate_perms(input[i], perms);
#pragma omp critical
// Must use operator[]() and not push_back() since this line
// might be called in any order with respect to 'i'
output[i] = perms;
}
cout << output << endl;
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
Notice that in this problem, at each step or
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.
scala
import scala.actors.Futures.future
class Generation(gen: Array[String]) {
val width = gen(0).length
val hight = gen.length
override def toString = gen.reduceLeft(_ + "\n" + _)
def nextGen = {
// Calculate each row separately as a "future"
val ngFuture = (0 until hight).map(row => future(nextRow(row)))
// Wait for each row to finish
val ng = ngFuture.map(_ apply ())
new Generation(ng.toArray)
}
private def nextRow(row: Int): String =
(0 until width).map(nextCell(row, _)).foldLeft("")(_ + _)
private def nextCell(row: Int, col: Int) = {
liveNeighbors(row, col) match {
case 2 => cellAt(row, col)
case 3 => gameOfLife.liveCell
case _ => gameOfLife.deadCell
}
}
private def cellAt(row: Int, col: Int) =
gen((row + hight) % hight)((col + width) % width)
private def liveNeighbors(row: Int, col: Int) =
// Generate coordinate to all adjacent cells
((row-1) to (row+1)).flatMap(x => ((col-1) to (col+1)).map((x,_)))
// Remove our own cell and all dead neighbor cells
.filter(p => p != (row,col) && cellAt(p._1, p._2) == gameOfLife.liveCell)
// Get the number of cells we kept
.length
}
object gameOfLife {
val liveCell = 'O'
val deadCell = '.'
val firstGen = new Generation(Array(".O......",
"..O.....",
"OOO.....",
"........",
"........",
"........",
"........"))
def main(args: Array[String]) {
val numGens = if (args.length > 0) args(0).toInt else 3
var thisGen = firstGen
for (genNr <- 0 to numGens) {
println("Generation " + genNr)
println(thisGen)
thisGen = thisGen.nextGen
}
}
}
class Generation(gen: Array[String]) {
val width = gen(0).length
val hight = gen.length
override def toString = gen.reduceLeft(_ + "\n" + _)
def nextGen = {
// Calculate each row separately as a "future"
val ngFuture = (0 until hight).map(row => future(nextRow(row)))
// Wait for each row to finish
val ng = ngFuture.map(_ apply ())
new Generation(ng.toArray)
}
private def nextRow(row: Int): String =
(0 until width).map(nextCell(row, _)).foldLeft("")(_ + _)
private def nextCell(row: Int, col: Int) = {
liveNeighbors(row, col) match {
case 2 => cellAt(row, col)
case 3 => gameOfLife.liveCell
case _ => gameOfLife.deadCell
}
}
private def cellAt(row: Int, col: Int) =
gen((row + hight) % hight)((col + width) % width)
private def liveNeighbors(row: Int, col: Int) =
// Generate coordinate to all adjacent cells
((row-1) to (row+1)).flatMap(x => ((col-1) to (col+1)).map((x,_)))
// Remove our own cell and all dead neighbor cells
.filter(p => p != (row,col) && cellAt(p._1, p._2) == gameOfLife.liveCell)
// Get the number of cells we kept
.length
}
object gameOfLife {
val liveCell = 'O'
val deadCell = '.'
val firstGen = new Generation(Array(".O......",
"..O.....",
"OOO.....",
"........",
"........",
"........",
"........"))
def main(args: Array[String]) {
val numGens = if (args.length > 0) args(0).toInt else 3
var thisGen = firstGen
for (genNr <- 0 to numGens) {
println("Generation " + genNr)
println(thisGen)
thisGen = thisGen.nextGen
}
}
}
Create a multithreaded "Hello World"
Create a program which outputs the string
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.
"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.
scala
import scala.actors.Actor
List("one", "two", "three", "four").foreach { name =>
new Actor { override def act() = { println("Thread " + name + " says Hello World!") } }.start
}
List("one", "two", "three", "four").foreach { name =>
new Actor { override def act() = { println("Thread " + name + " says Hello World!") } }.start
}
List("one", "two", "three", "four").foreach { name =>
new Thread { override def run() = { println("Thread " + name + " says Hello World!") } }.start
}
new Thread { override def run() = { println("Thread " + name + " says Hello World!") } }.start
}
import scala.actors.Futures._
List("one", "two", "three", "four").foreach(name => future(println("Thread " + name + " says hi")))
List("one", "two", "three", "four").foreach(name => future(println("Thread " + name + " says hi")))
cpp
#include <iostream>
#include <string>
using namespace std;
int main(){
int pid;
string text[4]={"one","two","three","four"};
for (int i=0;i<4;i++){
pid=fork();
if (pid>0){
//cout << "Process("<<pid<<") - " << "Thread " << text[i] << " says Hello World!" << endl;
cout << "Thread " << text[i] << " says Hello World!" << endl;
exit(0);
}
}
return 0;
}
#include <string>
using namespace std;
int main(){
int pid;
string text[4]={"one","two","three","four"};
for (int i=0;i<4;i++){
pid=fork();
if (pid>0){
//cout << "Process("<<pid<<") - " << "Thread " << text[i] << " says Hello World!" << endl;
cout << "Thread " << text[i] << " says Hello World!" << endl;
exit(0);
}
}
return 0;
}
#include <iostream>
#include <string>
#include <omp.h>
int main() {
unsigned int const num_threads = 4;
std::string const names[] = { "one", "two", "three", "four" };
# pragma omp parallel num_threads(num_threads)
{
unsigned const id = omp_get_thread_num();
// Stream concatenation isn't thread-safe so we use a critical section.
# pragma omp critical
std::cout << "Thread " << names[id] << " says Hello World!" << std::endl;
}
}
#include <string>
#include <omp.h>
int main() {
unsigned int const num_threads = 4;
std::string const names[] = { "one", "two", "three", "four" };
# pragma omp parallel num_threads(num_threads)
{
unsigned const id = omp_get_thread_num();
// Stream concatenation isn't thread-safe so we use a critical section.
# pragma omp critical
std::cout << "Thread " << names[id] << " says Hello World!" << std::endl;
}
}
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.
(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.
scala
import java.util.concurrent.locks.ReentrantReadWriteLock
import java.util.concurrent.locks.ReentrantReadWriteLock.ReadLock
import java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock
import scala.util.Random
class Reader(name: String, lock: ReadLock) extends Thread {
override def run() = {
println(name)
while (true) {
if (!lock.tryLock)
{
println("Thread " + name + " tried to read the value, but could not.")
lock.lock
}
println("Thread " + name + " says that the value is " + rwLockOnSharedResource.value)
lock.unlock
Thread.sleep(3) // Generates output more similar to the problem description
}
}
}
class Writer(name: String, lock: WriteLock) extends Thread {
override def run() = {
while (true) {
if (!lock.tryLock) {
println("Thread " + name + " tried to write the value, but could not.")
lock.lock
}
println("Thread " + name + " is taking the lock.")
rwLockOnSharedResource.value = rwLockOnSharedResource.nextValue
println("Thread " + name + " is changing the value to " + rwLockOnSharedResource.value)
lock.unlock
println("Thread " + name + " is releasing the lock.")
Thread.sleep(3) // Generates output more similar to the problem description
}
}
}
object rwLockOnSharedResource {
private val maxValue = 10
private val randomVal = new Random
var value = nextValue
def nextValue = randomVal.nextInt(maxValue)
def main(args: Array[String]) = {
val rwLock = new ReentrantReadWriteLock(true)
val threadNames = List("one", "two", "three", "four", "five")
val readerCnt = threadNames.length * 2 / 3
val readerNames = threadNames.take(readerCnt)
val writerNames = threadNames.drop(readerCnt)
readerNames.foreach(new Reader(_, rwLock.readLock).start)
writerNames.foreach(new Writer(_, rwLock.writeLock).start)
}
}
import java.util.concurrent.locks.ReentrantReadWriteLock.ReadLock
import java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock
import scala.util.Random
class Reader(name: String, lock: ReadLock) extends Thread {
override def run() = {
println(name)
while (true) {
if (!lock.tryLock)
{
println("Thread " + name + " tried to read the value, but could not.")
lock.lock
}
println("Thread " + name + " says that the value is " + rwLockOnSharedResource.value)
lock.unlock
Thread.sleep(3) // Generates output more similar to the problem description
}
}
}
class Writer(name: String, lock: WriteLock) extends Thread {
override def run() = {
while (true) {
if (!lock.tryLock) {
println("Thread " + name + " tried to write the value, but could not.")
lock.lock
}
println("Thread " + name + " is taking the lock.")
rwLockOnSharedResource.value = rwLockOnSharedResource.nextValue
println("Thread " + name + " is changing the value to " + rwLockOnSharedResource.value)
lock.unlock
println("Thread " + name + " is releasing the lock.")
Thread.sleep(3) // Generates output more similar to the problem description
}
}
}
object rwLockOnSharedResource {
private val maxValue = 10
private val randomVal = new Random
var value = nextValue
def nextValue = randomVal.nextInt(maxValue)
def main(args: Array[String]) = {
val rwLock = new ReentrantReadWriteLock(true)
val threadNames = List("one", "two", "three", "four", "five")
val readerCnt = threadNames.length * 2 / 3
val readerNames = threadNames.take(readerCnt)
val writerNames = threadNames.drop(readerCnt)
readerNames.foreach(new Reader(_, rwLock.readLock).start)
writerNames.foreach(new Writer(_, rwLock.writeLock).start)
}
}
cpp
class reader
{
string name_;
public:
reader(const string& name) : name_(name) {}
void operator()() {
for (;;this_thread::sleep(posix_time::milliseconds(1)))
{
shared_lock<shared_mutex> lock(m, try_to_lock);
lock_guard<mutex> cout_lock(io_m);
cout << "Thread " << name_;
if (lock)
cout << " says that the value is " << shared_value << "." << endl;
else
cout << " tried to read the value, but could not." << endl;
}
}
};
class writer
{
string name_;
public:
writer(const string& name) : name_(name) {}
void operator()() {
for (;;this_thread::sleep(posix_time::milliseconds(1)))
{
unique_lock<shared_mutex> lock(m, try_to_lock);
lock_guard<mutex> cout_lock(io_m);
cout << "Thread " << name_;
if (lock)
{
cout << " is taking the lock." << endl;
shared_value = rand() % 10;
cout << "Thread " << name_ << " is changing the value to " << shared_value << endl;
cout << "Thread " << name_ << " is releasing the lock. " << endl;
}
else
cout << " tried to write to the value, but could not." << endl;
}
}
};
int main()
{
thread t1 = thread(reader("one"));
thread t2 = thread(reader("two"));
thread t3 = thread(reader("three"));
thread t4 = thread(writer("four"));
writer("five")();
}
{
string name_;
public:
reader(const string& name) : name_(name) {}
void operator()() {
for (;;this_thread::sleep(posix_time::milliseconds(1)))
{
shared_lock<shared_mutex> lock(m, try_to_lock);
lock_guard<mutex> cout_lock(io_m);
cout << "Thread " << name_;
if (lock)
cout << " says that the value is " << shared_value << "." << endl;
else
cout << " tried to read the value, but could not." << endl;
}
}
};
class writer
{
string name_;
public:
writer(const string& name) : name_(name) {}
void operator()() {
for (;;this_thread::sleep(posix_time::milliseconds(1)))
{
unique_lock<shared_mutex> lock(m, try_to_lock);
lock_guard<mutex> cout_lock(io_m);
cout << "Thread " << name_;
if (lock)
{
cout << " is taking the lock." << endl;
shared_value = rand() % 10;
cout << "Thread " << name_ << " is changing the value to " << shared_value << endl;
cout << "Thread " << name_ << " is releasing the lock. " << endl;
}
else
cout << " tried to write to the value, but could not." << endl;
}
}
};
int main()
{
thread t1 = thread(reader("one"));
thread t2 = thread(reader("two"));
thread t3 = thread(reader("three"));
thread t4 = thread(writer("four"));
writer("five")();
}
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)
Please input another string to permute: (input thread)
EXIT
Quitting, I
--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.
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.
scala
import scala.actors.Actor
object Worker extends Actor {
def perm(s: String): List[String] =
s.length match {
case 0 => Nil
case 1 => s :: Nil
case sLen => (0 to sLen-1).map(i => perm(s.take(i) + s.drop(i+1)).map(s(i) + _)).toList.flatten
}
def act() = react {
case "EXIT" =>
println("We're quitting! Alright!")
case (s: String) =>
val r = perm(s)
println("Done working on " + s + "!")
print("[ ")
r.foreach(s => print("\"" + s + "\", "))
println("]")
act()
}
}
object userInteractBackgroundCalc {
def main(args: Array[String]) {
print("Hello user! ")
Worker.start
var str = ""
do {
println("Please input a string to permute:")
str = readLine()
Worker ! str
} while (str != "EXIT")
}
}
object Worker extends Actor {
def perm(s: String): List[String] =
s.length match {
case 0 => Nil
case 1 => s :: Nil
case sLen => (0 to sLen-1).map(i => perm(s.take(i) + s.drop(i+1)).map(s(i) + _)).toList.flatten
}
def act() = react {
case "EXIT" =>
println("We're quitting! Alright!")
case (s: String) =>
val r = perm(s)
println("Done working on " + s + "!")
print("[ ")
r.foreach(s => print("\"" + s + "\", "))
println("]")
act()
}
}
object userInteractBackgroundCalc {
def main(args: Array[String]) {
print("Hello user! ")
Worker.start
var str = ""
do {
println("Please input a string to permute:")
str = readLine()
Worker ! str
} while (str != "EXIT")
}
}
cpp
class bg_worker
{
mutex bg_mutex_;
condition_variable work_present_;
deque<string> work_queue_;
result calc_perm(string s) {
result perms = result(new list<string>());
// sleep to simulate lots of work...
this_thread::sleep(posix_time::seconds(3));
sort(s.begin(), s.end());
do {
perms->push_back(s);
} while (next_permutation(s.begin(), s.end()));
return perms;
}
public:
void submit_work(const string &s) {
lock_guard<mutex> lock(bg_mutex_);
work_queue_.push_back(s);
work_present_.notify_one();
}
void operator()() {
for (;;) {
unique_lock<mutex> lock(bg_mutex_);
while (work_queue_.empty())
work_present_.wait(lock);
string s = work_queue_.front();
work_queue_.pop_front();
lock.unlock();
if (s == "EXIT") {
lock_guard<mutex> cout_lock(cout_mutex);
cout << "We're quitting! Alright!" << endl;
break;
}
result perm = calc_perm(s);
lock_guard<mutex> cout_lock(cout_mutex);
cout << "Done Work On " << s << "!" << endl;
cout << perm << endl;
}
}
};
int main()
{
bg_worker worker;
thread bg_thr(boost::ref(worker));
bool done = false;
{
lock_guard<mutex> cout_lock(cout_mutex);
cout << "Hello user! Please input a string to permute:" << endl;
}
while (!done)
{
string input;
cin >> input;
{
lock_guard<mutex> cout_lock(cout_mutex);
if (input == "EXIT") {
cout << "Quitting, I'll let my worker thread know..." << endl;
done = true;
} else {
cout << "Passing on " << input << "..." << endl;
cout << "Please input another string to permute:" << endl;
}
}
worker.submit_work(input);
}
bg_thr.join();
}
{
mutex bg_mutex_;
condition_variable work_present_;
deque<string> work_queue_;
result calc_perm(string s) {
result perms = result(new list<string>());
// sleep to simulate lots of work...
this_thread::sleep(posix_time::seconds(3));
sort(s.begin(), s.end());
do {
perms->push_back(s);
} while (next_permutation(s.begin(), s.end()));
return perms;
}
public:
void submit_work(const string &s) {
lock_guard<mutex> lock(bg_mutex_);
work_queue_.push_back(s);
work_present_.notify_one();
}
void operator()() {
for (;;) {
unique_lock<mutex> lock(bg_mutex_);
while (work_queue_.empty())
work_present_.wait(lock);
string s = work_queue_.front();
work_queue_.pop_front();
lock.unlock();
if (s == "EXIT") {
lock_guard<mutex> cout_lock(cout_mutex);
cout << "We're quitting! Alright!" << endl;
break;
}
result perm = calc_perm(s);
lock_guard<mutex> cout_lock(cout_mutex);
cout << "Done Work On " << s << "!" << endl;
cout << perm << endl;
}
}
};
int main()
{
bg_worker worker;
thread bg_thr(boost::ref(worker));
bool done = false;
{
lock_guard<mutex> cout_lock(cout_mutex);
cout << "Hello user! Please input a string to permute:" << endl;
}
while (!done)
{
string input;
cin >> input;
{
lock_guard<mutex> cout_lock(cout_mutex);
if (input == "EXIT") {
cout << "Quitting, I'll let my worker thread know..." << endl;
done = true;
} else {
cout << "Passing on " << input << "..." << endl;
cout << "Please input another string to permute:" << endl;
}
}
worker.submit_work(input);
}
bg_thr.join();
}
