xung đột? pipelined và kỹ thuật forwarding, non-forwarding

 Pipeline là một kỹ thuật mà trong đó các lệnh được thực thi theo kiểu chồng lắp lên nhau.

- Cách tiếp cận dùng kỹ thuật pipeline tiêu tốn ít thời gian hơn cho tất cả các công việc hoàn tất bởi vì các công việc được thực hiện song song, vì vậy số công việc hoàn thành trong một giờ sẽ nhiều hơn so với không pipeline.

- Chú ý, pipeline không làm giảm thời gian hoàn thành một công việc mà làm giảm thời gian hoàn thành tổng số công việc (như trong ví dụ trên, thời gian cho người A hoàn thành việc giặt khi áp dụng pipeline hay không pipeline đều là 2 giờ, nhưng tổng số giờ cho 4 người A, B, C và D hoàn thành dùng pipeline giảm rất nhiều so với không pipeline)

Khi thực thi, các lệnh MIPS được chia làm 5 công đoạn:
1. Nạp lệnh từ bộ nhớ (IF – instruction fetch)
2. Giải mã lệnh và đọc các thanh ghi cần thiết (MIPS cho phép đọc và giải mã đồng thời) (ID – instruction decode)
3. Thực thi các phép tính hoặc tính toán địa chỉ (EX – execute)
4. Truy xuất các toán hạng trong bộ nhớ (MEM – memory access)
5. Ghi kết quả cuối vào thanh ghi (WB – write back)
Vì vậy, MIPS pipeline trong chương này xem như có 5 công đoạn (còn gọi là pipeline 5 tầng)

Sự tăng tốc của pipeline

v Trong trường hợp lý tưởng: khi mà các công đoạn pipeline hoàn toàn bằng nhau thì
thời gian giữa hai lệnh liên tiếp được thực thi trong pipeline bằng: thời gian giữa hai lệnh liên tiếp được thực thi trong pipeline bằng:
à Trong trường hợp lý tưởng, pipeline sẽ tăng tốc so với không pipeline với số lần đúng
bằng số tầng của pipeline.
bằng số tầng của pipeline.
v Trong thực tế: Các công đoạn thực tế không bằng nhau, việc áp dụng pipeline phải chọn
công đoạn dài nhất để làm một chu kỳ pipeline.
Speed-up ≈ Thời gian giữa hai lệnh liên tiếp không pipeline / Thời gian giữa hai lệnh liên tiếp pipeline
công đoạn dài nhất để làm một chu kỳ pipeline.
Speed-up ≈ Thời gian giữa hai lệnh liên tiếp không pipeline / Thời gian giữa hai lệnh liên tiếp pipeline
à Trong thực tế, pipeline sẽ tăng tốc so với không pipeline với số lần nhỏ hơn số tầng
của pipeline.
của pipeline.


Thời gian giữa hai lệnh liên tiếp không pipeline / Thời gian giữa hai lệnh liên tiếp pipeline

Lưu ý, pipeline tăng tốc so với không pipeline:

•  Kỹ thuật pipeline không giúp giảm thời gian thực thi của từng lệnhriêng lẽ mà giúp giảm tổng thời gian thực thi của đoạn lệnh/chươngtrình chứa nhiều lệnh (từ đó giúp thời gian trung bình của mỗi lệnhgiảm)riêng lẽ mà giúp giảm tổng thời gian thực thi của đoạn lệnh/chươngtrình chứa nhiều lệnh (từ đó giúp thời gian trung bình của mỗi lệnhgiảm)
• Việc giúp giảm thời gian thực thi cho nhiều lệnh vô cùng quantrọng, vì các chương trình chạy trong thực tế thông thường lên đếnhàng tỉ lệnh.trọng, vì các chương trình chạy trong thực tế thông thường lên đếnhàng tỉ lệnh.

Các xung đột có thể xảy ra khi áp dụng kỹ thuật pipeline (Pipeline Hazards):

 Xung đột là trạng thái mà lệnh tiếp theo không thể thực thi trong chu kỳ pipeline ngay sau đó (hoặc thực thi nhưng sẽ cho ra kết quả sai), thường do một trong ba nguyên nhân sau:

Xung đột cấu trúc (Structural hazard): là khi một lệnh dự kiến không thể thực thi trong đúng chu kỳ pipeline của nó do phần cứng cần không thể hỗ trợ.

Nói cách khác, xung đột cấu trúc xảy ra khi có hai lệnh cùng truy xuất vào một tài nguyên phần cứng nào đó cùng một lúc.Xung đột dữ liệu (Data hazard): là khi một lệnh dự kiến không thể thực thi trong đúng chu kỳ pipeline của nó do dữ liệu mà lệnh này cần vẫn chưa sẵn sàng.
Xung đột điều khiển (Control/Branch hazard): là khi một lệnh dự kiến không thể thực thi trong đúng chu kỳ pipeline của nó do lệnh nạp vào không phải là lệnh được cần. Xung đột này xảy ra trong trường hợp luồng thực thi chứa các lệnh nhảy

Cách giải quyết xung đột dữ liệu:

-         Cách 1: Chờ chu kỳ xung clock.

-         Cách 2: Kỹ thuật nhìn trước (forwarding hay bypassing)

+ Kỹ thuật nhìn trước: một phương pháp giải quyết xung đột dữ liệu bằng đưa thêm vào các bộ đệm phụ bên trong, các dữ liệu cần có thể được truy xuất từ bộ đệm này hơn là chờ đợi đến khi nó sẵn sàng trong bộ nhớ hay trong thanh ghi.

+ Lưu ý, với lệnh lw và các lệnh có chức năng tương tự, thông thường kết quả cuối của nó không phải khi hoàn tất công đoạn EX mà là khi hoàn tất công đoạn MEM. (chờ 4 chu kỳ)

Kỹ thuật forwarding có thể hỗ trợ giải quyết xung đột dữ liệu hiệu quả, tuy nhiên nó không thể ngăn chặn tất cả các trường hợp chu kỳ rỗi.

+ Tóm lại, với kỹ thuật forwarding có:

ALU-ALU forwarding hay EX-EX forwarding (hình 1)MEM-ALU forwarding hay MEM-EX forwarding (hình 2)

hình 1

hình 2

Đối với phần Pipelined trong KTMT, việc xảy ra xung dột là điều hoàn toàn có thể, nhưng cũng có giải quyết, có 2 chú ý với kỹ thuật cho phép gửi vượt trước : Forwarding và ko cho gửi Non - forwarding như sau
- Non - forwarding: khi có 2 lệnh ở các chu kỳ kế tiếp nhau sử dụng chung thanh ghi (1 lệnh đọc và 1 lệnh ghi) thì: Chỉ khi lệnh trước nó tới công đoạn WB (nửa đầu WB đã dc ghi) thì lệnh tiếp theo dc phép thực thi ở công đoạn ID (giải mã lệnh ở nửa sau ID)
=> Kết luận: chỉ cần chú ý đặt NOP sao cho WB của lệnh trước thẳng hàng với ID của lệnh kế tiếp (tham khảo thêm hình)
- Forwarding: với các lệnh thuộc kiểu R-Format (add, sub...) thì EX của lệnh trước cần thẳng hàng với ID của lệnh sau (đảm bảo EX sau khi cho KQ được truyền thẳng tới ALU lệnh sau nó),
lệnh LW thì MEM của lệnh trước thẳng hàng với ID của lệnh sau (đảm bảo sau khi đọc/ ghi DL ở công đoạn MEM xong mới dc truyền xuống ALU của lệnh kế tiếp)
Chia sẻ trên bỏ qua các lệnh ss nhảy như beq (vì vướng điều kiện tiên đoán) ^^
Bạn nào có kinh nghiệm làm bài ở dạng này có thể cmt chia sẻ với mọi người nhé ^^
p/s: lệnh SW ít xảy ra do theo trình tự code: lw để load DL từ ô nhớ ra thanh ghi, thực thi bằng lệnh add, sub... và cuối cùng lưu lại giá trị của thanh ghi này xuống bộ nhớ => sw đã là lệnh cuối và ko lệnh nào thực thi sau nó nữa ^^ (Đặng Thị Kim Luyến)

Read More

cách XĐ tín hiệu điều khiển từ khối "Control" - Datapath (KTMT)

** Tổng quan các lệnh cần xem xét:

(8 lệnh trong 3 nhóm chính của tập lệnh MIPS)

 § Nhóm lệnh tham khảo bộ nhớ (lw và sw):

Nạp lệnh > Đọc một/hai thanh ghi > Sử dụng ALU > Truy xuất bộ nhớ để đọc/ghi dữ liệu

 § Nhóm lệnh liên quan đến logic và số học (add, sub, AND, OR, và slt):

Nạp lệnh > Đọc một/hai thanh ghi > Sử dụng ALU > Ghi dữ liệu vào thanh ghi

 § Nhóm lệnh nhảy (Lệnh nhảy với điều kiện bằng beq):

Nạp lệnh > Đọc một/hai thanh ghi > Sử dụng ALU > Chuyển đến địa chỉ lệnh tiếp theo dựa trên kết quả so sánh

Giá trị các tính hiệu điều khiển từ khối “Control” sẽ như thế nào?

Khối control có các đường tín hiệu điều khiển: regdst,branch, memread, memwrite,memtoreg,ALUop, ALU src, regwrite

xét lệnh lw rt=rs+sign extend

+vì không có rd nên regdst =0

+lw sẽ load dữ liệu từ bộ nhớ và ghi dữ liệu đó và thanh ghi nên memread=1 và memwrite =1.

+ dữ liệu phải được ghi lại vào thanh ghi nên regwrite =1 và dữ liệu lấy từ D-mem nên memtoreg=1.

+ lw không phải là lệnh rẽ nhánh hay lệnh nhảy gì hết nên branch đương nhiên là =0

+ ALUsrc =1 vì dữ liệu thứ 2 được đưa vào ALU là sign-extend, dễ thấy, đường dữ liệu thứ nhất đưa vào ALU là thanh ghi đó, read data 1 đó

+ ALUop = add

nhìn hình minh họa cho đường dữ liệu ta cũng dễ thấy giá trị của các khối control đi ra, các giá trị điệu khiển hầu hết được đưa đến bộ MUX để cho phép đường này đi qua hay đường kia đi qua, tại hình ảnh có ghi rõ giá trị đầu nào của mux là 1, đầu nào là 0 nên cũng dễ dàng xá định được giá trị của control khi ta biết được đường đi datapath của lệnh. 

sau đây là hình ảnh của lệnh add rd=rs+rt

lệnh add sử dụng để rs,,rt,rd và không có signextend, nó chỉ cộng và ghi lên thanh ghi, không ddoogj chạm gì đến D-mem( truy xuất bộ nhớ) như lệnh lw cả và cũng không rẽ nhánh luôn, nên giá trị điều khiển của memread, memwrite, branch, ALUsrc đều =0

Tương tự đối lênh sw, sw không ghi lên thanh ghi mà nó chỉ lưu vào bộ nhớ thôi nhé, nên regwrite=0, còn lại tương tự như lw, quan sát hình mô tả đường đi datapath và so sánh với lệnh lw nhé.

và loại lệnh cần nhắc đến là lệnh bed rs,rt,branch address (rẻ nhánh có đk)

*chi tiết các loại lệnh, sử dụng rs,rt,rd hay signextend gì đó thì trong bảng MIPS có nêu rõ, nên khong cần bận tâm chổ này.

ở laoji lệnh này, ALU sẽ nạp dữ liệu từ 2 thanh ghi chứ không lấy từ sign extend, vì signextend lúc này là địa chỉ cần nhảy đến nếu điều đúng, ALU sẽ so sánh và đưa kết quả lên cổng AND với giá trị điều khiển 1 của control - branch, chỉ khi ALU trả về giá trị 1 thì mới đưa tín hiệu điều khiển =1 đến cho bộ mux của bộ Cộng lệnh nhảy và nhảy đến địa chỉ được nạp vào từ signextend. từ đó, khối D-mem tất nhiên không làm gì thì memread hay memwrite hay memtoreg, regwrite cũng vậy không liên liên quan đến lệnh này, do đó =0 tất., các giá trị còn lại, xác định qua hình rất dễ dàng

Read More

hiệu suất máy tính và cách tính hiệu suất, các thông số liên quan

execution time: thời gian thực thi (s)
performance:hiệu suất
clock cycle: chu kỳ xung đồng hồ
clock rate: số clock cycle thực hiện trong 1 giây (Hz)
clock cycle time: thời gian thực hiện 1 clock cycle (s)
instruction: số lệnh của 1 chương trình cần thực hiện
CPI ( clock cycle per instruction): số clock cycle cần thực hiện trên 1 lệnh
MIPS( million instruction per second): số triệu lệnh thực hiện được trên 1 giây
IPS( instruction per second): số triệu lệnh thực hiện được trên 1 giây

Read More

bên trong phần cứng máy tính

phần cứng của 1 máy tính bất kỳ thực hien các chức năng cơ bản sau: nhập, xuất , xử lý và lưu trữ dự liệu

nhập

bàn phím, chuột

xuất

màn hình là bộ phận xuất chuẩn

xử lý

thùng chứa bộ xử lý và các thiết bị I/O khác

ảnh màu:

- mỗi bức ảnh là 1 ma trận các phần tử ảnh, hay pixel được biểu diễn thnahf 1 ma trân bit được gọi là bit map

- đối với ảnh màu: dùng 8 bit cho mỗi màu sắc (red, blue, green) tương đương 24 bit cho 1 pixel , cho phép hàng triệu màu khác nhau được hiển thị

- phần cứng máy tính hổ trợ đồ họa có thành phần chủ yếu là frame buffer để lưu nội dung bit map, chúng xác định nội dung cần hiển thị và ghi chúng lên buffer, sau đó in nôi dung buffer lên màn hình tương ứng

Read More

bên dưới một chương trình ứng dụng trong máy tính

 

hệ điều hành:

đóng vai trò giao tiếp giữa chương trình của nguwoif dùng với phần cứng đồng thời cung cấp nhiều dịch vụ khác nhau và các chức năng quản lý, một số chức năng quan trong như:

- điều khiển các hoạt động nhập xuất cơ bản

- cấp phất bộ nhớ và vùng lưu trữ

- quản lý, chia sẽ tài nguyên máy tính khi có nhiều ứng dụng chạy đồng thời

trình biên dịch:

dịch chương trình của các ngon ngữ cấp cao thành các lệnh mà phần cứng máy tính có thể thực thi

 Bảng chữ cái cho máy tính: 0 và 1  Để giao tiếp với một máy điện tử, ta cần gởi đi các tín hiệu điện. Các tín hiệu dễ dàng nhất cho máy hiểu là tín hiệu on (0) và off (1) (mở và tắt). 

• Bảng chữ cái tiếng Anh có 26 kí tự 

• Bảng chữ cái cho máy tính có 2 kí tự 

 số nhị phân (binary number); mỗi kí tự là một kí số nhị phân (binary digit) hay còn gọi là bit

Ngôn ngữ Assembly (Hợp ngữ): ngôn ngữ mô tả lệnh của máy tính thông qua kí hiệu biểu diễn (symbol) 

Assembler: chương trình dịch lệnh hợp ngữ sang lệnh nhị phân. 

Ngôn ngữ lập trình cấp cao: Các ngôn ngữ có tính linh động (portable) như C, Fortran, Java; bao gồm các từ và kí hiệu số học, có thể được dịch sang ngôn ngữ Assembly bởi một trình biên dịch 

Read More

máy tính - giới thiệu các khái niệm và công nghệ

 Máy tính – cuộc cách mạng thứ ba của nền văn minh  (cùng với cuộc cách mạng về nông nghiệp và công nghiệp) 
 Xu hướng nghiên cứu khoa học mới:
 • Các nhà khoa học tính toán, lý thuyết và thực nghiệm cùng hợp tác nhau trong việc khám phá ra những thành tựu mới trong thiên văn học, sinh học, hóa học, vật lý, v.v…
 Những ứng dụng được xem là “khoa học viễn tưởng” trước đây:
 Máy tính trong ô tô
 Điện thoại
 Dự án di truyền học người
 World Wide Web
 Công cụ tìm kiếm

Read More

các cổng logic cơ bản OR, AND, NOT

cổng logic OR

ký hiệu cho cổng logic OR là dâu +, ví dụ C = A or B ký hiệu là C=A+B

cổng logic AND

thực hiện tương tự như phép nhân, ký hiệu A AND B là A.B

cổng logic NOT

là cổng mà nó sẽ đảo ngược giá trị của cổng hiện thời, 1 -> 0, 0->1, cổng luôn có 1 input và 1 out put với giá trị out put là đảo ngược của giá trị in put

mô tả mạch logic đại số

- nếu 1 mạch logic có cả 2 cổng AND và OR thì nó sẽ thực hiện AND trước, OR sau trừ khi có dấu ngoặc ngăn cách để chỉ cái nào thực hiện trước, cái nào thực hiện sau

- có bất kỳ 1 cổng NOT nào trong mạch thì giá trị out put tương đương với in put và có kèm thanh ngang trên đầu

quy tắc đánh giá 1 biểu thức boolean

- thực hiện NOT đối với in put đơn trước

- thực hiện các phép tính trong ngoặc

- thực hiện cổng AND trước rồi mới đến cổng OR

- nếu cả biểu thức có dấu thanh ngang trên đàu thì thực hiện bên trong trước rồi đổi dấu kết quả tìm được là xong

- caacsh tốt nhất để đánh giá là sử dụng bảng sự thật

+cho phép chúng ta đánh giá 1 cỏng và nhiều cổng có trong machj cùng 1 lúc

+dễ kiểm tra hoạt động cả mạch 1 cách chính xác

+ phát hiện và sử lý lỗi có trong mạch 1 cách dễ dàng

Read More

các hệ thống số cơ bản, nhị phân, bát phân, thập lục phân, thập phân

các hệ thống số cơ bản

thập phân:

gồm các chữ số 0,1,2,3,4,5,6,7,8,9

ví dụ: 576.348 = 5*10^2 + 7*10^1 + 6*10^0 + 3*10^-1 + 4*10^-2 + 8*10^-3

Read More