| 1 |
1
CPU에서, 입력되는 제1 그래프 스트림을 GPU로 전송하는 단계;상기 제1 그래프 스트림 이후 입력되는 제2 그래프 스트림 내에, 상기 제1 그래프 스트림의 정점이 포함되는 경우,상기 CPU에서, CPU 메모리로부터 CCLG 테이블을 로딩하여, 상기 제2 그래프 스트림의 입력에 의해 상기 제1 그래프 스트림에서 변경될 그래프 영역을 판별하는 단계;상기 CPU에서, 상기 판별된 그래프 영역을 포함하여 재계산 리스트를 구축하는 단계; 및상기 재계산 리스트에 기초한 계산에 의해, 상기 GPU에서 결과 파일이 생성됨에 따라, 상기 CPU에서, 상기 결과 파일을 상기 CCLG 테이블에 병합 함으로써, 상기 GPU에서의 상기 제1 그래프 스트림의 업데이트가 반영되도록 하는 단계를 포함하는 동적 그래프에서의 점진적 연결요소 판별 방법
|
| 2 |
2
제1항에 있어서,상기 GPU에서, 상기 CPU로부터 전송받은 상기 제1 그래프 스트림으로부터 연결요소를 계산하여 상기 CCLG 테이블을 생성하는 단계;상기 GPU에서, 상기 생성된 CCLG 테이블을, 상기 CPU 메모리에 저장하는 단계; 및상기 GPU에서, 상기 CPU로부터 전송받은 상기 재계산 리스트에 따라, 상기 그래프 영역으로부터 상기 연결요소를 재계산하여, 상기 제1 그래프 스트림의 업데이트를 처리하고, 상기 결과 파일을 생성하는 단계를 더 포함하는 동적 그래프에서의 점진적 연결요소 판별 방법
|
| 3 |
3
제2항에 있어서,상기 제1 그래프 스트림 내의 적어도 하나의 정점이 상기 제2 그래프 스트림에 포함되는 경우, 상기 CPU에서, 입력된 제2 그래프 스트림에 대한 실행 경로를, 상기 재계산 리스트의 구축을 위한 상기 CPU 내 IDRP부로 결정하는 단계; 및상기 제1 그래프 스트림 내의 적어도 하나의 정점이 상기 제2 그래프 스트림에 포함되지 않는 경우, 상기 CPU에서, 입력된 제2 그래프 스트림에 대한 실행 경로를, 상기 제2 그래프 스트림에 대한 CCLG 테이블 생성을 위한 상기 GPU 내 정적 계산부로 결정하는 단계를 더 포함하는 동적 그래프에서의 점진적 연결요소 판별 방법
|
| 4 |
4
제2항에 있어서,상기 CCLG 테이블을 생성하는 단계는,상기 제1 그래프 스트림을 구성하는 복수의 분리된 서브그래프 각각을, 상기 각각의 서브그래프를 구성하는 각 정점의 연결요소로서 계산하는 단계;상기 각 서브그래프의 번호를, 연결요소 레이블로서 상기 각 정점에 부여하고, 상기 각 정점에 부여된 연결요소 레이블을, 상기 각 정점의 입력 순서대로 부여된 고유번호에 연관시켜, 연결요소 테이블에 기록하는 단계;상기 연결요소 테이블 내 동일한 연결요소 레이블을 가지는 상기 각 정점 중에서 가장 앞선 고유번호가 부여된 정점을, 해당 정점이 속해 있는 연결요소에 대한 대표정점으로서 지정하는 단계; 및상기 연결요소 테이블 내 연결요소 레이블을, 각 정점이 상기 대표정점인지에 따라 수정하여, 상기 CCLG 테이블을 생성하는 단계를 포함하는 동적 그래프에서의 점진적 연결요소 판별 방법
|
| 5 |
5
제4항에 있어서,상기 각 정점이 상기 대표정점인지에 따라 수정하여, 상기 CCLG 테이블을 생성하는 단계는,상기 연결요소 테이블 내 상기 대표정점의 경우,상기 대표정점에 부여된 연결요소 레이블을, 상기 대표정점이 속해 있는 연결요소를 구성하는 각 정점의 개수에 마이너스 부호를 붙인 '음수값'으로 대체하는 단계; 및상기 연결요소 테이블 내, 상기 대표정점을 제외한 나머지 정점의 경우,상기 나머지 정점에 부여된 연결요소 레이블을, 상기 나머지 정점이 속해 있는 연결요소에 대한 대표정점의 고유번호로 대체하는 단계를 포함하는 동적 그래프에서의 점진적 연결요소 판별 방법
|
| 6 |
6
제5항에 있어서,상기 그래프 영역을 판별하는 단계는,상기 제2 그래프 스트림이, 상기 제1 그래프 스트림에 포함된 2개의 정점을 이은 간선의 리스트로 구성되는 경우,상기 CCLG 테이블로부터, 상기 2개의 정점 각각에 부여된 연결요소 레이블을 식별하는 단계; 및상기 식별된 각 연결요소 레이블이 서로 다르면, 상기 각 연결요소 레이블을, 상기 그래프 영역으로서 판별하는 단계를 포함하는 동적 그래프에서의 점진적 연결요소 판별 방법
|
| 7 |
7
제6항에 있어서,상기 재계산 리스트를 구축하는 단계는,상기 그래프 영역으로서 판별된 상기 각 연결요소 레이블을 포함하여 상기 재계산 리스트를 구축 시,상기 각 연결요소 레이블 중 음수값에 해당하는 제1 연결요소 레이블을, 대표정점의 연결요소 레이블로서, 상기 재계산 리스트에 삽입하는 단계;상기 각 연결요소 레이블 중 '0' 또는 양수값에 해당하는 제2 연결요소 레이블이 있으면,상기 CCLG 테이블로부터 상기 제2 연결요소 레이블과 일치하는 고유번호를 가지는 대표정점을 찾고, 해당 대표정점의 연결요소 레이블을, 상기 제2 연결요소 레이블 대신에, 상기 재계산 리스트에 삽입하는 단계; 및상기 재계산 리스트에 상기 연결요소 레이블이 삽입된 상기 대표정점의 고유번호를, 상기 재계산 리스트에 삽입하는 단계를 포함하는 동적 그래프에서의 점진적 연결요소 판별 방법
|
| 8 |
8
제7항에 있어서,상기 대표정점의 연결요소 레이블 및 고유번호가 삽입된 상기 재계산 리스트가 상기 CPU로부터 전송되면,상기 결과 파일을 생성하는 단계는,Weighted-Quick-Union을 기반으로, 상기 재계산 리스트 내 각 대표정점의 연결요소 레이블에 대한 절댓값 크기를 서로 비교하여, 더 작은 값의 연결요소 레이블을 SC값으로 정의하고, 더 큰 값의 연결요소 레이블을 LC값으로 정의하는 단계;상기 LC값으로 정의된 상기 대표정점의 연결요소 레이블을, 상기 SC값으로 정의된 상기 대표정점의 연결요소 레이블을 가산함으로써 변경하는 단계;상기 SC값으로 정의된 상기 대표정점의 연결요소 레이블을, 상기 LC값으로 정의된 상기 대표정점의 고유번호로 변경하는 단계; 및상기 대표정점의 변경된 연결요소 레이블 및 고유번호를 포함하여, 상기 결과 파일을 생성하는 단계를 포함하는 동적 그래프에서의 점진적 연결요소 판별 방법
|
| 9 |
9
제8항에 있어서,상기 CCLG 테이블에 병합 함으로써, 상기 GPU에서의 제1 그래프 스트림의 업데이트가 반영되도록 하는 단계는,상기 결과 파일 내 고유번호에 의해 매칭되는, 상기 CCLG 테이블 내 상기 대표정점의 연결요소 레이블을, 상기 결과 파일 내 변경된 연결요소 레이블로 교체하는 단계; 및상기 교체에 의해, 음수값이 아닌 연결요소 레이블을 가지는 제1 정점이 있으면, 상기 제1 정점의 고유번호와 일치하는 연결요소 레이블을 가지는 상기 CCLG 테이블 내 모든 정점의 연결요소 레이블을, 상기 제1 정점의 연결요소 레이블로 더 교체하는 단계를 포함하는 동적 그래프에서의 점진적 연결요소 판별 방법
|
| 10 |
10
제2항에 있어서,상기 CPU에서, 상기 제2 그래프 스트림에 대해 구축된 재계산 리스트를 상기 GPU로 전송하는 동안에, 상기 CPU에서, 상기 제2 그래프 스트림 이후에 입력되는 제3 그래프 스트림에 대한 재계산 리스트의 구축을 비동기로 실행하는 단계;상기 GPU에서, 상기 CPU로부터 전송받은 재계산 리스트에 따라 상기 제1 그래프 스트림의 업데이트를 처리하는 동안에, 상기 CPU에서, 상기 제3 그래프 스트림에 대해 구축된 재계산 리스트의 상기 GPU로의 전송을 비동기로 실행하는 단계;상기 GPU에서, 상기 제1 그래프 스트림의 업데이트를 처리하여 생성된 결과 파일을 상기 CPU로 전송하는 동안에, 상기 GPU에서, 상기 제3 그래프 스트림에 대해 구축된 재계산 리스트에 따라 상기 제2 그래프 스트림의 업데이트 처리를 비동기로 실행하는 단계; 및상기 CPU에서, 상기 GPU로부터 전송받은 결과 파일을 상기 CCLG 테이블에 병합하는 동안에, 상기 GPU에서, 상기 제2 그래프 스트림의 업데이트를 처리하여 생성된 결과 파일의 상기 CPU로의 전송을 비동기로 실행하는 단계를 더 포함하는 동적 그래프에서의 점진적 연결요소 판별 방법
|
| 11 |
11
입력되는 제1 그래프 스트림을 GPU로 전송하는, CPU 내 듀얼패스 실행부;상기 제1 그래프 스트림 이후 입력되는 제2 그래프 스트림 내에, 상기 제1 그래프 스트림의 정점이 포함되는 경우,CPU 메모리로부터 CCLG 테이블을 로딩하여, 상기 제2 그래프 스트림의 입력에 의해 상기 제1 그래프 스트림에서 변경될 그래프 영역을 판별하고, 상기 판별된 그래프 영역을 포함하여 재계산 리스트를 구축하는 CPU 내 IDRP부; 및상기 재계산 리스트에 기초한 계산에 의해, 상기 GPU에서 결과 파일이 생성됨에 따라, 상기 결과 파일을 상기 CCLG 테이블에 병합 함으로써, 상기 GPU에서의 상기 제1 그래프 스트림의 업데이트가 반영되도록 하는, CPU 내 병합부를 포함하는 동적 그래프에서의 점진적 연결요소 판별 시스템
|
| 12 |
12
제11항에 있어서,상기 CPU로부터 전송받은 상기 제1 그래프 스트림으로부터 연결요소를 계산하여 상기 CCLG 테이블을 생성하고, 상기 생성된 CCLG 테이블을, 상기 CPU 메모리에 저장하는, GPU 내 정적 계산부; 및상기 CPU로부터 전송받은 상기 재계산 리스트에 따라, 상기 그래프 영역으로부터 상기 연결요소를 재계산하여, 상기 제1 그래프 스트림의 업데이트를 처리하고, 상기 결과 파일을 생성하는, GPU 내 그래프 업데이트부를 더 포함하는 동적 그래프에서의 점진적 연결요소 판별 시스템
|
| 13 |
13
제12항에 있어서,상기 듀얼패스 실행부는,상기 제1 그래프 스트림 내의 적어도 하나의 정점이 상기 제2 그래프 스트림에 포함되는 경우, 입력된 제2 그래프 스트림에 대한 실행 경로를, 상기 재계산 리스트의 구축을 위한 상기 IDRP부로 결정하고,상기 제1 그래프 스트림 내의 적어도 하나의 정점이 상기 제2 그래프 스트림에 포함되지 않는 경우, 입력된 제2 그래프 스트림에 대한 실행 경로를, 상기 CCLG 테이블 생성을 위한 상기 정적 계산부로 결정하는동적 그래프에서의 점진적 연결요소 판별 시스템
|
| 14 |
14
제12항에 있어서,상기 정적 계산부는,상기 제1 그래프 스트림을 구성하는 복수의 분리된 서브그래프 각각을, 상기 각각의 서브그래프를 구성하는 각 정점의 연결요소로서 계산하고,상기 각 서브그래프의 번호를, 연결요소 레이블로서 상기 각 정점에 부여하고, 상기 각 정점에 부여된 연결요소 레이블을, 상기 각 정점의 입력 순서대로 부여된 고유번호에 연관시켜, 연결요소 테이블에 기록하고,상기 연결요소 테이블 내 동일한 연결요소 레이블을 가지는 상기 각 정점 중에서 가장 앞선 고유번호가 부여된 정점을, 해당 정점이 속해 있는 연결요소에 대한 대표정점으로서 지정하고,상기 연결요소 테이블 내 연결요소 레이블을, 각 정점이 상기 대표정점인지에 따라 수정하여, 상기 CCLG 테이블을 생성하는동적 그래프에서의 점진적 연결요소 판별 시스템
|
| 15 |
15
제14항에 있어서,상기 정적 계산부는,상기 연결요소 테이블 내 상기 대표정점의 경우,상기 대표정점에 부여된 연결요소 레이블을, 상기 대표정점이 속해 있는 연결요소를 구성하는 각 정점의 개수에 마이너스 부호를 붙인 '음수값'으로 대체하고,상기 연결요소 테이블 내, 상기 대표정점을 제외한 나머지 정점의 경우,상기 나머지 정점에 부여된 연결요소 레이블을, 상기 나머지 정점이 속해 있는 연결요소에 대한 대표정점의 고유번호로 대체하는동적 그래프에서의 점진적 연결요소 판별 시스템
|
| 16 |
16
제15항에 있어서,상기 IDRP부는,상기 제2 그래프 스트림이, 상기 제1 그래프 스트림에 포함된 2개의 정점을 이은 간선의 리스트로 구성되는 경우,상기 CCLG 테이블로부터, 상기 2개의 정점 각각에 부여된 연결요소 레이블을 식별하고, 상기 식별된 각 연결요소 레이블이 서로 다르면, 상기 각 연결요소 레이블을, 상기 그래프 영역으로서 판별하는동적 그래프에서의 점진적 연결요소 판별 시스템
|
| 17 |
17
제16항에 있어서,상기 IDRP부는,상기 그래프 영역으로서 판별된 상기 각 연결요소 레이블을 포함하여 상기 재계산 리스트를 구축 시, 상기 각 연결요소 레이블 중 음수값에 해당하는 제1 연결요소 레이블을, 대표정점의 연결요소 레이블로서, 상기 재계산 리스트에 삽입하고,상기 각 연결요소 레이블 중 '0' 또는 양수값에 해당하는 제2 연결요소 레이블이 있으면, 상기 CCLG 테이블로부터 상기 제2 연결요소 레이블과 일치하는 고유번호를 가지는 대표정점을 찾고, 해당 대표정점의 연결요소 레이블을, 상기 제2 연결요소 레이블 대신에, 상기 재계산 리스트에 삽입하고,상기 재계산 리스트에 상기 연결요소 레이블이 삽입된 상기 대표정점의 고유번호를, 상기 재계산 리스트에 삽입하는동적 그래프에서의 점진적 연결요소 판별 시스템
|
| 18 |
18
제17항에 있어서,상기 대표정점의 연결요소 레이블 및 고유번호가 삽입된 상기 재계산 리스트가 상기 CPU로부터 전송되면,상기 그래프 업데이트부는,Weighted-Quick-Union을 기반으로, 상기 재계산 리스트 내 각 대표정점의 연결요소 레이블에 대한 절댓값 크기를 서로 비교하여, 더 작은 값의 연결요소 레이블을 SC값으로 정의하고, 더 큰 값의 연결요소 레이블을 LC값으로 정의하고,상기 LC값으로 정의된 상기 대표정점의 연결요소 레이블을, 상기 SC값으로 정의된 상기 대표정점의 연결요소 레이블을 가산함으로써 변경하고, 상기 SC값으로 정의된 상기 대표정점의 연결요소 레이블을, 상기 LC값으로 정의된 상기 대표정점의 고유번호로 변경하고,상기 대표정점의 변경된 연결요소 레이블 및 고유번호를 포함하여, 상기 결과 파일을 생성하는동적 그래프에서의 점진적 연결요소 판별 시스템
|
| 19 |
19
제18항에 있어서,상기 병합부는,상기 결과 파일 내 고유번호에 의해 매칭되는, 상기 CCLG 테이블 내 상기 대표정점의 연결요소 레이블을, 상기 결과 파일 내 변경된 연결요소 레이블로 교체하고,상기 교체에 의해, 음수값이 아닌 연결요소 레이블을 가지는 제1 정점이 있으면, 상기 제1 정점의 고유번호와 일치하는 연결요소 레이블을 가지는 상기 CCLG 테이블 내 모든 정점의 연결요소 레이블을, 상기 제1 정점의 연결요소 레이블로 더 교체하는동적 그래프에서의 점진적 연결요소 판별 시스템
|
| 20 |
20
제12항에 있어서,상기 IDRP부에서, 상기 제2 그래프 스트림에 대해 구축된 재계산 리스트를 상기 GPU로 전송하는 동안에, 상기 IDRP부에서, 상기 제2 그래프 스트림 이후에 입력되는 제3 그래프 스트림에 대한 재계산 리스트의 구축을 비동기로 실행하고,상기 그래프 업데이트부에서, 상기 CPU로부터 전송받은 재계산 리스트에 따라 상기 제1 그래프 스트림의 업데이트를 처리하는 동안에, 상기 IDRP부에서, 상기 제3 그래프 스트림에 대해 구축된 재계산 리스트의 상기 GPU로의 전송을 비동기로 실행하고,상기 그래프 업데이트부에서, 상기 제1 그래프 스트림의 업데이트를 처리하여 생성된 결과 파일을 상기 CPU로 전송하는 동안에, 상기 그래프 업데이트부에서, 상기 제3 그래프 스트림에 대해 구축된 재계산 리스트에 따라 상기 제2 그래프 스트림의 업데이트 처리를 비동기로 실행하고,상기 병합부에서, 상기 GPU로부터 전송받은 결과 파일을 상기 CCLG 테이블에 병합하는 동안에, 상기 그래프 업데이트부에서, 상기 제2 그래프 스트림의 업데이트를 처리하여 생성된 결과 파일의 상기 CPU로의 전송을 비동기로 실행하는동적 그래프에서의 점진적 연결요소 판별 시스템
|
