Zeah Engineering Factory

라우터의 datapath는 buffer와 switch로 구성되는 반면, control path는 대부분 arbiter와 allocator로 이루어진다. 16장에서 논의한 것처럼 allocator는 packet에 virtual channel을 할당하거나 flit에 switch cycle을 할당할 때 사용된다. 이 장에서는 하나의 자원에 대해 여러 요청이 있을 경우 이를 해결하는 arbiter에 대해 설명한다. arbiter는 그 자체로도 유용하지만, 여러 요청자와 여러 자원을 매칭하는 allocator의 기본 구성 요소이기도 하다. allocator에 대한 설명은 19장에서 다룬다.

버퍼, 채널, 또는 스위치 포트와 같은 자원이 여러 agent에 의해 공유되는 경우, arbiter는 이 자원에 대한 접근 권한을 한 번에 한 agent에게만 할당해야 한다. 그림 18.1(a)는 crossbar switch의 입력 포트와 같은 자원에 대해 연결된 virtual channel들이 접근을 요청할 때 사용하는 n-input arbiter의 기호를 보여준다. 전송할 flit을 가진 각 virtual channel은 자신의 request line을 assert하여 입력 포트 접근을 요청한다. 예를 들어, n = 8개의 VC 중에서 VC 1, 3, 5가 각각 r1, r3, r5를 assert했다고 하자. 그러면 arbiter는 이들 중 하나, 예컨대 VC 3을 선택해 g3을 assert함으로써 입력 포트를 VC 3에게 grant한다. VC 1과 5는 arbitration에서 패배하여, 나중에 r1과 r5를 다시 assert해야 한다. 일반적으로 이들 line은 grant를 받을 때까지 계속 high 상태를 유지한다.

18.1 Arbitration Timing

grant의 지속 시간은 애플리케이션에 따라 다르다. 어떤 경우에는 요청자가 자원을 여러 사이클 동안 중단 없이 사용할 필요가 있다. 반면, 매 cycle마다 다시 arbitration을 수행해도 되는 경우도 있다. 이처럼 다양한 상황에 대응하기 위해, arbiter는 단일 cycle, 고정된 cycle 수, 또는 자원이 해제될 때까지 grant를 유지하는 방식으로 설계할 수 있다.

예를 들어, flit을 단일 cycle 동안 처리하는 스위치의 arbitration에서는 VC가 스위치 포트를 단 한 cycle만 사용할 수 있도록 grant된다. 이 경우, 매 cycle마다 새로운 arbitration이 수행되며, 대부분은 arbitration 직후 cycle에 grant가 적용된다. 그림 18.2(a)는 이 예를 보여준다. cycle 1에서 VC 0과 VC 1이 r0, r1을 assert하여 요청한다. VC 0이 arbitration에서 승리하여 cycle 2에 grant를 받고 같은 cycle에 요청을 drop한다. VC 1은 요청을 계속 유지하고, 경쟁자가 없으므로 cycle 3에 grant를 받는다. 두 VC가 request line을 계속 유지하고 arbiter가 공정하다면(18.2절 참고), cycle 6~9처럼 매 cycle마다 번갈아가며 스위치 포트를 할당받게 된다.

그림 18.2(b)는 각 grant가 4 cycle 동안 유지되는 경우이다. 예를 들어 flit 전송이 4 cycle 걸리며 중단할 수 없는 스위치가 있는 라우터에서 발생한다. 여기서 VC 0이 cycle 1에서 arbitration에 승리하여 cycle 2~5까지 스위치를 할당받는다. VC 1은 요청을 계속 유지하지만, cycle 6까지 대기해야 한다.

마지막으로, 그림 18.2(c)는 자원이 해제될 때까지 grant가 유지되는 경우이다. 이때 VC i는 arbiter와 request line ri 및 hold line hi로 연결된다(그림 18.1(b) 참조). arbitration에서 승리한 VC는 hold line이 high 상태인 한 자원을 독점한다. 예를 들어, VC 0이 cycle 24까지 3 cycle 동안 스위치를 유지하고, 이후 VC 1이 cycle 56 동안 2 cycle 사용한다.

일부 arbiter는 request line이 low 상태로 바뀔 때까지 자원을 유지함으로써 가변 길이 grant를 구현하지만, 이 방식은 같은 agent가 자원을 연속해서 사용할 때 반드시 1 cycle 이상의 idle gap이 필요하다. 그러나 hold line이 별도로 존재하면, 자원을 release하고 같은 cycle 내에 다시 request할 수 있다. VC 1은 cycle 6에서 정확히 이런 방식으로 동작하여 cycle 7에 다시 스위치를 grant받는다.

18.2 공정성 (Fairness)

arbiter의 핵심 특성 중 하나는 공정성(fairness)이다. 직관적으로 공정한 arbiter는 여러 요청자에게 동등한 서비스를 제공한다. 그러나 이 "동등함"의 의미는 애플리케이션에 따라 다를 수 있다. 공정성에 대한 유용한 세 가지 정의는 다음과 같다:

• 약한 공정성 (Weak fairness): 모든 요청은 결국 처리된다.
• 강한 공정성 (Strong fairness): 요청자는 동일한 횟수로 서비스받는다. N번의 arbitration 평균 기준으로, 어떤 요청자가 서비스받은 횟수와 다른 요청자가 받은 횟수의 차이는 ε 이내여야 한다. 종종 이 개념은 가중치 공정성(weighted fairness)으로 확장되어 요청자 i가 서비스받은 횟수는 그 가중치 wi에 비례해야 한다.
• FIFO 공정성: 요청자가 요청한 순서대로 서비스받는다. 빵집에서 번호표를 받아 순서대로 서비스받는 방식과 유사하다.

arbiter가 local하게는 공정하더라도, 그 arbiter를 사용하는 전체 시스템이 공정하지 않을 수 있다. 그림 18.3은 이러한 예를 보여준다. 네 개의 source r0~r3가 단일 destination으로 packet을 전송하는데, 이들은 세 개의 strongly fair한 2:1 arbiter를 통과한다. 각 arbiter는 두 입력에 대해 bandwidth를 반반씩 할당하지만, 최종적으로는 source들 간에 bandwidth가 공정하게 분배되지 않는다. r3는 한 번의 arbitration만 거쳐 전체 bandwidth의 절반을 얻지만, r0와 r1은 세 번의 arbitration을 거쳐야 하므로 각각 1/8만 얻는다. 이와 같은 문제와 해결 방안은 15.4.1절 및 본 장의 18.6절에서 더 자세히 설명된다.

18.3 고정 우선순위 Arbiter

우선순위를 선형적으로 정의하면, 이를 반복적(iterative) 회로로 구현할 수 있다. 그림 18.4의 고정 우선순위 arbiter가 그 예이다. 이 arbiter는 비트 셀(bit cell)들의 선형 배열로 구성된다. 각 비트 셀 i는 요청 입력 ri와 carry 입력 ci를 받아 grant 출력 gi와 carry 출력 ci+1을 생성한다.

carry 입력 ci는 더 높은 우선순위를 가진 요청이 자원을 아직 얻지 못했음을 나타내며, 이 셀에서 자원을 사용할 수 있음을 의미한다. 현재 요청 ri가 true이고 carry도 true이면, grant 라인을 assert하고 carry 출력을 deassert하여 자원이 이미 할당되었음을 나타낸다.

그림 18.4(a)와 같이 반복형 arbiter의 비트 셀을 구성할 수 있다. 이 비트 셀은 요청 입력 ri와 carry 입력 ci를 받아 grant 출력 gi와 carry 출력 ci+1을 생성한다. 이 논리를 식으로 표현하면 다음과 같다:

• gi = ri ∧ ci
• ci+1 = ¬ri ∧ ci

그림 18.4(b)는 이러한 방식으로 구성된 4비트 고정 우선순위 arbiter를 보여준다. 이 arbiter는 그림 18.4(a)의 비트 셀 4개로 구성된다. 단, 첫 번째와 마지막 비트 셀은 간소화되어 있다. 첫 번째 비트 셀은 c0이 항상 1이라는 점을 활용하며, 마지막 비트 셀은 c4를 생성할 필요가 없다는 점을 활용한다.

처음 보면, 반복형 arbiter의 지연 시간이 입력 개수에 비례해 선형적으로 증가할 것처럼 보인다. 실제로 그림 18.4처럼 구성된다면, 최악의 경우 carry가 한쪽 끝에서 다른 쪽 끝까지 전달되어야 하므로 선형 지연이 발생한다. 그러나 adder에서 사용되는 carry-lookahead 기법을 적용하면 지연 시간을 입력 개수에 대해 로그(logarithmic) 수준으로 줄일 수 있다 (Exercise 18.1 참고).

비록 반복형 구성 예시로는 유용하지만, 그림 18.4의 arbiter는 실제로는 전혀 공정하지 않다. 약한 공정성조차 만족하지 않는다. 예를 들어 요청 r0이 계속 assert되어 있으면, 다른 어떤 요청도 절대 서비스받지 못한다.

18.4 가변 우선순위 반복형 Arbiter

공정한 반복형 arbiter를 만들기 위해서는 매 cycle마다 우선순위를 바꾸면 된다. 그림 18.5는 이를 보여주는 예로, one-hot 우선순위 신호 p를 사용하여 가장 높은 우선순위 요청을 선택한다. p에서 한 비트만 1로 설정되며, 해당 위치의 요청이 가장 높은 우선순위를 가지며 이후 우선순위는 원형 carry chain을 따라 순환적으로 감소한다.

이 arbiter의 논리식은 다음과 같다:

• gi = ri ∧ (ci ∨ pi)
• ci+1 = ¬ri ∧ (ci ∨ pi)
• c0 = cn

18.4.1 Oblivious Arbiter

그림 18.5의 회로에 입력되는 우선순위 p는 여러 방식으로 생성할 수 있으며, 이 방식에 따라 arbitration의 성질이 달라진다. 만약 p가 r이나 g에 대한 정보 없이 생성된다면, 이는 oblivious arbiter가 된다. 예를 들어 shift register를 사용하여 매 cycle마다 우선순위를 한 칸씩 회전시키는 방식이나, 난수 발생기의 출력을 디코딩하여 p를 생성하는 방식 등이 있다.

이러한 rotating arbiter나 random arbiter는 약한 공정성은 만족한다. 결국 모든 요청은 언젠가 높은 우선순위를 얻게 되어 서비스받을 수 있다. 그러나 이들은 강한 공정성은 제공하지 못한다.

예를 들어, n-input arbiter에서 두 인접 요청 ri와 ri+1만 지속적으로 요청하고 나머지 입력은 모두 low라고 하자. 이 경우 ri+1이 승리하는 경우는 pi+1이 true일 때뿐이며, ri는 나머지 n−1개의 p 입력에 대해 모두 승리한다. 따라서 ri는 ri+1보다 n−1배 더 자주 grant를 받는다. 이 불공정함은 round-robin arbiter를 사용하면 해결할 수 있다.

18.4.2 Round-Robin Arbiter

Round-robin arbiter는 방금 서비스받은 요청자가 다음 arbitration에서 가장 낮은 우선순위를 갖도록 동작한다. 이는 현재의 grant 벡터 g로부터 다음 우선순위 벡터 p를 생성함으로써 구현할 수 있다. Verilog로 표현하면 다음과 같다:

 assign next_p = |g ? {g[n-2:0],g[n-1]}:p;

그림 18.6은 4비트 round-robin arbiter를 도식화한 것이다. 현재 cycle에 grant가 발생하면, 해당 gi 라인 하나가 high가 되고, 다음 cycle에는 pi+1이 high가 되어 그 다음 요청이 가장 높은 우선순위를 갖게 된다. 이전에 grant를 받았던 요청은 다음 arbitration에서 가장 낮은 우선순위를 갖는다. 만약 현재 cycle에 어떤 grant도 발생하지 않으면, anyg가 low가 되어 우선순위 상태는 유지된다.

Round-robin arbiter는 강한 공정성을 제공한다. ri가 서비스받으면 가장 낮은 우선순위가 되며, 다른 pending 요청들이 먼저 서비스된 후 다시 ri가 서비스된다.

18.4.3 Grant-Hold Circuit

지금까지 살펴본 arbiter들은 자원을 한 cycle씩만 할당한다. grant를 받은 클라이언트는 단 한 cycle 동안만 자원을 사용할 수 있으며, 이후 다시 arbitration을 해야 한다. 이 방식은 많은 애플리케이션에서 충분하지만, 18.1절에서 설명했듯이 몇몇 상황에서는 자원을 여러 cycle 동안 연속으로 사용하는 것이 필요하다. 예를 들어, 클라이언트가 packet을 output buffer로 전송하기 위해 3 cycle 동안 switch에 uninterrupted access가 필요할 수 있다.

grant-hold circuit을 사용하면 grant의 지속 시간을 연장할 수 있다. 그림 18.7은 이를 보여준다. Verilog 코드로 표현하면 다음과 같다:

 assign g = anyhold ? hold : gc ; // n-bit grant vector
 assign hold = last&h; // n-bit hold vector
 assign anyhold = |hold ; // hold not zero
 always @(posedge clk) last=g; // last cycle’s grant vector

grant를 받은 bit가 이전 cycle에서도 grant를 받고 있었고(last가 true), hold 라인 h가 assert되어 있다면, 해당 bit는 계속해서 grant를 받는다(gi가 계속 high 상태를 유지). 이 동안에는 arbitration이 비활성화된다.

18.4.4 Weighted Round-Robin Arbiter

일부 애플리케이션에서는 하나의 요청자가 다른 요청자보다 더 많은 grant를 받도록 제어된 불공정성을 요구한다. Weighted round-robin arbiter는 이러한 동작을 수행한다. 각 요청자 i는 weight wi를 할당받으며, 이 값은 요청자가 받을 수 있는 최대 grant 비율 fi를 나타낸다:

  fi = wi / W  여기서 W = ∑(j=0~n−1) wj

즉, 큰 weight를 가진 요청자는 많은 grant를 받고, 작은 weight를 가진 요청자는 적은 grant를 받는다. 예를 들어, 입력 weight가 1, 3, 5, 7이라면, 각각 전체 grant의 1/16, 3/16, 5/16, 7/16을 받는다.

그림 18.8과 같이, weighted round-robin arbiter는 각 요청자가 자신에게 할당된 quota를 초과했는지를 판단하는 회로를 arbiter 앞단에 배치하여 구성할 수 있다. 이 그림은 1비트 슬라이스를 보여주며, 이 회로는 weight 레지스터, 카운터, AND 게이트, 일반 arbiter로 구성된다.

preset 신호가 assert되면, 각 슬라이스의 카운터는 해당 weight로 초기화된다. 카운터 값이 0이 아닌 동안에는 AND 게이트가 활성화되어 요청이 arbiter로 전달된다. 요청자가 grant를 받을 때마다 카운터는 감소한다. 카운터가 0이 되면 AND 게이트가 비활성화되어 요청이 차단되며, 다음 preset까지 이 요청자는 grant를 받을 수 없다.

preset 신호는 W cycle마다 활성화된다. 모든 요청자들이 자신의 quota를 요청했다면, preset 구간이 끝날 때쯤 모든 카운터는 0이 된다. 일부 요청자가 자신의 quota를 사용하지 않는 경우, 나머지 요청자의 카운터는 더 빨리 0에 도달하여 preset 구간이 끝날 때까지 자원이 idle 상태로 남게 된다.

이러한 idle을 줄이기 위해 multistage arbiter를 사용하여 quota를 다 쓴 요청자도 idle cycle을 놓치지 않고 경쟁할 수 있도록 할 수 있다.

weight 비트 수를 정하는 것은 precision과 burstiness 사이의 trade-off를 발생시킨다. weight 비트를 많이 사용하면 정밀한 비율을 설정할 수 있지만, 그만큼 burstiness가 커진다. 각 요청자는 preset 구간인 W cycle 동안 평균적으로 quota만큼 보장받기 때문에, 이 간격이 길어질수록 초기에는 low-weight 요청자가 많이 받고, 이후 high-weight 요청자가 따라잡는 식의 불균일한 사용 패턴이 나타난다. (Exercise 18.2 참고)

18.5 Matrix Arbiter

Matrix arbiter는 가장 최근에 서비스받은 요청자의 우선순위를 가장 낮게 만드는 우선순위 방식을 구현한다. 이를 위해 상태 비트 wij로 구성된 삼각형 배열을 유지하며, 여기서 i < j이다. wij는 요청 i가 요청 j보다 우선이라는 의미이다. 배열의 대각선 원소는 필요하지 않으며, wji = ¬wij 이므로 상삼각형 부분만 저장하면 된다.

어떤 요청 k가 grant를 받으면, 해당 row wk의 모든 bit를 clear하고, column wk의 모든 bit를 set하여 요청 k가 가장 최근에 서비스된 것으로 처리하고 가장 낮은 우선순위가 되도록 한다.

그림 18.9는 4-input matrix arbiter를 보여준다. 상태는 상삼각형의 6개의 flip-flop (실선 박스)에 저장되며, 하삼각형의 음영 박스는 대칭 위치의 상태 bit의 반전값을 나타낸다.

요청이 assert되면 해당 row의 상태 bit와 AND 연산을 수행하여 낮은 우선순위의 요청들을 비활성화한다. 각 column에 대해, AND 결과들은 OR 게이트로 모여 해당 요청에 대한 disable 신호를 생성한다. 예를 들어, w02가 set되고 r0이 assert되면, dis2가 assert되어 r2 요청을 disable시킨다.

disable되지 않은 요청은 AND 게이트를 통해 해당 grant 출력으로 전달된다. grant가 발생하면 해당 row의 상태 bit를 clear하고, column의 상태 bit를 set하여 이 요청자가 이후 arbitration에서 가장 낮은 우선순위가 되도록 한다. 이 상태 변화는 다음 클럭 상승 에지에서 반영된다 (그림 18.10 참고).

정상 동작을 위해서는 matrix arbiter가 올바른 초기 상태로 설정되어야 한다. n-input arbiter의 가능한 상태는 2^[n(n−1)/2]개이지만, 입력 순열은 n!개에 불과하다. 의미 없는 상태나 순환(cycle)이 발생하는 상태는 위험하며 deadlock을 유발할 수 있다. 예를 들어, w01 = w12 = 1이고 w02 = 0이며 r0, r1, r2가 모두 assert되면, 서로를 disable시켜 아무도 grant를 받지 못한다.

(비트 오류 등으로 인해 arbiter가 불법 상태로 들어갈 경우 이를 복구하는 메커니즘을 마련하는 것도 중요하다.)

18.6 Queueing Arbiter

Matrix arbiter가 가장 최근에 서비스된 요청을 낮은 우선순위로 설정하는 방식이라면, Queueing arbiter는 FIFO 방식으로 요청을 처리한다. 그림 18.11처럼, 각 요청에 대해 assert 시점을 기준으로 timestamp를 부여하고, 이후 comparator tree를 통해 가장 오래된 요청을 선택한다.

Timer 블록은 arrival interval(일반적으로 클럭 cycle)마다 timestamp를 증가시키는 카운터이다. 요청이 도착하면(새로운 요청이 0→1로 전이되거나 이전 cycle에서 grant를 받고 계속 high 상태를 유지하는 경우), 현재 timestamp가 latch되어 stamp 블록에 저장되며 요청의 index(예: r0 → index 0, r1 → 1 등)와 함께 기록된다. 이때 요청은 index와 timestamp 쌍 (i, ti)로 표현된다.

요청이 없는 입력은 특별한 큰 값의 timestamp와 grant로 디코딩되지 않는 index로 표현된다. 이후 comparator tree에서 pairwise 비교를 통해 가장 작은 timestamp를 갖는 index iw를 찾는다. 각 comparator 노드는 두 요청을 비교해 더 빠른 timestamp를 가진 요청을 다음 단계로 전달한다. 마지막으로, 이 winning index iw가 디코딩되어 하나의 radial grant 신호로 변환된다.

arbiter의 cost는 주로 timestamp를 표현하기 위한 비트 수에 의해 결정되며, 이는 stamp 블록의 레지스터 크기를 좌우한다.

Queueing arbiter의 cost는 stamp 블록에 사용되는 레지스터 크기와 comparator tree의 comparator 폭에 의해 결정된다. 두 시간 관련 파라미터의 비율은 필요한 timestamp의 비트 수 wt를 결정한다:

  wt = log₂(Δt / ta)

여기서 Δt는 timestamp의 범위이고, ta는 요청 도착 간격이다. 두 값 모두 일반적으로 clock cycle 단위로 표현된다.

Δt는 예상 가능한 최대 요청 도착 시간 차이를 커버할 수 있을 만큼 커야 하며, timer rollover도 감당할 수 있어야 한다. 다음과 같이 정의된다:

  Δt = 2nTmax  (식 18.1)

여기서 n은 arbiter 입력 수, Tmax는 최대 서비스 시간이다. 식에서 2를 곱한 이유는 뒤에 설명된다.

Δt가 너무 커서 wt가 부담스러워지는 경우, ta를 증가시켜 비트 수를 줄일 수 있지만, 이 경우 정확도는 떨어지게 된다. 즉, arbiter는 요청 도착 시점을 ta 단위로 반올림하여 처리하게 되며, ta가 클수록 순서가 어긋날 수 있다.

타이머가 최대값에서 0으로 롤오버될 때, 새 요청이 기존 요청보다 더 작은 timestamp를 받는 일이 생기면, 큐의 앞쪽으로 끼어드는 부당한 동작이 발생할 수 있다.

이러한 문제는 모든 timestamp의 MSB를 현재 timer의 MSB와 XNOR 연산하여 비교하기 전에 보정하면 해결할 수 있다. 예를 들어, Δt = 16 (따라서 wt = 4), ta = 1일 경우, 요청 간 최대 시간 차 nTmax = 8이다. 타이머가 15에서 0으로 롤오버될 때, 모든 timestamp는 [8,15] 범위에 있게 된다. 이때 timestamp의 MSB를 보정하면 [0,7]로 변환되고, 새 요청은 8이 되어 새로운 요청이 늦게 들어온 것처럼 판단된다.

이 방식은 Δt가 요청 시간 간 최대 차이의 두 배가 되도록 요구하므로, 식 18.1에서 계수 2가 필요하다. Exercise 18.7에서는 Δt를 nTmax보다 약간 더 큰 값으로 줄이기 위한 방법을 다룬다.

서비스 시간이 작을 경우에는 Δt 요구 범위도 작다. 예를 들어, 모든 서비스 시간이 1인 4-input arbiter에서는 nTmax = 4이고, MSB 보정 방식 사용 시 Δt = 8이므로 3비트 timestamp면 충분하다. ta를 4로 완화하면 1비트만으로도 동작은 가능하지만, 이 경우 queueing arbiter의 공정성은 round-robin 수준과 다를 바 없게 된다.

Queueing arbiter는 여러 단계에 걸친 arbitration에서 글로벌(system-level) 공정성을 확보하는 데 특히 유용하다. 이 문제는 18.2절과 그림 18.3에서 다루었다. 시스템 수준의 공정성을 확보하려면, 각 요청(예: 각 패킷)에 대해 시스템 진입 시 timestamp를 부여해야 하며, 이 시점은 실제 arbitration 대기 큐에 들어가기 직전이다.

이를 위해 시스템 전체에 동기화된 timestamp counter와, 각 진입 지점마다 stamp module을 배치한다. 이렇게 부여된 timestamp는 이후 모든 arbitration 단계에서 유지되며, 새로 갱신되지 않는다. 또한 시스템 내 모든 queue는 timestamp 순으로 정렬되어야 하며, 가장 오래된 timestamp가 우선적으로 처리되어야 한다. 이렇게 전체 시스템에서 가장 작은 timestamp를 선택하도록 설계된 arbiter는 강한 시스템 수준의 공정성을 제공하게 된다. 예를 들어, 그림 18.3의 예에서는 모든 요청자가 전체 bandwidth의 정확히 0.25를 받게 된다.

18.7 연습문제

18.1 Carry-lookahead arbiter. 입력 수에 비례하지 않고 로그 비례한 시간에 동작하는 64-input fixed-priority arbiter를 설계하라. 힌트: 4비트 그룹으로 나누고, 각 그룹에 대해 propagate 신호를 계산하라. 이 propagate 신호는 그룹 내 carry가 끝까지 전달되는지를 의미한다. 이후 4비트 그룹들의 propagate 신호를 이용하여 16비트 그룹 propagate 신호를 생성하라.

18.2 Weighted round-robin. 4-input weighted round-robin arbiter에서 가중치가 각각 5, 5, 5, 49일 때, 모든 입력이 항상 요청하는 상황을 고려하라. 이 경우 arbiter의 grant 시간 순서를 설명하고, 이상적인 순서와 어떤 차이가 있는지 설명하라. 필요하면 이상적인 순서를 제공하는 arbiter를 도식으로 그려도 좋다.

18.3 Matrix arbiter 동작. 그림 18.9와 같은 4-input matrix arbiter가 있다고 하자. arbiter는 모든 상태 비트를 0으로 초기화한 후, 다음과 같은 요청 벡터를 매 cycle마다 받는다: r3...r0 = 1111, 1111, 1010, 1001. 각 cycle마다 어떤 grant가 발생하는지, 마지막에 matrix 상태는 어떻게 되는지를 서술하라.

18.4 Queueing arbiter 설계. 입력이 8개인 queueing arbiter를 설계하라. 각 입력의 최대 서비스 시간은 8 cycle이며, 어떤 8개의 서비스 시간 합도 32 cycle을 넘지 않는다. timing precision은 ta = 4 cycle 허용한다. timer rollover 처리를 위해 MSB 보정 기법을 사용할 경우, timestamp는 몇 비트가 필요한가?

18.5 Timer rollover. Figure 18.11과 같은 queueing arbiter에서 Δt = nTmax + 1일 때 timer rollover를 어떻게 처리할 수 있는지 설명하라.

18.6 Matrix arbiter 상태 오류. 어떤 i > j에 대해 wij의 상태 값이 illegal일 경우, 여러 요청이 동시에 grant를 받을 수 있는 상태가 존재하는가? 또한 arbiter 상태 오류를 탐지하고 수정하는 간단한 방법을 제안하라.