Team Members
- 김준홍 (KAIST 전산학부)
- 이승준 (KAIST 전산학부)
- 조민경 (KAIST 전산학부)
배경: Network on Chip (NoC)
Network on chip(NoC)이란 하나의 칩셋 내에 다수의 코어(Core)들을 집적하여 대규모 연산 등에 사용할 목적으로 제작한 시스템을 의미합니다. 쉽게 말해서, 그래픽 처리 장치(GPU)를 포괄하는 보다 상위 개념으로 생각할 수 있습니다.
이렇게 집적한 코어들을 활용해서 필요한 동작을 수행하기 위해서는 코어들이 서로 연결되어 네트워크를 구성해서 명령이나 데이터가 모든 코어로 도달할 수 있도록 해야만 합니다. 모든 코어가 서로 연결되어 있는 완전그래프(Complete graph) 형태로 네트워크를 구성하면 좋겠지만, 실제 시스템에서는 코어가 수백~수천개에 이르는 물리적 한계로 인해 보다 간단한 형태의 네트워크를 구성하게 됩니다.
다음 그림은 NoC를 구성하는 여러 Topology중 하나인 2D Mesh를 나타냅니다. 그림에 나타난 것과 같이 S에서 D로 정보를 전송하기 위해서는 직접 연결된 경로가 없으므로 다른 코어들을 통해 간접적으로 통신을 해야만 합니다.
▲ 2D Mesh topology
이러한 칩셋 내의 네트워크라는 특수한 환경에서 코어들을 배치하고 서로 연결하는 방법인 Topology의 구성 방법을 탐구하고, 코어간 통신이 서로 원활하게 이루어지도록 하는 Routing protocol을 설계 및 검증하는 과정이 바로 NoC 분야에서 주로 다루는 연구 주제입니다.
해결하려는 문제
위 단락의 배경 설명에서 NoC란 '하나의 칩셋 내에' 다수의 코어들을 '집적'한 것이라고 설명을 드렸습니다. 집적이란 곧 반도체 공정이므로, 이 과정에서 정상적으로 동작하지 않는 불량(Fault) 코어들이 포함될 가능성이 존재합니다. 헌데, 불량 코어가 하나라도 포함된 칩셋을 그냥 버려야 한다면 제조사 입장에서는 손실이 이만저만이 아닐 것입니다. 게다가, 통상 NoC에는 코어가 최소 수백개 이상 들어가므로 불량 코어가 포함되는 상황에 대한 대비가 필요합니다.
이 연구에서는 통신이 불가능한 불량 코어가 한 개 이상 포함된 NoC에서도 정상적인 통신이 가능하도록 하는 내결함성 라우팅 알고리즘(Fault-tolerant routing algorithm)을 설계하였습니다. 예를 들어, 다음 그림과 같이 S에서 D로 통신하는 최단 경로(녹색 점선)에 불량 코어(B)가 포함되어 있는 경우, 우회 경로(보라색 실선)를 자동으로 찾아서 통신이 가능하도록 합니다.
▲ 불량 코어(B)가 포함된 4x4 Mesh topology
제안하는 방법
한 학기라는 짧은 기간 내에 수행해야 하는 연구였던 만큼, 라우팅 알고리즘을 처음부터 고안하는 방법보다는 잘 알려진 기존 라우팅 알고리즘을 기반으로 하여 이를 보완하는 수단을 추가하는 방향으로 연구를 진행하였습니다.
2D Mesh topology에 적용 가능한 간단한 라우팅 알고리즘중 하나인 Dimension order routing(DOR)을 기반으로, 여기에 Flit tracker table(FTT)을 설계·도입하여 내결함성(Fault-tolerent) 특성을 부여한 새로운 라우팅 알고리즘을 고안하였습니다.
FTT는 거시 네트워크 프로토콜인 TCP의 수신확인(Acknowledgement)과 재전송(Retransmit) 동작 기재에 착안하여 이를 미시 네트워크에 맞도록 수정한 것입니다. 시스템상의 모든 코어들은 자신의 Local memory에 이 Table 구조체를 관리합니다.
▲ Flit tracker table (FTT)
코어가 Flit(거시 네트워크의 Packet과 유사한 개념)을 처음 수신하면 일단 DOR 라우팅 알고리즘에 따라 인접 노드에 전달하고, FTT에 Flit 정보와 함께 전달한 인접 노드의 방향(상/하/좌/우)을 기록합니다. 이와 더불어, 전체 시스템 클럭과 동기화되어 동작하는 재전송 타이머(Retransmit timer)를 초기화합니다.
Flit이 목적지(Destination)에 도착하면 자신이 지나온 경로의 역순으로 수신확인(ACK) 메시지를 전송하며, 이를 수신한 코어는 자신의 FTT에서 해당 Flit의 추적 정보를 삭제합니다. 반면, Flit이 일정 시간 내에 목적지에 도착하지 못해서 경로상 코어의 FTT의 타이머가 만료(Timeout)되면 해당 Flit을 지금까지 보내지 않은 다른 인접 노드로 재전송합니다. 이렇게 재전송되는 경로는 기존 DOR에 의한 경로의 일부 구간을 우회하는 경로로 정해지며, 이 기재를 통해 결함 노드를 피해 목적지 노드에 Flit이 도달하게 할 수 있습니다.
FTT Entry의 기존 전송 인접 노드(Sent output port)가 모두 '전송함(T)'으로 Mark된 채로 재전송 타이머가 만료되는 경우, ACK 수신 여부에 관계 없이 해당 Entry를 삭제합니다. 이로써 네트워크가 단절되는 등의 이유로 인해 가능한 통신 경로가 존재하지 않는 상황에 대처할 수 있게 됩니다.
▲ 내결함성 라우팅 알고리즘의 동작 방식
실험 방법
BookSim Interconnection Network Simulator(https://github.com/booksim/booksim2)를 수정하여 고안한 알고리즘을 구현하고, 다양한 Flit inject rate에서 알고리즘이 정상 동작함을 검증하였습니다.
실험 결과
▲ Average flit latency
※ X축은 Inject rate을, Y축은 Transmit latency[ms]를 의미합니다.
참고 문헌
- Jovanovic, S., Tanougast, C., Weber, S., Bobda, C., "A NEW DEADLOCK-FREE FAULT-TOLERANT ROUTING ALGORITHM FOR NOC INTERCONNECTIONS", in IEEE, 2009.
- Fukushima, Y., Fukushi, M., Horiguchi, S., "Fault Tolerant Algorithms for Network on Chip without Virtual Channels", in IEEE, 2009.
- Timo Schonwald, Jochen Zimmermann, Oliver Bringmann, Wolfgang Rosenstiel, "Fully Adaptive Fault-Tolerant Routing Algorithm for Network-on-Chip Architectures", in Digital System Design Architectures, Methods and Tools, 2007.
- N. Enright Jerger and L. Peh. On-Chip Networks. Morgan and Claypool Publishers, San Francisco, CA, USA, 1 edition, 2009.
- Ville Rantala, Teijo Lehtonen, Juha Plosila, "Network on Chip Routing Algorithms", TUCS Technical Report, No 779, August 2006
- N. Jiang et al., "A detailed and flexible cycle-accurate network-on-chip simulator", in Proceedings of ISPASS’13.