[Arbiter] Bài 4 - Bộ phân xử Round Robin kết hợp mức ưu tiên

Bài viết này trình bày một cách thiết kế bộ phân xử Round Robin (RR) kết hợp với mạch logic ưu tiên giúp giảm số chu kỳ delay giữa các lần phân xử so với bộ phân xử chỉ dùng một bộ đếm.

Trước khi đọc bài này, các bạn hãy tham khảo các bài viết trước về bộ phân xử ưu tiên, bài 1 và bài 2, và Round Robin đơn giản, bài 3.

1) Mô tả tổng quan thiết kế

Như đã trình bày trong bài 3, bộ phân xử RR đơn giản chỉ dùng một bộ đếm để kiểm tra các nguồn request có nhiều nhược điểm. Trong đó, một nhược điểm làm chậm quá trình grant là "có thể xuất hiện nhiều chu kỳ rảnh giữa hai lần grant" vì một request phải chờ đến lượt của nó mới được grant cho dù request này đã được tích cực trong khi không có request nào khác tích cực.

Để giải quyết vấn đề này, một phương pháp có thể thực hiện là thiết kế kết hợp bộ đếm Round Robin và các logic xác định mức ưu tiên. Chú ý, việc sử dụng logic xác định ưu tiên không có nghĩa là bộ phân xử này là bộ phân xử theo mức ưu tiên. Về bản chất, nó là bộ phân xử RR vì quyền ưu tiên truy cập được chuyển qua lại giữa các nguồn request chứ không giữ cố định cho một nguồn request nào.

Hình 1: Cấu trúc tổng quan bộ phân xử RR kết hợp xét mức ưu tiên

Bộ phân xử RR kết hợp mức ưu tiên gồm các thành phần logic sau:

1. RR Counter: Bộ đến RR là bộ đếm tăng hoặc giảm đều 1 đơn vị khi không có request nào tích cực hoặc khi kết thúc một grant.
2. Select priority logic: là thành phần sử dụng giá trị bộ đếm RR để tạo tín hiệu chọn "mạch logic ưu tiên" nào sẽ được phép hoạt động.
3. Priority logic: là mạch logic xét mức ưu tiên có số lượng bằng số nguồn request. Mỗi mạch logic ưu tiên nhận tất cả các nguồn request để so sánh mức ưu tiên nhưng thứ tự ưu tiên của các nguồn request ở mỗi mạch là khác nhau và không trùng nhau.
4. Grant logic: là logic lái ngõ ra tín hiệu grant.

2) Mô tả chi tiết thiết kế

Mạch nguyên lý của bộ đếm RR thể hiện trong hình sau:

Hình 2: Mạch nguyên lý bộ đếm RR (RR counter)

Bộ đếm trên tăng trong 2 trường hợp:

• Không có bất cứ request nào đang tích cực, ứng với việc tất cả các req[REQ_NUM-1:0] bằng 0
• Kết thúc một quá trình grant, ứng với việc req[*]=0 trong khi grant[*]=1

Hai trường hợp trên làm cho tín hiệu incCounter=1. Nếu giá trị bộ đếm bằng với mức của nguồn request cuối cùng (req[REQ_NUM-1]) thì nó sẽ quay về 0.

Mạch lựa chọn logic ưu tiên là các bộ so sánh. Số lượng bộ so sánh bằng số lượng nguồn request.

Hình 3: Mạch nguyên lý tạo tín hiệu chọn "logic ưu tiên"

Các mạch logic ưu tiên sẽ có cấu trúc giống nhau. Nguyên lý của mạch này các bạn đã gặp ở bài 1 và bài 2. Ở đây, thứ tự ưu tiên từ cao đến thấp là reqIn[0] đến reqIn[REQ_NUM-1]. Sau khi xét xong thứ tự ưu tiên, kết quả sẽ được AND với Sel, có tác dụng như một tín hiệu enable, để xác định thời điểm ngõ ra reqOut có giá trị hợp lệ.

Hình 4: Mạch nguyên lý của logic xác định mức ưu tiên

Bằng cách nối các bit của tín hiệu req[REQ_NUM-1:0] đến mạch logic trên theo các thứ tự khác nhau, chúng ta sẽ tạo ra các bộ logic ưu tiên như hình minh họa 1. Giả sử REQ_NUM=4, ứng với 4 nguồn request, chúng ta cần tạo 4 bộ xác định mức ưu tiên như sau:

1. Priority logic 0 (nối prioritySel[0] với Sel)
• req[3] nối đến reqIn[3] (Ưu tiên thấp nhất)
• req[2] nối đến reqIn[2]
• req[1] nối đến reqIn[1]
• req[0] nối đến reqIn[0] (Ưu tiên cao nhất)
2. Priority logic 1 (nối prioritySel[1] với Sel)
• req[0] nối đến reqIn[3] (Ưu tiên thấp nhất)
• req[3] nối đến reqIn[2]
• req[2] nối đến reqIn[1]
• req[1] nối đến reqIn[0] (Ưu tiên cao nhất)
3. Priority logic 2 (nối prioritySel[2] với Sel)
• req[1] nối đến reqIn[3] (Ưu tiên thấp nhất)
• req[0] nối đến reqIn[2]
• req[3] nối đến reqIn[1]
• req[2] nối đến reqIn[0] (Ưu tiên cao nhất)
4. Priority logic 3 (nối prioritySel[3] với Sel)
• req[2] nối đến reqIn[3] (Ưu tiên thấp nhất)
• req[1] nối đến reqIn[2]
• req[0] nối đến reqIn[1]
• req[3] nối đến reqIn[0] (Ưu tiên cao nhất)

Các bạn sẽ thấy ngõ vào của một bộ xét mức ưu tiên quay phải (right rotate) 1 bit so với bộ xét mức ưu tiên ngay trên nó. Vì vậy, ngõ ra reqOut sẽ được quay lái (left rotate) tương ứng trước khi đưa đến Grant logic. 

Hình 5: Sơ đồ minh họa kết nối của các bộ xét mức ưu tiên và việc quay trái (left rotate) reqOut tạo ra reqOutVector

Lưu ý, trong hình minh họa trên đây, reqOut có độ rộng bit bằng độ rộng bit tất cả các ngõ ra của "Priority logic" cộng lại, tức là REQ_NUM*REQ_NUM. Giả sử có 4 nguồn request, nếu không quay trái, thì vị trí bit trong reqOut ứng với req[0] tại mỗi bộ ưu tiên như sau:

• Priority logic 0: reqOut[0] vì req[0] nối đến reqIn[0]
• Priority logic 1: reqOut[7] vì req[0] nối đến reqIn[3]
• Priority logic 2: reqOut[10] vì req[0] nối đến reqIn[2]
• Priority logic 3: reqOut[13] vì req[0] nối đến reqIn[1]

Phân bố như trên làm việc chọn ra các bit thuộc về từng nguồn request trở nên khó khăn (khó viết RTL code). Như nếu "left rotate" tạo thành tín hiệu reqOutVector, thì vị trí bit trong reqOutVector ứng với req[0] sẽ là:

• Priority logic 0: reqOutVector[0] 
• Priority logic 1: reqOutVector[4]
• Priority logic 2: reqOutVector[8]
• Priority logic 3: reqOutVector[12]

Hình 6: Mạch nguyên lý tạo tín hiệu grant và noGrant

3) Kết quả mô phỏng

Một trong các waveform minh họa được thể hiện dưới đây, tác giả sẽ không giải thích chi tiết từng phần, các bạn có thể quan sát và phân tích waveform để có thể hiểu thiết kế hơn.

Ở đây, tác giả chỉ chú ý một điểm, dù các request tích cực ở bất cứ thời điểm nào thì nó cũng sẽ được phân xử và cấp phát chứ không phải chờ đến lượt ưu tiên như bài 3. Ví dụ, ở đoạn cuối waveform, khi rrCounter=1, "priorityLogic 1" được cho phép hoạt động, req[0]=1 có mức ưu tiên thấp nhất nhưng các request có mức ưu tiên cao hơn là req[3:1] không tích cực nên req[0] được grant (grant[0]=1) ngay chu kỳ kế tiếp.

Hình 7: Một waveform minh họa hoạt động của arbiter

Nhận xét, bộ phân xử trong bài viết này loại bỏ được chu kỳ rảnh giữa các lần cấp phát quyền truy cập. Bất cứ khi nào có request xuất hiện là nó sẽ được phân xử và grant ngay chu kỳ kế tiếp, điều này khác với bộ phân xử RR trong bài 3.
Tuy nhiên, mức độ "cân bằng" khả năng cấp phát quyền truy cập chưa cao vì bộ đếm RR tăng liên tục trong khi không có nguồn nào request (noGrant=1). Điều này làm cho mức ưu tiên các nguồn request thay đổi liên tục nên một nguồn request vẫn có khả năng được grant hai lần liên tiếp trong khi nguồn request khác tích cực nhưng không được grant. Ví dụ, khi rrCounter=0, req[0] có mức ưu tiên cao nhất, req[0] tích cực tại thời điểm này và được grant. Sau đó, req[0] thôi tích cực nhưng chưa có nguồn request nào tích cực (noGrant=1), rrCounter đếm lên 1, 2, 3, ..., REQ_NUM-1 và quay lại giá trị 0. Giả sử lúc này, tất cả các request tích cực cùng lúc thì req[0] vẫn được grant lần 2 vì khi rrCounter=0 bộ logic ưu tiên priorityLogic0 được chọn và req[0] đang có mức ưu tiên cao nhất.

Dữ liệu có thể tải:
Source code trên Github

Lịch sử cập nhật:
1) 2019.Aug.23 - Tạo lần đầu
2) 2019.Aug.24 - Thêm nhận xét về ưu nhược điểm ở cuối bài viết