1 |
1
온칩 네트워크의 자동 생성 방법에 있어서, 상기 온칩 네트워크의 설계 사양을 코딩한 레퍼런스 코드를 수행하여 상기 온칩에 포함된 모듈 상호 간의 통신량 및 통신 요구 방향을 나타내는 트래픽 그래프로 출력하는 단계와,상기 레퍼런스 코드 내에 있는 각 오퍼레이션을 상기 모듈 단위로 스케줄링하는 단계와,상기 스케줄링 결과로부터 상기 각 모듈사이의 통신 경로간의 충돌 여부를 판단하여 충돌(conflict) 경로 리스트를 추출하는 단계와,상기 트래픽 그래프와 상기 충돌 경로 리스트로부터 상기 통신 경로간에 충돌이 없고, 상기 통신량이 많은 모듈들을 인접 배치한 이진 트리를 생성하는 단계와,상기 생성된 이진 트리의 중간 노드들을 병합하여 상기 이진 트리를 최적화하는 단계와,상기 최적화된 이진 트리를 기반으로 온칩 네트워크를 생성하는 단계를 포함하는 것을 특징으로 하는 온칩 네트워크 자동 생성 방법
|
2 |
2
제1항에 있어서, 상기 레퍼런스 코드는 C코드 또는 SystemC 코드로 쓰여져 있는 알고리즘 단계의 설계 사양이 구현된 것을 특징으로 하는 온칩 네트워크 자동 생성 방법
|
3 |
3
제1항에 있어서, 상기 트래픽 그래프는 상기 모듈에 대응하는 노드, 상기 모듈 간의 통신 요구의 방향을 나타내는 방향성 에지(edge) 및 통신량을 표시하는 에지 웨이트(weight)로 구성된 것을 특징으로 하는 온칩 네트워크 자동 생성 방법
|
4 |
4
제1항에 있어서, 상기 충돌 경로 리스트의 추출단계는 상기 추출된 스케줄링 결과에서 각 통신 경로들 간의 시간 프레임을 비교하여 기준시간 이상 중복된 통신 경로를 추출하는 것을 특징으로 하는 온칩 네트워크 자동 생성 방법
|
5 |
5
제1항에 있어서, 상기 이진 트리의 생성단계는 a) 상기 충돌 경로 리스트에서 충돌이 있는 통신 경로의 각 노드를 연결하는 통신 경로들 중 상기 충돌이 있는 통신 경로를 제외한 통신 경로들로 구성된 충돌 노드 그래프를 구성하는 단계와,b) 상기 트래픽 그래프의 모든 노드들이 연결된 완전 그래프(perfect graph, PG)로부터 상기 충돌 노드 그래프(CG)를 감산 연산하여 비충돌 노드 그래프를 구성하는 단계와,c) 상기 트래픽 그래프와 상기 비충돌 노드 그래프의 AND 연산을 수행하는 단계와,d) 상기 연산의 수행 결과 최대 웨이트의 에지를 연결하는 두 노드를 클러스터링하여 하나의 노드로 만들고 상기 트래픽 그래프를 업데이트하는 단계와,e) 상기 두 노드의 클러스터링 결과에 따라 상기 충돌 경로 리스트를 업데이트하는 단계와,f) 상기 업데이트 결과에 따라 모든 노드들이 클러스터링 되었는지 여부를 판단하여 모든 노드들이 클러스터링 되지 않은 경우 상기 단계들(a 내지 e)을 다시 수행하는 단계와,g) 상기 수행된 노드 클러스터링 결과에 따라 이진 트리를 생성하는 단계를 포함하는 것을 특징으로 하는 온칩 네트워크 자동 생성 방법
|
6 |
6
제5항에 있어서, 상기 충돌 노드 그래프를 구성하는 단계(a)는 중복된 에지의 개수만큼 웨이트를 증가시키는 것을 특징으로 하는 온칩 네트워크 자동 생성 방법
|
7 |
7
제5항에 있어서, 상기 그래프들 간의 AND 연산을 하는 단계(c)는 각각 대응하는 노드 쌍을 연결하는 에지들 및 웨이트들 끼리의 곱을 통해 이루어지는 것을 특징으로 하는 온칩 네트워크 자동 생성 방법
|
8 |
8
제5항에 있어서, 상기 트래픽 그래프를 업데이트하는 단계(d)는 상기 클러스터링 된 두 노드에 연결되었던 에지들을 노드 별로 웨이트값을 합친 하나의 에지로 변경하는 단계를 포함하는 것을 특징으로 하는 온칩 네트워크 자동 생성 방법
|
9 |
9
제5항에 있어서, 상기 충돌 경로 리스트를 업데이트하는 단계(e)는 상기 클러스터링 된 노드 쌍의 통신 경로를 상기 리스트에서 삭제한 후 잔존 통신 경로들 간의 시간 프레임을 비교하여 기준시간 이상 중복된 통신 경로를 추출하는 것을 특징으로 하는 온칩 네트워크 자동 생성 방법
|
10 |
10
제5항에 있어서, 상기 이진 트리 생성단계(g)는 상기 노드 클러스터링의 최종 결과를 반영한 트래픽 그래프를 구성하는 각 노드들의 클러스터링 순서를 확인하는 단계와,상기 순서에 따라 상기 클러스터링 된 두 노드를 하위 노드로 갖는 상위 노드를 위치시켜 트리를 상향식으로 구성하는 단계와,상기 상위 노드가 포함된 상위 클러스터링에 대하여 다시 상위 트리를 상향식으로 구성하여 상기 트래픽 그래프의 모든 구성 노드들을 하나의 이진 트리로 생성하는 단계를 포함하는 것을 특징으로 하는 온칩 네트워크 자동 생성 방법
|
11 |
11
제1항에 있어서, 상기 이진 트리를 최적화하는 단계는 a) 상기 이진 트리를 구성하는 노드 중에서 종단 노드보다 한 단계 상위에 있는 제1 상위 노드와 상기 제1상위 노드보다 한 단계 상위에 있는 제2 상위 노드 간에 선정된 병합 방식들을 통해 노드 병합을 실행하는 단계와,b) 상기 노드 병합 결과를 기준으로 상기 병합 방식별로 통신 비용을 계산하여 최소 비용 해를 산출하는 단계와,c) 상기 최소 비용 해를 갖는 병합 방식을 적용한 결과를 바탕으로 상기 제1 상위 노드와 상기 제2 상위 노드를 재설정하는 단계와,d) 상기 재설정 결과를 바탕으로 상기 모든 제1 상위 노드들이 상기 노드 병합의 실행 단계를 거칠 때까지 상기 단계들(a 내지 c)을 반복하여 이진 트리를 최적화하는 단계를 포함하는 것을 특징으로 하는 온칩 네트워크 자동 생성 방법
|
12 |
12
제11항에 있어서, 상기 노드 병합 방식은 종단 노드보다 한 단계 상위에 있는 두 개의 제1 상위 노드들과 상기 제1상위 노드들보다 한 단계 상위에 있는 제2 상위 노드를 모두 병합하는 방식과, 상기 제2 상위 노드와 상기 두 개의 제1 상위 노드들 중 왼쪽 제1 상위 노드와 병합하는 방식과, 상기 제2 상위 노드와 상기 두 개의 제1 상위 노드들 중 오른쪽 제1 상위 노드와 병합하는 방식과, 상기 제2 상위 노드와 상기 두 개의 제1 상위 노드를 병합하지 않는 방식을 포함하는 것을 특징으로 하는 온칩 네트워크 자동 생성 방법
|
13 |
13
제11항에 있어서, 상기 통신 비용은 중간 노드의 홉수(hop count)와 각 노드들간의 통신량의 곱을 모두 합산한 것에 의해 산출되는 것을 특징으로 하는 온칩 네트워크 자동 생성 방법
|
14 |
14
제1항에 있어서, 상기 온칩 네트워크를 생성하는 단계는 상기 최적화된 이진 트리의 각 중간 노드를 상기 각 중간 노드에 연결된 브랜치(Branch) 개수만큼의 포트를 갖는 크로스바 스위치로 대치하여 온칩 네트워크로 생성하는 것을 특징으로 하는 온칩 네트워크 자동 생성 방법
|
15 |
15
제4항 또는 제9항에 있어서, 상기 기준시간을 변화시켜 상기 기준 시간별로 상기 충돌 경로 리스트를 추출하는 단계를 포함하는 것을 특징으로 하는 온칩 네트워크 자동 생성 방법
|