Hardware/ASIC/SoC/NoC2009.11.06 15:57

Wormhole routing

  비록 Virtual cut-through와 circuit Switching이 경로의 길이에 상대적으로 독립적인 낮은 네트워크 Latency를 제공할지라도, virtual cut-through는 블럭킹된 패킷을 버퍼에 저장하고 Circuit switching은 패킷들 사이의 채널들의 공유를 지원하기 위한것을 어렵게 만든다. Wormhole routing은 Dally와 Seitz에 의해 제안되었으며, 비슷한 네트워크 Latency 일 때 패킷들 사이의 채널들을 공유하는 어려움을 해결하기 위해서 설계 되었다. Wormhole routing은 또한 switching에서 cut-through 방법을 사용한다. 패킷은 전송을 위해서 많은 flit들(Flow control digits)로 나뉜다. 한 flit의 크기는 개개의 채널 폭에서 시스템 파라미터에 의존한다. 일번적으로 한 flit을 구성하는 bit들은 두 라우터 사이에 병렬로 전송된다. 피킷의 헤더 flit 또는 flit 들은 라우트를 제어하고, 헤더가 특정 route를 따라서 이동하기 때문에, 남아있는 flit들은 파이프라인 방식으로 뒤 따른다. 만약 헤더 flit이 이미 사용되고 있는 채널과 만난다면, 채널이 이용 가능할 때 까지 블럭킹된다.

  Wormhole routing의 파이프라인되는 성질은 두가지 긍정적 영향을 나타낸다.
첫째로, 네트워크의 회선쟁탈의 없음은 경로 길이에 상대적으로 영향을 받지 않는 네트워크 Latency를 만든다.
둘째로, 각 중간 노드에서 큰 패킷 버퍼는 미연에 방지되고 오직 작은 FIFO flit 버퍼를 필요로한다.

  Wormhole routing은 store-and-forward routing 이상의 몇 몇 이점을 가지고 있다. store-and-forward routing에서 만약 한 b-flit 메시지를 길이 d인 경로로 운반한다면, 그리고 지연이 없다고 한다면, 이것은 bd step(각 channel은 각 step에서 하나의 flit을 전송한다고 가정)에서 목적지에 도착할 것이다.
  Wormhole routing에서 그러나 처음 flit은 메시지의 나머지를 기다리지 않는다. 이것은 그러므로 d step이후에 이것의 목적지에 도착한다. 그리고 메시지의 마지막 flit은 d+ b-1 step이후에 도착한다. 시간의 차이는 wormhole router에 의해 network edge의 더 나은 이용성 때문이다. 게다가 latency를 감소시키기 위해서 wormhole routing은 작고, 빠른 스위치로 구현되고 Optical communication에서 실제 모델이다라는 이점을 가지고 있다.
  Wormhole routing에서 주요 장애는 회선 쟁탈이다. 이것은 보통 traffic 조차에서도 발생하것이며, 높은 메시지 latency에 이른다.
  언제 어떤 메세지든지간에 회선 쟁탈 때문에 진행이 불가능하고, header와 data flit들은 network에서 제거 되지 않는다, 대신에 메시지는 모든 Channel들을 점유한다. source에서 목적지까지 경로를 따라 각 channel은 그 시간에 점유되기 때문에 이것은 전체 메시지가 그 채널을 통과 할때 까지 계속된다.  회선쟁탈은 어려워지고 메시지 latency는 받아들일 수 없게 높게 될것이기 때문에 성능은 감소된다.
  한 제안은  Latency와 회선 쟁탈을 감소시키기 위해서 몇몇 Channel들을 지원하기 위한 Link를 허용하는 것이다(Link bandwidth를 증가 시키기 위해서). 우리는 이 방법이 wormhole routing방법을 실제 많은 개선을 할 것이다라는 것을 보여 줄것이다.
  우리는 이것을 보여주기 전에 wormhole routing의 영역에서 결과에 대한 주어진 역사적인 개요를 시작하고 임의의 경로 모집에서 wormhole routing을 위한 upper와 lower bound를 나타낸다.

1.Wormhole Routing의 역사.
  Wormhole routing은 대규모 병령 컴퓨터의 최근 세대에서 routing 방법으로 선택 되었다. 이것은 Dally와 Seitz의 논문에서는 Deadlock을 피하기 위한 Wormhole routing 알고리즘의 설계를 제안하였다. 이 문제의 해법은 worm은 cycle형태가 되지 않게 가상 network를 구성하고, 몇몇 가상 channel과 경쟁하기 위한 각 link를 허용하는 것이다. 가상 channel은 link에 의해 제공되는 물리적 wire를 공유한다, 그러나 switch는 각 가상 channel를 위해 개별적인 buffer를 유지한다.

'Hardware > ASIC/SoC/NoC' 카테고리의 다른 글

NoC Simulator  (0) 2009.11.09
WDM(Wavelength-division multiplexing)  (0) 2009.11.06
Wormhole routing[미완료]  (0) 2009.11.06
Crossbar switch fabric  (0) 2009.11.06
Source routing  (0) 2009.11.06
Temrs in ONoC(Optical Network-on-Chip)  (0) 2009.11.06
Posted by Act of God