Tiếp theo chuỗi bài viết về các giải thuật phân xử, bài 1 và bài 2 trình bày về việc phân xử dựa trên mức ưu tiên của các nguồn request. Bài viết này trình bày về giải thuật phân xử Round Robin (RR) giúp cân bằng quyền truy cập giữa các nguồn request.
*Lưu ý, một số thuật ngữ dùng trong bài viết đã trình bày trong các bài trước sẽ không được giải thích lại.
1) Tổng quan
Với việc phân xử theo mức tiên, nguồn request có mức ưu tiên cao luôn chiếm ưu thế và dễ dàng được grant hơn các nguồn request có mức ưu tiên thấp. Nguồn request có mức ưu tiên thấp nhất có thể bị "treo" (không được grant) nếu các nguồn request ưu tiên cao hơn tích cực liên tục. Đối với các hệ thống cần sự cân bằng quyền truy cập giữa các nguồn request thì cơ chế Round Robin là một lựa chọn hiệu quả.
Trước khi đến với cách thiết kế bộ phân xử RR dưới góc nhìn của người thiết kế phần cứng. Chúng ta cùng xem xét sơ qua về RR dưới góc độ của người lập trình phần mềm.
Nguyên tắc cơ bản của RR là không độc quyền (preemtive). Trên phương diện phần mềm (software), RR là thuật toán dùng cho hệ thống chia sẻ thời gian để thực thi các tiến trình (process). RR định nghĩa một khoảng thời gian cố định, gọi là time quantum hay time slice, dành cho việc thực thi một tiến trình. Một tiến trình xử lý vượt quá thời gian này sẽ bị ngắt để nhường quyền thực thi cho các tiến trình khác đang đợi. Sau khi tất cả các tiến trình đang đợi đã thực thi xong một lượt trong khoảng thời gian quy định, thì quyền thực thi tiếp tục được cấp phát lại cho các tiến trình chưa hoàn tất.
Ví dụ, giả sử có 3 tiến trình với khoảng thời gian cần thiết để xử lý mỗi tiến trình như sau:
- P1 - 12 giây
- P2 - 3 giây
- P3 - 7 giây
Khoảng thời gian time quantum được quy định là 4 giây. Việc cấp phát quyền xử lý cho các tiến trình sẽ thực hiện theo thứ tự như sau:
- P1 - 4 giây
- P2 - 3 giây -> hoàn tất và không cần cấp phát thêm
- P3 - 4 giây
- P1 - 4 giây
- P3 - 3 giây -> hoàn tất và không cần cấp phát thêm
- P1 - 4 giây -> hoàn tất và không cần cấp phát thêm
Qua ví dụ trên, chúng ta có thể thấy RR đảm bảo không có tiến trình nào độc quyền. Các tiến trình được phục vụ đều đặn mà không phụ thuộc vào thời gian xử lý của tiến trình trước.
Quay lại với thiết kế phần cứng, RR trên phần cứng có đôi chút khác biệt, việc quy định một khoảng thời gian truy cập và ngắt giữa chừng làm thiết kế phần cứng phức tạp và tốn nhiều tài nguyên trong khi mức độ cần thiết thường không lớn. Bên cạnh đó, một vài giao thức (protocol) không cho phép ngắt giữa chừng khi đã được grant mà phải chờ đến khi request hiện tại hoàn thành xử lý của nó.
Vì vậy, trong thiết kế phần cứng, RR thường (không phải tất cả) tập trung chính vào việc phân phối quyền truy cập cho mỗi nguồn request để đảm bảo mỗi nguồn request đều có khả năng truy cập ngang nhau, chứ không tập trung vào việc giám sát và ngắt một request đang được grant. Nghĩa là một request đã được grant thì có quyền hoàn thành truy cập của nó trước khi chuyển quyền truy cập cho request khác.
Bên cạnh đó, RR có nhiều cách thực hiện khác nhau với mức độ "cân bằng quyền truy cập" khác nhau.
2) Bộ phân xử Round Robin đơn giản
Một cách đơn giản nhất để thực hiện RR là dùng một bộ đếm tăng đều hoặc giảm đều một đơn vị để quét qua từng nguồn request. Mỗi nguồn request ứng với một giá trị cố định của bộ đếm, khi bộ đếm chứa giá trị trùng với một nguồn request đang tích cực, nguồn request này sẽ được grant và bộ đếm tăng/giảm để chọn nguồn request tiếp theo. Lúc này, nguồn request đang được grant sẽ có mức ưu tiên thấp nhất trong lần phân xử tiếp theo.
 |
| Hình 1: Sơ đồ nguyên lý của bộ phân xử Round Robin đơn giản |
- RR counter: Bộ đếm dùng để quét các nguồn request tuần tự. Trong thiết kế minh họa, tác giả dùng bộ đếm lên quét từ req[0] đến req[REQ_NUM-1] và lặp lại.
- Select the request source: là mạch logic xác định nguồn request nào sẽ được grant.
 |
| Hình 2: Mạch nguyên lý bộ đếm lên |
 |
| Hình 3: Mạch nguyên lý tạo tín hiệu grant cho các nguồn request và logic của tín hiệu noGrant |
Chú ý, mạch nguyên lý được vẽ trên đây hướng tới mục tiêu khái quát hóa mạch logic để giúp viết RTL code khả tổng hợp dễ dàng. Ví dụ như hình 3, khi bỏ cổng NOR tạo noGrant thì các mạch logic có cấu trúc giống nhau, chỉ khác các tín hiệu input/output của mạch.
3) RTL code và kết quả minh họa
Các mạch nguyên lý trình bày trên đây trùng với RTL code thực tế nên các bạn có thể tự so sánh và phân tích.
assign noGrant = ~|grant[REQ_NUM-1:0];
//
always @ (posedge clk, negedge rst_n) begin
if (~rst_n)
rrCounter[COUNTER_W-1:0] <= {COUNTER_W{1'b0}};
else if (noGrant) begin
if (rrCounter[COUNTER_W-1:0] == REQ_NUM-1)
rrCounter[COUNTER_W-1:0] <= {COUNTER_W{1'b0}};
else
rrCounter[COUNTER_W-1:0] <=
rrCounter[COUNTER_W-1:0] + 1'b1;
end
end
//
//Create grant
generate
genvar i;
//
for (i = 0; i < REQ_NUM; i=i+1) begin: uGrant
always @ (posedge clk, negedge rst_n) begin
if (~rst_n)
grant[i] <= 1'b0;
else if (noGrant)
grant[i] <= req[i] &
(rrCounter[COUNTER_W-1:0] == i);
else
grant[i] <= req[i] & grant[i];
end
end //for loop
endgenerate
 |
| Hình 4: Một waveform minh họa hoạt động của bộ phân xử Round Robin đơn giản |
- Bộ phân xử theo cách thiết kế này tốn ít tài nguyên, đơn giản và dễ thực hiện
- Cách phân xử chưa thực sự "cân bằng" vì một nguồn request có khả năng tích cực 2 lần liên tiếp cho dù trong lúc đó, một nguồn request khác chưa được grant đang tích cực. Điều này xảy ra là bởi vì trong quá trình không có nguồn request nào tích cực, bộ đếm rrCounter sẽ đếm lên liên tục làm cho một nguồn request không thể được grant ngay nếu giá trị bộ đếm đã qua lượt của nó. Giả sử req[2] tích cực trong khi rrCounter=3, lúc này lượt của req[2] đã qua, thì req[2] phải chờ rrCounter đếm qua giá trị 0 và 1 rồi mới đến 2. Lúc này, req[0] hoặc req[1] sẽ được grant trước nếu hai tín hiệu này tích cực dù trong lần gần nhất một trong 2 nguồn này đã được grant.
- Có thể xuất hiện nhiều chu kỳ rảnh (không làm gì) giữa hai lần grant, nhất là khi số lượng nguồn request tăng cao. Xem lại waveform của grant[0], các bạn sẽ thấy rằng lầm grant sau cách nhiều chu kỳ so với lần grant trước cho dù chỉ có một mình req[0] tích cực vì req[0] phải chờ đến lượt của nó.
Vậy cách nào tốt hơn không? một vài cách thiết kế Round Robin khác sẽ được trình bày trong các bài tiếp theo.
Dữ liệu có thể tải:
Lịch sử cập nhật:
1) 2019.Aug.22 - Tạo lần đầu
0 bình luận:
Đăng nhận xét