So sánh hai số nguyên trong mips năm 2024

1. trúc MIPS Phạm Tuấn Sơn ptson@fit.hcmus.edu.vn
2. này, SV có khả năng: – Giải thích quan điểm thiết kế bộ lệnh MIPS – Có khả năng lập trình hợp ngữ MIPS Mục tiêu
3. cơ bản nhất của bộ xử lý là xử lý các lệnh máy [instruction]. • Tập hợp các lệnh mà một bộ xử lý nào đó cài đặt gọi là bộ lệnh [Instruction Set]. • Các bộ xử lý khác nhau cài đặt các bộ lệnh khác nhau. – Ví dụ: Pentium 4 [Intel], MIPS R3000 [MIPS Technology Inc], ARM2 [ARM], PowerPC 601 [IBM], SPARC V8 [Sun],… • Câu hỏi – Một chương trình thực thi [.exe] chạy trên bộ xử lý Pentium 3 [Intel] có thể chạy được trên bộ xử lý Pentium 4 [Intel] không ? – Một chương trình thực thi [.exe] chạy trên một bộ xử lý của Intel có thể chạy được trên bộ xử lý của AMD ? Bộ lệnh
4. lệnh • Các bộ xử lý khác nhau có cùng kiến trúc bộ lệnh [Instruction Set Architecture - ISA] có thể thực thi cùng một chương trình • x86 [máy tính cá nhân – PC, laptop, netbook] – x86-32 [IA-32/ i386]: Intel 80386, Intel 80486, Intel Pentium, AMD Am386, AMD Am486, AMD K5, AMD K6,… – x86-64: Intel 64 [Intel Pentium D, Intel Core 2, Intel Core i7, Intel Atom,…], AMD64 [AMD Athlon 64, AMD Phenom , …] • IA-64: Pentium Itanium [máy chủ - server] • MIPS [hệ thống nhúng – embedded system và siêu máy tính – supercomputer] – MIPS32: R2000, R3000, R6000,… – MIPS64: R4000, R5000, R8000,… • Ngoài ra, PowerPC [máy chủ, hệ thống nhúng], SPARC [máy chủ], ARM [hệ thống nhúng], … 4
5. thiết kế bộ lệnh MIPS • Cấu trúc lệnh đơn giản và có quy tắc [Simplicity favors regularity] • Lệnh và bộ lệnh càng nhỏ gọn càng xử lý nhanh [Smaller is faster] • Tăng tốc độ xử lý cho những trường hợp thường xuyên xảy ra [Make the common case fast] • Thiết kế tốt đòi hỏi sự thỏa hiệp tốt [Good design demands good compromises]
6. sát và nhận xét • MIPS chỉ cần hỗ trợ 32 thanh ghi là đủ, đánh số từ $0 - $31 • Mỗi thanh ghi có kích thước 32 bit [4 byte] • Các phép toán luận lý và số học như a = b + c a = b & c a = b thì sao? • Hướng tiếp cận – Thêm tất cả các lệnh so sánh không bằng: bgt, blt, ble, bge ? – Chỉ cần thêm 1 lệnh mà có thể thực hiện các phép so sánh không bằng • MIPS hỗ trợ lệnh: – “Set on Less Than” – Cú pháp: slt reg1,reg2,reg3 [Cấu trúc R-Format] – Ý nghĩa if [reg2 < reg3] reg1 = 1; else reg1 = 0; “set” nghĩa là “set to 1” “reset” nghĩa là “set to 0” So sánh không bằng trong MIPS [1/3]
62. bằng trong MIPS [2/3] • Câu lệnh sau: if [g < h] goto Less;
g:$s0, h:$s1 • Được chuyển thành lệnh MIPS như sau… slt $t0,$s0,$s1 # $t0 = 1 if gb # do if a= 1] goto Loop Loop: . . . slti $t0,$s0,1 # $t0 = 1 if # $s0 2 && j < i 5: j < 2 || j < i 6: j ≥ 2 || j < i 7: j < 2 || j ≥ i 8: j ≥ 2 || j ≥ i 9: j > 2 || j < i [$s0=i, $s1=j] Trắc nghiệm
68. số lệnh MIPS đã tìm hiểu 68 Hình 2.13 trang 78, P&H
69. C main[] { int a,b,c; ... c = sum[a,b]; ... } /* khai báo hàm sum */ int sum [int x, int y]{ return x+y; } • Lời gọi thủ tục và khai báo thủ tục được chuyển thành lệnh máy như thế nào ? • Đối số được truyền vào thủ tục như thế nào ? • Kết quả trả về của thủ tục được truyền ra ngoài như thế nào ?
70. gọi thủ tục thì lệnh tiếp theo được thực hiện là lệnh đầu tiên của thủ tục à Có thể xem tên thủ tục là một nhãn và lời gọi thủ tục là một lệnh nhảy tới nhãn này sum[a,b]; j sum # nhảy tới # nhãn sum ... ... int sum [...] sum: • Sau khi thực hiện xong thủ tục phải quay về thực hiện tiếp lệnh ngay sau lời gọi thủ tục return ... j ? C MIPS
71. { ... c=sum[a,b];/* a,b:$s0,$s1 */ ... } int sum[int x, int y] { return x+y; } địa chỉ 1000 add $a0,$s0,$zero # x = a 1004 add $a1,$s1,$zero # y = b 1008 addi $ra,$zero,1016 # lưu địa chỉ quay về # vào $ra=1016 1012 j sum # nhảy tới nhãn sum 1016 ... 2000 sum: add $v0,$a0,$a1# khai báo thủ tục sum 2004 jr $ra # nhảy tới địa chỉ # trong $ra • Hỏi: Tại sao lại dùng jr ? Mà không đơn giản dùng j? • Trả lời: thủ tục sum có thể được gọi ở nhiều chỗ khác nhau, do đó vị trí quay về mỗi lần gọi khác nhau sẽ khác nhau.
72. vì phải dùng 2 lệnh để lưu địa chỉ quay về vào $ra và nhảy tới thủ tục: 1008 addi $ra,$zero,1016 # $ra=1016 1012 j sum # goto sum • MIPS còn hỗ trợ 1 lệnh jal [jump and link] để thực hiện 2 công việc trên: 1008 jal sum # $ra=1012,goto sum • Tại sao lai thêm lệnh jal? – không cần phải xác định tường minh địa chỉ quay về trong $ra • Lý do nào khác ?
73. { ... c=sum[a,b];/* a,b:$s0,$s1 */ ... } int sum[int x, int y] { return x+y; } địa chỉ 1000 add $a0,$s0,$zero # x = a 1004 add $a1,$s1,$zero # y = b 1008 jal sum # lưu địa chỉ quay về # vào $ra=1012 và nhảy # tới sum 1012 ... 2000 sum: add $v0,$a0,$a1# khai báo thủ tục sum 2004 jr $ra # nhảy tới địa chỉ # trong $ra
74. jal [jump and link]: J-Format – Cú pháp: jal label – 1 [link]: Lưu địa chỉ của lệnh kế tiếp vào thanh ghi $ra – 2 [jump]: nhảy tới nhãn label • Lệnh jr [jump register]: R-Format – Cú pháp: jr register – Nhảy tới địa chỉ nằm trong thanh ghi register • 2 lệnh này được sử dụng hiệu quả trong thủ tục: – jal lưu địa chỉ quay về vào thanh ghi $ra và nhảy tới thủ tục – jr $ra Nhảy tới địa chỉ quay về đã được lưu trong $ra
75. trợ thêm một số thanh ghi để lưu trữ các dữ liệu phục vụ cho thủ tục: – Đối số $a0, $a1, $a2, $a3 – Kết quả trả về $v0, $v1 – Địa chỉ quay về $ra • Nếu thủ tục sử dụng nhiều dữ liệu [đối số, kết quả trả về, biến cục bộ] hơn số lượng thanh ghi kể trên ? Sử dụng thêm nhiều thanh ghi hơn… Bao nhiêu thanh ghi cho đủ ? à Sử dụng ngăn xếp [stack] Các thanh ghi mới
76. = mult[j,k]; ... m = mult[i,i]; ... } /* khai báo hám mult */ int mult [int mcand, int mlier]{ int product; product = 0; while [mlier > 0] { product = product + mcand; mlier = mlier -1; } return product; } 76 Bài tập
77. nhau int sumSquare[int x, int y] { return mult[x,x]+ y; } • Thủ tục sumSquare gọi thủ tục mult. • Vấn đề – Địa chỉ quay về của thủ tục sumSquare trong thanh ghi $ra sẽ bị ghi đè bởi địa chỉ trả về của thủ tục mult khi thủ tục này được gọi – Như vậy cần phải lưu lại địa chỉ quay về của thủ tục sumSquare [trong thanh ghi $ra ] trước khi gọi thủ tục mult. à Sử dụng thanh ghi…Bao nhiêu cho đủ? à Sử dụng ngăn xếp [stack].
78. chương trình Static Vùng nhớ chứa các biến cấp phát tĩnh của mỗi chương trình. Ví dụ: biến toàn cục của C Heap Vùng nhớ chứa các biến cấp phát động. Ví dụ: con trỏ C được cấp phát động bởi hàm malloc[] Stack Vùng nhớ được sử dụng trong quá trình thực thi thủ tục như lưu các biến cục bộ, lưu địa chỉ trả về,…$sp Con trỏ ngăn xếp • Một chương trình C thực thi sẽ được cấp phát các vùng nhớ sau: Mô hình cấp phát bộ nhớ của C
79. xếp [1/2] • Con trỏ ngăn xếp, thanh ghi $sp, được sử dụng để định vị vùng ngăn xếp. • Để sử dụng ngăn xếp, cần khai báo kích thước vùng ngăn xếp bằng cách tăng giá trị con trỏ ngăn xếp. • Lệnh MIPS tương ứng với int sumSquare[int x, int y] { return mult[x,x]+ y; }
80. khai báo kích thước # ngăn xếp cần dùng sw $ra, 4[$sp] # cất địa chỉ quay về # của thủ tuc sumSquare # vào ngăn xếp sw $a1, 0[$sp] # cất y vào ngăn xếp add $a1,$a0,$zero # gán x vào $a1 jal mult # gọi thủ tục mult lw $a1, 0[$sp] # sau khi thực thi xong # thủ tục mult, khôi # phục y từ ngăn xếp add $v0,$v0,$a1 # mult[]+y lw $ra, 4[$sp] # lấy lại địa chỉ quay về # của thủ tục sumSquare # đã lưu vào ngăn xếp, # đưa vào thanh ghi $ra addi $sp,$sp,8 # kết thúc dùng ngăn xếp jr $ra mult: ... “push” “pop” # x,y : $a0,$a1 Sử dụng ngăn xếp [2/2]
81. $ra, framesize-4[$sp] # cất địa chỉ trả # về của thủ tục # trong $ra vào # ngăn xếp Lưu tạm các thanh ghi khác nếu cần Phục hồi các thanh ghi khác nếu cần lw $ra, framesize-4[$sp] # khôi phục $ra addi $sp,$sp, framesize jr $ra Cuối thủ tục Đầu thủ tục Thân thủ tục … [có thể gọi các thủ tục khác…] ra memory Cấu trúc cơ bản của thủ tục
82. tắc sử dụng thủ tục • Thủ tục R [caller] gọi thủ tục E [callee] Trong thủ tục R 1. Lưu địa chỉ trả về [trong $ra] của R vào ngăn xếp 2. Gán các đối số [nếu có] R truyền vào E 3. Gọi lệnh jal Trong thủ tục E 3. Khởi tạo ngăn xếp 4. Lưu vào ngăn xếp các thanh ghi trong R có thể bị thay đổi trong E. 5. … 6. Khôi phục các dữ liệu đã lưu tạm trong ngăn xếp 7. Phục hồi ngăn xếp 8. Gọi lệnh jr $ra để trở lại thủ tục R
83. MIPS… A. CÓ THỂ sao lưu $a0 vào $a1 [và sau đó không lưu lại $a0 hay $a1 vào ngăn xếp] để lưu lại n qua những lời gọi đệ qui. B. PHẢI lưu $a0 vào ngăn xếp vì nó sẽ thay đổi. C. PHẢI lưu $ra vào ngăn xếp do cần để biết địa chỉ quay về… ABC 0: FFF 1: FFT 2: FTF 3: FTT 4: TFF 5: TFT 6: TTF 7: TTT int fact[int n]{ if[n == 0] return 1; else return[n*fact[n-1]];} Trắc nghiệm
84. cần cất các thanh ghi nào vào ngăn xếp trước khi gọi “jal e”? 0: 0 of [$s0,$sp,$v0,$t0,$a0,$ra] 1: 1 of [$s0,$sp,$v0,$t0,$a0,$ra] 2: 2 of [$s0,$sp,$v0,$t0,$a0,$ra] 3: 3 of [$s0,$sp,$v0,$t0,$a0,$ra] 4: 4 of [$s0,$sp,$v0,$t0,$a0,$ra] 5: 5 of [$s0,$sp,$v0,$t0,$a0,$ra] 6: 6 of [$s0,$sp,$v0,$t0,$a0,$ra] r: ... # đọc ghi $s0,$v0,$t0,$a0,$sp,$ra,mem ... ### cất các thanh ghi vào ngăn xếp? jal e # gọi thủ tục e ... # đọc ghi $s0,$v0,$t0,$a0,$sp,$ra,mem jr $ra # quay về thủ tục gọi r e: ... # đọc ghi $s0,$v0,$t0,$a0,$sp,$ra,mem jr $ra # quay về thủ tục r Trắc nghiệm
85. cần cất các thanh ghi nào vào ngăn xếp trước khi gọi “jal e”? 0: 0 of [$s0,$sp,$v0,$t0,$a0,$ra] 1: 1 of [$s0,$sp,$v0,$t0,$a0,$ra] 2: 2 of [$s0,$sp,$v0,$t0,$a0,$ra] 3: 3 of [$s0,$sp,$v0,$t0,$a0,$ra] 4: 4 of [$s0,$sp,$v0,$t0,$a0,$ra] 5: 5 of [$s0,$sp,$v0,$t0,$a0,$ra] 6: 6 of [$s0,$sp,$v0,$t0,$a0,$ra] r: ... # đọc ghi $s0,$v0,$t0,$a0,$sp,$ra,mem ... ### cất các thanh ghi vào ngăn xếp? jal e # gọi thủ tục e ... # đọc ghi $s0,$v0,$t0,$a0,$sp,$ra,mem jr $ra # quay về thủ tục gọi r e: ... # đọc ghi $s0,$v0,$t0,$a0,$sp,$ra,mem jr $ra # quay về thủ tục r Không cần cất vào ngăn xếp Cần cất vào ngăn xếp Đáp án
86. $0 $zero Reserved for Assembler $1 $at Return Values $2-$3 $v0-$v1 Arguments $4-$7 $a0-$a3 Temporary $8-$15 $t0-$t7 Saved $16-$23 $s0-$s7 More Temporary $24-$25 $t8-$t9 Used by Kernel $26-27 $k0-$k1 Global Pointer $28 $gp Stack Pointer $29 $sp Frame Pointer $30 $fp Return Address $31 $ra Vai trò 32 thanh ghi của MIPS
87. dụng thanh ghi [1/2] • $0: Không thay đổi. Luôn bằng 0. • $s0-$s7: Khôi phục nếu thay đổi. Rất quan trọng. Nếu thủ tục được gọi [callee] thay đổi các thanh ghi này thì nó phải phục hồi các thanh ghi này trước khi kết thúc. • $sp: Khôi phục nếu thay đổi. Thanh ghi con trỏ ngăn xếp phải có giá trị không đổi trước và sau khi gọi lệnh jal , nếu không thủ tục gọi [caller] sẽ không quay về được. • Dễ nhớ: tất cả các thanh ghi này đều bắt đầu bằng ký tự s!
88. dụng thanh ghi [2/2] • $ra: Có thể thay đổi. Lời gọi lệnh jal sẽ làm thay đổi giá trị thanh ghi này. Thủ tục gọi lưu lại thanh ghi này vào ngăn xếp nếu cần. • $v0-$v1: Có thể thay đổi. Các thanh ghi này chứa các kết quả trả về. • $a0-$a3: Có thể thay đổi. Đây là các thanh ghi chứa đối số. Thủ tục gọi cần lưu lại giá trị nếu nó cần sau khi gọi thủ tục. • $t0-$t9: Có thể thay đổi. Đây là các thanh ghi tạm nên có thể bị thay đổi bất kỳ lúc nào. Thủ tục gọi cần lưu lại giá trị nếu nó cần sau các lời gọi thủ tục.
89. cấu trúc lệnh MIPS 89 Hình 2.26 trang 104, P&H
90. số lệnh MIPS đã tìm hiểu 90 Hình 2.47 trang 146, P&H
91. giả [Pseudo Instruction] là các lệnh hợp ngữ không có cài đặt lệnh máy tương ứng, nhằm mục đích giúp cho việc lập trình hợp ngữ dễ dàng hơn 91 Hình 2.47 trang 146, P&H
92. thực hiện nhập xuất 92
93. Quá trình biên dịch và thực thi chương trình [phần 2.10, trang 106-115, P&H] + các khái niệm – Symbol table – Compiler, Linker, Loader – Dynamically Linked Library [DLL] – Java bytecode, Java Virtual Machine [JVM], Just In Time Compiler [JIT] • Bộ lệnh Intel IA-32 [phần 2.16, trang 134-143, P&H] + các khái niệm – General Purpose Register [GPR] – Addressing Modes 93
94. 2, trang 28, P&H 94
95. trúc và hoạt động của Bộ xử lý Phạm Tuấn Sơn ptson@fit.hcmus.edu.vn
96. tính 2 Máy tính [Computer] Bộ nhớ chính [Main Memory] Thiết bị nhập xuất [Input Output] Hệ thống kết nối [Bus] Bộ xử lý [Central Processing Unit] Máy tính
97. trình 3
98. xử lý 4 Computer CPU I/O Memory System Bus Đơn vị xử lý [Arithmetic & Logic Unit] Đơn vị điều khiển [Control Unit] Internal Bus Thanh ghi [Registers] Bộ xử lý [CPU] Xử lý, tính toán trên dữ liệu lưu trong thanh ghi Điều khiển xử lý của ALU và dữ liệu trên thanh ghi Lưu trữ tạm dữ liệu để ALU, CU xử lý và điều khiển Kết nối giữa các thành phần CU, ALU và Register trong CPU
99. máy [machine instruction/ instruction/ machine code] là dãy bit chứa yêu cầu mà bộ xử lý phải thực hiện • Cấu trúc của một lệnh máy thường gồm: – Mã thao tác [opcode]: cho biết lệnh thực hiện thao tác gì [+. –, and, or, …] – Các toán hạng [operand]: cho biết các đối tượng bị tác động bởi thao tác trong mã thao tác [thanh ghi, vùng nhớ, hằng số, …] • Mỗi bộ xử lý chỉ hiểu được một số lệnh với một vài cấu trúc nhất định 5
100. trình… …cụ thể hơn 6
101. CPU • Xử lý lệnh máy qua 2 bước, gọi là chu kỳ lệnh [instruction cycle] – Nạp lệnh [Fetch] • Di chuyển lệnh từ bộ nhớ vào thanh ghi – Thực thi lệnh • Giải mã lệnh và thực hiện thao tác yêu cầu 7
102. lệnh 8 • Thanh ghi MAR [Memory Address Register] – Lưu địa chỉ được gửi ra/ nhận vào từ bus địa chỉ. • Thanh ghi MBR [Memory Buffer Register] – Lưu giá trị được gửi ra/ nhận vào từ bus dữ liệu. • Thanh ghi PC [Program Counter] – Lưu địa chỉ của lệnh sẽ được nạp. • Thanh ghi IR [Instruction Register] – Lưu lệnh sẽ được xử lý. • Bộ xử lý di chuyển lệnh từ vùng nhớ có địa chỉ trong thanh ghi PC vào thanh ghi IR. • Mặc định, giá trị thanh ghi PC được tăng 1 lượng bằng chiều dài của lệnh được nạp. • MAR ß [PC] • MBR ß Memory • IR ß [MBR] • PC ß [PC] + 1
103. thi lệnh 9 • Bộ xử lý giải mã lệnh trong thanh ghi IR và thực hiện thao tác yêu cầu như: – Thực hiện các phép tính số học và luận lý – Thực hiện di chuyển dữ liệu giữa thanh ghi và bộ nhớ – Thực hiện di chuyển dữ liệu giữa thanh ghi và thiết bị nhập xuất – Thực hiện các thao tác điều khiển như rẽ nhánh
104. trình xử lý lệnh của CPU Mã thao tác Địa chỉ 10 4 bit 12 bit Cấu trúc lệnh Mã thao tác 0001 = Nạp dữ liệu từ “địa chỉ” vào thanh ghi AC 0010 = Lưu dữ liệu từ thanh ghi AC vào bộ nhớ tại “địa chỉ” 0101 = Cộng dồn giá trị tại “địa chỉ” vào thanh ghi AC Các thanh ghi: PC, IR, AC Nạp lệnh Thực thi lệnh
105. tổng quát 11 1. Tính địa chỉ của lệnh 2. Nạp lệnh 3. Giải mã lệnh 4. Tính địa chỉ của toán hạng 5. Nạp toán hạng 6. Thực thi lệnh 7. Tính địa chỉ của toán hạng chứa kết quả 8. Ghi kết quả
106. là cơ chế cho phép ngắt quá trình thực thi tuần tự thông thường từng lệnh của bộ xử lý để phục vụ công việc khác như nhập xuất. • Một số loại ngắt – Ngắt chương trình • Debug chương trình • Trường hợp tràn số, chia cho 0,… – Ngắt đồng hồ • Được phát sinh bởi bộ định giờ bên trong bộ xử lý • Được sử dụng trong các môi trường đa nhiệm – Nhập xuất • Ví dụ: nhập ký tự,… – Lỗi phần cứng • Ví dụ: lỗi truyền dữ liệu,..
107. vụ ngắt • Bộ xử lý kiểm tra ngắt mỗi khi thực thi xong 1 lệnh dựa vào tín hiệu ngắt • Nếu không có ngắt, nạp lệnh kế tiếp có địa chỉ trong PC. • Nếu có ngắt: – Tạm ngừng thực thi tiếp các lệnh của chương trình đang được thực hiện. – Lưu lại các dữ liệu đang thực hiện dang dở của chương trình. – Đặt địa chỉ bắt đầu thủ tục xử lý ngắt vào thanh ghi PC. – Xử lý ngắt – Khôi phục các dữ liệu đang thực hiện dang dở của chương trình bị ngắt và tiếp tục thực hiện chương trình này
108. 12, William Stallings 14