Performance

11 October 2005

• Questions?

• Performance

Which has best performance?

Which network is best?

• 56kb modem (56k bits / second, WW)

• Road Runner (5M bits / second, WW)

• USB Memory + Sneakers (8G bits / 5 minutes, feet)

• DLT (Digital Linear Tape) + FedEx (1T bit/12 hours)

TIME is THE measure!

• Response Time (latency)

  • How long does it take for my job to run?

  • How long does it take to execute a job?

  • How long must I wait for the database query?

• Throughput

  • How many jobs can the machine run at once?

  • What is the average execution rate?

  • How much work is getting done?

• If we upgrade a machine with a new processor what do we increase?

• If we add a new machine to the lab what do we increase?

What kind of time?

• Wall-clock Time

  • counts everything (disk and memory accesses, I/O , etc.)

  • a useful number, but sometimes not good for comparison or analysis purposes

• CPU time

  • doesn't count I/O or time spent running other programs

  • can be broken up into system time, and user time

• Our focus: user CPU time

  • time spent executing the lines of code that are "in" our program

DANGER Will Robinson!

• Focus on CPU time can SERIOUSLY distort our world view…

• SYSTEM designers (as opposed to CPU designers) must focus on the USER EXPERIENCE.

Performance

• For some program running on machine X

  • Performance_X = 1 / Execution time_X

• "X is n times faster than Y“

  • Performance_X / Performance_Y = n

Problem: machine A runs a program in 20 seconds, machine B runs the same program in 25 seconds.

Cycles

• Instead of reporting execution time in seconds, we often use cycles

seconds/program = cycles/program * seconds/cycle

• Clock ticks indicate when to start activities

• cycle time = time between ticks = seconds / cycle

• clock rate (frequency) = cycles / second (1 Hertz = 1 cycle/second)

A 2GHz clock has a 1/(2*10⁹) = 0.5 nanoseconds cycle time

How to improve performance?

seconds/program = cycles/program * seconds/cycle

So to improve performance you can either:

__________ the # of required cycles for a program, or
__________ the clock cycle time or, said another way,
__________ the clock rate

How many cycles are required for a program?

Could assume that # of cycles = # of instructions

Wrong! Different instructions take different numbers of cycles on different machines? Why?

Instructions take differing # of cycles

• Division takes longer than addition

• Floating point operations take longer than integer

• Accessing memory takes longer than accessing registers

Important point: changing cycle time often changes # of cycles required

Now that we understand cycles...

• A given program will require:

  • some number of machine instructions

  • some number of cycles

  • some number of seconds

• We have a vocabulary that relates the quantities:

  • cycle time (seconds / cycle)

  • clock rate (cycles / second)

  • CPI (cycles per instruction)

  • MIPS (millions of instructions per second)

Do any of these equal performance?

• # of cycles to execute program?

• # of instructions in program?

• # of cycles per second?

• average # cycles per instruction?

• average # of instructions per second?

Common pitfall: thinking one of the variables is indicative of performance when it really isn't.

CPI Example

Suppose we have two implementations of the same instruction set architecture (ISA). For some program, machine A has a clock cycle time of 10 ns. and a CPI of 2.0, and machine B has a clock cycle time of 20 ns. and a CPI of 1.2. Which machine is faster for this program, and by how much?

If two machines have the same ISA which of our quantities (e.g., clock rate, CPI, execution time, # of instructions, MIPS) will always be identical?

# of instructions example

A compiler designer is trying to decide between two code sequences for a particular machine. Based on the hardware implementation, there are three different classes of instructions: Class A, Class B, and Class C, and they require one, two, and three cycles (respectively).

The first code sequence has 5 instructions: 2 of A, 1 of B, and 2 of C.

The second sequence has 6 instructions: 4 of A, 1 of B, and 1 of C.

Which sequence will be faster? How much? What is the CPI for each sequence?

MIPS example

Two different compilers are being tested for a 100 MHz. machine with three different classes of instructions: Class A, Class B, and Class C, which require one, two, and three cycles (respectively). Both compilers are used to produce code for a large piece of software.

The first compiler's code uses 5 million Class A, 1 million Class B, and 1 million Class C instructions. The second compiler's code uses 10 million Class A, 1 million Class B, and 1 million Class C instructions.

Which sequence will be faster according to MIPS?

Which sequence will be faster according to execution time?

Benchmarks

• Performance best determined by running a real application

  • Use programs typical of expected workload

  • Or, typical of expected class of applications e.g., compilers/editors, scientific applications, graphics, etc.

• Synthetic benchmarks (Dhrystone, Whetstone)

  • nice for architects and designers

  • easy to standardize

  • Easy to abuse

• SPEC (System Performance Evaluation Cooperative)

  • companies have agreed on a set of real program and inputs

  • can still be abused

  • valuable indicator of performance (and compiler technology)

SPEC '89

Compiler "enhancements" and performance

SPEC '95

Does increasing clock rate increase performance?

Amdahl's Law

Execution time after improvement =
  Execution time unaffected +
    Execution time affected / Amount of improvement

T_I = T_U + T_A/I

Amdahl's Law Example

Suppose a program runs in 100 seconds on a machine, with multiply responsible for 80 seconds of this time. How much do we have to improve the speed of multiplication if we want the program to run 4 times faster?

100/4 = 20 + 80/n

n = 16

How about 5 times faster?

Amdahl's Law

T_I = T_U + T_A/I

• Principle: Make the common case fast

• Parallel Machines, Algorithms in hardware, GPU

Another example

Suppose we enhance a machine making all floating-point instructions run five times faster. If the execution time of some benchmark before the floating-point enhancement is 10 seconds, what will the speedup be if half of the 10 seconds is spent executing floating-point instructions?

speedup = old/new = 10/(0.5*10 + 0.5*10/5) = 1.67

One more example

We are looking for a benchmark to show off the new floating-point unit described above, and want the overall benchmark to show a speedup of 3. One benchmark we are considering runs for 100 seconds with the old floating-point hardware. How much of the execution time would floating-point instructions have to account for in this program in order to yield our desired speedup on this benchmark?

100/3 = 100*f/5 + 100*(1-f)

f = 5/6

Remember

• Performance is specific to particular programs

  • Total execution time is a consistent summary of performance

• For a given ISA performance increases come from:

  • increases in clock rate (without increasing CPI)

  • improvements in implementation that reduce CPI

  • compiler enhancements that lower CPI and/or instruction count

• Pitfall: expecting improvement in one aspect of machine's performance to improve total performance

Cultural Highlight

• Go to the State Fair!

• Check out Cream