Designing an Instruction Set - Computer Science

Designing an Instruction Set - Computer Science

Concocting an Instruction Set omp 411 Fall 2010 move add add move rotate ... Nerd Chef at work. flour,bowl milk,bowl egg,bowl bowl,mixer mixer Read: Chapter 2.1-2.3, 2.5-2.7 9/8/10 L03 Instruction Set 1 A General-Purpose Computer The von Neumann Model Many architectural approaches to the general purpose computer have been explored. The one on which nearly all modern, practical computers is based was proposed by John von Neumann in the late 1940s. Its major components are: omp 411 Fall 2010 Input/ Output Central Processing Unit Main Memory Central Processing Unit (CPU): A device which fetches, interprets, and executes a specified set of operations called Instructions. Memory: storage of N words of W bits each, where W is a fixed architectural parameter, and N can be expanded to meet I/O: Devices for communicating with the needs. outside world. 9/8/10

L03 Instruction Set 2 Anatomy of an Instruction Computers execute a set of primitive operations called instructions Instructions specify an operation and its operands (the necessary variables to perform the operation) Operation Types of operands: immediate, Operandssource, and destination (variables, arguments, e add $t0, $t1, $t2 Why the $ on some operands? $X is a convention to denote the contents of a temporary variable named X, whereas immediate operands indicate the specified omp value 411 Fall 2010 Source Operands Destination Operand addi $t0, $t1, 1 9/8/10 Immediate Operand L03 Instruction Set 3 Meaning of an Instruction Operations are abbreviated into opcodes (1-4 letters) Instructions are specified with a very regular syntax First an opcode followed by arguments Usually the destination is next, then source arguments

(This is not strictly the case, but it is generally true) Why this order? add $t0, $t1, $t2 The instruction syntax provides operands in the same order as you would expect in a statement from a high level language. implies Analogy to high-level language like Java or C int t0, t1, t2 t0 = t1 + t2 omp 411 Fall 2010 9/8/10 L03 Instruction Set 4 Being the Machine! Generally Instructions are executed sequentially from a list Instructions execute after all previous instructions have completed, therefore their results are available to the next instruction But, you may see exceptions to these rules Instructions add $t0, $t1, $t1 add $t0, $t0, $t0 add $t0, $t0, $t0 sub $t1, $t0, Variables $t0: 0 122448 What is this program doing? $t1: 6 42 $t2: 8 $t3: 10 $t1

omp 411 Fall 2010 9/8/10 L03 Instruction Set 5 Analyzing the Machine! Repeat the process treating the variables as unknowns Knowing what the program does allows us to write down its specification, and give it a meaningful name The instruction sequence is now a general purpose tool Instructions times7: add $t0, $t1, $t1 add $t0, $t0, Variables $t0: w2x4x 8x $t1: x 7x $t2: y $t3: z $t0 add $t0, $t0, $t0 sub $t1, $t0, $t1 omp 411 Fall 2010 9/8/10 L03 Instruction Set 6 Looping the Flow Operations to change the flow of sequential execution A jump instruction with opcode j The operand refers to a label of some other instruction Instructions times7: add $t0, $t1, $t1 add $t0, $t0, An infinite loop $t0 add $t0, $t0, $t0

sub $t1, $t0, Variables $t0: w8x56x392x $t1: x 7x49x343x $t2: y $t3: z $t1 j times7 omp 411 Fall 2010 9/8/10 L03 Instruction Set 7 Open Issues in our Simple Model WHERE are INSTRUCTIONS stored? HOW are instructions represented? WHERE are VARIABLES stored? How are labels associated with particular instructions? How do you access more complicated variable types like Arrays? Structures? Objects? Where does a program start executing? How does it stop? omp 411 Fall 2010 9/8/10 L03 Instruction Set 8 The Stored-Program Computer The von Neumann architecture addresses these issues of our simple programmable machine example: Instructions and Data are stored in a common memory Main Sequential semantics: To the programmer all instructions Memory

appear to be executed sequentially Key idea: Memory holds not only data, but coded instructions that make up a program. Central Processing Unit CPU fetches and executes instructions from memory ... instruct instruct ion ion instruct ion data data data The CPU is a H/W interpreter Program IS simply data for this interpreter Main memory: Single expandable resource pool - constrains both data and program size 9/8/10 omp 411 Fall 2010 L03 Instruction Set 9 Internal storage Anatomy of a von Neumann Computer control Data Paths address status Control Unit address data

instructions MEMORY +1 dest PC 1101000111011 R1 R2+R3 registers asel bsel fn operations omp 411 Fall 2010 ALU Ccs More about this stuff later! INSTRUCTIONS coded as binary data PROGRAM COUNTER or PC: Address of next instruction to be executed logic to translate instructions into control signals for data path 9/8/10 L03 Instruction Set 10 Instruction Set Architecture (ISA) Encoding of instructions raises some interesting choices... Tradeoffs: performance, compactness, programmability Uniformity. Should different instructions Be the same size? Take the same amount of time to execute?

Trend: Uniformity. Affords simplicity, speed, pipelining. Complexity. How many different instructions? What level operations? Level of support for particular software operations: array indexing, procedure calls, polynomial evaluate, etc Reduced Instruction Set Computer Our representative example:simple the MIPS architecture! (RISC) philosophy: instructions, optimized for speed omp 411 Fall 2010 9/8/10 L03 Instruction Set 11 MIPS Programming Model a representative simple RISC machine Processor State (inside the CPU) In Comp 411 well use a clean and sufficient subset of the MIPS-32 core Instruction set. Main Memory 00 PC Addresses 31 0 r0 r1 r2 000000....0 0 3 2 1 0 4 8 32 bit words 16 (4 bytes) 20

... 32 bit words next instruction r31 fetch fetch Mem[PC] Mem[PC] PC PC = = PC PC + + 44 execute execute fetched fetched instructio instructio (may (may change change PC!) PC!) repeat! repeat! General Registers: A small scratchpad of frequently used or temporary variables omp 411 Fall 2010 Fetch/Execute Fetch/Execute loop: loop: 9/8/10 MIPS uses byte memory addresses. However, each instruction is 32-bits wide, and *must* be aligned on a multiple of 4 (word) address. Each word contains four 8-bit bytes. Addresses of L03 Instruction Set 12 consecutive instructions Some MIPs Memory Nits Memory locations are 32 bits wide BUT, they are addressable in different-sized chunks

short2 short0 8-bit chunks (bytes) 16-bit chunks (shorts) byte3 byte2 byte1 byte0 32-bit chunks (words)Addr 2 1 0 0: 3 long0 64-bit chunks (longs/double) 31 30 29 43210 4: We also frequently need8: access to individual bits! 12: 7 6 5 4 12 10 9 8 15 14 13 12 (Instructions help to do this) Every BYTE has a unique address (MIPS is a byte-addressable machine) Every instruction is one word omp 411 Fall 2010 9/8/10 long8 L03 Instruction Set 13

MIPS Register Nits There are 32 named registers [$0, $1, . $31] The operands of *all* ALU instructions are registers This means to operate on a variables in memory you must: Load the value/values from memory into a register Perform the instruction Store the result back into memory Going to and from memory can be expensive (4x to 20x slower than operating on a register) Net effect: Keep variables in registers as much as possible! 2 registers have H/W specific side-effects (ex: $0 always contains the value 0 more later) 4 registers are dedicated to specific tasks by convention 26 are available for general use Further conventions delegate tasks to other registers omp 411 Fall 2010 9/8/10 L03 Instruction Set 14 MIPS Instruction Formats All MIPs instructions fit in a single 32-bit word. Every instruction includes various fields that encode combinations of a 6-bit operation or OPCODE specifying one of < 64 basic operations escape codes to enable extended functions several 5-bit OPERAND fields, for specifying the sources and destination of the operation, usually one of the 32 registers Embedded constants (immediate values) of various sizes, 16-bits, 5-bits, and 26-bits. Sometimes treated as R-type, 3 register sham r rt rd OP signed sometimes not. t operands (2 values, sources,

func s destination) There three basic instruction I-type,are 2 register r formats: rt 16-bit constant OP operands, 16-bit s J-type, no register literal constant 26-bit constant OP operands, 26-bit literal constant omp 411 Fall 2010 9/8/10 L03 Instruction Set 15 MIPS ALU Operations mple coded operation: ADD instruction R-type:0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 op = 0x00 func = 0x20 rd = 10 rs = 11 dictating an dictating an Reg[10] ALU function Reg[11] add destination unused source rt = 9 Reg[9] fields are source set to 0 References to register contents are

prefixed by a $ to distinguish them from constants or memory addresses What we prefer to write: add $10, $11, $9 The convention with MIPS assembly (assembly language) language is to specify the destination followed by source operands. addoperand rd,first,rs, rt: Similar instructions for other ALU Reg[rd] Reg[rs] + Reg[rt] arithmetic: add, sub, operations: addu, subu, Add the contents mult, multu, div, of rs to the divu contents of rt; compare: slt, sltu store the result in 9/8/10 logical: and, or,L03 xor, nor omp 411 Fall 2010 Instruction Set 16 MIPS Shift Operations le coded operation: SHIFT LOGICAL LEFT instruction How are shifts useful? R-type:0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 op = 0x00 func = 0x00 rd = 2 unused dictating an dictating an Reg[2] ALU function set to

sll rt = 2 destination shamt = 4 0 Reg[2] dictates a source shift of 4bits Assembly: sll $2, $2, 4 sll rd, rt, shamt: This is peculiar syntax for MIPS, in this ALU instruction the rt operand precedes the rs operand. Usually, its the other way around Assembly: sllv $2, $2, $8 sllv rd, rt, rs: Reg[rd] Reg[rt] << shamt Reg[rd] Reg[rt] << Reg[rs] Shift the contents of rt to the left by shamt; store the omp 411 Fall 2010 9/8/10 Shift the contents of rt left by the contents of rs; L03 Instruction Set 17 MIPS ALU Operations with Immediate nstruction: adds register contents, signed-constant: I-type:0 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 OP = 0x08, dictating

addi rs = 11, Reg[11] source rt = 9, Reg[9] destination Symbolic version: addi $9, $11, constant field, indicating -3 as second operand (sign-3 extended!) values Similar instructions forImmediate are sign-extended addi rt, rs, imm: for arithmetic and other ALU compare operations, but Reg[rt] Reg[rs] + sxt(imm) operations: arithmetic: addi, not for logical Add the contents of rs to const; store result in rt omp 411 Fall 2010 9/8/10 addiu compare: slti, sltiu logical: andi, ori, operations. L03 Instruction Set 18 Why Built-in Constants? (Immediate) Why not put constants in memory (was common in older instruction sets)? create more hard-wired registers for constants (like $0)?

SMALL constants are used frequently (50% of How large of constants should operands) we allow for? If they are too big, In a C compiler (gcc) 52% of ALU operations involve we wont have enough bits a constant leftover for the instructions. In a circuit simulator (spice) 69% involve constants Why are there so e.g., B = B + 1; C = W & 0x00ff; A = B + 0; many different sized constants in the MIPS ISA? Couldnt the shift amount have been encoded using the I-format? ISA Design Principle: Make the common cases fast MIPS Instructions: addi $29, $29, 4 One to questions slti $8, $18,architectural 10 One way way to answer answer architectural questions is is to to andi $29, $29, 6 evaluate the consequences of different choices using evaluate

the consequences of different choices using ori $29, $29, 4 carefully carefully chosen chosen representative representative benchmarks benchmarks (programs (programs and/or and/or code code sequences). sequences). Make Make choices choices that are best according to some metric (cost, that are best according to some metric (cost, 9/8/10 omp 411 Fall 2010 L03 Instruction Set 19 How About Larger Constants? In order to load a 32-bit constant into a register a two instruction sequence is used, load upper immediate lui $8, 1010101010101010 1010101010101010 0000000000000000 Then must get the lower order bits right, Reminder: In i.e., MIPS, Logical

ori $8, $8, 1010101010101010 1010101010101010 0000000000000000 ori omp 411 Fall 2010 0000000000000000 1010101010101010 1010101010101010 1010101010101010 9/8/10 Immediate instructions (ANDI, ORI, XORI) do not sign-extend their constant operand L03 Instruction Set 20 First MIPS Program (fragment) Suppose you want to compute the following expression: f = (g + h) (i + j) Where the variables f, g, h, i, and j are assigned to registers $16, $17, $18, $19, and $20 respectively. What is the MIPS assembly code? add $8,$17,$18 add $9,$19,$20 sub $16,$8,$9 # (g + h) # (i + j) # f = (g + h) (i + j) These three instructions are like our little ad-hoc machine from the beginning of lecture. Of course, limiting ourselves to registers for storage falls short of our ambitions.... Needed: instruction-set support for reading and writing locations in main memory... omp 411 Fall 2010 9/8/10

L03 Instruction Set 21 MIPS Load & Store Instructions MIPS is a LOAD/STORE architecture. This means that *all* data memory accesses are limited to load and store instructions, which transfer register contents to-and-from memory. ALU operations work only on registers. 16-bit signed I-type: OP rs rt constant w rt, imm(rs) Reg[rt] Mem[Reg[rs] + sxt(con Fetch into rt the contents of the memory location whose address is const plus the contents of rs Abbreviation: lw rt,imm for lw rt, w rt, imm(rs) Mem[Reg[rs] + sxt(const)] Reg imm($0) Store the contents of rt into the memory location whose address is const plus the contents of rs Abbreviation: sw rt, imm for sw rt, BYTE ADDRESSES, but lw and sw 32-bit word BYTEimm($0) ADDRESSES, but lw and sw 32-bit word access access word-aligned word-aligned addresses. addresses. The The resulting resulting lowest

lowest two two address address bits bits must must be be 0! 0! omp 411 Fall 2010 9/8/10 L03 Instruction Set 22 Storage Conventions int x, y; y = x + 37; Addr assigned at compile time Data and Variables are stored in memory Compilation approach: LOAD, COMPUTE, STOR Operations done on registers Registers hold Temporary lw results translates to 1000: 1004: 1008: 100C: 1010: omp 411 Fall 2010 n r x y addi sw $t0, 0x1008($0) $t0, $t0, 37 $t0, 0x100C($0) x=0x1008 or, more humanely, y=0x100C

lw $t0, x to addi $t0, $t0, 37 sw $t0, y rs defaults to Reg[0] (0) 9/8/10 L03 Instruction Set 23 MIPS Register Usage Conventions By convention, the MIPS registers are assigned to specific uses, and names. These are supported by the assembler, and higher-level languages. Well use these names increasingly. Name Register number 0 $zero 1 $at 2-3 $v0-$v1 4-7 $a0-$a3 8-15 $t0-$t7 16-23 $s0-$s7 24-25 $t8-$t9 28 $gp 29 $sp 30 $fp 31 $ra omp 411 Fall 2010 Usage the constant value 0 assembler temporary values for results and expression evaluation arguments temporaries saved more temporaries global pointer stack pointer frame pointer

return address 9/8/10 L03 Instruction Set 24 Capabilities thus far: Expression Evaluation Translation of an Expression: VARIABLES VARIABLES are are int x, y; allocated allocated storage storage in in y = (x-3)*(y+123456) main main memory memory VARIABLE VARIABLE references references x: .word 0 translate y: .word 0 translate to to LD LD or or ST ST c: .word 123456 OPERATORS OPERATORS translate translate ... to to ALU ALU instructions instructions lw $t0, x addi $t0, $t0, -3 SMALL SMALL CONSTANTS CONSTANTS lw $t1, y translate lw $t2, c translate to

to ALU ALU add $t1, $t1, $t2 instructions instructions w/ w/ built-in built-in mul $t0, $t0, $t1 constant sw $t0, y constant LARGE LARGE CONSTANTS CONSTANTS translate to initialized translate to initialized NB: Here we assume variables variables that variable omp 411 Fall 2010 addresses fit into 16bit constants! 9/8/10 L03 Instruction Set 25 Can We Run Any Algorithm? Model thus far: Executes instructions sequentially Number of operations executed = number of instructions in our program! Good news: programs cant loop forever! So far the MIPS subset produces straight-line code only Bad news: Straight-line code Cant do a loop Cant reuse a block of code

omp 411 Fall 2010 9/8/10 Needed: ability to change the PC. L03 Instruction Set 26 MIPS Branch Instructions MIPS branch instructions provide a way of conditionally changing the PC to some nearby location... I-type:OPCODE beq rs, rt, label rs rt 16-bit signed constant # Branch if equal bne if (REG[RS] == REG[RT]) { PC = PC + 4 + 4*offset; } rs, rt, label # Branch if not equ if (REG[RS] != REG[RT]) { PC = PC + 4 + 4*offset; } Notice on memory references offsets are multiplied by 4, so that branch targets are restricted to word boundaries. NB: Branch targets are specified relative to the current instruction (actually relative to the next instruction, which would be fetched by default). The assembler hides the calculation of these offset values from the user, by allowing them to specify a target address (usually a label) and it does the job of computing the offsets value. The size of the constant field (16-bits) limits the range of branches. 9/8/10 omp 411 Fall 2010

L03 Instruction Set 27 MIPS Jumps The range of MIPS branch instructions is limited to approximately 64K instructions from the branch instruction. In order to branch farther an unconditional jump instruction is used. Instructions: j label # jump jal label jr $t0 # jump jalr $t0, $ra contents to label (PC = PC[31-28] || CONST[25:0]*4) # jump to label and store PC+4 in $31 to address specified by registers contents # jump to address specified by registers Formats: J-type: used forOP j =2 26-bit constant J-type: used forOP jal = 3 26-bit constant R-type, used forOP jr = 0 r 0 0 0 R-type, used forOP jalr =0 s r 0 r 0

omp 411 Fall 2010 s 9/8/10 func = 8 func = 9 d L03 Instruction Set 28 MIPS Now we can do a real program: Factorial... Synopsis (in C): int n, ans; r1 = 1; r2 = n; while (r2 != 0) { r1 = r1 * r2; r2 = r2 1; } ans = r1; Input in n, output in ans r1, r2 used for temporaries follows algorithm of ourin earlier data paths. code, assembly language: n: ans: loop: done: omp 411 Fall 2010 .word .word ... addi

lw beq mul addi beq sw 123 0 $t0, $0, 1 $t1, n $t1, $0, done $t0, $t0, $t1 $t1, $t1, -1 $0, $0, loop $t0, ans # # # # # # # 9/8/10 t0 = 1 t1 = n while (t1 != 0) t0 = t0 * t1 t1 = t1 - 1 Always branch ans = r1 L03 Instruction Set 29 To summarize: MIPS operands Name 32 registers Example Comments $s0-$s7, $t0-$t9, $zero, Fast locations for data. In MIPS, data must be in registers to perform $a0-$a3, $v0-$v1, $gp, arithmetic. MIPS register $zero always equals 0. Register $at is $fp, $sp, $ra, $at reserved for the assembler to handle large constants. Memory[0], Accessed only by data transfer instructions. MIPS uses byte addresses, so 30 2 memory Memory[4], ..., sequential words differ by 4. Memory holds data structures, such as arrays,

words and spilled registers, such as those saved on procedure calls. Memory[4294967292] add MIPS assembly language Example Meaning add $s1, $s2, $s3 $s1 = $s2 + $s3 Three operands; data in registers subtract sub $s1, $s2, $s3 $s1 = $s2 - $s3 Three operands; data in registers addi $s1, $s2, 100 lw $s1, 100($s2) store word sw $s1, 100($s2) load byte lb $s1, 100($s2) store byte sb $s1, 100($s2) load upper immediate lui $s1, 100 $s1 = $s2 + 100 $s1 = Memory[$s2 + 100] Memory[$s2 + 100] = $s1 $s1 = Memory[$s2 + 100] Memory[$s2 + 100] = $s1 Used to add constants branch on equal beq $s1, $s2, 25 if ($s1 == $s2) go to PC + 4 + 100 Equal test; PC-relative branch branch on not equal bne

$s1, $s2, 25 if ($s1 != $s2) go to PC + 4 + 100 Not equal test; PC-relative set on less than slt $s1, $s2, $s3 if ($s2 < $s3) $s1 = 1; else $s1 = 0 Compare less than; for beq, bne set less than immediate slti jump j jr jal Category Arithmetic Instruction add immediate load word Data transfer Conditional branch Unconditional jump omp 411 Fall 2010 jump register jump and link 16 $s1 = 100 * 2 $s1, $s2, 100 if ($s2 < 100) $s1 = 1; Comments

Word from memory to register Word from register to memory Byte from memory to register Byte from register to memory Loads constant in upper 16 bits Compare less than constant else $s1 = 0 2500 $ra 2500 Jump to target address go to 10000 For switch, procedure return go to $ra $ra = PC + 4; go to 10000 For procedure call 9/8/10 L03 Instruction Set 30 MIPS Instruction Decoding Ring OP 000 001 010 011 100 101 110 111 000 001 ALU addi addi u j slti 010 011 100 101 110 111 ALU 000 001

010 011 100 101 110 111 omp 411 Fall 2010 jal sltiu beq andi bne ori 100 sllv and xori lui 101 110 srlv 111 srav or xor nor lw sw 000 sll jr 001 mult mult u addu add

010 srl 011 sra div divu sub slt subu sltu jalr 9/8/10 L03 Instruction Set 31 Summary We will use a subset of MIPS instruction set as a prototype Fixed-size 32-bit instructions Mix of three basic instruction formats R-type - Mostly 2 source and 1 destination register I-type - 1-source, a small (16-bit) constant, and a destination register J-type - A large (26-bit) constant used for jumps Load/Store architecture 31 general purpose registers, one hardwired to 0, and, by convention, several are used for specific purposes. ISA design requires tradeoffs, usually based on 9/8/10 omp 411 Fall 2010 History L03 Instruction Set 32

Recently Viewed Presentations

  • CLS 231 Practical part Introduction Lecture 1 Course

    CLS 231 Practical part Introduction Lecture 1 Course

    Complexometric determination of calcium in milk. 6- Determination of blood glucose by a Redox titration method . 7- Determination of chloride by the Vohlard method . 8- Gravimetric determination of chloride . 9- Revision . Marking criteria .
  • Teacher Data Team Summit - Brevard Public Schools

    Teacher Data Team Summit - Brevard Public Schools

    Best if typed during meeting and displayed as we go. (Jayna will make a template to make this easier). After meeting, tweaks and formats, distributes to administration and TDT members within 24 hours. TIME KEEPER: Will have a copy of...
  • Les changements climatiques au Canada…

    Les changements climatiques au Canada…

    Les changements climatiques au Canada… Réponse par Matt O, Alyson, et Matthew M. Montréal l'après midi Montréal est une ville au Canada. Elle est une des villes le plus pollués. Cette photo est une photo quotidienne de Montréal. A chaque...
  • Natural Waters - University of Vermont

    Natural Waters - University of Vermont

    Pycnocline - Density gradient change Chemocline - Chemical gradient change Ocean Chemistry Elements in the Oceans Split elemental abundances in the ocean into 3 classes: Conservative - constant Recycled - used by organisms in photic zone Scavenged - taken out...
  • Basic Communication Operations Ananth Grama, Anshul Gupta, George

    Basic Communication Operations Ananth Grama, Anshul Gupta, George

    The Prefix-Sum Operation Given p numbers n0,n1,…,np-1 (one on each node), the problem is to compute the sums sk = ∑ik= 0 ni for all k between 0 and p-1 . Initially, nk resides on the node labeled k, and...
  • Closing - Four Blocks

    Closing - Four Blocks

    create.kahoot.it/login. Good literacy instruction is good for all students . Curriculum is only a resource . There is not a reading program or instructional approach that does not require a knowledgeable teacher. Duke, Cervetti, and Wise (2015) reminded us that...
  • Chapter 9

    Chapter 9

    North Africa was divided into three sultanates. Thousands of pilgrims traveled to Mecca for the hajj, going through Cairo. Cairo became was the cultural capital of the Islamic world in 1261. Rulers of the . Mamluk . empire . announced...
  • New Semantic Elements (2)

    New Semantic Elements (2)

    New Semantic Elements (Part 2) Three More New HTML5 Elements The <article> element represents web content that could stand by itself, even if separated from the surrounding page information. The <aside> element represents content that is visually set apart from...