KR101800320B1 - 버스 프로토콜 기반의 네트워크 온 칩 시스템, 그 설계 방법 및 그 설계 방법에 관한 프로그램이 기록된 컴퓨터 판독가능 기록매체 - Google Patents
버스 프로토콜 기반의 네트워크 온 칩 시스템, 그 설계 방법 및 그 설계 방법에 관한 프로그램이 기록된 컴퓨터 판독가능 기록매체 Download PDFInfo
- Publication number
- KR101800320B1 KR101800320B1 KR1020160072372A KR20160072372A KR101800320B1 KR 101800320 B1 KR101800320 B1 KR 101800320B1 KR 1020160072372 A KR1020160072372 A KR 1020160072372A KR 20160072372 A KR20160072372 A KR 20160072372A KR 101800320 B1 KR101800320 B1 KR 101800320B1
- Authority
- KR
- South Korea
- Prior art keywords
- router
- nodes
- network
- topology
- chip system
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000000034 method Methods 0.000 title claims abstract description 42
- 238000013461 design Methods 0.000 title claims abstract description 26
- 230000001419 dependent effect Effects 0.000 claims abstract description 4
- 238000004891 communication Methods 0.000 claims description 30
- 238000013507 mapping Methods 0.000 claims description 5
- 238000000638 solvent extraction Methods 0.000 claims description 4
- 238000004422 calculation algorithm Methods 0.000 claims description 2
- 238000004590 computer program Methods 0.000 claims description 2
- 235000008694 Humulus lupulus Nutrition 0.000 description 6
- 230000006870 function Effects 0.000 description 5
- 238000010586 diagram Methods 0.000 description 2
- 238000005516 engineering process Methods 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 238000005457 optimization Methods 0.000 description 2
- 230000008569 process Effects 0.000 description 2
- 238000012545 processing Methods 0.000 description 2
- 230000005540 biological transmission Effects 0.000 description 1
- 238000004364 calculation method Methods 0.000 description 1
- 238000007796 conventional method Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 230000006872 improvement Effects 0.000 description 1
- 230000007774 longterm Effects 0.000 description 1
- 230000000399 orthopedic effect Effects 0.000 description 1
- 230000009467 reduction Effects 0.000 description 1
- 238000004904 shortening Methods 0.000 description 1
- 238000001308 synthesis method Methods 0.000 description 1
Images
Classifications
-
- G06F17/509—
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F15/00—Digital computers in general; Data processing equipment in general
- G06F15/76—Architectures of general purpose stored program computers
- G06F15/78—Architectures of general purpose stored program computers comprising a single central processing unit
- G06F15/7807—System on chip, i.e. computer system on a single chip; System in package, i.e. computer system on one or more chips in a single package
-
- G06F17/5077—
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- General Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- Microelectronics & Electronic Packaging (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
본 발명의 일 실시예에 따르는, 버스 프로토콜 기반의 네트워크 온 칩 시스템 설계 방법은 (a) 복수의 노드와 라우터를 포함하는 네트워크 온 칩 시스템에 대하여, 버스 프로토콜 주소에 기반한 주소 네트워크 토폴로지를 설계하는 단계; 및 (b) 상기 주소 네트워크 토폴로지에 기반하여, 상기 주소 네트워크 토폴로지의 라우터에 종속된 데이터 네트워크 토폴로지를 설계하는 단계;를 포함한다.
Description
본 발명은 버스 프로토콜 기반의 네트워크 온 칩 시스템, 그 설계 방법 및 그 설계 방법에 관한 프로그램이 기록된 컴퓨터 판독가능 기록매체에 관한 것으로서, 보다 상세하게는, 버스 프로토콜 기반 IP를 재사용할 수 있는 네트워크 온 칩 설계에 있어, 성능 개선과 설계시간 단축을 달성하기 위한 버스 프로토콜 기반의 네트워크 온 칩 시스템, 그 설계 방법 및 그 설계 방법에 관한 프로그램이 기록된 컴퓨터 판독가능 기록매체에 관한 것이다.
다중 프로세서-온-칩(Multi-Processor SoC, MPSoC)에서의 코어 및 IP 개수 증가 추세에 따라, 온-칩 인터 커넥트 구조 설계가 중요해지고 있다. 전통적인 버스 구조의 경우, 연결되는 컴포넌트 수가 증가함에 따른 병목현상으로 인해 확장성에 한계가 있다. 이러한 문제를 해결하기 위해서 병렬처리와 확장성에 유리한 네트워크-온-칩 (Network-on-Chip, NoC)이 유망한 인터커넥션 아키텍처 기술로 주목 받고 있다.
하지만 현재 표준화된 NoC 프로토콜의 부재 및 기존 버스 프로토콜로 설계된 legacy IP의 호환성 문제 등으로 인해 NoC의 성능을 제대로 활용하지 못하고 있다. 특히 확장성에 초점을 맞춘 NoC 설계는 지연시간에 매우 민감한 디스플레이 IP 및 실시간 처리가 필요한 어플리케이션에 대하여 설계의 검증 및 데드라인 충족하기 위한 최적화 과정을 반드시 필요로 한다.
NoC에서의 지연시간은 데이터가 경과하는 홉(즉, 노드) 수와 직접적인 연관이 있다. 그에 따라, 지연시간을 최소화하기 위해 이분 그래프 (Bipartite graph)를 이용한 라우터 할당 기법, MCF (Multicommodity Flow) 기반의 경로 계산을 적용한 토폴로지 합성 방법, 링크 추가를 통한 대체 경로 생성 방법 및 메시지 스케줄링을 적용하여 지연시간을 개선하는 방법 등이 제시되고 있다. 그러나, 이러한 종래의 기법들은 경로 및 링크의 특성을 반영한 설계법을 제안하고 있기는 하나, 버스 프로토콜 호환 가능한 NoC에서 버스 프로토콜의 트랜잭션 지연시간 최적화를 위한 방법에 대해서는 제안하고 있지 않다.
본 발명은 버스 프로토콜 호환 가능한 네트워크 온 칩 시스템 설계 시, 데이터 네트워크 토폴로지와 주소 네트워크 토폴로지를 구분하여 설계함으로써, 지연시간 증가 문제를 최소화하는 것을 목적으로 한다.
본 발명의 일 실시예에 따르는, 버스 프로토콜 기반의 네트워크 온 칩 시스템 설계 방법은 (a) 복수의 노드와 라우터를 포함하는 네트워크 온 칩 시스템에 대하여, 버스 프로토콜 주소에 기반한 주소 네트워크 토폴로지를 설계하는 단계; 및 (b) 상기 주소 네트워크 토폴로지에 기반하여, 상기 주소 네트워크 토폴로지의 라우터에 종속된 데이터 네트워크 토폴로지를 설계하는 단계;를 포함한다.
본 발명의 다른 실시예에 따르는, 버스 프로토콜 기반의 네트워크 온 칩 시스템은, 복수의 노드와 복수의 라우터를 포함하되, 상기 복수의 노드와 복수의 라우터는 별도로 설계된 주소 네트워크 토폴로지와 데이터 네트워크 토폴로지에 연결되되, 상기 데이터 네트워크 토폴로지는, 버스 프로토콜 주소에 기반한 상기 주소 네트워크 토폴로지의 라우터에 종속되도록 설계된다.
본 발명은 버스 프로토콜 기반 IP에 대한 주소 네트워크 토폴로지와 데이터 네트워크 토폴로지를 구분하여 설계함으로써, 주소 네트워크 토폴로지에서는 노드 수의 최소화를 달성하고, 데이터 전송량이 상대적으로 훨씬 많은 데이터 네트워크 토폴로지에서는 경로 충돌 문제를 해결함으로써 경로 다양성을 보장할 수 있다.
이에 따라, 버스 프로토콜 기반으로 구성된 IP를 이용한 네트워크 온 칩 시스템의 성능 개선(즉, 지연시간 단축)을 달성할 수 있으며, 설계시간 단축을 가져올 수 있다.
도 1은 본 발명의 일 실시예에 따르는 네트워크 온 칩 시스템의 구조도이다.
도 2 내지 도 4는 본 발명의 일 실시예의 네트워크 온 칩 시스템 설계 중 주소 네트워크 토폴로지 설계 단계를 도식화한 개념도이다.
도 5는 본 발명의 일 실시예에 따르는 네트워크 온 칩 시스템 설계 방법에 대한 순서도이다.
도 6은 본 발명의 일 실시예에 따르는 주소 네트워크 토폴로지 설계 단계를 구체화한 순서도이다.
도 7은 본 발명의 일 실시예에 따르는 데이터 네트워크 토폴로지 설계 단계를 구체화한 순서도이다.
도 2 내지 도 4는 본 발명의 일 실시예의 네트워크 온 칩 시스템 설계 중 주소 네트워크 토폴로지 설계 단계를 도식화한 개념도이다.
도 5는 본 발명의 일 실시예에 따르는 네트워크 온 칩 시스템 설계 방법에 대한 순서도이다.
도 6은 본 발명의 일 실시예에 따르는 주소 네트워크 토폴로지 설계 단계를 구체화한 순서도이다.
도 7은 본 발명의 일 실시예에 따르는 데이터 네트워크 토폴로지 설계 단계를 구체화한 순서도이다.
아래에서는 첨부한 도면을 참조하여 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자가 용이하게 실시할 수 있도록 본 발명의 실시예를 상세히 설명한다. 그러나 본 발명은 여러 가지 상이한 형태로 구현될 수 있으며 여기에서 설명하는 실시예에 한정되지 않는다. 그리고 도면에서 본 발명을 명확하게 설명하기 위해서 설명과 관계없는 부분은 생략하였으며, 명세서 전체를 통하여 유사한 부분에 대해서는 유사한 도면 부호를 붙였다.
명세서 전체에서, 어떤 부분이 다른 부분과 "연결"되어 있다고 할 때, 이는 "직접적으로 연결"되어 있는 경우뿐 아니라, 그 중간에 다른 소자를 사이에 두고 "전기적으로 연결"되어 있는 경우도 포함한다. 또한 어떤 부분이 어떤 구성요소를 "포함"한다고 할 때, 이는 특별히 반대되는 기재가 없는 한 다른 구성요소를 제외하는 것이 아니라 다른 구성요소를 더 포함할 수 있는 것을 의미한다.
본 발명의 일 실시예에 따르는 버스 프로토콜 기반의 네트워크 온 칩 시스템 설계 방법은 컴퓨터 장치에 의해 수행될 수 있는 것으로서, 메모리에 저장된 네트워크 온 칩 시스템 설계를 위한 컴퓨터 프로그램을 프로세서가 수행함으로써 실행될 수 있다. 이때, 컴퓨터 장치는 다양한 장치나 휴대용 단말기로 구현될 수 있다. 여기서, 컴퓨터 장치는 예를 들어, 웹 브라우저(WEB Browser)가 탑재된 노트북, 데스크톱(desktop), 랩톱(laptop) 등을 포함하고, 휴대용 단말기는 예를 들어, 휴대성과 이동성이 보장되는 무선 통신 장치로서, IMT(International Mobile Telecommunication)-2000, CDMA(Code Division Multiple Access)-2000, W-CDMA(W-Code Division Multiple Access), Wibro(Wireless Broadband Internet), LTE(Long Term Evolution) 통신 기반 단말, 스마트폰, 태블릿 PC 등과 같은 모든 종류의 핸드헬드(Handheld) 기반의 무선 통신 장치를 포함할 수 있다.
이하, 도면을 통하여 본 발명의 일 실시예에 대하여 구체적으로 설명하도록 한다.
도 1을 참조하면, 본 발명의 일 실시예는 복수의 노드(100)(즉, 코어)와 라우터(200)를 포함하여 구성되되, 주소 네트워크 토폴로지와 데이터 네트워크 토폴로지가 구분되어 설계될 수 있다. 이때, 주소 네트워크 토폴로지란 버스 프로토콜 기반의 IP 주소 정보와 제어정보를 전송하는 네트워크 토폴로지이며, 데이터 네트워크 토폴로지란 주소 주소 및 제어정보가 아닌 다른 실질적인 데이터들을 전송하는 네트워크 토폴로지를 의미한다.
이때, 각 노드(100)들은 버스 프로토콜 기반의 고유 IP 주소(IP1 ~ IP8)를 가지며, 주소 네트워크 토폴로지 내에서 라우터(200)를 통하여 계층적인 구조로 조직화된다. 또한, 데이터 네트워크의 입력포트(300) 및 출력포트(400)와의 연결을 통해 데이터 네트워크 통신을 수행한다. 각 노드(100)들은 네트워크 인터페이스(NI : Network Interface)를 통해 주소 및 데이터 네트워크 토폴로지와 호환될 수 있다.
이와 같이 본 발명의 일 실시예는 주소 네트워크와 데이터 네트워크를 서로 구분하여 이종 토폴로지로 설계함으로써, 시스템 연산의 지연시간을 최소화하고 설계시간 단축을 제공할 수 있다.
이러한 효과를 제공하기 위한 이종 토폴로지 설계문제는 아래 수학식의 TG() 함수를 찾는 문제로 귀결된다.
여기서, G(V,E)는 노드(100) 간의 통신을 나타내는 커뮤니케이션 추적 그래프(Communication Trace Graph) 값으로서, V는 노드(100)를, e는 노드(100)가 데이터를 전송하는 통신을 의미한다. 그리고, AT(U,R,F)는 주소 네트워크 토폴로지 그래프 값을 의미하며, U는 노드(100) 및 IP를 나타내고, R은 해당 토폴로지에 존재하는 각각의 라우터(200)를 나타내며, F는 노드(100)와 라우터(200) 사이의 연결 또는 라우터(200) 간의 연결을 나타낸다. 또한, DT(U,C,F)는 데이터 네트워크 토폴로지 그래프 값을 의미하며, U는 노드(100) 및 IP를 나타내고, C는 해당 토폴로지 내의 크로스바(cross-bar)를 의미하며, F는 코어와 크로스바 간의 연결 또는 크로스바 간의 연결을 나타낸다.
이때, TG() 함수는 다음과 같은 세가지 조건을 만족해야 한다.
첫 번째 조건으로서, TG() 함수는 주소 네트워크에서의 지연시간은 주로 연산시 거쳐가야만 하는 노드(100)의 개수의 영향을 받으므로 총 노드(100) 개수를 최소화시키도록 구성되어야 한다. 총 노드(100) 개수에 대한 수학식은 아래와 같다.
여기서, BW(ei , j)는 i노드(100)가 j 노드(100)로 보내는 통신의 대역폭을 의미하며, CV(ei, j)는 한 번의 통신시 전송할 수 있는 최대 데이터량을 의미하고, hops(ei, j)는 i 노드(100)에서 j 노드(100)까지 통신시 거쳐가는 노드(100)의 개수를 의미한다.
두 번째 조건으로서, TG() 함수는 데이터 네트워크에서 경로 충돌을 최소화하기 위해 각 링크에 중복되는 통신의 수를 최소화시킬 수 있는 방향으로 데이터 네트워크 토폴로지를 설계해야 한다.
세 번째 조건으로서, 주소 정보를 주소 네트워크가 갖고 있기 때문에, 데이터 네트워크의 경로 설정을 주소 네트워크에서 제어해야만 한다. 이러한 경우, 주소 네트워크에서의 라우터(200)들이 데이터 네트워크를 분산 제어할 수 있어야 한다.
본 발명의 일 실시예에 따르는 네트워크 온 칩 시스템은 상술한 세 가지의 조건을 만족시키기 위한 TG() 함수를 기반으로 설계된다.
이하, 상술한 세 가지 조건을 만족시키기 위한 버스 프로토콜 기반의 네트워크 온칩 시스템 설계 방법에 대하여 도 2 내지 도 7을 참조하여 구체적으로 설명하도록 한다.
먼저, 도 5를 참조하면, 본 발명의 일 실시예에 따르는 네트워크 온 칩 시스템 설계 방법은 두 가지 단계로 구성된다.
즉, 버스 프로토콜 주소에 기반한 주소 네트워크 토폴로지를 설계하는 단계(S100) 후, 주소 네트워크 토폴로지에 기반하여 데이터 네트워크 토폴로지를 설계하는 단계(S200)로 진행된다.
먼저, 주소 네트워크 토폴로지를 설계하는 방법에 대하여 도 2 내지 4 및 도 6을 참조하여 설명하도록 한다.
주소 네트워크 토폴로지 설계 단계는 네트워크 온 칩 시스템 내의 복수의 노드(100)들 간의 전체 통신량이 최소화되도록 (예를 들어, 기 설정된 값보다 적도록) 각 라우터(200)마다 노드(100)를 할당하도록 수행된다.
이때, 트리 구조 기반의 토폴로지 기법을 통해 라우터(200)에 대한 노드(100) 할당이 수행될 수 있다. 트리 토폴로지는 노드(100) 수를 최적화함과 동시에 확장 가능한 솔루션을 제공할 수 있는 정형적인 토폴로지이다. 트리 토폴로지는 계층적으로 구성되는데, 노드(100)에서 상위 라우터(200)로, 상위 라우터(200)에서 최상위 라우터(200)로 한 레벨씩 통신이 지나갈 때마다 홉(hop) 수가 증가되기 때문에, 상위 레벨을 지나가는 통신을 줄이는 것이 전체 홉 수 감소에 매우 효과적인 설계법이 된다. 트리 토폴로지의 홉 수는 다음과 같은 수학식으로 도출될 수 있다.
여기서 LHei , j는 ei , j가 경과하는 상위 라우터(200)의 레벨, LLei , j는 하위 라우터(200)의 레벨을 나타낸다.
먼저, 전체 통신량이 최소화되도록 복수의 노드(100)를 그룹핑한다(S110). 이때, 각 노드(100)들 간의 통신 루트 또는 통신량에 관한 정보를 나타내는 커뮤니케이션 추적 그래프(Communication Trace Graph, CTG)값을 기초로 노드(100)들을 그룹핑할 수 있다. 특히, CTG를 다수의 그래프로 분할 하여 트리 토폴로지로 매핑하였을 때 서로 다른 서브 그래프로 분할되는 통신은 상위 라우터(200)를 지나가게 되므로 홉 수가 증가하게 될 수 있다. 이에 따라, 통신량 최소화를 위하여 균등 그래프 분할 (Balanced graph partitioning) 기반의 알고리즘을 통하여 노드(100)들을 그룹핑할 수 있다.
구체적으로, 먼저, 도 2와 같은 형태의 복수의 노드(100) 구조를 가정한다. 이때, 화살표는 노드(100) 간 통신을 의미하는 것으로서, 예를 들어, 노드(100) 1은 노드(100) 6으로 데이터를 전송하는 것을 의미한다. 이어서, 도 3과 같이 그룹핑을 수행한다. 이때, 각 그룹 간에는 각 노드(100)들 간에 설정된 통신 루트에 기인하여 그룹 간을 연결하도록 발생되는 통신 루트(즉, 외부 엣지)가 발생된다. 예를 들어, 노드(100) 1, 2, 6이 포함된 그룹은 노드(100) 9, 10, 11이 포함된 그룹에 대하여 3개의 외부 엣지가 발생된다. 이때, 이러한 외부 엣지가 최소화되도록, 즉, 임의로 그룹핑된 경우의 외부 엣지보다 적은 외부 엣지를 갖도록 그룹핑을 수행한다. 도 3의 경우, 노드(100) 6이 타 노드(100)에 대해 가능 많은 통신루트를 갖기 때문에, 노드(100) 6을 중심으로 그룹핑이 수행될 수 있다. 또한, 그룹핑은 가장 많은 통신량을 보유하고 있는 노드(100)(즉, 통신 루트의 개수가 미리 설정된 개수 이상인 노드(100))가 포함된 그룹은 타 그룹보다 적은 개수의 노드(100)를 포함하도록 그룹핑될 수도 있다. 예를 들어, 통신량이 매우 많은 노드(100)가 속한 그룹의 노드(100) 개수는 1-2개이되, 다른 그룹의 노드(100) 개수는 3개 이상이 될 수도 있다.
이어서, 각 그룹에 대하여 각 라우터(200)를 할당하고, 하위 라우터(200)에 대해서는 상위 라우터(200)를 할당한다(S120).
이때, 노드(100)들 간의 전체 통신량을 최소화하는 트리 토폴로지 생성을 위해, 우선적으로 전체 노드(100) 개수(n)와 라우터(200)의 포트 수(p)에 따라 수학식 2를 최소화하는 그래프 분할을 통해 라우터(200)를 할당할 수 있다.
즉, 최상위 라우터(200)는 그보다 높은 상위 라우터(200)로의 링크가 없으므로, 최상위 라우터(200)에 연결 가능한 하위 라우터(200)는 (p, 1+p/n) - 그래프 분할을 통하여 생성할 수 있다. 반면 하위 라우터(200)에 대한 최하위 라우터(200)는 (p-1, 1+(p-1)/n)-그래프 분할을 통하여 생성할 수 있다. 이때, 하나의 최하위 라우터(200)에 배치되는 최대 노드(100)의 수는 아래 수학식 4와 같다.
그래프 분할을 각 하위 라우터(200)에 포함되는 노드(100)의 개수가 p-1이하가 될 때까지 수행하며, 결국 리프 라우터(200)에는 p-1이하의 노드(100)가 연결된 트리 구조 기반 정형 토폴로지가 구성될 수 있다. 그에 따라, 도 4와 같은 노드(100), 하위 라우터(200a), 상위 라우터(200b) 구조가 구성될 수 있다.
이어서, 트리구조 토폴로지의 최적화를 수행한다(S130). 구체적으로, 노드(100)가 연결되지 않은 라우터(200)는 제거한다. 또는, 통합이 가능한 리프 라우터(200)들은 하나의 리프 라우터(200)로 통합한다. 예를 들어, 라우터(200)의 개수가 노드(100)의 개수와 같거나 큰 라우터(200)와 노드(100) 조합들을 서로 통합하여 하나의 라우터(200) 및 노드(100) 조합으로 생성한다.
이상, 상술한 방식을 통하여 버스 프로토콜 기반의 주소 네트워크 토폴로지 설계를 완료한다.
이어서, 도 7을 참조하여, 데이터 네트워크 토폴로지 설계 방법에 대하여 구체적으로 설명하도록 한다.
데이터 네트워크 토폴로지는 어느 한 라우터(200)부터 마지막 라우터(200)까지 각 라우터(200)마다 순차적으로 수행되어 설계된다. 이때, 각 라우터(200)마다 베니스 토폴로지를 기반으로 한 네트워크 토폴로지가 설계된다. 데이터 네트워크는 경로 충돌을 최소화시키기 위해 경로의 다양성을 보장하여야 하는데, 이를 위해서는 분산 제어가 가능한 데이터 네트워크 설계가 필요하다. 그러므로, 베니스(Benes) 토폴리지 기반의 데이터 네트워크 설계가 수반되어야 한다.
먼저, 어느 한 라우터(200)에 대하여 베니스 토폴로지를 생성한다(S210). 이때의 베니스 토폴로지는 입력과 출력의 개수가 각각 n개인 베니스 토폴로지이다.
한편, 생성된 베니스 토폴로지를 2개의 서브 베니스 토폴로지가 구성되는 형태로 분할 생성한다(S220). 예를 들어, 입력과 출력의 개수가 각각 n/2 개인 서브 베니스 토폴로지 2개로 분할하여 생성할 수 있다. (n =2a, a는 자연수)
이어서, 데이터 네트워크의 입력포트(300)와 데이터 네트워크의 출력포트(400)를 베니스 토폴로지에 매핑한다(S230). 즉, 2개의 서브 베니스 토폴로지의 입력과 데이터 네트워크 입력포트(300) 간의 매칭 및 2개의 서브 베니스 토폴로지의 출력과 데이터 네트워크 출력포트(400) 간의 매칭의 경우의 수가 여러가지가 도출될 수 있는데, 어느 한 가지 경우에 대한 매칭을 수행한다.
이어서, 크로스바 비용(cross-bar cost)이 최소화되었는지 판단한다(S240). 크로스바 스위치는 네트워크 상에서 입력단과 출력단 연결을 위해 조직되는 연결구조를 의미하는 것으로서, S240단계는 불필요한 크로스바 스위치는 제거하고 가장 비용 효율적인 매핑 구조를 도출하기 위해 수행된다.
만약 최소 비용이 아닌 경우, 베니스 토폴로지의 입력, 출력과 데이터 네트워크의 입력포트(300), 출력포트(400) 간의 매핑 조합을 다른 경우의 수로 변경한다(S250).
S240 단계를 통과한 경우, 서브 베니스 토폴로지가 2 x 2 (입력 및 출력의 개수가 2개) 크기인지 판단하고(S260), 그렇지 않은 경우, 서브 베니스 토폴로지에 대한 분할을 수행하여, 서브 베니스 토폴로지의 크기가 2 x 2가 될 때까지, S220 및 S260 단계를 반복 수행한다.
이를 통해 베니스 토폴로지가 한 라우터(200)에 대하여 완성된 경우, 아직 베니스 토폴로지가 생성되지 않은 다른 라우터(200)가 있는지 확인한다(S270). 만약 다른 라우터(200)가 남아 있는 경우, 다른 라우터(200)에 대하여 S210 단계 내지 S260 단계를 반복수행한다(S280).
이를 통하여 전체 라우터(200)에 대하여, 각 라우터(200)에 종속된 베니스 토폴로지가 생성된 경우, 데이터 네트워크 입력포트(300) 및 출력포트(400)에 대한 스테이지를 생성함으로써, 네트워크 온 칩 설계를 완료한다(S290).
본 발명의 일 실시예는 컴퓨터에 의해 실행되는 프로그램 모듈과 같은 컴퓨터에 의해 실행가능한 명령어를 포함하는 기록 매체의 형태로도 구현될 수 있다. 컴퓨터 판독 가능 매체는 컴퓨터에 의해 액세스될 수 있는 임의의 가용 매체일 수 있고, 휘발성 및 비휘발성 매체, 분리형 및 비분리형 매체를 모두 포함한다. 또한, 컴퓨터 판독가능 매체는 컴퓨터 저장 매체를 포함할 수 있다. 컴퓨터 저장 매체는 컴퓨터 판독가능 명령어, 데이터 구조, 프로그램 모듈 또는 기타 데이터와 같은 정보의 저장을 위한 임의의 방법 또는 기술로 구현된 휘발성 및 비휘발성, 분리형 및 비분리형 매체를 모두 포함한다.
본 발명의 방법 및 시스템은 특정 실시예와 관련하여 설명되었지만, 그것들의 구성 요소 또는 동작의 일부 또는 전부는 범용 하드웨어 아키텍쳐를 갖는 컴퓨터 시스템을 사용하여 구현될 수 있다.
전술한 본 발명의 설명은 예시를 위한 것이며, 본 발명이 속하는 기술분야의 통상의 지식을 가진 자는 본 발명의 기술적 사상이나 필수적인 특징을 변경하지 않고서 다른 구체적인 형태로 쉽게 변형이 가능하다는 것을 이해할 수 있을 것이다. 그러므로 이상에서 기술한 실시예들은 모든 면에서 예시적인 것이며 한정적이 아닌 것으로 이해해야만 한다. 예를 들어, 단일형으로 설명되어 있는 각 구성 요소는 분산되어 실시될 수도 있으며, 마찬가지로 분산된 것으로 설명되어 있는 구성 요소들도 결합된 형태로 실시될 수 있다.
본 발명의 범위는 상기 상세한 설명보다는 후술하는 특허청구범위에 의하여 나타내어지며, 특허청구범위의 의미 및 범위 그리고 그 균등 개념으로부터 도출되는 모든 변경 또는 변형된 형태가 본 발명의 범위에 포함되는 것으로 해석되어야 한다.
100: 노드 200: 라우터
300: 데이터 네트워크 입력포트
400 : 데이터 네트워크 출력포트
300: 데이터 네트워크 입력포트
400 : 데이터 네트워크 출력포트
Claims (14)
- 컴퓨터 장치에 의해 수행되는, 버스 프로토콜 기반의 네트워크 온 칩 시스템 설계 방법에 있어서,
(a) 복수의 노드와 라우터를 포함하는 네트워크 온 칩 시스템에 대하여, 버스 프로토콜 주소에 기반한 주소 네트워크 토폴로지를 설계하는 단계; 및
(b) 상기 주소 네트워크 토폴로지에 기반하여, 상기 주소 네트워크 토폴로지의 라우터에 종속된 데이터 네트워크 토폴로지를 설계하는 단계;를 포함하며,
상기 (a) 단계는,
(a-1) 상기 복수의 노드 간의 통신 루트에 관한 정보를 기준으로 상기 복수의 노드를 복수의 그룹으로 그룹핑하는 단계; 및
(a-2) 상기 복수의 그룹과 복수의 라우터가 서로 매핑되도록 상기 각 그룹에 대하여 라우터를 할당하는 단계;를 포함하는, 버스 프로토콜 기반의 네트워크 온 칩 시스템 설계 방법. - 제 1 항에 있어서,
상기 (a) 단계는,
상기 네트워크 온 칩 시스템 내의 복수의 노드들 간의 전체 통신량이 기 설정된 값보다 적도록 각 라우터마다 노드를 할당하는 것인, 버스 프로토콜 기반의 네트워크 온 칩 시스템 설계 방법. - 제 2 항에 있어서,
상기 (a) 단계는,
트리 구조 기반의 토폴로지 기법으로 각 라우터에 대하여 상기 복수의 노드들을 할당하는 것인, 버스 프로토콜 기반의 네트워크 온 칩 시스템 설계 방법. - 제 2 항에 있어서,
상기 (a) 단계는,
균등 그래프 분할 (Balanced graph partitioning) 기반의 알고리즘을 통하여 설계하는 것인, 버스 프로토콜 기반의 네트워크 온 칩 시스템 설계 방법. - 삭제
- 제 1 항에 있어서,
상기 (a-1) 단계는,
상기 복수의 노드 간에 설정된 통신 루트에 기인하여 상기 복수의 그룹 간을 연결하도록 발생되는 통신 루트의 개수가 임의로 그룹핑된 경우의 통신 루트의 개수보다 적도록 그룹핑하는 것인, 버스 프로토콜 기반의 네트워크 온 칩 시스템 설계 방법. - 제 1 항에 있어서,
상기 (a-1) 단계는,
상기 통신 루트의 개수가 미리 설정된 개수 이상인 노드가 포함된 그룹은 타 그룹보다 적은 개수의 노드를 포함하도록 그룹핑하는 것인, 버스 프로토콜 기반의 네트워크 온 칩 시스템 설계 방법. - 제 1 항에 있어서,
상기 (a) 단계는,
(a-3) 상기 (a-2) 단계 후, 각 라우터에 대하여 상위 라우터를 할당하는 단계;
(a-4) 노드가 연결되지 않은 라우터를 제거하는 단계; 및
(a-5) 라우터의 개수가 노드의 개수와 같거나 큰 라우터와 노드 조합들을 서로 통합하여 하나의 라우터 및 노드 조합으로 생성하는 단계;를 더 포함하는, 버스 프로토콜 기반의 네트워크 온 칩 시스템 설계 방법. - 제 1 항에 있어서,
상기 (b) 단계는,
어느 한 라우터부터 마지막 라우터까지 각 라우터마다 순차적으로 데이터 네트워크 토폴로지를 설계하는 것인, 버스 프로토콜 기반의 네트워크 온 칩 시스템 설계 방법. - 제 9 항에 있어서,
상기 (b) 단계는,
각 라우터마다 베니스 토폴로지를 기반으로 한 네트워크 토폴로지를 설계하는 것인, 버스 프로토콜 기반의 네트워크 온 칩 시스템 설계 방법. - 제 10 항에 있어서,
상기 (b) 단계는,
(b-1) 입력과 출력의 개수가 각각 n개인 베니스 토폴로지를 설계하되, 입력과출력의 개수가 각각 n/2 개인 서브 베니스 토폴로지 2개로 분할하여 설계하는 단계; (n =2a, a는 자연수) 및
(b-2) 데이터 네트워크의 입력포트와 데이터 네트워크의 출력포트를 상기 베니스 토폴로지에 매핑하고, 복수의 매핑의 경우의 수 중 가장 적은 비용을 나타내는 경우의 매핑을 선택하는 단계;
를 포함하는, 버스 프로토콜 기반의 네트워크 온 칩 시스템 설계 방법. - 제 11 항에 있어서,
상기 (b) 단계는,
(b-3) 상기 (b-2) 단계 후, 상기 서브 베니스 토폴로지에 대하여 상기 (b-1) 및 (b-2) 단계를 반복 수행하되, 입력과 출력의 개수가 각각 2개가 될 때까지 수행하는 단계; 및
(b-4) 상기 복수의 노드들이 연결된 데이터 네트워크 입력포트와 출력포트를 생성하는 단계;를 더 포함하는, 버스 프로토콜 기반의 네트워크 온 칩 시스템 설계 방법. - 제 1 항 내지 제 4 항 및 제 6 항 내지 제 12 항 중 어느 한 항에 따르는 버스 프로토콜 기반의 네트워크 온 칩 시스템 설계 방법을 수행하기 위한 컴퓨터 프로그램이 저장된 컴퓨터 판독가능 기록매체.
- 버스 프로토콜 기반의 네트워크 온 칩 시스템에 있어서,
복수의 노드와 복수의 라우터를 포함하되,
상기 복수의 노드와 복수의 라우터는 별도로 설계된 주소 네트워크 토폴로지와 데이터 네트워크 토폴로지에 연결되되,
상기 주소 네트워크 토폴로지는,
상기 복수의 노드 간의 통신 루트에 관한 정보를 기준으로 상기 복수의 노드가 복수의 그룹으로 그룹핑된 후, 상기 복수의 그룹과 복수의 라우터가 서로 매핑되도록 상기 각 그룹에 대하여 라우터가 할당되도록 설계된 것이며,
상기 데이터 네트워크 토폴로지는, 버스 프로토콜 주소에 기반한 상기 주소 네트워크 토폴로지의 라우터에 종속되도록 설계된 것인, 버스 프로토콜 기반의 네트워크 온 칩 시스템.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020160072372A KR101800320B1 (ko) | 2016-06-10 | 2016-06-10 | 버스 프로토콜 기반의 네트워크 온 칩 시스템, 그 설계 방법 및 그 설계 방법에 관한 프로그램이 기록된 컴퓨터 판독가능 기록매체 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020160072372A KR101800320B1 (ko) | 2016-06-10 | 2016-06-10 | 버스 프로토콜 기반의 네트워크 온 칩 시스템, 그 설계 방법 및 그 설계 방법에 관한 프로그램이 기록된 컴퓨터 판독가능 기록매체 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| KR101800320B1 true KR101800320B1 (ko) | 2017-11-22 |
Family
ID=60809804
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| KR1020160072372A Expired - Fee Related KR101800320B1 (ko) | 2016-06-10 | 2016-06-10 | 버스 프로토콜 기반의 네트워크 온 칩 시스템, 그 설계 방법 및 그 설계 방법에 관한 프로그램이 기록된 컴퓨터 판독가능 기록매체 |
Country Status (1)
| Country | Link |
|---|---|
| KR (1) | KR101800320B1 (ko) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR102042194B1 (ko) * | 2019-08-08 | 2019-11-07 | 마인엔지니어링건축사사무소 주식회사 | 효율적 제어가 가능한 홈 네트워크 시스템 |
| KR102042186B1 (ko) * | 2019-08-08 | 2019-11-27 | 마인엔지니어링건축사사무소 주식회사 | 사용자 맞춤 설정 및 제어가 가능한 홈 네트워킹 시스템 제공 방법 |
| CN116886591A (zh) * | 2023-09-06 | 2023-10-13 | 芯来智融半导体科技(上海)有限公司 | 片上网络的拓扑结构及路由方法 |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR101548695B1 (ko) | 2014-11-03 | 2015-09-01 | 성균관대학교산학협력단 | 하이브리드 광학 네트워크 온 칩의 토폴로지 설계 장치 및 방법 |
-
2016
- 2016-06-10 KR KR1020160072372A patent/KR101800320B1/ko not_active Expired - Fee Related
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR101548695B1 (ko) | 2014-11-03 | 2015-09-01 | 성균관대학교산학협력단 | 하이브리드 광학 네트워크 온 칩의 토폴로지 설계 장치 및 방법 |
Non-Patent Citations (2)
| Title |
|---|
| "지연시간 효율 개선을 위한 On-Chip Network 구조 설계 및 구현", 전자공학회 논문지 제46권 SD편 제11호(pp. 56-65), 2009년 11월* |
| "하이브리드 광학 네트워크-온-칩에서 지연 시간 최적화를 위한 매핑 알고리즘", 전자공학회 논문지 제50권 7호(pp. 131-139), 2013년 7월 |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR102042194B1 (ko) * | 2019-08-08 | 2019-11-07 | 마인엔지니어링건축사사무소 주식회사 | 효율적 제어가 가능한 홈 네트워크 시스템 |
| KR102042186B1 (ko) * | 2019-08-08 | 2019-11-27 | 마인엔지니어링건축사사무소 주식회사 | 사용자 맞춤 설정 및 제어가 가능한 홈 네트워킹 시스템 제공 방법 |
| CN116886591A (zh) * | 2023-09-06 | 2023-10-13 | 芯来智融半导体科技(上海)有限公司 | 片上网络的拓扑结构及路由方法 |
| CN116886591B (zh) * | 2023-09-06 | 2023-12-15 | 芯来智融半导体科技(上海)有限公司 | 计算机网络系统及路由方法 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN111149330B (zh) | 软件定义网络中的拓扑感知控制器关联 | |
| Ferguson et al. | Hierarchical policies for software defined networks | |
| CN108462594B (zh) | 虚拟专有网络及规则表生成方法、装置及路由方法 | |
| CN107113241B (zh) | 路由确定方法、网络配置方法以及相关装置 | |
| US11310169B2 (en) | Network-on-chip topology generation | |
| CN115426312B (zh) | 一种大规模多模态网络中标识管理及优化转发方法和装置 | |
| CN114844827A (zh) | 一种用于片上网络芯片的基于共享存储的生成树路由硬件架构及方法 | |
| Fuerst et al. | Virtual network embedding with collocation: Benefits and limitations of pre-clustering | |
| KR101800320B1 (ko) | 버스 프로토콜 기반의 네트워크 온 칩 시스템, 그 설계 방법 및 그 설계 방법에 관한 프로그램이 기록된 컴퓨터 판독가능 기록매체 | |
| CN113747277B (zh) | 路径确定方法及装置 | |
| CN108965134B (zh) | 报文转发方法及装置 | |
| US20130227171A1 (en) | Apparatus and method for interconnecting heterogeneous networks | |
| Liao et al. | Distributed FlowVisor: a distributed FlowVisor platform for quality of service aware cloud network virtualisation | |
| Miao et al. | Multicast virtual network mapping for supporting multiple description coding-based video applications | |
| CN114064206A (zh) | 一种访问边缘节点的pod方法、系统、设备及存储介质 | |
| US11411855B1 (en) | Computation of ranked path options in networks | |
| CN113452758A (zh) | 一种业务访问方法及装置 | |
| US12081923B1 (en) | Low congestion routing method of Optical Network-on-Chip and related device | |
| Li et al. | Towards full virtualization of SDN infrastructure | |
| CN107294746B (zh) | 一种部署业务的方法及设备 | |
| CN103491023B (zh) | 用于三维torus光电混合网络的路由方法 | |
| Yang et al. | Scalable forwarding tables for supporting flexible policies in enterprise networks | |
| GB2607653A (en) | Network-on-chip topology generation | |
| Sun et al. | Minimally buffered router and deflection routing algorithm for 3D mesh NoC | |
| CN117951079B (zh) | 一种片上网络、芯片及芯片中数据传输方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PA0109 | Patent application |
Patent event code: PA01091R01D Comment text: Patent Application Patent event date: 20160610 |
|
| PA0201 | Request for examination | ||
| PE0902 | Notice of grounds for rejection |
Comment text: Notification of reason for refusal Patent event date: 20170419 Patent event code: PE09021S01D |
|
| E701 | Decision to grant or registration of patent right | ||
| PE0701 | Decision of registration |
Patent event code: PE07011S01D Comment text: Decision to Grant Registration Patent event date: 20171012 |
|
| GRNT | Written decision to grant | ||
| PR0701 | Registration of establishment |
Comment text: Registration of Establishment Patent event date: 20171116 Patent event code: PR07011E01D |
|
| PR1002 | Payment of registration fee |
Payment date: 20171117 End annual number: 3 Start annual number: 1 |
|
| PG1601 | Publication of registration | ||
| PR1001 | Payment of annual fee |
Payment date: 20200925 Start annual number: 4 End annual number: 4 |
|
| PR1001 | Payment of annual fee |
Payment date: 20210817 Start annual number: 5 End annual number: 5 |
|
| PC1903 | Unpaid annual fee |
Termination category: Default of registration fee Termination date: 20230827 |