Speed-up and Efficiency Calculations

• Speed-up
• Efficiency
• Size and Depth
• Examples

Speed-up

Speed-up is defined as the time it takes to complete an algorithm with one processor divided by the time it takes to complete the same algorithm with N processors.

Conceptually we think of speed-up as the gain we achieve by parallelizing an algorithm.  The larger the speed-up the greater the gain.

Efficiency

Efficiency is defined as the Speed-up with N processors divided by the number of processors N.

Conceptually we think of efficiency as how well we are utilizing all N processors when the algorithm is computed in parallel.  An efficiency of 100 percent means that all of the processors are being fully used all the time.

Size and Depth

Two other measures useful when analyzing an algorithm are size and depth.  Simply, size is the total number of operations performed, and depth is number of parallel steps necessary to complete the algorithm.

Examples

For the prefix algorithms we have the following:

                                                                                            *all of the above assumes N is a power of 2

For an example of speed-up and efficiency calculation see Project.