# Speedup prediction of rotating mask filter

I am trying to do the speed up analysis of the rotating mask filter (section 4.2.3).

Let $N^2$ be the pixels in the image and let $m^2$ be the neighborhood of a given pixel, what I have for my sequential code is basically the following steps

for every pixel in the image
compute dispersion
end
compute average brightness with the mask of lowest dispersion
update pixel value
end


There is one formula to compute the idea speedup of an algorithm $\displaystyle S_p = \frac{t_s}{t_p}$ where $S_p$ is the speed up given $t_s$ time to run the sequential algorithm and $t_p$ time to run the parallel algorithm.

The first thing I don't understand is that if $t_s$ and $t_p$ are real measured time values or if we can take the complexity based on the input size.

Assuming the latter is possible, the complexity of this algorithm would be $O(NM)$ where $N$ is the total number of pixels and $M$ is the total number of pixels in the neighborhood. Having this $t_s = NM$ and $t_p = \frac{NM}{p}$ where $p$ is the number of processors, I get the ideal speedup $S_p$ to be linear, is this true?. I feel like I'm missing something, could you enlighten me to understand how to compute the speedup?

• For the speed up, you can do both. If $t_s$ and $t_p$ are real time measures, you will obtain the actual, real speed up. If $t_s$ and $t_p$ represent theoretical time measures, then you will obtain the theoretical speed up. Of course, you would like that both are the same but this depends on what you take into account for the theoretical time measures.
• Yes, it's normal that you obtain a linear speed up. Indeed, $t_p = \frac{NM}{p}$ says that you can perfectly split your works among your working units, without any extra cost. In this case, the speed up is "optimal", i.e. linear.
• So, in theory, you should obtain a linear speed up. If you measure it but experimentally it is not linear, this means that $t_p \neq \frac{NM}{p}$ and that you are missing something in your theoretical model. This can be a small amount of redundancy in the computation (for some reason, some computations are done twice), a suboptimal load balancing (not every working unit receives the same amount of work), communications (some data must be communicated between working units which takes time), synchronizations (at some point, some working units must wait for other units before going on),...

Let's make a small and very simple example.

You have a list of $N$ numbers $x_i$ and you want to compute for each $i$ the numbers $y_i = x_{i-1}^2 + x_i^2 + x_{i+1}^2$. You could say, I have $N$ numbers $y_i$ to compute, each of the $p$ working units computes $N/p$ numbers, so the speed up is $p$.

It might be not that easy.

(I suppose that you do not share the memory between the working units and for the extremities, we just restart on the other side of the list.)

Example: You have $20$ numbers.

With one working unit, you can square all the $x_i$ and then all the additions.

=> $20$ square operations and $40$ addition operations.

First attempt

With two working units, you split the work from $1$ to $10$ and $11$ to $20$. Here is the problem. To compute $y_{10}$ on the first working unit, you need $x_{11}$. The same for the second working unit, which requires $x_{10}$. The same for $y_1$ which requires $x_{20}$ and $y_20$ which requires $x_1$.

=> Each working unit makes $12$ square operations and $20$ addition operations.

The thing is that now there are redundant computations (we have $24$ square operations instead of $20$).

If you generalize this to $N$ numbers and $p$ processes, you obtain that each process needs $N/p+2$ square operations and $2N/p$ additions. So, $t_p$ will be something like $3N/p + 2$ and so the speed up will not be linear any more (even if it will looks like linear if $N>>p$).

Second attempt

To avoid the redundant computation, you first compute the squares of all the numbers in parallel and then compute the sums in parallel.

With two working units, the first working unit computes the squares from $x_1$ to $x_{10}$, with the second the squares from $x_{11}$ to $x_{20}$. Then, you compute the $y_1$ to $y_{10}$ with the first working unit and $y_{11}$ to $y_{20}$ with the second working unit. Now, you have exactly the same number of operations as in serial! Miracle? Nop.

You will have the square of $x_{11}$ compute on the second unit, but it's required in the first working unit for the computation of $y_{10}$. So you have to communicate the results between the working units, which costs time...

Again, the speed up is not optimal (looks like the one of the first attempt).

Now, there could be many other things that could go wrong:

• How do you get the list of numbers? If read from a file with one single working unit, this is a big bottleneck.
• What if instead of the square operation, we have a more complicated function that is sometimes easy to compute, sometimes hard? It will be very difficult to balance the work between the working units.
• ...
• I already measured the timings and from my experimental results I do not reach the theoretical speedup, which is what I expected. Could you give me some example of an algorithm where the ideal speed up is not linear? Does a convolution has a linear speed up in general? – BRabbit27 Apr 25 '13 at 11:41
• @BRabbit27 Edited my post with an example. For the convolution, I don't know, sorry! – Dr_Sam Apr 25 '13 at 13:34
• I see the point of not being linear, but the thing is that when $N>>p$ (which usually is the case), the upper bound for the speedup will be something like $O(p)$. I don't know if it is good or not to use the big-O notation when doing this speedup stuff. Actually in the code we have something more complex for the speedup: $N_{pixels}[(M_{rotations} - 1 )M_{dispersions}+M_{average}]$ I don't know how good is this to represent the speedup or should I just stick with the theoretical speedup being the ideal linear one. – BRabbit27 Apr 25 '13 at 13:55

The typical problem is that there is some portion of your work that doesn't actually parallelize. This is usually captured in the formula for Amdahl's Law. That being said, there must be at least one step in the above pseudocode that actually happens serially. If this is a shared-memory program, I suspect that there is serialization in "update-pixel".

• Actually that part of the code is parallelizable. Because the update of the value of a given pixel does not depends on the updated value of others, just depends on the things computed in the neighborhood (dispersion and mean brightness). Probably I'm confusing things. – BRabbit27 Apr 25 '13 at 13:44
• There must be some aspect of the code that's not parallelizing if you're not getting the expected speedup. I took a guess that it was the update because I presumed you were using shared memory and that your code might be mutexing or otherwise locking accesses to a shared array of pixels. What model of parallelism and library or API are you using? – Bill Barth Apr 25 '13 at 14:44
• I'm using CUDA. I know there are many factors that will avoid giving me the whole speedup (communications, memory access, etc). What I did try to ask was if the way I was making the prediction of my problem was well posed or If I'm being to vague. – BRabbit27 Apr 25 '13 at 15:55
• Your prediction is theoretically right, but it leaves out the possibility of parts that don't parallelize. – Bill Barth Apr 26 '13 at 2:54
• Ok. I can only think of reading/writing the image from/to a file. – BRabbit27 Apr 26 '13 at 5:20