Computer Organization CS224 - Bilkent University

Computer Organization CS224 - Bilkent University

Computer Organization CS224 Fall 2011 Chapter 2 c With thanks to M.J. Irwin, D. Patterson, and J. Hennessy for some lecture slide contents CS224 Fall 2011 Chapter 2c Branch instructions specify Opcode, two registers, target address Most branch targets are near branch Forward or backward op rs rt constant or address 6 bits 5 bits 5 bits 16 bits

PC-relative addressing Target address = PC + offset 4 PC already incremented by 4 by this time CS224 Fall 2011 Chapter 2c 2.10 MIPS Addressing for 32-Bit Immediates and Addresses Branch Addressing Other Control Flow Instructions MIPS also has an unconditional branch instruction or jump instruction: j label #go to label Instruction Format (J Format): 0x02 26-bit address from the low order 26 bits of the jump instruction 26 00 32

4 PC CS224 Fall 2011 Chapter 2c 32 Jump Addressing Jump (j and jal) targets could be anywhere in text segment Encode full address in instruction op address 6 bits 26 bits Pseudo-Direct jump addressing Target address = PC3128 : (address 4) CS224 Fall 2011 Chapter 2c Target Addressing Example Loop code from earlier example

Assume Loop at location 80000 $t1, $s3, 2 80000 0 0 19 9 2 0 add $t1, $t1, $s6 80004 0 9 22 9 0 32 lw

$t0, 0($t1) 80008 35 9 8 0 bne $t0, $s5, Exit 80012 5 8 21 2 addi $s3, $s3, 1 80016 8 19 19 1 j

80020 2 Loop: sll Loop Exit: CS224 Fall 2011 Chapter 2c 80024 20000 Aside: Branching Far Away What if the branch destination is further away than can be captured in 16 bits? The assembler comes to the rescue it inserts an unconditional jump to the branch target and inverts the condition beq $s0, $s1, L1_far becomes bne $s0, $s1, L2 j L1_far L2: CS224 Fall 2011 Chapter 2c Addressing Mode Summary

CS224 Fall 2011 Chapter 2c MIPS Organization So Far Processor Memory Register File src1 addr src2 addr dst addr write data 5 5 5 11100 src1 data 32 32 registers ($zero - $ra) read/write addr src2 32 data 32 32 32 bits

branch offset 32 PC Fetch PC = PC+4 Exec 32 Add 4 32 Add read data 32 32 32 write data 32 Decode 230 words 32 32 ALU 32 32 4 0

5 1 32 bits byte address (big Endian) CS224 Fall 2011 Chapter 2c 6 2 7 3 01100 01000 00100 00000 word address (binary) MIPS Instruction Classes Distribution Frequency of MIPS instruction classes for SPEC2006 Instruction Class Frequency Integer Ft. Pt. Arithmetic 16%

48% Data transfer 35% 36% Logical 12% 4% Cond. Branch 34% 8% Jump 2% 0% CS224 Fall 2011 Chapter 2c Two processors sharing an area of memory P1 writes, then P2 reads Data race if P1 and P2 dont synchronize

- Result depends of order of accesses Hardware support required Atomic read/write memory operation No other access to the location allowed between the read and write Could be a single instruction E.g., atomic swap of register memory Or an atomic pair of instructions CS224 Fall 2011 Chapter 2c 2.11 Parallelism and Instructions: Synchronization Synchronization Atomic Exchange Support Need hardware support for synchronization mechanisms to avoid data races where the results of the program can change depending on how events happen to occur

Two memory accesses from different threads to the same location, and at least one is a write Atomic exchange (atomic swap) interchanges a value in a register for a value in memory atomically, i.e., as one operation (instruction) Implementing an atomic exchange would require both a memory read and a memory write in a single, uninterruptable instruction. An alternative is to have a pair of specially configured instructions ll $t1, 0($s1) #load linked sc $t0, 0($s1) #store conditional CS224 Fall 2011 Chapter 2c Atomic Exchange with ll and sc If the contents of the memory location specified by the ll are changed before the sc to the same address occurs, the sc fails (returns a zero) try: add $t0, $zero, $s4 ll $t1, 0($s1) sc $t0, 0($s1)

beq $t0, $zero, try add $s4, $zero, $t1 #$t0=$s4 (exchange value) #load memory value to $t1 #try to store exchange #value to memory, if fail #$t0 will be 0 #try again on failure #load value in $s4 If the value in memory between the ll and the sc instructions changes, then sc returns a 0 in $t0 causing the code sequence to try again. CS224 Fall 2011 Chapter 2c C program compiler assembly code assembler object code library routines linker machine code executable loader memory CS224 Fall 2011 Chapter 2c 2.12 Translating and Starting a Program The C Code Translation Hierarchy

Assembler Pseudoinstructions Most assembler instructions represent machine instructions one-to-one Pseudoinstructions: figments of the assemblers imagination move $t0, $t1 add $t0, $zero, $t1 blt $t0, $t1, L slt $at, $t0, $t1 bne $at, $zero, L $at (register 1): assembler temporary CS224 Fall 2011 Chapter 2c Producing an Object Module Assembler (or compiler) translates program into machine instructions Provides information for building a complete program from the pieces Header: described contents of object module Text segment: translated instructions

Static data segment: data allocated for the life of the program Relocation info: for contents that depend on absolute location of loaded program Symbol table: global definitions and external refs Debug info: for associating with source code CS224 Fall 2011 Chapter 2c Linking Object Modules Produces an executable image 1.Merges segments 2.Resolve labels (determine their addresses) 3.Patch location-dependent and external refs Could leave location dependencies for fixing by a relocating loader But with virtual memory, no need to do this Program can be loaded into absolute location in virtual memory space

CS224 Fall 2011 Chapter 2c Loading a Program Load from image file on disk into memory 1. Read header to determine segment sizes 2. Create virtual address space 3. Copy text and initialized data into memory - Or set page table entries so they can be faulted in 4. Set up arguments on stack 5. Initialize registers (including $sp, $fp, $gp) 6. Jump to startup routine - Copies arguments to $a0, and calls main - When main returns, do exit syscall CS224 Fall 2011 Chapter 2c Dynamic Linking Only link/load library procedure when it is called Requires procedure code to be relocatable Avoids image bloat caused by static linking of all (transitively) referenced libraries Automatically picks up new library versions CS224 Fall 2011 Chapter 2c Lazy Linkage

Indirection table Stub: loads routine ID, jumps to linker/loader Linker/loader code Dynamically mapped code CS224 Fall 2011 Chapter 2c Starting Java Applications Simple portable instruction set for the JVM Compiles bytecodes of hot methods into native code for host machine CS224 Fall 2011 Chapter 2c Interprets bytecodes Illustrates use of assembly instructions for a C bubble sort function Swap procedure (leaf) void swap(int v[], int k) {

int temp; temp = v[k]; v[k] = v[k+1]; v[k+1] = temp; } v in $a0, k in $a1, temp in $t0 CS224 Fall 2011 Chapter 2c 2.13 A C Sort Example to Put It All Together C Sort Example The Procedure Swap swap: sll $t1, $a1, 2 # $t1 = k * 4 add $t1, $a0, $t1 # $t1 = v+(k*4) # (address of v[k]) lw $t0, 0($t1) # $t0 (temp) = v[k] lw $t2, 4($t1) # $t2 = v[k+1] sw $t2, 0($t1) # v[k] = $t2 (v[k+1]) sw $t0, 4($t1)

# v[k+1] = $t0 (temp) jr $ra # return to calling routine CS224 Fall 2011 Chapter 2c The Sort Procedure in C Non-leaf (calls swap) void sort (int v[], int n) { int i, j; for (i = 0; i < n; i += 1) { for (j = i 1; j >= 0 && v[j] > v[j + 1]; j -= 1) { swap(v,j); } } } v in $a0, n in $a1, i in $s0, j in $s1 CS224 Fall 2011 Chapter 2c The Procedure Body move move move for1tst: slt beq addi for2tst: slti bne sll

add lw lw slt beq move move jal addi j exit2: addi j CS224 Fall 2011 Chapter 2c $s2, $a0 $s3, $a1 $s0, $zero $t0, $s0, $s3 $t0, $zero, exit1 $s1, $s0, 1 $t0, $s1, 0 $t0, $zero, exit2 $t1, $s1, 2 $t2, $s2, $t1 $t3, 0($t2) $t4, 4($t2) $t0, $t4, $t3 $t0, $zero, exit2 $a0, $s2 $a1, $s1 swap $s1, $s1, 1 for2tst $s0, $s0, 1 for1tst # #

# # # # # # # # # # # # # # # # # # # save $a0 into $s2 Move save $a1 into $s3 params i = 0 $t0 = 0 if $s0 $s3 (i n) Outer loop go to exit1 if $s0 $s3 (i n) j = i 1 $t0 = 1 if $s1 < 0 (j < 0) go to exit2 if $s1 < 0 (j < 0) $t1 = j * 4 Inner loop $t2 = v + (j * 4) $t3 = v[j] $t4 = v[j + 1] $t0 = 0 if $t4 $t3 go to exit2 if $t4 $t3 1st param of swap is v (old $a0) Pass

2nd param of swap is j params call swap procedure & call j = 1 Inner loop jump to test of inner loop i += 1 jump to test of outer loop Outer loop The Full Procedure sort: exit1: addi $sp,$sp, 20 sw $ra, 16($sp) sw $s3,12($sp) sw $s2, 8($sp) sw $s1, 4($sp) sw $s0, 0($sp) lw $s0, 0($sp) lw $s1, 4($sp) lw $s2, 8($sp) lw $s3,12($sp) lw $ra,16($sp) addi $sp,$sp, 20 jr $ra CS224 Fall 2011 Chapter 2c # make room on stack for 5 registers # save $ra on stack # save $s3 on stack # save $s2 on stack

# save $s1 on stack # save $s0 on stack # procedure body # # # # # # # restore $s0 from stack restore $s1 from stack restore $s2 from stack restore $s3 from stack restore $ra from stack restore stack pointer return to calling routine Compiler Benefits Comparing performance for bubble (exchange) sort To sort 100,000 words with the array initialized to random values on a Pentium 4 with a 3.06 clock rate, a 533 MHz system bus, with 2 GB of DDR SDRAM, using Linux version 2.4.20 gcc opt Relative performance Clock cycles (M)

Instr count (M) CPI None 1.00 158,615 114,938 1.38 O1 (medium) 2.37 66,990 37,470 1.79 O2 (full) 2.38 66,521 39,993 1.66 O3 (proc mig) 2.41

65,747 44,993 1.46 The unoptimized code has the best CPI, the O1 version has the lowest instruction count, but the O3 version is the fastest. Why? CS224 Fall 2011 Chapter 2c Effect of Compiler Optimization Compiled with gcc for Pentium 4 under Linux Relative Performance 3 140000 Instructioncount 120000 2.5 100000 2 80000 1.5 60000 1

40000 0.5 20000 0 0 none 180000 160000 140000 120000 100000 80000 60000 40000 20000 0 O1 O2 none O3 Clock Cycles O1 O2 O3 O2

O3 CPI 2 1.5 1 0.5 0 none O1 CS224 Fall 2011 Chapter 2c O2 O3 none O1 Sorting in C versus Java Comparing performance for two sort algorithms in C and Java (BubbleSort vs. Quicksort) The JVM/JIT is Sun/Hotspot version 1.3.1/1.3.1 Method Opt Bubble

Quick Relative performance Speedup Quick vs. Bubble C Compiler None 1.00 1.00 2468 C Compiler O1 2.37 1.50 1562 C Compiler

O2 2.38 1.50 1555 C Compiler O3 2.41 1.91 1955 Java Interpreted 0.12 0.05 1050 Java JIT compiler 2.13 0.29 338

Observations? CS224 Fall 2011 Chapter 2c Effect of Language and Algorithm Bubblesort Relative Performance 3 2.5 2 1.5 1 0.5 0 C/ none C/ O1 C/ O2 C/O3 Java/ int J ava/ J IT Quicksort Relative Performance 2.5 2 1.5 1 0.5 0 C/ none C/ O1

C/ O2 C/ O3 Java/ int J ava/J IT Quicksort vs. Bubblesort Speedup 3000 2500 2000 1500 1000 500 0 C/ none CS224 Fall 2011 Chapter 2c C/ O1 C/ O2 C/ O3 Java/ int Java/ JIT Lessons Learned Instruction count and CPI are not good performance indicators in isolation

Compiler optimizations are sensitive to the algorithm Java/JIT compiled code is significantly faster than JVM interpreted Comparable to optimized C in some cases Nothing can fix a dumb algorithm! CS224 Fall 2011 Chapter 2c Array indexing involves Multiplying index by element size Adding to array base address Pointers correspond directly to memory addresses Can avoid indexing complexity CS224 Fall 2011 Chapter 2c 2.14 Arrays versus Pointers Arrays vs. Pointers

Example: Clearing an Array clear1(int array[], int size) { int i; for (i = 0; i < size; i += 1) array[i] = 0; } move $t0,$zero loop1: sll $t1,$t0,2 add $t2,$a0,$t1 clear2(int *array, int size) { int *p; for (p = &array[0]; p < &array[size]; p = p + 1) *p = 0; } # i = 0 move $t0,$a0 # p = & array[0] # $t1 = i * 4 sll $t1,$a1,2 # $t1 = size * 4 # $t2 = add $t2,$a0,$t1 # $t2 = # &array[i]

sw $zero, 0($t2) # array[i] = 0 # &array[size] loop2: sw $zero,0($t0) # Memory[p] = 0 addi $t0,$t0,1 # i = i + 1 addi $t0,$t0,4 slt $t3,$t0,$a1 # $t3 = slt $t3,$t0,$t2 # $t3 = # (i < size) bne $t3,$zero,loop1 # if () # goto loop1 CS224 Fall 2011 Chapter 2c # p = p + 4 #(p<&array[size]) bne $t3,$zero,loop2 # if () # goto loop2 Comparison of Array vs. Pointer Versions Multiply strength reduced to shift

Both versions use sll instead of mul Array version requires shift to be inside loop Part of index calculation for incremented i c.f. incrementing pointer Compiler can achieve same effect as manual use of pointers Induction variable elimination Better to make program clearer and safer Optimizing compilers do these, and many more! See Sec. 2.15 on CD-ROM CS224 Fall 2011 Chapter 2c ARM: the most popular embedded core

Similar basic set of instructions to MIPS ARM MIPS 1985 1985 Instruction size 32 bits 32 bits Address space 32-bit flat 32-bit flat Data alignment Aligned Aligned 9 3 15 32-bit 31 32-bit Memory mapped Memory mapped

Date announced Data addressing modes Registers Input/output CS224 Fall 2011 Chapter 2c 2.16 Real Stuff: ARM Instructions ARM & MIPS Similarities Compare and Branch in ARM Uses condition codes for result of an arithmetic/logical instruction Negative, zero, carry, overflow are stored in program status Has compare instructions to set condition codes without keeping the result Each instruction can be conditional Top 4 bits of instruction word: condition value Can avoid branches over single instructions, save code space and execution time

CS224 Fall 2011 Chapter 2c Instruction Encoding CS224 Fall 2011 Chapter 2c Evolution with backward compatibility 8080 (1974): 8-bit microprocessor - Accumulator, plus 3 index-register pairs 8086 (1978): 16-bit extension to 8080 - Complex instruction set (CISC) 8087 (1980): floating-point coprocessor - Adds FP instructions and register stack 80286 (1982): 24-bit addresses, MMU - Segmented memory mapping and protection 80386 (1985): 32-bit extension (now IA-32) - Additional addressing modes and operations - Paged memory mapping as well as segments CS224 Fall 2011 Chapter 2c 2.17 Real Stuff: x86 Instructions

The Intel x86 ISA The Intel x86 ISA Further evolution i486 (1989): pipelined, on-chip caches and FPU - Compatible competitors: AMD, Cyrix, Pentium (1993): superscalar, 64-bit datapath - Later versions added MMX (Multi-Media eXtension) instructions - The infamous FDIV bug Pentium Pro (1995), Pentium II (1997) - New microarchitecture (see Colwell, The Pentium Chronicles) Pentium III (1999) - Added SSE (Streaming SIMD Extensions) and associated registers Pentium 4 (2001) - New microarchitecture - Added SSE2 instructions CS224 Fall 2011 Chapter 2c

The Intel x86 ISA And further AMD64 (2003): extended architecture to 64 bits EM64T Extended Memory 64 Technology (2004) - AMD64 adopted by Intel (with refinements) - Added SSE3 instructions Intel Core (2006) - Added SSE4 instructions, virtual machine support AMD64 (announced 2007): SSE5 instructions - Intel declined to follow, instead Advanced Vector Extension (announced 2008) - Longer SSE registers, more instructions If Intel didnt extend with compatibility, its competitors would! Technical elegance market success CS224 Fall 2011 Chapter 2c Basic x86 Registers CS224 Fall 2011 Chapter 2c

Basic x86 Addressing Modes Two operands per instruction Source/dest operand Second source operand Register Register Register Immediate Register Memory Memory Register Memory Immediate Memory addressing modes Address in register

Address = Rbase + displacement Address = Rbase + 2scale Rindex (scale = 0, 1, 2, or 3) Address = Rbase + 2scale Rindex + displacement CS224 Fall 2011 Chapter 2c x86 Instruction Encoding Variable length encoding Postfix bytes specify addressing mode Prefix bytes modify operation: - Operand length, repetition, locking, CS224 Fall 2011 Chapter 2c Implementing IA-32 Complex instruction set makes implementation difficult Hardware translates instructions to simpler microoperations - Simple instructions: 1-to-1 - Complex instructions: 1-to-many

Microengine similar to RISC Market share makes this economically viable Comparable performance to RISC Compilers avoid the complex instructions CS224 Fall 2011 Chapter 2c Powerful instruction higher performance Fewer instructions required But complex instructions are hard to implement - May slow down all instructions, including simple ones Compilers are good at making fast code from simple instructions Use assembly code for high performance

But modern compilers are better at dealing with modern processors More lines of code more errors and less productivity CS224 Fall 2011 Chapter 2c 2.18 Fallacies and Pitfalls Fallacies Fallacies Backward compatibility instruction set doesnt change True: Old instructions never die (Backwards compatibility) But new instructions are certainly added ! x86 instruction set CS224 Fall 2011 Chapter 2c Concluding Remarks Stored program concept (Von Neumann architecture) means everything is just bitsnumbers, characters, instructions, etcall stored in and fetched from memory 4 design principles for instruction set architectures (ISA)

Simplicity favors regularity Smaller is faster Make the common case fast Good design demands good compromises CS224 Fall 2011 Chapter 2c Concluding Remarks MIPS ISA offers necessary support for HLL constructs SPEC performance measures instruction execution in benchmark programs Instruction class MIPS examples (HLL examples) SPEC2006 Int SPEC2006 FP Arithmetic add, sub, addi (ops used in assignment statements)

16% 48% Data transfer lw, sw, lb, lbu, lh, lhu, sb, lui (references to data structures, e.g. arrays) 35% 36% Logical and, or, nor, andi, ori, sll, srl (ops used in assigment statements) 12% 4% Cond. Branch beq, bne, slt, slti, sltiu (if statements and loops) 34% 8% Jump j, jr, jal (calls, returns, and case/switch)

2% 0% CS224 Fall 2011 Chapter 2c

Recently Viewed Presentations

  • SEL2211: Contexts Lecture 1: Introduction

    SEL2211: Contexts Lecture 1: Introduction

    It is often used as an antonym for arts and humanities by people who believe that knowledge of such things as literature, drama, music, history and so on is fundamentally different from scientific knowledge, but this view is simply mistaken.
  • The Minds and the Eyes: Two Under-Utilized Tools of the ...

    The Minds and the Eyes: Two Under-Utilized Tools of the ...

    focus Cleveland State University Established in 1964 Started as private Fenn College in 1929 Current student population: ~16,000 Degree awarded: ~4,000 per year Department of Chemistry 14 CSU and 32 CCF faculty members 5 staff members ~ 60 students in...
  • F1 for CKW - University of Florida

    F1 for CKW - University of Florida

    Ed Carlisle. Outline. Reconfigurable Multi-Core Platform. E-health and robotics case studies. Reconfigurable Computing Framework for Robotics. Leverages dynamic partial reconfiguration to fully utilize smaller devices required from tight constraints of micro UAVs. ... F1 for CKW Last modified by: Ed
  • Metric Conversions w/o Dimensional Analysis

    Metric Conversions w/o Dimensional Analysis

    Metric Conversions w/o Dimensional Analysis Just move the decimal!! Metric Conversions To change from a smaller unit to a larger unit, move the decimal point to the left. 4206 mm = _____ cm = 420.6 cm Try these….
  • WRITING - Queen Eleanor&#x27;s C of E Junior School

    WRITING - Queen Eleanor's C of E Junior School

    For this, children are expected to apply their knowledge of spelling patterns for example, words ending in - cious, -sion, -ly, -ure. These patterns are the same patterns that children have for homework. As well as the spelling patterns, the...
  • ABECEDA KOTSKE Denis Singer ABERDEEN Nekad ribarski grad

    ABECEDA KOTSKE Denis Singer ABERDEEN Nekad ribarski grad

    CONNERY SEAN Najpoznatiji škotski glumac , slavu stekao kao tajni agent 007 - James Bond . Izrazito ponosan na svoje porijeklo , na slici prilikom obnavljanja škotskog parlamenta 1999. godine . Č ČIČAK Nacionalni cvijet Škotske . D DESTILERIJE Mjesta...
  • Intro/subtitle copy here INVESTMENT PRODUCTS: NOT FDIC INSURED

    Intro/subtitle copy here INVESTMENT PRODUCTS: NOT FDIC INSURED

    Before I begin the presentation, I'd like to take just a moment to briefly introduce myself and let you know a little about my professional background and qualifications. (Briefly state your background and experience.) This presentation was put together with...
  • Principles of Supply Chain Management

    Principles of Supply Chain Management

    strategic drivers of supply chain performance in a changing world brazil executive seminar ... environment now todays supply chains are characterized by adverserial relationships between suppliers and customer pursueing opposing objectives buyers and sellers are internally focused differing ...