Skip to content
TUWLAB.com

Timer-based Fault-Tolerant Routing Algorithm on Broken Mesh Topology

by TUW Posted 2017. 01. 22 Updated 2017. 03. 20 Views 363 Likes 0 Replies 0
Extra Form
작품 설명 결함성 망형 통신망에서의 타이머를 활용한 내결함성 라우팅 알고리즘 설계
주요 기능 2D-Mesh형태의 Network-on-Chip(NoC)에서 결함이 있는 Node의 유무에 관계없이 성공적으로 통신을 수행하기 위한 방법에 대한 연구입니다. TCP/IP에 적용되어 사용되고 있는 Timer기반 재전송 기법에 Flit tracker table을 도입하여 통신 알고리즘을 설계하고, BookSim NoC Simulator를 통해 동작을 검증하였습니다.
제작 기간 약 3개월 (2015. 4 ~ 6)
관련 분야 임베디드 시스템,컴퓨터 공학
제작 동기 2015-봄학기 컴퓨터구조(CS510) 수업에서 진행한 연구 프로젝트입니다.
제작 소감 대학원 석사과정에 입학하고 처음으로 수행한 연구 프로젝트입니다. 한학기라는 제한된 시간 내에 연구 주제 찾기 및 타당성 검토 - 개선 방안과 검증 방법 설계 - 실험과 결과분석 및 고찰로 진행되는 통상적인 공학 연구의 전체 프로세스를 연습해 볼 수 있었던 좋은 기회가 되었습니다.

Team Members

  • 김준홍 (KAIST 전산학부)
  • 이승준 (KAIST 전산학부)
  • 조민경 (KAIST 전산학부)


배경: Network on Chip (NoC)

Network on chip(NoC)이란 하나의 칩셋 내에 다수의 코어(Core)들을 집적하여 대규모 연산 등에 사용할 목적으로 제작한 시스템을 의미합니다. 쉽게 말해서, 그래픽 처리 장치(GPU)를 포괄하는 보다 상위 개념으로 생각할 수 있습니다.

이렇게 집적한 코어들을 활용해서 필요한 동작을 수행하기 위해서는 코어들이 서로 연결되어 네트워크를 구성해서 명령이나 데이터가 모든 코어로 도달할 수 있도록 해야만 합니다. 모든 코어가 서로 연결되어 있는 완전그래프(Complete graph) 형태로 네트워크를 구성하면 좋겠지만, 실제 시스템에서는 코어가 수백~수천개에 이르는 물리적 한계로 인해 보다 간단한 형태의 네트워크를 구성하게 됩니다.

다음 그림은 NoC를 구성하는 여러 Topology중 하나인 2D Mesh를 나타냅니다. 그림에 나타난 것과 같이 S에서 D로 정보를 전송하기 위해서는 직접 연결된 경로가 없으므로 다른 코어들을 통해 간접적으로 통신을 해야만 합니다.

fig1_xy_dor_routing.png
▲ 2D Mesh topology

이러한 칩셋 내의 네트워크라는 특수한 환경에서 코어들을 배치하고 서로 연결하는 방법인 Topology의 구성 방법을 탐구하고, 코어간 통신이 서로 원활하게 이루어지도록 하는 Routing protocol을 설계 및 검증하는 과정이 바로 NoC 분야에서 주로 다루는 연구 주제입니다.


해결하려는 문제

위 단락의 배경 설명에서 NoC란 '하나의 칩셋 내에' 다수의 코어들을 '집적'한 것이라고 설명을 드렸습니다. 집적이란 곧 반도체 공정이므로, 이 과정에서 정상적으로 동작하지 않는 불량(Fault) 코어들이 포함될 가능성이 존재합니다. 헌데, 불량 코어가 하나라도 포함된 칩셋을 그냥 버려야 한다면 제조사 입장에서는 손실이 이만저만이 아닐 것입니다. 게다가, 통상 NoC에는 코어가 최소 수백개 이상 들어가므로 불량 코어가 포함되는 상황에 대한 대비가 필요합니다.

이 연구에서는 통신이 불가능한 불량 코어가 한 개 이상 포함된 NoC에서도 정상적인 통신이 가능하도록 하는 내결함성 라우팅 알고리즘(Fault-tolerant routing algorithm)을 설계하였습니다. 예를 들어, 다음 그림과 같이 S에서 D로 통신하는 최단 경로(녹색 점선)에 불량 코어(B)가 포함되어 있는 경우, 우회 경로(보라색 실선)를 자동으로 찾아서 통신이 가능하도록 합니다.

fig2_4x4_broken_mesh_topology.png
▲ 불량 코어(B)가 포함된 4x4 Mesh topology


제안하는 방법

한 학기라는 짧은 기간 내에 수행해야 하는 연구였던 만큼, 라우팅 알고리즘을 처음부터 고안하는 방법보다는 잘 알려진 기존 라우팅 알고리즘을 기반으로 하여 이를 보완하는 수단을 추가하는 방향으로 연구를 진행하였습니다.

2D Mesh topology에 적용 가능한 간단한 라우팅 알고리즘중 하나인 Dimension order routing(DOR)을 기반으로, 여기에 Flit tracker table(FTT)을 설계·도입하여 내결함성(Fault-tolerent) 특성을 부여한 새로운 라우팅 알고리즘을 고안하였습니다.

FTT는 거시 네트워크 프로토콜인 TCP의 수신확인(Acknowledgement)재전송(Retransmit) 동작 기재에 착안하여 이를 미시 네트워크에 맞도록 수정한 것입니다. 시스템상의 모든 코어들은 자신의 Local memory에 이 Table 구조체를 관리합니다.

fig3_flit_tracker_table.png
▲ 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를 삭제합니다. 이로써 네트워크가 단절되는 등의 이유로 인해 가능한 통신 경로가 존재하지 않는 상황에 대처할 수 있게 됩니다.

fig4_flow_chart.png
▲ 내결함성 라우팅 알고리즘의 동작 방식


실험 방법

BookSim Interconnection Network Simulator(https://github.com/booksim/booksim2)를 수정하여 고안한 알고리즘을 구현하고, 다양한 Flit inject rate에서 알고리즘이 정상 동작함을 검증하였습니다.


실험 결과

fig6_average_flit_latency.png
▲ Average flit latency

※ X축은 Inject rate을, Y축은 Transmit latency[ms]를 의미합니다.


참고 문헌

  1. Jovanovic, S., Tanougast, C., Weber, S., Bobda, C., "A NEW DEADLOCK-FREE FAULT-TOLERANT ROUTING ALGORITHM FOR NOC INTERCONNECTIONS", in IEEE, 2009.
  2. Fukushima, Y., Fukushi, M., Horiguchi, S., "Fault Tolerant Algorithms for Network on Chip without Virtual Channels", in IEEE, 2009.
  3. 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.
  4. N. Enright Jerger and L. Peh. On-Chip Networks. Morgan and Claypool Publishers, San Francisco, CA, USA, 1 edition, 2009.
  5. Ville Rantala, Teijo Lehtonen, Juha Plosila, "Network on Chip Routing Algorithms", TUCS Technical Report, No 779, August 2006
  6. N. Jiang et al., "A detailed and flexible cycle-accurate network-on-chip simulator", in Proceedings of ISPASS’13.


서비스 선택
이용중인 SNS 버튼을 클릭하여 로그인 해주세요.
SNS 계정을 통해 로그인하면 회원가입 없이 댓글을 남길 수 있습니다.
댓글
?
Powered by SocialXE

  1. Analysing Security Vulnerability of Commercial Wire-wireless Routers

    Reply0 Views735 작품 설명상용 유무선 공유기의 보안 취약점 분석 관련 분야임베디드 시스템,컴퓨터 공학,웹 프로그래밍 제작 기간약 3개월 (2016. 4 ~ 6) file
    Read More
  2. 전국 학생식당 메뉴 포탈 - 메뉴플렉서(Menuplexer)

    Reply0 Views485 작품 설명대학교의 학생식당 메뉴를 끼니별로 구분하여 보여주는 웹 서비스입니다. 관련 분야웹 프로그래밍 제작 기간약 6개월 (2015. 9 ~ 2016. 1) file
    Read More
  3. Timer-based Fault-Tolerant Routing Algorithm on Broken Mesh Topology

    Reply0 Views363 작품 설명결함성 망형 통신망에서의 타이머를 활용한 내결함성 라우팅 알고리즘 설계 관련 분야임베디드 시스템,컴퓨터 공학 제작 기간약 3개월 (2015. 4 ~ 6) file
    Read More
  4. Qualcomm IT Tour 홈페이지

    Reply0 Views1179 작품 설명XE를 사용하여 제작한 퀄컴 IT Tour 홍보 및 커뮤니티 홈페이지입니다. 관련 분야컴퓨터 공학,웹 프로그래밍 제작 기간2014. 12 ~ 2015. 2 file
    Read More
  5. 자동 문단속 냉장고

    Reply0 Views1635 작품 설명펠티어 소자와 ATmega16 AVR 프로세서를 활용하여 제작한 자동 문단속 및 잠금 기능이 내장된 냉장고입니다. 관련 분야전자 공학,임베디드 시스템 제작 기간약 3개월 (2014.7.20 ~ 10.16) file
    Read More
  6. Smart Peltier Air Conditioner

    Reply0 Views1874 작품 설명펠티어 소자와 EK-TM4C1294XL 런치패드를 활용하여 제작한 인터넷에 연결되어 동작하는 스마트 에어컨입니다. 관련 분야전자 공학,임베디드 시스템,웹 프로그래밍 제작 기간약 4개월 (2014.5.22 ~ 9.16) file
    Read More
  7. Automobile CAN Communication System Simulator

    Reply0 Views2463 작품 설명자동차 내부의 통신 버스인 CAN을 중심으로 한 주변 장치들을 그대로 구현한 시뮬레이터입니다. 관련 분야전자 공학,임베디드 시스템 제작 기간약 2주일 (2013.12.10 ~ 24) file
    Read More
  8. 2-3-4 Tree

    Reply0 Views2019 작품 설명Balanced Search Tree의 한 종류인 2-3-4 Tree를 생성하고 관리하는 C++ 프로그램입니다. 관련 분야컴퓨터 공학 제작 기간약 2주일 (2013.11.15 ~ 11.29) file
    Read More
  9. 32bit Multi Cycle MIPS CPU

    Reply0 Views2197 작품 설명Verilog HDL을 이용하여 구현한 Multi Cycle 방식으로 동작하는 CPU입니다. 관련 분야전자 공학,컴퓨터 공학 제작 기간약 3개월 (2012.4 ~ 6), 학기중 점진적으로 진행 file
    Read More
  10. 8bit DAC를 활용한 Wave 음악 재생기 - DAC Wave 8

    Reply0 Views2807 작품 설명EEPROM에 저장되어 있는 Wave파일 형식의 음악을 직접 구현한 8bit DAC를 통해 재생합니다. 관련 분야전자 공학,임베디드 시스템 제작 기간약 2주일 (2009.6.15 ~ 29) file
    Read More
  11. Computer Generated Random Variable Simulator

    Reply0 Views4155 작품 설명컴퓨터로 생성한 확률변수의 샘플 갯수에 따른 분포를 그려보고, 시뮬레이션해 보는 텀프로젝트입니다. 관련 분야전자 공학,컴퓨터 공학 제작 기간약 2주일 (2009.5) file
    Read More
  12. Sequential Adder & Multiplier with 7-Segment display

    Reply0 Views2338 작품 설명두 개의 숫자의 합과 곱을 7-segment에 표시하는 논리 회로를 설계하는 텀프로젝트입니다. 관련 분야전자 공학 제작 기간약 일주일 (2008.6.18 ~ 6.25) file
    Read More
  13. 3D 공간 스캐너

    Reply0 Views2555 작품 설명레이저 포인터와 웹캠으로 거리를 측정하여 내부 공간을 3D로 스캔하는 공간 스캐너입니다. 관련 분야전자 공학,임베디드 시스템 제작 기간약 4개월 (2009.2.1 ~ 5.20) file
    Read More
  14. 무선 배틀 테트리스 게임기 - BATENDO

    Reply0 Views3001 작품 설명넷마블 테트리스를 모티브로 제작한 1:1 무선 블루투스 배틀 테트리스 게임기입니다. 관련 분야전자 공학,임베디드 시스템 제작 기간약 4개월 (2008.5 ~ 8, 2013.4) file
    Read More
  15. BIS 연구실 소개 홈페이지

    Reply0 Views2888 작품 설명XE를 사용하여 제작한 대학원 연구실 홈페이지입니다. 관련 분야웹 프로그래밍 제작 기간약 1개월 (2014.3.12 ~ 4.16), 실 작업일 약 일주일 file
    Read More
  16. 웹 기반 시간표 자동 조합 프로그램 - BATTO

    Reply2 Views3762 작품 설명수강신청 기간 대학생을 대상으로 한 웹 기반 시간표 자동 조합 프로그램입니다. 관련 분야컴퓨터 공학,웹 프로그래밍 제작 기간약 3개월 (2013.9.19 ~ 12.3) file
    Read More
  17. 전자동 커튼

    Reply3 Views2552 작품 설명기존 수동 커튼에 AVR을 활용한 구동 회로를 장착하여 제작한 전동 커튼입니다. 관련 분야전자 공학,임베디드 시스템,기계 공학 제작 기간약 2주일 (2010.2.10 ~ 24) file
    Read More
  18. HAKKO 온도조절 인두기

    Reply0 Views2074 작품 설명HAKKO 히터 및 팁을 장착한 온도조절 인두기 관련 분야전자 공학,임베디드 시스템 제작 기간약 2개월 (2013.4 + 2014.1) file
    Read More
목록
Board Pagination Prev 1 Next
/ 1

Powered by Xpress Engine / Designed by Sketchbook

sketchbook5, 스케치북5

sketchbook5, 스케치북5