1 |
1
그래프 압축을 수행하는 장치로서, 강한 소셜 컴포넌트(strong social component: SSC)에 속하는 버텍스(vertex)들에 관련된 변수들을, 동일한 속성을 가지는 것들끼리 연속적으로 배치되는 형태로 저장하되, 상기 버텍스들의 속성들 중 버텍스 레이블(label)을 가장 앞부분에 포함하고, 상기 버텍스 레이블을 제외한 나머지 속성들 내에서 상기 변수들이 저장되는 순서는 상기 버텍스 레이블의 순서에 대응하는 순서로 저장하는 그래픽 전역 메모리;연속적으로 배치되어 저장된 상기 동일한 속성을 가지는 변수들 중 적어도 하나를 병합하여 읽고(coalescing access) 저장하는 그래픽 지역 메모리; 상기 그래픽 지역 메모리에 저장된 변수들에 기반하여, 상기 버텍스들 중에서 압축 대상 버텍스를 결정하는 그래픽 처리부를 포함하는 장치
|
2 |
2
제 1 항에 있어서, 상기 그래픽 처리부는 다수의 하위 프로세서를 운영하고, 각 하위 프로세서에는 스레드(thread)가 할당되며, 각 스레드는 대응하는 SSC에 속하는 버텍스들 중에서 상기 압축 대상 버텍스를 탐색하는 것을 특징으로 하는, 장치
|
3 |
3
제 2 항에 있어서, 상기 그래픽 처리부는 상기 동일한 속성을 가지는 변수들 중 적어도 하나를 병합하여 읽고 상기 스레드에 할당하는 것을 특징으로 하는, 장치
|
4 |
4
제 1 항에 있어서, 상기 변수들은 소셜 컴포넌트 내의 버텍스 레이블(label), 엣지 레이블(edge label)을 포함하는 것을 특징으로 하는, 장치
|
5 |
5
제 1 항에 있어서, 상기 그래픽 처리부는 한 쌍의 버텍스 vi, vj에 대하여 조상 버텍스와 자손 버텍스를 비교하는 방식으로 상기 압축 대상 버텍스를 결정하는 것을 특징으로 하는, 장치
|
6 |
6
제 5 항에 있어서, 상기 그래픽 처리부는 상기 결정된 압축 대상 버텍스를 압축 대상 버텍스 집합에 추가하고, 상기 압축 대상 버텍스 집합을 상기 그래픽 전역 메모리에 저장한 뒤 반환하는 것을 특징으로 하는, 장치
|
7 |
7
그래프 압축 수행장치에 의해 그래프 압축을 수행하는 방법으로서, 그래픽 전역 메모리에 의해, 강한 소셜 컴포넌트(strong social component: SSC)에 속하는 버텍스(vertex)들에 관련된 변수들을, 동일한 속성을 가지는 것들끼리 연속적으로 배치되는 형태로 저장하되, 상기 버텍스들의 속성들 중 버텍스 레이블(label)을 가장 앞부분에 포함하고, 상기 버텍스 레이블을 제외한 나머지 속성들 내에서 상기 변수들이 저장되는 순서는 상기 버텍스 레이블의 순서에 대응하는 순서로 저장하는 단계; 그래픽 지역 메모리에 의해, 연속적으로 배치되어 저장된 상기 동일한 속성을 가지는 변수들 중 적어도 하나를 병합하여 읽고(coalescing access) 저장하는 단계;그래픽 처리부에 의해, 상기 저장된 변수들에 기반하여, 상기 버텍스들 중에서 압축 대상 버텍스를 결정하는 단계를 포함하는 방법
|
8 |
8
제 7 항에 있어서, 상기 압축 대상 버텍스는 SSC에 대응하는 각 스레드에서 병렬적으로 결정되는 것을 특징으로 하는, 방법
|
9 |
9
제 8 항에 있어서, 상기 병합하여 읽혀진 적어도 하나의 변수는 상기 스레드에 할당되는 것을 특징으로 하는, 방법
|
10 |
10
제 7 항에 있어서, 상기 변수들은 소셜 컴포넌트 내의 버텍스 레이블(label), 엣지 레이블(edge label)을 포함하는 것을 특징으로 하는, 방법
|
11 |
11
제 7 항에 있어서, 상기 압축 대상 버텍스를 결정하는 단계는, 한 쌍의 버텍스 vi, vj에 대하여 조상 버텍스와 자손 버텍스를 비교하는 방식을 포함하는 것을 특징으로 하는, 방법
|
12 |
12
제 11 항에 있어서, 상기 그래픽 처리부에 의해, 상기 결정된 압축 대상 버텍스를 압축 대상 버텍스 집합에 추가하고, 상기 압축 대상 버텍스 집합을 저장한 뒤 반환하는 단계를 더 포함함을 특징으로 하는, 방법
|