Bài giảng Computer architecture - Chapter 2: Instructions - Language of the computer

Nội dung text: Bài giảng Computer architecture - Chapter 2: Instructions - Language of the computer

1. CE Operands of the Computer Hardware Operands of the computer hardware 1. Register Operands 2. Memory Operands 3. Constant or Immediate Operands 11
2. CE Operands of the Computer Hardware Register Operands:  Unlike programs in high-level languages, the operands of arithmetic instructions are restricted; they must be from a limited number of special locations built directly in hardware called registers.  The size of a register in the MIPS architecture is 32 bits; groups of 32 bits occur so frequently that they are given the name word in the MIPS architecture. (note: a word in other instruction sets is able to not be 32 bits)  One major difference between the variables of a programming language and registers is the limited number of registers, typically 32 on current computers. MIPS has 32 registers. 12
3. CE Operands of the Computer Hardware Memory Operands (1):  The processor can keep only a small amount of data in registers, but computer memory contains millions of data elements.  With MIPS instructions, arithmetic operations occur only on registers; thus, MIPS must include instructions that transfer data between memory and registers. Such instructions are called data transfer instructions. Data transfer instruction: A command that moves data between memory and registers  To access a word in memory, the instruction must supply the memory address Address: A value used to delineate the location of a specific data element within a memory array. 13
4. CE Operands of the Computer Hardware Memory Operands (2):  Memory is just a large, single-dimensional array, with the address acting as the index to that array, starting at 0. For example, in Figure 2.2, the address of the third data element is 2, and the value of Memory[2] is 10. Fig.2 Memory addresses and contents Fig.3 Actual MIPS memory addresses and contents of memory at those locations. of memory for those words. This is a simplification of the MIPS The changed addresses are highlighted to contrast addressing; Fig.3 shows the actual with Fig.2. Since MIPS addresses each byte, word MIPS addressing for sequential word addresses are multiples of four: there are four bytes addresses in memory. in a word. 14
5. CE Operands of the Computer Hardware Memory Operands (3):  The data transfer instruction that copies data from memory to a register is traditionally called load. The format of the load instruction: lw $s1,20($s2) offset Base address in a base register • $s1: register to be loaded • A constant (20) and register ($s2) used to access memory. The sum of the constant and the contents of the second register forms the memory address. 15
6. CE Operands of the Computer Hardware Memory Operands (4): Example for load. Let’s assume that A is an array of 100 words and that the compiler has associated the variables g and h with the registers $s1 and $s2 as before. Let's also assume that the starting address, or base address of the array is in $s3. Compile this C assignment statement: g = h + A[8]; Actually in MIPS, a word is 4 bytes Compile: lw $ t0, 32($s3) lw $t0,8($s3) # Temporary reg $t0 gets A[8] add $s1,$s2,$t0 # g = h + A[8]  The constant in a data transfer instruction (8) is called the offset, and the register added to form the address ($s3) is called the base register 16
7. CE Operands of the Computer Hardware Memory Operands (5):  Alignment restriction - In MIPS, words must start at addresses that are multiples of 4. This requirement is called an alignment restriction, and many architectures have it. (why alignment leads to faster data transfers – read more in Chapter 5 suggests ) - Computers divide into those that use the address of the leftmost or “big end” byte as the word address versus those that use the rightmost or “little end” byte. MIPS is in the Big Endian camp. 17
8. CE Operands of the Computer Hardware Memory Operands (6):  The instruction complementary to load is traditionally called store; it copies data from a register to memory. The format of a store is sw $s1,20($s2) offset Base address in a base register • $s1: register to be stored • A constant (20) and register ($s2) used to access memory. The sum of the constant and the contents of the second register forms the memory address. 18
9. CE Operands of the Computer Hardware Memory Operands (7): Example for store. Assume variable his associated with register $s2and the base address of the array A is in $s3. What is the MIPS assembly code for the C assignment statement below? A[12] = h + A[8]; Compile: lw $t0,32($s3) # Temporary reg $t0 gets A[8] add $t0,$s2,$t0 # Temporary reg $t0 gets h + A[8] sw $t0,48($s3) # Stores h + A[8] back into A[12] 19
10. CE Operands of the Computer Hardware Constant or Immediate Operands Many times a program will use a constant in an operation Example: addi $s3, $s3, 4 # $s3 = $s3 + 4 Constant or immediate operands Notes:  Although the MIPS registers considered here are 32 bits wide, there is a 64-bit version of the MIPS instruction set with 32 64-bit registers. To keep them straight, they are officially called MIPS-32 and MIPS-64. (In this chapter, a subset of MIPS-32 is used; see more MIPS-64 in Appendix E)  Since MIPS supports negative constants, there is no need for subtract immediate in MIPS 20
11. CE Instructions: Language of the Computer 1. Introduction 2. Operations of the Computer Hardware 3. Operands of the Computer Hardware 4. Signed and Unsigned number 5. Representing Instructions in the Computer 6. Logical Operations 7. Instructions for Making Decisions 8. Supporting Procedures in Computer Hardware 9. Communicating with People 10. MIPS Addressing for 32-Bit Immediates and Addresses 11. Translating and Starting a Program 21
12. CE Signed and Unsigned number  Humans are taught to think in base 10, but numbers may be represented in any base. For example, 123 base 10 = 1111011 base 2.  Numbers are kept in computer hardware as a series of high and low electronic signals, and so they are considered base 2 numbers. Example: the drawing below shows the numbering of bits within a MIPS word and the placement of the number 1011:  The MIPS word is 32 bits long, so the numbers from 0 to 232-1 (4.294.967.295)  The least significant bit: the rightmost bit in a MIPS word (bit 0) The most significant bit: the leftmost bit in a MIPS word (bit 31) 22
13. CE Signed and Unsigned number Positive and negative number in computer: Using two’s complement representation Leading ‘0’ mean positive, leading ‘1’ mean negative. 23
14. CE Signed and Unsigned number 31 The positive half of the numbers, from 0 to 2,147,483,647ten (2 – 1), use the same representation as before. 1000 0000two = -2,147,483,648ten 1000 0001two = -2,147,483,647ten 1111 1111two = -1ten The 32nd bit is called the sign bit. We can represent positive and negative 32-bit numbers in terms of the bit value times a power of 2 Two’s complement does have one negative number -2,147,483,648 , that has ten no corresponding positive number. Every computer today uses two’s complement binary representations for signed number Note: The sign bit is multiplied by -231, and the rest of the bits are then multiplied by positive versions of their respective base values. 24
15. CE Signed and Unsigned number Example Answer 25
16. CE Signed and Unsigned number Sign Extension: How to convert a binary number represented in n bits to a number represented with more than n bits? Example: Convert 16-bit binary versions of 2ten and -2ten to 32-bit binary numbers. 2ten: -2ten: Taking the sign bit and replicating it to fill the new bits of larger quantity. The old bits are simply copied into the right portion of the new word. 26
17. CE Instructions: Language of the Computer 1. Introduction 2. Operations of the Computer Hardware 3. Operands of the Computer Hardware 4. Signed and Unsigned number 5. Representing Instructions in the Computer 6. Logical Operations 7. Instructions for Making Decisions 8. Supporting Procedures in Computer Hardware 9. Communicating with People 10. MIPS Addressing for 32-Bit Immediates and Addresses 11. Translating and Starting a Program 27
18. CE Representing Instructions in the Computer  How is an instruction (add $t0, $s1, $s2) kept in the computer? Computer only can work with low and high electronic signals, thus an instruction kept in computer must be represented as a serial of “0” and “1”, called machine code/machine instruction.  Machine language: Binary representation used for communication within a computer system.  In order to convert from a instruction to machine code, using instruction format Instruction format: A form of representation of an instruction composed of fields of binary numbers. Fig.4 An example of instruction format 28
19. CE Representing Instructions in the Computer  Example: Translating a MIPS Assembly Instruction into a Machine Instruction add $t0,$s1,$s2 With instruction format: 29
20. CE Representing Instructions in the Computer  Answer: Translating a MIPS Assembly Instruction into a Machine Instruction add $t0,$s1,$s2 With instruction format: . In MIPS assembly language, registers $s0 to $s7 map onto registers 16 to 23, and registers $t0 to $t7 map onto registers 8 to 15 . Each of these segments of an instruction format is called a field. . The first and last fields (containing 0 and 32 in this case) in combination tell the MIPS computer that this instruction performs addition. . The second field gives the number of the register that is the first source operand of the addition operation (17 = $s1) . The third field gives the other source operand for the addition (18 = $s2). . The fourth field contains the number of the register that is to receive the sum (8 = $t0). . The fifth field is unused in this instruction, so it is set to 0. 30
21. CE Representing Instructions in the Computer Different kinds of instruction formats for different kinds of MIPS instructions: . R-type(for register) or R-format . I-type (for immediate) or I-format and is used by the immediate and data transfer instructions 31
22. CE Representing Instructions in the Computer MIPS Fields of R-format: MIPS fields are given names to make them easier to discuss: . op: Basic operation of the instruction, traditionally called the opcode. Opcode: The field that denotes the operation and format of an instruction . rs: The first register source operand. . rt: The second register source operand. . rd: The register destination operand. It gets the result of the operation. . shamt: Shift amount. (the next part explains shift instructions and this term; it will not be used until then, and hence the field contains zero.) . funct: Function. This field selects the specific variant of the operation in the op field and is sometimes called the function code. 32
23. CE Representing Instructions in the Computer MIPS Fields of I-format: MIPS fields are given names to make them easier to discuss: The 16-bit address means a load word instruction can load any word within a region of ± 215 or 32,768 bytes (±213 or 8192 words) of the address in the base register rs. Similarly, add immediate is limited to constants no larger than ± 215 33
24. CE Representing Instructions in the Computer Fig.6 shows the numbers used in each field for some MIPS instructions Fig.6 MIPS instruction encoding. . “reg” means a register number between 0 and 31 . “address” means a 16-bit address . “n.a.” (not applicable) means this field does not appear in this format. . Note that “add” and “sub” instructions have the same value in the “op” field; the hardware uses the “funct” field to decide the variant of the operation: “add” (32) or “subtract” (34). 34
25. CE Representing Instructions in the Computer  Example: Translating MIPS Assembly Language into Machine Language If $t1 has the base of the array A and $s2 corresponds to h, the assignment statement: A[300] = h + A[300]; is compiled into: lw $t0,1200($t1) # Temporary reg $t0 gets A[300] add $t0,$s2,$t0 # Temporary reg $t0 gets h + A[300] sw $t0,1200($t1) # Stores h + A[300] back into A[300] What is the MIPS machine language code for these three instructions?  Answer: 35
26. CE Representing Instructions in the Computer In conclusion, 1. Instructions are represented as numbers. 2. Programs are stored in memory to be read or written, just like numbers. (Commercial software are often shipped as files of binary numbers) . Treating instructions in the same way as data greatly simplifies both the memory hardware and the software of computer systems. . In order to perform a program, simply loading the program and data into memory and then telling the computer to begin executing at a given location in memory. 36
27. CE Instructions: Language of the Computer 1. Introduction 2. Operations of the Computer Hardware 3. Operands of the Computer Hardware 4. Signed and Unsigned number 5. Representing Instructions in the Computer 6. Logical Operations 7. Instructions for Making Decisions 8. Supporting Procedures in Computer Hardware 9. Communicating with People 10. MIPS Addressing for 32-Bit Immediates and Addresses 11. Translating and Starting a Program 37
28. CE Logical Operations Fig.7 C and Java logical operators and their corresponding MIPS instructions. . Shifts: moving all the bits in a word to the left or right, filling the emptied bits with 0s (Shifting left by i bits gives the same result as multiplying by 2i) . AND is a bit-by-bit operation that leaves a 1 in the result only if both bits of the operands are 1 . OR is a bit-by-bit operation that places a 1 in the result if either operand bit is a 1 . NOT takes one operand and places a 1 in the result if one operand bit is a 0, and vice versa. . NOR: NOT OR . Constants are useful in AND and OR logical operations as well as in arithmetic operations, so MIPS also provides the instructions and immediate (andi) and or immediate (ori) 38
29. CE Instructions: Language of the Computer 1. Introduction 2. Operations of the Computer Hardware 3. Operands of the Computer Hardware 4. Signed and Unsigned number 5. Representing Instructions in the Computer 6. Logical Operations 7. Instructions for Making Decisions 8. Supporting Procedures in Computer Hardware 9. Communicating with People 10. MIPS Addressing for 32-Bit Immediates and Addresses 11. Translating and Starting a Program 39
30. CE Instructions for Making Decisions  What distinguishes a computer from a simple calculator is its ability to make decisions.  In programming languages, decision making is commonly represented using the “if” statement, sometimes combined with “go to” statements and labels.  MIPS assembly language includes two decision-making instructions, similar to an “if” statement with a “go to”. Example: beq register1, register2, L1 This instruction means go to the statement labeled L1 if the value in register1 equals the value in register2. The mnemonic beq stands for “branch if equal” These such instructions are traditionally called conditional branches Conditional branch: An instruction that requires the comparison of two values and that allows for a subsequent transfer of control to a new address in the program based on the outcome of the comparison. 40
31. CE Instructions for Making Decisions Conditional branch instructions of MIPS: 41
32. CE Instructions for Making Decisions  Compiling if-then-else into Conditional Branches: In the following code segment, f, g, h, i, and j are variables. If the five variables f through j correspond to the five registers $s0 through $s4, what is the compiled MIPS code for this C if statement? if (i == j) f = g + h; else f = g – h;  Answer: bne $s3,$s4,Else # go to Else if i != j add $s0, $s1, $s2 # f = g + h (skipped if i != j) j exit # go to Exit else: sub $s0, $s1, $s2 # f = g – h (skipped if i = j) exit: 42
33. CE Instructions for Making Decisions  Compiling a while loop in C Here is a traditional loop in C: while (save[i] == k) i += 1; Assume that i and k correspond to registers $s3 and $s5 and the base of the array save is in $s6. What is the MIPS assembly code corresponding to this C segment?  Answer: Loop: sll $t1,$s3,2 # Temp reg $t1 = 4 * i add $t1,$t1,$s6 # $t1 = address of save[i] lw $t0,0($t1) # Temp reg $t0 = save[i] bne $t0,$s5, Exit # go to Exit if save[i] != k add $s3,$s3,1 # i = i + 1 j Loop # go to Loop Exit: 43
34. CE Instructions: Language of the Computer 1. Introduction 2. Operations of the Computer Hardware 3. Operands of the Computer Hardware 4. Signed and Unsigned number 5. Representing Instructions in the Computer 6. Logical Operations 7. Instructions for Making Decisions 8. Supporting Procedures in Computer Hardware 9. Communicating with People 10. MIPS Addressing for 32-Bit Immediates and Addresses 11. Translating and Starting a Program 44
35. CE Supporting Procedures in Computer Hardware  A procedure or function is one tool programmers use to structure programs, both to make them easier to understand and to allow code to be reused.  Procedures allow the programmer to concentrate on just one portion of the take at a time.  To execute of a procedure, the program must follow these six steps: 1. Put parameters in a place where the procedure can access them. 2. Transfer control to the procedure. 3. Acquire the storage resources needed for the procedure. 4. Perform the desired task. 5. Put the result value in a place where the calling program can access it. 6. Return control to the point of origin, since a procedure can be called from several points in a program. 45
36. CE Supporting Procedures in Computer Hardware  Registers are the fastest place to hold data in a computer, so we want to use them as much as possible.  MIPS software follows the following convention for procedure calling in allocating its 32 registers: ■ $a0-$a3: four argument registers in which to pass parameters ■ $v0-$v1: two value registers in which to return values ■ $ra: one return address register to return to the point of origin 46
37. CE Supporting Procedures in Computer Hardware  MIPS assembly language includes an instruction just for the procedures: it jumps to an address and simultaneously saves the address of the following instruction in register $ra. The jump-and-link instruction(jal) is simply written: jal ProcedureAddress  Nowadays, computers like MIPS use jump register instruction (jr), meaning an unconditional jump to the address specified in a register: jr $ra 47
38. CE Supporting Procedures in Computer Hardware Terms and definitions:  return address: A link to the calling site that allows a procedure to return to the proper address; in MIPS it is stored in register $ra.  caller: The program that instigates a procedure and provides the necessary parameter values.  callee: A procedure that executes a series of stored instructions based on parameters provided by the caller and then returns control to the caller.  program counter (PC): The register containing the address of the instruction in the program being executed.  stack: A data structure for spilling registers organized as a last-in first-out queue (In case compiler needs more registers for a procedure than the four argument and two return value registers).  stack pointer (SP): A value denoting the most recently allocated address in a stack that shows where registers should be spilled or where old register values can be found. In MIPS, it is register $sp.  push: Add element to stack.  pop: Remove element from stack. 48