[Arbiter] Bài 1 - Phân xử theo mức ưu tiên cố định

Đây là bài đầu tiên trong chuỗi bài trình bày về lý thuyết và cách thiết kế các bộ phân xử (arbiter). Qua chuỗi bài viết này các bạn có thể hiểu về các phương pháp phân xử, ưu nhược điểm của từng phương pháp và cách mô tả giải thuật phân xử khả tổng hợp với RTL code có tính linh động cao.
Bài này trình lý thuyết, sơ đồ nguyên lý và Verilog code của một số phương pháp phân xử truy cập với mức ưu tiên cố định (fixed priority) trong hệ thống.

1) Tại sao cần phải có phân xử truy cập?

Trong một hệ thống SoC, nhiều nguồn (source) hay nhiều master cùng truy cập (access) đến một đích (destination) hay một slave là một hoạt động bình thường và thường xuyên xảy ra. Ví dụ, nhiều master cùng truy cập, đọc hoặc ghi, đến một vùng bộ nhớ (memory). Trong trường hợp này, một đích hoặc slave không thể đáp ứng đồng thời tất cả các truy cập cùng lúc mà chỉ có thể đáp ứng tuần tự từng truy cập theo một thứ tự trước sau nhất định.

Việc xác định truy cập nào thực hiện trước, truy cập nào thực hiện sau, chính là "phân xử truy cập". Thành phần thực hiện chức năng "phân xử truy cập" thường gọi là "bộ phân xử" (arbiter).

Hình 1: Ví trị của arbiter trong một hệ thống hoặc một thiết kế

Bộ phân xử thực hiện chức năng chính như sau:

• Nhận các yêu cầu truy cập từ nhiều nguồn, mỗi yêu cầu truy cập gọi là một request.
• Thực thi thuật toán phân xử nếu có nhiều request xuất hiện cùng lúc.
• Cấp phát (grant) quyền truy cập cho nguồn (source hoặc master) được chọn

Một thành phần trong hệ thống SoC thường có bộ phân xử bên trong là BUS hệ thống.

Hình 2: Ví dụ minh họa về arbiter trong bus hệ thống (nguồn: https://www.silvaco.com)

2) Các phương pháp phân xử cơ bản

Các thuật toán phân xử có thể được xây dựng theo các hướng sau:

• Phân xử theo mức độ ưu tiên
• Phân xử cân bằng

Phân xử theo mức độ ưu tiên là mỗi nguồn phát request sẽ được gán một mức ưu tiên khác nhau. Nguồn có mức ưu tiên cao sẽ luôn được grant trước nguồn có mức ưu tiên thấp nếu hai nguồn cùng phát request.
Thuật ngữ "được grant" sử dụng trong bài này với ý nghĩa "bộ phân xử cấp phát quyền truy cập cho một nguồn request bằng cách tích cực tín hiệu grant tương ứng".
Phân xử cân bằng hướng đến mục tiêu làm cho các nguồn phát request có cơ hội được grant như nhau. Trong phương pháp phân xử cân bằng, không phải các nguồn có mức độ ưu tiên ngang nhau mà các nguồn có "cơ hội được grant" ngang nhau. Nghĩa là tại một thời điểm, nếu hai hay nhiều nguồn cùng phát request thì chỉ có một request được grant. Request được grant là request được ưu tiên nhất tại thời điểm đó. Sau khi request của nguồn hiện tại hoàn thành thì bộ phân xử sẽ ưu tiên grant cho các request từ các nguồn khác cho dù nguồn hiện tại tiếp tục gửi request thứ 2. Điều này đảm bảo một nguồn phát request không thể chiếm quyền truy cập của các nguồn khác bằng cách phát request liên tục.
Để làm rõ hơn các lý thuyết trên, phần sau bài viết sẽ trình bày một số phương pháp thiết kế bộ phân xử. Trong các ví dụ này, các bạn lưu ý các điểm sau:

• Mỗi bit của tín hiệu req kết nối đến một nguồn phát request. Mức 1 biểu thị một request từ nguồn đang gửi đến arbiter.
• Mỗi bit của tín hiệu grant kết nối đến nguồn phát request tương ứng, ví dụ như grant[0] ứng với req[0]. Mức 1 biểu thị request được cấp quyền truy cập.

3) Phân xử với mức ưu tiên cố định (Fixed priority)
Trong phương pháp này, mỗi nguồn phát request có một mức ưu tiên khác nhau và giá trị này là cố định.
Hình sau đây minh họa bộ phân xử với độ ưu tiên giảm dần từ bit 0 đến bit msb.

Hình 1: Sơ đồ nguyên lý bộ phân xử theo mức ưu tiên cố định

Để có thể mô tả RTL code cho bộ MUX ưu tiên với số lượng tín hiệu select thay đổi, cấu trúc sau đây được sử dụng.

Hình 2: Sơ đồ logic dùng để mô tả RTL code của bộ phân xử theo mức ưu tiên cố định

Theo sơ đồ logic trên, req[0] có mức ưu tiên cao nhất và luôn được grant (grant[0]=1) bất cứ khi nào req[0]=1. Các nguồn request khác chỉ được grant khi nguồn request có ưu tiên cao hơn nó không phát request. Ví dụ, req[2] chỉ được grant nếu req[1]=0 và req[0]=0.  Các bạn có thể nhận thấy rằng mức ưu tiên của các nguồn request là "tuyệt đối", mức ưu tiên cao luôn chiếm ưu thế tuyệt đối so với mức ưu tiên thấp. Vì vậy, tác giả tạm gọi đây là kiểu phân xử có mức ưu tiên cố định tuyệt đối. RTL code cho bộ phân xử này như sau:
Ví dụ 1: Bộ phân xử có mức ưu tiên cố định tuyệt đối

generate
    genvar i;
 //For req[0]
 always @ (posedge clk, negedge rst_n) begin
      if (~rst_n)
     grant[0] <= 1'b0;
   else
     grant[0] <= req[0];
    end
 //For req[REQ_NUM-1:1]
 for (i = 1; i < REQ_NUM; i++) begin: uGrant
      always @ (posedge clk, negedge rst_n) begin
        if (~rst_n)
       grant[i] <= 1'b0;
     else
       grant[i] <= req[i] & ~|req[i-1:0];
      end
 end //for loop
  endgenerate

Hình 3: Một waveform minh họa hoạt động của bộ phân xử theo mức ưu tiên cố định tuyệt đối

Bộ phân xử như trình bày ở trên có cấu tạo đơn giản, tài nguyên ít nhưng có nhiều nhược điểm:

• Nguồn request có ưu tiên cao chiếm ưu thế tuyệt đối. Nó luôn chiếm được grant cho dù nguồn request thấp hơn đang được grant. Ví dụ, grant[1]=1 nhưng nếu req[0]=1 thì grant[1]=0 và grant[0]=1, quyền truy cập được cấp cho req[0].
• Nếu các nguồn request có mức ưu tiên càng thấp thì khả năng không được grant càng cao. Nếu các request mức ưu tiên cao luôn tích cực trong suốt quá trình hoạt động thì request có mức ưu tiên thấp có khả năng không bao giờ được grant. 

Thiết kế của bộ phân xử có thể được điều chỉnh lại để thêm đặc điểm "khi một nguồn request đã được grant thì grant của nó chỉ thôi tích cực khi request hiện tại thôi tích cực". Nghĩa là nếu một nguồn request đang được grant thì nó sẽ không bị chiếm quyền bởi request có mức ưu tiên cao hơn. Lúc này, request có mức ưu tiên cao hơn phải chờ cho grant hiện tại kết thúc thì mới được cấp phát.

Hình 4: Sơ đồ nguyên lý bộ phân xử theo mức ưu tiên cố định không tuyệt đối

Trong sơ đồ trên, mạch tạo nextGrant sẽ chỉ lấy giá trị phân xử mới nếu không có grant nào đang tích cực (noGrant = 1). Nếu một bit grant đang tích cực thì bit grant đó sẽ được giữ mức 1 nếu request vẫn giữ mức 1.

Hình 5: Sơ đồ logic dùng để mô tả RTL code của bộ phân xử theo mức ưu tiên cố định không tuyệt đối

Ví dụ 2: Bộ phân xử có mức ưu tiên cố định không tuyệt đối

  assign noGrant = ~|grant[REQ_NUM-1:0];
  //
  generate
    genvar i;
    //For req[0]
    always @ (posedge clk, negedge rst_n) begin
      if (~rst_n)
 grant[0] <= 1'b0;
      else if (noGrant)
 grant[0] <= req[0];
      else
        grant[0] <= req[0] & grant[0];
    end
    //For req[REQ_NUM-1:1]
    for (i = 1; i < REQ_NUM; i++) begin: uGrant
      always @ (posedge clk, negedge rst_n) begin
        if (~rst_n)
   grant[i] <= 1'b0;
 else if (noGrant)
   grant[i] <= req[i] & ~|req[i-1:0];
        else
          grant[i] <= req[i] & grant[i];
      end
    end //for loop
  endgenerate

Hình 6: Một waveform minh họa hoạt động của bộ phân xử theo mức ưu tiên cố định không tuyệt đối

4) Phân xử với mức ưu tiên cố định và khóa quyền truy cập (Fixed priority and Lock)
"Bộ phân xử theo mức ưu tiên cố định không tuyệt đối" giúp quyền truy cập của một nguồn request không bị chiếm trong suốt quá trình nguồn request đó đang tích cực nhưng không thể giúp giữ quyền truy cập này cho lần request kế tiếp. Trong trường hợp này, chúng ta có thể sử dụng bộ phân xử hỗ trợ khóa (lock) quyền truy cập.
Bộ phân xử hỗ trợ khóa quyền truy cập cho phép một nguồn request có thể yêu cầu giữ grant cho nhiều request liên tiếp. Chức năng lock chỉ có tác dụng khi nguồn request được grant. Khi chức năng lock được thực thi, không một nguồn request nào có thể chiếm quyền truy cập (grant) của nguồn request đang lock.
Các tín hiệu của một thiết kế ví dụ như sau:

• clk: clock đồng bộ
• rst_n: reset tích cực mức thấp
• req[REQ_NUM-1:0]: Request từ các nguồn phát. Mỗi bit ứng với 1 nguồn.
• lockIn[REQ_NUM-1:0]: Tín hiệu khóa (lock) quyền truy cập ứng với từng nguồn request. lockIn[i] ứng với req[i].
• lockSta: Báo trạng thái lock. lockSta=1 nghĩa là có 1 nguồn đang lock quyền truy cập
• grant[REQ_NUM-1:0]: Tín hiệu báo cấp quyền truy cập cho mỗi nguồn request. grant[i] ứng với req[i].

Hình 7: Tín hiệu input/output của bộ phân xử có hỗ trợ LOCK

Mạch nguyên lý của bộ phân xử trên được minh họa bởi các hình dưới đây:

Hình 7: Sơ đồ nguyên lý bộ phân xử theo mức ưu tiên cố định với chức năng LOCK

Hình 8: Mạch nguyên lý tín hiệu lockSta and noLock

Trong các mạch nguyên lý trên, một số tín hiệu cần lưu ý:

• noLock: Tín hiệu báo trạng thái chưa có nguồn nào được cấp lock hoặc lock hiện tại đã hết hiệu lực
• lockReg[REQ_NUM-1:0]: Thanh ghi lưu lại trạng thái lock của các nguồn request
• nextGrant[REQ_NUM-1:0]: Tín hiệu đầu vào cho các bit grant, có hai nhánh điều kiện:
• Nếu nguồn hiện tại đang lock (lockReg[i]=1) thì grant[i] chỉ phụ thuộc vào nguồn request (req[i])
• Nếu nguồn hiện tại không được lock thì việc phân xử phụ thuộc vào quyền ưu tiên của các nguồn. req[0] ưu tiên cao nhất, req[REQ_NUM-1] ưu tiên thấp nhất

Ví dụ 3: Bộ phân xử theo mức ưu tiên cố định hỗ trợ LOCK

assign noGrant = ~|grant[REQ_NUM-1:0];
  //
  //Grant logic
  //
  generate
    genvar i;
    //For req[0]
    always @ (*) begin
      if (lockReg[0])
        nextGrant[0] = req[0];
      else if (noLock & noGrant)
        nextGrant[0] = req[0];
      else
        nextGrant[0] = req[0] & grant[0];
    end
    //For req[REQ_NUM-1:1]
    for (i = 1; i < REQ_NUM; i=i+1) begin: uGrant
      always @ (*) begin
        if (lockReg[i])
          nextGrant[i] = req[i];
        else if (noLock & noGrant)
          nextGrant[i] = req[i] & ~|req[i-1:0];
        else
   nextGrant[i] = req[i] & grant[i];
      end
    end //for loop
  endgenerate
  always @ (posedge clk, negedge rst_n) begin
    if (~rst_n)
      grant[REQ_NUM-1:0] <= {REQ_NUM{1'b0}};
    else
      grant[REQ_NUM-1:0] <= nextGrant[REQ_NUM-1:0];
  end
  //
  //Lock logic
  //
  generate
    genvar j;
   //
   for (j = 0; j < REQ_NUM; j=j+1) begin: uLock
   //
     always @ (posedge clk, negedge rst_n) begin
        if (~rst_n)
   lockReg[j] <= 1'b0;
 else if (nextGrant[j] & noLock)
   lockReg[j] <= lockIn[j];
 else if (lockReg[j])
          lockReg[j] <= lockIn[j];
        else
         lockReg[j] <= 1'b0;
      end
    end //for loop
  endgenerate
  //
  assign lockSta = |lockReg[REQ_NUM-1:0];
  assign noLock  = ~|(lockReg[REQ_NUM-1:0]
    & lockIn[REQ_NUM-1:0]);

Hình 9: Một waveform minh họa hoạt động LOCK trong bộ phân xử

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

Lịch sử cập nhật:
1) 2019.Aug.17 - Tạo lần đầu