Lecture 05-06 Motivation And Background Of MIPS Instruction Set .

Lecture 05-06 Motivation and Background of MIPS Instruction Set Architecture (ISA) " Suggested reading:" (HP Chapter 2.1-2.3 & 2.5-2.7)" (do not need to read HP Chapter 2.4)" 1"

Processor components" Multicore processors and programming" Processor comparison" vs." CSE 30321" Writing more " efficient code" The right HW for the right application" HLL code translation" 2"

Fundamental lesson(s)" Today I’ll explain what an ISA in a typical, modern microprocessor looks like" – How memory references are handled / encoded, etc. in the MIPS ISA (our example) are fairly representative of others too (e.g. the ARM ISA)." 3"

Why it’s important " In this lecture, you'll get a very good sense as to what kind of assembly code is generated when you compile some HLL code" Later in the semester, I'll show you what HLL code you write can SIGNIFICANTLY impact its execution time" – Should already start to see this in lab" To really take advantage of this, need to understand how HLL code gets mapped to assembly code how assembly suggests how HW actually performs a computation" 4"

Quick recap" Context" – Lecture 01:" Introduction to the course" – Lectures 02-03:" Introduction to programmable processors" – (6-instruction some ARM ISA)" – Lecture 04 (and part of Lecture 05):" How to quantify impact of design decisions" – Lecture 05: (MIPS ISA)" Apply / revisit ideas introduced in Lectures 02, 03, but use context of modern ISA" Use benchmark techniques from Lecture 04 with this material and throughout the rest of the course" 5"

A more sophisticated ISA" Shortcomings of the simple processor" – – – – Only 16 bits for data and instruction" Data range can be too small" Addressable memory is small" Only “room” for 16 instruction opcodes" MIPS ISA: 32-bit RISC processor" – A representative RISC ISA " Most modern microprocessors are RISC-like including ARMs" (RISC – Reduced Instruction Set Computer)" – A fixed-length, regularly encoded instruction set and uses a load/store data model " – Used by NEC, Cisco, Silicon Graphics, Sony, Nintendo " and more" 6"

Instruction" Encoding" 6-instruction vs. MIPS" q 6-instruction processor:" Add instruction: 0010 ra3ra2ra1ra0 rb3rb2rb1rb0 rc3rc2rc1rc0" Add Ra, Rb, Rc—specifies the operation RF[a] RF[b] RF[c] q MIPS processor:" Assembly: add 9, 7, 8 # add rd, rs, rt: RF[rd] RF[rs] RF[rt]" " "" " " 31 " " " op (6) " " 26 25 rs (5) " " 21 20 rt (5) " " " " 16 15 " " 11 10 rd (5) " " " "(add: op func)" 6 5 shamt (5) funct (6) xxxxx x 100000 32 0 " Machine:" B: 000000 00111 01000 01001 D: 0 7 8 9 7"

Instruction" Encoding" 6-instruction vs. MIPS" q 6-instruction processor:" Sub instruction: 0111 ra3ra2ra1ra0 rb3rb2rb1rb0 rc3rc2rc1rc0" SUB Ra, Rb, Rc—specifies the operation RF[a] RF[b] – RF[c] q A MIPS subtract" Assembly: sub 9, 7, 8 # sub rd, rs, rt: RF[rd] RF[rs]-RF[rt]" " "" "" " " " 31 op (6) " 26 25 rs (5) " 21 20 rt (5) " " 16 15 " 11 10 rd (5) " 6 5 shamt (5) funct (6) xxxxx x 100010 34 " " 0 " Machine:" B: 000000 00111 01000 01001 D: 0 7 8 9 8"

6-instruction vs. MIPS" Datapat h" Path of Add from start to finish." 9"

6-instruction vs. MIPS" Datapat h" Path of Add from start to finish." 10"

Note:" We’ll discuss the specifics of the MIPS ISA in more detail shortly ! ! but first, I’ll go through a few slides on how MIPSlike (i.e. RISC) ISAs came to be.! 11"

Instructions Sets" An instruction set specifies a processor’s functionality" – what operations it supports " – what storage mechanisms it has & how they are accessed " – how the programmer/compiler communicates programs to processor " ISA: “interface” between HLL and HW" ISAs may have different syntax (6-instruction vs. MIPS), but can still support same general types of operation (i.e. register-register)" 12"

Instruction Set Architecture" Instructions must have some basic functionality:" – Access memory (read and write)" – Perform ALU operations (add, multiply, etc.)" – Implement control flow (jump, branch, etc.)" I.e. to take you back to the beginning of a loop" Significant difference often how memory, data addressed" – Operand location" (stack, memory, register)" – Addressing modes" (computing memory addresses)" – (Let’s digress on the board and preview how MIPS does a load)" – (Compare to 6-instruction processor?)" 13"

What makes a good instruction set" implementability " – supports a (performance/cost) range of implementations " implies support for high performance implementations " programmability " – easy to express programs (for human and/or compiler) " backward/forward compatibility " – implementability & programmability across generations " e.g., x86 generations: 8086, 286, 386, 486, Pentium, Pentium II, Pentium III, Pentium 4. " 14"

Example: range of cost implementations" 32-bit ARM not unlike 32-bit MIPS" ARM and Thumb-2 Instruction Set Quick Reference Card Operation § Multiply Multiply and accumulate and subtract T2 unsigned long unsigned accumulate long unsigned double accumulate long 6 Signed multiply long and accumulate long 16 * 16 bit 5E 32 * 16 bit 5E 16 * 16 bit and accumulate 5E 32 * 16 bit and accumulate 5E 16 * 16 bit and accumulate long 5E Dual signed multiply, add 6 and accumulate 6 and accumulate long 6 Dual signed multiply, subtract 6 and accumulate 6 and accumulate long 6 Signed top word multiply 6 and accumulate 6 s/instruction-set-architectures.php" and subtract 6 with internal 40-bit accumulate XS packed halfword XS halfword XS Divide Signed or Unsigned RM Move Move data NOT top T2 wide T2 40-bit accumulator to register XS http://www.arm.com/images/pro-A7TDMI-s.gif" http://www.arm.com/images/armpp/nook2 %281%29.jpg" register to 40-bit accumulator XS Shift Arithmetic shift right Logical shift left Assembler MUL{S} Rd, Rm, Rs MLA{S} Rd, Rm, Rs, Rn MLS Rd, Rm, Rs, Rn UMULL{S} RdLo, RdHi, Rm, Rs UMLAL{S} RdLo, RdHi, Rm, Rs UMAAL RdLo, RdHi, Rm, Rs 1.4 ARM7TDMI Core Diagram SMULL{S} RdLo, RdHi, Rm, Rs A[31:0] ABERm, Rs I ALE RdHi, SMLAL{S} RdLo, n c SMULxy Rd, Rm, Rs r Address Register e SMULWy Rd, Rm, Rs m P e n SMLAxy Rd, Rm,C Rs, Address Rn t Incrementer e b SMLAWy Rd, Rm, Rs, Rn r u SMLALxy RdLo, s RdHi, Rm, Rs b u Register Bank s SMUAD{X} Rd, (31Rm, x 32-bitRs registers) A (6 status registers) SMLAD{X} Rd, Rm, Rs, Rn L U SMLALD{X} RdLo, RdHi, Rm, Rs b u Rd, Rm, Rs SMUSD{X} s 32 x 8 Multiplier SMLSD{X} Rd, ARm, Rs, Rn b SMLSLD{X} RdLo, RdHi, Rm, Rs u s SMMUL{R} Rd, Rm, Rs Barrel SMMLA{R} Rd, Rm, Rs,Shifter Rn SMMLS{R} Rd, Rm, Rs, Rn MIA Ac, Rm, Rs 32-bit ALU MIAPH Ac, Rm, Rs MIAxy Ac, Rm, Rs op Rd, Rn, Rm MOV{S} Rd, Write Operand2 Data Register MVN{S} Rd, Operand2 MOVT Rd, # imm16 nENOUT nENIN MOV Rd, # imm16 DBE D[31:0] MRA RdLo, RdHi, Ac MAR Ac, RdLo, RdHi ASR{S} Rd, Rm, Rs sh LSL{S} Rd, Rm, Rs sh S updates N Z C* N Z C* Action Rd : (Rm * Rs)[31:0] Rd : (Rn (Rm * Rs))[31:0] Rd : (Rn – (Rm * Rs))[31:0] N Z C* V* RdHi,RdLo : unsigned(Rm * Rs) Introduction N Z C* V* RdHi,RdLo : unsigned(RdHi,RdL RdHi,RdLo : unsigned(RdHi R N Z C* V* RdHi,RdLo : signed(Rm * Rs) N Z C* V* RdHi,RdLo : signed(RdHi,RdLo Scan Rd : Rm[x] * Rs[y] Control Rd : (Rm * Rs[y])[47:16] DBGRQI Rd : Rn Rm[x] * Rs[y] BREAKPTI Rd : Rn (Rm * Rs[y])[47:16] DBGACK ECLK RdHi,RdLo : RdHi,RdLo Rm[x nEXEC ISYNC Rd : Rm[15:0] * RsX[15:0] Rm BL[3:0] APE Rd : Rn Rm[15:0] * RsX[15:0] MCLK nWAIT RdHi,RdLo : RdHi,RdLo Rm[1 nRW B Rd : Rm[15:0] MAS[1:0]* RsX[15:0] – Rm nIRQ Instruction b Rd : Rn Rm[15:0] * RsX[15:0] Decoder nFIQ u & nRESET s Control RdHi,RdLo : RdHi,RdLo Rm[1 ABORT Logic nTRANS Rd : (RmnMREQ * Rs)[63:32] nOPC Rd : Rn SEQ (Rm * Rs)[63:32] LOCK Rd : Rn –nCPI (Rm * Rs)[63:32] CPA Ac : Ac Rm * Rs CPB nM[4:0] Ac : Ac Rm[15:0] * Rs[15:0] TBE TBIT Ac : Ac HIGHZ Rm[x] * Rs[y] Rd : Rn / Rm Pipeline N &ZInstruction C Rd : Operand2 Read Data Register & Thumb Instruction Decoder N Z C Rd : 0xFFFFFFFF EOR Operand Rd[31:16] : imm16, Rd[15:0] un Rd[15:0] : imm16, Rd[31:16] 0 RdLo : Ac[31:0], RdHi : Ac[39 Figure 1-2: ARM7TDMI core Ac[31:0] : RdLo, Ac[39:32] : R N Z C Rd : ASR(Rm, Rs sh) N Z C Rd : LSL(Rm, Rs sh) Open Access Simplified (16-bit) ARMs available too" http://infocenter.arm.com/help/index.jsp?topic /com.arm.doc.ddi0210c/index.html" MIPS: Mul 9, 7, 8 # mul rd, rs, rt: RF[rd] RF[rs]*RF[rt]" 15"

Programmability" a history of programmability " – pre - 1975: most code was hand-assembled " – 1975 – 1985: most code was compiled " “Programming” literally sitting down and writing machine code" but people thought that hand-assembled code was superior " – 1985 – present: most code was compiled " and compiled code was at least as good as hand-assembly " over time, a big shift in what “programmability” means" 16"

pre-1975: Human Programmability" focus: instruction sets that were easy for humans to program" – ISA semantically close to high-level language (HLL) " closing the “semantic gap” " – semantically heavy complex instructions " e.g., the VAX had instructions for polynomial evaluation " – people thought computers would someday execute HLL directly " never materialized " Let’s look at an example" 17"

The Quadratic Forumla" 2 b b 4ac x 2a Approach 1:" QUAD Plus X1, a, b, c" QUAD Minus X2, a, b, c" or" QUAD X1, X2, a, b, c" Generally requires more specialized HW! A" Approach 2:" Mult R1, b, b" Mult R2, a, c" Multi R2, R2, 4" Sub R3 R1, R2" Sqrt R3, R3" Mult, R4, a, 2" Mult R5, b, -1" Add R6, R5, R3" Div R6, R6, R4 Sub R7, R5, R3" Div R7, R7, R4 "# result 1" "# result 2" Provides primitives, not solutions! 18"

Storage Model: Register-Register (Ld/St)" load R1,A load R2,B add R3,R1,R2 R1 M[A]; ! R2 M[B]; ! R3 R1 R2; ! store C,R3 M[C] R3; " Again, typical of a modern ISA and the focus in this course " – load/store architecture: ALU operations on regs only " (minus) poor code density " (plus) easy decoding, operand symmetry " (plus) deterministic length ALU operations " (plus) fast decoding helps pipelining (later)" – 1960’s and onwards " RISC machines: Alpha, MIPS, PowerPC, ARM" 19"

Instruction Formats" fixed length (most common: 32-bits) " – (plus) easy for pipelining (e.g. overlap) and for multiple issue (superscalar)" don’t have to decode current instruction to find next instruction " – (minus) not compact" Does the MIPS add “waste” bits? " Operation" Address" Field 1" Address" Field 2" Address" Field 3" variable length " – (plus) more compact " – (minus) hard (but do-able) to efficiently decode" (important later)" Operation &" # of operands" Address" Address" Specifier 1" Field 1" ." Address" Address" Specifier n" Field n" 20"

Present Day: Compiled Assembly" Consider a representative set of passes" Function:" Dependencies:" Transform HLL to common, intermediate form" Front end language specific" Representative examples:" Procedure in-lining, loop transformations, etc." High-level optimizations" (things any HLL code might benefit from)" Language dependent, machine independent" Somewhat language dependent, largely machine independent" Representative example:" Register allocation" Global optimizer" Small language dependencies, some machine dependencies (i.e. register counts)" Detailed instruction selection and machine-dependent optimizations" Code generator" Highly machine dependent, language independent" 21"

More specifics about:" MIPS instruction syntax" Register usage" " NOW: INTRODUCTION TO MIPS ISA" 22"

MIPS registers" q 32x32-bit GPRs (General purpose registers)" n 0 zero (therefore only 31 GPRs)" n 1 at (reserved for assembler)" 32 bits 0 r0 r1 . n 2 - 3 v0 - v1 (return values)" n 4 - 7 a0 - a3 (arguments)" r31 n 8 - 15 t0 - t7 (temporaries)" n 16 - 23 s0 - s7 (saved)" n 24 - 25 t8 - t9 (more temporaries)" bn-1 . b0 PC n 26 - 27 k0 - k1 (reserved for OS)" n n n n 28 gp (global pointer)" 29 sp (stack pointer)" 30 fp (frame pointer)" 31 ra (return address)" 32x32-bit floating point registers (paired double precision) Program counter Status, Cause, BadVAddr, EPC ." a bit Let’s think ahead 23"