The computer revolution ���������� 15� – e.g.

,: multiplication takes more cycles than addition • Hierarchical layers of abstraction

= 10� = 1.5x
• The third revolution along with agriculture and ���������� • More precise CPU clock cycles should take instruction – In both hardware and software
industry • Progress in computer technology – Measuring time types into account • Instruction set architecture
Underpinned by Moore’s Law • Makes novel • Elapsed time Clock cycles = ��=1 (���� × ����������� ������ ) – The hardware/software interface
applications feasible – Computers in automobiles – Cell – Total response time, including all aspects • • Weighted average CPI • Execution time: the best performance measure
phones – Human genome project – World Wide Web– Processing, I/O, OS overhead, idle time • Power is a limiting factor
Search Engines • Computers are pervasive – Determines system performance • CPU time – Use parallelism to improve performance
A Brief History of Computers – Time spent processing a given job Von Neumann architecture
• Discounts I/O time, other jobs’ shares Example: • Question: two implementations of an
• The first generation – Vacuum tubes 1946 – 1955 • Stored-program concept • Instruction category:
– Comprises user CPU time and system CPU time application that use instructions in classes A, B, and C
• The second generation– Transistors 1955 – 1965 – Arithmetic – Data transfer– Logical – Conditional
– Different programs are affected differently by CPU as follows. Which one is better?
• The third generation– Integrated circuits 1965 – 1980 branch– Unconditional jump
and system performance. – Implementation 1 uses 2 A, 1 B, and 2 C
• The current generation– Personal computers – 1980 -
Measuring CPU time – Implementation 2 uses 4 A, 1 B, and 1 C
• What’s the next? – Quantum computers? – Memristor?
• Operations of digital hardware (including – CPIs for A, B, and C are 1, 2, and 3, respectively
Classes of Computers
CPU/processor) governed by a constant-rate clock • Answer:
• Personal computers: General purpose, variety of
– Implementation 1: • IC = 5, wCPI = 2.0
software – Subject to cost/performance tradeoff
– Implementation 2: • IC = 6, wCPI = 1.5
• Server computers: – Network based – High capacity,
Exercise: • A program is executed on a 2 GHz CPU. The
performance, reliability – Range from small servers to
program consists of
building sized • Supercomputers: – High-end scientific
1000 instructions in which: – 30% load/store
and engineering calculations – Highest capability but
instructions, CPI = 2.5 – 10% jump instructions, CPI = 1 –
represent a small fraction of the overall computer • Clock period (T): duration of a clock cycle – s, ms, μs,
20% branch instructions, CPI = 1.5 – The rest are
market • Embedded computers: – Hidden as ns • Clock rate/frequency : the number of cycles
arithmetic instructions, CPI = 2.0
components of systems – Stringent per second – Hz, KHz, MHz, GHz
a) What is execution time (CPU time) of the program? Computer components
power/performance/cost constraints CPU time
b) What is the weighted average CPI of the program?
Modern computer components • Performance improved by – Reducing number of clock
c) If load/store instructions are improved so that their
• Same components for all kinds • Components – cycles – Increasing clock rate – Hardware designer
execution time is reduced by a factor of 2, what is the
Processor: • Datapath • controller – Memory • Main must often trade off clock rate against cycle count
speed-up of the system?
memory • Cache – Input/Output: • User-interface • CPU Time = CPU Clock cycles x Clock Cycle Time
-------------------
Network• Storage = CPU Clock cycles / Clock rate
Performance summary
Below your program Example: • Computer A: 2GHz clock, 10s CPU time
• The BIG picture (take home message)
• Application software – Written in high-level language • Designing Computer B – Aim for 6s CPU time – Can do ����������� ����� ������ �������
• System software – Compiler: translates HLL code to faster clock, but causes 1.2 × clock cycles CPU time= × ×
������� ����������� ����� �����
machine code– Operating System: service code • How fast must Computer B clock be?
• Performance depends on
• Handling input/output • Managing memory and
– Algorithm: IC, possibly CPI
storage • Scheduling tasks & sharing resources
– Programming language: IC, CPI
• Hardware – Processor, memory, I/O Controllers
– Compiler: IC, CPI
Levels of Program Code
– Instruction set architecture: IC, CPI, T
• High-level language – Level of abstraction closer to
Instruction count & CPI Reducing power
problem domain – Provides for productivity and
• Instruction Count for a program • Suppose a new CPU has
portability • Assembly language – Textual
– Determined by program, ISA and compiler – 85% of capacitive load of old CPU
representation of instructions • Hardware
• Average cycles per instruction – 15% voltage and 15% frequency reduction
representation – Binary digits (bits) – Encoded
instructions and data – Determined by CPU hardware Instruction execution model
Technology trends – If different instructions have different CPI
• Thanks to electronics and material technologies – • Average CPI affected by instruction mix • The power wall
Increased capacity and performance– Reduced cost • We can’t reduce voltage further
Response Time and Throughput • We can’t remove more heat
• Response time – How long it takes to do a task • How else can we improve performance?
Benchmark • Instruction fetch: from the memory
• Throughput – Total work done per unit time – PC increased– PC stores address of the next
• e.g., tasks/transactions/… per hour Example: • Which is faster, and by how much? • Programs used to measure performance
– Supposedly typical of actual workload instruction • Execution: decode and execute
• How are response time and throughput affected by – Computer A: Cycle Time = 250ps, CPI = 2.0
• Standard Performance Evaluation Corp (SPEC) MIPS instruction set
– Replacing the processor with a faster version? – Computer B: Cycle Time = 500ps, CPI = 1.2
– Develops benchmarks for CPU, I/O, Web, … MIPS architecture
– Adding more processors? – Same ISA, compiler
• SPEC CPU2006 • MIPS Assembly Instruction <=> MIPS M achine
• We’ll focus on response time for now… Instruction• Assembly: add $t0, $s2, $t0
Relative performance – Elapsed time to execute a selection of programs
• Negligible I/O, so focuses on CPU performance • Machine: 000000_10010_01000_01000_00000_100000
Performance = 1/Execution time • Only one operation is performed per MIPS instruction
• Computer X is times faster than Computer Y – Normalize relative to reference machine
– Summarize as geometric mean of performance ratios – e.g., needs at least two instructions
������������ ��������� �����
= =n • CINT2006 (integer) and CFP2006 (floating-point) Instruction set design principle
������������ ��������� ����� • Simplicity favors regularity • Smaller is faster • Make
Concluding remarks
Example: time take to run a program: 10s on A and 15s Mixed instructions CPI the common case fast • Good design demands good
• Cost/performance is improving
on B, A is faster than B because • CPI for instructions/operations may vary compromises
– Due to underlying technology development
MIPS operands – Arrays, structures, dynamic data branch instructions – beq $rs, $rt, L1 #branch if equal • • Memory operands: offset + base register
1. Register: 32 32-bit registers (start with the $ sign) • To apply arithmetic operations If (rs == rt), go to L1 – bne $rs, $rt, L1 • If (rs != rt), go to Leaf procedure
– $s0-$s7: corresponding to variables (save) – $t0-$t9: – Load value(s) from memory into register(s) L1 • Label: a given name – format: <label>: <instruction> C code:
storing temporary value– $a0-$a3– $v0-$v1 – $gp, $fp, – Apply arithmetic operations to the register(s) int leaf_example (int g, h, i, j){
$sp, $ra, $at, $zero, $k0-$k1 – Store result from a register to memory (if required) int f; f = (g + h) - (i + j); return f; }
2. Memory operand: memory words (4 byte each): • MIPS is Big Endian – Arguments g, …, j in $a0, …, $a3
accessed only by data transfer instructions – Most-significant byte at least address of a word – f in $s0 (hence, need to save $s0 on stack)
3. Short integer immediate: -10, 20, 2020,… – Little Endian: least-significant byte at least address – Result in $v0
1st group: arithmetic instructions Example 1: • C code: g = h + A[8]; 5th group: unconditional jump instructions MIPS code:
• Assembly instruction format: Opcode - Destination – g in $s1, h in $s2, base address of A in $s3 Immediately jump to a label – Without any condition
register - Source register 1 - Source Register 2* • Compiled MIPS code:– Index 8 requires offset of 32, 4 checked• Three standard unconditional jumps
• Opcode: bytes per word – j <label>: • Jump to the label, e.g., L1
– add: DR = SR1 + SR2 lw $t0, 32($s3) # load word – jal <label> • Jump to the label L1 and store address of
– sub: DR = SR1 – SR2 add $s1, $s2, $t0 the next instruction to the $ra register • Used for
– addi: (*) SR2 is an immediate (e.g. 20), DR= SR1 + SR2 Example 2: C code: A[12] = h + A[8]; function/procedure call
• Three register operands – h in $s2, base address of A in $s3 – jr $register • Jump to an instruction whose address is
Example: • Question: what is MIPS code for the • Compiled MIPS code:– Index 8 requires offset of 32 stored in the register • Used for returning to the caller
following C code f = (g + h) – (i + j); lw $t0, 32($s3) # load word function/procedure from a sub-function/-
• If the variables g, h, i, j, and f are assigned to the add $t0, $s2, $t0 procedure
Non -leaf procedure
register $s0, $s1, $s2, $s3, and $s4, respectively. sw $t0, 48($s3) # store word Example: Compile the following C code into MIPS code
C code: int fact (int n){
Exercises: (assume that f, g, h, i, and j are stored in registers from
$s0 to $s4, respectively) if (i == j) f = g + h; if (n < 1) return 1; else return n * fact(n - 1);}
1. Given the following memory map, assume that the – Argument n in $a0 – Result in $v0
register $t0 stores value 8 while $s0 contains else f = g - h;
MIPS code:
2nd group: data transfer instructions 0xCAFEFACE. Show the effects on memory and addi $sp, $sp, -8 # adjust stack for 2 items
Copy data b/w memory and registers in CPU registers of following instructions: a/ lw $t1, 0($t0) b/ sw $ra, 4($sp) # save return address
– Register lw $t2, 4($t0) c/ lh $t6, 4($t0) d/ lb $t5, 3($t0) e/ sw $s0, sw $a0, 0($sp) # save argument
– Address: a value used to delineate the location of a 0($t0) f/ sb $s0, 4($t0) g/ lh $s0, 7($t0) slti $t0, $a0, 1 # test for n < 1
specific data element within a memory array Exercise: • Convert the following C code to MIPS. beq $t0, $zero, L1
• Load (l): copy data from memory to a register Assume that the base address of the save array is addi $v0, $zero, 1 # if so, result is 1
• Store (s): copy data from a register to memory stored in $s0 while i and k are stored in the registers addi $sp, $sp, 8 # pop 2 items from stack
2. Convert the following C statements to equivalent $s1 and $s2, respectively jr $ra # and return
MIPS assembly language if the variables f, g, and h are int save[]; int i, k; … i = 0; while (save[i] == k) i += 1; L1: addi $a0, $a0, -1 # else decrement n
assigned to registers $s0, $s1, and $s2 respectively. Set-on-less-than instruction jal fact # recursive call
Assume that the base address of the array A and B are Example-1: Assume that values storing in $s1 and $s2 lw $a0, 0($sp) # restore original n
in registers $s6 and $s7, respectively. are 0xFFFFFFFF and 0x00000001, respectively. What lw $ra, 4($sp) # and return address
a) f = g + h + B[4] b) f = g – A[B[4]] are the results in $t0 and $t1 after the following addi $sp, $sp, 8 # pop 2 items from stack
3rd group: logical instructions instruction sslt $t0, $s1, $s2 sltu $t1, $s1, $s2 mul $v0, $a0, $v0 # multiply to get result
• Instruction format: the same with arithmetic $t0 = 1 due to signed numbers comparison ($s1 = -1) jr $ra # and return
Data transfer instructions instructions • Bitwise manipulation – Process operands $t1 = 0 due to unsigned numbers comparison ($s1 = Register numbers & some function fields
• Assembly instruction format: Opcode - register - bit by bit [Link]) what is machine code of following instruction? add $t0, $s1,
memory operand Pseudo instructions $s2 R-format is used to encode the above instruction
• Opcode:– Size of data: 1 byte, 2 bytes (half of word), or Most assembler instructions represent machine
4 bytes (word) – Behaviors: load or store instructions one-to-one
• Register:– Load: destination– Store: source • Pseudo instructions (instructions in blue): figments of Machine code:
• Memory operand: offset(base register) – offset: short the assembler’s imagination – Help programmer – 0x02324020
integer number – Byte address: each address identifies Need to be converted into standard instructions Some opcode fields
an 8-bit byte – “words” are aligned in memory (address Procedure calling what is machine code of following instruction lw
Example: assume that $s0 and $s1 are storing values
must be multiple of 4) • Caller vs. Callee • Steps required to call a procedure – $t0, 32($s3)
0x12345678 and 0xCAFEFACE, respectively. What is
Memory operand Place parameters in registers – Transfer control to – I-format is used to encode the above instruction
value of $S2 after each following instructions
Memory address = < offset > + value( < base register > ) procedure – Acquire storage for procedure – Perform
1. sll $s2, $s0, 4 2. and $s2, $s0, $s1
Example: given the following memory map, assume procedure’s operations – Place result in register for
3. or $s2, $s0, $s1 4. andi $s2, $s0, 2020
that $s0 stores value of 8. Which is the memory caller – Return to place of call
1. 0x23456780 2. 0x02345248 0x8E680020
operand used to access the byte storing value of 0x9A? Machine instructions
3. 0xDAFEFEFE 4. 0x00000660 PC-relative addressing
Instructions are encoded in binary – Called machine code
Exercise: Find the value for $t2 after each following • Use for encoding bne and beq instructions
• MIPS instructions – Encoded as 32-bit instruction words
sequence of instructions if the values for register $t0 • Target address (the instruction associated with the
• Answer: and $t1 are – Small number of formats encoding operation code
label) calculated based on PC - program counter
– Address of the byte storing value of 0x9A is 12 a) $t0 = 0xAAAAAAAA, $t1 = 0x12345678 (opcode), register numbers, …– Regularity!
register– PC is already increased by 4
– If we use $s0 as the base register, offset = 12 − 8 = 4 b) $t0 = 0xF00DD00D, $t1 = 0x11111111 • Representing instructions:– Instruction format: R, I, and J
target address = PC + address field × 4
– Memory operand: 4($s0) 4th group: conditional branch instructions – Opcode: predefined (check the reference card)
• When encoding branch conditional instructions,
Memory operands • Branch to a label if a condition is true; otherwise, Operands:• Register numbers: predefined (check the
address field should be calculated by
• Main memory used for composite data continue sequentially • Only two standard conditional reference card) • Immediate: integer to binary
Address field = (target address − PC)/4