Zeah Engineering Factory

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 비교 시뮬레이션 수행

Arbiter는 하나의 자원을 여러 요청자 중 하나에게 할당하는 반면, allocator는 여러 자원과 여러 요청자 간의 매칭을 수행한다. 각 요청자는 하나 이상의 자원을 요청할 수 있다. 예를 들어, 스위치의 다양한 출력 포트를 향해 여러 flit을 보유한 router 입력 유닛 집합을 생각해 보자. allocator에 대해서는 이미 17.2.2절에서 crossbar switch 할당을 설명할 때 소개한 바 있다. 매 cycle마다 switch allocator는 입력 유닛과 출력 포트 사이의 매칭을 수행해야 하며, 이때 각 입력 포트에서는 하나의 flit만 선택되고, 각 출력 포트로 향하는 flit도 하나만 선택되어야 한다.

19.1 표현 방식

n × m allocator는 n개의 m비트 벡터를 입력으로 받고, n개의 m비트 벡터를 출력으로 생성하는 유닛이다. 그림 19.1은 n = 4, m = 3인 allocator를 나타낸다. 입력 rij가 1로 설정되면 요청자 i가 자원 j를 요청하고 있음을 의미한다. 각 요청자는 동시에 여러 자원을 요청할 수 있다. router 설계에 사용되는 allocator에서는 요청자가 switch 입력이고 자원이 switch 출력인 경우가 많다. 따라서 일반적으로 요청자는 입력(input), 자원은 출력(output)이라 부른다.

allocator는 다음 세 가지 규칙에 따라 요청을 고려하고 grant 벡터를 생성한다.

1. gij가 1이면 반드시 rij도 1이어야 한다. 즉, 요청이 있어야만 grant가 주어진다.
2. gij가 1이면 같은 입력 i에 대해서는 다른 어떤 k ≠ j에 대해서도 gik는 0이어야 한다. 즉, 각 입력에 대해 최대 하나의 grant만 허용된다.
3. gij가 1이면 같은 출력 j에 대해서는 다른 어떤 k ≠ i에 대해서도 gkj는 0이어야 한다. 즉, 각 출력에 대해서도 최대 하나의 grant만 허용된다.

allocator는 요청 rij로 구성된 n × m 요청 행렬 R을 받아, grant gij로 구성된 grant 행렬 G를 생성한다고 볼 수 있다. R은 임의의 이진 값 행렬이고, G는 다음 조건을 만족하는 이진 값 행렬이다:

• 요청이 있는 곳에만 1이 있어야 하고 (규칙 1),
• 각 행에 1이 최대 한 개,
• 각 열에도 1이 최대 한 개 있어야 한다 (규칙 2, 3).

예를 들어 다음과 같은 요청 행렬 R과 두 개의 가능한 grant 행렬 G₁, G₂를 생각해 보자.

G₁과 G₂는 모두 위의 세 가지 규칙을 만족하기 때문에 유효한 grant 행렬이다. 그러나 G₂는 세 자원을 모두 입력에 할당했기 때문에 더 바람직한 grant 행렬이라 할 수 있다. G₂와 같이 가능한 최대 수의 할당을 포함하는 해를 maximum matching이라 부른다. G₁처럼 더 이상 요청을 수용할 수 없는 행렬은 maximum matching이 아닐 수 있다.

※ 주: 일부 응용에서는 요청 행렬 R이 정수값을 가질 수 있으며, 하나의 출력에 대해 다중 요청을 허용할 수 있다. 하지만 여기서는 그와 같은 경우는 고려하지 않는다.

매칭을 더 이상 추가할 수 없는 상태이면서도 현재의 grant를 제거하지 않고는 새로운 요청을 처리할 수 없는 경우, 이를 maximal matching이라고 한다.

G₁ 행렬은 좋은 매칭을 계산하기 어려운 예시를 보여준다. 예를 들어 첫 번째 행에서 g₀₀ grant를 설정하면, 더 이상 maximum matching은 불가능하다. 입력 2는 오직 자원 0만 요청하고 있기 때문에, 자원 0을 다른 입력에 할당하면 입력 2는 동작하지 못하게 된다. 또한 자원 1을 입력 0에 할당하면, 입력 1과 입력 2가 자원 0을 동시에 가질 수 없기 때문에 역시 maximum matching을 방해하게 된다. 이런 식으로, 하나의 잘못된 할당이 전체적으로 sub-optimal matching을 초래할 수 있다.

할당 문제는 bipartite graph 형태로도 표현할 수 있다. 그림 19.2(a)는 요청 행렬 R에 해당하는 bipartite graph를 보여준다. 이 방식에서는 할당 문제가 바로 bipartite matching 문제와 동일하다. 즉, 각 정점이 최대 하나의 엣지에만 연결되도록 하면서 가능한 많은 엣지를 선택하는 문제다. 그림 19.2(b)는 grant 행렬 G₂에 해당하는 그래프에서의 maximum matching을 나타낸다.

어떤 bipartite graph든지 maximum matching은 시간 복잡도 O(P²․⁵)로 계산할 수 있다 (P는 포트 수). 일반적으로 maximum-size match를 계산하려면 backtracking이 필요하다. 즉, 일시적으로 grant를 설정했다가 나중에 제거해야 할 수도 있다. 하지만 switch allocator나 virtual channel allocator는 이 정도의 복잡도를 감당할 수 없고, backtracking이 필요한 알고리즘은 pipeline 구현이 어렵다. 보통 할당을 수행할 수 있는 시간이 단 하나의 cycle, 또는 몇 개의 cycle에 불과하므로, 실제로는 maximal matching을 목표로 하는 것이 현실적이다. 그러나 maximal matching조차도 비용이 클 수 있기 때문에, 실제 하드웨어 allocator는 빠르지만 근사적인 해를 제공하는 단순한 heuristic을 사용하는 경우가 많다.

19.2 Exact Algorithms

정확한 maximum matching은 대부분의 router 응용에서는 시간 제약 때문에 현실적으로 불가능하지만, 오프라인 계산이 가능할 때도 있다. 또한 새로운 heuristic을 평가할 때 기준점으로 사용할 수 있도록 정확한 maximum matching이 필요할 수도 있다. 이런 경우에는 sub-maximum matching을 반복적으로 개선해 가는 방식으로 계산할 수 있다.

이때 사용하는 augmenting path algorithm은 Clos 네트워크의 스케줄링에 사용했던 반복 알고리즘과 유사하다 (6.11절 참조). 우선 초기에는 sub-optimal matching M으로 시작한다. 이 매칭을 기반으로 residual graph를 만든다. 이 residual graph는 원래의 bipartite graph와 노드와 엣지는 같지만 방향이 지정된다. 현재 매칭 M에 속한 엣지는 출력에서 입력 방향 (오른쪽 → 왼쪽)으로 향하고, 매칭되지 않은 엣지는 입력에서 출력 방향 (왼쪽 → 오른쪽)으로 향한다.

그 다음, augmenting path를 찾는다. augmenting path는 매칭되지 않은 입력에서 시작하여 매칭되지 않은 출력까지 이어지는 방향 있는 경로이다. 이 경로를 따라 입력→출력 방향의 엣지는 매칭에 추가되고, 출력→입력 방향의 엣지는 매칭에서 제거된다. 이렇게 하면 매칭의 엣지가 하나 더 늘어난다. 이 과정을 반복하면서 residual graph에 더 이상 augmenting path가 존재하지 않게 될 때까지 수행하면 된다.

예를 들어 다음 요청 행렬 R을 보자:

이 요청 행렬을 기반으로 하는 bipartite graph와 그 위에서의 maximum matching 계산 과정이 그림 19.3에 나와 있다.

• (a): 초기 매칭이 진하게 표시되어 있다. 회색으로 표시된 입력과 출력은 이미 매칭된 상태이다. 이 매칭은 maximal이긴 하지만 maximum은 아니다.
• (b): 위 매칭에 기반하여 residual graph를 구성한 모습이다.
• (c): 매칭되지 않은 입력 2에서 시작해 출력 0까지 이어지는 augmenting path를 찾은 모습이다. 경로는 (i2,o1) → (o1,i0) → (i0,o0) 이다.
• (d): 위 경로를 따라 (i2,o1), (i0,o0)은 매칭에 추가되고, (o1,i0)은 매칭에서 제거된다.
• (e): 입력 5에서 출력 5까지의 augmenting path가 발견된 모습.
• (f): 그 경로를 적용한 최종 매칭 상태. 더 이상 augmenting path가 존재하지 않으므로 알고리즘 종료.

Ford-Fulkerson 이론에 따르면 augmenting path가 존재하지 않으면 해당 매칭은 maximum이다.

입력 우선 separable allocator는 요청 행렬의 행 기준으로 먼저 arbitration을 수행하고, 이후 열 기준으로 처리한다. 반대로 출력 우선 separable allocator는 열을 먼저, 그 다음 행을 arbitration 한다. 정사각형 행렬의 경우 두 방식 모두 동등하게 작동하지만, 직사각형 행렬에서는 짧은 방향을 먼저 arbitration 하는 것이 유리하다. 예를 들어, 4 × 3 allocator에서는 입력 arbitration을 먼저 수행하는 것이 출력 단계로 더 많은 요청을 전달할 수 있어 유리하다. 따라서 입력 속도가 출력 속도보다 더 빠른 switch에서는 보통 입력 우선 방식이 효율적이다.

예를 들어 다음 요청 행렬 R을 보자:

이 요청 행렬에 대한 하나의 입력 우선 separable allocation 예시는 그림 19.6에 나와 있다. 이 예에서는 각 arbiter가 처음 발견한 요청을 선택한다. 이때 input arbitration 이후의 중간 요청 행렬 X는 다음과 같다:

X 행렬은 입력 충돌을 제거하여 각 행에 1이 최대 한 개만 남는다. 이후 출력 arbitration을 통해 출력 충돌도 제거하면 최종 grant 행렬 G는 다음과 같다:

만약 첫 번째나 마지막 input arbiter가 마지막 요청을 선택했더라면, 세 개의 출력 모두에 할당할 수 있었을 것이다.

같은 요청 행렬(식 19.2)을 출력 우선 방식으로 처리했을 때 (각 arbiter가 처음 요청된 입력을 선택한다고 가정), 중간 행렬 Y와 grant 행렬 G는 다음과 같다:

이 경우 세 개의 출력 arbiter가 모두 동일한 입력을 선택해버리는 바람에 grant는 하나밖에 생성되지 않았다. 실제 하드웨어에서는 이렇게 정렬이 정확히 일치하는 경우는 드물지만, input 우선과 output 우선 방식의 차이는 Exercise 19.6에서 더 자세히 다룬다.

Separable allocator의 매칭 품질을 개선하기 위해 자주 사용되는 두 가지 기술이 있다.

첫째, 각 단계의 arbiter에서 높은 우선순위를 주는 입력을 staggering하여 여러 arbiter가 같은 출력을 선택하지 않도록 한다. 예를 들어, wavefront allocator (19.4절 참고)는 완전한 separable allocator는 아니지만, 입력 arbiter의 우선순위를 한 포트씩 offset 하여 설정하고 각 cycle마다 이를 회전시킨다. PIM (19.3.1절), iSLIP (19.3.2절), LOA (19.3.3절)도 각기 다른 방식으로 입력 우선순위를 staggering한다.

둘째, 시간이 허용된다면 여러 번 반복 실행(iteration)을 통해 매칭 품질을 향상시킬 수 있다. 각 반복에서는 이전 iteration에서 grant된 요청과 행이나 열에서 충돌하는 요청을 제거하고, 남은 요청에 대해 다시 separable allocation을 수행한다. 각 iteration에서 생성된 grant는 누적되어 전체 누적 grant 행렬을 만든다.

예를 들어 위 예시에서 두 번째 반복을 수행하면 모든 요청 중 r₃₂만 남아 충돌 없이 처리되며, g₃₂가 생성된다. 이때 각 행렬은 다음과 같다:

iSLIP은 단일 반복으로도 uniform 트래픽에서 100% throughput을 달성하지만, 반복 횟수를 한 번만 늘려도 지연(latency)은 크게 줄어들며, wavefront와 유사한 성능을 갖게 된다. 두 번 이상 반복해도 성능 개선은 미미하다.

17.2.2절에서 언급했듯, allocator 성능을 향상시키는 또 다른 방법은 switch에 입력 속도 향상(input speedup), 출력 속도 향상(output speedup), 혹은 둘 다 적용하는 것이다. 그림 19.15는 입력과 출력 속도 향상이 적용된 LOA의 성능을 보여준다.

• 속도 향상 없음 (IS=1, OS=1): 약 69%에서 포화
• 입력 속도 향상 2배 (IS=2, OS=1): 포화점이 약 95%로 증가하고 지연도 감소
• 입력과 출력 속도 모두 2배 (IS=2, OS=2): throughput이 100%로 향상

또 다른 접근은 crossbar와 allocator의 동작 속도를 채널 속도보다 빠르게 설정하는 것이다. 채널 속도로 패킷이 도착할 때, speedup 비율 S에 따라 S개의 패킷이 crossbar를 통과할 수 있다.

그림 19.16은 LOA에 speedup을 적용했을 때의 성능을 보여준다.

• S = 1.25: 약 85%까지 포화 throughput 증가
• S = 1.5: 약 98% 도달
• S = 1.75: 이후에는 throughput 또는 지연에 큰 개선 없음

19.8 사례 연구: Tiny Tera Allocator

Tiny Tera는 Stanford 대학에서 개발된 고속 패킷 스위치이며, 후에 Abrizio에 의해 상용화되었다. 핵심은 32포트 crossbar이며, 매 51ns마다 재구성이 필요하다. 이 시스템의 allocator는 iSLIP 알고리즘을 기반으로 출력 우선(output-first) arbitration 및 3회 반복으로 구성되어 있으며, timing 목표를 만족시키기 위해 파이프라인화 및 고속 arbiter 설계가 요구되었다.

일반적으로 iSLIP을 여러 번 반복할 경우, 각 반복에서 두 개의 arbitration 단계가 모두 끝난 후 다음 반복이 시작되어야 한다. 이전 반복의 결과를 바탕으로 matched된 input/output에 대응하는 요청을 비활성화해야 하기 때문이다. 이 방식은 반복당 두 arbitration 시간이 소요된다.

그러나 Tiny Tera에서는 clever한 최적화를 통해 이 반복 시간을 절반 수준으로 줄였다.

핵심 아이디어:
만약 어떤 출력 arbiter가 특정 입력을 선택했다면, 해당 입력은 이후 input arbitration에서도 매칭될 것이므로, 이를 미리 알고 **입력 마스크(input mask)**를 계산할 수 있다. 즉, 출력 arbitration 결과를 OR 연산하여 입력 마스크 imᵢ를 만들고, 다음 단계에서 이를 적용하면 된다.

그림 19.17은 3×3 iSLIP allocator의 일부 구조를 보여준다. 각 출력 arbitration은 OR 연산을 통해 imᵢ를 생성하고, 이는 다음 cycle에서 input arbitration에 입력 마스크로 사용된다. 이 방법을 사용하면 반복 시간이 "arbitration 1회 + OR 연산 시간"으로 줄어든다. 특히 Tiny Tera처럼 arbiter가 클 경우 OR 연산 시간은 매우 짧기 때문에 큰 이점이 있다.

두 번째 pipeline 단계에서는 input arbiter가 작동하며, 이들이 생성한 grant 신호를 OR 연산하여 **출력 마스크(omᵢ)**를 만든다. 이 마스크는 다음 input arbitration 단계에 적용되며, 이미 매칭된 output으로의 요청이 다음 cycle에서 input arbiter에 영향을 미치지 않도록 한다. 다만, 이 마스크는 처음부터 요청을 차단하는 것이 아니라 input arbiter에만 적용되므로, 첫 번째 출력 arbitration 단계에서 불필요한 요청이 처리되는 것은 막지 못한다. 하지만 최종 grant에는 영향을 미치지 않는다.

이 마스크 동작의 예시는 다음 페이지 2×2 allocator에 대한 반복 예제로 설명된다.

그림 19.18은 2×2 allocator에 대해 iSLIP 파이프라인 알고리즘을 2회 반복한 예시를 보여준다.

• 첫 반복(iteration 1)에서는 두 출력 arbiter가 모두 입력 0을 선택하고, 이 정보는 이후 cycle에서 입력 0이 매칭되었다는 표시(gray)로 사용된다.
• 두 번째 cycle에서는 첫 번째 반복의 input arbitration에서 입력 0이 출력 0에 요청을 보내고 grant를 받는다.
• 동시에 두 번째 반복의 출력 arbitration에서는 입력 1을 선택한다.
• 세 번째 cycle 시작 시, 출력 마스크는 출력 0이 이미 매칭되었다는 것을 반영한다. 이로 인해 입력 1 → 출력 0의 잘못된 요청은 두 번째 반복의 grant 계산 전에 마스킹되어 제거된다.

19.9 참고 문헌

maximum matching 알고리즘은 Hall과 Ford & Fulkerson이 가장 먼저 제안했다. augmenting path 알고리즘의 복잡도는 O(|V||E|)이며, Hopcroft와 Karp는 O(√|V||E|) 알고리즘을 개발했다 [83]. McKeown 등은 maximum-size matching이 non-uniform 트래픽에서는 100% throughput을 보장하지 않으며, 더 복잡한 maximum weight matching이 필요함을 보여주었다 [126].

이후, 100% throughput을 유지하면서도 maximum weight matching을 근사하는 다양한 기법들이 제안되었다 [183, 71]. **Parallel Iterative Matching (PIM)**은 Anderson 등이 처음 제안했다 [11]. iSLIP은 McKeown이 처음 고안 및 기술하였고 [123], Tiny Tera packet switch에 적용되었다 [125, 79]. Wavefront allocator는 Tamir가 개발하였으며 [180], Incremental allocation은 Alpha 21364 라우터에 효과적으로 사용되었다 [130, 131].

19.10 연습문제

19.1 Separable allocator의 성능
다음 요청 행렬에 대해 single-pass separable allocator가 생성할 수 있는 최상의 grant 행렬과 최악의 grant 행렬을 찾아라.

19.2 Wavefront allocator에서의 randomization 및 history 효과
다음 요청 행렬 R을 갖는 4×4 wavefront allocator를 고려하자. 우선순위 그룹은 그림 19.10과 동일하게 구성된다.

(a) 우선순위 그룹이 매 cycle마다 증가(p0, p1, p2, p3, p0, …)하고 요청 행렬 R이 고정되었을 때, 각 요청에 대해 얼마나 자주 grant가 주어지는가? 이것이 switch의 throughput에 미치는 영향은?

(b) 매 cycle마다 우선순위 그룹을 무작위로 선택하면 성능이 개선되는가?

(c) 일반적으로, 우선순위 셀은 각 행과 열에 하나씩 있는 어떤 패턴(즉, 순열)으로도 설정할 수 있다. 각 cycle마다 무작위 순열을 우선순위로 사용할 경우, (a) 및 (b)와 비교해 성능은 어떻게 되는가?

19.3 Multicast allocation
separable allocator를 확장하여 unicast뿐만 아니라 multicast 요청도 처리하게 하려면 어떻게 해야 하는가? multicast allocator는 각 입력 포트당 두 개의 추가 입력을 받는다:

• multicast 요청 신호 rm (동시 다출력 요청 시 활성화)
• 출력 포트별 비트벡터 bm (multicast 대상 출력 지정)

19.4 Incremental multicast allocation
라우터에서 multicast 요청을 한 번에 처리할 수도 있고, 작은 단위로 나누어 처리할 수도 있다. 극단적으로는 각 출력에 대해 하나씩 unicast로 나눌 수도 있다. 가능한 출력만 매 cycle마다 할당하고 나머지는 다음 cycle로 미루는 greedy incremental multicast allocator는 어떻게 설계할 수 있을까?

19.5 PIM의 수렴성
Uniform traffic 하에서 PIM이 maximal matching에 수렴하는 데 필요한 평균 반복 횟수는? 가능한 모든 요청 패턴 중 최악의 경우 반복 횟수는?

19.6 입력 속도 향상 환경에서의 input-first vs. output-first allocation
SN 입력, N 출력 스위치에서 S는 입력 속도 향상 계수라 하자.

(a) 요청이 uniform하고 single-pass PIM allocator를 사용할 경우, input-first 방식의 throughput은? output-first 방식은?

(b) N이 큰 경우, input-first와 output-first 방식 간 throughput 차이를 가장 크게 만드는 S는 몇인가? 그 차이는?

19.7 시뮬레이션 과제
속도 향상 1의 스위치에서 4회 반복 PIM allocator와, 속도 향상 2의 스위치에서 1회 반복 PIM allocator의 성능을 비교하라.