Programming Parallel Computers 2020

Exercise MF: median filter

Individual tasks

Please see the grading tool for details on benchmark instances and time limits.

MF1: CPU baseline ★

Implement a simple sequential baseline solution. Make sure it works correctly. Do not use any form of parallelism yet.

You are expected to use a naive algorithm that computes the median separately for each pixel, with a linear-time median-finding algorithm.

Deadline week 1. Maximum points 5, after deadline 3.

MF2: multicore parallelism ★

Parallelize your solution to MF1 with the help of OpenMP and multithreading so that you are exploiting multiple CPU cores in parallel.

Deadline week 2. Maximum points 3, after deadline 2.

MF9a: better algorithm [challenging] ★★★

Design a better algorithm that does not recalculate the median separately for each pixel. Make it as efficient as possible, also for very large window sizes. You are encouraged to use all resources that you have in the CPU.

Deadline week 6. Maximum points 5.