KR101508573B1 - 네트워크 온 칩 및 그 대역폭 할당 방법 - Google Patents

Abstract

본 발명은 메시 토폴로지(mesh topology)로 서로 연결된 라우터; 및 상기 라우터와 연결되어 상기 라우터를 통해 다른 프로세싱 엘리먼트와 데이터를 주고 받는 프로세싱 엘리먼트;를 포함하되, 상기 라우터 내의 충돌(contention) 지연, 버퍼 지연, 및 링크 지연에 기초하여, 각 데이터 플로우의 라우터 지연 시간을 산출하고, 상기 라우터 지연 시간이 요구 지연 시간보다 긴 플로우가 지나는 링크에 기설정된 기본 대역폭보다 큰 추가 대역폭을 할당하는 네트워크 온 칩을 제공한다.

Description

네트워크 온 칩 및 그 대역폭 할당 방법{NETWORK-ON-CHIP AND METHOD FOR BANDWIDTH ALLOCATION THEREOF}

본발명은 네트워크 온 칩에 관한 것이다.

반도체 칩이 점차 미세화 및 복잡화되면서, 각각의 기능을 수행하는 복수의 코어(Core, 또는 IP블록(IP block: Intellecture Property block)으로도 지칭함)를 하나의 칩으로 집적하기 위한 시스템 온 칩(System on Chip: SoC) 기술이 대두되었다.

시스템 온 칩 내 각 코어간 통신에 있어, 각 코어에 병렬로 연결된 버스(BUS) 기반의 통신을 사용하는 경우, 즉, 버스에 연결된 다수 개의 IP 블록 중 단 하나의 IP 블록에만 데이터 송신을 위한 버스 이용 권한을 주는 경우, 코어의 개수가 증가하거나, 또는 코어 간 송수신되는 데이터의 용량이 증가할수록, 버스에서의 데이터 지연 시간이 기하급수적으로 증가하는 문제점이 있다.

이러한 시스템 온 칩의 문제점을 극복하고자, 네트워크 온 칩(Network-on-Chip: NoC) 기술이 제안되었다.

네트워크 온 칩은 버스 기반 대신 각 코어에 대응하는 라우터에 의한 패킷 기반의 네트워크 방식으로 코어 간에 데이터를 송수신한다. 많은 개수의 코어를 집적하더라도, 버스 이용 권한을 기다릴 필요 없이, 라우터를 통해 패킷 형태로 데이터를 송수신함에 따라, 데이터 전송 처리량(throughput)을 대폭 향상시킬 수 있고, 이로써 전력 소모를 낮출 수 있다.

네트워크 온 칩은 라우터의 토폴로지 구성에 있어서도 유연하다. 예를 들어, 다수 개의 라우터를 사방으로 이웃한 것끼리 연결한 형태인 메시 토폴로지(mesh topology)가 많이 사용된다. 이외에도 하나의 중심 라우터에 다수 개의 주변 라우터를 연결한 형태의 스타 토폴로지(star topology), 다수 개의 라우터를 중심 케이블인 버스(bus)에 연결한 형태인 버스 토폴로지(bus topology), 다수 개의 라우터를 일방향으로 이웃한 것끼리 원형을 이루도록 연결한 형태인 링 토폴로지(ring topology), 및 다수 개의 라우터를 수직 관계의 피라미드로 연결한 형태인 트리 토폴로지(tree topology) 등을 채용할 수 있다.

네트워크 온 칩의 대역폭은 동작 주파수와 링크 폭에 영향을 받아 네트워크 온 칩의 면적과 파워 소모를 증가시키는 중요한 요인이다. 따라서 네트워크 온 칩을 디자인할 때 서비스 품질을 충족시키는 선에서 최소의 대역폭을 할당해야만 한다.

이때, 서비스 품질을 고려한 대역폭 할당을 위해선 정확한 지연 모델을 구하는 것이 중요하다. 네트워크 온 칩의 주어진 스케줄링 조건을 통해서 얻어지는 각각의 지연에 따라 해당 링크는 다른 대역폭 값을 필요로 하기 때문이다. 또한 링크에서의 지연 시간만 고려하면 정확한 대역폭 할당을 할 수 없다.

따라서 네트워크 온 칩의 라우터에서 각 링크에 트래픽 조건에 따른 최소의 대역폭을 할당하는 방법이 필요하다.

본 발명과 관련하여 한국등록특허 제10-1254706호("3차원 네트워크 온 칩")에는 라우터와 코어를 다수개의 레이어로 적층한 구성이 개시되어 있다.

또한, 한국등록특허 제10-1242172호("하이브리드 광학 네트워크-온-칩 시스템 및 그의 라우팅 방법")에는 광 라우터와 전기 라우터를 포함하는 구성이 개시되어 있다.

본 발명은 전술한 문제를 해결하기 위한 것으로서, 그 목적은 가상 채널을 통해 네트워크 온 칩의 성능을 향상시키면서, 각 링크에 트래픽 조건에 따른 최소의 대역폭을 할당하는 알고리즘을 제공하는 것이다.

특히 라우터내의 충돌 지연, 버퍼 지연, 및 링크 지연을 고려한 지연 시간 모델을 제공하고 이 모델을 통해 네트워크 온 칩의 스케줄링 조건을 만족시키는 최소의 대역폭을 할당하고자 한다.

상기와 같은 목적을 달성하기 위한 본 발명의 제 1 측면에 따른 네트워크 온 칩(Network-on-Chip) 시스템은 메시 토폴로지(mesh topology)로 서로 연결된 라우터; 및 상기 라우터와 연결되어 상기 라우터를 통해 다른 프로세싱 엘리먼트와 데이터를 주고 받는 프로세싱 엘리먼트;를 포함하되, 상기 라우터 내의 충돌(contention) 지연, 버퍼 지연, 및 링크 지연에 기초하여, 각 데이터 플로우의 라우터 지연 시간을 산출하고, 상기 라우터 지연 시간이 요구 지연 시간보다 긴 플로우가 지나는 링크에 기설정된 기본 대역폭보다 큰 추가 대역폭을 할당하는 네트워크 온 칩(Network-on-Chip) 시스템에서의 대역폭 할당 방법은 (a) 라우터 내의 충돌(contention) 지연, 버퍼 지연, 및 링크 지연에 기초하여, 각 데이터 플로우의 라우터 지연 시간을 산출하는 단계; 및 (b) 상기 라우터 지연 시간이 요구 지연 시간보다 긴 플로우가 지나는 링크에 기설정된 기본 대역폭보다 큰 추가 대역폭을 할당하는 것을 특징으로 한다.

상기와 같은 목적을 달성하기 위한 본 발명의 제 2 측면에 따른 zzz 것을 특징으로 한다.

본 발명은 네트워크 온 칩 및 그 라우팅 방법에 있어, 가상 채널을 통해 네트워크 온 칩의 성능을 향상시키면서, 각 링크에 트래픽 조건에 따른 최소의 대역폭을 할당하는 알고리즘을 제공하는 효과를 얻는다.

네트워크 온 칩에서 라우터 내의 가상 채널에 의한 패킷 지연 시간을 정확히 알 수 있으며, 제공하는 알고리즘을 통하여 낭비되는 대역폭를 줄여 자원 비용을 최소화 할 수 있다.

도 1 및 도 2는 본 발명의 일실시예에 따른 네트워크 온 칩의 구조를 도시함.
도 2는 도 1의 라우터의 가상 채널을 도시함.
도 3은 본 발명의 일실시예에 따른 대역폭 할당 방법의 흐름을 도시함.
도 4는 본 발명의 일실시예에 따른 가상 채널 지연 모델의 표기를 도시함.
도 5는 본 발명의 일실시예에 따른 가상 채널 지연 모델의 수식을 도시함.
도 6은 본 발명의 일실시예에 따른 최소 대역폭 할당 알고리즘을 도시함.
도 7은 본 발명의 일실시예에 따른 대역폭 할당 알고리즘을 도시함.
도 8 내지 도 10은 본 발명의 일실시예에 따른 실험 결과를 도시함.

아래에서는 첨부한 도면을 참조하여 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자가 용이하게 실시할 수 있도록 본 발명의 실시예를 상세히 설명한다. 그러나 본 발명은 여러 가지 상이한 형태로 구현될 수 있으며 여기에서 설명하는 실시예에 한정되지 않는다. 그리고 도면에서 본 발명을 명확하게 설명하기 위해서 설명과 관계없는 부분은 생략하였으며, 명세서 전체를 통하여 유사한 부분에 대해서는 유사한 도면 부호를 붙였다.

명세서 전체에서, 어떤 부분이 다른 부분과 "연결"되어 있다고 할 때, 이는 "직접적으로 연결"되어 있는 경우뿐 아니라, 그 중간에 다른 소자를 사이에 두고 "전기적으로 연결"되어 있는 경우도 포함한다. 또한 어떤 부분이 어떤 구성요소를 "포함"한다고 할 때, 이는 특별히 반대되는 기재가 없는 한 다른 구성요소를 제외하는 것이 아니라 다른 구성요소를 더 포함할 수 있는 것을 의미한다.

도 1 및 도 2는 본 발명의 일실시예에 따른 네트워크 온 칩의 구조를 도시하고 있다.

전술한 바와 같이 네트워크-온-칩(Network-on-Chip: NoC)은 다중 프로세서 시스템-온-칩 (Multi-Processor SoC: MPSoC)에서 다중 코어로 인하여 생기는 성능 병목 현상을 해결하고자 제안된 기술이다. NoC는 코어 간 라우터를 사용하여 병렬적으로 통신을 하기 때문에 기존의 버스 기반 통신 방식에 비하여 향상된 성능과 스루풋(throughput)을 얻을 수 있다.

하지만 데이터의 처리 및 전송량이 많아짐에 따라 몇 가지 문제가 발생하는데, 그 중 하나가 라우터 내에서의 충돌 문제이다.

따라서 본 발명의 일실시예에 따른 네트워크 온 칩 및 그 대역폭 할당 방법은 네트워크 온 칩에서 가상 채널 라우팅 기법을 사용할 때, 충돌, 버퍼 및 스위칭 지연을 고려한 패킷 지연 모델을 제공한다. 이 모델을 통하여 가상 채널을 사용한 네트워크 온 칩의 패킷 지연 시간을 측정할 수 있으며, 각각의 링크에서 지연 시간을 고려한 최적의 채널 대역폭을 할당하는 기법을 제공한다.

본 발명의 일실시예에 따른 네트워크 온 칩은 도 1 및 도 2에 도시되어 있는 바와 같은 2D-메시(mesh) 형태의 토폴로지를 사용하여 구성될 수 있다.

다수의 코어를 메시 토폴로지로 연결하면, 모든 링크의 길이가 동일해진다는 장점이 있다.

2D-메시 토폴로지로 구성된 본 발명의 일실시예에 따른 네트워크 온 칩(10)은 2차원, 즉, X좌표와 Y 좌표를 따라 격자 형태로 배열되는 복수의 프로세싱 엘리먼트(200) 및 복수의 프로세싱 엘리먼트(200, Processing Element: PE)와 연결되는 라우터(100)를 포함한다.

프로세싱 엘리먼트(200)는 코어(Core) 또는 프로세서 코어(Processing Core), 또는 IP블록(IP block: Intellecture Property block)이라 지칭되기도 한다.

2D-메시 토폴로지는 각 라우터(100)와 프로세싱 엘리먼트(200)가 격자 형태로 연결되므로, 도시되어 있는 바와 같이, 각 라우터(100)에서 이웃 라우터(100)의 방향을 동(E: east), 서(W: west), 남(S: south), 북(N: north)로 지칭하기도 한다(각각 X축 및 Y축).

따라서 도시되어 있는 바와 같이 본 발명의 일실시예에 따른 네트워크 온 칩(10)의 라우터(100)는 자신과 연결된 프로세싱 엘리먼트(200)의 데이터 송수신을 위한 1개의 로컬 포트(T)에 4개의 이웃 라우터(100)와의 통신을 위한 입출력 포트(E, W, S, N)를 합쳐 5개의 입출력 포트를 포함할 수 있다.

라우터(100)는 예를 들어 크로스바 스위치(Crossbar)를 통해 데이터 플로우(flow), 패킷(packet), 또는 플릿(flit: FLow control digIT)의 방향을 제어할 수 있다. 패킷은 소스 정보와 목적지 정보를 포함하고 있으며, 플릿은 이름이 내포하고 있는 바와 같이, 패킷을 흐름 제어를 위해 좀더 작게 쪼갠 데이터 단위이다. 일반적으로 헤더 플릿이 해당 패킷의 경로(route) 정보를 가지고 있으며, 그 이후의 플릿은 헤더 플릿을 따라 간다.

예를 들어, 어떤 패킷의 헤더 플릿이 라우터(100)의 서쪽 포트에서 입력되어 북쪽 포트로 출력되도록 경로가 정해졌다면 상기 패킷의 플릿들은 모두 서쪽 포트에서 입력되어 북쪽 포트로 출력된다.

각 입출력 포트는 하나 이상의 버퍼를 포함할 수 있다. 예를 들어, 라우터(100)는 입력 버퍼 또는 출력 버퍼를 포함할 수 있다. 이때 하나의 물리적인 버퍼가 2개 이상의 가상 채널(Virtual Channel: VC) 버퍼(110)로 활용될 수 있다.

라우터(100) 내에서 여러 개의 패킷이 동일한 출력 포트를 사용할 때 패킷이 링크의 가용 대역폭을 초과한다면 충돌(contention)이 발생한다. 이 충돌은 패킷의 지연 시간을 증가시켜 시스템의 성능이 감소되는 원인이 된다. 가상 채널은 네트워크 온 칩에서 충돌에 의한 입출력의 한계를 극복하고 성능 향상을 위해 도입된 기술이다.

가상 채널은 도 2와 같이 하나의 물리적인 버퍼 공간을 두 개의 가상 채널 버퍼(110)가 있는 것처럼 사용하는 것이다. 그리고 가상 채널 식별자(VC Identifier)를 통해 패킷의 전송을 단 대 단(end to end)으로 연결하여 전송량을 증가시키기 때문에, 라우터(100)의 스루풋과 네트워크 온 칩(10)의 성능이 향상된다.

하지만 가상 채널을 사용하게 되면 추가되는 로직에 의하여 공간과 파워 소모가 증가하는 문제점을 가지게 된다.

이 문제점을 완화시키기 위해 트래픽에 따라 가상 채널을 선택적으로 할당하는 방법이 제안되었다. 라우터(100) 내의 충돌 확률을 계산하여 기준 이상의 지연 시간을 가지는 라우터(100)에만 가상 채널을 할당하는 것이다.

또한, 링크의 대역폭 할당을 최소화하는 방법을 통해 네트워크 온 칩(10)의 성능을 개선할 수 있다. 네트워크 온 칩(10)에서 대역폭은 면적과 전력 소모에 영향을 주기 때문에 네트워크 온 칩을 디자인할 때 서비스 품질(Quality-of-Service, QoS)를 충족시키는 선에서 최소의 대역폭을 할당해야만 한다.

이를 위해 네트워크 온 칩 지연 모델을 설계하여 트래픽 조건에 따라 각 링크에 최소의 대역폭을 할당하는 방법이 제안되었다. 하지만 링크에서의 지연 시간만 고려했기 때문에 라우터(100) 내에서 발생하는 지연 시간(버퍼 지연, 충돌 지연)을 모른다는 문제를 가지고 있다.

본 발명은 가상 채널을 통해 네트워크 온 칩(10)의 성능을 향상시키면서, 각 링크에 트래픽 조건에 따른 최소의 대역폭을 할당하는 알고리즘을 제공한다. 라우터(100)내의 충돌 지연, 버퍼 지연, 및 링크 지연을 고려한 지연 시간 모델을 제안하고 이 모델을 통해 네트워크 온 칩(10)의 스케줄링 조건을 만족시키는 최소의 대역폭을 할당한다.

도 3을 통해 이에 대해 간력히 살펴본 후 도 4 내지 도 7을 통해 자세히 설명한다.

도 3은 본 발명의 일실시예에 따른 대역폭 할당 방법의 흐름을 도시하고 있다.

본 발명의 일실시예에 따른 대역폭 할당 방법은 라우터 내의 충돌(contention) 지연, 버퍼 지연, 및 링크 지연에 기초하여, 후술하는 지연 모델에 따라 각 데이터 플로우의 라우터 지연 시간을 산출하고, 라우터 지연 시간이 요구 지연 시간보다 긴 플로우가 지나는 링크에 기설정된 기본 대역폭보다 큰 추가 대역폭을 할당한다.

이를 위해 먼저, 플로우에 대해 초기 대역폭을 할당한다(S100). 초기 대역폭은 링크에 기설정된 기본 대역폭이며, 예를 들어, 도 6의 알고리즘에 도시되어 있는 바와 같이 400MB일 수 있다. 그러나 초기 대역폭이 이 값에 한정되는 것은 아니다.

다음, 지연 모델에 따라 라우터(100)에서의 지연 시간 및 플로우 지연 시간을 산출한다(S200 및 S300). 지연 모델은 라우터(100) 내의 지연 시간을 고려한 플로우의 지연 시간을 산출하기 위한 수학 모델이며, 이에 대해서는 도 4 및 도 5를 통해 곧 후술한다.

요구 지연 시간보다 긴 최장 지연 시간을 갖는 플로우에 대해 대역폭을 추가한다(S400). 즉, 상기 단계들(S200, S300)을 통해 산출된 플로우의 지연 시간을 기초로, 라우터 지연 시간이 요구 지연 시간보다 긴 플로우 중 라우터 지연 시간이 가장 긴 플로우가 지나는 링크에 추가 대역폭을 할당한다.

할당되는 추가 대역폭은 데이터 플로우의 전체 지연 시간이 요구 지연 시간보다 작은 값을 가질 수 있도록 할당되며, 이를 위해 라우터는 라우터 지연 시간이 요구 지연 시간보다 긴 플로우가 지나는 모든 링크에 소정의 대역폭 변위를 추가한 대역폭 값을 산출한 후, 라우터 지연 시간이 가장 긴 플로우가 지나는 링크에만 소정의 대역폭 변위를 추가한 대역폭 값인 추가 대역폭을 할당하고 나머지 링크에는 기본 대역폭을 할당한다.

상기의 각 단계를 위한 구체적인 알고리즘은 도 6 내지 도 7을 통해 후술하며, 먼저 도 4 및 도 5를 통해 지연 모델을 설명한다.

도 4 및 도 5는 본 발명의 일실시예에 따른 가상 채널 지연 모델을 도시하고 있다. 도4에서 정의한 가상 채널을 이용한 라우터(100) 및 패킷의 특성을 사용하여, 도 5의 수식을 통해 가상 채널 라우터 지연 모델을 설명한다.

지연 시간을 구하기 위해 가상 채널을 이용한 라우터(100) 및 패킷의 특성을 도 4와 같이 정의 하여야 한다. 그 중 몇가지를 정리하면 다음과 같다.

= 입력 포트 i에서 출력 포트 j로 이동할때 다른 플로우에 의해 막힐 확률

= 한 플릿(flit)이 입력 포트 I에서 j로 흐를 조건부 확률

= 입력 포트 i에서 출력 포트 j로 이동하는 플릿의 평균 개수 [flits/cycle]

W = 링크의 대역폭 [bits/sec]

= 한 플릿이 입력 포트 i에서 출력 포트 j로 이동할 때 충돌이 발생할 확률

, = 입력 포트 i의 가상 채널에서 충돌이 발생할 확률 (

은 2개의 가상 채널에서 충돌이 발생할 확률이며,

는 한 개의 가상 채널에서만 충돌이 발생할 확률이다 )

= 입력 포트 k로 들어오는 평균 패킷 개수

R = 평균 잔여 서비스 시간

= 입력 포트 j의 큐(queue)에서 한 패킷이 기다리는 평균 시간

= 플로우 f 가 지나는 채널의 집합

= 플로우 f의 전체 전송 시간

F = 전체 플로우 f의 집합

패킷의 평균 전송 시간은 도 5의 1번째 수식 (EQ1)과 같다. 즉, 패킷의 평균 전송 시간은 헤더 플릿이 라우터(100)와 링크를 지나는 시간과 패킷의 사이즈를 링크의 대역폭으로 나눈 값인 링크 지연의 합으로 산출할 수 있다.

(EQ1)

단, 상기 수식 (EQ1)은 라우터(100) 내의 버퍼 지연 시간과 충돌 지연 시간을 제외한 시간이다.

이때 전술한 바와 같이 헤더 플릿을 제외한 나머지 플릿들은 파이프라인(pipeline) 방식으로 헤더 플릿을 따라간다.

링크의 전송 시간을 기반으로 라우터(100) 내에서 패킷의 지연 시간을 알기 위해 다음과 같은 4가지 가정을 사용하여 라우터(100)를 모델링 한다.

1> 2-D 메시 구조의 네트워크 온 칩(10)에서 각 라우터(100)는 5개의 채널을 통해 주변의 4개 라우터(100)와 1개의 프로세싱 엘리먼트(200)와 통신한다. 이는 도 1 및 도 2를 통해 상술하였다.

2> 라우터(100)의 채널은 웜홀 라우팅(wormhole routing) 방식을 따르고 각각 2개의 가상 채널을 포함한다.

3> 라우터(100)의 채널 버퍼 사이즈는 무한하다고 가정한다.

4> 출력 포트의 충돌은 전체 출력 플릿이 링크 대역폭보다 큰 경우 발생한다고 가정한다.

라우터(100) 내의 입력 포트 i에 있는 패킷이 출력 포트로 이동할 때 충돌이 발생할 확률

을 구하기 위해선 먼저 상기 네번째 가정에서 제시한 출력 포트 j로 나가려는 플릿의 전체 대역폭을 구해야 한다.

전체 플로우가 주어져 있을 때, 채널 i에서 채널 j로 이동하는 평균 플릿의 개수

는 도 5의 2번째 수식 (EQ2)와 같이 표현된다.

(EQ2)

여기서

는 플로우 f가 라우터(100)에 들어오는지를 나타내고, R(f,i,j)는 해당 플로우가 라우터(100)의 채널 i에서 채널 j로 이동하는 지를 나타내는 함수이다. 앞선 가정에서 설명했듯 라우터(100)는 4개의 채널과12개의 종단 채널을 가지므로 i ∈ {E,W,S,N}, j ∈ {E,W,S,N,T} 를 따른다.

도 5의 2번째 수식 (EQ2)를 통해 라우터(100)의 출력 포트 j에서 충돌 발생할 확률

와 입력 포트 I에서 j로 이동할 확률

는 도 5의 3, 4번째 수식 (EQ3, 4)와 같이 표현할 수 있다.

(EQ3)

(EQ4)

이렇게 구한

와

를 곱하면 플릿이 라우터(100) 내의 입력 포트 i에서 출력 포트 j로 이동할 할 때 충돌이 발생할 확률

를 구할 수 있다. 그리고

의 출력단을 모두 더하면 입력 포트 i에서 충돌 발생 확률

를 다음과 같이 표현할 수 있다.

(EQ5)

(EQ6)

이를 토대로 입력 포트 i가 2개의 가상 채널을 가진다고 할 때의 충돌 발생 확률은 다음과 같이 표현된다.

(EQ7)

(EQ8)

과

는 두개의 가상 채널을 사용할 때 채널 i에서 발생할 수 있는 충돌의 두 가지 경우를 나타낸 것이다. 이것을 통해서 라우터(100) 내에서 충돌이 발생할 때의 지연 시간을 모델링 할 수 있다.

모델링에 사용할 라우터(100)의 각 채널은 2개의 가상 채널을 가지고, 선입 선출법(First-in-First-out)을 방법으로 크로스바를 통과한다고 가정한다. 각 채널에 들어오는 평균 패킷의 개수는

(k ∈ {E,W,S,N})라 하고, 채널에 들어오는 패킷 도착률

은 포와송 과정을 따를 때 도 5의 9번째 수식 (EQ9)와 같이 표현된다.

(EQ9)

이때

는 패킷이 큐 j에서 기다리는 평균 시간이며 다음과 같이 4개의 요소로 이루어진다.

1> 채널의 버퍼에서 기다리는 패킷의 평균 시간

2> 입력 포트 j의 가상 채널 두 개 모두 충돌이 발생해서 지연되는 시간.

3> 입력 포트 j의 가상 채널 중 한 개만 충돌이 발생해서 지연되는 시간.

4> 채널로 들어오는 패킷 때문에 발생하는 잔여 서비스 시간.

이것은 도 5의 10번째 수식 (EQ10)으로 표현된다.

(EQ10)

앞서 구한 평균 패킷 도착률을 나타낸 도 5의 9번째 수식 (EQ9)를 도 5의 1번째 수식 (EQ1)에 적용하면 다음과 같이 정리된다.

(EQ11)

는 단위 사이클당 채널 j로 들어오는 평균 패킷의 개수를 나타내므로, 도 5의 11번째 수식 (EQ11)을 다시 도 5의 9번째 수식 (EQEQ9)에 적용하면 큐 j에서 기다리는 패킷의 평균 시간

를 도 5의 12번째 수식 (EQ12)와 같이 나타낼 수 있다.

(EQ12)

웜홀 모델에서 플로우 f의 전체 전송 시간

는 링크와 라우터(100) 지연 시간

중 가장 긴 지연 시간에 종속된다.

(EQ13)

도 5의 13번째 수식 (EQ13)을 통해 라우터(100) 내의 지연 시간을 고려한 플로우의 지연 시간을 나타낼 수 있다. 본 발명의 일실시예에 따른 대역폭 할당 알고리즘은 이를 도 6 및 도 7에서 후술할 알고리즘에 적용하여 요구 시간을 충족시키며 각각의 링크에 최소의 대역폭을 할당한다.

도 6 및 도 7은 본 발명의 일실시예에 따른 대역폭 할당 알고리즘을 도시하고 있다.

종래의 웜홀 방식의 네트워크 온 칩은 링크의 대역폭을 할당할 때, 스케줄링 조건을 충족하는 동일한 크기의 대역폭을 전체 링크에 할당하였다. 이 방법은 링크를 개별적으로 보았을 때, 필요 이상의 대역폭을 가지는 링크로 인해 불필요한 파워를 소모하고 자원을 낭비하게 된다.

본 발명은 요구 지연 시간을 충족시키며 각각의 링크에 최소의 대역폭을 할당하는 알고리즘을 제공한다.

최소의 대역폭 할당 문제는 도 6과 같이 정의 할 수 있다.

이 문제를 해결하기 위해서 도 7과 같이 각 링크에 최소의 대역폭을 넣는 그리디(greedy) 알고리즘을 구성한다.

우선 모든 링크에 초기 대역폭을 할당하고 루프를 돌려가며 요구 시간 TfREQ를 충족하지 못하는 플로우를 찾는다.

도 7의 알고리즘의 줄1 내지 줄 3은 각 링크에 초기 대역폭을 할당하는 과정이다. 초기 대역폭은 스케줄링 조건에 따른 플로우의 대역폭을 플로우가 지나는 링크에 따라 가산하여 할당한다.

다음, TfREQ보다 큰 지연 시간 Tf를 가지는 플로우를 찾아낸다. 도 7의 알고리즘의 줄4 내지 줄 6은 앞서 찾은 플로우가 지나는 모든 링크에 d값만큼의 대역폭을 임시로 추가하여 패킷 전송 시간을 낮추는 과정이다.

도 7의 알고리즘의 줄7 내지 줄 10은 가장 긴 지연 시간을 찾아낸다.

도 7의 알고리즘의 줄 11은 가장 긴 지연 시간을 가지는 링크에 d만큼의 대역폭을 실제로 추가하고 임시로 추가했던 대역폭 값은 다시 원래 값으로 되돌린다.

그리고 다시 돌아가 대역폭이 할당된 전체 지연 시간이 요구 지연 시간 보다 작은지를 확인하고, 조건을 만족한다면 while문을 빠져나와 대역폭 할당을 완료한다.

이 과정을 모든 플로우에 대해 시행하면 알고리즘이 끝나면 각 링크에는 최소의 대역폭이 할당되고 모든 플로우는 요구 지연 시간을 충족하게 된다.

이상 상술한 내용을 정리하면, 네트워크 온 칩(10)은 메시 토폴로지(mesh topology)로 서로 연결된 라우터(100), 및 라우터(100)와 연결되어 라우터(100)를 통해 다른 프로세싱 엘리먼트(200)와 데이터를 주고 받는 프로세싱 엘리먼트(200)를 포함한다. 라우터(100)는 입력 채널에 2개의 가상 채널(virtual channel) 버퍼를 사용하며, 웜홀(wormhole) 라우팅을 사용한다.

라우터(100) 내의 충돌(contention) 지연, 버퍼 지연, 및 링크 지연에 기초하여, 각 데이터 플로우의 라우터 지연 시간을 산출하고, 라우터 지연 시간이 요구 지연 시간보다 긴 플로우가 지나는 링크에 기설정된 기본 대역폭보다 큰 추가 대역폭을 할당하되, 라우터 지연 시간이 요구 지연 시간보다 긴 플로우 중 라우터 지연 시간이 가장 긴 플로우가 지나는 링크에 추가 대역폭을 할당하며, 데이터 플로우의 전체 지연 시간이 요구 지연 시간보다 작은 값을 가지도록 추가 대역폭을 할당한다.

이를 위해 라우터(100)는 라우터 지연 시간이 요구 지연 시간보다 긴 플로우가 지나는 모든 링크에 소정의 대역폭 변위를 추가한 대역폭 값을 산출한 후, 라우터 지연 시간이 가장 긴 플로우가 지나는 링크에만 소정의 대역폭 변위를 추가한 대역폭 값인 추가 대역폭을 할당하고 나머지 링크에는 기본 대역폭을 할당한다.

도 8 내지 도 10은 본 발명의 일실시예에 따른 실험 결과를 도시하고 있다.

가상 채널 지연 모델을 통한 대역폭 할당을 위하여 C언어를 기반으로 한 시뮬레이터를 작성하였다. 본 시뮬레이터에서 구성한 네트워크 온 칩은 3x4의 2-D 메시로 구성되며 XY 라우팅 기법을 사용하는 이형(heterogeneous) 구조이다. 인접한 라우터(100)는 서로 다른 방향의 단일 방향(unidirectional) 링크로 연결되었다. 각 라우터(100)는 입력 채널에 2개의 가상 채널을 포함하며 입력된 패킷은 웜홀 라우팅 방식으로 목적지까지 전송된다.

링크 대역폭의 초기값은 스케줄링한 플로우에 따라 할당되며, 하나의 패킷은 500개의 16비트 플릿으로 구성된다. 스케줄링에 사용한 플로우들은 이형 구성에 의하여 대역폭과 요구하는 지연 시간이 서로 다르다.

도 8의 표는 실험에서 사용한 플로우의 특성을 보여주고 있다.

초기 대역폭은 링크에 따라 다르게 할당되며 라우터(100) 내에서의 버퍼 지연 시간과 충돌 지연 시간도 라우터(100)에 따라 다르다. 파이프라인 방식으로 패킷을 전송하는 네트워크에서 각 플로우가 지나는 링크에서의 지연 시간 중 가장 지배적인(dominant) 지연 시간을 통하여 해당 플로우의 전체 전송 시간을 구한다.

도 9는 플로우에 사용된 초기 지연 시간, 요구 지연 시간 및 제안하는 알고리즘을 통해 얻은 시뮬레이션 지연 시간을 보여주고 있다.

시뮬레이션을 통하여 얻은 지연 시간은 초기 지연 시간보다 더 작아짐을 볼 수 있으며, 모든 시뮬레이션 지연 시간이 요구 지연 시간보다 작은 값으로 되어 도 8의 요구 조건을 만족하는 것을 볼 수 있다.

도 10은 본 발명의 일실시예에 따른 라우터 지연 모델과 대역폭 할당 알고리즘을 통하여 네트워크 온 칩(10)의 각 링크에 할당한 대역폭을 구한 결과를 도시하고 있다.

할당한 전체 링크의 대역폭 합은 13.9Gb/sec 로 균일(Uniform) 할당 기법, 즉, 모든 링크에 동일한 대역폭을 할당하는 방법에 의한 대역폭 (41.8Gb/sec) 보다 66.7% 의 감소를 보인다.

즉, 적은 양의 대역폭 할당을 통해서 도 9에 도시되어 있는 바와 같이 요구 지연 시간을 충족시키는 네트워크를 구성할 수 있다.

대역폭 감소는 모델링한 네트워크 온 칩 구조가 이형라는 점도 원인이 된다. 각 플로우들은 서로 다른 값의 대역폭과 충족 요건을 가지고 있기 때문에, 필요없는 대역폭을 줄여 최소의 대역폭을 할당할 수 있다.

상술한 바와 같이, 본 발명은 가상 채널을 통해 네트워크 온 칩의 성능을 향상시키면서, 각 링크에 트래픽 조건에 따른 최소의 대역폭을 할당하는 알고리즘을 제공한다. 또한 라우터 내의 충돌 지연, 버퍼 지연, 및 링크 지연을 고려한 지연시간 모델을 통해 네트워크 온 칩의 스케줄링 조건을 만족시키는 최소의 대역폭을 할당한다.

가상 채널을 사용한 웜홀 라우터 구조에서 지연 시간을 모델링하고 본 발명의 일실시예에 따른 대역폭 할당 방법을 시뮬레이션한 결과, 스케쥴링에 따른 요구 지연 시간을 만족하면서 각 링크에 최소의 대역폭을 할당할 수 있었다. 3x4 메시 토폴로지에서 이형 스케줄링 하였을 때 균일 대역폭 할당보다 66.7%의 대역폭 감소를 확인할 수 있었으며 지연시간의 감소로 인해 성능 또한 향상됨을 알 수 있었다.

전술한 본 발명의 설명은 예시를 위한 것이며, 본 발명이 속하는 기술분야의 통상의 지식을 가진 자는 본 발명의 기술적 사상이나 필수적인 특징을 변경하지 않고서 다른 구체적인 형태로 쉽게 변형이 가능하다는 것을 이해할 수 있을 것이다. 그러므로 이상에서 기술한 실시예들은 모든 면에서 예시적인 것이며 한정적이 아닌 것으로 이해해야만 한다. 예를 들어, 단일형으로 설명되어 있는 각 구성 요소는 분산되어 실시될 수도 있으며, 마찬가지로 분산된 것으로 설명되어 있는 구성 요소들도 결합된 형태로 실시될 수 있다.

본 발명의 범위는 상기 상세한 설명보다는 후술하는 특허청구범위에 의하여 나타내어지며, 특허청구범위의 의미 및 범위 그리고 그 균등 개념으로부터 도출되는 모든 변경 또는 변형된 형태가 본 발명의 범위에 포함되는 것으로 해석되어야 한다.

10: 네트워크 온 칩
100: 라우터
200: 프로세싱 엘리먼트
110: 가상 채널 버퍼

Claims (10)

1. 네트워크 온 칩(Network-on-Chip) 시스템에 있어서,
   메시 토폴로지(mesh topology)로 서로 연결된 라우터; 및
   상기 라우터와 연결되어 상기 라우터를 통해 다른 프로세싱 엘리먼트와 데이터를 주고 받는 프로세싱 엘리먼트;를 포함하되,
   상기 라우터 내의 충돌(contention) 지연, 버퍼 지연, 및 링크 지연에 기초하여, 각 데이터 플로우의 라우터 지연 시간을 산출하고, 상기 라우터 지연 시간이 요구 지연 시간보다 긴 플로우가 지나는 링크에 기설정된 기본 대역폭보다 큰 추가 대역폭을 할당하되,
   상기 라우터는 상기 데이터 플로우의 전체 지연 시간이 상기 요구 지연 시간보다 작은 값을 가지도록 상기 추가 대역폭을 할당하는 네트워크 온 칩.
2. 제 1 항에 있어서,
   상기 라우터는 입력 채널에 2개의 가상 채널(virtual channel) 버퍼를 사용하는 네트워크 온 칩.
3. 제 1 항에 있어서,
   상기 라우터는 웜홀(wormhole) 라우팅을 사용하는 네트워크 온 칩.
4. 제 1 항에 있어서,
   상기 라우터는 상기 라우터 지연 시간이 요구 지연 시간보다 긴 플로우 중 상기 라우터 지연 시간이 가장 긴 플로우가 지나는 링크에 상기 추가 대역폭을 할당하는 네트워크 온 칩.
5. 삭제
6. 제 1 항에 있어서,
   상기 라우터는 상기 라우터 지연 시간이 요구 지연 시간보다 긴 플로우가 지나는 모든 링크에 소정의 대역폭 변위를 추가한 대역폭 값을 산출한 후, 상기 라우터 지연 시간이 가장 긴 플로우가 지나는 링크에만 상기 소정의 대역폭 변위를 추가한 대역폭 값인 상기 추가 대역폭을 할당하고 나머지 링크에는 상기 기본 대역폭을 할당하는 네트워크 온 칩.
7. 네트워크 온 칩(Network-on-Chip) 시스템에서의 대역폭 할당 방법 있어서,
   (a) 라우터 내의 충돌(contention) 지연, 버퍼 지연, 및 링크 지연에 기초하여, 각 데이터 플로우의 라우터 지연 시간을 산출하는 단계; 및
   (b) 상기 라우터 지연 시간이 요구 지연 시간보다 긴 플로우가 지나는 링크에 기설정된 기본 대역폭보다 큰 추가 대역폭을 할당하는 단계를 포함하되,
   상기 (b) 단계는 상기 데이터 플로우의 전체 지연 시간이 상기 요구 지연 시간보다 작은 값을 가지도록 상기 추가 대역폭을 할당하는 대역폭 할당 방법.
8. 제 7 항에 있어서,
   상기 (b) 단계는 상기 라우터 지연 시간이 요구 지연 시간보다 긴 플로우 중 상기 라우터 지연 시간이 가장 긴 플로우가 지나는 링크에 상기 추가 대역폭을 할당하는 대역폭 할당 방법.
9. 삭제
10. 제 7 항에 있어서,
    상기 (b) 단계는 상기 라우터 지연 시간이 요구 지연 시간보다 긴 플로우가 지나는 모든 링크에 소정의 대역폭 변위를 추가한 대역폭 값을 산출한 후, 상기 라우터 지연 시간이 가장 긴 플로우가 지나는 링크에만 상기 소정의 대역폭 변위를 추가한 대역폭 값인 상기 추가 대역폭을 할당하고 나머지 링크에는 상기 기본 대역폭을 할당하는 대역폭 할당 방법.

Images