딥 러닝 모델의 그래프 탐색 방법 및 장치
METHOD AND APPARATUS FOR SEARCHING GRAPH OF DEEP LEARNING MODEL
특허 요약
본 발명은 딥 러닝 모델의 그래프 탐색에 대한 것으로, 딥 러닝 모델의 그래프가 입력되면, 상기 그래프를 구성하는 정점들 각각의 속성 정보에 추가된 프로파일 관련 정보를 초기화하고, 상기 정점들에 대한 위상 정렬(topological sort)을 진행하고, 위상 정렬된 순서에 따라 해당 정점을 탐색하고, 상기 탐색이 완료되면, 상기 해당 정점의 선행자 정점의 프로파일 관련 정보와 상기 해당 정점의 진입 연결선 정보를 기반으로 상기 해당 정점의 프로파일 관련 정보를 도출하여 상기 해당 정점의 속성 정보를 업데이트하고, 상기 그래프의 시작점으로부터 상기 해당 정점까지의 경로에서 상기 그래프를 구성하는 서로 다른 연결선들이 모두 탐색될 경우, 상기 경로 정보를 출력한다. 또한 본 발명은 제안한 데이터 구조를 통해 그래프 탐색을 수행함으로써, 다항 시간 내에 탐색하고자 하는 연결선을 포함하는 최소 실행 횟수와 이때의 경로를 구한다.
청구항
번호청구항
1

딥 러닝 모델의 그래프 탐색을 수행하는 방법에 있어서,딥 러닝 모델의 그래프가 입력되면, 상기 그래프를 구성하는 정점들 각각의 속성 정보에 추가된 프로파일 관련 정보를 초기화하는 과정과,상기 정점들에 대한 위상 정렬(topological sort)을 진행하고, 위상 정렬된 순서에 따라 해당 정점을 탐색하는 과정과,상기 탐색이 완료되면, 상기 해당 정점의 선행자 정점의 프로파일 관련 정보와 상기 해당 정점의 진입 연결선 정보를 기반으로 상기 해당 정점의 프로파일 관련 정보를 도출하여 상기 해당 정점의 속성 정보를 업데이트하는 과정과,상기 그래프의 시작점으로부터 상기 해당 정점까지의 경로에서 상기 그래프를 구성하는 서로 다른 연결선들이 모두 탐색될 경우, 상기 경로 정보를 출력하는 과정을 포함하는 그래프 탐색 방법.

2

제1항에 있어서,상기 프로파일 관련 정보는 상기 서로 다른 연결선들의 탐색 여부를 나타내는 프로파일 연결선 리스트 정보와 상기 시작점으로부터 상기 해당 정점까지의 경로를 나타내는 프로파일 경로 정보를 포함함을 특징으로 하는 그래프 탐색 방법.

3

제2항에 있어서,상기 업데이트 과정은, 상기 해당 정점에 대한 진입 연결선이 한 개일 경우, 상기 해당 정점의 선행자 정점의 프로파일 연결선 리스트 정보와 상기 진입 연결선 정보를 기반으로 상기 해당 정점의 프로파일 연결선 리스트 정보 및 프로파일 경로 정보를 도출하여 상기 해당 정점의 속성 정보를 업데이트하는 과정을 포함함을 특징으로 하는 그래프 탐색 방법.

4

제2항에 있어서,상기 업데이트 과정은, 상기 해당 정점에 대한 진입 연결선이 복수 개일 경우, 진입 연결선들 각각에 대한 선행자 정점의 프로파일 연결선 리스트 정보와 해당 진입 연결선 정보를 기반으로 상기 진입 연결선 개수에 상응하는 후보 프로파일 연결선 리스트 정보들을 도출하고, 후보 프로파일 연결선 리스트 정보들의 포함관계를 판단하여 상위 집합에 해당하는 프로파일 연결선 리스트 정보 및 프로파일 경로 정보를 도출하여 상기 해당 정점의 속성 정보를 업데이트하는 과정을 포함함을 특징으로 하는 그래프 탐색 방법.

5

제2항에 있어서,상기 프로파일 연결선 리스트의 값이 상기 서로 다른 연결선들이 모두 탐색되었음을 나타내는 특정 값을 만족할 경우, 상기 그래프 탐색을 종료하는 과정을 더 포함하는 그래프 탐색 방법.

6

딥 러닝 모델의 그래프 탐색을 수행하는 장치에 있어서,딥 러닝 모델의 그래프를 입력 받는 입력부와, 상기 그래프를 구성하는 정점들 각각의 속성 정보에 추가된 프로파일 관련 정보를 초기화하고, 상기 정점들에 대한 위상 정렬(topological sort)을 진행하고, 위상 정렬된 순서에 따라 해당 정점을 탐색하고, 상기 탐색이 완료되면, 상기 해당 정점의 선행자 정점의 프로파일 관련 정보와 상기 해당 정점의 진입 연결선 정보를 기반으로 상기 해당 정점의 프로파일 관련 정보를 도출하여 상기 해당 정점의 속성 정보를 업데이트하는 프로세서와,상기 그래프의 시작점으로부터 상기 해당 정점까지의 경로에서 상기 그래프를 구성하는 서로 다른 연결선들이 모두 탐색될 경우, 상기 경로 정보를 출력하는 출력부를 포함하는 그래프 탐색 장치.

7

제6항에 있어서,상기 프로파일 관련 정보는 상기 서로 다른 연결선들의 탐색 여부를 나타내는 프로파일 연결선 리스트 정보와 상기 시작점으로부터 상기 해당 정점까지의 경로를 나타내는 프로파일 경로 정보를 포함함을 특징으로 하는 그래프 탐색 장치.

8

제7항에 있어서,상기 프로세서는, 상기 해당 정점에 대한 진입 연결선이 한 개일 경우, 상기 해당 정점의 선행자 정점의 프로파일 연결선 리스트 정보와 상기 진입 연결선 정보를 기반으로 상기 해당 정점의 프로파일 연결선 리스트 정보 및 프로파일 경로 정보를 도출하여 상기 해당 정점의 속성 정보를 업데이트함을 특징으로 하는 그래프 탐색 장치.

9

제7항에 있어서,상기 프로세서는, 상기 해당 정점에 대한 진입 연결선이 복수 개일 경우, 진입 연결선들 각각에 대한 선행자 정점의 프로파일 연결선 리스트 정보와 해당 진입 연결선 정보를 기반으로 상기 진입 연결선 개수에 상응하는 후보 프로파일 연결선 리스트 정보들을 도출하고, 후보 프로파일 연결선 리스트 정보들의 포함관계를 판단하여 상위 집합에 해당하는 프로파일 연결선 리스트 정보 및 프로파일 경로 정보를 도출하여 상기 해당 정점의 속성 정보를 업데이트함을 특징으로 하는 그래프 탐색 장치.

10

제7항에 있어서,상기 프로세서는, 상기 프로파일 연결선 리스트의 값이 상기 서로 다른 연결선들이 모두 탐색되었음을 나타내는 특정 값을 만족할 경우, 상기 그래프 탐색을 종료함을 특징으로 하는 그래프 탐색 장치.

도면대표도면