Class 1: Performance Analysis

Announcements:

1. This week, you should start working on putting your project report documents on the Web. If you need to do the conversion to LaTeX, do that first, and then run it through LaTeX2html (using the commands talked about in class last week). Once you have done the conversion to html, let me know where your html documents are stored on kaduna. Make the documents readable, and I will setup a link to the top html file from the PPL homepage. If you have any problems, please contact me.
2. Please see Amol Mali's suggestion on the csm.class.macs440 newsgroup. I think it is a great idea for the graduate students to post brief synopses of relevant papers on the newsgroup.

Today, we will talk about Chapter 3 of the Foster text. We will talk about how to do a methodical performance evaluation of your design.

The performance of a parallel solution design can be expressed in terms of a number of factors:

• speedup
• efficiency, processor-time product
• scalability
• memory requirements
• throughput, latency, I/O performance
• network throughput
• software engineering measures such as design costs, implementation costs, potential for reuse, etc.

A performance law that is often used to show the limits of parallel computing is Amdahl's Law. This law states that the speedup obtainable through parallel computation is limited by the ``sequential'' component of the algorithm. If f is the fraction of the code that is sequential, the law states that the speedup using n PEs is limited by:

This paints a very pessimistic picture of parallel computing. However, Amdahl's Law is only applicable to a fixed workload situation, and assumes that the parallel solution design follows the sequential design. The situation in real problems is often more optimistic, and Gustafson's Law on scaled problems is more appropriate.

Often times, parallel performance is reported as a single observation. This has the limitation that it does not convey how the performance scales with problem size or with number of processors. Therefore, a more thorough analysis should include a discussion about this.

Also, just an asymptotic analysis of the performance does not convey everything about parallel performance. There are other factors that need to be looked into:

1. what are the leading constants.
2. what are the low order terms that were ignored.
3. what parallel machine model was the analysis performed on.

It is therefore necessary to devise a more detailed model of performance that can answer questions related to real performance while still abstracting out most of the details. We will discuss the performance model for multicomputer algorithms presented in Section 3.3. This model divides up the time spent by a processor in terms of compute time, communication time, and idle time.

Towards the end of today's class, we will talk about Scalability Analysis.