From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computing (Rated C-class, Low-importance)
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Low  This article has been rated as Low-importance on the project's importance scale.


Surely there is a conflict here!

"It is not uncommon to observe more than N speedup when using N processors in parallel computing, which is called super linear speedup. Super linear speedup rarely happens...."

not uncommon = happens moderately often

rarely happens = happens hardly ever

This needs tidying up. David Martland 11:32, 7 July 2006 (UTC)

I've rewritten it a bit now. Henrik 08:01, 13 July 2006 (UTC)

Too focused[edit]

Speedup can apply in more situations than just parallel computation. There is a more general story that can be told here. Jean-Loup Baer's book (and from what I have gathered Hennessy & Patterson) have a more general definition for the speedup of any program. If no one ends up editing the article by the time I have finished the class, I suppose I will do it. Doctorsher (talk) 03:29, 12 February 2014 (UTC)

Edited the page[edit]

I have re-edited the page to make it more general, as promised. Personally, I don't think the existing stuff on efficiency (which I moved to additional details, with everything else) even fits in the speedup section. Shouldn't that be its own page? Additionally, I think the more in-depth parallel processing notions should be done in the Amdahl's law page as opposed to this. However, someone with more writing/editing experience should make the judgement call on that, so I left it in. Just trying to make the article better. Doctorsher (talk) 21:57, 5 June 2014 (UTC)

parallel computing?[edit]

OK the definition currently goes like "In parallel computing, speedup refers to how much a parallel algorithm is faster than a corresponding sequential algorithm.", but the way I learned about speedup in uni is that it's a much more general thing in computer architecture and doesn't have to do with parallel computing. You could talk about speedup about any technology that makes processing faster. For example, you could talk about the speedup of using MMX-optimized code versus non-MMX code. This whole article focuses around parallelisation and the number of processors, and I think all of this needs rewriting, or maybe merging with amdahl's law. Someone please give your input on this. Alex.g (talk) 15:01, 23 January 2008 (UTC)

  • I agree. I just need some time to make these changes. Volunteers? --Diego Queiroz 19:29, 1 March 2011 (UTC) — Preceding unsigned comment added by Diego Queiroz (talkcontribs)

Explanation of parallel efficiency[edit]

Where does the $ \frac{1}{\log p} $ for "many difficult-to-parallelize algorithms" come from? Could someone please provide an example of an algorithm with such poor parallel efficieny? --Rolf (talk) 21:59, 22 March 2008 (UTC)

discussion of superlinear speedup misleading[edit]

It seems to me that superlinear speedup as defined is heavily dependent on the sequential algorithm. If the sequential algorithm is suboptimal, then the speedup can be anything and superlinear speedup will not be surprising. I suggest that for the purposes of discussing how big speedup can be as a function of the number of processors, it is better to assume that the sequential algorithm is optimal. For example, if the multiprocesor algorithm can have a thread that stops execution of a different thread, then why can't the sequential algorithm have the same threads? In addition, there is ambiguity about the problem size in regards to the multiprocessor algorithm. Do we assume that we are solving exactly the same problem with P processors as with 1 processor? If so, then we have to deal with the size of the memory when there are P processors. If the multiprocessor is allowed to have more memory then speedup may be due to the size of the memory rather than the number of processors. In the extreme case, the problem might be intractible with a single processor because of lack of memory. Speedup would then be infinite. Ec23nav (talk) 04:08, 16 April 2008 (UTC)

  • My understanding is that the same parallel algorithm is run on all the systems; but on the serial machine, the number of processors is set to 1. And the problem size is also assumed to be the same (and small enough that one processor can solve it). Ben Standeven (talk) 03:56, 21 January 2013 (UTC)

Linear speedup and efficiency 1[edit]

I have doubts with this. In my opinion linear speedup means for large, which means efficiency CONSTANT (i.e. bounded by below) not necessarily 1. Mariostorti (talk) 01:47, 28 June 2010 (UTC)

another super linear example[edit]

If the parallel algorithm uses some search like a random walk, the more processors that are walking, the less distance has to be walked in total before you reach what you are looking for. — Preceding unsigned comment added by (talk) 00:04, 29 August 2013 (UTC)