Bài giảng Kiến trúc máy tính - Chương 3: Kiến trúc tập lệnh (ISA)

Nội dung text: Bài giảng Kiến trúc máy tính - Chương 3: Kiến trúc tập lệnh (ISA)

1. dce 2017 Chapter 3 MIPS Instruction Set Architecture Kiến trúc Máy tính– Chương 3 © Fall 2017 2
2. dce 2017 Kiến trúc tập lệnh (ISA)  Là dao diện chính giữa phần cứng và phần mềm, là cái nhìn trừu tượng của phần cứng trên quan điểm phần mềm  Kiến trúc tập lệnh bao gồm  Tập lệnh và định dạng lệnh  Kiểu dữ liệu, cách mã hóa và biễu diễn  Đối tượng lưu trữ: Thanh ghi (Registers) và bộ nhớ (Memory)  Các chế độ định địa chỉ để truy xuất lệnh và dữ liệu  Xử lý các điều kiện ngoại lệ (vd: chia cho 0)  Ví dụ (Phiên bản) Năm giới thiệu  Intel (8086, 80386, Pentium, ) 1978  MIPS (MIPS I, II, III, IV, V) 1986  PowerPC (601, 604, ) 1993 Kiến trúc Máy tính– Chương 3 © Fall 2017 4
3. dce 2017 Kiến trúc Stack latch latch stack ALU Memory latch stack pt Ví dụ lệnh: a = b+c; push b; push b push c add pop a push c; add; stack: b c b+c pop a; b Kiến trúc Máy tính– Chương 3 © Fall 2017 6
4. dce 2017 So sánh giữa các kiến trúc  Thanh ghi tích lũy  Một toán hạn (có thể là thanh ghi hoặc memory), thanh ghi tích lũy được sử dụng ngầm định  Stack  Không toán hạn: các toán hạn ngầm định trên đỉnh Stack (TOS)  Register (load store)  Ba toán hạn đều là thanh ghi  Load & Store là các lệnh dành riêng cho việc truy xuất memory (truy xuất gián tiếp thông qua thanh ghi)  Register-Memory  Hai toán hạn, một là memory  Memory-Memory  Ba toán hạn, có thể tất cả là memory Kiến trúc Máy tính– Chương 3 © Fall 2017 8
5. dce 2017 Ví dụ chương trình hợp ngữ MIPS Kiến trúc Máy tính– Chương 3 © Fall 2017 10
6. dce 2017 Sơ bộ kiến trúc MIPS . . . 4 bytes per word Memory Up to 232 bytes = 230 words . . . EIU $0 Execution & FPU F0 Floating 32 General $1 Integer Unit F1 Point Unit Purpose $2 (Main proc) F2 (Coproc 1) 32 Floating-Point Registers Registers $31 F31 Arithmetic & Integer FP ALU Logic Unit mul/div Arith Floating-Point Arithmetic Unit Hi Lo TMU BadVaddr Trap & Status Memory Unit Cause (Coproc 0) Integer EPC Multiplier/Divider Kiến trúc Máy tính– Chương 3 © Fall 2017 12
7. dce 2017 Quy ước tên gọi bộ thanh ghi MIPS  Assembler tham khảo thanh ghi bằng tên hoặc số  Lập trình viên thường dùng thanh ghi theo tên  Assembler chuyển tham khảo từ tên sang số Name Register Usage $zero $0 Always 0 (forced by hardware) $at $1 Reserved for assembler use $v0 – $v1 $2 – $3 Result values of a function $a0 – $a3 $4 – $7 Arguments of a function $t0 – $t7 $8 – $15 Temporary Values $s0 – $s7 $16 – $23 Saved registers (preserved across call) $t8 – $t9 $24 – $25 More temporaries $k0 – $k1 $26 – $27 Reserved for OS kernel $gp $28 Global pointer (points to global data) $sp $29 Stack pointer (points to top of stack) $fp $30 Frame pointer (points to stack frame) $ra $31 Return address (used by jal for function call) Kiến trúc Máy tính– Chương 3 © Fall 2017 14
8. dce 2017 Phân loại lệnh trong tập lệnh – nhóm lệnh  Các lệnh số học nguyên (Integer Arithmetic)  Các lệnh cộng/trừ, lệnh luận lý (and, or, nor, xor) và lệnh dịch (shift left, shift right)  Các lệnh truy xuất dữ liệu từ bộ nhớ (Data Transfer)  Lệnh Load&Store tương ứng thao tác Đọc/Ghi  Hỗ trợ dữ liệu byte (1byte), half word (2byte), word (4byte)  Nhảy và rẽ nhánh (Jump and Branch)  Các lệnh điều khiển dòng thực thi khác cách tuần tự  Các lệnh số học số thực (Floating Point Arithmetic)  Các lệnh thao tác trên các thanh ghi số thực  Các lệnh phụ  Các lệnh hỗ trợ xử lý ngoại lệ (exceptions)  Các lệnh quản lý bộ nhớ Kiến trúc Máy tính– Chương 3 © Fall 2017 16
9. dce 2017 R-Type Format Op6 Rs5 Rt5 Rd5 sa5 funct6  Op: mã phép toán (opcode)  Cho biết lệnh làm phép toán gì  funct: function code – mở rộng opcode  Có thể có 26 = 64 functions có thể mở rộng cho một opcode  MIPS sử dụng opcode 0 để định nghĩa lệnh loại R-type  Ba thanh ghi toán hạn (Register Operand)  Rs, Rt: Hai toán hạn nguồn  Rd: Toán hạn đích chứa kết quả  sa: Quy định số bit dịch trong các lệnh dịch Kiến trúc Máy tính– Chương 3 © Fall 2017 18
10. dce 2017 Số nguyên nhị phân không dấu  Cho 1 số n-bit, có dạng n  Tầm vực giá trị sẽ là: 0 đến +2 – 1  Ví dụ:  0000 0000 0000 0000 0000 0000 0000 10112 = 0 + + 1×23 + 0×22 +1×21 +1×20 = 0 + + 8 + 0 + 2 + 1 = 1110  Giá trị 1 số nhị phân không dấu 32-bit sẽ là:  0 đến +4,294,967,295 (giá trị thập phân) Kiến trúc Máy tính– Chương 3 © Fall 2017 20
11. dce 2017 Số âm có dấu  Đảo giá trị bit và cộng 1  Đảo giá trị bit: 1 → 0, 0 → 1  Ví dụ: giá trị (-) 2  +2 = 0000 0000 00102  –2 = 1111 1111 11012 + 1 = 1111 1111 11102 Kiến trúc Máy tính– Chương 3 © Fall 2017 22
12. dce 2017 Tầm biểu diễn của số nguyên có dấu Số nguyên có dấu n-bit: Tầm biểu diễn từ -2n–1 đến (2n–1 – 1) Các số dương: 0 đến 2n–1 – 1 Các số âm: -2n–1 đến -1 Storage Type Unsigned Range Powers of 2 Byte –128 to +127 –27 to (27 – 1) Half Word –32,768 to +32,767 –215 to (215 – 1) Word –2,147,483,648 to +2,147,483,647 –231 to (231 – 1) –9,223,372,036,854,775,808 to Double Word –263 to (263 – 1) +9,223,372,036,854,775,807 Câu hỏi: Cho biết tầm biểu diễn của số nguyên có dấu 20 bits? Kiến trúc Máy tính– Chương 3 © Fall 2017 24
13. dce 2017 Ví dụ về Nhớ/Tràn  “Nhớ” và “Tràn” là độc lập với nhau  Có bốn trường hợp (Ví dụ số 8-bit) 1 1 1 1 1 1 0 0 0 0 1 1 1 1 15 0 0 0 0 1 1 1 1 15 + + 0 0 0 0 1 0 0 0 8 1 1 1 1 1 0 0 0 248 (-8) 0 0 0 1 0 1 1 1 23 0 0 0 0 0 1 1 1 7 Carry = 0 Overflow = 0 Carry = 1 Overflow = 0 1 1 1 1 0 1 0 0 1 1 1 1 79 1 1 0 1 1 0 1 0 218 (-38) + + 0 1 0 0 0 0 0 0 64 1 0 0 1 1 1 0 1 157 (-99) 1 0 0 0 1 1 1 1 143 0 1 1 1 0 1 1 1 119 (-113) Carry = 0 Overflow = 1 Carry = 1 Overflow = 1 Kiến trúc Máy tính– Chương 3 © Fall 2017 26
14. dce 2017 Các phép toán luận lý  Xét 4 phép toán: and, or, xor, nor x y x and y x y x or y x y x xor y x y x nor y 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 0  AND có tính chất xóa: x and 0 = 0  OR có tính chất tạo: x or 1 = 1  XOR có tính chất đảo: x xor 1 = not x  NOR có thể dùng như NOT:  x nor x tương ứng not x Kiến trúc Máy tính– Chương 3 © Fall 2017 28
15. dce 2017 Phép dịch (Shift Operation)  Phép dịch thực hiện di chuyển tấc cả các bit của một thanh ghi sang trái hoặc phải  Có 3 lệnh dịch số lượng bit cố định: sll, srl, sra  sll/srl tương ứng shift left/right logical (số không dấu)  Trường “sa” (5-bit shift amount) chỉ số lượng bit được dịch  sra tương ứng shift right arithmetic (bảo toàn dấu)  Bit dấu (sign-bit) được thêm vào từ bên trái sll 32-bit register shift-out MSB . . . shift-in 0 srl shift-in 0 . . . shift-out LSB sra shift-in sign-bit . . . shift-out LSB Kiến trúc Máy tính– Chương 3 © Fall 2017 30
16. dce 2017 Phép nhân dựa trên phép dịch  Lệnh dịch trái (sll) có thể thực hiện phép nhân  Khi số nhân là mũ của 2  Một số nguyên bất kỳ có thể biểu diễn thành tổng của các số là mũ của 2  Ví dụ: nhân $s1 với 36 . Phân tích 36 thành (4 + 32) và sử dụng tính chất phân phối của phép nhân  $s2 = $s1*36 = $s1*(4 + 32) = $s1*4 + $s1*32 sll $t0, $s1, 2 ; $t0 = $s1 * 4 sll $t1, $s1, 5 ; $t1 = $s1 * 32 addu $s2, $t0, $t1 ; $s2 = $s1 * 36 Kiến trúc Máy tính– Chương 3 © Fall 2017 32
17. dce 2017 Tiếp theo  Kiến trúc tập lệnh (Instruction Set Architecture)  Sơ bộ kiến trúc bộ xử lý MIPS  R-Type Các lệnh số học, luận lý, dịch  I-Type Các lệnh số học, luận lý có hằng số  Các lệnh nhảy và rẽ nhánh  Chuyển phát biểu If và các biểu thức boolean  Các lệnh truy xuất bộ nhớ Load & Store  Chuyển đổi khối lặp và duyệt mảng  Các chế độ định địa chỉ Kiến trúc Máy tính– Chương 3 © Fall 2017 34
18. dce 2017 Các lệnh số học luận lý (ALU) kiểu I-Type Instruction Meaning I-Type Format addi $s1, $s2, 10 $s1 = $s2 + 10 op = 0x8 rs = $s2 rt = $s1 imm16 = 10 addiu $s1, $s2, 10 $s1 = $s2 + 10 op = 0x9 rs = $s2 rt = $s1 imm16 = 10 andi $s1, $s2, 10 $s1 = $s2 & 10 op = 0xc rs = $s2 rt = $s1 imm16 = 10 ori $s1, $s2, 10 $s1 = $s2 | 10 op = 0xd rs = $s2 rt = $s1 imm16 = 10 xori $s1, $s2, 10 $s1 = $s2 ^ 10 op = 0xe rs = $s2 rt = $s1 imm16 = 10 lui $s1, 10 $s1 = 10 << 16 op = 0xf 0 rt = $s1 imm16 = 10  addi: overflow sinh ra arithmetic exception  Trong trường hợp overflow, kết quả không được ghi vào thanh ghi đích  addiu: giống lệnh addi nhưng tràn số được bỏ qua  Hằng số 16 bit trong lệnh addi và addiu là số có dấu  Không có lệnh subi hoặc subiu  Hằng số 16 bit trong lệnh andi, ori, xori là số không dấu Kiến trúc Máy tính– Chương 3 © Fall 2017 36
19. dce 2017 Khởi tạo hằng số 32-bit???  Lệnh I-Type chỉ chứa hằng số 16-bit Op6 Rs5 Rt5 immediate16  Làm thế nào để khởi tạo giá trị 32-bit cho một thanh ghi?  Không thể có giá trị 32-bit trong lệnh I-Type   Gợi ý: dùng nhiều lệnh thay vì một lệnh Ví dụ: khởi tạo $s1=0xAC5165D9 (hằng số 32-bit) addiu $s1,$0,0xAC51 lui: load upper immediate sll $s1,$s1,16 ori $s1,$s1,0x65D9 load upper clear lower 16 bits 16 bits lui $s1,0xAC51 $s1=$17 0xAC51 0x0000 ori $s1,$s1,0x65D9 $s1=$17 0xAC51 0x65D9 Kiến trúc Máy tính– Chương 3 © Fall 2017 38
20. dce 2017 Định dạng lệnh J-Type Op6 immediate26  Định dạng J-type áp dụng cho các lệnh nhảy không điều kiện (unconditional jump, giống như lệnh goto): j label # jump to label . . . label:  Hằng số 26-bit được gắn vào trong lệnh Hằng số này cho biết địa chỉ nhảy đến  Thanh ghi Program Counter (PC) được thay đổi như sau: least-significant 4 26 Next PC = PC immediate 00 2 bits are 00 4 bit cao nhất của PC không đổi 2 bit cuối luôn bằng 00 Kiến trúc Máy tính– Chương 3 © Fall 2017 40
21. dce 2017 Các lệnh Set on Less Than  MIPS cung cấp lệnh gán bằng 1 khi nhỏ hơn (set on less than) slt rd,rs,rt if (rs < rt) rd = 1 else rd = 0 sltu rd,rs,rt unsigned < slti rt,rs,im16 if (rs < im16) rt = 1 else rt = 0 sltiu rt,rs,im16 unsigned <  So sánh có dấu / không dấu (Signed / Unsigned) Có thể sinh ra các kết quả khác nhau Giả sử $s0 = 1 và $s1 = -1 = 0xffffffff slt $t0,$s0,$s1 kết quả $t0 = 0 stlu $t0,$s0,$s1 kết quả $t0 = 1 Kiến trúc Máy tính– Chương 3 © Fall 2017 42
22. dce 2017 Các lệnh giả Pseudo-Instructions  Cung cấp bởi assembler và được tự động chuyển đổi sang lệnh có thật  Mục đích để hỗ trợ lập trình hợp ngữ được dễ dàng Pseudo-Instructions Các lệnh Thật tương ứng move $s1, $s2 addu Ss1, $s2, $zero not $s1, $s2 nor $s1, $s2, $s2 li $s1, 0xabcd ori $s1, $zero, 0xabcd lui $s1, 0xabcd li $s1, 0xabcd1234 ori $s1, $s1, 0x1234 sgt $s1, $s2, $s3 slt $s1, $s3, $s2 slt $at, $s1, $s2 blt $s1, $s2, label bne $at, $zero, label  Assembler dùng thanh ghi $at = $1 trong các chuyển đổi  $at được gọi là thanh ghi assembler temporary Kiến trúc Máy tính– Chương 3 © Fall 2017 44
23. dce 2017 Tiếp theo  Kiến trúc tập lệnh (Instruction Set Architecture)  Sơ bộ kiến trúc bộ xử lý MIPS  R-Type Các lệnh số học, luận lý, dịch  I-Type Các lệnh số học, luận lý, dịch có hằng số  Các lệnh nhảy và rẽ nhánh  Chuyển phát biểu If và các biểu thức boolean  Các lệnh truy xuất bộ nhớ Load & Store  Chuyển đổi khối lặp và duyệt mảng  Các chế độ định địa chỉ Kiến trúc Máy tính– Chương 3 © Fall 2017 46
24. dce 2017 Biểu thức điều kiện kết hợp AND  Ngôn ngữ lập trình sử dụng short-circuit evaluation  Nếu biểu thức đầu false, biểu thức thứ 2 được bỏ qua if (($s1 > 0) && ($s2 < 0)) {$s3++;} # One Possible Implementation bgtz $s1, L1 # first expression j next # skip if false L1: bltz $s2, L2 # second expression j next # skip if false L2: addiu $s3,$s3,1 # both are true next: Kiến trúc Máy tính– Chương 3 © Fall 2017 48
25. dce 2017 Biểu thức điều kiện kết hợp OR  Short-circuit evaluation cho phép OR  Nếu biểu thức 1 true, biểu thức kế tiếp được bỏ qua if (($sl > $s2) || ($s2 > $s3)) {$s4 = 1;}  Lời giải: bgt $s1, $s2, L1 # yes, execute if part ble $s2, $s3, next # no: skip if part L1: li $s4, 1 # set $s4 to 1 next:  bgt, ble, và li là những lệnh giả pseudo-instructions  Được assembler chuyển tự động sang các lệnh thật (Slide 44) Kiến trúc Máy tính– Chương 3 © Fall 2017 50
26. dce 2017 Tiếp theo  Kiến trúc tập lệnh (Instruction Set Architecture)  Sơ bộ kiến trúc bộ xử lý MIPS  R-Type Các lệnh số học, luận lý, dịch  I-Type Các lệnh số học, luận lý, dịch có hằng số  Các lệnh nhảy và rẽ nhánh  Chuyển phát biểu If và các biểu thức boolean  Các lệnh truy xuất bộ nhớ Load & Store  Chuyển đổi khối lặp và duyệt mảng  Các chế độ định địa chỉ Kiến trúc Máy tính– Chương 3 © Fall 2017 52
27. dce 2017 Load và Store dữ liệu Word (32-bit)  Lệnh Load Word (Word = 4 bytes in MIPS) lw Rt, imm16(Rs) # Rt MEMORY[Rs+imm16]  Lệnh Store Word sw Rt, imm16(Rs) # Rt MEMORY[Rs+imm16]  Các xác định địa chỉ ô nhớ dùng địa chỉ nền và độ dời: Memory Address = Rs (base) + Immediate16 (offset) Độ dời immediate16 được mở rộng dấu thành số 32 bit Định địa chỉ dùng địa chỉ nền và dộ dời Op6 Rs5 Rt5 immediate16 + Memory Word Base address Kiến trúc Máy tính– Chương 3 © Fall 2017 54
28. dce 2017 Địa chỉ theo Byte  Dữ liệu 8-bit bytes vẫn hữu dụng, hầu hết các kiến trúc hỗ trợ định địa chỉ bộ nhớ theo bytes  Alignment restriction – địa chỉ của một ô nhớ word phải là số chi hết cho kích thức một word (4 byte đối với MIPS-32)  Big Endian: leftmost byte is word address IBM 360/370, Motorola 68k, MIPS, Sparc, HP PA  Little Endian: rightmost byte is word address Intel 80x86, DEC Vax, DEC Alpha (Windows NT) little endian byte 0 3 2 1 0 msb lsb 0 1 2 3 big endian byte 0 Kiến trúc Máy tính– Chương 3 © Fall 2017 56
29. dce 2017 Ví dụ chi tiết dữ liệu lệnh Store Kiến trúc Máy tính– Chương 3 © Fall 2017 58
30. dce 2017 Load/Store Byte và Halfword  MIPS hỗ trợ kiểu dữ liệu: Byte = 8 bits, Halfword = 16 bits, Word = 32 bits  Lệnh Load & store cho bytes và halfwords lb = load byte,lbu = load byte unsigned, sb = store byte lh = load half, lhu = load half unsigned, sh = store halfword  Load mở rộng giá trị ô nhớ thành số 32-bit trong thanh ghi 32-bit Register s sign – extend s s b 0 zero – extend 0 bu s sign – extend s s h 0 zero – extend 0 hu Kiến trúc Máy tính– Chương 3 © Fall 2017 60
31. dce 2017 Tiếp theo  Kiến trúc tập lệnh (Instruction Set Architecture)  Sơ bộ kiến trúc bộ xử lý MIPS  R-Type Các lệnh số học, luận lý, dịch  I-Type Các lệnh số học, luận lý, dịch có hằng số  Các lệnh nhảy và rẽ nhánh  Chuyển phát biểu If và các biểu thức boolean  Các lệnh truy xuất bộ nhớ Load & Store  Chuyển đổi khối lặp và duyệt mảng  Các chế độ định địa chỉ Kiến trúc Máy tính– Chương 3 © Fall 2017 62
32. dce 2017 Sử dụng con trỏ để duyệt Arrays  Xét phát biểu WHILE: i = 0; while (A[i] != k) i = i+1; A là mảng số nguyên 4 byte Giả sử địa chỉ A, i, k tương ứng $s0, $s1, $s2  Sử dụng con trỏ (Pointer) để duyệt mảng A Pointer được tăng lên 4 (faster than indexing) move $t0, $s0 # $t0 = $s0 = addr A j cond # test condition loop: addiu $s1, $s1, 1 # i = i+1 addiu $t0, $t0, 4 # point to next cond: lw $t1, 0($t0) # $t1 = A[i] bne $t1, $s2, loop # loop if A[i]!= k  Chỉ còn 4 lệnh (thay vì 6) trong thân vòng lặp Kiến trúc Máy tính– Chương 3 © Fall 2017 64
33. dce 2017 Tính tổng của một mảng nguyên sum = 0; for (i=0; i<n; i++) sum = sum + A[i]; Giả sử $s0 = địa chỉ của A, $s1 = kích thức mảng = n move $t0, $s0 # $t0 = address A[i] xor $t1, $t1, $t1 # $t1 = i = 0 xor $s2, $s2, $s2 # $s2 = sum = 0 L1: lw $t2, 0($t0) # $t2 = A[i] addu $s2, $s2, $t2 # sum = sum + A[i] addiu $t0, $t0, 4 # point to next A[i] addiu $t1, $t1, 1 # i++ bne $t1, $s1, L1 # loop if (i != n) Kiến trúc Máy tính– Chương 3 © Fall 2017 66
34. dce 2017 Các chế độ định địa chỉ  Địa chỉ (vị trí) của toán hạn?  Địa chỉ của ô nhớ được tính như thế nào? Immediate Addressing Op6 Rs5 Rt5 immediate16 Operand is a constant Register Addressing Op6 Rs5 Rt5 Rd5 sa5 funct6 Operand is in a register Register Operand is in memory (load/store) Base or Displacement Addressing Op6 Rs5 Rt5 immediate16 + Byte Halfword Word Register = Base address Kiến trúc Máy tính– Chương 3 © Fall 2017 68
35. dce 2017 Giới hạn của lệnh nhảy và rẽ nhánh  Phạm vi địa chỉ của lệnh Jump = 226 lệnh = 256 MB  Nhảy đến vị trí không quá 226 lệnh hoặc 256 MB  4 bit cao của PC không đổi Địa chỉ đích của lệnh Jump PC4 immediate26 00  Phạm vi địa chỉ của lệnh rẽ nhánh  Lệnh rẽ nhánh có định dạng I-Type (16-bit hằng số)  Định địa chỉ tương đối với PC: PC30 + immediate16 + 1 00 . Địc chỉ đích = PC + 4×(1 + immediate16) . Là số lệnh tính từ vị trí lệnh kế của lệnh rẽ nhánh . Hằng số dương => Forward, Hằng số âm => Backward . Khoảng cách xa nhất ±215 lệnh (thông thường lệnh rẽ nhánh có địch chỉ đích lân cận vị trí lệnh) Kiến trúc Máy tính– Chương 3 © Fall 2017 70
36. dce 2017 Four Design Principles 1. Simplicity favors regularity  Fix the size of instructions (simplifies fetching & decoding)  Fix the number of operands per instruction . Three operands is the natural number for a typical instruction 2. Smaller is faster  Limit the number of registers for faster access (typically 32) 3. Make the common case fast  Include constants inside instructions (faster than loading them)  Design most instructions to be register-to-register 4. Good design demands good compromises  Fixed-size instructions compromise the size of constants Kiến trúc Máy tính– Chương 3 © Fall 2017 72