硬件和状态介绍

1 .CS 61C: Great Ideas in Computer Architecture Introduction to Hardware: Representations and State Instructors: Krste Asanović and Randy H. Katz http://inst.eecs.Berkeley.edu/~cs61c/fa17 1 Fall 2017 -- Lecture #9 9/20/17

2 .From Last Time: Where Are We Now? 9/20/17 Fall 2017 - Lecture #9 2 Translation : Compilation to Assembly Replace pseudo with real instructions Resolve local jumps, branches Create Symbol, Relocation Tables Symbol Table: Labels defined or referenced Relocation Table: Address locations to be adjusted

3 .. o file 1 text 1 data 1 info 1 . o file 2 text 2 data 2 info 2 Linker a.out Relocated text 1 Relocated text 2 Relocated data 1 Relocated data 2 Linker (2/3) 9/20/17 Fall 2017 - Lecture #9 3

4 .Four Types of Addresses PC-Relative Addressing ( beq , bne , jal ; lla : auipc / addi ) Never need to relocate (PIC: position independent code) Absolute Function Address ( la : auipc / lw + jalr ) Always relocate External Function Reference ( la : auipc / lw + jalr ) Always relocate Static Data References ( lui / addi ) Always relocate 4 9/20/17 Fall 2017 - Lecture #9

5 .Resolving References (1/2) Linker assumes first word of first text segment is at address 0x10000 for RV32 . (More later when we study “virtual memory”) Linker knows: L ength of each text and data segment O rdering of text and data segments Linker calculates: A bsolute address of each label to be jumped to (internal or external) and each piece of data being referenced 5 9/20/17 Fall 2017 - Lecture #9

6 .Resolving References (2/2) To resolve references: S earch for reference (data or label) in all “user” symbol tables I f not found, search library files (e.g., for printf ) Once absolute address is determined, fill in the machine code appropriately Output of linker: executable file containing text and data (plus header) 6 9/20/17 Fall 2017 - Lecture #9

7 .Where Are We Now? 7 9/20/17 Fall 2017 - Lecture #9

8 .Loader Basics Input: Executable Code (e.g., a.out for RISC-V) Output: (program is run) Executable files are stored on disk When one is run, loader loads it into memory and start it In reality, loader is the operating system (OS) L oading is one of the OS tasks 8 9/20/17 Fall 2017 - Lecture #9

9 .Loader … What Does It Do? Reads executable file’s header to determine size of text and data segments Creates new address space for program large enough to hold text and data segments, along with a stack segment Copies instructions + data from executable file into the new address space Copies arguments passed to the program onto the stack Initializes machine registers Most registers cleared, but stack pointer assigned address of 1st free stack location Jumps to start-up routine that copies program’s arguments from stack to registers & sets the PC If main routine returns, start-up routine terminates program with the exit system call 9 9/20/17 Fall 2017 - Lecture #9

10 .Peer Instruction At what point in process are all the machine code bits determined for the following assembly instructions: 1) add x6, x7, x8 2) jal x1, fprintf A : 1) & 2) After compilation B : 1) After compilation, 2) After assembly C : 1) After assembly, 2) After linking D : 1) After assembly, 2) After loading 9/20/17 Fall 2017 - Lecture #9 10

11 .Example C Program: Hello.c #include < stdio.h > int main() { printf ("Hello, %s

12 .Compiled Hello.c : Hello.s .text .align 2 . globl main main: addi sp,sp,-16 sw ra,12( sp ) lui a0,%hi(string1) addi a0,a0,%lo(string1) lui a1,%hi(string2) addi a1,a1,%lo(string2) call printf lw ra,12( sp ) addi sp,sp,16 li a0,0 ret .section . rodata . balign 4 string1: .string "Hello, %s!

13 .Assembled Hello.s : Linkable Hello.o 00000000 < main >: 0: ff010113 addi sp,sp,-16 4 : 00112623 sw ra,12( sp ) 8 : 00000 537 lui a0,0x0 # addr placeholder c : 000 50513 addi a0,a0,0 # addr placeholder 10 : 00000 5b7 lui a1,0x0 # addr placeholder 14 : 000 58593 addi a1,a1,0 # addr placeholder 18 : 00000097 auipc ra,0x0 # addr placeholder 1c : 000 080e7 jalr ra # addr placeholder 20 : 00c12083 lw ra,12( sp ) 24 : 01010113 addi sp,sp,16 28 : 00000513 addi a0,a0,0 2c : 00008067 jalr ra 13 9/20/17 Fall 2017 - Lecture #9 13

14 .Linked Hello.o : a.out 000101b0 < main >: 101b0 : ff010113 addi sp,sp,-16 101b4 : 00112623 sw ra,12( sp ) 101b8 : 00021 537 lui a0,0x21 101bc : a10 50513 addi a0,a0,-1520 # 20a10 <string1> 101c0 : 00021 5b7 lui a1,0x21 101c4 : a1c 58593 addi a1,a1,-1508 # 20a1c <string2> 101c8 : 28800 0ef jal ra , 0x 10450 # 10450 < printf > 101cc : 00c12083 lw ra,12( sp ) 101d0 : 01010113 addi sp,sp,16 101d4 : 00000513 addi a0,0 ,0 101d8 : 00008067 jalr ra 14 9/20/17 Fall 2017 - Lecture #9

15 .LUI/ADDI Address Calculation in RISC-V Target address of <string1> is 0x00020 A10 Instruction sequence LUI 0x00020 , ADDI 0xA10 does not quite work because immediates in RISC-V are sign extended (and 0xA10 has a 1 in the high order bit)! 0x00020 000 + 0xFFFFF A10 = 0x0001F A10 (Off by 0x00001 000) So we get the right address if we calculate it as follows: ( 0x00020 000 + 0x00001 000) + 0xFFFFF A10 = 0x00020 A10 What is 0xFFFFF A10 ? Twos complement of 0xFFFFF A10 = 0x00000 5EF + 1 = 0x00000 5F0 = 1520 ten So 0xFFFFF A10 = -1520 ten Instruction sequence LUI 0x00021 , ADDI -1520 calculates 0x00020 A10 15 9/20/17 Fall 2017 - Lecture #9

16 .Break! 16 9/20/17 Fall 2017 - Lecture #9

17 .Parallel Requests Assigned to computer e.g., Search “Katz” Parallel Threads Assigned to core e.g., Lookup, Ads Parallel Instructions >1 instruction @ one time e.g., 5 pipelined instructions Parallel Data >1 data item @ one time e.g., Add of 4 pairs of words Hardware descriptions All gates @ one time Programming Languages 9/20/17 Fall 2017 -- Lecture #9 17 Smart Phone Warehouse Scale Computer Software Hardware Harness Parallelism & Achieve High Performance Logic Gates Core Core … Memory (Cache) Input/Output Computer Cache Memory Core Instruction Unit(s ) Functional Unit(s ) A 3 +B 3 A 2 +B 2 A 1 +B 1 A 0 +B 0 Today You are Here!

18 .Levels of Representation/Interpretation lw $t0, 0($2) lw $t1, 4($2) sw $t1, 0($2) sw $t0, 4($2) High Level Language Program (e.g., C) Assembly Language Program (e.g., RISC-V) Machine Language Program (RISC-V) Hardware Architecture Description (e.g., block diagrams) Compiler Assembler Machine Interpretation temp = v[k]; v[k] = v[k+1]; v[k+1] = temp; 0000 1001 1100 0110 1010 1111 0101 1000 1010 1111 0101 1000 0000 1001 1100 0110 1100 0110 1010 1111 0101 1000 0000 1001 0101 1000 0000 1001 1100 0110 1010 1111 Logic Circuit Description (Circuit Schematic Diagrams) Architecture Implementation Anything can be represented as a number , i.e., data or instructions 9/20/17 18 Fall 2017 -- Lecture #9

19 .Agenda Switching Networks, Transistors Gates and Truth Tables for Circuits Boolean Algebra Logisim And in Conclusion, … 9/20/17 19 Fall 2017 -- Lecture #9

20 .Agenda Switching Networks, Transistors Gates and Truth Tables for Circuits Boolean Algebra Logisim And in Conclusion, … 9/20/17 20 Fall 2017 -- Lecture #9

21 .Hardware Design Next several weeks: how a modern processor is built, starting with basic elements as building blocks Why study hardware design? Understand capabilities and limitations of hw in general and processors in particular What processors can do fast and what they can’t do fast (avoid slow things if you want your code to run fast!) Background for more in depth hw courses (CS 152) Hard to know what will need for next 30 years There is just so much you can do with standard processors: you may need to design own custom hw for extra performance Even some commercial processors today have customizable hardware! 9/20/17 Fall 2017 -- Lecture #9 21

22 .Synchronous Digital Systems 9/20/17 Fall 2017 -- Lecture #9 22 Synchronous : All operations coordinated by a central clock “Heartbeat” of the system! Digital : Represent all values by two discrete values Electrical signals are treated as 1’s and 0’s 1 and 0 are complements of each other High /low voltage for true / false, 1 / 0 Hardware of a processor, such as the RISC-V, is an example of a Synchronous Digital System

23 .Fall 2017 -- Lecture #9 A Z Switches: Basic Element of Physical Implementations Implementing a simple circuit (arrow shows action if wire changes to “1” or is asserted ): Z  A A Z 9/20/17 23 Close switch (if A is “1” or asserted) and turn on light bulb (Z) Open switch (if A is “0” or unasserted ) and turn off light bulb (Z)

24 .Fall 2017 -- Lecture #9 AND OR Z  A and B Z  A or B A B A B Switches (cont’d) Compose switches into more complex ones (Boolean functions): 9/20/17 24

25 .Historical Note Early computer designers built ad hoc circuits from switches Began to notice common patterns in their work: ANDs , ORs , … Master’s thesis (by Claude Shannon) made link between work and 19 th Century Mathematician George Boole Called it “Boolean” in his honor Could apply math to give theory to hardware design, minimization, … 9/20/17 Fall 2017 -- Lecture #9 25

26 .Fall 2017 -- Lecture #9 Transistors High voltage ( V dd ) represents 1, or true Low voltage (0 volts or Ground) represents 0, or false Let threshold voltage ( V th ) decide if a 0 or a 1 If switches control whether voltages can propagate through a circuit, can build a computer Our switches: CMOS transistors 9/20/17 26

27 .Fall 2017 -- Lecture #9 CMOS Transistor Networks Modern digital systems designed in CMOS MOS: Metal-Oxide on Semiconductor C for complementary: use pairs of normally -open and normally-closed switches Used to be called COS-MOS for complementary-symmetry -MOS CMOS transistors act as voltage-controlled switches Similar, though easier to work with, than relay switches from earlier era Use energy primarily when switching 9/20/17 27

28 .n -channel transitor open when voltage at Gate is low closes when: voltage(Gate ) > voltage (Threshold) (High resistance when gate voltage Low, Low resistance when gate voltage High) Fall 2017 -- Lecture #9 p -channel transistor closed when voltage at Gate is low opens when: voltage(Gate ) > voltage (Threshold) (Low resistance when gate voltage Low, High resistance when gate voltage High) CMOS Transistors Three terminals: source, gate, and drain Switch action: if voltage on gate terminal is (some amount) higher/lower than source terminal then conducting path established between drain and source terminals (switch is closed) Gate Source Drain Gate Source Drain 9/20/17 28 Note circle symbol to indicate “NOT” or “complement” Gate Drain Source

29 .Fall 2017 -- Lecture #9 CMOS Circuit Rules Don’t pass weak values => Use Complementary Pairs N-type transistors pass weak 1’s ( V dd - V th ) N-type transistors pass strong 0’s (ground) Use N-type transistors only to pass 0’s (N for negative) Converse for P-type transistors: Pass weak 0s, strong 1s Pass weak 0’s ( V th ), strong 1’s ( V dd ) Use P-type transistors only to pass 1’s (P for positive) Use pairs of N-type and P-type to get strong values Never leave a wire undriven Make sure there’s always a path to V dd or gnd Never create a path from V dd to gnd (ground) 9/20/17 29