KR101382606B1 - 하이브리드 광학 네트워크 온 칩의 태스크 매핑 장치 및 방법과 이를 이용한 하이브리드 광학 네트워크 온 칩 시스템 - Google Patents

Abstract

복수의 처리 소자(Processing Element, PE), PE 별로 매칭된 복수의 라우터 및 라우터 간에 경로를 형성하는 광학적 링크 및 전기적 링크가 구성된 하이브리드 광학 네트워크 온 칩(Hybrid Optical Network-on- Chip)의 태스크 매핑 시, 복수의 태스크 간 관계 및 복수의 태스크 별 데이터 크기를 정의하여 태스크 특성 그래프를 모델링하고. 복수의 PE의 배치 및 PE 간 연결 상태를 정의하여 PE 특성 그래프를 모델링하고, 태스크 특성 그래프를 PE 특성 그래프 상에 임시 매핑하는 매핑 모델링을 복수 회 수행하고, 복수 회의 매핑 모델링 중 복수의 태스크 간에 광학적 링크의 경로 중첩이 최소 값을 갖는 매핑 모델링의 결과에 따라 PE 별로 태스크를 매핑한다.

Description

하이브리드 광학 네트워크 온 칩의 태스크 매핑 장치 및 방법과 이를 이용한 하이브리드 광학 네트워크 온 칩 시스템{APPARATUS AND METHOD FOR TASK MAPPING OF HYBRID OPTICAL NETWORKS ON CHIP AND HYBRID OPTICAL NETWORKS ON CHIP SYSTEM USING THE SAME}

본 발명은 하이브리드 광학 네트워크-온-칩(Hybrid Optical Networks-On-Chip, HONoC) 환경에서 처리 소자(Processing Element, PE)에 태스크를 매핑하는 장치 및 방법과, 이를 이용한 HONoC 시스템에 관한 것이다.

싱글 코어 프로세서의 전력 효율 대비 성능의 한계로 인해 다중 코어를 이용한 다중 프로세서 시스템-온-칩(Multi-Processor System-on-Chip, MPSoC)이 개발되었다. 이러한 다중 프로세서 시스템-온-칩에서는 기존의 버스(bus) 구조를 적용할 경우 병목의 문제가 발생되어 전체 시스템 성능 향상이 저하될 수 있다. 이로 인해, 수백개 이상의 코어와 IP(Intellectual Property)가 집적된 첨단 SoC 구조에 온-칩 네트워크(On-chip Network, OCN) 개념을 적용한 네트워크-온-칩(Network-on-Chip, NoC)이 등장하였다. 일례로, 최근 들어 실감 멀티미디어와 사용자 인터페이스/사용자 경험 (UI/UX)이 중요해지고 있으며, 초고해상도가 요구되는UHD급 차세대 TV 등에서 고도의 병렬 연산 요구가 커짐에 따라 NoC의 적용이 크게 고려되고 있다.

한편, NoC는 토폴로지와 프로토콜 관점의 구조적 변화이므로, 기존 반도체 공정/소자 기술의 한계에 대응하기 위해서는 추가적으로 물리적 연결 매체 (Interconnection medium)까지 고려한 접근 방식이 요구된다. 이에 따라, 기존 NoC에서의 전기적 상호 연결(Electrical Interconnect, EI)에 의한 전력 소모 및 지연 시간 문제를 광학적 상호 연결(Optical Interconnect, OI)을 통해 해결하는 하이브리드 광학적 네트워크-온-칩(Hybrid Optical NoC, HONoC)이 등장하였다.

예를 들어, 메시 토폴로지에서 OI를 통해 대용량 패이로드(payload) 데이터를 전송하고, EI를 통해 컨트롤 패킷 및 경로 설정 패킷을 전송하도록 하는 방법이 제안되었다. 그리고, 경로가 긴 통신은 OI를 이용하고 경로가 짧은 통신은 EI를 사용해 전송 효율을 높이는 방법이 제안되었다. 그리고, TSV(Through-Silicon-Vias)를 이용해 칩을 두 층으로 구성하여 한 층에서는 광학적 네트워크를 통한 페이로드(payload) 데이터 전송을 다른 층에서는 전기적 네트워크를 통한 컨트롤 패킷 전송 및 광학적 경로 설정을 하는 방법이 제안되었다. 또한, 4개 코어 단위로 클러스터(cluster)를 구성하여 클러스터 내부에서는 EI로 클러스터 간에는 OI에 의한 데이터를 전송하는 방법도 제안되었다.

이러한, HONoC에서는 광 신호를 패킷 스위칭(Packet Switching) 방식으로 라우팅하게 되면 각 라우터에서 광신호의 전기 신호로의 변환과 이를 통한 목적지 판별 과정을 거쳐야 하므로, 지연 시간(latency)이 오히려 EI기반 NoC보다 증가하기 때문에 EI를 통해 OI의 경로를 설정하게 하는 서킷 스위칭(Circuit Switching) 네트워크로 구성한다.

따라서, 독립적인 복수 데이터의 전송 경로가 일부라도 서로 중첩되면 동시 전송이 불가능하여, 하나의 전송이 완료될 때까지 다른 전송들은 대기해야 하는 문제가 발생한다. 즉, HONoC에서는 서킷 스위칭을 사용함에 따라 네트워크 트래픽과 네트워크 사이즈가 증가할수록 경로 충돌 발생 확률이 더 빠르게 증가하고, 이 경로 충돌을 적절히 제어하지 못할 경우 전체적인 시스템 성능이 급격히 저하된다. 또한 대용량 데이터 전송 경로와 충돌되는 경우 지연 시간 불균등(latency unfairness)문제 또한 심화된다.

기존 NoC에서도 성능과 전력 소모 최적화를 위해 태스크를 처리 소자(PE)에 할당하는 다양한 매핑 알고리즘 연구들이 진행되어 왔다. 예를 들어, 통신 대역폭 제약을 선형 문제로 도식화하여 해결하는 방법, 각 태스크의 에너지와 통신에 필요한 성능 요구를 알고 이를 분기 한정법(branch-and-bound)을 사용하여 매핑하는 방법, 실제 태스크 수행 시간의 제약을 고려한 슬랙 예산 관리(slack-budgeting) 태스크 매핑 방법, 및 이종 다중 프로세서 NoC에서 에너지 소모량을 최소화시키기 위해 ILP(Integer Linear Programming)를 이용하여 매핑하는 방법등이 있었다.

이와 관련하여, 대한민국등록특허 제714073호(발명의 명칭: 통신 자원의 충돌이 없는 온칩 네트워크 자동 생성 방법)에서는, SoC 설계에 있어서, 온칩 네트워크를 구성하는 모듈들간의 통신량에 대한 트래픽 그래프 및 통신 스케줄을 분석하여 각 통신 요구들 간의 경합이 없는 최적의 온칩 네트워크를 자동으로 생성하는 방법을 개시하고 있다.

하지만 이러한 기존의 연구들은 광학적 상호 연결(OI)의 적용을 통해 서킷 스위칭을 사용해야 하는HONoC 구조의 환경을 제대로 반영하지 못하여, 앞서 설명한 바와 같은 HONoC 구조에서의 경로 충돌 제어에는 한계가 있었다.

전술한 종래 기술의 문제점을 해결하기 위해, 본 발명의 일 실시예는 HONoC 구조에서 광학적 경로 충돌에 의해 발생하는 지연 시간 비용(cost)을 최적화하여 태스크를 PE에 매핑하는 태스크 매핑 장치 및 방법과, 이를 이용한 HONoC 시스템을 제공하고자 한다.

다만, 본 실시예가 이루고자 하는 기술적 과제는 상기된 바와 같은 기술적 과제로 한정되지 않으며, 또 다른 기술적 과제들이 존재할 수 있다.

상기와 같은 기술적 과제를 달성하기 위한 본 발명의 일 측면에 따른, 복수의 처리 소자(Processing Element, PE), 상기 PE 별로 매칭된 복수의 라우터 및 상기 라우터 간에 경로를 형성하는 광학적 링크 및 전기적 링크가 구성된 하이브리드 광학 네트워크 온 칩(Hybrid Optical Network-on-Chip, HONoC)의 태스크 매핑 장치는, 복수의 태스크 간 관계 및 상기 복수의 태스크 별 데이터 크기를 정의하여 태스크 특성 그래프를 모델링하는 태스크 모델링부; 상기 복수의 PE의 배치 및 PE간 연결 상태를 정의하여 PE 특성 그래프를 모델링하는 처리 소자 모델링부; 및 상기 태스크 특성 그래프를 상기 PE 특성 그래프 상에 매핑하는 매핑 모델링을 복수 회 수행하되, 상기 복수 회의 매핑 모델링 중 상기 복수의 태스크 간에 상기 광학적 링크의 경로 중첩이 최소 값을 갖는 매핑 모델링의 결과에 따라 상기 PE 별로 상기 태스크를 매핑하는 태스크 매핑부를 포함한다.

그리고 본 발명의 다른 측면에 따른, 복수의 처리 소자(Processing Element, PE), 상기 PE 별로 매칭된 복수의 라우터 및 상기 라우터 간에 경로를 형성하는 광학적 링크 및 전기적 링크가 구성된 하이브리드 광학 네트워크 온 칩(Hybrid Optical Network-on- Chip)의 태스크 매핑 장치를 통한 태스크 매핑 방법은, 복수의 태스크 간 관계 및 상기 복수의 태스크 별 데이터 크기를 정의하여 태스크 특성 그래프를 모델링하는 단계; 상기 복수의 PE의 배치 및 PE 간 연결 상태를 정의하여 PE 특성 그래프를 모델링하는 단계; 상기 태스크 특성 그래프를 상기 PE 특성 그래프 상에 임시 매핑하는 매핑 모델링을 복수 회 수행하는 단계; 및 상기 복수 회의 매핑 모델링 중 상기 복수의 태스크 간에 상기 광학적 링크의 경로 중첩이 최소 값을 갖는 매핑 모델링의 결과에 따라 상기 PE 별로 상기 태스크를 매핑하는 단계를 포함한다.

또한, 본 발명의 또 다른 측면에 따른, 하이브리드 광학 네트워크 온 칩(Hybrid Optical Network-on- Chip) 시스템은, 복수의 처리 소자(Processing Element, PE); 상기 PE 별로 매칭되며, 광학적 링크를 통해 상기 PE 간 데이터의 전송을 위한 서킷 스위칭을 처리하고, 전기적 링크를 통해 상기 PE 간 경로 설정을 위한 패킷 스위칭을 처리하는 복수의 라우터; 및 상기 복수의 PE에 복수의 태스크를 임시 매핑하는 매핑 모델링을 복수 회 수행하고, 상기 복수 회의 매핑 모델링 중 상기 복수의 태스크 간에 상기 광학적 링크의 경로 중첩이 최소 값을 갖는 매핑 모델링의 결과에 따라 상기 PE 별로 상기 태스크를 매핑하는 태스크 매핑 장치를 포함한다.

전술한 본 발명의 과제 해결 수단 중 어느 하나에 의하면, 서킷 스위칭 기반의HONoC 환경에서 광학적 경로의 라우팅 복잡도를 증가시키지 않으면서도 경로 충돌 빈도를 감소시키고, 경로 충돌 시에도 워스트 케이스(worst case)에서의 경로 지연(latency)을 최소 값으로 보장하는 효과가 있다.

도 1은 본 발명의 일 실시예에 따른 하이브리드 광학 네트워크 온 칩 시스템을 설명하기 위한 도면이다.
도 2는 본 발명의 일 실시예에 따른 하이브리드 광학 네트워크 온 칩의 태스크 매핑 장치의 구성을 나타낸 블록도이다.
도 3은 본 발명의 일 실시예에 따른 태스크 특성 그래프의 일례를 나타낸 도면이다.
도 4는 본 발명의 일 실시예에 따른 태스크 매핑부의 구성을 나타낸 블록도이다.
도 5는 본 발명의 일 실시예에 따른 하이브리드 광학 네트워크 온 칩 환경에서 지연 시간 최적화를 위한 매핑 알고리즘의 의사(pseudo) 코드이다.
도 6은 본 발명의 일 실시예에 따른 매핑 알고리즘의 변수 초기화 부분의 의사 코드이다.
도 7은 본 발명의 일 실시예에 따른 하이브리드 광학 네트워크 온 칩의 태스크 매핑 방법을 설명하기 위한 순서도이다.

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

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

도 1은 본 발명의 일 실시예에 따른 하이브리드 광학 네트워크 온 칩 시스템을 설명하기 위한 도면이다.

그리고, 도 2는 본 발명의 일 실시예에 따른 하이브리드 광학 네트워크 온 칩의 태스크 매핑 장치의 구성을 나타낸 블록도이다.

먼저, 도 1에 도시한 바와 같이, 본 발명의 일 실시예에 따른 하이브리 광학 네트워크 온 칩(Hybrid Optical NoC, HONoC) 시스템(10)은 복수의 처리 소자(processing element, PE)(100), 각 PE(100)와 매칭되어 연결된 복수의 라우터(200), 및 각 라우터(200) 간에 광학적 경로를 형성하는 광학적 링크(300), 각 라우터 간에 전기적 경로를 형성하는 전기적 링크(400)로 구성된 HONoC를 포함한다. 또한, HONoC 시스템(10)은 HONoC 상의 복수의 PE(100)에 각각 태스크를 매핑하는 태스크 매핑 장치(500)를 포함하여 구성된다.

이때, 도 1에서는 본 발명의 일 실시예에 따른 HONoC 시스템(10)이 메시 토폴로지 형태의 HONoC로 구성된 것을 나타내었으며, 본 발명의 실시예에 따른HONoC의 토폴로지 종류는 다양하게 설정될 수 있다.

한편, 본 발명의 일 실시예에서 광학적 링크(300)는 광학적 상호 연결(Optical Interconnect, OI)로서, 광학적 경로가 설정된 라우터(200) 간에 대용량의 페이로드(payload) 패킷을 광 신호로 통신할 수 있는 링크이다. 그리고, 전기적 링크(400)는 전기적 상호 연결(Electrical Interconnect, EI)로서, 복수의 라우터(200) 중 출발지 라우터와 목적지 라우터 간에 광학적 경로를 설정하기 위한 경로 설정용 패킷을 전기 신호로 통신할 수 있는 링크이다.

구체적으로, 본 발명의 일 실시예에 따른 HONoC 시스템(10)은 다음과 같은 동작을 통해 PE(100) 간에 데이터 통신을 수행한다.

먼저, 출발지 라우터에서 전기적 링크(400)를 통해 경로 설정 패킷을 목적지 라우터로 전송한다. 그런 다음, 경로 설정 패킷을 받은 라우터는 경로 설정 패킷을 확인하여 HONoC 상에서 기설정된 다음 순번의 라우터로 라우팅하거나, 또는 자신이 최종 목적지일 경우 자신과 매칭 연결된 PE(100)로 라우팅을 함과 동시에 페이로드 패킷 전송을 위한 광학적 경로를 설정한다.

이때, 경로 설정 패킷이 최종 목적지 라우터에 도착하면, 해당 목적지 라우터는 전기적 링크(400)를 통해 출발지 라우터로 응답 패킷(즉, Ack)을 전송한다. 그러면, 응답 패킷(Ack)을 수신한 출발지 라우터는 설정된 광학적 링크(300)를 통해 목적된 데이터(즉, 페이로드 패킷)가 전송되도록 한다. 즉, 출발지 라우터와 매칭 연결된 PE(100)와 목적지 라우터와 매칭 연결된 PE(100) 간에 광학적 링크(300)를 통한 데이터 통신이 수행된다.

마지막으로, 출발지 라우터로부터의 데이터 전송이 완료되면, 출발지 라우터는 경로 해제 패킷을 전기적 링크(400)를 통해 전송하여, 목적지 라우터까지 설정되어 있던 광학적 링크(300) 상의 경로를 해제시킨다.

이상에서 설명한, PE(100) 간의 데이터 통신을 수행하기 위한 라우팅 동작은, 각 라우터(200) 별로 사전에 설정된 라우팅 알고리즘에 따를 수 있다. 본 발명의 일 실시예에서는, 이하에서 설명할 태스크 매핑 장치(500)가 각 라우터(200)의 데이터 통신을 위한 라우팅 동작을 제어할 수 있다.

한편, 본 발명의 일 실시예에 따른 HONoC 시스템(10)에서는, 이상에서 설명한 HONoC의 데이터 통신 동작을 수행하기에 앞서, 태스크 매핑 장치(500)가 애플리케이션에 따른 복수의 태스크(task)를 복수의 PE(100)에 매핑 처리한다.

본 발명의 일실시예에 따른 태스크 매핑 장치(500)는 복수의 태스크 간에 광학적 링크(300)의 경로 중첩이 최소 값을 갖는 매핑 모델링의 결과에 따라 PE(100) 별로 태스크를 매핑한다.

이때, 태스크 매핑 장치(500)는 복수의 태스크 별 최대 데이터 크기, 및 복수의 PE(100) 별로 라우터(200)를 통해 연결된 광학적 링크(300)의 대역폭 크기에 기초하여, 매핑 모델링에 따른 경로 지연 비용을 산출한다. 그리고, 태스크 매핑 장치(500)는 경로 지연 비용이 최소 값인 매핑 모델링의 결과에 따라 복수의 태스크를 복수의 PE(100)에 매핑한다.

구체적으로, 도 2에 도시한 바와 같이, 본 발명의 일 실시예에 따른 태스크 매핑 장치(500)는 태스크 모델링부(510), 처리 소자 모델링부(520), 태스크 매핑부(530) 및 데이터 통신 제어부(540)를 포함하여 구성된다.

태스크 모델링부(510)는 복수의 태스크의 태스크 간 관계 및 데이터 크기를 정의하여 태스크 특성 그래프를 모델링한다.

구체적으로, 도 3은 본 발명의 일 실시예에 따른 태스크 특성 그래프의 일례를 나타낸 도면이다.

도 3에서는 애플리케이션에 포함된 복수의 태스크 간의 통신 패턴과 각 태스크에서 처리할 데이터의 크기를 DAG(directed acyclic graph)로 모델링한 것을 나타내었다.

이때, DAG 표기에 의해 G=<V, E>로 표현할 수 있다. 여기서, V는 태스크로서 v_i∈V로 표현할 수 있고, E는 태스크 간에 데이터 통신으로서 v_i가 v_j로 데이터를 전송하는 통신을 e_{i ,j}∈E라고 표현할 수 있다.

그리고, 도 3에 도시한 바와 같이, e_{i ,j}는 BW(e_{i ,j}) 및 CV(e_{i ,j})의 두 가지 값을 가질 수 있다. BW(e_i,j)는 v_i가 v_j로 데이터를 전송할 때의 통신의 대역폭이며, CV(e_{i ,j})는 v_i가 v_j로 데이터를 전송할 때 한번의 통신에서 처리되는 최대 데이터양(즉, 데이터 크기)을 의미한다.

이와 같이, 태스크의 통신 패턴 및 특성을 태스크 특성 그래프로 모델링하여, 복수의 태스크의 특성에 기초하여 태스크와 PE(100) 간에 매핑을 수행할 수 있다.

다시 도 2로 돌아가서, 처리 소자 모델링부(520)는 복수의 PE(100)의 배치 및 PE(100) 간 연결 상태를 정의하여 PE 특성 그래프를 모델링한다.

구체적으로, 앞서 태스크 특성 그래프를 모델링한 것과 마찬가지로, PE(100)들의 배치 상태 및 연결 상태를 정의하여 PE 특성 그래프를 모델링할 수 있다.

이때, PE 특성 그래프는 DAG 표기에 의해 P=<U, F>로 표현할 수 있다. 여기서, U는 PE(100)로서 u_j∈U로 표현할 수 있고, F는 PE(100) 간의 연결을 의미하는 것으로서 u_i와 u_j간의 연결을 f_{i ,j}∈F라고 표현할 수 있다.

태스크 매핑부(530)는 태스크 모델링부(510)를 통해 모델링된 태스크 특성 그래프를, 처리 소자 모델링부(520)를 통해 모델링된 PE 특성 그래프 상에 매핑한다.

이때, 태스크 매핑부(530)는 복수의 태스크를 복수의 PE(100)에 임시 할당하는 매핑 모델링을 복수 회 수행하며, 복수 회의 매핑 모델링 중 복수의 태스크 간에 광학적 링크(300)의 경로 중첩이 최소 값을 갖는 매핑 모델링의 결과에 따라 PE(100) 별로 태스크를 최종 매핑한다.

참고로, 태스크 매핑부(530)가 태스크와 PE(100)를 매핑하는 동작에 대해서는 하기 도 4 내지 도 6을 통해 상세히 설명하도록 한다.

데이터 통신 제어부(540)는 복수의 태스크를 포함하는 애플리케이션의 실행에 따라 PE(100) 간 데이터 통신을 제어한다.

구체적으로, 데이터 통신 제어부(540)는 복수의 라우터(200) 중 적어도 하나가 전기적 링크(400)를 통해 어느 하나의 태스크에 의해 설정된 목적지 라우터와의 경로 설정을 위한 패킷 스위칭을 처리하도록 제어한다. 그리고, 데이터 통신 제어부(540)는 광학적 링크(300)를 통해 상기 목적지 라우터와의 페이로드 패킷의 통신을 위한 서킷 스위칭을 처리하도록 제어한다.

이하, 도 4 내지 도 6을 참조하여 본 발명의 일 실시예에 따른 태스크 매핑부(530)의 구성 및 태스크 매핑 방식에 대해서 상세히 설명하도록 한다.

도 4는 본 발명의 일 실시예에 따른 태스크 매핑부의 구성을 나타낸 블록도이다.

도 4에 도시한 바와 같이, 본 발명의 일 실시예에 따른 태스크 매핑부(530)는 매핑 모델링 모듈(531), 경로 지연 비용 산출 모듈(532) 및 매핑 처리 모듈(533)을 포함하여 구성된다.

매핑 모델링 모듈(531)은 복수의 PE(100)에 복수의 태스크를 임시 할당하는 매핑 모델링을 복수 회 처리한다. 이때, 매핑 모델링 모듈(540)은 상기 복수 회의 매핑 모델링마다 상이한 매핑 모델을 적용하여 복수의 태스크를 복수의 PE(100)에 임시 할당한다.

구체적으로, 매핑 모델링 모듈(531)은 기설정된 매핑 함수를 통해 태스크 특성 그래프를 PE 특성 그래프에 매핑한다.

예를 들어, 기설정된 매핑 함수 'map()'를 사용하여 태스크 특성 그래프 G=<V, E>를 PE 특성 그래프 P=<U, F>에 매핑하며, 이를 통해 각각의 태스크를 PE(100)에 매핑한 후의 결과는 다음과 같은 수학식 1로 표현할 수 있다.

<수학식 1>

이때, |V|≤|U|일 경우, 매핑이 정의된다.

본 발명의 일 실시예에서는, 매핑 모델링 모듈(531)을 통한 매핑 모델링마다, 아래에서 설명할 경로 지연 비용 산출 모듈(532)을 통한 경로 지연 비용의 산출 동작이 병렬적으로 수행된다.

경로 지연 비용 산출 모듈(532)은 복수의 태스크 별 최대 데이터 크기, 및 복수의 PE(100) 별로 라우터(200)를 통해 연결된 광학적 링크(300)의 대역폭 크기에 기초하여, 매핑 모델링 회차 별 경로 지연 비용을 산출한다.

구체적으로, 경로 지연 비용 산출 모듈(532)은 매 회차의 매핑 모델링에서, 복수의 태스크가 순차적으로 임시 할당될 때마다 해당 태스크(즉, 임시 할당된 태스크)의 경로 지연 비용(이하, '제 1 경로 지연 비용'으로 지칭함)을 산출한다.

여기서, 제 1 경로 지연 비용은, 해당 회차의 매핑 모델링에서 기할당된 적어도 하나의 다른 태스크의 데이터 통신이 완료된 후 해당 태스크의 데이터 통신을 처리하기까지 필요한 값이다. 즉, 해당 태스크와 기할당된 다른 태스크 간에 광학적 링크(300) 상의 경로 중첩이 발생된 경우, 해당 태스크의 제 1 경로 지연 비용은 영(0) 이상의 값을 갖는다.

이때, 경로 지연 비용 산출 모듈(532)은 복수의 태스크에 대한 임시 할당이 완료될 때까지 제 1 경로 지연 비용을 누적하고, 제 1 경로 지연 비용들을 누적한 결과를 해당 매핑 모델링에 대한 경로 지연 비용(이하, '제 2 경로 지연 비용'으로 지칭함)으로 산출한다.

그리고, 경로 지연 비용 산출 모듈(532)은 경로 지연 비용(즉, 제 2 경로 지연 비용) 중 최소 값을 갖는 매핑 모델링의 결과에 따라 최적 매핑 모델 및 최소 경로 지연 비용을 매칭하여 저장한다.

이때, 경로 지연 비용 산출 모듈(532)은 매핑 모델링 모듈(531)을 통한 매핑 모델링 수행 중에, 기저장된 최소 경로 지연 비용보다 큰 값의 경로 지연 비용이 발생되면 현재 수행 중인 매핑 모델링을 중지시킨다. 즉, 이미 수행된 매핑 모델링의 제 2 경로 지연 비용이 최소 경로 지연 비용으로 저장된 상태에서, 현재 수행 중인 매핑 모델링의 제 1 경로 지연 비용의 누적 값이 기저장된 최소 경로 지연 비용을 초과할 경우 상기 현재 수행 중인 매핑 모델링을 중지시켜 불필요한 매핑 모델링을 방지한다.

또한, 경로 지연 비용 산출 모듈(532)은 해당 매핑 모델링의 수행이 완료된 상태에서의 경로 지연 비용이 기저장된 최소 경로 지연 비용보다 작은 값인 경우, 매핑 모델링의 결과에 따른 매핑 모델 및 경로 지연 비용을 최적 매핑 모델 및 상기 최소 경로 지연 비용으로 갱신하여 저장한다.

매핑 처리 모듈(533)은 경로 지연 비용(즉, 제 2 경로 지연 비용)이 최소 값인 매핑 모델링의 결과에 따라 복수의 태스크를 복수의 PE(100)에 매핑 처리한다.

이때, 매핑 처리 모듈(533)은 복수 회의 매핑 모델링 중 경로 지연 비용이 최소 값인 매핑 모델링의 결과에 따른 최적 매핑 모델을 결정하고, 결정된 최적 매핑 모델에 따라 PE(100) 별로 태스크를 매핑한다.

이상, 도 4에서는 본 발명의 일 실시예에 따른 태스크 매핑부(530)가 매핑 모델링을 통해, 최소 지연 시간 비용을 갖는 최적의 매핑 모델을 설정하여 복수의 태스크를 복수의 PE(100)에 매핑하는 방식을 설명하였다.

위와 같은 태스크 매핑부(530)의 태스크 매핑 방식을 하기 도 5 및 도 6에 나타낸 알고리즘을 통해 상세히 설명하도록 한다.

도 5는 본 발명의 일 실시예에 따른 하이브리드 광학 네트워크 온 칩 환경에서 지연 시간 최적화를 위한 매핑 알고리즘의 의사(pseudo) 코드이다.

그리고, 도 6은 본 발명의 일 실시예에 따른 매핑 알고리즘의 변수 초기화 부분의 의사 코드이다.

먼저, 도 5와 같이, 본 발명의 일 실시예에서 태스크 매핑부(530)는, 목적 함수 (objective function)로 구현된 매핑 알고리즘을 수행하여 태스크 매핑을 처리할 수 있다.

도 5에서는 재귀 함수로 구현된 매핑 알고리즘을 수행하는 것을 나타내었으며, 이러한 재귀 함수는 태스크를 순차적으로 PE(100)에 매핑을 시도하면서 최적해를 찾는다.

이때, 'allocation_calculation_path()' 함수에서는 태스크가 PE(100)에 매핑 되었을 때, 코스트(즉, 지연 시간 비용) 증가율 계산 및 각 광학적 연결에 새로 적용될 통신을 반영하고, 'returning_path()' 함수에서 반영된 통신을 이전 상태로 복구시킨다. 만약 태스크 매핑이 완료된 후의 코스트가 지금까지 찾은 후보 해 중 최소 코스트보다 작다면 이를 갱신해 주고 최소 코스트가 영(0)이 되거나, 또는 모든 후보 해(즉, 매핑 모델링)들의 고려가 완료되면 알고리즘이 종료된다. 참고로, 도 5에서 나타낸 매핑 알고리즘의 모든 변수들은 도 6에서 나타낸 초기화 알고리즘에 따라 초기화된다. 이때, 'total_task' 는 매핑해야 할 태스크의 총 개수를 의미하고 'total_pe'는 HONoC의 네트워크에 존재하는 PE(100)의 개수를 의미한다.

이와 같은 매핑 알고리즘은, 전체적인 지연 시간을 감소시키기 위해 매핑 모델링 별 경로 지연 비용 중 최소 값의 경로 지연 비용을 갖는 매핑 모델링에 따라 매핑을 처리한다. 즉, 복수의 태스크에 대한 통신 경로의 충돌(즉, 중첩)을 최소화시킬 수 있도록 매핑을 처리한다. 뿐만 아니라, HONoc의 네트워크 복잡도와 통신 데이터양이 증가할수록 모든 충돌 통신 경로를 고려하여 독립적으로 배치(즉, 매핑)하는데 어려움이 있어, 대용량 데이터가 전송되는 광학적 경로의 경우 우선적으로 전송 경로 중첩을 제거/최소화하고, 불가피한 충돌 경로의 경우 데이터양이 적은 전송에서 발생하도록 매핑한다. 이처럼, 불필요하게 고려할 해의 제거를 통해 빠른 연산을 수행할 수 있도록 분기 한정법(branch-and-bound)을 기반으로 작성될 수 있다.

구체적으로, 도 5에 도시한 매핑 알고리즘에 따르면, 복수의 태스크를 복수의 PE(100)에 매핑할 시에 최적의 조건에 따라 매핑을 처리하기 위해서는, 라우팅 경로를 매핑(즉, 태스크를 PE에 할당)함과 동시에 복수의 태스크에 대해 광학적 링크(300)에서 지연 시간을 최소화시킬 수 있는 지연 시간 최소화의 문제가 정의되어야 한다.

이를 위하여, 본 발명의 일 실시예에서는, 이러한 경로 지연 비용의 최소화의 문제를 정의하기 위하여 확정적 알고리즘(Deterministic algorithm)에 기반하여 지연 시간 비용에 대한 문제를 정의한다. 이때, 확정적 알고리즘에 의해 매핑된 태스크 v_i로부터 v_j로의 통신에 사용되는 연결 F의 부분 집합을 L(e_{i ,j})로 정의할 수 있다.

구체적으로, 매핑 모델링 모듈(531)을 통해 매핑 모델링이 수행되는 중에, 복수의 태스크가 각각 PE(100)에 임시 할당된 후, e_{i ,j}와 라우팅 경로(즉, 광학적 링크(300))가 공유되는 모든 e_{i' , j'}∈E를 S_{i ,j}라고 정의한다. 이에 따라, L(e_{i ,j})∩L(e_i',j')≠φ 이면, e_{i' , j'}∈S_{i ,j}가 된다.

이상에서의 정의에 기반하면, 광학적 링크(300)의 경로 중첩에 의한 지연 시간을 하기 수학식 2와 같이 정의할 수 있다.

<수학식 2>

상기 수학식 2에서, OptBW는 광학적 연결의 대역폭을 의미하고, WLat(e_{i ,j})는 경로 중첩(즉, 충돌) 발생 시 중첩된 다른 모든 데이터의 전송 작업이 완료된 후 자신의 데이터 전송이 완료될 때 '워스트 케이스(worst case)'의 지연 시간을 의미한다.

이를 통해, 하기 알고리즘 1과 같이 지연 시간 균등화 및 최소화 문제를 정의할 수 있다.

<알고리즘 1>

상기 알고리즘 1에서 Link_BW(f_{i ,j})는 광학적 대역폭의 요구량을 의미하며, 하기 수학식 3과 같이 표현될 수 있다.

<수학식 3>

참고로, 상기 광학적 대역폭 요구량 LinkBW(f_{i ,j})이 실질적으로 사용 가능한 대역폭 OptBW를 초과하는 매핑을 수행할 경우, 태스크의 수행 시간을 증가시킬 뿐만 아니라 HONoC 의 네트워크 지연 시간 자체도 크게 증가하게 된다. 예를 들어, Task1이 Task2에 60Gbps로 발생하는 데이터를 전송하는데 전송 가능한 대역폭은 40Gbps라면 데이터를 생성하는 Task1의 처리 시간이 지연되고 데이터 전송 또한 누적될수록 더욱 지연되게 된다. 즉, 광학적 지연 시간을 최적화하기 위해서는 각각의 광학적 경로에서의 대역폭 요구량이 실질적인 광학적 대역폭을 초과하지 않도록 하면서 경로를 공유하는 전송 간의 시간을 줄여야 한다.

이에 따라, 매핑 알고리즘에서는 하나의 f_{i ,j}(즉, 광학적 연결)가 수용할 수 있는 대역폭을 초과하게 되면 코스트를 무한대 값으로 줄 수 있게 설정된다. 이는, 대역폭을 초과하게 되면 지연 시간에 치명적인 영향을 미칠 수 있으므로 이를 방지하기 위해서이다.

한편, 통신 f_{i ,j}에 대한 지연 시간 비용은 v_i 와 v_j가 매핑된 후 산출될 수 있다. 이때, 지연 시간 비용의 초기값은 영(0)으로 설정되고, 매핑 모델링 시 태스크가 매핑된 후 해당 태스크와 연관된 통신(즉, 중첩된 광학적 경로)이 지연 시간 비용으로 누적될 때마다 하기 수학식 4를 통해 갱신된다.

<수학식 4>

상기 수학식 4에서, cost는 기존에 누적된 제 1 지연 시간 비용이고, cost'는 추가되는 통신에 의해 누적되는 제 1 지연 시간 비용이다. 그리고, N은 추가되는 통신과 경로가 충돌되는 통신의 개수이다.

이와 같은 수학식 4를 통해, 새로 추가되는 통신의 지연 시간뿐만 아니라 이미 반영된 통신이 새로 추가된 통신에 의해 증가하는 지연시간까지 반영할 수 있다.

또한, 매핑 알고리즘에서, 최적해(Optimum solution) 탐색 시간을 줄이기 위해서는, 각 매핑 모델링을 통해 찾아진 후보 해(candidate solution) 중 가장 작은 코스트 값(즉, 최소 지연 시간 비용)을 저장해 놓는다. 그리고, 현재 매핑 중인 후보 해가 저장된 코스트(최소 지연 시간 비용)를 이미 초과하면 이 매핑은 최적해가 될 수 없다고 판단하여 해당 후보 해를 통해 파생되는 다른 해를 탐색하지 않는다. 이를 통해 불필요한 매핑 시도를 줄일 수 있다. 참고로, 모든 태스크가 PE(100)에 매핑되었을 때 누적된 코스트가 영(0)이라면 최적해가 된다. 이는 경로 충돌과 대역폭 초과를 하는 통신이 없다는 것이고 결국 정의된 문제의 최적해로 바로 채택될 수 있으므로 더 이상의 매핑 모델링을 진행할 필요가 없다.

이하, 도 7을 참조하여 본 발명의 일 실시예에 따른 HONoC 시스템(10)에서 태스크 매핑을 수행하는 방법을 상세히 설명하도록 한다.

도 7은 본 발명의 일 실시예에 따른 하이브리드 광학 네트워크 온 칩의 태스크 매핑 방법을 설명하기 위한 순서도이다.

먼저, 복수의 태스크의 태스크 간 관계 및 데이터 크기를 정의하여 태스크 특성 그래프를 모델링한다(S710).

그리고, HONoC 상의 복수의 PE의 배치 및 PE 간 연결 상태를 정의하여 PE 특성 그래프를 모델링한다(S720)

이때, 상기 모델링하는 단계(S710, S720)는 순서가 변경될 수 있으며, 동시에 수행될 수 있다. 즉, 본 발명의 일 실시예에서는 태스크 특성 그래프의 모델링 및 PE 특성 그래프의 모델링의 선후 관계에 영향을 받지 않는다.

그런 다음, 태스크 특성 그래프 및 PE 특성 그래프에 기초하여 복수의 태스크를 복수의 PE에 임시 매핑하는 매핑 모델링을 반복 수행한다(S730).

즉, 태스크 특성 그래프를 상기 PE 특성 그래프 상에 임시 매핑하는 매핑 모델링을 복수 회 수행하며, 복수 회의 매핑 모델링마다 상이한 매핑 모델에 따라 복수의 PE에 상기 복수의 태스크를 순차적으로 임시 할당한다.

이와 같은 매핑 모델링의 반복 수행 중에, 복수의 태스크 간에 HONoC 상의 광학적 링크의 경로 중첩이 최소 값을 갖는 최적 매핑 모델을 검출한다(S740).

구체적으로, 복수 회의 매핑 모델링마다, 복수의 태스크 별 최대 데이터 크기 및 복수의 PE 별로 라우터를 통해 연결된 광학적 링크의 대역폭 크기에 기초하여 경로 지연 비용을 산출한다. 이때, 복수의 태스크가 복수의 PE에 순차적으로 임시 할당될 때마다, 임시 할당된 태스크와 기할당된 적어도 하나의 다른 태스크 간에 광학적 링크 상의 경로 중첩이 발생된 경우에 대한 해당 태스크의 제 1 경로 지연 비용을 산출하고, 복수의 태스크 별 제 1 경로 지연 비용을 누적하여 해당 매핑 모델링에 대한 제 2 경로 지연 비용을 산출한다.

또한, 복수 회의 매핑 모델링 중 최소 값의 경로 지연 비용을 갖는 매핑 모델링의 결과에 따라 최적 매핑 모델 및 최소 경로 지연 비용을 매칭하여 저장하여, 복수 회의 매핑 모델링 중 경로 지연 비용이 최소 값인 매핑 모델링의 결과에 따른 최적 매핑 모델을 선택한다.

구체적으로, 어느 하나의 매핑 모델링의 수행 중에 기저장된 상기 최소 경로 지연 비용보다 큰 값의 경로 지연 비용이 발생되면 수행 중인 매핑 모델링을 중지시키고, 어느 하나의 매핑 모델링의 수행이 완료된 상태에서의 경로 지연 비용이 기저장된 최소 경로 지연 비용보다 작은 값인 경우, 해당 매핑 모델링의 결과에 따른 매핑 모델 및 경로 지연 비용을 최적 매핑 모델 및 최소 경로 지연 비용으로 갱신하여 저장한다.

그런 후, 최적 매핑 모델에 따라 PE(100) 별로 태스크를 매핑한다(S750).

즉, 복수 회의 매핑 모델링 중 복수의 태스크 간에 상기 광학적 링크의 경로 중첩이 최소 값을 갖는 매핑 모델링의 결과에 따라 PE 별로 태스크를 매핑한다.

한편, 본 발명의 일 실시예에서는 상기 PE 별로 상기 태스크를 매핑하는 단계 이후에, 복수의 태스크를 포함하는 애플리케이션의 실행에 따라 PE 간 데이터 통신을 제어하는 단계를 더 포함할 수 있다. 이러한, PE 간 데이터 통신을 제어하는 단계는, 상기 복수의 라우터 중 적어도 하나가 상기 전기적 링크를 통해 상기 태스크에 의해 설정된 목적지 라우터와의 경로 설정을 위한 패킷 스위칭을 처리하도록 제어하거나, 상기 경로 설정에 의해 설정된 상기 광학적 링크를 통해 상기 목적지 라우터와의 페이로드 패킷의 통신을 위한 서킷 스위칭을 처리하도록 제어할 수 있다.

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

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

10: 하이브리드 광학 네트워크 온 칩 시스템
100: 처리 소자
200: 라우터
300: 광학적 경로
400: 전기적 경로
500: 태스크 매핑 장치

Claims (17)

1. 복수의 처리 소자(Processing Element, PE), 상기 PE 별로 매칭된 복수의 라우터 및 상기 라우터 간에 경로를 형성하는 광학적 링크 및 전기적 링크가 구성된 하이브리드 광학 네트워크 온 칩(Hybrid Optical Network-on-Chip, HONoC)의 태스크 매핑 장치에 있어서,
   복수의 태스크 간 관계 및 상기 복수의 태스크 별 데이터 크기를 정의하여 태스크 특성 그래프를 모델링하는 태스크 모델링부;
   상기 복수의 PE의 배치 및 PE간 연결 상태를 정의하여 PE 특성 그래프를 모델링하는 처리 소자 모델링부; 및
   상기 태스크 특성 그래프를 상기 PE 특성 그래프 상에 매핑하는 매핑 모델링을 복수 회 수행하되, 상기 복수 회의 매핑 모델링 중 상기 복수의 태스크 간에 상기 광학적 링크의 경로 중첩이 최소 값을 갖는 매핑 모델링의 결과에 따라 상기 PE 별로 상기 태스크를 매핑하는 태스크 매핑부를 포함하는 하이브리드 광학 네트워크 온 칩의 태스크 매핑 장치.
2. 제 1 항에 있어서,
   상기 태스크 매핑부는,
   상기 복수의 PE에 상기 복수의 태스크를 임시 할당하는 상기 매핑 모델링을 복수 회 처리하는 매핑 모델링 모듈;
   상기 복수의 태스크 별 최대 데이터 크기 및 상기 복수의 PE 별로 상기 라우터를 통해 연결된 상기 광학적 링크의 대역폭 크기에 기초하여, 상기 매핑 모델링 회차 별 경로 지연 비용을 산출하는 경로 지연 비용 산출 모듈; 및
   상기 경로 지연 비용이 최소 값인 매핑 모델링의 결과에 따라 상기 복수의 태스크를 상기 복수의 PE에 매핑하는 매핑 처리 모듈을 포함하는 하이브리드 광학 네트워크 온 칩의 태스크 매핑 장치.
3. 제 2 항에 있어서,
   상기 매핑 모델링 모듈은,
   상기 복수 회의 매핑 모델링마다 상이한 매핑 모델에 따라 상기 태스크를 임시 할당하는 하이브리드 광학 네트워크 온 칩의 태스크 매핑 장치.
4. 제 2 항에 있어서,
   상기 경로 지연 비용 산출 모듈은,
   매 회차의 상기 매핑 모델링에서, 상기 복수의 태스크가 순차적으로 임시 할당될 때마다 상기 임시 할당된 태스크와 기할당된 적어도 하나의 다른 태스크 간에 상기 광학적 링크 상의 경로 중첩이 발생된 경우에 대해 상기 임시 할당된 태스크의 제 1 경로 지연 비용을 산출하고,
   상기 복수의 태스크에 대한 임시 할당이 완료될 때까지 상기 제 1 경로 지연 비용을 누적하여 해당 매핑 모델링에 대한 제 2 경로 지연 비용을 산출하되,
   상기 제 1 경로 지연 비용은,
   상기 적어도 하나의 다른 태스크의 데이터 통신이 완료된 후 상기 임시 할당된 태스크의 데이터 통신을 처리하는데 필요한 값인 하이브리드 광학 네트워크 온 칩의 태스크 매핑 장치.
5. 제 2 항에 있어서,
   상기 경로 지연 비용 산출 모듈은,
   상기 경로 지연 비용 중 최소 값을 갖는 매핑 모델링의 결과에 따라 최적 매핑 모델 및 최소 경로 지연 비용을 매칭하여 저장하되,
   상기 매핑 모델링 모듈을 통한 매핑 모델링 수행 중에, 기저장된 상기 최소 경로 지연 비용보다 큰 값의 경로 지연 비용이 발생되면 상기 수행 중인 매핑 모델링을 중지시키고,
   상기 매핑 모델링의 수행이 완료된 상태에서의 경로 지연 비용이 상기 기저장된 최소 경로 지연 비용보다 작은 값인 경우, 상기 매핑 모델링의 결과에 따른 매핑 모델 및 경로 지연 비용을 상기 최적 매핑 모델 및 상기 최소 경로 지연 비용으로 갱신하여 저장하는 하이브리드 광학 네트워크 온 칩의 태스크 매핑 장치.
6. 제 1 항에 있어서,
   상기 복수의 태스크를 포함하는 애플리케이션의 실행에 따라 상기 PE 간 데이터 통신을 제어하는 데이터 통신 제어부를 더 포함하되,
   상기 데이터 통신 제어부는,
   상기 복수의 라우터 중 적어도 하나가 상기 전기적 링크를 통해 상기 태스크에 의해 설정된 목적지 라우터와의 경로 설정을 위한 패킷 스위칭을 처리하도록 제어하고, 상기 광학적 링크를 통해 상기 목적지 라우터와의 페이로드 패킷의 통신을 위한 서킷 스위칭을 처리하도록 제어하는 하이브리드 광학 네트워크 온 칩의 태스크 매핑 장치.
7. 복수의 처리 소자(Processing Element, PE), 상기 PE 별로 매칭된 복수의 라우터 및 상기 라우터 간에 경로를 형성하는 광학적 링크 및 전기적 링크가 구성된 하이브리드 광학 네트워크 온 칩(Hybrid Optical Network-on-Chip)의 태스크 매핑 장치를 통한 태스크 매핑 방법에 있어서,
   복수의 태스크 간 관계 및 상기 복수의 태스크 별 데이터 크기를 정의하여 태스크 특성 그래프를 모델링하는 단계;
   상기 복수의 PE의 배치 및 PE 간 연결 상태를 정의하여 PE 특성 그래프를 모델링하는 단계;
   상기 태스크 특성 그래프를 상기 PE 특성 그래프 상에 임시 매핑하는 매핑 모델링을 복수 회 수행하는 단계; 및
   상기 복수 회의 매핑 모델링 중 상기 복수의 태스크 간에 상기 광학적 링크의 경로 중첩이 최소 값을 갖는 매핑 모델링의 결과에 따라 상기 PE 별로 상기 태스크를 매핑하는 단계를 포함하는 하이브리드 광학 네트워크 온 칩의 태스크 매핑 방법.
8. 제 7 항에 있어서,
   상기 매핑 모델링을 복수 회 수행하는 단계는,
   상기 복수 회의 매핑 모델링마다 상이한 매핑 모델에 따라 상기 복수의 PE에 상기 복수의 태스크를 순차적으로 임시 할당하는 하이브리드 광학 네트워크 온 칩의 태스크 매핑 방법.
9. 제 8 항에 있어서,
   상기 PE 별로 상기 태스크를 매핑하는 단계는,
   상기 복수 회의 매핑 모델링마다, 상기 복수의 태스크 별 최대 데이터 크기 및 상기 복수의 PE 별로 상기 라우터를 통해 연결된 상기 광학적 링크의 대역폭 크기에 기초하여 경로 지연 비용을 산출하는 단계;
   상기 복수 회의 매핑 모델링 중 상기 경로 지연 비용이 최소 값인 매핑 모델링의 결과에 따른 최적 매핑 모델을 결정하는 단계; 및
   상기 최적 매핑 모델에 따라 상기 PE 별로 상기 태스크를 매핑하는 단계를 포함하는 하이브리드 광학 네트워크 온 칩의 태스크 매핑 방법.
10. 제 9 항에 있어서,
    상기 경로 지연 비용을 산출하는 단계는,
    상기 복수의 태스크가 순차적으로 임시 할당될 때마다 상기 임시 할당된 태스크와 기할당된 적어도 하나의 다른 태스크 간에 상기 광학적 링크 상의 경로 중첩이 발생된 경우에 대한 상기 임시 할당된 태스크의 제 1 경로 지연 비용을 산출하는 단계; 및
    상기 복수의 태스크 별 상기 제 1 경로 지연 비용을 누적하여 해당 매핑 모델링에 대한 제 2 경로 지연 비용을 산출하는 단계를 포함하되,
    상기 제 1 경로 지연 비용은,
    상기 적어도 하나의 다른 태스크의 데이터 통신이 완료된 후 상기 임시 할당된 태스크의 데이터 통신을 처리하는데 필요한 값인 하이브리드 광학 네트워크 온 칩의 태스크 매핑 방법.
11. 제 9 항에 있어서,
    상기 최적 매핑 모델을 결정하는 단계 이전에,
    상기 복수 회의 매핑 모델링 중 최소 값의 경로 지연 비용을 갖는 매핑 모델링의 결과에 따라 최적 매핑 모델 및 최소 경로 지연 비용을 매칭하여 저장하는 단계를 포함하되,
    상기 경로 지연 비용을 산출하는 단계는,
    어느 하나의 상기 매핑 모델링의 수행 중에, 기저장된 상기 최소 경로 지연 비용보다 큰 값의 경로 지연 비용이 발생되면 상기 수행 중인 매핑 모델링을 중지시키고,
    상기 어느 하나의 매핑 모델링의 수행이 완료된 상태에서의 경로 지연 비용이 상기 기저장된 최소 경로 지연 비용보다 작은 값인 경우, 상기 어느 하나의 매핑 모델링의 결과에 따른 매핑 모델 및 경로 지연 비용을 상기 최적 매핑 모델 및 상기 최소 경로 지연 비용으로 갱신하여 저장하는 하이브리드 광학 네트워크 온 칩 시스템의 태스크 매핑 방법.
12. 제 7 항에 있어서,
    상기 PE 별로 상기 태스크를 매핑하는 단계 이후에,
    상기 복수의 태스크를 포함하는 애플리케이션의 실행에 따라 상기 PE 간 데이터 통신을 제어하는 단계를 더 포함하되,
    상기 PE 간 데이터 통신을 제어하는 단계는,
    상기 복수의 라우터 중 적어도 하나가 상기 전기적 링크를 통해 상기 태스크에 의해 설정된 목적지 라우터와의 경로 설정을 위한 패킷 스위칭을 처리하도록 제어하거나, 상기 경로 설정에 의해 설정된 상기 광학적 링크를 통해 상기 목적지 라우터와의 페이로드 패킷의 통신을 위한 서킷 스위칭을 처리하도록 제어하는 하이브리드 광학 네트워크 온 칩 시스템의 태스크 매핑 방법.
13. 하이브리드 광학 네트워크 온 칩(Hybrid Optical Network-on- Chip) 시스템에 있어서,
    복수의 처리 소자(Processing Element, PE);
    상기 PE 별로 매칭되며, 광학적 링크를 통해 상기 PE 간 데이터의 전송을 위한 서킷 스위칭을 처리하고, 전기적 링크를 통해 상기 PE 간 경로 설정을 위한 패킷 스위칭을 처리하는 복수의 라우터; 및
    상기 복수의 PE에 복수의 태스크를 임시 매핑하는 매핑 모델링을 복수 회 수행하고, 상기 복수 회의 매핑 모델링 중 상기 복수의 태스크 간에 상기 광학적 링크의 경로 중첩이 최소 값을 갖는 매핑 모델링의 결과에 따라 상기 PE 별로 상기 태스크를 매핑하는 태스크 매핑 장치를 포함하는 하이브리드 광학 네트워크 온 칩 시스템.
14. 제 13 항에 있어서,
    상기 태스크 매핑 장치는,
    상기 복수의 태스크 별 최대 데이터 크기 및 상기 복수의 PE 별로 상기 라우터를 통해 연결된 상기 광학적 링크의 대역폭 크기에 기초하여, 상기 매핑 모델링 회차 별 경로 지연 비용을 산출하고,
    상기 경로 지연 비용이 최소 값인 매핑 모델링의 결과에 따라 상기 복수의 태스크를 상기 복수의 PE에 매핑하는 하이브리드 광학 네트워크 온 칩 시스템.
15. 제 14 항에 있어서,
    상기 태스크 매핑 장치는,
    매 회차의 상기 매핑 모델링에서, 상기 복수의 태스크를 상기 PE에 순차적으로 임시 할당하고,
    상기 임시 할당된 태스크와 기할당된 적어도 하나의 다른 태스크 간에 상기 광학적 링크 상의 경로 중첩이 발생된 경우에 대한 경로 지연 비용을 산출하고,
    상기 복수의 태스크에 대한 임시 할당이 완료될 때까지 상기 산출된 경로 지연 비용을 누적하여 해당 매핑 모델링에 대한 경로 지연 비용을 산출하는 하이브리드 광학 네트워크 온 칩 시스템.
16. 제 15 항에 있어서,
    상기 태스크 매핑 장치는,
    상기 매핑 모델링의 수행 중에 상기 누적된 경로 지연 비용이 기산출된 경로 지연 비용의 최소 값보다 큰 경우 상기 매핑 모델링의 수행을 중지시키고 다음 매핑 모델링을 수행하는 하이브리드 광학 네트워크 온 칩 시스템.
17. 제 13 항에 있어서,
    상기 태스크 매핑 장치는,
    상기 복수 회의 매핑 모델링마다 상이한 매핑 모델에 따라 상기 복수의 PE에 복수의 태스크를 임시 매핑하는 하이브리드 광학 네트워크 온 칩 시스템.

Images