CS 152 Computer Architecture and Engineering Lecture 2 Simple Machine Implementations Krste Asanovic Electrical Engineering and Computer Sciences University of California at Berkeley http www eecs berkeley edu krste http inst eecs berkeley edu cs152 Last 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 machine 1 24 2008 CS152 Spring 08 2 Burrough 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 1 24 2008 tagged data virtual memory multiple processors and memories CS152 Spring 08 3 A Stack Machine Processor stack Main Store 1 24 2008 typical operations push pop a A Stack machine has a stack as a part of the processor state Instructions like implicitly specify the top 2 elements of the stack as operands push b b a push c CS152 Spring 08 c b a pop b a 4 Evaluation of Expressions a b c a d c e a b e c a d c Reverse Polish a b c a d c e push ab c push push multiply 1 24 2008 CS152 Spring 08 c b b c a Evaluation Stack 5 Evaluation of Expressions a b c a d c e a b e c a d c Reverse Polish a b c a d c e add 1 24 2008 CS152 Spring 08 b c a c a b Evaluation Stack 6 Hardware 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 memory 1 24 2008 CS152 Spring 08 7 Stack Operations and Implicit 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 pop operation 1 memory reference 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 08 8 Stack Size and Memory References a b c a d c e program push a push b push c push a push d push c push e 1 24 2008 stack size R0 R0 R1 R0 R1 R0 R1 R0 R0 R1 R0 R1 R0 R1 R0 R1 R2 R0 R1 R0 R1 R0 R1 R0 4 2 R2 R2 R2 R3 R2 memory refs a b c ss a sf a a d ss a b c c ss a sf a sf a b c e ss a b c sf a b c stores 4 fetches implicit CS152 Spring 08 9 Stack Size and Expression Evaluation a b c a d c e program push a push b push c a and c are loaded twice push a not the best push d use of registers push c push e 1 24 2008 stack size R0 R0 R1 R0 R1 R0 R1 R0 R0 R1 R0 R1 R0 R1 R0 R1 R2 R0 R1 R0 R1 R0 R1 R0 CS152 Spring 08 4 R2 R2 R2 R3 R2 10 Register Usage in a GPR Machine a b c a d c e Reuse R2 Reuse R3 Reuse R0 Load Load Load Mul Add Load Mul Add Load Sub Div R0 R1 R2 R2 R2 R3 R3 R3 R0 R3 R2 a c b R1 R0 d R1 R0 e R0 R3 More control over register usage since registers can be named explicitly Load Load Load Ri m Ri Rj Ri Rj Rk eliminates unnecessary Loads and Stores fewer Registers but instructions may be longer 1 24 2008 CS152 Spring 08 11 Stack Machines Essential features In addition to push pop etc the instruction set must provide the capability to machinery to carry out etc 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 top stack SP DP PC push push push push a b c e a b c data code 1 24 2008 CS152 Spring 08 12 Stack versus GPR Organization Amdahl Blaauw and Brooks 1964 1 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 subroutine advantage can be realized only with the help of an independent stack for addressing 6 Fitting variable length fields into fixed width word is awkward 1 24 2008 CS152 Spring 08 13 Stack Machines Mostly Died by 1980 1 Stack programs are not smaller if short Register addresses are permitted 2 Modern compilers can manage fast register space better than the stack discipline GPR s and caches are better than stack and displays Early language directed architectures often did not take into account the role of compilers B5000 B6700 HP 3000 ICL 2900 Symbolics 3600 Some would claim that an echo of this mistake is visible in the SPARC architecture register windows more later 1 24 2008 CS152 Spring 08 14 Stacks post 1980 Inmos Transputers 1985 2000 Designed to support many parallel processes in Occam language Fixed height stack design simplified implementation Stack trashed on context swap fast context switches Inmos T800 was world s fastest microprocessor in late 80 s Forth machines Direct support for Forth execution in small embedded real time environments Several manufacturers Rockwell Patriot Scientific Java Virtual Machine Designed for software emulation not direct hardware execution Sun PicoJava implementation others Intel x87 floating point unit Severely broken stack model for FP arithmetic Deprecated in Pentium 4 replaced with SSE2 FP registers 1 24 2008 CS152 Spring 08 15 Microprogramming A brief look at microprogrammed machines To show how to build very small processors with complex ISAs To help you understand where CISC machines came from Because it is still used in the most common machines x86 PowerPC IBM360 As a gentle introduction into machine structures To help understand how technology drove the move to RISC 1 24 2008 CS152 Spring …
View Full Document
Unlocking...