Bài tập 4-way associative tối đa tag năm 2024

Nội dung 1 Kiểu lệnh 1.1 Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3

2 Single clock processor 2.1 Single clock processor 2.2 Kiến trúc single cycle 2.2.1 phần cứng . . . 2.2.2 Datapath . . . 2.3 Bài tập . . . . . . . . 2.4 Đáp án/Gợi ý . . . . .

3 3 4 4 6 6 6

. . . . . .

3 Pipeline processor 3.1 Pipeline processor . . . . . . . . . . . . . . . 3.1.1 Các bước trong pipeline . . . . . . . . 3.1.2 Hiệu suất. . . . . . . . . . . . . . . . . 3.2 Hazard . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Structural hazard . . . . . . . . . . . . 3.2.2 Data hazards . . . . . . . . . . . . . . 3.2.3 Phương pháp giải quyết data hazard. . 3.3 Control hazard . . . . . . . . . . . . . . . . . 3.4 Bài tập . . . . . . . . . . . . . . . . . . . . . 3.5 Đáp án/gợi ý . . . . . . . . . . . . . . . . . .

. . . . . . . . . .

8 . 8 . 8 . 8 . 8 . 8 . 8 . 9 . 10 . 10 . 11

4 Memory 4.1 Memory . . . . . . . . . . . . . . 4.2 Cache . . . . . . . . . . . . . . . 4.2.1 Block placement . . . . . 4.2.2 Block identification . . . . 4.2.3 Block replacement . . . . 4.2.4 Write strategy . . . . . . 4.2.5 Miss/hit . . . . . . . . . . 4.3 CPI . . . . . . . . . . . . . . . . 4.4 Thời gian truy xuất bộ nhớ trung 4.5 Bài tập . . . . . . . . . . . . . . 4.6 Đáp án/Gợi ý . . . . . . . . . . . 4.7 Virtual Memory . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . bình . . . . . . . . .

. . . . . .

. . . . . . . . . . . .

. . . . . .

. . . . . . . . . . . .

. . . . . .

. . . . . . . . . . . .

12 12 12 12 13 14 14 14 15 15 16 16 18

Ôn Tập 1

Kiểu lệnh

R-type Op6 Rs5 Kiểu I-type Op6 Rs5 Kiểu J-type Op6

Rt5

Rd5

Rt5

Shamt5

F unction6

Immediate16 Immediate26

• Op [operation code] Mã lệnh, dùng để xác định kiểu lệnh, và lệnh thực thi [Kiểu R thì Op = 0]. • Rs, Rt, Rd [register]: Trường xác định thanh ghi [trường thanh ghi 5 bit tương ứng với 32 thanh ghi]. • Shamt [shift amount]: Xác định số bits dịch trong các lệnh dịch bit. • Function: Xác định toán tử[operator hay còn gọi là lệnh] trong kiểu lệnh R. • Immediate: Số trực tiếp, địa chỉ.

1.1

Bài tập

Bài 1.1. Cho đoạn code hợp ngữ MIPS sau: addi $a0, $zero, 100 addi $a1, $zero, 0 add $a2, $zero, $zero

1 2 3 4

loop: beq $a0, $a1, exit add $a2, $a2, $a1 addi $a1, $a1, 1 j loop

5 6 7 8 9

// upper threshold // count variable // sum initialization

exit: [a] Xác định loại lênh của từng lệnh trong đoạn code trên. [b] Xét lệnh 5, xác định khoảng cách rẽ nhánh tối đa của lệnh beq [c] Giả sử địa chỉ bắt đầu của đoạn chương trình trên là 0x 10 00 00 00. Xác định mã máy của lệnh j loop

Single clock processor

2.1

Single clock processor

• Ưu điểm: Một lệnh một chu kỳ, đơn giản. • Nhược điểm: Một chu kỳ tốn nhiều thời gian, mỗi lệnh dù nhanh hay chậm đều thực thi trong một chu kỳ, hiệu suất thấp.

2.2 2.2.1

Kiến trúc single cycle phần cứng

Hình. 1: Kiến trúc bộ xử lý MIPS single clock cycle • Thanh PC: Trỏ đến lệnh đang thực thi. • Instruction memory: Chứa code thực thi, khối này chỉ cho phép đọc. • Registers file: Chứa 32 thanh ghi, do đó cần 5 bit để xác định thanh ghi [25 = 32]. Để xác định chi tiết thanh ghi, ta tham khảo Bảng 1. • Sign-extern: Bộ mở rộng dấu, mở rộng dấu 16 bits → 32 bits. • Bộ chọn [MUX]: Dùng để chọn input cho output tương ứng. Tín hiệu select đưa ra sự lựa chọn. • ALU: Thực hiện tính toán. • Data memory: Là vùng nhớ để chứa dữ liệu trong phần data. Chỉ có lệnh LOAD và STORE mới truy xuất vào khối Data Memory này. • Control: Khối điều khiển, sinh ra tín hiệu điều khiển dựa vào mã lệnh Opcode.

0 1 2-3 4-7 8-15 16-23 24-25 26-27 28 29 30 31

zero at v0-v1 a0-a3 t0-t7 s0-s7 t8-t9 k0-k1 gp sp fp/s8 ra

Bảng. 1: Danh sách 32 thanh ghi REGISTERS Always equal to zero Assembler temporary; used by the assembler Return value from a function call First four parameters for a function call Temporary variables; need not be preserved Function variables; must be preserved Two more temporary variables Kernel use registers; may change unexpectedly Global pointer Stack pointer Stack frame pointer or subroutine variable Return address of the last subroutine call

Bảng. 2: Giá trị ALUop Input output 4 bit encoding Op[6bit] funct[6bit] ALUCtrl R-type Add ADD 0000 R-type Sub SUB 0010 R-type And AND 0100 R-type Or OR 0101 R-type Xor XOR 0110 R-type Slt SLT 1010 Addi X ADD 0000 Slti X SLT 1010 Andi X AND 0100 Ori X OR 0101 Xori X XOR 0110 Lw X ADD 0000 Sw X ADD 0000 Beq X SUB 0010 Bne X SUB 0010 J X X xxxx

Bảng. 3: Ý nghĩa của các tín hiệu điều khiển. Ta giả sử tín hiệu tích cực ở mức cao [HIGH].

Tín hiệu RegDest RegWrite ALUSrc Memwrite MemRead MemtoReg Branch Jump

Ý nghĩa Chọn thanh ghi kết quả Cho phép ghi kết quả ngược vào thanh ghi Chọn thanh ghi hoặc số để đưa vào ALU Cho phép ghi vào vùng data memory Cho phép đọc từ vùng data memory Dùng để chọn đường từ data memory đến thanh ghi Dùng cho các lệnh nhảy/rẽ nhánh có điều kiện Dùng cho các lệnh nhảy/rẽ nhánh không có điều kiện

Giá trị [tích cực] Chọn Rd để ghi kết quả Cho phép

Giá trị [không tích cực] Chọn Rt để ghi kết quả Không cho phép

Chọn input là số

Chọn input là thanh ghi

Cho phép ghi

Không cho phép ghi

Cho phép đọc

Không cho phép đọc

Chọn đường từ data memory đến thanh ghi [lệnh load] Khi điều kiện thỏa mãn, PC sẽ rẽ nhánh 1 đoạn đến nhãn Nhảy đến nhãn cần

Chọn đường từ kết quả của ALU đến thanh ghi Khi điều kiện không thỏa, PC thực thi lệnh tiếp theo PC chỉ đến lệnh tiếp theo

Chú ý: Không quan tâm đến RegDst, Memread, MemtoReg khi tín hiệu RegWrite = 0 2.2.2

Datapath

Bảng liệt kê các bước thực thi của các lệnh. Bảng. 4: Các bước của lệnh MIPS. ALU Load Store Branch Jump

2.3

Instruction Fetch Instruction Fetch Instruction Fetch Instruction Fetch Instruction Fetch

Decode

Execute

Decode

Execute

Decode

Execute

Decode

Execute

Write Back Memory Read Memory Write

Write Back

Decode

Bài tập

Dùng lại kiến trúc được miêu tả ở Hình 1 để trả lời các câu hỏi bên dưới: Cho bảng delay của các khối phần cứng như Bảng bên dưới: I-MEM ADDER MUX ALU REG D-MEM Control 200ps 10ps 30ps 180ps 150ps 200ps 10ps Bài 2.1. Xác định đường đi có độ trễ lâu nhất của lệnh AND, LOAD, và tính độ trễ đó? Bài 2.2. Xác định các tín hiệu của khối control khi thực thi lệnh BEQ $8, $9, LABEL. Với $8 = 0x00FF, $9 = 0x00FE Bài 2.3. Thành phần phần cứng nào không sử dụng khi ta thực thi lệnh SLTI, lệnh J. Bài 2.4. Bỏ qua delay của các khối adder, mux, control. Xác định data path và thời gian của các loại lệnh sau. • ALU • LOAD • STORE • BRANCH • JUMP Bài 2.5. Xác định thời gian của single cycle và multi-cycle Bài 2.6. Giả sử có 1 chương trình gồm 40% ALU, 20% Loads, 10% stores, 20% branches, và 10% jumps. Tính CPI trong trường hợp single cycle , multi cylce. Bài 2.7. Tính speed up của hệ thống Multi cycle đối với hệ thống single clock cycle.

2.4

Đáp án/Gợi ý

Bài 2.1. Critical path. • ADD: I-MEM[200] → REGs[150] → MUX[30] → ALU[180] → MUX[30] = 590 • LOAD: I-MEM [200] → REGs[150] → ALU[180] → D-MEM[200] → MUX[30] = 760 Bài 2.2. Xác định tín hiệu điều khiển. Xét lệnh beq $8, $9, lable. Với $8 = 0x00FF, $9 = 0x00FE. Lệnh này xét so sánh giá trị 2 thanh ghi: nếu thanh ghi $8 mà bằng thanh ghi $9 thì nó sẽ nhảy đến nhãn label. Nếu $8 khác $9 thì hệ thống sẽ thực hiện lệnh tiếp theo. Ta thấy nội dung thanh ghi $8 và $9 khác nhau nên lệnh BEQ không thực hiện nhảy đến nhãn label. Từ đó, ta đưa ra tín hiệu cho lệnh Bbeq $8, $9, lable như sau:

Tín hiệu RegDest RegWrite ALUSrc Memwrite MemRead MemtoReg Branch J ALUop

Giá trị x 0 0 0 x x 1 0 10

Giải thích don’t care Không ghi kết quả vào thanh ghi Chonj thanh ghi để so sánh với thanh ghi $8 Không truy xuất vào vùng data don’t care don’t care Lệnh rẽ nhánh Lệnh branch không phải lệnh jump Tham khảo Bảng 2

Bài 2.3. Hoạt động khối phần cứng. Lệnh slti dùng để set giá trị thanh ghi đích lên 1 nếu thanh ghi đem so sánh nhỏ hơn số cho trước, ngược lại nó sẽ reset giá trị thanh ghi đích xuống 0 nếu thanh ghi đem so sánh lớn hơn số cho trước. Ví dụ: slti $t1, $t2, 100 Khi thanh ghi $t2 < 100 thì $t1 = 1, ngược lại khi $t2 >= 100 thì $t1 = 0. Từ đó ta xét các khỗi‘ phần cứng mà lệnh slti đi qua như sau: Qua I-MEM [lệnh nào cũng qua I-MEM] → control unit, Reg files, MUX [2x], Sign extend, không đi qua bộ cộng PC → ALU → không qua D-MEM → MUX → Reg files. Bài 2.4. Data path, thời gian thực thi lệnh. Instruction Instruction Register class memory read ALU 200 150 Load 200 150 Store 200 150 Branch 200 150 Jump 200 150

ALU Operation 180 180 180 180

Data memory 200 200

Total 500 730 730 530 350

ps ps ps ps ps

Bài 2.5. Thời gian chu kỳ của hệ thống single cycle và hệ thống multi cycle • Tính thời gian của hệ thống single cycle = max[thời gian thực thi của tất cả các lệnh]. Lệnh LOAD là lệnh có thời gian thực thi lâu nhất 880 ps → thời gian của single cycle = 730 ps. • Tính thời gian của hệ thống multi cycle = max{của 5 bước} = max{IF [Instruction Memory], ID [Register Files], EXE [ALU], MEM [Data Memory], WB [Register Files]} = max{200, 150, 180, 200, 150} = 200 → thời gian của multi cycle = 200ps. Bài 2.6. CPI [Cycle per instruction: số chu kỳ trên lệnh]. • CPI của hệ thống single cycle = 1 [1 chu kỳ thực thi 1 lệnh]. • CPI của multi cycle = 0.4 × 4 + 0.2 × 5 + 0.1 × 4 + 0.2 × 3 + 0.1 × 2 = 3.8 [ALU 4 cycles; Load 5 cycles; Store 4 cycles; Branch 3 cycles; Jump 2 cycles] Bài 2.7. Thời gian thực thi. Thời gian chạy của 1 chương trình = IC × CP I× thời gian 1 chu kỳ = IC × CP I/f . • IC: số lệnh. • CPI: số chu kỳ trên một lệnh. • f: tần số. Thời gian chạy trên hệ thống single cycle: IC × 1 × 730. Thời gian chạy trên hệ thống multi cycle: IC × 3.8 × 200. Speedup = [1 × 730]/[3.8 × 200] = 730/760 = 0.96. Trong trường hợp này ta thấy hệ thống Multi clock cycle lại không hiệu quả bằng hệ thống Single clock cycle vì: • Các bước thực thi có thời gian không đều. • Những lệnh nhiều bước [load, store] chiếm phần lớn trong chương trình • Trong hệ thống single clock cycle quá trình write back được thực thi ở chu kỳ tiếp theo nên cycle time của hệ thống single clock cycle giảm. 7

Pipeline processor

3.1

Pipeline processor

3.1.1

Các bước trong pipeline

Pipeline chia lệnh thực thi ra thành 5 bước, mỗi bước thực thi trong trong một chu kỳ • IF: Lấy lệnh, 32bits lệnh chứa các thông tin của 1 lệnh được lấy ra từ instruction memory. • ID: Giải mã lệnh, xác định loại lệnh, toán tử, các tín hiệu điều khiển, nội dung các thanh ghi, giá trị immediate ... • EXE: Thực thi tác vụ lệnh. • MEM: Truy xuất vùng nhớ - chỉ dùng cho lệnh load/store. • WB: Ghi kết quả vào thanh ghi. 3.1.2

Hiệu suất.

Ta chia quá trình thực hiện lệnh ra thành k bước. • Thời gian thực thi N lệnh trên hệ thống single cycle = N × single cycle. • Thời gian thực thi N lệnh trên hệ thống pipeline = [k + N -1] × pipeline cycle. Lệnh đầu tiên: mất k chu kỳ, n -1 lệnh còn lại: còn lại mỗi lệnh 1 chu kỳ. Trường hợp lý tưởng: single cycle = k × pipeline cycle. Khi đó speedup =

k × n × pipelinecycle [k + n − 1] × pipelinecycle

Khi n → ∞ thì speedup → k [tức là pipeline nhanh tối đa gấp k lần single cycle] Chú ý: • Pipeline không rút ngắn thời gian thực thi của một lệnh, mà chỉ tăng hiệu suất lên bằng cách tăng thông năng [through-put] của máy. • Khi các bước của một lệnh có thời gian thực thi khác nhau thì sẽ làm giảm speed up. • Thời gian fill và drain cũng đồng thời làm giảm speed up. • Để hiện thực pipeline người ta dùng thanh ghi để lưu kết quả lại ở mỗi bước. – Tín hiệu từ khối control unit [main control] – Tất cả tín hiệu điều khiển được sinh ra ở bước ID – Mỗi bước dùng 1 số tín hiệu điều khiển – RegDst được dùng trong bước ID – ExtOp, ALUSrc, ALUCtrl, J, Beq, Bne, zero được dùng trong bước EXE – MemRead, MemWrite, MemtoReg dùng trong bước MEM – RegWrite dùng trong bước WB

3.2

Hazard

Khi hiện thực pipeline sẽ gây ra các loại hazard: structural hazard, data hazard, control hazard. 3.2.1

Structural hazard

Xảy ra khi có sự tranh chấp tài nguyên phần cứng, 2 lệnh cùng dùng chung phần cứng trong cùng chu kỳ. 3.2.2

Data hazards

Xảy ra khi có sự phụ thuộc dữ liệu kiểu Read After Write [RAW]. 8

Sự phụ thuộc dữ liệu • Read After Write – RAW Hazard 1 2

add $s1, $s2, $s3 J. sub $s4, $s1, $s3

thanh ghi $s1 duoc ghi

thanh ghi $s1 duoc doc

Pipeline c1 c2 c3 c4 c5 c6 IF ID EXE MEM WB IF ID EXE MEM WB Data hazard xuất hiện khi lệnh J đọc nội dung $s1 ở bước ID chu kỳ thứ 3 mà lệnh I lại đưa ra kết quả của $s1 ở bước WB chu kỳ thứ 5. • Write After Read: Name Dependence 1 2

I: sub $t4, $t1, $t3 # $t1 duoc doc truoc J: add $t1, $t2, $t3 # $t1 duoc ghi sau Không có sự phụ thuộc dữ liệu ở đây, chỉ có phụ thuộc tên biến $t1. Để loại bỏ sự phụ thuộc về tên biến, ta đổi tên thanh ghi.

1 2

I: sub $t4, $t1, $t3 J: add $t5, $t2, $t3

• Write After write: Name Dependence 1 2

I: sub $t1, $t4, $t3 # $t1 duoc ghi J: add $t1, $t2, $t3 # $t1 duoc ghi lan nua Không có sự phụ thuộc dữ liệu ở đây, chỉ có phụ thuộc tên biến. Kết quả chỉ phụ thuộc vào lệnh J sau. Để loại bỏ sự phụ thuộc về tên biến, ta đổi tên thanh ghi.

1 2

I: sub $t1, $t4, $t3 J: add $t5, $t2, $t3

• Read After Read: không gây ra sự phụ thuộc. 3.2.3

Phương pháp giải quyết data hazard.

Chèn stall Chèn stall để đảm bảo lệnh trước trả kết quả về mà lệnh sau có thể đọc được kết quả đó trong cùng chu kỳ. Phương pháp này không tốn tài nguyên phần cứng [giá thành], chỉ tạo ra delay cho chương trình [giảm hiệu suất]. Dùng kỹ thuật forwarding xúc tiến sớm. Phương pháp này cần thêm tài nguyên phần cứng [giá thành tăng] để hiện thực kết hợp với chèn stall khi cần thiết. Khi xảy ra hazard đối với lệnh load và lệnh nằm kề sau nó, cho dù ta có dùng kỹ thuật forward thì cũng phải tốn 1 stall để giải quyết chúng. Để hiện thực forward, người ta thêm bộ mux cho việc lựa chọn input cho ALU. Các lệnh [ngoại trừ lệnh load] thì kết quả được cho ra ở bước ALU [EXE] nên khi ta dùng kỹ thuật forward sẽ không còn stall nữa. Chú ý: • Các forwarding đều forward về vị trí EXE vì ALU là nơi bắt đầu tính toán → cần đưa input trước ALU. • Forward kết quả về chu kỳ n từ chu kỳ n-1 [là chu kỳ trước n]. Sắp xếp lại code Việc sắp xếp phải đảm bảo thứ tự trước sau khi có sự phụ thuộc và đảm bảo tính đúng đắn của chương trình.

3.3

Control hazard

Xét đoạn lệnh sau Dùng đoạn code sau để trả lời các câu hỏi bên dưới 1 2 3 4 5

label:

6 7

beq $t1, addi $t1, addi $t2, j exit addi $t1, addi $t2,

$t2, label $zero, 100 $zero, 100 $zero, 10 $zero, 10

exit: Sau khi IF [lấy lệnh] beq, ở chu kỳ tiếp theo ta giải mã beq và lấy lệnh tiếp theo. Lệnh tiếp theo sau lệnh branch là lệnh nào? • Khi $t1 = $t2, lúc đó điều kiện lệnh beq thỏa nên nó rẽ nhánh đến label thì lệnh tiếp theo là lệnh ở dòng thứ 5. • Khi $t1 != $t2, lúc đó điều kiện lệnh beq không thỏa nên nó thực hiện lệnh tiếp theo, khi đó lệnh tiếp theo là lệnh ở dòng thứ 2. Hiện tượng trên là control hazard. Để giải quyết control hazard ta có thể dùng phương pháp chèn stall hoặc tiên đoán kết hợp chèn stall. Ta biết bước EXE là bước hiện thực việc so sánh điều kiện, sau đó bước MEM sẽ cập nhập thanh ghi PC. Đó đó sau bước MEM ta mới biết chính xác là lệnh tiếp theo sau lệnh branch là lệnh nào. Nên ta cần phải chèn 3 stall [khi đó bước IF nằm sau bước MEM của lệnh branch] để loại bỏ control hazard. Ngoài ra ta có thể dùng tiên đoán để tăng hiệu suất của chương trình. Tiên đoán 1 bit và tiên đoán 2 bit

3.4

Bài tập

Thời gian delay của mỗi khối cho như bảng bên dưới. I-MEM ALU REG D-MEM 200ps 150ps 200ps 200ps Bài 3.1. Bỏ qua độ trễ của khối ADD, MUX, Control. Tính single cycle, pipeline clock? Bài 3.2. Tính thời gian thực thi của chương trình gồm 150 line code đối với single cycle và pipeline. Từ đó tính speed up để so sánh single cycle và pipeline [không có stall] Bài 3.3. Giả sử chương trình không có stall và thống kê được là có ALU 50%, Beq 25%, lw 15%, sw10%. Tính speed up giữa multi cycle và pipeline. Dùng đoạn code sau để trả lời các câu hỏi bên dưới 1 2 3 4 5 6 7

addi addi add lw lw and sw

$t1, $t2, $t3, $t4, $t5, $t6, $t6,

$zero, 100 $zero, 100 $t1, $t2 Label_4 Label_5 $t4, $t5 Label_KQ

Bài 3.4. Xác định sự phụ thuộc RAW [read after write] giữa các lệnh và thanh ghi nào gây ra sự phụ thuộc đó. Bài 3.5. Chèn stall để giải quyết hazard trên, cần bao nhiêu stall? Bài 3.6. Sắp xếp lại thứ tự các lệnh sao cho khi chạy đoạn code đó thì ít stall nhất mà chương trình vẫn giữ tính đúng đắn. Bài 3.7. Dùng kỹ thuật forward để giải quyết hazard khi đó còn bao nhiêu stall.

3.5

Đáp án/gợi ý

Bài 3.1. Thời gian chu kỳ single cycle, pipeline. Single cycle = thời gian thực thi lệnh dài nhất [lệnh load]. = I-Mem → Regs → ALU → D-Mem. = 200 + 200 + 150 + 200 = 750ps Pipeline clock = max [I-Mem, Regs, ALU, D-Mem, Regs] = 200ps Bài 3.2. Thời gian thực thi chương trình, speed up giữa single cycle và pipeline. CP Isingleclockcycle = 1. CP Ipipeline = 1. T imesinglecycle = 150 × 750 = 112500 ps T imeP ipeline = [5 + 150 - 1]×200 = 30800 ps 142500 = 3.65 Speed up = 30800 Bài 3.3. Thời gian thực thi chương trình, speed up giữa multi cycle và pipeline CP IM ultiCycle = 50%×4 + 25%×3 + 15%×5 + 10%×4= 3.9 CP IP ipeline = 1. Time = Số lệnh × CPI × thời gian 1 chu kỳ. T imeM ultiCycle = 150×3.9×200. T imeP ipeline = [5 + 150 - 1]×1×200. Speed up = 3.80. Bài 3.4. Phụ thuộc dữ liệu Read After Write 1 2 3 4 5 6 7

addi addi add lw lw and sw

$t1, $t2, $t3, $t4, $t5, $t6, $t6,

$zero, 100 $zero, 100 $t1, $t2 Lable_4 Lable_5 $t4, $t5 Lable_KQ

Lệnh [3] phụ thuộc lệnh [2] và [1]. Lệnh [6] phụ thuộc lệnh [5] và [4]. Lệnh [7] phụ thuộc lệnh [6]. Bài 3.5. Giải quyết data hazard bằng cách chèn stall 6 stall 2 stall giữa [2] và [3]. 2 stall giữa [5] và [6]. 2 stall giữa [6] và [7]. Lúc chèn stall vào đảm bảo là những chỗ cần giải mã giá trị thanh ghi [ID] phải cùng chu kỳ ghi kết quả [WB] Bài 3.6. Sắp xếp lại lệnh. Một trong những cách sắp xếp làm giảm stall [4] → [5] → [1] → [2] → [6] → [3] → [7] 1 2 3 4 5 6 7

lw lw addi addi add add sw

$t4, $t5, $t1, $t2, $t6, $t3, $t6,

Label_4 Label_5 $zero, 100 $zero, 100 $t4, $t5 $t1, $t2 Label_KQ

4

5

1

2

6

3

7

Còn lại 1 stall giữa 6 và 3 11

Bài 3.7. Giải quyết data hazard bằng forwarding. Còn 1 stall giữa lệnh [5] và [6].

Hình ảnh so sánh hệ thống single cycle, multi cycle và pipeline cycle Single clock cycle Load

Add

MEM WB

EXE

MEM WB

EXE ID IF

MEM EXE ID IF

EXE

Multi cycle Load IF

Jump ID

EXE

MEM WB

EXE

Add

Store EXE

Jump

Store

MEM WB

Branch EXE

MEM WB

EXE

Branch EXE

MEM IF

EXE

Pipeline IF

ID IF

WB MEM EXE ID IF

WB MEM WB EXE MEM WB ID EXE MEM WB

Các yếu tố ảnh hưởng đến hiệu suất của hệ thống: • Độ dài của chương trình [instruction count] • Số chu kỳ trên 1 lệnh [CPI] • Thời gian của 1 chu kỳ [clock cycle time].

4 4.1

Memory Memory

SRAM và DRAM [updated later]

4.2

Cache

Nguồn gốc Cache: do tốc độ phát triển của CPU quá nhanh so với Memory nên khi CPU truy xuất Memory sẽ tạo ra delay khá lớn, do đó cần có cache để làm bộ đệm giữa ALU và MEM. Cache thường được làm bằng SRAM. Mục đích làm giảm thời gian truy xuất memory từ CPU.

Bảng. 5: Tốc độ và thời gian truy xuất của các loại memory Type Size Access time Registers size < 1 KB < 0.5 ns Level 1 Cache size 8 – 64 KB 1 ns Level 2 Cache 512KB – 8MB 3 – 10 ns Main Memory 4 – 16 GB 50 – 100 ns Disk Storage > 200 GB 5 – 10 ms Temporal Locality [tính cục bộ về thời gian] một biến, thực thể được truy xuất thì có thể nó sẽ được truy xuất lần nữa. Thường xuất hiện trong những vòng lặp, hay gọi hàm/thủ tục nhiều lần. Đối với truy xuất theo thời gian thì xu hướng thường giữ block đó trong cache nhằm truy xuất lại lần sau. Spatial Locality [tính cục bộ về không gian] lệnh/data trong vùng nhớ khi được truy xuất có thể các lệnh/data gần nó sẽ được truy xuất. Thường xuất hiện trong khai báo mảng, thực thi tuần tự. . . Đối với truy xuất theo không gian thì xu hướng thường chuẩn bị trước block kế tiếp. 4.2.1

Block placement

Phương pháp đặt block vào cache. Direct mapped Mỗi block được xác định một vị trí đặt duy nhất. Cho N là số block trong cache. Block thứ M trong bộ nhớ [RAM] sẽ được đặt vào vị trí set M % N trong cache. Full associative Block được đặt vào bất kỳ vị trí nào còn trống trong cache. 12

MEM WB

K-way set associative Một set bao gồm K blocks [K có dạng 2x ]. Trong set đó có K sự lựa chọn. Cho N là số set trong cache, Block thứ M trong bộ nhớ [RAM] sẽ được đặt vào vị trí set M % N trong cache. Hình ảnh so sánh 3 cấu hình Direct map, k-way associative, full associative. Ở ví dụ trên k = 2.

Hình. 2: Directed map – 2-way set associative – Full set associative.

4.2.2

Block identification

Để xác định địa chỉ người ta chia địa chỉ ra làm 3 phần Tag, Index, block offset.

Tag

Index

Block Offset

Block offset Xác định thành phần trong block được truy xuất. Để xác định block offset có bao nhiêu bit, ta đi xác định trong block đó có bao nhiêu phần tử. Xác định số phần tử bằng cách lấy [size of block]/[size of đơn vị truy xuất]. Byte-offset Xác định byte trong block. Half-word-offset Xác định 2 bytes trong block. Word-offset Xác định word trong block. Index Dùng để xác định số set trong bộ nhớ đệm. • Direct mapped: 1 block là 1 set. • K-way Set Associative: k block tạo thành 1 set. • Full Associative: toàn bộ block thành 1 set. Index lúc này là 0 bit – không cần xác định set. Xác định số block bằng cách lấy [size of cache]/[size of block]. Tag Để xác định block nào đang nằm trong cache hoặc kết hợp với index để xác định block ID trong RAM. Tag bit = không gian địa chỉ – index – bytes offset. Trong trường hợp không đề cập đến không gian địa chỉ thì ta dùng không gian 32 bit.

4.2.3

Block replacement

Khi một block vào mà không còn chỗ trống để đặt vào thì cần phải thay block cũ bằng block mới. • Trong trường hợp direct mapped, vì mỗi set chỉ có 1 block nên khi nào có block mới vào thì block cũ bị thay thế do đó không có chính sách thay thế trong trường hợp này. • FIFO: cái nào được đặt vào trước thì sẽ được lấy ra trước. • Ramdom • LRU: cái nào ít dùng nhất thì được thay thế trước. • FILO: vào trước ra sau. 4.2.4

Write strategy

Chiến lược ghi ngược lại cache, memory Write Through Updata cả cache và memory, cần bit valid để xác định block đó có valid hay không. • Đơn giản, dễ hiện thực • Tốn lưu lượng băng thông của hệ thống vì phải update nhiều. Write Back Chỉ updata cache, khi có yêu cầu hay cần thay thế thì sẽ update giá trị sau cùng xuống memory. Cần bit valid để xác định block đó có valid hay không và bit modified để xác định block đó có update chưa. • Khó hiện thực • Ít tốn lưu lượng băng thông của hệ thống. 4.2.5

Miss/hit

• Miss: cần truy xuất mà tìm không thấy trong cache. Do đó phải đưa block chứa địa chỉ cần truy xuất vào cache, và sau đó truy xuất lại. • Hit: cần truy xuất và tìm thấy cái muốn truy xuất trong cache. • Ngoài dữ liệu, bộ nhớ đệm còn thêm các trường thông tin: – Valid: xác định có block tồn tại trong set hay không. – Tag: xác định block ID nào đang chứa trong block của Cache. • Miss Penalty: số chu kỳ để xử lý cache miss. • Hit rate =

hit . hit + miss

• Miss rate =

miss . hit + miss

• Miss rate + hit rate = 1. • I-Cache Miss Rate = Miss rate trong lúc truy xuất I-MEM. • D-Cache Miss Rate = Miss rate trong lúc truy xuất D-MEM Ví dụ 1: Chương trình có 1000 lệnh trong đó có 25% là load/store. Biết lúc đọc I-MEM bị miss 150, D-MEM bị miss 50. Tìm I-Cache Miss Rate, D-Cache Miss Rate. • I-Cache Miss Rate = số lần miss / số lần truy xuất I-MEM = 150/1000 = 15%. • D-Cache Miss Rate = số lần miss / số lần truy xuất D-MEM = 50/[1000×25%] =50/250 = 20%.

4.3

CPI

Khi cache miss thì sẽ gây ra stall. Để xác định bao nhiêu stall, ta đi tìm các thông số sau: • Memory stall cycles = Combined Misses × Miss Penalty. • Miss Penalty: số chu kỳ để giải quyết việc miss. • Combined Misses = I-Cache Misses + D-Cache Misses. • I-Cache Misses = I-Count × I-Cache Miss Rate. • D-Cache Misses = LS-Count × D-Cache Miss Rate. • LS-Count [Load & Store] = I-Count × LS Frequency. • Memory Stall Cycles Per Instruction = Combined Misses Per Instruction × Miss Penalty. • Combined Misses Per Instruction = I-Cache Miss Rate + LS Frequency × D-Cache Miss Rate • Memory Stall Cycles Per Instruction = I-Cache Miss Rate × Miss Penalty + LS Frequency × D-Cache Miss Rate × Miss Penalty. Trong đó: – I-count: tổng số lệnh. – LS-count: số lệnh Load/Store. – LS Frequency: tỉ lệ lệnh Load/Store trong chương trình. Ví dụ 2: Cho chương trình có 106 lệnh, trong đó 30% lệnh loads/stores. D-cache miss rate là 5% và I-cache miss rate là 1%. Miss penalty là 100 chu kỳ. Tính combined misses per instruction and memory stall cycles. • 1% + 30% * 5% = 0.025 combined misses. Mỗi lệnh tương đương 25 misses trên 1000 lệnh. • Memory stall cycles = 0.025 * 100 [miss penalty] = 2.5 stall cycles per instruction. • Total memory stall cycles = 106 * 2.5 = 2,500,000 • CPI Memory Stalls = CPI Perfect Cache + Mem Stalls per Instruction Ví dụ 3: Cho CPI = 1.5 khi không có stall, Cache miss rate là 2% đối với instruction và 5% đối với data. Lệnh loads và stores chiếm 20%. Miss penalty là 100 chu kỳ đối với I-cache và D-cache. Tính CPI của hệ thống? • Mem stalls cho mỗi lệnh = 0.02*100 + 20%*0.05*100 =3 • CPI Memory Stalls = 1.5 + 3 = 4.5 cycles

4.4

Thời gian truy xuất bộ nhớ trung bình

Average Memory Access Time [AMAT]. AMAT = Hit time + Miss rate × Miss Penalty Do đó để giảm thời gian truy xuất: • Ta giảm Hit time: bằng cách dùng bộ nhớ cache nhỏ [tăng miss rate :D], đơn giản. • Giảm Miss Rate: bằng cách dùng bộ nhớ cache lớn , block size lớn [tăng Hit time] và k-way set associativity với k lớn. • Giảm Miss Penalty bằng cách dùng cache nhiều mức. Ví dụ 4: Tìm thời gian truy xuất trung bình khi biết hit time 1 chu kỳ, miss penalty 20 chu kỳ, miss rate 0.05 %. Biết máy tính chạy với tần số 0.5Ghz • AMAT [cycles] = 1 + 0.05 × 20 = 2 cycles • 0.5 Ghz → 1 chu kỳ 2ns • AMAT [time] = 2×2 = 4ns Ví dụ 5: Tìm thời gian truy xuất trung bình khi biết thời gian truy xuất cache L1 là 1 chu kỳ, thời gian truy xuấtcache L2 là 10 chu kỳ, thời gian truy xuất bộ nhớ chính là 100 chu kỳ, miss rate L1 5%, miss rate L2 10%. Biết máy tính chạy với tần số 1Ghz. • AMAT [cycles] = 1 + 5% x 20 + 10%×100 = 20 cycles • 1Ghz → 1 chu kỳ 1ns • AMAT [time] = 20×1= 20 ns 15

4.5

Bài tập

Bài 4.1. Cho bộ nhớ cache có dung lượng 256KB, block size là 4 word, mỗi lần truy xuất 1 byte. Xác định số bit của các trường tag, index, block offset trong các trường hợp. • Direct mapped • Full associcative • 2-Way set associcative Bài 4.2. Cho bộ nhớ chính có dung lượng 1G, bộ nhớ cache có dung lượng 1MB, block size là 256B, mỗi lần truy xuất 1 word. Xác định số bit của các trường tag, index, block offset trong các trường hợp. • Direct mapped • Full associcative • 4-Way set associcative Bài 4.3. Trong cache có 8 blocks, mỗi block là 4 words. Xác định số lần miss/hit khi hệ thống truy xuất vào các địa chỉ [dạng byte] theo thứ tự sau: 0x0001002A 0x00010020 0x0002006A 0x00020066 0x00020022 0x0001002B Trong các trường hợp: • Direct mapped • Full associcative • 2-Way set associcative

4.6

Đáp án/Gợi ý

Byte-offset: xác định byte trong block. Word-offset: xác định word trong block. index: xác định set trong block. Tag: xác định block trong cache. Tag + index: xác định block trong bộ nhớ chính. Direct mapped: một block 1 set. k-Way Set Associative: k block [k = 2x ] một set. Full: Tấc cả block 1 set. Bài 4.1. Xác định tag, index, byte-offset. Số phần tử trong 1 block = [size of block]/[size of phần tử truy xuất] = 4 word /1 byte = 4x4 bytes/ 1 byte = 16 = 24 . Số block trong cache = [size of cache] / [size of block] = 256 KB / 4 words = 28 ∗ 210 /4 ∗ 4 = 214 blocks. Không gian địa chỉ là 32 bit. • Direct mapped: byte-offset 4 bits, index = 14 bits, tag = 32 – 4 - 14 = 14 bits • Full associcative: byte-offset 4 bits, index = 0 bits, tag = 32 – 4 = 28 bits. • 2-Ways set associative: 2 block tạo thành 1 set mà có 214 blocks nên có 213 sets, byte-offset 4 bits, index = 13 bits, tag = 32 -4 - 13 = 15 bits Bài 4.2. Xác định tag, index, word-offset. Số phần tử trong 1 block = [size of block]/[size of phần tử truy xuất] = 256B / 4 bytes = 26 . Số block trong cache = size of cache / size of block = 1MB / 256B = 210 x210 /28 = 212 blocks. Không gian địa chỉ là 1G, do đó ta dùng thanh ghi 30 bit tính theo byte-offset. • Direct mapped: word-offset 6 bits, index = 12 bits, tag = 30 – 6 – 12 – 2 = 10 bits. • Full associcative: word-offset 6 bits, index = 0 bits, tag = 30 – 6 – 2 = 22 bits. • 4 ways set associative: 4 block tạo thành 1 set mà có 212 blocks nên có 210 sets, word-offset 6 bits, index = 10 bits, tag = 30 – 6 - 10 - 2 = 12 bits. 16

Chú ý: không gian tính theo byte thì phải chuyển về byte-offset để tính: số bit của địa chỉ = số bit của tag, index, và byte-offset. Bài 4.3. HIT/MISS Ta tính được có 4 bits byte-offset, 3 bits index. Do đó ta phân tích địa chỉ như bên dưới: Cách 1: • Direct map Address 0x0001002A 0x00010020 0x0002006A 0x00020066 0x00020022 0x0001002B

0000 0000 0000 0000 0000 0000

0001 0001 0010 0010 0010 0001

0000 0000 0000 0000 0000 0000

Tag 0000 0 0000 0 0000 0 0000 0 0000 0 0000 0

Index 010 010 110 110 010 010

Offset 1010 0000 1010 0110 0010 1011

Miss/Hit M H M H M M

Giải thích First access First access Khác tag Khác tag

• Full associative Address 0x0001002A 0x00010020 0x0002006A 0x00020066 0x00020022 0x0001002B

0000 0000 0000 0000 0000 0000

0001 0001 0010 0010 0010 0001

0000 0000 0000 0000 0000 0000

Tag 0010 0010 0110 0110 0010 0010

Offset 1010 0000 1010 0110 0010 1011

Miss/hit M H M H M H

Giải thích First access First access First access

• 2 ways set associative, cần 2 bit index Address 0x0001002A 0x00010020 0x0002006A 0x00020066 0x00020022 0x0001002B

thanh ghi $s1 duoc ghi

thanh ghi $s1 duoc doc

4

5

1

2

6

3

7

Bài Viết Liên Quan

Toplist mới

Bài mới nhất

Chủ Đề