Question on grading a parallelized algorithm

General OpenMP discussion

Question on grading a parallelized algorithm

Postby Linuxhippy » Mon Mar 25, 2013 4:59 am

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

Postby ftinetti » Mon Mar 25, 2013 5:38 am

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: 558
Joined: Wed Feb 10, 2010 2:44 pm

Re: Question on grading a parallelized algorithm

Postby Linuxhippy » Mon Mar 25, 2013 6:21 am

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

Postby MarkB » Mon Mar 25, 2013 8:01 am

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: 408
Joined: Thu Jan 08, 2009 10:12 am

Re: Question on grading a parallelized algorithm

Postby Linuxhippy » Thu Apr 04, 2013 8:09 am

Thanks a lot Mark.B., the links were quite helpful.

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: Image?

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

Postby MarkB » Fri Apr 05, 2013 3:09 am

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: 408
Joined: Thu Jan 08, 2009 10:12 am


Return to Using OpenMP

Who is online

Users browsing this forum: No registered users and 5 guests