MIT OpenCourseWarehttp://ocw.mit.edu For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. 6.004 Computation Structures Spring 2009 Instruction Sets 1 6.004 – Spring 20093/10/09Designing an Instruction Set Nerd Chef at work. move flour,bowl add milk,bowl add egg,bowl move bowl,mixer rotate mixer ...Quiz 2 FRIDAY Instruction Sets 2 6.004 – Spring 20093/10/09Let’s Build a Simple Computer Data path for computing N*(N-1) *L.E.AL.E.B1N-10 10 1ASELBSELBLEALEANSWERL.E. = load enable. Register only loads new value when LE=1 Instruction Sets 3 6.004 – Spring 20093/10/09A Programmable Control System Computing N*(N-1) with this data path is a multi-step process. We can control the processing at each step with a FSM. If we allow different control sequences to be loaded into the control FSM, then we allow the machine to be programmed.Control FSMALEBLEASELBSELA1AA * B BB -1 BNAA * B Instruction Sets 4 6.004 – Spring 20093/10/09A First Program A1AA * B BB -1 BNAA * B S0S1S2S3S4Once more, writing a control program is nothing more than filling in a table: SNSN+1AselALEBselBLE01234SNSN+1AselALEBselBLE011101120100230011340100440000Instruction Sets 5 6.004 – Spring 20093/10/09An Optimized Program A1AA * B BB -1 BNAA * B S0S1S2S3Some parts of the program can be computed simultaneously: SNSN+1AselALEBselBLE011101120111230100330000Instruction Sets 6 6.004 – Spring 20093/10/09Computing Factorial L.E.L.E.*AB1N-10 1 0 1 ASELBSELBLEALEANSWER=0?Control FSMAselBselAleBleThe advantage of a programmable control system is that we can reconfigure it to compute new functions. In order to compute N! we will need to add some new logic and an input to our control FSM: Instruction Sets 7 6.004 – Spring 20093/10/09Control Structure for Factorial AA * B BB -1 BN A1 Z=0Z=1DONES0S1S2Programmability allows us to reuse data paths to solve new problems. What we need is a general purpose data path, which can be used to efficiently solve most problems as well as an easier way to control it. ZSNSN+1AselALEBselBLE-00111-2ZSNSN+01110101101111120111-220000Instruction Sets 8 6.004 – Spring 20093/10/09A Programmable Engine We’ve used the same data paths for computing N*(N-1) and Factorial; there are a variety of other computations we might implement simply by re-programming the control FSM. Although our little machine is programmable, it falls short of a practical general-purpose computer – and fails the Turing Universality test – for three primary reasons: 1.It has very limited storage: it lacks the “expandable” memory resource of a Turing Machine. 2.It has a tiny repertoire of operations. 3.The “program” is fixed. It lacks the power, e.g., to generate a new program and then execute it. Control FSMALEBLEASELBSELL.E.L.E.*AB1N-10 1 ASELBSELBLEALEANSWER=0?0 1 Instruction Sets 9 6.004 – Spring 20093/10/09A 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: Central Processing UnitCentral Processing Unit (CPU): containing several registers, as well as logic for performing a specified set of operations on their contents. MainMemory Memory: storage of N words of W bits each, where W is a fixed architectural parameter, and N can be expanded to meet needs. Input/Output I/O: Devices for communicating with the outside world. Ah, an FSM! Like an Infinite Tape? Hmm, guess J. von N was an engineer after all! Instruction Sets 10 6.004 – Spring 20093/10/09The Stored Program Computer The von Neumann architecture easily addresses the first two limitations of our simple programmable machine example: •A richer repertoire of operations, and •An expandable memory. But how does it achieve programmability?CPU fetches and executes – interprets – successive instructions of the program ... •Program is simply data for the interpreter, specifying what computation to perform •Single expandable resource pool – main memory – constrains both data and program size. Key idea: Memory holds not only data, butcoded instructions that make up aprogram.Central Processing UnitInstruction Sets 11 6.004 – Spring 20093/10/09registers operations Anatomy of a von Neumann Computer Control UnitData Paths Internal storage MEMORY control statusinstructions data…destaselfnbselCc’s ALU PC1101000111011• 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 +1R1R2+R3address address Instruction Sets 12 6.004 – Spring 20093/10/09Instruction Set Architecture Coding 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” (RISC) philosophy: simple instructions, optimized for speed Mix of engineering & Art... Trial (by simulation) is our best technique for making choices! Our representative example: the architecture! Main Memory data data data instruction instruction instruction Instruction Sets 13 6.004 – Spring 20093/10/09Programming Model a representative, simple, contemporary RISCFetch/Execute loop: •fetch Mem[PC] •PC = PC + 4†•execute fetched instruction (may change PC!) •repeat! 00PC†Even though each memory word is 32-bits wide, for historical reasons the uses byte memory addresses. Since each word contains four 8-bit bytes, addresses of consecutive words differ by 4. Main Memory 0123(4 bytes) 32-bit “words” 031next instruction Processor State r0r1r2...r31000000....0 32-bit “words” General Registers Instruction Sets 14 6.004 – Spring 20093/10/09Instruction Formats All Beta instructions fit in a single 32-bit word, whose fields encode combinations of •a 6-bit OPCODE (specifying one of < 64 operations) •several 5-bit OPERAND locations, each one of the 32 registers •an embedded 16-bit constant (“literal”) There are two instruction formats: •Opcode, 3 register operands (2 sources, destination) •Opcode, 2 register operands, 16-bit literal constant OPCODE rcrarbunusedOPCODE rcra16-bit signed constant Instruction Sets 15 6.004 – Spring 20093/10/09ALU Operations Sample coded operation: ADD instruction 32-bit hex: 0x80611000 What we prefer to write: ADD(r1,r2,r3)ADD(ra,rb,rc):“Add the contents of ra to the contents of rb; store the result in rc” OPCODE = 100000, encoding ADD rc=3,encoding R3 as destinationra=1,rb=2encoding R1 and R2 as source locations Reg[rc] = Reg[ra] + Reg[rb] arithmetic: ADD, SUB, MUL, DIV compare: CMPEQ, CMPLT, CMPLE boolean: AND, OR, XOR shift: SHL, SHR, SAR Similar instructions for other ALU operations: 10000000011000010001000000000000unused“assembly language” Instruction Sets 16 6.004 – Spring 20093/10/09ALU Operations with Constant ADDC instruction: adds constant, register contents: Symbolic version: ADDC(r1,-3,r3)“Add the contents of ra to const; store the result in rc” OPCODE = 110000, encoding ADDC rc=3,encoding R3 as destinationra=1,encoding R1 as first operand Reg[rc] = Reg[ra] + sxt(const) arithmetic: ADDC, SUBC, MULC, DIVC compare: CMPEQC, CMPLTC, CMPLEC boolean: ANDC, ORC, XORC shift: SHLC, SHRC, SARC Similar instructions for other ALU operations: constant field, encoding -3 as second operand (sign-extended!) ADDC(ra,const,rc):11000000011000011111111111111101Instruction Sets 17 6.004 – Spring 20093/10/09Do We Need Built-in Constants? Percentage of the operations that use a constant operand One way to answer architectural questions is to evaluate the consequences of different choices using carefully chosen representative benchmarks (programs and/or code sequences). Make choices that are “best” according to some metric (cost, performance, …). Instruction Sets 18 6.004 – Spring 20093/10/09Baby’s First Beta Program (fragment)SUBC(r1,1,r2)| put N-1 into r2 MUL(r2,r1,r2)| leave N*(N-1) in r2 Suppose we have N in r1, and want to compute N*(N-1), leaving the result in r2: These two instructions do what our little ad-hoc machine did. Of course, limiting ourselves to registers for storage falls short of our ambitions.... it amounts to the finite storage limitations of an FSM! Needed: instruction-set support for reading and writing locations in main memory... Instruction Sets 19 6.004 – Spring 20093/10/09Loads & Stores LD(ra,const,rc)Reg[rc] = Mem[Reg[ra] + sxt(const)] ST(rc,const,ra)Mem[Reg[ra] + sxt(const)] = Reg[rc] “Fetch into rc the contents of the memory location whose address is C plus the contents of ra” Abbreviation: LD(C,rc)for LD(R31,C,rc)“Store the contents of rc into the memory location whose address is C plus the contents of ra” Abbreviation: ST(rc,C) for ST(rc,C,R31)BYTE ADDRESSES, but only 32-bit word accesses to word-aligned addresses are supported. Low two address bits are ignored! OPCODE rcra16-bit signed constant address Instruction Sets 20 6.004 – Spring 20093/10/09Storage Conventions •Variables live in memory • Operations done on registers • Registers hold Temporary values 1000:1004:1008:1010:100C:nrxyAddr assigned at compile time int x, y; y = x * 37; LD(r31, 0x1008, r0) MULC(r0, 37, r0) ST(r0, 0x100C, r31) x=0x1008y=0x100CLD(x, r0) MULC(r0, 37, r0) ST(r0, y) translates to or, more humanely, to Ra defaults to R31 (0) Compilation approach: LOAD, COMPUTE, STORE Bar graph of percentage operations that use a constant operand, for loads, compares, and ALU operations.Figure by MIT OpenCourseWare.Instruction Sets 21 6.004 – Spring 20093/10/09can do these with appropriate choices for Ra and const Common “Addressing Modes” •Absolute: “constant” –Value = Mem[constant] –Use: accessing static data •Indirect (aka Register deferred): “(Rx)” –Value = Mem[Reg[x]] –Use: pointer accesses •Displacement: “constant(Rx)” –Value = Mem[Reg[x] + constant] –Use: access to local variables •Indexed: “(Rx + Ry)” –Value = Mem[Reg[x] + Reg[y]] –Use: array accesses (base+index) •Memory indirect: “@(Rx)” –Value = Mem[Mem[Reg[x]]] –Use: access thru pointer in mem •Autoincrement: “(Rx)+” –Value = Mem[Reg[x]]; Reg[x]++ –Use: sequential pointer accesses •Autodecrement: “-(Rx)” –Value = Reg[X]--; Mem[Reg[x]] –Use: stack operations •Scaled: “constant(Rx)[Ry]” –Value = Mem[Reg[x] + c + d*Reg[y]] –Use: array accesses (base+index) Argh! Is the complexity worth the cost? Need a cost/benefit analysis! Instruction Sets 22 6.004 – Spring 20093/10/09Memory Operands: Usage Usage of different memory operand modes Instruction Sets 23 6.004 – Spring 20093/10/09Capability so far: Expression Evaluation Translation of an Expression: int x, y; y = (x-3)*(y+123456) x:long(0)y:long(0)c:long(123456)...LD(x, r1) SUBC(r1,3,r1)LD(y, r2) LD(c, r3) ADD(r2,r3,r2)MUL(r2,r1,r1)ST(r1,y)•VARIABLES are allocated storage in main memory•VARIABLE references translate to LD or ST • OPERATORS translate to ALU instructions • SMALL CONSTANTS translate to ALU instructions w/built-in constant • “LARGE” CONSTANTS translate to initialized variables NB: Here we assume that variable addresses fit into 16-bit constants! Instruction Sets 24 6.004 – Spring 20093/10/09Can We Run Every Algorithm? Needed:ability to change the PC.Model thus far: •Executes instructions sequentially – •Number of operations executed = number of instructions in our program! Good news: programs can’t “loop forever”! •Halting problem* is solvable for our current Beta subset! Bad news: can’t compute Factorial: •Only supports bounded-time computations; •Can’t do a loop, e.g. for Factorial! NOTUniversal* *more next week! Bar graph of usage different memory operand nodes, for autoincrement, displacement deferred, scaled, register and displacement.Figure by MIT OpenCourseWare.Instruction Sets 25 6.004 – Spring 20093/10/09Beta Branch Instructions PC = PC + 4; Reg[rc] = PC; if (REG[ra] != 0) PC = PC + 4*offset;BNE(ra,label,rc):Branch if not equal PC = PC + 4; Reg[rc] = PC; if (REG[ra] == 0) PC = PC + 4*offset;BEQ(ra,label,rc):Branch if equal NB: “offset” is a SIGNED CONSTANT encoded as part of the instruction! OPCODE rcra16-bit signed constant The Beta’s branch instructions provide a way of conditionally changing the PC to point to some nearby location... ... and, optionally, remembering (in Rc) where we came from (useful for procedure calls). offset = (label -)/4 – 1 = up to 32767 instructions before/after BNE/BEQ Instruction Sets 26 6.004 – Spring 20093/10/09Now we can do Factorial... int n, ans; r1 = 1; r2 = n; while (r2 != 0) { r1 = r1 * r2; r2 = r2 – 1 }ans = r1; Synopsis (in C): •Input in n, output in ans •r1, r2 used for temporaries •follows algorithm of our earlier data paths. n:long(123)ans:long(0)...ADDC(r31, 1, r1)| r1 = 1 LD(n, r2)| r2 = n loop:BEQ(r2, done, r31)| while (r2 != 0) MUL(r1, r2, r1)| r1 = r1 * r2 SUBC(r2, 1, r2)| r2 = r2 -1 BEQ(r31, loop, r31)| Always branches! done:ST(r1, ans, r31)| ans = r1 Beta code, in assembly language: Instruction Sets 27 6.004 – Spring 20093/10/09Summary•Programmable data paths provide some algorithmic flexibility, just by changing control structure. •Interesting control structure optimization questions – e.g., what operations can be done simultaneously? •von Neumann model for general-purpose computation: need •support for sufficiently powerful operation repertoire •Expandable Memory •Interpreter for program stored in memory •ISA design requires tradeoffs, usually based on benchmark results: art, engineering, evaluation & incremental optimizations •Compilation strategy •runtime “discipline” for software implementation of a general class of computations •Typically enforced by compiler, run-time library, operating system. We’ll see more of these!