CS 152 Computer Architecture and Engineering Lecture 2 - Simple Machine ImplementationsLast Time in Lecture 1Burrough’s B5000 Stack Architecture: An ALGOL Machine, Robert Barton, 1960A Stack MachineEvaluation of ExpressionsSlide 6Hardware organization of the stackStack Operations and Implicit Memory ReferencesStack Size and Memory ReferencesStack Size and Expression EvaluationRegister Usage in a GPR MachineStack Machines: Essential featuresStack versus GPR Organization Amdahl, Blaauw and Brooks, 1964Stack Machines (Mostly) Died by 1980Stacks post-1980MicroprogrammingISA to Microarchitecture MappingMicroarchitecture: Implementation of an ISAMicrocontrol Unit Maurice Wilkes, 1954Microcoded MicroarchitectureThe MIPS32 ISAMIPS Instruction FormatsA Bus-based Datapath for MIPSMemory ModuleInstruction ExecutionMicroprogram FragmentsMicroprogram Fragments (cont.)MIPS Microcontroller: first attemptMicroprogram in the ROM worksheetMicroprogram in the ROMMicroprogram in the ROM Cont.CS152 AdministriviaSize of Control StoreReducing Control Store SizeMIPS Controller V2Jump LogicInstruction Fetch & ALU:MIPS-Controller-2Load & Store: MIPS-Controller-2Branches: MIPS-Controller-2Jumps: MIPS-Controller-2VAX 11-780 MicrocodeImplementing Complex InstructionsMem-Mem ALU Instructions: MIPS-Controller-2Performance IssuesHorizontal vs Vertical mCodeNanocodingMicroprogramming in IBM 360Microcode EmulationMicroprogramming thrived in the SeventiesWritable Control Store (WCS)Microprogramming: early EightiesModern UsageAcknowledgementsCS 152 Computer Architecture and Engineering Lecture 2 - Simple Machine ImplementationsKrste AsanovicElectrical Engineering and Computer SciencesUniversity of California at Berkeleyhttp://www.eecs.berkeley.edu/~krstehttp://inst.eecs.berkeley.edu/~cs1521/24/2008 CS152-Spring’082Last Time in Lecture 1•Computer Science at crossroads from sequential to parallel computing•Computer Architecture >> ISAs and RTL–CS152 is about interaction of hardware and software, and design of appropriate abstraction layers•Comp. Arch. shaped by technology and applications–History provides lessons for the future•Cost of software development a large constraint on architecture–Compatibility a key solution to software cost•IBM 360 introduces notion of “family of machines” running same ISA but very different implementations–Within same generation of machines–“Future-proofing” for subsequent generations of machine1/24/2008 CS152-Spring’083Burrough’s B5000 Stack Architecture: An ALGOL Machine, Robert Barton, 1960•Machine implementation can be completely hidden if the programmer is provided only a high-level language interface. •Stack machine organization because stacks are convenient for:1.expression evaluation;2.subroutine calls, recursion, nested interrupts;3.accessing variables in block-structured languages.•B6700, a later model, had many more innovative features–tagged data–virtual memory–multiple processors and memories1/24/2008 CS152-Spring’084A Stack MachineA Stack machine has a stack as a part of the processor state typical operations:push, pop, +, *, ...Instructions like + implicitly specify the top 2 elements of the stack as operands.a:stackProcessorMainStorebapush b cbapush c bapop 1/24/2008 CS152-Spring’085abcEvaluation of Expressions(a + b * c) / (a + d * c - e)/+*+ae-acdc*bReverse Polisha b c * + a d c * + e - /push apush bpush cmultiply*Evaluation Stackb * c1/24/2008 CS152-Spring’086aEvaluation of Expressions(a + b * c) / (a + d * c - e)/+*+ae-acdc*bReverse Polisha b c * + a d c * + e - /add+Evaluation Stackb * ca + b * c1/24/2008 CS152-Spring’087Hardware organization of the stack•Stack is part of the processor state stack must be bounded and small number of Registers, not the size of main memory• Conceptually stack is unbounded a part of the stack is included in the processor state; the rest is kept in the main memory1/24/2008 CS152-Spring’088Stack Operations andImplicit Memory References•Suppose the top 2 elements of the stack are kept in registers and the rest is kept in the memory.Each push operation 1 memory reference pop operation 1 memory reference No Good!•Better performance can be got if the top N elements are kept in registers and memory references are made only when register stack overflows or underflows. Issue - when to Load/Unload registers ?1/24/2008 CS152-Spring’089Stack Size and Memory Referencesprogram stack (size = 2) memory refspush a R0 apush b R0 R1 bpush c R0 R1 R2 c, ss(a)* R0 R1 sf(a)+ R0push a R0 R1 apush d R0 R1 R2 d, ss(a+b*c)push c R0 R1 R2 R3 c, ss(a)* R0 R1 R2 sf(a)+ R0 R1 sf(a+b*c)push e R0 R1 R2 e,ss(a+b*c)- R0 R1 sf(a+b*c)/ R0a b c * + a d c * + e - /4 stores, 4 fetches (implicit)1/24/2008 CS152-Spring’0810Stack Size and Expression Evaluationprogram stack (size = 4)push a R0push b R0 R1push c R0 R1 R2* R0 R1+ R0push a R0 R1push d R0 R1 R2push c R0 R1 R2 R3* R0 R1 R2+ R0 R1push e R0 R1 R2- R0 R1/ R0a b c * + a d c * + e - /a and c are“loaded” twicenot the bestuse of registers!1/24/2008 CS152-Spring’0811Register Usage in a GPR MachineMore control over register usage since registers can be named explicitlyLoad Ri mLoad Ri (Rj)Load Ri (Rj) (Rk) - eliminates unnecessary Loads and Stores- fewer Registersbut instructions may be longer!Load R0 aLoad R1 cLoad R2 bMul R2 R1(a + b * c) / (a + d * c - e)Reuse R2Add R2 R0Load R3 dMul R3 R1Add R3 R0Reuse R3Load R0 eSub R3 R0Div R2 R3Reuse R01/24/2008 CS152-Spring’0812Stack Machines: Essential features•In addition to push, pop, + etc., the instruction set must provide the capability to–refer to any element in the data area–jump to any instruction in the code area–move any element in the stack frame to the topmachinery tocarry out+, -, etc.stackSPDP PCdata...abcpush apush bpush c*+push e/code1/24/2008 CS152-Spring’0813Stack versus GPR OrganizationAmdahl, Blaauw and Brooks, 19641. The performance advantage of push down stack organization is derived from the presence of fast registers and not the way they are used.2.“Surfacing” of data in stack which are “profitable” is approximately 50% because of constants and common subexpressions.3. Advantage of instruction density because of implicit addresses is equaled if short addresses to specify registers are allowed.4. Management of finite depth stack causes complexity.5. Recursive
View Full Document
Unlocking...