검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

LEF: An Effective Routing Algorithm for Two-Dimensional Meshes LEF: 2차원 메시를 위한 효과적인 라우팅 알고리즘

Thiem Van CHU, Kenji KISE

  • 조회수

    0

  • 이것을 인용

요약 :

우리는 낮은 설계 복잡성으로 높은 처리량을 제공하는 LEF(Long Edge First)라는 1차원 메시 기반 NoC(Networks-on-Chip)를 위한 새로운 망각 라우팅 알고리즘을 설계합니다. LEF의 기본 아이디어는 비대칭 메시 또는 토러스 상호 연결이 있는 슈퍼컴퓨터에 적합한 DOR(차원 순서 라우팅) 알고리즘을 선택하는 일반적인 통념에서 비롯됩니다. 즉, 가장 긴 차원을 먼저 라우팅하면 다른 전략보다 더 나은 성능을 제공합니다. LEF에서는 XY DOR과 YX DOR을 결합합니다. 패킷을 라우팅할 때 어떤 DOR 알고리즘이 선택되는지는 소스 노드와 대상 노드 사이의 상대적 위치에 따라 달라집니다. 적절한 DOR 알고리즘을 선택하는 결정은 네트워크 형태에 고정되지 않고 대신 패킷별로 결정됩니다. 또한 가상 채널의 사용이 기존 방법보다 더 유연한 LEF에 대한 효율적인 교착 상태 방지 방법을 제안합니다. 우리는 또 다른 효과적인 망각 라우팅 알고리즘인 O16TURN과 홀짝 회전 모델을 기반으로 하는 최소 적응형 라우팅 알고리즘에 대해 LEF를 평가합니다. 평가 결과는 통신이 비대칭 메시 내에 있을 때 LEF가 특히 효과적이라는 것을 보여줍니다. 8×4 NoC에서 LEF는 경우에 따라 적응형 라우팅 알고리즘보다 성능이 뛰어나며 O64.5TURN보다 약 1%에서 최대 약 1% 더 높은 처리량을 제공합니다. 또한 우리의 결과는 제안된 교착 상태 회피 방법이 LEF의 성능을 크게 향상시키는 데 도움이 되며 O100TURN의 성능을 향상시키는 데 사용될 수 있음을 보여줍니다. 또한 수천 개의 노드가 있는 대규모 NoC에서 LEF를 검사합니다. 우리의 결과는 NoC 크기가 증가할수록 라우팅 알고리즘의 성능은 네트워크의 자원 할당 정책에 의해 더 강하게 영향을 받으며, 그 효과는 알고리즘마다 다르다는 것을 보여줍니다. 이는 노드 수가 XNUMX개 정도인 중간 규모 NoC의 결과를 대규모 NoC에 직접 적용할 수 없다는 점에서 분명합니다.

발행
IEICE TRANSACTIONS on Information Vol.E102-D No.10 pp.1925-1941
발행일
2019/10/01
공개일
2019/07/09
온라인 ISSN
1745-1361
DOI
10.1587/transinf.2019EDP7019
원고의 종류
PAPER
범주
컴퓨터 시스템

작성자

Thiem Van CHU
  Tokyo Institute of Technology
Kenji KISE
  Tokyo Institute of Technology

키워드