Question 1: [total 40 marks]
Designing/implementing parallel algorithms in Java
PerfectImage is company producing an image processing tool, they have many filters, all
implementing the filter interface:
public interface Filter{
void applyFilter(Image img);
}
A Filter takes an image and does some in place transformation on the image.
This means that applyFilter modifies the (large) Image object in order to obtain a filtered version of
the same image.
Is it possible to set up a filter chain in this simple way:
void applyFilters(List<Filter>filters,Image img){
for(Filter f:filters){
f.applyFilter(img);
}
}
Now PerfectImage wants to support movies. In this simple context movies are just collections of
images.
A naive attempt of applying all the filters to all the images works correctly, but is too slow.
void applyAllFilters0(List<Filter>filters,List<Image> movie){
for(Image i:movie){
for(Filter f:filters){
f.applyFilter(i);
}
}
}
Question 1a: [6]
They asked to their programmer Bob to write a parallel version for such task.
This is the first attempt that Bob comes out with:
private static final ExecutorService pool=Executors.newCachedThreadPool();
void applyFilters1(List<Filter>filters,List<Image> movie)
throws InterruptedException, ExecutionException{
for(Image i:movie){
for(Filter f:filters){
pool.submit(()->f.applyFilter(i));
}
}
}
With great happiness of Bob, this method executes very fast!
However, when Bob run the test suite on this method, sometimes the test fails
stating that some filters was not
applied at all.
Describe what happens in this code, and explain where is the error.
Question 1b: [6]
After understanding his mistake, Bob modify his code as follows.
The only code difference is in the lines marked with //#
private static final ExecutorService pool=Executors.newCachedThreadPool();
void applyFilters2(List<Filter>filters,List<Image> movie)
throws InterruptedException, ExecutionException{
for(Image i:movie){
List<Future<?>> results=new ArrayList<>();//#
for(Filter f:filters){
results.add(pool.submit(()->f.applyFilter(i));//#
}
for(Future<?> r:results){r.get();}//#
}
}
Now, when Bob, runs the tests, he discovers that some images get corrupted. He is very confused.
Describe what happens this time:
-Explain why some images are corrupted.
-State the name for this kind of problems.
Question 1c: [8]
Depressed but still not ready to surrender, Bob learn about the synchronized statement
on a web forum and naively tries to use it.
The only difference is in the line marked with //#
private static final ExecutorService pool=Executors.newCachedThreadPool();
void applyFilters2(List<Filter>filters,List<Image> movie)
throws InterruptedException, ExecutionException{
for(Image i:movie){
List<Future<?>> results=new ArrayList<>();
for(Filter f:filters){
results.add(pool.submit(()->{ synchronized(i){f.applyFilter(i);} });//#
}
for(Future<?> r:results){r.get();}
}
}
Now, when Bob, runs the tests, they pass just fine!
Bob is very happy and goes to sleep.
However, the day after while doing some performance test he discovers that his code was much
slower than the
sequential version, and only one core is ever used.
Moreover, sometimes the result is still different from what is expected!
Explain why:
-Only one core is used.
-It is even slower than the sequential version.
-The result could still be different with respect to the sequential version
-[HARD:] How could Bob improve his tests to automatically detect this change in behavior?