Network Interfaces

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되지 않도록 보장하려면 어떻게 해야 할까? 해결 방안을 구상하라.