## Question on grading a parallelized algorithm

General OpenMP discussion

### Question on grading a parallelized algorithm

Hi,

My supervisor requested that I should specify the theoretical scalability of processing steps using the Big-O notation: O(W(n)/p+T(n)) where W(n) is the parallelizeable part and T(n) is the serializeable part of a processing step.

I have to admit, although I've searched in various books for this definition, I've never seen scalability defined by using the Big-O notation.
And I also don't get the idea. An O(N^2) method will stay O(n^2) regardless how many CPUs are used for processing.

I am quite confused and would be really grateful for some enlightenmend.

Regards, Alexander
Linuxhippy

Posts: 3
Joined: Thu Mar 21, 2013 3:12 am

### Re: Question on grading a parallelized algorithm

Hi Alexander,

I think you can get some ideas in books like
"Introduction to Parallel Computing", A. Grama, A. Gupta, G. Karypis & V. Kumar (chapter 5, specifically)
"Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes", Frank Thomson Leighton

HTH,

Fernando.
ftinetti

Posts: 603
Joined: Wed Feb 10, 2010 2:44 pm

### Re: Question on grading a parallelized algorithm

Ok, I'll check those two books in our library today. However, as I wrote I've already searched for it in quite a few books and at at least the table of contents of "Introduction to Parallel Computing" looks very familiar. We have definitions of Speedup, Efficiency, Cost, .... but nothing related to the Big-O notation.
Linuxhippy

Posts: 3
Joined: Thu Mar 21, 2013 3:12 am

### Re: Question on grading a parallelized algorithm

Hi Alexander,

Linuxhippy wrote:And I also don't get the idea. An O(N^2) method will stay O(n^2) regardless how many CPUs are used for processing.

The idea is to express the time complexity of the computation as a function of both the problem size n and the number of processors p.
For example, suppose an step consists of matrix-matrix multiplication which is O(n^3) and parallelisable, followed by a triangular solve by forward/backward substitution which is O(n^2) and sequential, then the overall complexity would be O(n^3/p + n^2). You can find some more examples and explanations here: http://www.toves.org/books/distalg/

Hope that helps,
Mark.
MarkB

Posts: 670
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

### Re: Question on grading a parallelized algorithm

However I still have a last unanswered question. My functions often consist of two independent sub-functions which parallelize differently, e.g. O(W1/c +W2/min(c, 4)) where W1 scales without bounds, but W2 is limited to 4 cores.

Is it correct to specify the complexity of W1/W2 directly as arguments of the workload-function as done here: ?

Or is it better to just write W1, W2 and later mention that W1 = width*height?
As I need to reference W1/W2 in the text later, I cannot simply substitute W1 with width*height.

Thanks a lot, Clemens
Linuxhippy

Posts: 3
Joined: Thu Mar 21, 2013 3:12 am

### Re: Question on grading a parallelized algorithm

It depends a bit on what you are using the Big-O notation for, but in general it would be useful to express the complexity as a function of the most basic variables which determine the computational cost, e.g. width and height. One approach you might take is to write the expression as you have it: T_c = O(W1/c +W2/min(c, 4)) then write down equations for W1 and W2 in terms of the width w and height h, derive Big-O expressions for them (such as W1 ~ O(wh) ) and then substitute these in, so you end up with a Big-O expression for T_c in terms of c, w, and h (and any other variables which determine the cost).

Hope that makes sense,
Mark.
MarkB

Posts: 670
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh