Zeah Engineering Factory

책 전반에서 살펴본 바와 같이, interconnection network의 설계는 성능 요구사항 명세와 몇 가지 패키징 및 비용 제약 조건으로부터 시작된다. 이러한 기준들이 해당 네트워크의 topology, routing, flow-control 선택을 이끈다. 이러한 설계 초기 결정들을 안내하기 위해, 우리는 zero-load latency와 throughput 같은 단순한 성능 예측 지표들을 소개했다. 물론 이 지표들은 네트워크에 대한 몇 가지 가정을 포함한다. 예를 들어, routing algorithm과 topology에 대한 대부분의 분석에서 이상적인 flow control을 가정했다. 네트워크 설계 초기에는 단순한 모델이 합리적이지만, 네트워크의 정확한 성능을 정확히 특성화하려면 더 정밀한 모델이 필요하다.

이 장에서는 먼저 네트워크의 기본적인 성능 지표들을 정의하고, 이 지표들을 어떻게 추정하고 해석하는지를 설명한다. 이어서 queuing model과 확률적 기법을 포함하는 상위 수준 네트워크 동작 모델링에 유용한 분석 도구들을 소개한다. 24장에서는 보다 정밀한 네트워크 시뮬레이터 사용을 다루고, 25장에서는 여러 네트워크 구성에서의 시뮬레이션 결과를 제시한다.

23.1 Interconnection Network 성능 측정 지표

특정 네트워크의 성능을 측정하고 표현하는 방법은 여러 가지가 있지만, 여기서는 throughput, latency, fault tolerance의 세 가지 기본 항목에 초점을 맞춘다. 이 용어들은 일반적으로 들릴 수 있으나, 그 정확한 정의는 어떻게 측정하느냐, 즉 측정 환경에 강하게 의존한다.

측정 구성

interconnection network의 표준 측정 구성은 그림 23.1에 나타나 있다. 네트워크 성능을 측정하기 위해, 네트워크의 각 terminal 또는 port에 terminal instrumentation을 부착한다. 이 instrumentation은 지정된 traffic pattern, packet 길이 분포, interarrival 시간 분포에 따라 packet을 생성하는 packet source를 포함한다. 각 terminal에서는 packet source와 네트워크 사이에 무한 깊이의 source queue가 존재한다. 이 source queue는 시뮬레이션 대상 네트워크의 일부는 아니며, traffic process와 네트워크를 분리하기 위해 사용된다. packet source와 source queue 사이에는 입력 packet을 카운트하고 각 packet의 시작 시간을 측정하는 input packet measurement process가 있다. 이 측정 프로세스는 반드시 source queue 이전에 위치해야 한다. 그래야 source에 의해 생성되었지만 아직 네트워크에 주입되지 않은 packet도 고려되며, packet의 latency가 source queue에서의 시간도 포함하게 된다. 각 출력 terminal에도 대응되는 측정 프로세스가 있어 packet을 카운트하고 각 packet의 종료 시간을 기록한다. throughput은 각 출력에서 도착한 packet을 카운트하여 측정하고, latency는 각 packet의 종료 시간에서 시작 시간을 뺀 값으로 측정한다.

Open-loop 측정

이러한 open-loop 측정 구성은 traffic parameter를 네트워크와 독립적으로 제어할 수 있게 해 준다. source queue가 없다면, packet source가 네트워크 terminal이 수용 불가능한 시점—예를 들어 input buffer가 가득 찼을 때—에 packet을 주입하려 할 수 있다. 이 경우, source가 생성한 traffic은 네트워크에 의해 영향을 받아 원래 지정한 traffic pattern이 아니게 된다. 우리는 일반적으로 특정 traffic pattern에서 네트워크를 평가하는 것이 목표이므로, throughput, latency, fault tolerance 측정을 위해 open-loop 방식을 사용한다.

Closed-loop 측정

네트워크가 traffic에 영향을 미치는 closed-loop 측정 시스템은 전체 시스템 성능을 측정할 때 유용하다. 예를 들어, multicomputer의 성능을 추정하려면 terminal instrumentation을 multicomputer processor 시뮬레이션으로 대체한 시뮬레이션을 수행한다. 생성되는 traffic은 실제 애플리케이션 실행 중 발생하는 프로세서 간 혹은 프로세서-메모리 간 메시지이다. 프로세서는 네트워크와 상호작용하므로 주입률은 쉽게 제어되지 않는다. 예를 들어, 메모리 응답을 기다리는 프로세서는 outstanding request 수 제한으로 인해 요청 수가 줄어든다. 이 설정에서는 보통 애플리케이션 실행 시간이 bandwidth, routing algorithm, flow control 같은 네트워크 parameter에 얼마나 민감한지 테스트하는 데 사용된다.

Steady-state 성능 측정

대부분의 경우, 우리는 네트워크의 정상 상태(steady-state) 성능, 즉 고정된 traffic source가 equilibrium에 도달한 후의 성능에 관심을 가진다. 네트워크가 equilibrium에 도달했다는 것은 평균 queue 길이가 정상 상태 값에 도달했다는 의미이다. 정상 상태 측정은 측정 대상 process가 stationary할 때만 의미 있다. 즉, process의 통계적 특성이 시간에 따라 변하지 않아야 한다. transient 성능 측정, 즉 traffic이나 구성 변화에 대한 네트워크의 응답도 때때로 관심 대상이지만, 대부분은 steady-state 측정에 초점을 둔다.

정상 상태 성능을 측정하기 위해 실험(또는 시뮬레이션)을 세 단계로 나눈다: warm-up, measurement, drain.

• Warm-up phase: 네트워크가 equilibrium에 도달할 수 있도록 N₁ 사이클을 실행하며, 이 기간 동안 packet은 측정되지 않는다.
• Measurement phase: N₂ 사이클 동안, source queue에 들어가는 모든 packet에 시작 시간이 태그되며, 이들을 measurement packet이라 부른다.
• Drain phase: measurement packet이 목적지에 모두 도달할 때까지 네트워크를 계속 실행한다. 도착한 packet의 종료 시간을 측정하고 기록한다. 이 측정 구간 동안 도착한 모든 packet은 throughput 측정을 위해 카운트된다. latency는 measurement packet의 시작 시간과 종료 시간으로 계산된다.

모든 measurement packet의 종료 시간을 측정하지 못하면 latency 분포의 꼬리 부분이 잘려 나가게 되므로, simulation을 충분히 길게 실행해야 한다.

※ 네트워크가 공정(fair)하지 않다면 마지막 measurement packet이 도달하는 데 많은 cycle이 걸릴 수 있다. 네트워크가 starvation에 취약하다면 drain phase가 끝나지 않을 수도 있다.

warm-up과 drain phase 동안에도 packet source는 packet을 계속 생성하지만, 이 packet은 측정 대상이 아니다. 그러나 이 packet은 background traffic으로서 measurement packet에 영향을 준다. N₁과 N₂ 값의 결정 방법은 24.3절에서 다룬다.

23.1.1 Throughput

Throughput은 특정 traffic pattern에서 네트워크가 packet을 전달하는 속도이다. 각 flow(즉, source-destination 쌍)에서 지정된 시간 동안 도착한 packet 수를 카운트하여 flow rate를 계산하고, 이로부터 전체 traffic pattern의 일부로서 얼마나 전달되었는지를 계산한다.

Throughput(accepted traffic)은 demand(offered traffic)과 대비된다. demand는 packet source가 packet을 생성하는 속도이다.

Throughput과 demand의 관계를 이해하기 위해 일반적으로 throughput(accepted traffic)을 demand(offered traffic)의 함수로 나타낸 그래프를 사용한다. (그림 23.2 참조) saturation 이하의 traffic 수준에서는 throughput이 demand와 같고, 이때 그래프는 직선이다. offered traffic이 계속 증가하면 결국 saturation에 도달하게 되며, 이는 throughput이 demand와 같게 유지되는 최대 수치이다. demand가 saturation을 넘으면 네트워크는 더 이상 동일한 속도로 packet을 전달할 수 없다.

packet이 생성되는 속도만큼 빠르게 전달되지 못하면 — 또는 적어도 우리가 요구하는 traffic pattern에 대해서는 — 네트워크는 saturation을 초과한 상태가 된다. saturation을 초과한 이후에도 안정적인 네트워크는 지정된 traffic pattern에 대해 최대 throughput을 유지하며 동작한다. 그러나 많은 네트워크는 불안정하며, saturation을 지나면 throughput이 급격히 떨어진다. 예를 들어, 그림 23.2의 네트워크는 안정적이며, saturation throughput은 전체 용량의 43%이다. 그림 23.3은 유사한 네트워크의 성능을 보여주는데, 이 또한 43%에서 saturation이 발생하지만, 그 이후 throughput이 급격히 하락하며 불안정하다. 이는 flow control mechanism의 unfairness 때문이며, 이러한 네트워크는 25.2.5절의 시뮬레이션 예제에서 더 자세히 분석된다.

throughput은 일반적으로 네트워크 용량의 일부로 표현된다. 이렇게 하면 네트워크의 성능을 더 직관적으로 이해할 수 있으며, 크기나 topology가 다른 네트워크 간의 비교도 가능하다. 예를 들어, 그림 23.2의 8-ary 2-mesh 네트워크의 총 용량은 U^,M=4b/k=b/2\hat{U},M = 4b/k = b/2U^,M=4b/k=b/2이다. 여기서 b는 channel bandwidth이다. 모든 source가 동일한 양의 traffic을 생성한다고 가정하면, 각 source는 bλ/2b\lambda/2bλ/2의 속도로 packet을 생성하며, 여기서 λ는 전체 용량 대비 offered traffic 비율이다. saturation은 이 용량의 43%에서 발생한다.

일부 불안정한 네트워크의 경우, saturation을 초과해도 전달된 packet의 총량은 일정하게 유지되지만, 이 packet들의 분포가 지정된 traffic pattern과 일치하지 않는다. 이러한 네트워크의 throughput을 정확히 측정하려면 특정 traffic pattern에 대한 throughput을 측정해야 한다. 이를 위해 네트워크의 모든 입력에 지정된 traffic을 적용하고, 각 flow에 대해 수용된 traffic을 별도로 측정한다. 지정된 traffic pattern에 대한 throughput은 모든 flow에 대해 수용된 traffic과 제공된 traffic의 비율 중 최소값으로 정의된다.

saturation을 초과하여 demand를 증가시키면, 도착지로 전달된 traffic matrix는 다음과 같은 형태를 가진다고 볼 수 있다:

즉, 목적지에 도달한 traffic은 우리가 원하는 traffic pattern의 Θ 단위와 추가적인 traffic X로 구성되며, X는 strictly positive한 행렬이다. throughput 측정 시 이 추가 traffic은 우리가 지정한 traffic pattern에 부합하지 않으므로 계산에 포함되지 않는다.

네트워크 불안정성은 종종 네트워크 내의 fairness 문제로 인해 발생한다. 과거에는 saturation 이후 평균 throughput만을 보고하는 경우가 많았으며, 이는 X에 대해 가산점을 주는 셈이다. 하지만 모든 flow 중 최소 throughput을 보고하면, 어떤 flow가 starvation되고 있는지를 확인할 수 있다. starvation은 일반적으로 unfair flow control의 결과이다. 그림 23.2에서는 saturation 이후에도 accepted traffic이 거의 일정하므로, 네트워크가 각 flow에 bandwidth를 공정하게 할당하고 있다고 볼 수 있다. 반면 그림 23.3에서는 saturation 이후 throughput이 급격히 감소하는데, 이는 flow control이 불공정하다는 것을 시사한다.

심지어 네트워크가 flow 간 bandwidth를 공정하게 할당하더라도, offered traffic이 증가함에 따라 accepted traffic이 줄어들 수 있다. 이는 non-minimal routing algorithm에 의해 발생할 수 있다. routing 결정이 불완전한 정보에 기반할 경우, contention이 증가하면서 misrouting도 늘어나고, 그 결과 packet이 더 많은 hop을 거치게 되어 channel load가 증가한다. 이러한 문제를 피하려면 routing algorithm을 신중히 설계해야 하며, 그렇지 않으면 saturation 이후 throughput이 빠르게 감소할 수 있다.

유사한 상황은 deadlock-free escape path를 사용하는 adaptive routing algorithm에서도 발생할 수 있다. offered traffic이 증가하면 더 많은 packet이 escape path로 밀려나고, accepted throughput은 결국 adaptive algorithm이 아닌 escape routing algorithm의 throughput 수준으로 떨어진다. 이 내용은 25.2절에서 추가로 다룬다.

offered traffic 대비 accepted traffic 그래프는 특정 traffic pattern에서 네트워크의 throughput 성능을 상세히 보여주지만, 여러 traffic pattern의 성능을 한눈에 보려면 saturation throughput에 대한 히스토그램을 그리는 것이 유용하다. 예를 들어, 10³ ~ 10⁶개의 무작위 permutation traffic pattern을 생성해 측정한 결과를 시각화할 수 있다. 이와 관련된 예시는 25.1절에 포함되어 있다.

23.1.2 Latency

Latency는 packet이 source에서 destination까지 네트워크를 통과하는 데 걸리는 시간이다. 지금까지 latency 평가는 주로 zero-load latency에 초점을 맞추었으며, 이는 shared resource에 대한 다른 packet들과의 contention에 의한 latency를 무시한다. contention latency를 모델링이나 시뮬레이션으로 포함하면 latency는 offered traffic의 함수가 되며, 이 함수를 그래프로 표현하면 도움이 된다. 그림 23.4는 latency vs. offered traffic 예시 그래프이다.

latency를 측정할 때는 그림 23.1의 측정 구성으로 traffic을 적용한다. 일반적으로 offered traffic αΛ를 α = 0에서 saturation throughput α = Θ까지 sweep한다. α > Θ인 traffic 수준에서는 latency가 무한대가 되어 측정이 불가능하다. 각 packet에 대해, source가 첫 번째 비트를 생성한 시점부터 마지막 비트가 네트워크를 빠져나가는 시점까지를 latency로 측정한다. 전체 latency는 모든 packet의 평균 latency로 보고된다. 경우에 따라서는 packet latency의 히스토그램, 최악의 packet latency, 특정 flow에 대한 통계도 유용하다. throughput과 마찬가지로 offered traffic은 네트워크 용량의 일부로 표시된다.

latency vs. offered traffic 그래프는 일정한 형태를 갖는다. 이는 zero-load latency의 수평 점근선에서 시작해, saturation throughput의 수직 점근선으로 향한다. low traffic 구간에서는 latency가 zero-load latency에 근접한다.

traffic이 증가함에 따라 contention도 증가하면서, packet은 buffer와 channel을 기다리게 되어 latency가 상승한다. 결국 offered traffic이 saturation throughput에 접근하면 latency 곡선은 수직 점근선에 근접하게 된다. 이 곡선의 형태는 기본적인 queuing theory (23.2.1절 참조)로 설명할 수 있다.

평균 latency도 유용하지만, 전체 또는 특정 subset에 대한 latency 분포를 분석하는 것도 의미 있다. 예를 들어, virtual-channel flow control을 사용하는 경우, 일부 채널은 high-priority traffic에 예약되어 있을 수 있다. 이럴 때 high-priority와 일반 traffic의 latency를 분리하여 분석하면 우선순위 정책의 효과를 평가할 수 있다. 또 하나의 유의미한 subset은 특정 source-destination pair 사이의 packet 전체이다. 특히 non-minimal routing algorithm을 사용하는 경우 유용하며, 해당 경로의 평균 길이를 추정하는 데 활용할 수 있다. 여러 latency 분포 그래프는 25.2절에 제시되어 있다.

23.1.3 Fault Tolerance

Fault tolerance는 하나 이상의 고장이 발생한 상태에서도 네트워크가 동작할 수 있는 능력을 의미한다. 네트워크의 fault tolerance에 대한 가장 중요한 정보는 고장 발생 시에도 정상적으로 동작할 수 있는지 여부이다. 어떤 node나 channel의 단일 고장이 있어도 (faulty terminal을 제외한) 모든 terminal 간 packet 전달이 가능한 경우, 해당 네트워크는 single-point fault tolerant하다고 한다. 많은 시스템에서는 단일 고장만 견딜 수 있어도 충분한데, 이는 단일 고장 확률이 낮고 동시에 여러 고장이 발생할 확률은 매우 낮기 때문이다. 또한 대부분의 고가용성 시스템은 고장이 발생하면 즉시 복구되므로 다른 고장이 발생하기 전에 faulty component가 교체된다.

fault tolerance 요구는 여러 설계 결정에 영향을 준다. 예를 들어, 네트워크가 single-point fault tolerant해야 한다면 deterministic routing을 사용할 수 없다. 특정 channel에 fault가 생기면, 그 경로를 사용하는 모든 node pair가 연결을 잃기 때문이다. fault가 발생해도 성능이 점진적으로 저하된다면, 이를 graceful degradation이라고 부른다. fault-tolerant 네트워크의 성능은 25.3절에서 다룬다.

23.1.4 Common Measurement Pitfalls

interconnection network의 성능을 측정할 때 자주 발생하는 오류가 몇 가지 있다. 저자들 자신도 과거에 이러한 실수를 저질렀으며, 여기에서 소개함으로써 독자들이 같은 실수를 반복하지 않기를 바란다.

Source queue 누락: 네트워크 성능을 측정하면서 source queue를 제대로 구성하지 않는 경우가 많다. 그림 23.5는 source queue의 효과가 누락되는 두 가지 경우를 보여준다. 그림 23.5(a)에서는 아예 source queue가 없다. 이 경우...

그림 23.5 설명

그림 23.5는 무한한 source queue 없이 네트워크 성능을 측정하려는 시도를 보여준다. 결과 시스템은 closed loop가 되며, 적용된 traffic pattern은 원래 의도한 패턴이 아니게 되고, 측정된 latency는 네트워크 진입을 대기한 시간을 포함하지 않는다.

• (a): 입력 채널이 바쁠 때 source는 packet을 drop하거나 입력이 가능해질 때까지 injection을 지연시켜야 한다. 후자의 경우, 이후 packet의 생성도 지연되어야 하며, 그렇지 않으면 queue가 필요하다. 어느 경우든 네트워크의 contention이 traffic pattern에 영향을 주게 된다.
• (b): source queue는 존재하지만, packet 카운팅과 timing이 source queue의 출력에서 시작된다.

source queue가 없이 수행된 측정은 두 가지 이유로 무효이다.
첫째, 측정 지점에서 적용된 traffic pattern이 우리가 의도한 것과 다르다. 예를 들어 그림 23.6의 간단한 두 노드 네트워크를 보자. 여기서 node 1에서 0으로, 그리고 0에서 1로 각각 1 단위의 traffic을 주입하도록 설정한다. 그러나 source queue 출력 이후에서 packet을 측정하면, 실제 routing에 수락된 0 → 1 방향의 0.1 단위 traffic만 카운트되며, 반대 방향은 전체 1 단위가 그대로 측정된다. 이 결과는 우리가 측정하고자 하는 traffic pattern이 아니다.

둘째, source queue를 생략하면 packet latency가 과소 추정된다. queue 깊이가 얕고 blocking flow control을 사용하는 네트워크에서는 고부하 상황에서 발생하는 contention latency의 대부분이 source queue에서 발생한다. 실제로 네트워크 내부로 packet이 들어가면, 빠르게 전달되는 경우가 많다. 입력 채널을 기다리는 시간을 제외하면 실제 latency보다 훨씬 낮은 값이 측정된다.

평균 throughput만 보고하는 문제

입력 측정에서는 source queue 생략이 문제였다면, 출력 측정에서는 flow별 최소 throughput이 아닌 평균 throughput을 보고하면 문제가 된다. 이 경우에도 실제 측정 대상 traffic pattern과 다른 결과가 나온다.

예를 들어 그림 23.6의 네트워크를 보자. 두 목적지에 도달한 traffic의 평균을 내면, 1과 0.1의 평균인 0.55 단위에서 saturation이 일어난다고 결론 내릴 수 있다. 그러나 실제로 네트워크는 아래와 같이 전달하고 있다:

즉, 지정된 traffic pattern의 0.1 단위만 전달되고 나머지는 추가 traffic일 뿐이다. flow 중 최소 수용량을 측정해야 정확한 throughput을 알 수 있다.

특정 flow가 starvation되는 네트워크에서는 평균 throughput만 보고하면 이러한 문제가 완전히 감춰진다. 예를 들어 chaotic routing에서는 네트워크 내부의 packet에 절대적인 우선권을 부여하므로, 일부 input에서는 네트워크가 바쁠 경우 packet이 전혀 진입하지 못해 완전히 starving될 수 있다. 이때 평균 throughput은 여전히 높게 유지되므로, 네트워크가 안정적인 것처럼 보이지만 실제로는 일부 flow가 완전히 차단된 불안정한 상태다.

Latency와 throughput을 함께 나타내는 그래프

일부 연구자는 latency vs. offered traffic 곡선과 accepted vs. offered traffic 곡선을 하나의 그래프로 표현하려 한다. 그림 23.7이 그 예시이다. 이 그래프는 latency를 accepted traffic의 함수로 나타내며, 곡선 위의 각 점은 offered traffic의 다양한 수준을 나타낸다. 불안정한 네트워크에서는 accepted traffic이 saturation 이후 감소하기 때문에, 곡선이 왼쪽으로 되돌아가는 모양을 보인다.

이런 형태의 가장 큰 문제점은 source queue가 측정에 포함되지 않았다는 것을 드러낸다는 점이다. source queue를 고려했다면, saturation을 초과한 모든 offered traffic에서 latency는 무한대가 되어야 하며, 곡선은 wrap-around되지 않고 최대 accepted traffic에서 점근선 형태로 끝나야 한다.

게다가 BNF(Burton Normal Form) 차트는 일반적으로 steady-state 성능을 반영하지 않는다. 대부분의 불안정한 네트워크에서는 saturation 직후 accepted traffic이 급격히 낮아진 후, 그 이후 offered traffic이 증가해도 그 수준에 머문다. 이는 saturation 이후 source queue가 무한히 커지기 시작하기 때문이며, steady-state에서는 큐 크기가 고정된 것이 아니라 무한이 된다. BNF 차트에서 gradual fold-back이 보인다면, simulation이 충분히 오래 실행되지 않았다는 뜻이다.

테스트 구간 동안 생성된 모든 packet을 측정하지 않은 경우

간혹 목적지에서 수신된 packet들의 latency 평균만을 측정하는 경우가 있는데, 이는 측정 구간 동안 생성된 모든 packet을 측정한 것이 아니므로 오류다. 이 경우 긴 latency를 가진 packet들은 측정에 포함되지 않아 latency 분포의 꼬리 부분이 잘리고 평균 latency도 과소 추정된다. warm-up 이후 생성된 packet의 unbiased 샘플을 사용해야 한다. arrival 기준으로 선택한 packet은 편향된 샘플이다.

무작위 traffic만 사용하는 문제

Uniform random traffic은 네트워크 채널 간 load를 자연스럽게 균등하게 분산시켜주는 아주 benign한 패턴이다. nearest-neighbor traffic보다는 약하지만, 거의 best-case workload에 가깝다. 이 때문에 좋지 않은 routing algorithm조차 무난하게 보이게 할 수 있다. 따라서 다양한 adversarial traffic pattern (3.2절 참조)과 충분히 많은 무작위 permutation을 함께 사용해야 한다.

23.2 Analysis

interconnection network의 성능을 측정하기 위해 여러 도구들이 존재한다. 분석(analysis), 시뮬레이션(simulation), 실험(experiment) 모두 네트워크 평가에서 중요한 역할을 한다.

우리는 일반적으로 수학적 모델을 통해 네트워크 성능을 추정하는 분석으로부터 시작한다. 분석은 적은 노력으로 근사적인 성능 수치를 제공하며, 다양한 요소들이 성능에 어떻게 영향을 미치는지를 파악할 수 있게 해 준다. 또한, 분석을 통해 다양한 파라미터나 설정을 가진 네트워크 전체에 대한 성능 예측을 할 수 있는 수식 집합을 도출할 수 있다.

하지만 분석은 보통 여러 가지 근사나 가정을 포함하게 되므로 결과의 정확도에 영향을 줄 수 있다.

분석을 통해 근사적인 결과를 얻은 후에는 보통 시뮬레이션을 수행하여 분석 결과를 검증하고 보다 정확한 성능 추정을 얻는다. 좋은 모델을 사용할 경우 시뮬레이션은 정확한 성능 예측을 제공하지만, 그만큼 시간이 많이 소요된다. 각 시뮬레이션 실행은 단일 네트워크 구성, traffic pattern, load point만 평가할 수 있다. 또한 시뮬레이션은 결과만 요약해서 보여주므로, 어떤 요인이 성능에 영향을 주었는지 직접적인 통찰을 제공하지는 않는다.

※ 하지만 적절한 instrumentation을 사용할 경우, 시뮬레이션을 통해 성능 문제를 진단할 수도 있다.

router의 타이밍과 arbitration을 무시하는 시뮬레이터는 정확도가 매우 낮은 결과를 낼 수 있다.
네트워크가 실제로 구축된 후에는, 실험을 통해 실제 성능을 측정하고 시뮬레이션 모델을 검증한다. 물론 이 시점에서 성능 문제가 발견되면 수정하기 어렵고, 시간과 비용이 많이 든다.

이 절에서는 네트워크 성능 평가의 첫 번째 단계인 분석(analysis)을 다룬다. 특히, analytic performance analysis를 위한 두 가지 기본 도구인 queuing theory와 probability theory를 소개한다. queuing theory는 packet이 대부분의 시간을 큐에서 대기하는 네트워크 분석에 유용하고, probability theory는 contention 시간이 주로 blocking에 의해 발생하는 경우에 적합하다.

23.2.1 Queuing Theory

interconnection network에서 packet은 많은 시간을 큐에서 대기하며 보낸다. 측정 구성에서의 source queue뿐 아니라, 경로상 각 단계의 input buffer들도 큐로 간주된다. queuing theory를 이용하여 각 큐에서 packet이 대기하는 평균 시간을 예측함으로써, packet latency의 구성 요소들을 근사할 수 있다.

queuing theory 전체를 다루는 것은 이 책의 범위를 넘지만, 이 절에서는 queuing theory의 기본 개념을 소개하고 이를 단순한 interconnection network 분석에 어떻게 적용할 수 있는지 설명한다. 보다 자세한 내용은 queuing theory 전문 서적 [99]을 참고하라.

그림 23.8은 기본적인 큐잉 시스템을 보여준다.

source는 초당 λ개의 packet을 생성한다. 이 packet들은 service를 기다리며 큐에 저장된다. server는 큐에서 순차적으로 packet을 꺼내 평균 T초의 시간 동안 처리하며, 평균 처리율은 μ = 1/T packet/초이다.

interconnection network에서의 packet source는 terminal에서 packet을 주입하거나 다른 node로부터 packet을 전달하는 channel이다. arrival rate λ는 input terminal에서 들어오는 traffic rate이거나, 네트워크 channel에 들어오는 traffic의 superposition일 수 있다. server는 네트워크에서 packet을 제거하는 terminal이거나, packet을 다른 node로 운반하는 channel이다. 두 경우 모두 service time T는 packet이 channel 또는 terminal을 통과하는 시간이며, packet 길이에 비례하므로 T = L/b로 표현된다.

Markov Chain을 이용한 모델링

분석을 단순화하기 위해, 우리는 현실과 다르다는 것을 알고 있으면서도 몇 가지 가정을 한다.

• 큐는 무한 길이를 가진다고 가정
• packet 간 도착 시간(inter-arrival time)과 service time은 exponential distribution을 따른다고 가정

exponential process는 memoryless라고도 하며, 새 이벤트(예: packet 도착)가 발생할 확률이 과거 이벤트에 영향을 받지 않는다. arrival과 service를 이렇게 단순화하면, queuing system을 Markov chain으로 모델링할 수 있다 (그림 23.9 참조).

그림 23.9의 Markov chain은 큐의 상태 전이를 나타낸다. 각 원은 큐의 상태를 나타내며, 해당 상태에서 큐에 존재하는 packet 수로 라벨링된다. packet은 λ의 속도로 큐에 도착하고, 이에 따라 상태는 오른쪽으로 전이된다. 반대로 packet이 큐에서 제거되면 μ의 속도로 왼쪽 상태로 전이된다.

정상 상태에서는 어떤 상태로 들어오는 속도와 나가는 속도가 같아야 한다.
예를 들어 상태 p₀에 대해서는 다음과 같다:

기대 queue 길이 및 대기 시간

각 상태의 확률을 구했으므로, 큐에 있는 평균 entry 수(기대 queue 길이)는 다음과 같다:

E(NQ)=∑i=0∞ipi=ρ/(1−ρ)E(N_Q) = ∑_{i=0}^{∞} i p_i = ρ / (1 - ρ)E(NQ​)=i=0∑∞​ipi​=ρ/(1−ρ)

즉, 도착한 packet은 앞서 있는 packet들을 기다려야 하므로 평균 대기 시간은 다음과 같이 계산된다:

E(TW)=T×E(NQ)=Tρ/(1−ρ)=ρμ(1−ρ)E(T_W) = T × E(N_Q) = Tρ / (1 - ρ) = \frac{ρ}{μ(1 - ρ)}E(TW​)=T×E(NQ​)=Tρ/(1−ρ)=μ(1−ρ)ρ​

이 관계는 Little's law로 알려져 있다.

분산 및 다른 queue 유형

queue entry 수의 분산(variance)은 다음과 같다:

Var(NQ)=E(σNQ2)=ρ/(1−ρ)2Var(N_Q) = E(σ^2_{N_Q}) = ρ / (1 - ρ)^2Var(NQ​)=E(σNQ​2​)=ρ/(1−ρ)2

우리는 지금 M/M/1 queuing system에 대해 계산하였다. 이는 도착 및 서비스 시간이 exponential distribution을 따르며 server가 1개인 시스템이다.

다음은 기타 queue 유형과 비교한 결과:

• M/D/1 (deterministic service time)의 경우:

E(NQ)=ρ2(1−ρ)E(N_Q) = \frac{ρ}{2(1 - ρ)}E(NQ​)=2(1−ρ)ρ​

• M/G/1 (general service time)의 경우:

E(NQ)=λ2X22(1−ρ)E(N_Q) = \frac{λ^2 X^2}{2(1 - ρ)}E(NQ​)=2(1−ρ)λ2X2​

여기서 X²는 service time의 두 번째 모멘트이다. 많은 네트워크에서는 packet 길이, 즉 service time이 일정하거나 거의 일정하기 때문에, 일반적으로 위 식 (23.8) 또는 (23.9)를 사용하는 것이 식 (23.5)보다 더 적절하다.

주의할 점은, λ ≥ μ 또는 ρ ≥ 1인 경우 위 식들이 무효라는 것이다. 이때 latency는 무한이 되며, 위 식들은 음수를 반환하므로 적용할 수 없다.

네트워크 모델 예시: Butterfly Network

그림 23.10은 queuing theory를 사용하여 4-terminal butterfly network를 모델링하는 예를 보여준다.

• (a): 2-ary 2-fly 네트워크가 uniform traffic을 전달
• (b): 이를 queuing system으로 모델링

각 source는 λ 속도의 packet stream을 생성하는 source로, 각 destination은 service rate μ를 가지는 server로 모델링된다.

각 2×2 switch는 splitter(입력), combiner(출력), 그리고 output queue 두 개로 구성된다.

• splitter는 λ rate의 입력을 λ/2씩 나누어 각 switch 출력으로 보낸다.
• 각 combiner는 입력 두 개로부터 λ/2 stream을 받아 λ rate로 output queue로 전달한다.

각 switch의 output queue는 combiner에 의해 합쳐진 traffic을 받아들인다. 이 큐는 내부 채널에 의해 μc 속도로 서비스되며, 마지막 단계에서는 terminal에 의해 μ 속도로 서비스된다.

이러한 switch model은 Poisson arrival process의 특성을 활용한다. 즉, exponential inter-arrival time을 갖는 stream을 나누면 여전히 exponential 특성을 유지하는 stream들이 생성된다.

23.2.2 Probabilistic Analysis

queuing theory를 보완하기 위해, 우리는 probabilistic analysis를 사용하여 buffer가 없는 네트워크 또는 네트워크 구성 요소를 분석한다.

Section 2.6에서 dropping flow control이 적용된 네트워크의 성능을 추정하기 위해 probabilistic analysis를 사용한 예제를 이미 살펴본 바 있다. 이 절에서는 blocking flow control을 사용하는 네트워크의 성능을 어떻게 추정하는지 보여준다.

예를 들어, 그림 23.12(a)와 같은 blocking flow control과 queuing이 없는 2×2 switch를 생각해 보자. 각 출력 포트의 service time은 같고, deterministic하며, To로 설정한다. 두 입력의 traffic rate는 동일하며, λ₁ = λ₂ = λ이고, 양쪽 입력에서 나오는 traffic은 두 출력에 대해 균일하게 분포되어 있다고 가정한다. 즉, λᵢⱼ = λ / 2 (∀i, j).

i₁ 입력 채널이 바쁜(busy) 시간 Ti를 계산하기 위해, 먼저 i₁에 들어온 packet이 대기해야 할 확률 Pw를 계산한다:

Pw=λTo2=ρo2P_w = \frac{λ T_o}{2} = \frac{ρ_o}{2}Pw​=2λTo​​=2ρo​​

여기서 ρₒ = λ To 는 출력 링크의 duty factor이다.

packet이 대기해야 하는 경우, 평균 대기 시간 Twc는 다음과 같다:

Twc=To2T_{wc} = \frac{T_o}{2}Twc​=2To​​

이를 종합하면, 전체 packet에 대한 평균 대기 시간 Tw는:

Tw=PwTwc=λTo24=ρoTo4T_w = P_w T_{wc} = \frac{λ T_o^2}{4} = \frac{ρ_o T_o}{4}Tw​=Pw​Twc​=4λTo2​​=4ρo​To​​

결국 입력 채널의 busy 시간 Ti는 다음과 같다:

Ti=To+Tw=To(1+λTo4)=To(1+ρo4)T_i = T_o + T_w = T_o \left(1 + \frac{λ T_o}{4} \right) = T_o \left(1 + \frac{ρ_o}{4} \right)Ti​=To​+Tw​=To​(1+4λTo​​)=To​(1+4ρo​​)

이 식은 switch의 입력 측 busy 시간이 출력 링크의 duty factor에 비례해 증가함을 보여준다.

collision이 발생했을 때의 대기 시간 Twc는 service time의 분산에 큰 영향을 받는다. deterministic한 service time의 경우, 평균적으로 packet은 이미 처리 중인 packet의 중간 지점에서 도착하므로 Twc = To / 2가 된다. 만약 service time이 exponential 분포를 따른다면, 기대 대기 시간은 두 배로 증가하여:

Twc=To,Tw=λTo22=ρoTo2,Ti=To(1+ρo2)T_{wc} = T_o, \quad T_w = \frac{λ T_o^2}{2} = \frac{ρ_o T_o}{2}, \quad T_i = T_o \left(1 + \frac{ρ_o}{2} \right)Twc​=To​,Tw​=2λTo2​​=2ρo​To​​,Ti​=To​(1+2ρo​​)

이처럼 service time의 분산이 커지면 대기 시간도 증가한다. 이는 긴 service time을 가진 packet들이 전체 busy 시간에서 더 많은 비율을 차지하기 때문이다. multistage network를 분석할 때는 각 단계마다 분산이 다를 수 있다. 예를 들어, 그림 23.12의 switch는 deterministic한 출력 service time을 갖지만, 여전히 non-zero variance를 가진다.

23.3 Validation

queuing theory, probabilistic analysis, 또는 simulation이 interconnection network의 성능을 얼마나 정확하게 예측할 수 있는지는 해당 분석에서 사용한 모델의 정확도에 달려 있다.

모델이 네트워크의 모든 관련 동작을 정확하게 반영한다면, 분석은 매우 정확해질 수 있으며, 넓은 설계 공간을 빠르게 탐색하거나 성능에 영향을 주는 요인을 이해하는 데 강력한 도구가 될 수 있다. 반면, 중요한 네트워크 특성을 누락하거나 부적절한 근사치를 사용하면 실제 네트워크 성능과 크게 다른 결과가 나올 수 있다. 시뮬레이션도 마찬가지로, 부정확한 모델은 부정확한 결과를 낳는다.

Validation은 analytic model 또는 simulation model이 실제로 정확한지를 검증하는 과정이다. 예를 들어, 실제 네트워크에서 측정한 latency vs. offered traffic 데이터를 보유하고 있다면, 이를 사용해 simulation 또는 analysis 결과와 비교해 볼 수 있다. 결과가 일치하면 해당 모델이 중요한 요소들을 정확히 반영하고 있다고 판단할 수 있으며, 유사한 네트워크나 조건에서도 정확할 가능성이 높다.

실험 데이터가 없는 경우, 신뢰할 수 있는 simulation 결과를 기준으로 analytic model을 검증할 수도 있다. 그림 23.11은 이런 방식의 validation 예시다.

모델을 검증하려면 다양한 동작 지점과 네트워크 구성에서의 결과를 대표적인 데이터와 비교해야 한다. 특정 하나의 지점에서 모델이 정확하다고 해서, 매우 다른 조건에서도 정확할 것이라고 단정할 수는 없다. 예를 들어, zero-load latency를 정확히 예측한다고 해서 saturation 근처의 latency를 정확히 예측한다고 보장할 수는 없다.

23.4 사례 연구: BBN Monarch Network의 효율성과 손실

BBN Advanced Computer Systems는 Butterfly TC-2000 (Section 4.5)을 계승한 시스템으로 BBN Monarch [156]를 설계했다. Monarch는 많은 흥미로운 구조적 특징을 포함하고 있었지만, 결국 완성되지 못했다.

Monarch는 uniform-memory-access shared memory 시스템이었다. 최대 64K개의 processor가 butterfly-like 네트워크를 통해 N개의 memory module에 접근했다. 이 네트워크는 다음과 같은 특징을 가지고 있었다:

• dropping flow control 사용
• 목적지 memory module을 무작위화하기 위한 hashed memory address
• hot-spot traffic 처리를 위한 access combining 기법

접근은 동기적(synchronous)으로 이루어졌는데, 이는 combining을 단순화하기 위한 목적이었다. 시간은 frame으로 나뉘며, 각 processor는 frame 시작 시 1회의 memory access를 수행할 수 있었다. 같은 frame 내에서 같은 위치로 접근하는 요청들은 네트워크 내부 노드에서 결합(combine) 되어 단일 access packet으로 memory module로 전달되었다.

Monarch 네트워크는 그림 23.13과 같이 switch와 concentrator 단계를 번갈아 배치하여 구성되었다.

• 각 switch는 최대 12개의 입력과 32개의 출력을 가졌으며, 최대 4비트의 주소를 해석할 수 있었다.
• switch의 출력 포트는 그룹 단위로 구성되어, 같은 방향으로 여러 packet이 동시에 전송될 수 있도록 했다.
  예를 들어, 하나의 switch는 2포트씩 16개의 출력 그룹, 또는 4포트씩 8개의 출력 그룹으로 구성할 수 있었다.

packet은 switch의 어떤 입력 포트로 도착하든, 구성된 출력 그룹 내의 어떤 포트를 통해도 전송이 가능했다.

그림 23.13에 보이는 BBN Monarch 네트워크(1990)는 switch와 concentrator를 번갈아 배치한 stage들로 구성되어 있다. 각 stage에서의 concentration ratio는 효율성을 극대화하고 dropping flow control로 인한 손실을 최소화하기 위해 조정되었다. 각 채널은 직렬(serial) 방식으로 작동하며, 대역폭은 350 Mbit/s였다.

각 packet은 요청한 출력 그룹의 어느 채널이든 하나를 얻을 수 있으면 다음 stage로 진행했다. 그렇지 못하면 drop되었다.

Concentrator는 여러 개의 lightly loaded 채널을 더 적은 수의 heavily loaded 채널로 multiplexing하는 역할을 한다. 예를 들어, 여러 패키징 단계를 거쳐야 하는 고비용 채널 전에 이를 사용하는 방식이다.

• 각 concentrator 칩은 최대 32개의 입력과 12개의 출력을 지원한다.
• 모든 입력과 출력은 동등하며, 매 frame마다 32개 입력 중 어떤 12개에서든 도착한 최대 12개의 packet만이 출력으로 라우팅된다.
• 추가로 도착한 packet은 drop된다.

손실 확률 계산

probabilistic analysis를 이용하여 Monarch 네트워크 각 단계에서의 packet 손실 확률을 계산할 수 있다. 다음의 가정을 사용한다:

• 모든 입력 채널은 균일하게 load됨
• traffic은 출력에 대해 균일하게 분포됨
• address hashing과 access combining이 이 가정을 현실적으로 만들어 줌

어떤 switch가 I 개의 입력, G 개의 출력 그룹, 그리고 각 그룹당 C개의 채널을 가질 때, 입력 duty factor가 Pi라고 하자. 특정 입력 i가 특정 출력 그룹 j를 요청할 확률은 다음과 같다:

Pij=PiGP_{ij} = \frac{P_i}{G}Pij​=GPi​​

이때, k개의 입력이 같은 출력 j를 요청할 확률은 이항 분포를 따른다:

Pk=(Ik)(PiG)k(1−PiG)I−kP_k = \binom{I}{k} \left( \frac{P_i}{G} \right)^k \left( 1 - \frac{P_i}{G} \right)^{I - k}Pk​=(kI​)(GPi​​)k(1−GPi​​)I−k

출력 채널 j가 busy할 확률 Po는, k ≤ C인 경우에 대해 다음과 같이 계산된다.
k개의 요청 중 (C - k)/C 비율만큼은 채널이 idle이므로:

Po=1−∑k=0C−1(C−kC)PkP_o = 1 - \sum_{k=0}^{C-1} \left( \frac{C - k}{C} \right) P_kPo​=1−k=0∑C−1​(CC−k​)Pk​

이를 정리하면:

Po=1−∑k=0C−1(C−kC)(Ik)(PiG)k(1−PiG)I−k(23.14)P_o = 1 - \sum_{k=0}^{C-1} \left( \frac{C - k}{C} \right) \binom{I}{k} \left( \frac{P_i}{G} \right)^k \left( 1 - \frac{P_i}{G} \right)^{I - k} \tag{23.14}Po​=1−k=0∑C−1​(CC−k​)(kI​)(GPi​​)k(1−GPi​​)I−k(23.14)

효율성과 손실 계산

각 단계의 efficiency는 출력 traffic의 총합을 입력 traffic의 총합으로 나눈 값이다:

P(transmit)=GCPoIPi(23.15)P(\text{transmit}) = \frac{G C P_o}{I P_i} \tag{23.15}P(transmit)=IPi​GCPo​​(23.15)

손실률은 다음과 같다:

P(drop)=1−P(transmit)=1−GCPoIPi(23.16)P(\text{drop}) = 1 - P(\text{transmit}) = 1 - \frac{G C P_o}{I P_i} \tag{23.16}P(drop)=1−P(transmit)=1−IPi​GCPo​​(23.16)

표 23.1은 64K 포트를 갖는 Monarch 네트워크의 구성과 손실 분석 결과를 보여준다.
각 stage마다 식 (23.14)를 사용해 Po를 계산하고, 이 값을 다음 단계의 Pi로 사용하여 efficiency 및 손실률을 계산한다.

결과적으로 이 네트워크는 100% input load에서도 손실률 10% 미만을 달성할 수 있다.
단, 그 대가로 링크를 과도하게 구성하여 각 switch의 입력은 65% 미만, 각 concentrator의 입력은 25% 미만만 사용하도록 설계되었다. 이와 관련된 duty factor와 loss 간의 관계는 연습문제 23.7에서 탐구한다.

버퍼링의 영향

버퍼를 추가하면 output이 바쁠 때 packet을 drop하지 않고 대기시킬 수 있으므로 손실을 줄일 수 있다.
버퍼는 있지만 backpressure가 없는 경우, 모든 output이 busy하고 모든 버퍼가 가득 찼을 때만 packet이 drop된다. Monarch와 유사한 네트워크에 대해 buffering이 있는 경우의 분석은 연습문제 23.9에서 다룬다.

23.5 참고 문헌

• queuing theory의 일반적인 참고 문헌: Kleinrock [99]
• 네트워크에 특화된 모델링 기법: Bertekas [20]
• 네트워크의 probabilistic 분석 예시: Dally [46], Agarwal [2]
• 부분적으로 차 있는 유한 큐에 대한 분석 모델: Dally [47]
• k-ary n-cube 네트워크에서 deadlock에 대한 모델링: Pinkston and Warnakulasuriya [152]

23.6 연습문제

각 문제는 앞서 배운 개념과 분석 기법을 실제 적용해보는 연습이다.

(간략 정리)

• 23.1: 그림 23.10의 트래픽을 비균일하게 수정하여 latency vs. offered traffic 곡선 계산
• 23.2: 4:1 concentrator에서 over-subscription 확률과 average queuing delay 계산
• 23.3: dropping flow control의 queuing 모델 유도
• 23.4: 2-ary 3-fly 회로 스위칭 네트워크의 expected throughput 계산
• 23.5~23.6: k 입력 스위치 및 임의 traffic matrix에 대한 확률적 모델링 확장
• 23.7~23.8: Monarch 네트워크의 duty factor, cost와 loss 간의 관계 그래프화
• 23.9: 버퍼가 추가된 Monarch 네트워크에서 dropping 확률 계산 (F=8인 경우)
• 23.10~23.12: 위 문제들에 대한 simulation 수행 및 모델과의 비교 분석

Bus는 interconnection network 중 가장 단순하고 가장 널리 사용되는 형태이다. Bus는 여러 module을 단일 공유 채널로 연결하며, 이 채널은 broadcast 매체로 작동한다. Bus는 일반적으로 여러 signal line(또는 단일 line)으로 구성되며, 이들 라인은 모든 module에 연결된다. 하나의 module이 bus를 통해 메시지를 전송하면, 나머지 모든 module은 해당 메시지를 수신하게 된다. 많은 경우 메시지는 특정 module을 대상으로 하며, 나머지 module은 이를 무시한다. 종종 메시지를 수신한 module은 원래 송신자에게 응답 메시지를 보낸다. 예를 들어, memory로부터 데이터를 읽기 위해 processor는 읽을 word를 지정하는 메시지를 memory module에 보낸다. 그러면 memory module은 요청된 데이터를 담은 메시지를 processor에 보내 transaction을 완료한다. Bus protocol은 어느 module이 언제 전송 권한을 가지는지를 결정하며, module 간 메시지와 transaction을 정의한다.

Bus는 상위 계층의 communication protocol이 활용하는 두 가지 주요 속성을 가진다: broadcast와 serialization. Bus에서 multicast나 broadcast 메시지를 전송하는 비용은 point-to-point 메시지를 전송하는 것과 동일하다. 이는 모든 메시지가 물리적으로 모든 module에 broadcast되기 때문이다. 이로 인해 global 정보를 bus를 통해 쉽게 분배할 수 있다. 또한, 한 번에 하나의 module만 bus를 통해 메시지를 전송할 수 있으므로 메시지들은 직렬화되어, 고정된 명확한 순서로 발생한다. Snooping cache-coherence protocol은 이러한 두 가지 속성을 모두 활용한다. 예를 들어, 쓰기 작업 시 cache line의 주소를 모든 module에 broadcast하여 각자 local copy를 무효화하거나 갱신할 수 있도록 하고, write는 직렬화되어 특정 주소에 마지막으로 쓰인 값이 무엇인지 명확하게 한다. 반면, broadcast가 무료가 아니고 serialization에 명시적 동기화가 필요한 일반적인 interconnection network에서는 이러한 protocol이 훨씬 복잡해진다.

22.1 Bus의 기본 개념

아래 그림 22.1은 A부터 D까지 네 개 module을 연결하는 일반적인 bus의 datapath를 보여준다. 각 module은 양방향 인터페이스를 통해 bus에 연결되어 있으며, 이 인터페이스는 transmit enable(ET)이 활성화될 때 신호 T를 bus로 내보내고, receive enable(ER)이 활성화될 때 bus에서 신호를 읽어와 내부 신호 R에 저장하도록 한다. 예를 들어, module A가 module C로 메시지를 보내려면, A는 transmit enable ETA를 활성화하여 TA 신호를 bus에 출력한다. 같은 cycle 동안, module C는 receive enable ERC를 활성화하여 bus로부터 메시지를 수신하여 내부 receive signal RC에 저장한다.

물리적으로, bus는 하나의 도선(serial bus), 전체 메시지를 한 번에 전달하는 여러 도선(parallel bus), 또는 그 중간 형태로 구성될 수 있다. 중간 형태에서는 메시지를 작은 수의 parallel conductor를 통해 순차적으로 여러 cycle에 나눠 전송할 수 있다.

전기적으로, bus는 각 module과의 연결로 인해 발생하는 stub 및 임피던스 불연속성 때문에 고속 동작이 매우 어렵다. 이러한 전기적 이슈는 이 책의 범위를 벗어난다. 논리적으로는, transmit 인터페이스는 각 module이 transmit enable이 활성화될 때 bus에 신호를 출력할 수 있도록 해야 한다. transmit 인터페이스는 다음과 같은 방식이 될 수 있다: tri-state driver(그림 22.2[a]), open-drain driver(22.2[b]), 또는 dotted-emitter driver(22.2[c]). 후자의 두 방식은 중첩(overlap)에 강점이 있다.

그림 22.1: 일반적인 bus의 datapath
네 개 module (A~D)이 공유 bus를 통해 통신한다. 특정 시점에 하나의 module만 transmit signal T를 bus에 출력할 수 있으며, 이때 transmit enable ET가 활성화된다. 해당 신호는 bus를 통해 broadcast되며, 다른 module은 각자의 receive enable ER을 통해 이를 수신할 수 있다.

그림 22.2: 일반적인 bus 송신기 인터페이스
(a) tri-state driver, (b) open-drain driver, (c) dotted-emitter driver

여러 module이 동시에 transmit enable 신호를 활성화하더라도 전력과 접지가 단락되지 않도록 설계되어 있다. 수신 인터페이스는 bus의 신호 레벨에 적합한 수신기와 receive enable이 활성화될 때 메시지를 캡처하는 레지스터로 구성된다. serial 또는 multicycle bus에서는 이 레지스터가 여러 cycle에 걸쳐 메시지를 조립할 수 있다.

Bus는 cycle, message, transaction 단위로 동작한다. 다른 interconnection network와 마찬가지로, message는 송신자로부터 수신자 집합으로 전달되는 논리적 정보 단위이다. 예를 들어 memory 주소를 읽기 위해 processor module은 주소와 control 정보를 포함한 message를 하나 또는 여러 memory module로 보낸다. Serial bus에서는 메시지를 구성하는 각 phit를 여러 cycle에 걸쳐 전송해야 한다. transaction은 인과관계에 의해 연결된 메시지들의 연속으로 구성된다. 모든 transaction은 하나의 message로 시작하며, 해당 message에 의해 유발된 일련의 응답 메시지로 구성된다. 예를 들어 memory read transaction은 processor에서 memory module로 보내는 요청 메시지와, 선택된 memory module에서 processor로 응답하는 메시지로 구성된다.

Bus는 외부 시퀀싱 방식 또는 내부 시퀀싱 방식으로 동작할 수 있다. 외부 시퀀싱 bus에서는 모든 transmit/receive enable 신호가 외부 중앙 시퀀서에 의해 제어된다. 내부 시퀀싱 bus에서는 각 module이 bus protocol에 따라 자체적으로 enable 신호를 생성한다. 예를 들어, 마이크로코드 방식 processor는 centralized control logic이 enable 신호를 생성해 레지스터와 연산 유닛 간의 데이터 전송을 제어하는 외부 시퀀싱 bus를 사용하는 경우가 많다. 반면, 대부분의 processor-memory bus는 내부 시퀀싱 구조를 가지고 있다. processor가 bus 제어권을 획득하면 자체적으로 transmit enable을 생성하고, memory module은 bus 상의 메시지를 모니터링하여 요청 메시지를 수신하거나 응답 메시지를 전송할 시점을 결정한다.

Bus cycle은 동기식(synchronous) 또는 비동기식(asynchronous)일 수 있다.
그림 22.3
(a) 동기식 bus에서는 bus clock에 동기화된 cycle 단위로 동작한다. 송신자는 clock cycle 시작 시 bus에 데이터를 출력하고, 수신자는 clock cycle 종료 시 데이터를 수신한다.
(b) 비동기식 bus에서는 송신자가 데이터를 bus에 출력한 뒤 request 신호(Req)를 assert한다. 수신자는 이 신호를 보고 데이터를 수신하고 acknowledge 신호(Ack)를 assert하여 전송 완료를 알린다. 송신자가 Ack를 받으면 driver를 비활성화하여 다음 전송을 위해 bus를 해제한다.

내부 시퀀싱 bus에서 메시지를 전송하는 과정은 arbitration, addressing, transfer, acknowledgment 순으로 진행된다.

• Arbitration: 어떤 module이 transaction을 시작할지를 결정하며, 이긴 module은 bus master가 된다. 단순한 경우 processor만 항상 master가 되어 arbitration이 필요 없다.
• Addressing: 수신 module을 지정한다. 어떤 bus는 broadcast address를 먼저 보내고 다음에 directed message를 보낸다. 또 어떤 경우는 메시지 자체에 address를 포함한다. 예: 그림 22.4와 같이 Control, Address, Data 순서로 구성된 메시지 사용. 여기서 address는 bus 상의 module을 지정하며, memory address는 Data 필드에 포함된다.

그림 22.5: 단순한 bus 예시
Processor P와 16개의 memory module (M0~M15)을 연결하는 병렬 bus 구조.

• Control: 4비트 (cycle 종류)
• Address: 4비트 (memory module 선택)
• Data: 32비트 (주소 및 데이터 전송)

Read Transaction (Cycle 1~3)

1. Cycle 1: Processor가 Control = Rd, Address = M4, Data = 100016 전송
2. Cycle 2: Memory module M4 내부 접근 시간으로 idle
3. Cycle 3: M4가 Control = Reply, Data = 요청된 데이터 전송

Write Transaction (Cycle 4~6)

1. Cycle 4: Control = WrA, Data = 200016
2. Cycle 5: Control = WrD, Data = 123416
3. Cycle 6: M3가 Control = Ack 전송

timeout이 발생하면 bus 제어권은 processor로 다시 넘어가며, 이는 구현되지 않은 주소나 응답하지 않는 module로 인한 bus block을 방지한다.

22.2 Bus Arbitration

여러 module이 transaction을 시작할 수 있는 구조에서는 bus 사용 권한을 얻기 위해 arbitration이 필요하다. 이는 18장에서 설명한 어떤 arbitration 방식도 사용 가능하다.

Radial arbitration: 중심 arbiter에서 방사형으로 각 module과 연결되어 있으며, module은 request를 보내고 arbiter는 grant를 응답한다. 공정성을 위해 module은 마지막 cycle에서 request를 해제하거나, arbiter가 transaction을 감지하여 grant를 다음 module로 전환한다.

그림 22.7은 동기식 bus의 arbitration timing을 보여준다.

• Cycle 1: Module 1이 request 전송
• Cycle 2: Arbiter가 grant 부여
• Cycle 3: Module 1이 transaction 시작
  → 고정 master 방식에 비해 2 cycle의 latency가 추가됨

그림 22.6: Radial Arbitration을 사용하는 bus 구조
각 module은 transaction을 시작하고자 할 때 중앙 arbiter로 request 신호를 보낸다. Arbiter가 grant 신호로 응답하면 해당 module은 bus master가 되어 transaction을 시작한다.

module 1이 transaction을 진행하는 동안 module 2는 bus 요청을 대기해야 한다. arbitration으로 인해 첫 transaction 종료와 두 번째 시작 사이에 2 cycle의 idle 구간이 생긴다. 이 idle 구간은 다음 transaction에 대한 arbitration을 현재 transaction과 동시에 수행하는 pipelining 기법으로 제거할 수 있다.

중앙 arbiter 없이 동작하는 방식으로는 Daisy-chain arbitration이 있다 (그림 22.8). 여기서는 고정 우선순위 arbiter가 각 module에 분산되어 있고, module 간 carry 신호를 전달한다. module 1은 carry0를 high로 고정하므로 항상 request 시 grant를 받는다. module 1이 요청하지 않으면 carry가 다음 module로 전달된다. 하지만 이 방식은 고정 우선순위와 delay 문제로 인해 현대 시스템에서는 거의 사용되지 않는다.

또 다른 방식은 wire-OR bus를 이용한 Sequential Distributed Arbitration이다. open-drain 또는 emitter-follower transmitter를 사용하는 경우, 각 bus line은 모든 송신기의 출력을 OR한 결과를 나타낸다. 이를 활용해 module의 주소 비트 우선순위대로 arbitration을 수행할 수 있다.

그림 22.9: Wire-OR bus를 이용한 분산 arbitration 알고리즘

1. 우선순위의 최상위 비트부터 시작
2. 모든 module이 자신의 우선순위를 bus에 출력
3. 각 module은 bus에서 읽은 값이 자신의 비트보다 크면 경쟁에서 탈락
4. 최종적으로 가장 높은 우선순위를 가진 module만 남아 bus master가 됨

표 22.1: 분산 arbitration 예시

• 세 module의 우선순위: 1001(9), 1010(10), 0111(7)
• Cycle 1: OR 결과 1111 → priority 7 탈락
• Cycle 2: OR 결과 1011 → 모두 유지
• Cycle 3: OR 결과 1011 → priority 9 탈락
• Cycle 4: OR 결과 1010 → priority 10 승리

이 분산 arbitration 방식은 고정 우선순위(주소를 우선순위로 사용), least-recently-served(기존 master는 우선순위 0, 나머지는 증가) 등으로 구현할 수 있다.

장점: 별도의 중앙 제어 회로 없이 bus line만으로 구현 가능
단점: 느리고 arbitration 동안 bus 사용이 제한됨 → transaction과 arbitration 병렬 수행 불가능

Replicated Arbiter는 각 module에 arbiter 복사본을 배치하고 request 신호를 모든 복사본에 전달하는 방식이다. reset 시 모든 복사본은 동일한 상태에서 시작하며, 같은 입력으로 동일한 grant를 생성한다. 단, 다음과 같은 단점이 있다:

• 버스 라인 수와 로딩 증가
• State replication 문제 발생 가능 (soft error, 동기화 문제로 grant 충돌 발생 위험)
  → 이 문제를 방지하려면 복잡한 동기화 로직이 필요함

22.3 고성능 Bus Protocol

22.3.1 Bus Pipelining

앞서 본 그림 22.7에서처럼 arbitration 대기 시간 동안 bus가 idle 상태가 되면 성능이 저하된다. 특히 shared-memory multiprocessor처럼 거의 모든 transaction에 대해 arbitration이 필요한 경우 문제는 더 심각해진다. 이 경우 bus transaction의 각 phase를 pipeline으로 구성해 bus의 duty factor를 높일 수 있다.

그림 22.10은 memory write와 memory read transaction에 대한 pipeline sequence 및 reservation table을 보여준다.

• 위쪽: cycle 순서
• 왼쪽: 사용되는 자원
• 진한 음영: 해당 cycle에서 독점 사용
• 옅은 음영: 공유 가능

(a) Memory Write Transaction

• Cycle 1: AR (arbiter request)
• Cycle 2: ARB (arbitration decision)
• Cycle 3: AG (grant)
• Cycle 4: RQ (request),
• Cycle 5: ACK (acknowledge)

(b) Memory Read Transaction (memory latency = 1 cycle)

• Cycle 1~3: AR, ARB, AG
• Cycle 4: RQ (read request)
• Cycle 5: P (processing, memory access)
• Cycle 6: RPLY (reply)

→ pipeline 구조 덕분에 각 phase가 중첩 실행되어 bus 사용률이 향상된다.

AG cycle은 arbitration 결과로 grant가 요청자에게 전달되는 cycle이다. Arbitration이 끝난 후, read transaction은 다음과 같이 구성된다:

• RQ: 주소를 memory module로 전송
• P: memory access 수행
• RPLY: 데이터를 요청자에게 반환

Reservation table은 각 cycle 동안 어떤 자원이 사용 중인지 나타낸다.

• 진한 음영: 해당 cycle 동안 transaction이 독점적으로 사용하는 자원
• 옅은 음영: 여러 transaction이 동시에 사용할 수 있는 자원 (ex. arbitration, request 등)

Reservation table은 다음과 같은 간단한 규칙을 제공한다:
고정 지연을 가진 transaction은 그 reservation table이 독점 자원을 이미 다른 transaction이 점유하고 있지 않은 어떤 cycle에서도 시작할 수 있다.

→ 예시:

• read transaction은 한 cycle 간격으로 시작할 수 있으나, 세 번째 read는 두 cycle을 기다려야 함
• write transaction은 read 이후 최소 세 cycle을 기다려야 시작할 수 있음

그림 22.11은 pipelined bus에서 6개의 transaction(read 4개, write 2개)을 실행한 timing을 보여준다.

• unpipelined bus에서는 34 cycle이 걸리지만
• pipelined bus에서는 arbitration latency가 완전히 숨겨지며, 총 17 cycle에 완료된다.
• Read 4의 P cycle 동안 Read 5가 RQ를 issue하는 것처럼 reservation 충돌이 없는 경우 병행 가능

그러나 read 후 write가 나오는 경우 pipeline 구조 mismatch로 인해 idle cycle이 발생한다. 예를 들어 Write 2는 Read 1의 RPLY와 충돌하지 않기 위해 cycle 7까지 대기해야 한다.
→ 가변 지연이 있는 transaction이 포함될 경우 상황은 더 악화된다. 예: read의 P cycle이 0~20까지 걸릴 수 있다면, 그 동안 bus는 idle 상태가 된다.

22.3.2 Split-Transaction Buses

이러한 idle 문제는 transaction을 둘로 나누고 그 사이에 bus를 arbitration에 개방함으로써 해결할 수 있다. Split-transaction bus는 request와 reply 사이가 길고 가변적인 경우, bus 자원을 보다 효율적으로 사용하기 위해 사용된다.

그림 22.12는 Figure 22.11과 동일한 transaction sequence를 split-transaction으로 구성한 예다.
각 transaction은 다음과 같이 둘로 나뉜다:

1. RQ 메시지를 보내는 transaction
2. RPLY 또는 ACK 메시지를 보내는 transaction

예: Read 1은 cycle 4에서 RQ 전송 후 종료되고, Rply 1이 cycle 8에서 응답

• 이 구조에서 arbitration은 3 cycle이 걸리므로, request와 응답 사이 최소 지연은 4 cycle
• Latency는 증가하지만, waiting 동안 bus를 계속 사용할 수 있으므로 utilization은 극대화

그림 22.13은 transaction delay가 가변적인 경우의 이점을 보여준다.
(a) pipelined bus: 요청 후 응답을 위해 bus를 예약해야 하므로 다음 transaction이 대기해야 함
(b) split-transaction bus: RQ A 이후 RP A까지 대기 시간 동안 RQ B, C 및 그 응답을 병렬로 수행 가능

→ 단, 같은 cycle에 RP A와 RP C가 준비된다면 arbitration을 통해 한 쪽이 우선 처리되고 나머지는 대기

Split-transaction bus는 응답이 어떤 요청에 대한 것인지 식별하는 메커니즘이 필요하다.

• 일반 bus는 timing으로 응답을 식별하지만
• split-transaction bus는 응답 순서가 임의적이므로
• 각 request에 고유한 tag를 부여하고, 응답 메시지에도 해당 tag를 포함해 매칭해야 함

예:

• Sequent Symmetry: 요청자가 arbitration을 이기면 tag를 중앙 pool에서 받아 사용
• SCSI: tag는 source address, destination address, sequence number로 암묵적으로 구성됨

22.3.3 Burst Messages

Bus transaction은 arbitration, addressing, acknowledgment 등 고정 오버헤드가 존재하며, 단일 word 전송일 경우 payload보다 오버헤드가 클 수 있다 (100% 이상).

→ 이 오버헤드를 줄이기 위한 방법: burst message, 즉 여러 word를 하나의 메시지로 묶어 전송

그림 22.14는 burst mode 메시지의 효율성 향상을 보여준다.
(a) 단일 word 전송: 3 cycle 중 2 cycle이 오버헤드 → 효율 1/3
(b) 4 word 전송: 총 6 cycle 중 4 word 전송 → 효율 2/3
(c) 8 word 전송이면 효율은 8/(8+2) = 4/5

일반화: 오버헤드 x cycle, 데이터 n word 전송 시 효율 = n / (n + x)

→ 그렇다고 무조건 burst size를 크게 하면 안 된다.

• Burst size가 커질수록 high-priority requester의 대기 시간이 길어짐
• 예: 256-word burst이면 대기 시간이 258 cycle로 증가 → 많은 application에서 불가능

해결책:

• 일부 bus는 **burst 중단(interrupt)**과 재개(resume) 또는 **재시작(restart)**을 지원
• 예: 메시지 A(8-word burst)를 메시지 B가 중단하고, 이후 A가 재개됨
  • A 재개 시 tag로 해당 message임을 식별해야 함
  • 중단된 메시지가 여러 개일 경우 이 tag는 필수
  • 경우에 따라 메시지를 처음부터 재시작할 수도 있음

그림 22.15는 interruptible burst message의 예를 보여준다 (이후 페이지에서 등장).

그림 22.15: Burst interrupt and resume
Message A가 전송 중에 Message B에 의해 중단되고, 이후 다시 재개됨.

• 메시지를 abort하고 처음부터 다시 시작하는 방식은 중복된 데이터 전송으로 인해 성능을 떨어뜨릴 수 있다.
• 긴 메시지를 중단하는 것은 긴 패킷을 여러 flit으로 나누는 것과 유사하다.
  → 고우선순위 패킷이 전체 패킷 전송을 기다릴 필요 없이 채널 대역폭을 할당받을 수 있다.
  → 차이점: flit은 매번 overhead를 가지지만, bus message는 실제로 interrupt될 때만 resume overhead가 발생한다.

22.4 Bus에서 Network로의 전환

기존에는 bus로 수행되던 많은 통신 작업이 이제 network로 이전되고 있다.
→ 일부 설계자는 bus의 특성을 point-to-point network에서 재현하려 한다.

복제하기 쉬운 특성: 모든 module이 공통 interface를 사용하는 구조
복제하기 어려운 특성: 모든 transaction의 직렬화(serialization), 전체 module에 대한 broadcast

예: Peripheral Component Interconnect (PCI) 버스는

• 다양한 컴퓨터와 주변기기가 모듈화된 방식으로 상호운용할 수 있게 해 줌

Network에서도 Chapter 20에서 설명한 것처럼 공통 interface를 제공하지만,

• 표준화는 미비함 → 최근 PCI-Express, Infiniband, Fibre Channel Switched Fabric 등의 등장으로 점점 확산 중

문제:

• On-chip bus는 RC delay 문제로 인해 큰 단일 전기 노드로 구현 불가
  → 전기적 제약으로 인해 shared medium 사용이 어려움

해결책:

• OR network 기반 논리적 bus (그림 22.16): 각 module의 출력이 OR되어 하나의 신호로 병합
  • 단, linear OR chain과 repeater chain은 delay가 큼 → tree network로 개선 가능 (Exercise 22.5 참고)

Broadcast & Serialization 유지 시도:

• 예: snooping cache-coherence protocol
• 256-bit wide bus로 cache line을 병렬 전송 (대용량 전송은 빨라지지만, 여러 address cycle을 동시에 처리 못함)
  → 해결책: 여러 parallel bus 사용
  • ex) 4개의 parallel address bus를 운영
  • 순서 보장을 위해 낮은 index의 bus가 먼저 도착한 것으로 간주
  • 단점: 충돌 감지를 위한 logic이 선형 이상으로 증가 → 고비용

궁극적 해결:

• bus semantics 포기, network로 전환
  • broadcast가 필요한 경우에만 multicast 또는 분산 트리 사용
  • serialization이 필요한 경우, 특정 노드를 통해 모든 메시지를 전달해 순서 보장
  • → 관련된 메시지만 직렬화하고 나머지는 병렬 처리 가능

예: directory-based coherence를 사용하는 대규모 shared memory 시스템은 일반적인 interconnection network 기반에서 동작함

22.5 PCI Bus 사례 연구

가장 널리 사용되는 버스 중 하나는 PCI Bus이다.

• 임베디드 시스템부터 서버까지 다양한 시스템에서 사용
• 이 장에서 설명한 여러 bus 특성을 종합적으로 갖춤

PCI 특징:

• Synchronous bus, Multiplexed address/data line, Pipelined arbitration
• 32-bit / 64-bit 지원
• 33MHz / 66MHz / 133MHz
• 최고 성능: 64-bit at 133MHz → 1 GByte/s burst 가능

표 22.2: 주요 PCI 신호선 설명

예: 두 word PCI read transaction (그림 22.17)

• Cycle 1: FRAME# assert, AD에 주소, C/BE에 memory read 명령
• Cycle 2: IRDY# assert되지만 TRDY#는 아직 → 전송 안됨 (idle)
• Cycle 3: TRDY# assert됨 → IRDY# & TRDY# 둘 다 활성 → 1st word 전송
• Cycle 4: TRDY# 유지, IRDY#는 비활성 → 대기
• Cycle 5: IRDY# 재활성화 → 2nd word 전송
• Cycle 6: FRAME#과 IRDY# 모두 비활성 → transaction 종료
• Cycle 7: 다음 master가 transaction 시작 가능

Write transaction은 read와 유사하나

• data cycle 동안 initiator가 AD를 구동
• turnaround idle cycle 불필요

그림 22.18: PCI bus arbitration pipelining

• Cycle 1: module 1, 2가 동시에 REQ# assert
• Cycle 2: arbiter가 module 1에 GNT1# assert
• Cycle 3: module 1이 FRAME# assert 후 transaction 시작
• Cycle 4: arbiter는 GNT1# 비활성화, GNT2# 활성화 → 다음 master에게 grant

그림 22.17: PCI bus read transaction

• Cycle 1: initiator가 FRAME#을 assert하고 주소와 명령어(memory read)를 AD 및 C/BE에 제공
• Cycle 2: IRDY#는 assert되지만 TRDY#는 아직 → 전송 없음 (turnaround idle)
• Cycle 3: target이 TRDY# assert 및 데이터 전송 → 첫 번째 word 전송
• Cycle 4: target은 데이터 제공, IRDY#는 비활성 → 대기
• Cycle 5: IRDY# 재활성화 → 두 번째 word 전송
• Cycle 6: FRAME#과 IRDY# 모두 비활성화 → transaction 종료

그림 22.18: PCI bus arbitration

• Cycle 1: module 1과 2가 각각 REQ# assert
• Cycle 2: arbiter가 module 1에 GNT# 부여
• Cycle 3: module 1이 FRAME#을 assert하며 transaction 시작
• Cycle 5: FRAME#과 IRDY# deassert → transaction 종료
• Cycle 6: module 2가 FRAME#을 assert하며 다음 transaction 시작

PCI transaction은 split되지 않는다.

• Read transaction은 요청과 응답을 포함
• 단, latency가 긴 경우 bus 점유 방지를 위해 delayed transaction을 허용
  • target은 요청 정보를 latch한 후 TRDY# 대신 STOP#을 assert하여 transaction을 abort
  • initiator는 나중에 retry

→ delayed transaction은 split transaction과 유사하지만, 효율이 떨어지며 예외적인 경우에만 사용

PCI는 module 초기화를 위한 protocol 포함

• 일반 address cycle 외에, IDSEL이라는 radial select signal로 slot 번호 기반 addressing 수행
• 이를 통해 module의 configuration register를 read/write 가능
• 초기화 과정:
  • controller가 module type을 파악하기 위해 register 읽음
  • 이후 address와 옵션을 설정하기 위해 configuration register에 write

22.6 문헌 주석

Bus의 기원은 1940~50년대 초기 컴퓨터까지 거슬러 올라간다.

• Digital의 Unibus 이후 peripheral interface의 표준으로 자리 잡음
• 현대 예시: PCI bus, SCSI bus

1960~1980년대: 대부분의 미니/마이크로컴퓨터는 bus로 CPU와 memory 연결
→ 현대 PC는 north-bridge chip을 통한 point-to-point 연결로 대체됨

흥미롭고 고성능인 예:

• Rambus의 DRDRAM bus: high-bandwidth DRAM 연결
• Sonics의 on-chip network: point-to-point 연결로 OR-tree 구조 bus 실현
• Sun Ultra Enterprise 10,000: point-to-point 기반의 다중 address bus 사용
  → 이 사례들은 bus보다 network를 사용하는 이유를 뒷받침함

추가 정보: The Digital Bus Handbook에서 bus 기술에 대해 더 자세히 설명됨

22.7 연습문제

22.1 Multiplexed vs. Non-multiplexed bus 설계

• 모든 transaction은 32-bit 주소와 4-bit control 포함
• Read: 70%, 32-bit data를 slave → master
• Write: 30%, 32-bit data를 master → slave (주소 전송과 동시에 가능)
• 전체 40개 bus line 사용 가능
  → throughput 극대화 설계를 하라 (multiplexed 및 non-multiplexed 고려, pipelined 구조 가정)

22.2 Early win 분산 arbitration 최적화

• Figure 22.9의 분산 arbitration은 b비트 address일 때 b cycle 소요
• 일부 경우 더 빠르게 끝낼 수 있는 최적화 방법 제시
• i개의 module이 무작위로 요청할 때의 평균 arbitration 시간 시뮬레이션 (0 < i ≤ b, b=8)

22.3 Reply bus 분리된 pipelined bus

• Figure 22.11의 transaction을 reply bus가 별도로 존재하며 arbitration도 독립인 시스템에서 timing diagram 작성
• 처리 속도 비교

22.4 Bus에서의 Virtual channel

• 메시지를 flit 단위로 나누고 각 flit에 virtual channel tag를 추가
• 대형 메시지가 짧은 고우선 메시지에 의해 interrupt될 수 있게 함
  → flit size에 따른 오버헤드 vs. 최대 대기 시간 그래프 작성
  (최대 메시지: 64KB, VC: 8개)

22.5 Tree 기반 bus 구조

• Figure 22.16의 point-to-point OR bus를 tree로 재구성해 delay 최소화
• 조건:
  • chip 크기 12mm x 12mm
  • module: 2mm 정사각형
  • 2mm마다 repeater 필요
  • 2mm 이동 및 1 gate 통과 시 시간 = 1 단위
    → 36개 module로 구성 시 linear vs. tree 구조의 최대 latency 비교

22.6 Split-transaction 버스에서의 reply ordering 시뮬레이션

• tag를 쓰지 않고 request 순서에 따라 reply 순서를 고정하는 구조 비교
• transaction delay는 1~Tmax 사이 균등 분포
  → tagged vs. ordered-reply bus의 평균 latency 비교 시뮬레이션

Figure 22.17: PCI bus read transaction
Cycle 1: initiator가 FRAME#을 assert하고, AD에 주소를, C/BE에 명령어(memory read)를 출력함
Cycle 2: IRDY#는 assert되었지만, TRDY#는 아직 비활성 상태 → 데이터 전송 없음 (turnaround)
Cycle 3: target이 TRDY#를 assert하고 첫 번째 데이터를 전송함 → IRDY#와 TRDY# 모두 assert되어 전송 발생
Cycle 4: 두 번째 데이터는 준비되었지만, IRDY#는 아직 비활성 → 전송 지연
Cycle 5: IRDY#가 assert되어 두 번째 데이터 전송 완료. 이 cycle에서 FRAME#도 deassert되어 마지막 data cycle임을 의미
Cycle 6: FRAME#과 IRDY#가 모두 deassert되어 transaction 종료됨

Figure 22.18: PCI bus arbitration
Cycle 1: module 1과 module 2가 각각 REQ1#과 REQ2#를 assert
Cycle 2: arbiter가 GNT1#을 assert하여 module 1에 bus master 권한 부여
Cycle 3~5: module 1이 transaction 수행
Cycle 5 종료 시 FRAME#과 IRDY#가 deassert되어 transaction 종료가 signal됨
Cycle 6: module 2가 이를 감지하고 FRAME#을 assert하여 새로운 transaction 시작

PCI의 주요 특징 요약

• PCI는 split transaction을 지원하지 않는다. 한 read transaction에 요청과 응답이 모두 포함된다.
• 단, long latency operation 중 bus 점유를 방지하기 위해 abort 및 retry 메커니즘을 제공함
  → target은 요청 정보를 latch한 뒤, TRDY# 대신 STOP#을 assert하여 transaction을 중단
  → initiator는 나중에 transaction을 retry (PCI 용어로 delayed transaction이라 함)

Delayed transaction은 bus 점유 최소화 측면에서 split transaction과 유사하지만, 효율이 떨어지며 예외적 경우에만 사용됨

초기화 프로토콜

• 일반적인 AD bus를 통한 address 지정 외에 IDSEL(radial select signal)을 사용한 slot 기반 module 선택이 가능
• Configuration read/write cycle을 통해 module의 구성 레지스터를 접근할 수 있음
  → 예: module 종류를 식별하고, 주소 설정 및 옵션 구성

22.6 문헌 주석

Bus는 등장 시점을 특정하기 어려울 만큼 오래되었으며, 1940~50년대의 초기 컴퓨터에서도 사용되었다.

• Digital의 Unibus 이후 peripheral interface의 표준 구조가 되었다.
• PCI와 SCSI는 현대적인 예시
• 1960~80년대: 대부분의 minicomputer와 microcomputer는 memory를 CPU에 연결할 때 bus를 사용
• 현재는 north-bridge chip을 통한 point-to-point 연결로 대체

현대 예시

• Rambus의 DRDRAM bus: 고대역폭 DRAM 연결
• Sonics의 on-chip network: OR-tree 방식의 point-to-point bus 실현
• Sun Ultra Enterprise 10,000: point-to-point 방식으로 bus 구성 + 다중 address bus 사용

→ 네트워크 방식이 bus보다 성능, 비용, 확장성에서 유리함을 잘 보여줌

추가 정보는 The Digital Bus Handbook 참고

22.7 연습문제

22.1 Multiplexed vs. Non-multiplexed bus 설계

• 모든 transaction은 32-bit 주소 + 4-bit 제어 신호 필요
• Read: 전체 transaction의 70%, slave → master로 32-bit data 전송
• Write: 나머지 30%, master → slave로 32-bit data 전송 (주소와 동시에 전송 가능 시 그렇게 함)
• 전체 bus line 수: 40개
  → 최대 throughput을 갖는 bus 설계 제안 (multiplexed / non-multiplexed, pipelined 구조 가정)

22.2 Early win 분산 arbitration 최적화

• Figure 22.9의 방식: b비트 address일 경우 b cycle 필요
  → 일부 경우 더 빠르게 끝낼 수 있는 방법 제시
  → i개의 module이 무작위로 요청할 때 (0 < i ≤ b, b = 8), 평균 arbitration 시간 시뮬레이션 및 그래프화

22.3 Reply bus가 분리된 pipelined bus의 timing 분석

• Figure 22.11의 transaction 시퀀스를, 응답을 위한 별도 bus와 arbitration이 존재한다고 가정하고 timing diagram 작성
  → 처리 속도 비교

22.4 Bus에서의 Virtual channel 개념 분석

• 메시지를 flit 단위로 나누고 각 flit에 virtual-channel tag 부여
• 고우선순위 짧은 메시지가 대형 메시지를 interrupt할 수 있음
  → flit size를 함수로 하여 overhead와 최대 대기 시간 그래프 작성
  (가정: 최대 메시지 64KB, virtual channel 8개)

22.5 Tree 기반 bus 지연 비교

• Figure 22.16의 point-to-point 기반 bus를 tree 구조의 OR-network와 repeater chain으로 개선
• 조건:
  • chip 크기 12mm², module 크기 2mm²
  • 2mm마다 repeater 또는 logic gate 필요
  • wire 2mm + gate 1개 = 1 단위 시간
    → 36 module 구성 시 linear vs. tree 구조에서 최대 latency 비교

22.6 Split-transaction 버스에서의 tagged vs. ordered reply 시뮬레이션

• Tag 사용 없이 요청 순서를 따라 응답 순서를 고정
  → 응답은 위치 기반으로 식별됨
• transaction delay는 1~Tmax 사이 균등 분포
  → tagged bus vs. ordered-reply bus의 평균 latency 비교 시뮬레이션 수행

다수의 interconnection network 응용은 높은 신뢰성과 가용성을 요구한다. 대형 병렬 컴퓨터는 interconnection network가 수천 시간 동안 packet 손실 없이 동작해야 한다. Internet router는 소량의 packet 손실은 허용될 수 있지만, router 자체는 연간 5분의 다운타임만 허용되는 99.999%의 가용성을 유지해야 한다. I/O system 역시 유사한 가용성 요건을 가진다.

Interconnection network는 일반적으로 수백 개(또는 수천 개)의 구성 요소—router, channel, connector—로 구성되며, 이들은 전체적으로 봤을 때 응용이 요구하는 것보다 높은 고장률을 가진다. 따라서 이러한 network는 오류 제어(error control)를 사용하여 구성 요소의 일시적 또는 영구적인 고장에도 불구하고 운영을 중단하거나 packet을 손실하지 않고 계속 동작할 수 있어야 한다.

21.1 적을 알라: 고장 방식과 fault 모델

오류를 다루는 첫 번째 단계는 구성 요소 고장의 본질을 이해하고, 이를 통해 고장을 분석하고 처리 방법을 논의할 수 있도록 단순한 모델을 개발하는 것이다. 시스템에서 발생할 수 있는 고장을 고장 방식(failure mode)이라 부른다. 고장 방식은 오류의 물리적인 원인을 의미한다. channel의 Gaussian noise, connector의 부식, 냉땜(cold solder joint) 불량, power supply 출력 드라이버의 open, 알파 입자(alpha-particle) 충돌, chip 내 도체의 전자이동(electromigration), 소자의 문턱 전압(threshold voltage) 변화, 잘못된 모듈 제거, 소프트웨어 오류 등이 그 예다.

이러한 고장 방식은 대개 복잡하고 난해하기 때문에, 우리는 해당 고장 방식의 관련 동작만을 묘사하고 대부분의 불필요한 복잡성을 숨기는 간단한 fault model을 개발한다. 표 21.1은 interconnection network에서 흔히 발생하는 고장 방식의 일부를 보여준다. 또한 각 고장 방식의 일반적인 고장률 값도 함께 제시한다. Gaussian noise나 alpha-particle 충돌과 같은 일부 고장은 일시적(transient) 오류를 유발하며, 이는 한두 개의 비트에 오류를 발생시키지만 시스템 동작에는 영구적인 영향을 주지 않는다. 반면 connector 고장이나 도선의 electromigration 등은 모듈의 영구적인 고장을 일으킨다.

일시적 고장은 일반적으로 bit-error rate (BER) 또는 soft-error rate (SER)로 모델링한다. 이러한 수치는 단위 시간당 오류 발생률(s⁻¹)을 가지며, 이 값의 역수는 오류 사이의 시간 간격을 의미한다. 한편, 영구적 고장은 stuck-at fault 모델로 모델링되며, 이는 어떤 논리 노드가 logic 1 또는 0에 고정되었다고 가정한다. 다른 영구 고장은 fail-stop fault로 모델링되며, 이는 구성 요소(예: link 또는 router)가 동작을 멈추고 인접한 모듈에 자신이 서비스를 중단했음을 알리는 것이다. 이러한 고장은 평균 고장 간격(mean-time between failures, MTBF)으로 표현되며, 시간 단위(보통 시간 또는 failures in 10⁹ hours, 즉 FITs)로 나타낸다. 설계 시 stuck-at fault나 지나치게 잦은 일시적 고장을 fail-stop fault로 전환하는 방식도 고려된다. 예를 들어, channel은 자체 동작을 모니터링하다가 오류를 감지하면 스스로 fail-stop 상태로 전환할 수 있다.

표 21.1 일반적인 interconnection network의 고장 방식과 fault 모델

처음 표 21.1에 나온 오류율을 보면 매우 작아 보이지만, 대형 시스템에서는 이 수치들이 누적되어 상당한 수준이 된다. 예를 들어, 1,024개의 노드를 가진 3차원 torus 네트워크에서 10 Gbits/s의 channel을 사용하고, 각 channel의 BER이 10⁻¹⁵인 경우를 보자. 처음엔 10⁻¹⁵이라는 수치가 매우 작게 느껴지지만, channel 속도인 10¹⁰ bits/s와 곱하면 channel 당 오류율이 10⁻⁵ errors/s가 된다. 이 시스템에는 총 6,144개의 channel이 있으므로 전체 오류율은 6 × 10⁻² errors/s, 즉 16초마다 한 번의 오류가 발생한다. BER이 10⁻²⁰으로 더 낮은 경우라도 전체 오류율은 6×10⁻⁷로, 한 달에 약 2건의 오류가 발생한다. 이러한 오류의 영향을 잘 제어하면, 이러한 link로도 매우 신뢰성 높은 시스템을 구축할 수 있다.

일부 고장은 Byzantine 형태인데, 이는 시스템이 작동을 멈추는 대신 악의적인 방식으로 동작을 계속하면서 protocol을 위반하여 인접 모듈을 고장나게 하려는 동작이다. Byzantine 고장은 처리하기 매우 어렵고, 실제로는 드물다. 이를 방지하기 위해 시스템을 스스로 점검하는 기능을 갖추고, 문제가 있는 모듈이 이상 동작을 하기 전에 셧다운되도록 설계한다. 소프트웨어 고장도 때때로 Byzantine 동작을 보일 수 있지만, 이 또한 하드웨어 고장처럼 실행을 감시하고 불변 조건을 위반할 경우 중단시킴으로써 처리할 수 있다.

전원공급 장치, 냉각 팬, 클럭 생성기 등의 구성 요소 고장은 여분(redundancy)과 현장 교체(field replacement)를 통해 처리한다. 전원공급 장치는 여유 전원을 확보하여 하나가 고장나도 나머지로 동작을 유지할 수 있도록 하고, 고장 여부는 모니터링 하드웨어로 쉽게 감지되어 교체할 수 있도록 한다. 냉각 팬도 N + 1 방식의 redundancy를 사용한다. 전역 클럭이 필요한 시스템에서는 여러 개의 클럭을 분산 배치하고, 클럭 고장이 감지되면 각 모듈이 스스로 다른 클럭으로 전환하여 PLL을 통해 안정적인 클럭을 제공한다. 이후 이 장에서는 전원, 냉각, 클럭 등 인프라는 좋은 엔지니어링 관행으로 잘 처리되었다고 가정하고, link와 router의 고장에 집중한다.

표 21.1에 제시된 고장률은 구성 요소의 수명 대부분 동안의 평균적인 고장률이다. 많은 구성 요소는 초기와 말기에 훨씬 높은 고장률을 보이며, 이는 그림 21.1의 배스타브 곡선(bathtub curve)에 나타나 있다. 초기에는 일부 불량한 부품이 몇 시간 이내에 고장나는데, 이를 infant mortality라 한다. 몇 백 시간 동안 정상적으로 동작한 부품은 그 이후부터는 비교적 일정한 고장률을 보이다가 수명이 다할 무렵 다시 고장률이 높아진다. infant mortality를 제거하기 위해 burn-in 과정을 거쳐 부품을 일정 시간(그리고 스트레스 환경 하에서) 동작시켜 불량 부품을 걸러낸 후 시스템에 탑재한다. wearout을 방지하기 위해 수명이 짧은 부품은 일정 시간이 지나기 전에 교체한다. 예를 들어, router chip은 시스템에 탑재하기 전에 고온, 고전압, 고속 환경에서 100시간 burn-in을 실시하며, 10년 수명을 가진 디스크 드라이브는 5년 후에 교체한다.

이후부터는 21.2절 "오류 제어 과정"과 21.3절 "Link 수준의 오류 제어"에 대한 내용입니다:

21.2 오류 제어 과정: 검출, 격리, 복구

모든 오류 제어는 다음 세 가지 기본 단계로 구성된다: 검출(detection), 격리(containment), 복구(recovery).

문제를 해결하기 위해 가장 먼저 해야 할 일은 문제가 존재함을 인식하는 것이다. interconnection network에서는 이것이 오류 검출 단계에 해당한다. 예를 들어, flit의 패리티(parity)나 check character를 확인함으로써 channel에서의 bit 오류를 감지할 수 있다. 오류나 고장을 검출한 이후에는 오류가 퍼지지 않도록 격리해야 한다. 예를 들어, 오류가 flit 내 virtual channel identifier를 손상시켰다면, 잘못된 virtual channel의 상태가 업데이트되는 것을 막아야 한다. 마지막으로, 오류 제어의 세 번째 단계는 오류로부터 복구하고 정상 동작을 재개하는 것이다. 예를 들어, bit 오류가 발생했다면 flit을 다시 전송하여 복구할 수 있다. 이 재전송은 link 수준이나 원래 송신자로부터 수행될 수 있다.

21.3 Link 수준의 오류 제어

대부분의 interconnection network는 오류 제어를 계층적으로 수행한다. 물리적인 link 수준에서 시작하여 router, network, system 또는 end-to-end 수준까지 이어진다. link 수준에서는 link 논리가 link 오류를 가려서 처리하거나(지연이 추가될 수 있음), 마스킹할 수 없는 경우 link를 종료(fail-stop)시켜 오류를 제어한다. link의 양 끝에 위치한 논리 모듈은 협력하여 link 상의 bit 오류를 검출, 격리, 복구한다. 치명적인 오류가 발생하면 link 논리는 해당 오류를 우회하도록 link를 재구성하거나 link를 종료시킨다.

21.3.1 Link 모니터링

link 수준에서의 오류 검출은 ECC(error control code)를 사용하여 link에 중복 정보를 추가하는 방식으로 수행된다. 단순한 parity로는 단일 bit 오류를 검출할 수 있지만, 대부분의 link는 CRC(cyclic-redundancy check)를 사용하며, 이때 CRC의 길이가 충분하면 다중 bit 오류가 검출되지 않을 확률은 극히 낮다. n-bit CRC는 n개 미만의 비트를 포함하는 오류는 모두 검출하고, 2ⁿ분의 1 확률로 나머지 오류를 검출하지 못할 수 있다.

오류 검출은 flit, packet, multipacket frame 등 다양한 크기로 수행될 수 있다. frame처럼 큰 단위로 검사하면 효율적이지만, 오류가 발생한 사실을 frame 전체를 받은 후에야 알 수 있어 격리에 불리하다. frame-level CRC가 오류를 검출할 때쯤이면, 이미 해당 오류는 여러 channel을 지나며 router들의 내부 상태를 손상시켰을 수 있다. 이를 방지하기 위해 많은 router들은 flit마다 검사하고, 특히 중요한 header 정보는 flit 전체를 받기 전에 별도로 보호하여 즉시 처리할 수 있도록 한다.

link 모니터링의 예로, 그림 21.2는 link 상의 bit 오류를 검사하기 위해 두 개의 CRC 필드를 포함한 flit 포맷을 보여준다. CRC1은 virtual-channel ID, flit type, credit 등 첫 cycle에서 수신되는 header 필드를 검사한다. CRC2는 flit 전체에 대한 CRC로, CRC1을 포함하여 검사한다. header에 대해 별도의 CRC를 제공하면, flit 전체가 도착하기 전이라도 해당 정보를 안전하게 사용할 수 있다. CRC1 필드에 문제가 없었더라도 CRC2에서 오류가 검출될 수 있기 때문에, 결과적으로 header 필드도 CRC2에 의해 더 강한 오류 검출 보호를 받게 된다.

link 모니터링은 연속적으로 수행되어야 한다. idle 상태인 channel을 검사하지 않으면 오류가 오랫동안 잠복하다가 다음 flit이 도착했을 때 드러날 수 있다. link가 idle인 경우에는 임의의 데이터를 담은 idle flit을 전송하여 link를 지속적으로 테스트해야 한다. 또는 flit 기반 검사 외에 frame 기반 검사 방식도 병행할 수 있다.

21.3.2 Link 수준의 재전송

오류가 검출되면 link 논리는 다음 단계인 격리를 수행해야 한다. 대부분의 link 오류는 router 논리에 노출되지 않도록 오류를 마스킹함으로써 격리된다. 마스킹은 오류를 격리하고 복구하는 두 가지 작업을 동시에 수행한다. 오류가 있는 flit을 재전송하는 것이 가장 단순한 마스킹 방법이다. 마스킹은 FEC(forward error-correcting) code를 사용하는 방법으로도 수행할 수 있다. FEC를 사용하면 보호 단위(보통 flit)에 충분한 정보를 담아 오류를 감지할 뿐만 아니라 수정도 할 수 있다. 하지만 round-trip latency가 짧은 interconnection network에서는 재전송 방식이 더 단순하고, 적은 오버헤드로 더 많은 오류를 수정할 수 있어 일반적으로 선호된다.

그림 21.3은 간단한 재전송 시스템을, 그림 21.4는 그 타이밍을 보여준다. 송신기는 flit을 전송할 때마다 transmit flit buffer에 사본을 저장하고, 수신 확인(ACK)이 올 때까지 유지한다. 일반적으로 switch output speedup을 위해 output buffer를 사용하는 구현에서는, transmit flit buffer는 output buffer와 결합되어 사용된다.

송신기가 각 flit을 전송할 때마다, 해당 flit은 작은 transmit flit buffer에 저장된다. 오류가 감지되면 이 buffer에서 해당 flit을 다시 전송하여 오류를 마스킹한다. 각 flit에는 식별을 위해 일반적으로 transmit flit buffer 내 주소와 같은 태그가 붙는다. 수신기는 수신된 각 flit에 대해 오류를 검사하며, flit이 올바르게 수신되었을 경우 acknowledgment를 송신기에게 전송한다. 이 acknowledgment에는 어떤 flit에 대한 응답인지 나타내는 태그와 함께 수신 상태(정상 수신, 오류 수신, 무시됨)가 포함된다. acknowledgment를 받은 송신기는 해당 flit의 사본을 삭제한다. 오류가 발생한 경우 송신기는 멀티플렉서를 전환하여 해당 flit을 재전송한다. 대부분의 경우 오류는 일시적이므로, 재전송된 flit은 올바르게 수신된다.

물론 acknowledgment 자체도 오류 검사가 필요하며, 오류가 있을 경우 재전송되어야 한다. 이는 일반적으로 반대 방향으로 이동하는 flit에 acknowledgment를 piggyback하는 방식으로 처리되며, flit의 일부라도 오류가 있으면 전체 flit을 재전송한다.

실제로는 오류가 발생한 하나의 flit만 재전송하면 되지만, 이는 channel 상의 flit 순서를 어지럽혀 router의 입력 논리를 복잡하게 만든다. 예를 들어 body flit이 head flit보다 먼저 수신될 수 있다. 이러한 복잡성을 피하기 위해, 오류가 발생한 지점부터 buffer에 있는 모든 flit을 다시 전송하는 방식이 더 간단하다. 이때 새로운 flit이 도착하면 flit buffer의 끝에 추가된다. 송신 포인터가 buffer의 끝에 도달하면, 멀티플렉서를 전환하여 switch에서 직접 flit을 전송하게 된다.

그림 21.4의 타이밍 다이어그램은 이러한 재전송의 예를 보여준다. 송신기는 flit을 보낼 때마다 수신기로부터 acknowledgment 또는 오류 알림을 받는다. flit 2가 전송 중 손상된다. 수신기는 flit 2의 CRC를 검사하여 오류를 감지하고, 송신기에게 오류를 알린다. 송신기는 오류 알림을 받기 전까지 flit 3~6을 계속 전송하며, 수신기는 이 flit들을 무시한다. 이후 송신기가 오류를 인지하면 전송을 flit 2부터 되돌리고, 그 이후 모든 flit을 다시 전송한다. 수신기는 재전송된 flit 2를 받은 시점부터 다시 정상 동작을 시작한다. 수신기의 관점에서는 단지 flit 5개만큼 지연되었을 뿐이며, 오류는 마스킹된다.

transmit flit buffer는 세 개의 포인터로 관리된다. 오류가 없을 경우 transmit 포인터와 tail 포인터는 FIFO transmit queue에서 head와 tail 포인터처럼 동작한다. 새로운 flit은 tail 포인터 위치에 추가되고, transmit 포인터 위치부터 flit이 전송된다. router가 switch로부터 직접 전송 중일 경우 transmit 포인터와 tail 포인터는 동일 위치를 가리킨다. 하지만 FIFO와 달리, flit이 전송되었다고 해서 해당 위치를 즉시 재사용할 수는 없다. 해당 flit이 acknowledgment를 받을 때까지 buffer에 유지되어야 한다. acknowledgment 포인터는 아직 acknowledgment를 받지 않은 가장 오래된 flit을 나타낸다. acknowledgment를 수신할 때마다 acknowledgment 포인터가 전진하며, buffer 한 칸이 해제된다. 오류 알림을 받으면 transmit 포인터는 acknowledgment 포인터 위치로 되돌아간다.

21.3.3 Channel 재구성, 성능 저하, 종료

격리(containment) 과정의 한 측면은 문제가 있는 구성 요소가 계속해서 트래픽에 영향을 미치지 않도록 차단하는 것이다. channel에서 오류가 반복되거나, 예상보다 높은 BER을 보일 경우 channel의 일부가 치명적인 고장을 겪었을 가능성이 높다. 이러한 지속적인 오류를 감지하기 위해 각 channel에는 오류 카운터가 존재하며, 해당 channel의 오류율을 추적한다. 오류율이 임계값을 넘으면 해당 channel은 고장으로 판단되어 서비스에서 제외된다. 예를 들어, 기대하는 오류율이 초당 10⁻⁵ errors (하루에 약 1건)인 channel에서 10⁴초(약 3시간) 동안 10건 이상의 오류가 기록되면 해당 channel은 고장으로 간주되어 종료된다. 이러한 BER 모니터링 및 고장 판단은 일반적으로 network 구성 요소 상태를 주기적으로 점검하는 supervisor 소프트웨어에 의해 수행된다.

일부 멀티비트 channel은 예비 신호선(spare bit)을 포함하여 하나의 비트에 문제가 생겼을 때 channel을 재구성할 수 있다. 이러한 channel에서 치명적인 오류가 감지되면, 진단 절차를 통해 어느 비트가 고장났는지 파악한 후 해당 비트를 우회하여 channel을 재구성할 수 있다.

그림 21.6은 예비 비트 1개를 포함한 8비트 channel의 예이다. 송신기와 수신기에 위치한 2:1 멀티플렉서 8쌍을 통해 d0d7의 데이터를 9개의 신호선 s0s8 중 동작 가능한 8개에 실어 보낼 수 있다. 예를 들어 s3에 문제가 생기면, 송신기는 d3d7을 왼쪽으로 한 칸씩 밀어 s4s8을 통해 전송하고, 수신기에서 이를 다시 되돌린다.

일부 channel은 예비 비트를 제공하지 않지만, channel의 정상적인 신호선을 사용하는 방식으로 전송 속도를 낮춰 재구성할 수 있다. 예를 들어 8비트 channel의 신호선 중 1개가 고장나면 나머지 7개 신호선을 사용하여 원래 속도의 7/8로 계속 전송할 수 있다. 이러한 재구성은 graceful degradation의 예이며, 첫 번째 비트가 고장났다고 해서 channel 전체를 정지시키지 않고, 대역폭만 점진적으로 줄여나간다. 심지어 hard bit 오류 발생 시 link가 fail-stop 방식으로 동작하더라도, network 수준에서 graceful degradation을 적용할 수 있다.

channel이 재구성될 수 없는 경우에는 해당 channel을 종료시켜 오류를 fail-stop으로 축소하며, 오류 제어는 다음 계층인 network 수준에서 수행된다. 종료 당시 transmit flit buffer에 있는 flit들은 입력 컨트롤러로 반환되어 다른 경로로 재전송되거나 폐기된다.

패킷이 고장 난 channel을 경유하던 중 분리(split)될 경우 문제가 발생한다. head flit은 여러 hop 아래쪽에 있고, tail flit은 고장 난 channel의 위쪽에 남아있을 수 있다. 고립된 tail flit은 head flit에 포함된 라우팅 정보를 참조할 수 없기 때문에 목적지를 알 수 없으며 폐기해야 한다. 더 심각한 문제는 head flit이 tail 없이 계속 전파되는 경우이다. 이 head flit은 경로상 virtual channel들을 점유하면서 목적지까지 이동한다. 이때 해당 virtual channel을 필요한 다른 패킷은 진행할 수 없게 된다. 이런 자원을 회수하기 위해서는 입력 컨트롤러는 고장 난 channel에 연결된 각 virtual channel이 아직 packet 전송 중이었다면 tail flit을 합성하여 전송한다. 고장으로 인해 분리되어 폐기된 packet은 end-to-end 오류 제어(21.6절)를 통해 복구할 수 있다.

21.4 Router 수준의 오류 제어

일부 고장 방식은 link 오류를 유발하지만, 다른 고장 방식은 router에 일시적 또는 영구적인 오류를 발생시킨다. 이러한 router 오류는 channel 상의 bit 오류보다 빈도는 낮지만, 신뢰성 높은 대규모 시스템을 구축하기 위해 반드시 제어되어야 한다. link 오류처럼 router 오류도 검출, 격리, 복구의 원칙을 따른다.

router 오류는 router 논리를 복제하고, cycle마다 대표적인 신호를 exclusive-OR 방식으로 비교하여 가장 쉽게 검출할 수 있다. 한 쪽 복제본은 master로서 주 출력 신호를 생성하고, 다른 하나는 shadow 복사본으로서 동일한 입력을 받지만 출력은 비교를 위한 용도로만 사용된다. checker는 두 복사본의 출력과 내부 신호를 비교한다. 두 모듈의 출력만 비교하는 것은 많은 오류를 제때 검출하지 못하므로 충분하지 않다. 많은 오류는 router의 내부 상태만 손상시키고, 출력에는 수천 cycle 후에야 드러나기 때문이다. 이를 단순화하기 위해 master와 shadow는 수천 개의 내부 신호 및 모듈 출력을 exclusive-OR로 압축하여 소수(예: 32개)의 compressed state line을 만든다. checker는 이 compressed line을 비교하고, 내부 신호 하나라도 다르면 오류로 감지된다.

router 내부 메모리나 버스에서 발생하는 오류는 ECC로 검출할 수 있다. 메모리와 버스에서는 주로 SECDED(Single Error Correcting, Double Error Detecting) 코드가 사용되며, n비트 메모리나 버스에는 log₂(n) + 1개의 check bit를 추가하여 보호한다. 메모리 오류를 마스킹하기 위해서는 주기적으로 메모리를 sweep하여 각 위치를 읽고 단일 bit 오류를 수정해야 한다. 오류가 발생한 직후에 이를 검출하고 수정함으로써 두 번째 오류가 발생하여 복구 불가능한 상태가 되기 전의 위험을 줄일 수 있다.

router 오류는 일관성 검사(consistency check)를 통해서도 검출된다. 예를 들어 protocol 일관성 검사에서는 head flit 사이에 적어도 하나의 tail flit이 존재해야 한다는 조건을 확인한다. credit 일관성 검사에서는 channel의 수신 측 입력 컨트롤러와 송신 측 출력 컨트롤러가 buffer 가용량에 대해 일치된 값을 갖고 있는지를 점검한다. 상태 일관성 검사에서는 현재 input controller나 virtual channel의 상태에 맞는 입력이 들어왔는지를 확인한다. 이러한 조건이 위반되면 오류로 간주되고 격리 조치가 필요하다.

오류가 검출되면 해당 router 또는 오류가 발생한 router 일부(예: input controller)를 중지시켜 격리할 수 있다. 구성 요소를 중지시키면 오류를 fail-stop으로 바꾸어 인접 router의 상태가 손상되는 것을 막는다. 이를 위해 router를 fault-containment region으로 나눈다. 보통 input controller는 각각 독립적인 fault-containment region이며, router 전체는 더 상위의 fault-containment region으로서, allocator나 공통 논리에서 오류가 검출되었을 때 router 전체가 중지된다.

오류가 일시적이면, 해당 router 또는 input controller는 상태를 초기화한 뒤 재시작할 수 있다. 이 경우 해당 구성 요소를 지나던 packet은 link 고장 시처럼 폐기된다. 재시작 중인 구성 요소는 인접 모듈들과 상태를 동기화해야 한다. 예를 들어 router가 재시작할 때는 인접 router마다 control flit을 보내 channel을 재설정하고, credit 수치를 초기화해야 한다.

영구적 오류가 발생한 경우 해당 구성 요소는 재시작할 수 없고 교체되어야 한다. 신뢰성 있는 설계를 위해 시스템이 동작 중에도 고장난 모듈을 교체할 수 있도록 하는 방식(hot swapping)을 도입한다. 대부분의 경우 router 같은 능동 구성 요소는 이런 방식으로 교체가 가능하다. 다만 교체 단위(field replaceable unit, FRU)는 보통 router 단위보다 클 수 있다. 예를 들어, 4개의 router가 하나의 PCB(card)에 실려 있다면, 하나의 router만 고장나더라도 전체 카드(4개 router)를 교체해야 한다.

field 교체의 대안으로는 시스템에 충분한 여분(router, channel 등)을 미리 포함시켜 전체 수명 동안 요구되는 성능을 확보하는 방법이 있다. 이 방법은 field servicing이 어려운 위치(예: 우주)에서 시스템이 배치될 때 유리하다.

21.5 Network 수준의 오류 제어

network 수준은 link 수준에서 시작한 오류 제어 계층에서 다음 단계이다. 이 수준에서는 link와 router 고장을 fail-stop link와 router로 모델링하며, packet은 이러한 고장난 구성 요소를 우회해야 한다. network 수준 오류 제어는 adaptive routing을 이용하면 가장 쉽게 구현된다. service에서 제외된 link는 adaptive routing 기능에서 제외되며, 모든 packet은 나머지 가용 link를 통해 전송된다.

network 수준 오류 제어는 table 기반 oblivious routing을 통해서도 실현 가능하다. 고장 직후에는 routing table을 그대로 사용하여 전송을 시도하며, 고장 link가 포함된 경로를 선택한 packet은 폐기되거나 local rerouting된다. local rerouting은 고장난 link(예: 동쪽)를 건너뛰기 위해 (북→동→남) 등의 대체 hop을 선택하는 것이다. 이후 routing table은 고장 link를 피하도록 재계산된다.

21.6 End-to-End 오류 제어

link 또는 router 고장 격리 도중에 packet이 폐기되었을 경우, end-to-end packet 재전송 방식으로 복구할 수 있다. 이 방식은 link 수준의 flit 재전송과 유사하나, packet 단위로 source부터 destination까지 전체 경로를 따라 재전송이 이루어진다는 점이 다르다.

재전송을 위해 송신 노드는 전송한 각 packet의 복사본을 유지하며, acknowledgment가 도착할 때까지 이를 보관한다. acknowledgment가 일정 시간 내에 도착하지 않거나, negative acknowledgment가 수신될 경우 재전송이 발생한다. acknowledgment가 올 때까지 이 과정은 반복되며, 성공적으로 수신되면 해당 packet 복사본은 폐기되어 transmit packet buffer의 공간이 해제된다.

이 방식에서는 destination이 동일한 packet을 두 번 수신하는 경우도 발생할 수 있다. 예를 들어, 재전송이 일어난 직후에 acknowledgment가 지연되어 도착하는 경우가 이에 해당한다. 이러한 중복 packet은 packet에 serial number를 부여하고, 각 노드가 마지막 T flit 간격 동안 수신한 일반 packet과 재전송 packet 리스트를 유지함으로써 탐지 및 폐기할 수 있다. 재전송 packet은 header의 특정 비트로 식별되며, 그 serial number가 일반 리스트에 있으면 중복으로 간주된다. 일반 packet은 재전송 리스트와 비교한다. 일반 리스트 확인은 비용이 크므로 드물게 수행되고, 재전송 리스트 비교는 대부분 1~2개 이내이므로 비용이 적다.

이처럼 end-to-end packet 재전송이 network, router, link 수준 오류 제어 위에 계층적으로 쌓이면 interconnection network는 임의의 수준까지 신뢰성을 높일 수 있다. 물론 interconnection network의 client (예: processing node, network line card, I/O device) 역시 고장의 대상이 되지만, 이러한 장치에도 동일한 신뢰성 설계 원칙을 적용할 수 있다. 예를 들어 서로 다른 terminal에 연결된 중복 client를 통해 전체 시스템 신뢰성을 확보할 수 있다.

Interconnection network와 network client 사이의 interface는 interconnection network의 성능에 중대한 영향을 미칠 수 있다. 잘 설계된 network interface는 사용자에게 투명하게 동작하여, network가 제공하는 최대 대역폭과 최소 latency를 활용할 수 있게 한다. 하지만 많은 interface는 이처럼 투명하지 못하다. 설계가 미흡한 interface는 throughput 병목을 유발하거나 network latency를 크게 증가시킬 수 있다.

이 장에서는 세 가지 유형의 network interface에 관련된 이슈를 간략히 살펴본다.

• Processor-network interface는 메시지를 memory로 복사하거나 I/O 인터페이스를 거치는 병목 없이 processor에서 network로의 고대역폭 경로를 제공해야 한다.
• 성공적인 인터페이스는 processor의 오버헤드를 최소화하며, 오작동하는 프로세스가 network를 비활성화하지 못하도록 보호 기능도 갖추어야 한다.
• Shared-memory interface는 processor와 memory controller를 interconnection network를 통해 연결하는 데 사용된다. 단순한 원격 memory 접근부터 복잡한 cache coherence protocol까지 다양한 형태가 있다. 이 경우, remote memory access의 핵심 경로에 위치하기 때문에 latency가 특히 중요하다.
• Line-card interface는 외부 network 채널과 switching fabric으로 사용되는 interconnection network를 연결한다. 주된 기능은 queueing과 packet scheduling이다. 입력 라인과 fabric 사이, 그리고 fabric과 출력 라인 사이에 queue가 존재한다. 일반적으로 각 output subport 및 packet class 조합마다 입력 queue를 제공하여, 하나의 subport로 향하는 packet이 다른 subport로 향하는 packet을 막지 않도록 하며, 낮은 우선순위 클래스의 packet이 높은 우선순위 packet을 차단하지 않도록 한다. 이들 queueing 시스템은 성능뿐만 아니라 안정성 측면에서도 고려가 필요하다. 출력 측에서는 fabric의 속도(일반적으로 speedup이 존재)를 출력 라인의 속도에 맞추며, 다양한 traffic class에 대해 rate shaping을 수행할 수 있다.

20.1 Processor-Network Interface

많은 interconnection network 응용은 네트워크에 연결된 processor 간의 메시지 전달을 포함한다. Message-passing parallel computer의 network는 명백히 이에 해당하지만, 대부분의 I/O network나 packet switching fabric도 I/O 장치 또는 line interface에 연결된 processor 간의 메시지 전달을 포함한다.

Figure 20.1에서는 processor node P1부터 PN까지 메시지를 주고받는 구조를 보여준다. 실제 응용에서 메시지 길이는 bimodal한 분포를 보이며, 약 32바이트의 짧은 메시지는 요청 또는 제어 용도(예: 디스크 섹터 x 읽기)에 사용되고, 1KB 이상의 긴 메시지는 데이터 블록 전달에 사용된다. 짧고 긴 메시지 모두에서 latency와 throughput이 중요하지만, 특히 짧은 메시지의 throughput을 확보하는 것이 가장 어렵다.

효율적인 message-passing interface는 두 가지를 충족해야 한다.

1. 낮은 오버헤드로 network 접근 가능해야 하며
2. 오류가 있는 프로세스가 다른 프로세스에 영향을 주지 못하도록 보호되어야 한다.

접근 경로는 latency가 낮아야 하며, 짧은 메시지를 수 사이클 내에 전송할 수 있어야 한다. 또한 memory interface와 같은 저대역폭 병목 지점을 통과하지 않도록 설계해야 한다. 일반적으로 message를 memory를 통해 복사하지 않고 직접 전송하는 것이 latency와 bandwidth 병목을 피하는 데 유리하다.

네트워크 인터페이스 설계에서 중요한 것은 processor node의 어느 지점에 연결하느냐이다. Figure 20.2는 typical processor node를 보여준다. processor chip은 register file과 on-chip cache memory를 가지고 있으며, DRAM memory 및 I/O 장치들과 bridge chip을 통해 연결된다. Network interface는 이 중 어느 지점에든 연결될 수 있다.

가장 효율적인 network interface는 processor의 internal register에 직접 연결된다. 이렇게 하면 processor register 또는 cache에서 직접 작은 메시지를 구성할 수 있어 off-chip memory interface를 거치지 않아 latency가 줄어든다. 하지만 대부분의 network interface는 기존 구성요소의 변경이 가장 적은 I/O 버스에 연결된다. 이 방식은 메시지를 interconnection network와 memory 사이에서 전달하며, modern processor에서 외부 버스 싸이클을 발생시키는 데 30 cycle 이상 소요되므로 상당한 latency가 발생한다. 또한 메시지의 모든 word가 양 끝에서 memory interface를 두 번 통과해야 하므로 memory bandwidth를 과도하게 점유하게 된다. 이러한 I/O 기반 인터페이스는 일반적인 주변장치 인터페이스와 유사하므로 이후에는 다루지 않는다.

20.1.2 Register-Mapped Interface

Register-mapped 인터페이스는 Figure 20.4에 나타난 것처럼 processor의 register에 메시지를 구성한 후, 시작 register와 마지막 register를 지정하는 단일 send 명령으로 메시지를 atomic하게 전송한다. 이 방식은 메시지가 중간에 끊겨 network에 남겨질 수 없으므로 안정성(safety) 측면에서 안전하다. 그러나 이 방식은 긴 메시지를 보내지 못하게 제한되며, 긴 메시지를 segment로 나누어야 하고, 일반-purpose register를 많이 사용하게 되어 register pressure를 유발하며, 여전히 processor가 DMA engine 역할을 수행해야 하는 단점이 있다.

20.1.3 Descriptor-Based Interface

Figure 20.5에 제시된 descriptor 기반 메시지 전송 방식은 register-based 방식의 한계를 극복한다. 이 방식에서는 processor가 dedicated message descriptor register에 메시지를 구성한다. 이 register 세트는 메시지 descriptor의 working set을 저장할 수 있을 만큼 충분히 크다.

각 descriptor는 다음 중 하나를 포함할 수 있다:

• 메시지에 삽입될 즉시값(immediate value)
• processor register에 대한 참조
• memory 블록에 대한 참조

Figure에 보이는 메시지 예시는 이 세 가지 descriptor 타입을 모두 포함한다.

이 descriptor 기반 메시지 전송 방식은 안전(safe) 하며, register interface에서 processor가 수행해야 했던 오버헤드를 제거한다. 본질적으로 processor의 오버헤드를 co-processor가 대신 처리하면서 descriptor를 순차적으로 읽고 메시지를 구성한다.

20.1.4 Message Reception

안전하고 processor의 오버헤드 없이 메시지를 수신하려면, 수신 전용 co-processor나 multi-threaded processor에서의 별도 thread를 사용하는 것이 가장 효율적이다. 메시지 수신 thread는 단순한 메시지는 직접 처리하고, 복잡한 메시지는 사용자 thread에 전달하기 위해 queue에 저장한다. 예를 들어, 공유 memory 접근과 같은 일반적인 메시지 유형은 전용 하드웨어가 효율적으로 처리할 수도 있다.

이 수신 인터페이스는 안전하며, 수신 thread가 항상 유한 시간 내에 메시지를 수신하도록 설계되었기 때문에, network 상의 메시지가 무기한 남아 있는 일이 없다.

20.2 Shared-Memory Interface

Shared-memory multiprocessor 시스템에서는 processor에서 memory로 가는 메시지를 전달하기 위해 interconnection network를 사용한다. 예를 들어, Cray T3E와 같이 원격 캐싱이 허용되지 않는 시스템에서는 메시지가 단순한 read/write 요청 및 응답으로 구성된다. 반면, SGI Origin 2000과 같이 remote data의 coherent caching을 지원하는 시스템에서는 cache coherence protocol을 구현하기 위한 더 많은 유형의 메시지가 필요하다.

이러한 시스템에서는 두 개의 network interface가 필요하다:

• processor-network interface: processor의 load/store 명령에 따라 메시지를 생성함 (예: cache miss 또는 cache line eviction)
• memory-network interface: network로부터 메시지를 수신하고, 요청된 작업을 수행한 후 응답 메시지를 보냄

일반적으로 shared-memory 처리 노드에서는 이 두 인터페이스가 동일 위치에 있고 network injection/extraction port를 공유하지만, 기능적으로는 구분된다. Shared-memory multiprocessor에서의 latency는 매우 중요하기 때문에, 이러한 인터페이스는 processor나 memory 이벤트에 대한 요청 메시지를 몇 클럭 사이클 내에 inject할 수 있도록 최적화되어 있다.

20.2.1 Processor-Network Interface

Figure 20.6은 processor-network interface의 단순화된 블록 다이어그램이다.

• processor가 load/store 명령을 수행하면, memory request register (Req Reg)에 요청을 기록한다.
  • 요청은 요청 유형(read/write, cacheable/uncacheable 등), 접근할 물리 주소, write일 경우에는 data를 포함한다.
  • 각 요청은 tag를 가지고 있어 응답이 돌아왔을 때 processor가 이를 식별할 수 있다.
• 우선 요청은 cache에 전달된다.
  • cache에 데이터가 있으면 요청은 cache에서 수행되고, 요청된 데이터(read인 경우)가 memory reply register에 저장된다.
  • cache miss가 발생하면 **MSHR(miss-status holding register)**에 요청이 게시되고, 그 상태가 초기화된다.
• 단순한 시스템(원격 캐싱 불가)에서 read 요청이 발생하면 MSHR 상태는 pending read로 설정된다.
  • 이후, 메시지 송신 블록은 read request 메시지를 생성하여 목적지 노드로 전송하고, 상태를 read requested로 갱신한다.
  • 이 과정에서 memory 주소를 network 주소(노드 번호)로 변환하는 단계가 필요할 수 있다.
• network는 결국 read reply 메시지를 되돌려주며, 메시지의 주소 필드는 해당 데이터를 기다리고 있는 MSHR을 식별하는 데 사용된다.
  • 매칭되는 MSHR은 데이터와 함께 상태가 read complete로 갱신되며, 순차적으로 processor reply register로 전달된다.
  • processor는 tag를 통해 데이터를 올바른 위치로 보낸다.
  • 처리된 요청은 status가 idle로 갱신되어 다음 요청을 처리할 준비가 된다.
• Uncacheable write의 경우는 read와 거의 동일하지만, 데이터가 요청 메시지에 포함되며 응답 메시지에는 포함되지 않는다.
  • 동일 주소에 대기 중인 요청이 있을 경우, write를 두 번 전송해야 하며, 두 write가 순서대로 처리되도록 보장하는 메커니즘이 필요하다.

MSHR는 outstanding 요청에 대한 scoreboard 역할을 한다. 요청이 cache에서 miss되면 MSHR에 항목이 생성되고 상태가 초기화된다. 요청을 처리하는 agent들(protocol FSM과 message transmit block)은 MSHR 상태를 모니터링하며, 특정 상태에서 동작이 필요함을 감지하면 적절한 동작을 수행한다. 이 모니터링은 종종 status field의 one-hot encoding을 사용하고, 해당 상태 비트를 OR 연산하여 트리거된다.

MSHR은 동일 주소에 대한 여러 요청을 병합하는 기능도 한다. 동일 위치에 두 번째 read 요청이 발생할 경우, MSHR에 게시될 때 address match가 감지되어 중복된 read 메시지를 보내지 않게 된다. 첫 번째 요청에 대한 응답이 도착하면 동일 주소를 기다리는 모든 요청에 대해 응답을 만족시킨다.

MSHR의 수는 동시에 처리 가능한 memory 참조 요청 수를 결정한다. MSHR이 가득 차 있으면, 다음 cache miss 요청은 MSHR이 비워질 때까지 request register에서 stall된다. 일반적으로 MSHR 수는 4개에서 32개 사이이다. 더 많은 outstanding reference를 처리하기 위한 shared-memory network interface는 MSHR을 제거하고 요청 상태 전체를 메시지와 함께 전송하는 방식으로도 구성될 수 있다. 이 절에서는 MSHR 기반 인터페이스만 다룬다.

20.2.2 Cache Coherence

원격 데이터를 cache할 수 있고 coherence protocol을 사용하는 시스템에서는 기본적인 read/write 요청 처리와 유사하되 세 가지 주요 차이점이 있다.

1. 모든 작업은 cache line 단위로 수행된다. 예를 들어 read 요청은 전체 cache line을 읽어 로컬 cache에 저장한다.
2. 메시지 종류가 많다. 예를 들어, read-only 상태의 cache line을 요청하는 메시지와 read-write 상태를 요청하는 메시지가 구분되며, forwarding 및 invalidation을 위한 메시지도 추가로 필요하다.
3. 수신된 메시지에 반응하여 메시지를 전송해야 한다. processor 동작에 의한 요청뿐만 아니라, network로부터 수신된 coherence 메시지에 대응한 메시지 전송도 필요하다.

단순 coherence protocol에서는 다음과 같은 메시지를 processor가 전송한다:

• read request (read miss 시)
• read exclusive (write miss 시 cache line 획득)
• writeback (dirty line evict 시)
• forward (dirty cache line을 새로운 소유자에게 전달)
• invalidation acknowledgment (clean line invalidation 후 응답)

수신하는 메시지는 다음과 같다:

• read reply (read-only line 포함)
• forward (read-write line 포함)
• invalidation request (read-only line invalidation 요청)
• forward request (exclusive line 전달 요청)

각 수신 메시지는 기존 MSHR을 갱신하거나(예: read reply), 새로운 MSHR 항목을 생성한다(예: invalidation/forward request). MSHR의 status field는 protocol FSM과 message transmit unit을 트리거하여 응답 동작을 수행하게 한다. 예를 들어, invalidation 요청은 지정된 cache line을 무효화하고 완료 메시지를 전송해야 한다. forward 요청 역시 invalidation 후 cache line 데이터를 지정된 노드에 전송해야 한다.

Coherence 메시지는 전체 cache line을 포함한다. modern 시스템에서 cache line 크기는 8B(Cray X-1)부터 512B(IBM Power4 L2)까지 다양하며, 일반적으로 128B가 많이 사용된다. 전송은 816B 단위로 진행되며 총 816 cycle이 소요된다. latency를 줄이기 위해 메시지 전송은 pipelining되며, MSHR에서 header가 준비되는 즉시 inject되며, cache line은 word 단위로 읽는 즉시 network에 inject된다. 일부 protocol은 요청한 word를 먼저 전송하고 나머지는 wrapping 순서로 전송하여 latency를 최소화한다.

Cache-coherent system에서의 주요 설계 이슈는 occupancy이다. 이는 각 memory access가 system 자원을 얼마나 오래 점유하는지를 나타낸다. 잘 설계된 경우, cache, MSHR, 송수신 유닛은 memory access 당 한 cycle(또는 word 당 한 cycle)만 점유한다. 반면, coherence protocol을 software로 구현하는 경우 tens of cycles 이상 점유할 수 있으며 이는 throughput 병목으로 이어진다.

20.2.3 Memory-Network Interface

Figure 20.7의 memory-network interface는 processor-network interface로부터 요청 메시지를 수신하고 응답 메시지를 전송한다. 이 인터페이스 역시 낮은 latency를 목표로 최적화된다.

수신된 메시지는 **transaction status holding register (TSHR)**를 초기화하는 데 사용된다. 모든 TSHR이 사용 중일 경우, 작은 request queue가 요청 메시지를 임시 저장하여 네트워크로의 역류(backpressure)를 방지한다. 각 TSHR은 processor 측 MSHR과 유사하게 pending 상태인 memory transaction을 추적한다.

Memory bank controller들과 message transmit unit은 TSHR의 상태 변화를 모니터링하며, 해당 상태에 따라 적절한 동작을 수행한다. 각 memory bank는 요청된 read/write를 수행하며, TSHR의 data 필드와 memory bank 간에 데이터를 이동시킨다. transaction이 완료되면 message transmit unit이 응답 메시지를 구성하고 전송한다.

예를 들어, non-cacheable read 요청의 경우:

• TSHR은 status를 read pending으로 설정하고 주소 및 source 노드를 기록한다.
• 해당 주소의 bank-select bit에 맞는 memory bank가 유휴 상태가 되면 접근이 시작되고, status는 bank activated로 변경된다.
• 데이터가 반환되기 두 cycle 전, status는 read complete로 변경되어 message transmit unit을 트리거한다.
• 이때 message header가 source node를 대상으로 inject되고, 이어지는 word들이 memory bank에서 network로 직접 전송되어 응답 메시지를 완성한다. 완료 후 TSHR은 idle로 표시된다.

만약 요청이 단순한 read/write이고 순서를 유지할 수 있다면, TSHR을 제거하고 간단한 queue나 bank별 queue로 대체할 수 있다. 이 경우:

• 요청이 queue의 헤드에 도달하면, 해당 memory bank가 유휴 상태가 될 때까지 대기한다.
• 이후 요청이 시작되어 pending request queue로 이동하며, memory 작업이 완료되면 해당 요청과 매칭된다.
• message transmit unit이 정보를 사용해 응답 메시지를 생성한다.

Queue는 TSHR보다 구현이 간단하고 비용이 적게 들지만, 복잡한 protocol이 요구하는 동작은 지원하지 못한다.

Cache-coherent 요청의 경우, TSHR은 protocol 메시지 사이에서 transaction 상태를 유지한다.

예: read-exclusive 요청

• 요청은 TSHR 항목을 생성하고 status를 read-exclusive directory pending으로 설정
• Directory unit이 요청된 cache line의 현재 상태를 판별
• Line이 shared 상태면, status는 read pending 및 invalidate pending으로 설정되며, 공유 노드 리스트와 개수가 TSHR에 기록
• read pending에 의해 memory bank 접근 시작
• invalidate pending에 따라 invalidate 메시지가 순차적으로 전송되며, 각 전송 후 count 갱신
• 모든 invalidate 전송 후 status는 awaiting invalidate reply로 변경
• 응답이 모두 수신되면 status는 invalidate complete로 변경
• read도 완료되었으면 응답 메시지 전송이 트리거됨

20.3 Line-Fabric Interface

Packet switch 또는 router에서 interconnection network를 switching fabric으로 사용할 경우, 해당 network interface는 fabric 전후에 queueing 기능을 제공해야 한다. Figure 20.8과 같이 입력 및 출력 queue가 필요하다.

입력 queue는 출력 포트 간 간섭 방지를 위한 것이다. 특정 출력 A가 일시적으로 혼잡할 경우, A로 향하는 패킷 때문에 모든 입력이 멈추는 것은 바람직하지 않다. Packet switch에서는 입력으로 들어오는 패킷을 차단할 수 있는 backpressure 메커니즘이 없으므로 결국 drop된다.

이를 방지하기 위해, 입력 측에서는 출력 포트별로 virtual output queue를 제공한다. A가 혼잡하더라도 다른 출력으로 가는 패킷은 그대로 진행할 수 있다. 실제 구현에서는 포트뿐만 아니라 각 subport 및 트래픽 class 조합마다 queue를 제공하여, low-priority traffic이 high-priority traffic을 막지 않도록 설계한다.

Figure 20.8에 보이듯, packet router나 switch는 interconnection network 앞뒤에 packet queueing 기능이 필요하다. 입력 queue는 network로 전송될 packet을 저장하고, 출력 queue는 외부 라인으로 나갈 packet을 보관한다.

출력 측에서는 또 다른 queue 집합이 필요한데, 이는 fabric이 보통 speedup을 가지기 때문이다. 즉, interconnection network에서 line card로의 bandwidth는 line out보다 크다. 출력 측에는 subport × class 당 하나의 buffer만 필요하지만, 출력 buffer는 일반적으로 상당히 크다. 왜냐하면 어떤 응용에서는 출력 노드에서 수 밀리초(예: 10ms) 이상 일시적 과부하가 발생할 수 있기 때문이다.

예를 들어, 256개의 line card가 있고 각 card는 20 Gbit/s 용량을 가지며 8개의 2.5 Gbit/s subport로 구성되어 있다고 하자. line card는 4개의 서비스 class를 정의하며, class 간에는 strict priority가 필요하다. 이 경우, 각 line card는 총 8K개의 입력 queue(256 포트 × 8 subport/포트 × 4 class)를 제공해야 한다. 출력 측에는 32개의 queue(8 subport × 4 class)만 필요하다.

일반적인 line card에는 입력 및 출력 경로 모두에 packet processing logic이 포함되어 있다. 이 logic은 packet을 다시 작성하거나 통계 카운터를 갱신한다. 이 동작은 fabric과의 interface와는 무관하며 여기서 더 이상 다루지 않는다.

일부 응용에서는 interconnection network와는 독립적으로 출력 queue 관리자에서 입력 queue 관리자까지 end-to-end flow control을 제공한다. 이는 Figure 20.8의 점선으로 표시되어 있으며, 일반적으로는 특정 입력 queue에서 packet의 흐름을 시작 또는 중단하기 위해 전용 control packet을 network를 통해 전송하여 구현된다.

낮은 우선순위의 packet이 높은 우선순위 packet을 방해하지 않게 하고, 혼잡한 출력 subport로의 트래픽이 같은 class의 다른 출력 subport로 가는 트래픽을 방해하지 않도록 하기 위해, interconnection network는 서로 다른 class 및 서로 다른 출력 subport로 향하는 packet에 대해 non-interfering해야 한다. 이를 달성하기 위한 단순하지만 강력한 방법은 **각 subport × class 조합마다 virtual network(즉, 각 physical channel에 대해 virtual channel 세트)**를 제공하는 것이다.

실제로, 입력 라인에서 packet이 도착하면, packet processor가 해당 packet을 분류하고 출력 포트를 지정한다. 그런 다음 입력 queue 관리자(traffic manager라고도 불림)가 적절한 입력 queue에 packet을 저장한다. 만약 해당 queue가 비어 있었다면, fabric scheduler에 요청을 보내게 되며, 이는 Figure 20.8의 queue 블록에 포함된 구성 요소이다.

fabric scheduler는 입력 queue와 interconnection network의 입력 포트 상태를 추적하며, 이를 기반으로 가장 높은 우선순위의 packet 중 현재 차단되지 않은 출력으로 향하는 packet을 선택하여 network에 삽입한다.

interconnection network는 입력 라인보다 높은 대역폭을 가지므로, 대부분의 입력 queue는 비어 있거나 매우 짧다. 출력이 차단된 경우에만 입력 queue가 눈에 띄게 커진다. 이러한 이유로, 대부분의 queue는 on-chip memory에 저장될 수 있어, packet을 off-chip memory에 기록하고 다시 읽는 데 필요한 전력 소모를 피할 수 있다.

Figure 20.9는 queue 관리자와 scheduler의 블록 다이어그램이다.

• queue 관리자는 상태 벡터 S, on-chip head/tail 포인터 h, t와 off-chip head/tail 포인터 H, T를 유지한다.
• 상태 벡터는 queue가 온전히 on-chip에 있는지 (h, t) 또는 tail이 off-chip에 있고 head만 on-chip에 있는지(H, T, h, t)를 나타낸다.

packet이 도착하면 queue 번호가 지정되며, 이 번호로 상태가 조회된다.

• 만약 off-chip 부분이 비어 있고 on-chip에 공간이 있다면, packet은 on-chip queue에 삽입된다.
• 그렇지 않으면 off-chip에 삽입된다.

모든 off-chip memory 접근은 여러 DRAM bank에 걸쳐 striping 되어 분산된다. 각 bank에는 읽기/쓰기 queue가 있으며, bank가 유휴 상태가 될 때까지 요청을 버퍼링한다.

queue 관리자가 packet을 삽입하는 동안, scheduler는 packet을 꺼낸다.

• scheduler는 비어 있지 않은 queue를 선택하고 on-chip queue에서 packet을 dequeue 한다.
• 모든 queue의 head는 on-chip에 있으므로, scheduler는 off-chip에서 직접 읽지 않는다.
• dequeue 이후, 해당 queue가 non-empty off-chip tail을 가지고 있고 on-chip 공간이 낮은 워터마크 이하로 떨어지면, off-chip → on-chip 전송 요청이 이루어진다.

이처럼 queue head는 on-chip, tail은 off-chip에 유지됨으로써 대부분의 경우 off-chip memory traffic은 거의 발생하지 않는다.

또한 memory bandwidth는 power와 핀 수 면에서 비싸기 때문에, packet은 line card로 들어오거나 나갈 때 한 번만 queueing 되는 것이 바람직하다. 이는 processor-memory interface에서 memory copy를 피하려는 원칙과 유사하다. 그러나 많은 router는 이 원칙을 따르지 않고, packet을 여러 번 queue에 저장한다:

• packet processor,
• traffic shaping을 수행하는 traffic manager,
• fabric scheduler 등에서 각각 queue가 발생할 수 있다.
  신중하게 설계하면, 동일한 기능을 단 한 번의 memory 쓰기/읽기로 구현할 수 있다.

20.4 사례 연구: MIT M-Machine Network Interface

M-Machine은 MIT와 Stanford에서 개발한 실험용 multicomputer로, on-chip multithreaded processor 간의 fine-grain communication 메커니즘을 검증하기 위한 시스템이다. M-Machine은 register-mapped network interface를 가진 2차원 torus interconnection network를 포함한다. 이 인터페이스는 message-passing과 shared-memory 모델 모두를 지원하며, 낮은 오버헤드의 통신을 제공하면서도 프로세스 간 격리와 안정성을 유지한다.

M-Machine은 2차원 torus 네트워크로 연결된 여러 processing node로 구성된다. 각 노드는 Multi-ALU Processor(MAP) 칩 기반이며, Figure 20.10에 도시되어 있다.
각 MAP 칩은 다음을 포함한다:

• 세 개의 64비트 multithreaded processor
• memory subsystem
• 2-D torus router
• network interface

MAP 칩 내의 각 processor의 동일 thread-slot에서 실행 중인 thread 간에는 register를 통해 효율적인 통신 및 동기화가 가능하다. 이 절에서는 특히 network interface에 초점을 맞춘다.

M-Machine에서는 메시지를 processor register에서 직접 구성하고, SEND 명령어를 통해 atomic하게 전송한다(20.1.2절 및 Figure 20.4 참조).

• 각 processor의 각 thread는 14개의 64비트 정수 레지스터와 15개의 64비트 부동소수점 레지스터를 가진다.
• thread는 register I4 또는 F4부터 시작하여 연속된 register에 메시지를 구성한 뒤, send instruction을 실행하여 메시지를 전송한다.

Figure 20.11은 M-Machine의 SEND 명령어 형식을 보여준다. 이 명령어는 다음의 4개 필드를 가진다:

• length: 메시지를 구성할 register 개수 (I4부터 시작)
• dest: 목적지 가상 주소를 담고 있는 register
• handler
• CCR

이 가상 주소는 이후에 실제 주소로 변환된다.

Figure 20.11에 나타난 SEND 명령어는 register 파일에서 I4(FSEND의 경우 F4)부터 시작하여 메시지를 구성하고 전송한다. 이 명령어는 다음을 지정한다:

• length: 메시지를 구성할 register 수
• dest: 목적지 가상 주소가 저장된 register
• handler: 수신 후 실행할 핸들러의 가상 주소
• CCR: 메시지 수신 후 true로 설정될 condition-code register

이 방식은 message-driven computation을 지원한다. CCR 필드를 통해 메시지가 network에 삽입되었는지를 나타내므로, 이후 명령어와 **오버랩된 실행(overlapping execution)**이 가능하다. 메시지가 삽입되기 전까지는 network 자원을 점유하지 않고, 모든 상태가 processor의 register에 존재하므로 프로세스 전환 시에도 안전하다. CCR이 설정되면, 메시지는 완전히 network input queue에 들어간 상태이며, deadlock 및 livelock이 없는 network 구조에 의해 목적지까지 전달될 수 있음이 보장된다. 이는 J-Machine에서 발생할 수 있는 partial message로 인한 blocking 문제를 해결한 방식이다.

하지만 한계점도 존재한다. MAP 칩의 register 파일이 작아(14개의 integer, 15개의 floating-point register), 메시지 길이가 최대 10~11개 word로 제한되고, 그 이상이면 register spilling이 발생하여 stack을 사용해야 한다. 따라서 더 큰 register 파일이 있다면 이 방식은 훨씬 더 효과적일 것이다.

시스템 수준에서의 deadlock-free를 보장하기 위해, M-Machine은 return-to-sender 방식을 사용했다. 각 노드는 반환 메시지 전용 버퍼를 유지하고, FS (Free Space) 카운터로 버퍼 여유 공간을 추적한다.

• 메시지를 보내기 전에 FS > L (L은 메시지 길이)을 확인하고 FS에서 L을 차감하여 공간을 예약한다.
• 메시지가 성공적으로 수신되면 수신 측에서 acknowledgment를 보내고, 이로 인해 FS는 L만큼 증가한다.
• 수신 측에서 메시지를 수신할 수 없으면, 해당 메시지는 반환 채널을 통해 전송자에게 되돌아가며, 전용 virtual channel 및 injection/extraction buffer를 사용하여 요청-응답 간 데드락을 방지한다.

Figure 20.12는 M-Machine의 메시지 수신 방식을 보여준다. 도착한 메시지는 두 개의 수신 queue 중 하나에 저장되며, 각각은 논리적 network 하나에 대응된다.

• 각 queue는 전용 thread slot에서 실행되는 수신 thread가 관리하며,
• I15(register 115)를 읽으면 다음 word를 읽고
• I16(register 116)을 읽으면 다음 메시지의 헤더를 건너뛰고 queue head를 다음 메시지로 이동시킨다.
• 아직 도착하지 않은 word를 읽으려 하면 해당 thread는 block된다.

수신 thread는 항상 메시지를 읽어야 하므로, 단기적이며 bounded한 연산만 수행할 수 있다. 이를 보장하기 위해 각 메시지의 handler IP는 시스템에서 검증된 안전한 pointer만 허용된다.

• 간단한 메시지(acknowledge, physical memory read/write 등)는 handler가 직접 처리하고
• 복잡하거나 오래 걸릴 수 있는 메시지는 시스템 queue에 넣고 다음 메시지를 처리하도록 한다.

M-Machine은 이 메시지 시스템 위에 shared memory 구현을 위한 특별한 지원도 제공하였다.

• memory 요청은 on-chip cache 및 local TLB(LTLB)를 먼저 확인한다.
• cache miss 또는 remote access가 필요한 경우, event queue에 요청 사유, 주소, 데이터, 응답을 받을 continuation 정보(register 및 thread ID)가 저장된다.
• 전용 event handler thread가 메시지 handler thread와 동일 방식으로 event를 처리한다.

예를 들어:

• event handler는 remote read를 위해 메시지를 전송한다(handler IP 포함)
• 원격 노드에서는 handler가 해당 주소를 읽고 응답 메시지를 전송
• 결과적으로 remote memory access 시간은 하드웨어 방식에 비해 약간 길 뿐이며, software 방식이기 때문에 다양한 coherence protocol 및 memory 정책을 실험할 수 있는 유연성을 제공한다.

20.5 서지 노트

초기의 대부분 processor-network 인터페이스는 I/O 버스에 연결되어 program transfer나 DMA로 메시지를 전송했다. Joerg와 Henry는 다양한 인터페이스 구조와 위치를 연구했다 [82].

• MARS accelerator는 송수신 모두에 two-register interface를 사용했다 [4]
• J-Machine은 register에서 메시지를 구성하고 send 명령어로 전송했지만, 수신은 local memory에 저장했다 [53]
• AP1000은 interface를 cache에 연결해 성능을 향상시켰다 [80]
• M-Machine은 register 연속 블록을 메시지로 전송하는 send 명령어를 구현했다 [112]
• SHRIMP multicomputer는 I/O attached processor-memory 인터페이스를 사용했고, address space 간 memory window mapping으로 overhead를 줄였다 [22, 23]
• Myrinet도 I/O attached 구조이며 protocol 처리를 위한 local processor가 포함되어 있다 [24]
• Berkeley NOW project [10]도 이러한 구조 기반 multicomputer 사례이다
• 이러한 I/O 기반 메시지 인터페이스는 Active Messages [189], Illinois Fast Messages [139] 같은 라이브러리와 함께 사용되기도 한다
• MSHR의 사용은 Kroft에 의해 처음 제안되었으며 [105],
• 네트워크 기반 shared-memory 시스템 중 초창기 구현으로는 DASH [115],
• 상용 시스템으로는 SGI Origin 2000 [108]이 있다.
• Shared memory MP는 Lenoski와 Weber의 저서 [116]에 정리되어 있다.
• On-chip/off-chip queue 분리는 U.S. Patent 6,078,565 [16] 및 Iyer et al. [87]에 설명되어 있다.

20.6 연습문제

20.1 메시지 인터페이스 오버헤드 비교
128비트 짧은 메시지와 32Kb 긴 메시지를 (a) two-register interface, (b) register-mapped interface, (c) descriptor-based interface로 전송할 때의 processor 오버헤드를 비교하라. 짧은 메시지는 register에, 긴 메시지는 memory에 있다고 가정.

20.2 Cache coherence protocol 설계
각 processor가 cache line을 invalid/shared/exclusive 상태로 가질 수 있는 coherence protocol에서, 각 상태에서 read 또는 write 요청이 발생했을 때의 메시지 전송 순서를 설명하라.

20.3 Two-register interface 보호
악의적인 thread가 two-register interface를 사용해 network를 무기한 점유할 수 있는 방법을 설명하고, 이 문제를 나타내는 간단한 코드 조각을 작성하라. 이를 방지할 방법도 제안하라.

20.4 Register-mapped interface로 긴 메시지 전송
64개의 general purpose register를 가진 processor에서 register-mapped interface(20.1.2절 참조)를 사용해, memory 버퍼에 있는 1,024-word 메시지를 전송해야 한다. 이를 수행하는 간단한 코드 조각을 작성하고, 오버헤드를 줄이는 방법을 제안하라.

20.5 Descriptor-based 메시지 포맷 구성
1,024-word의 memory buffer를 다른 노드로 전송하는 descriptor-based 메시지를 구성하라. 이 메시지는 다음을 포함해야 한다:

• 목적지 주소
• 메시지의 유형과 길이를 나타내는 헤더
• 데이터 본문

각 항목을 register 내용으로 표현하라.

20.6 단일 memory 기반 line-network interface
packet이 fabric의 출력 측 memory에만 저장되고, 입력 측에는 단지 100개의 packet을 담을 수 있는 작은 on-chip queue만 존재하는 line-network interface를 고려하자. 이 router는 128개의 line card를 지원해야 하며, 각 card는 4개의 traffic class를 처리한다. 또한 (비현실적이지만) 입력 트래픽이 출력 노드 전체에 균등하게 분포한다고 가정하자.
이러한 환경에서 작은 입력 queue에서 packet이 drop되지 않도록 보장하려면 어떻게 해야 할까? 해결 방안을 구상하라.