Part 1 - Introduction

In this series we’ll understand and learn how to compute, quantify and, measure the performance of different systems and programs.

To compute, quantify and, measure performance let’s start by first defining what performance depends on.

Performance dependencies

When we’re making a system or a program a lot of different factors will weigh in the total performance:

• The underlying algorithm

  • Determines number of operations required, which directly impacts the performance.

• Programming language, compile, and, architecture of choice.

  • Determines number of instructions.

• Processor and memory

  • Determines how quickly each instruction executes

• I/O System (Includes the OS)

  • Determines how quickly each I/O operation executes

CPU Time

We can define CPU time by a very nice equation: $$ \text{CPU Time} = \frac{\text{Instructions}}{\text{Program}} \cdot\ \frac{\text{Clock cycles}}{\text{Instruction}} \cdot\ \frac{\text{Seconds}}{\text{Clock cycle}} $$

We will call these as the following: $$ \text{CPU Time} = IC \cdot\ CPI \cdot\ T_c $$

One way to actually then measure computers or programs is using SPEC.

SPEC, or Standard Performance Evaluation Corp, is a company which specialize in measuring.

The idea is to normalize compared to a reference computer using geometric means.

This is called the SPECvalue.

Geometric mean: $$ \sqrt[n]{\prod_{i = 1}^{n} \text{Execution time ratio}_i} $$

RISC/CISC Architecture

In the early days, it was thought that, if we made the machine instructions closer to real (higher-level) programming functions, it would be faster for the computer.

We now know this is not true, and machine instructions are therefore as small and atomic as possible. These two approaches are known as RISC and CISC.

• RISC (Reduced Instruction Set Computers)
• CISC (Complex Instruction Set Computers)

MIPS

In this series we will use a MIPS instruction set, MIPS is still used widely in the real world, but it’s slowly fading away to due RISC V’s popularity.

Let’s see some MIPS operations:

Arithmetic operations

1
add a, b, c # a := b + c

All arithmetic operations have this form, two source register and one destination registers.

We also see that comments are denoted by a # in MIPS programs.

Register operations

All operations in assembly languages utilize registers.

MIPS has a 32 x 32 bit register file (RF)

They are numbered 0 to 31 and, just a refresher, 32-bit data is called a “word”.

Example:

1
f = (g + h) - (i + j);

Given that $f, \ldots, j$ are in registers $s_0, \ldots, s_4$, in MIPS this will become:

1
add $t0, $s1, $s2 # temp0 := g + h
2
add $t1, $s3, $s4 # temp1 := i + j
3
sub $s0, $t0, $t1 # f := t0 - t1

Memory operations

Since MIPS is byte addressable, it means that each “word” has 4 bytes. Also good to note here is that MIPS uses big endian

Example:

1
g = h + A[8];

Given that g is in $s_1$, h in $s_2$ and, the starting address for A is at $s_3$

We will get the following MIPS code:

1
lw $t0, 32($s3)     # load word
2
add $s1, $s2, $t0

Example 2:

1
A[12] = h + A[8];

Given that h is in $s_2$, and, the starting address for A is at $s_3$

1
lw $t0, 32($s3)     # load word
2
add $t0, $s2, $t0
3
sw $t0, 48($s3)     # store word

Immediate operations

Instead of, for example, adding two registers, we may just want to add a constant, this can be done via:

1
addi $s3, $s3, 4

For subtracting we just do:

1
addi $s2, $s1, -1

Zero register

In MIPS there is a hard-coded zero register, that always contains the value zero, this can be used to quickly move values between registers:

1
add $t2, $s1, $zero     # t2 := s1

Logical operations

In MIPS there are of course logical operations:

1
# Logical Shifts
2
sll $t0, $t1, 2     # t0 := t1 * 4
3
srl $t0, $t1, 2     # t0 := t1 / 4
4

5
# Logical AND
6
and $t0, $t1, $t2   # t0 := t1 & t2
7
andi $t0, $t1, 2   # t0 := t1 & 2
8

9
# Logical OR
10
or $t0, $t1, $t2   # t0 := t1 | t2
11
ori $t0, $t1, 2   # t0 := t1 | 2
12

13
# Logical NOT
14
nor $t0, $t1, $zero # := NOT(t1)

Notice there isn’t an explicit not operation, but rather we use a nor operation with the zero register.

Conditional jumps

In MIPS there is only two conditional jumps, beq and bne:

1
beq rs, rt, L1 # if(rs == rt); Jump to L1
2
bne rs, rt, L1 # if(rs != rt); Jump to L1
3
j L1           # Jump to L1

So for example the following C-code:

1
if(i == j) {
2
    f = g + h;
3
} else {
4
    f = g - h;
5
}

Given that $f, g, \ldots$ is in $s_0, s_1, \ldots$

MIPS:

1
bne $s3, $s4, Else # if(i == j) jump to Else
2
add $s0, $s1, $s2  # f = g + h
3
j Exit             # Jump to exit
4

5
Else: sub $s0, $s1, $s2 # f = g - h
6
Exit: ...

Notice how there isn’t any usual blt, bge, since MIPS is of RISC architecture, we don’t need those.

Instead, what we can do is using slt. Which stands for set less than, we can now use this to replicate a blt or bge.

However, blt, bge are still pseudo-keywords in MIPS. The assembler will still be able to interpret these.

On the topic of pseudo-keywords, things like move and li are also pseudo-keywords.