Developer Division Performance Engineering blog : Parallel Scalability Isn???t Child???s Play

Wed, 29 Apr 2009 08:31:23 GMT

PingBack from http://blogs.msdn.com/ddperf/archive/2009/03/16/parallel-scalability-isn-t-child-s-play.aspx

re: Parallel Scalability Isn’t Child’s Play, Part 2: Amdahl’s Law vs. Gunther’s Law

Sunny Egbo — Wed, 29 Apr 2009 21:25:38 GMT

Parallelism exists everywhere: instruction level, memory level, loop level, task level etc. Hence, parallelism has been with us all along for quite some time now (hardware engineers have been quietly busy for the last several decades solving them for us). The major difference now is that software engineers are being asked to step up to the plate due to the fact that the brick walls created by memory speed and power have now forced CPU architects to go multi-core in a major way (2x Frequency bumps every eighteen months are no longer practical).

In practice, the theoretical treatment of computing by Amdahl, Gunther or Gustafson can obfuscate the opportunities inherent in parallel computing. These treatments often part ways from reality by glossing over a number of important points in the use of parallelism for general purpose computing, including:

1. Many user tasks are non-monolithic; they can be solved in a distributed fashion; background tasks (e.g. virus scans) in a way that improves user experiences.

2. Some algorithms have inefficient sequential solutions but surprisingly efficient parallel solutions. [The fact that many problems that have very poor sequential algorithms are easier to parallelize should be comforting to fans of algorithms.] For example, many applications require matrix multiplication, which turns out to be easily parallelizable. Although the best sequential algorithm for matrix multiplication has a time complexity of O(n2.376), a straight-forward parallel solution has an asymptotic time complexity of O(log n) using n2.376 processor. In other words, we can readily find a parallel solution for matrix multiplication that improves its runtime as more and more processor cores become available.

3. Some poor sequential algorithms can be (easily) parallelized to execute in less time than their sequential solutions. For example, bubble-sort takes (n2+n)/2 time units when programmed to run sequentially; but it takes (n2 +6n)/4 time units when programmed to run in parallel in two processors. Thus, the parallel solution to bubble sort runs better in a multi-core environment when the size of the list is greater than four elements. Parallel bubble-sort takes even less time when many more processors are available. Hence, at some point, the benefit of the simpler parallelization of some solutions can outweigh the benefit of an equivalent complex but efficient sequential algorithm

In summary, it is where the rubber meets the road, in practice, that matters.

Parallel Scalability Isn’t Child’s Play, Part 3: The Problem with Fine-Grained Parallelism

Developer Division Performance Engineering blog — Tue, 09 Jun 2009 07:57:08 GMT

In the last blog entry in this series , I introduced the model for parallel program scalability proposed

Parallel Scalability Isn’t Child’s Play, Part 3: The Problem with Fine-Grained Parallelism

Developer Division Performance Engineering blog — Tue, 09 Jun 2009 23:32:48 GMT

In the last blog entry in this series , I introduced the model for parallel program scalability proposed