그래프 데이터의 입력에 연동하여,상기 그래프 데이터를 GPU의 캐시를 고려하여, 복수의 서브그래프로 분할하는 단계;상기 복수의 서브그래프 각각의 도착 정점을 확인하는 단계;상기 확인된 도착 정점의 개수가 임계치 이상인 제1 서브그래프를 상기 GPU로 전송하되, 상기 확인된 도착 정점의 개수가 임계치 미만인 제2 서브그래프에 대해서는 간선 데이터 만을 상기 GPU로 전송하는 단계;상기 복수의 서브그래프 각각에 대한, 상기 GPU에서의 처리를 위한 스케줄링을 수행하는 단계로서,ⅰ)상기 제1 서브그래프에 대해 High-Value Subgraph Process를 수행하여, 상기 제1 서브그래프를 연산한 후, 상기 제1 서브그래프를 상기 GPU의 전역 메모리에 저장하는 단계; 및ⅱ)상기 간선 데이터에 대해 Low-Value Subgraph Process를 수행하여, 상기 간선 데이터를 한번만 연산하고 상기 GPU의 전역 메모리에 저장하지 않는 단계를 포함하는, GPU를 이용한 그래프 알고리즘 처리 방법.

삭제

삭제

삭제

제1항에 있어서,상기 GPU에서의 처리를 위한 스케줄링을 수행하는 단계로서,상기 High-value subgraph Process에 의해, 상기 제1 서브그래프 내 UD(Useful Data), PUD(Potentially Useful Data), 및 간선 데이터를 추출하는 단계;상기 제1 서브그래프가 상기 전역 메모리에 기존재하는지 확인하는 단계;상기 확인 결과, 존재하지 않으면, 상기 UD, 상기 PUD, 및 상기 간선 데이터를 연산하여, 상기 제1 서브그래프를 상기 GPU에서 처리하는 스케줄을 결정하는 단계; 및상기 확인 결과, 존재하면, 상기 UD, 상기 PUD, 및 상기 간선 데이터를 큐에 할당하여, 상기 제1 서브그래프를 상기 GPU에서 처리하는 스케줄을 결정하지 않고 지연하는 단계를 더 포함하는, GPU를 이용한 그래프 알고리즘 처리 방법.

제1항에 있어서,상기 분할하는 단계는,Cache-blocking Vertex-cuts를 통해, 상기 그래프 데이터를, 상기 GPU의 L2 Cache 보다 작은 크기를 갖는, 상기 복수의 서브그래프로 분할하는 단계를 포함하는, GPU를 이용한 그래프 알고리즘 처리 방법.

제1항에 있어서,상기 분할하는 단계는,서브그래프 마다 정점 개수를 균등하게 하여, 상기 서브그래프를 분할하는 단계; 또는시작 정점과 도착 정점이 같은 서브그래프에 간선 데이터를 할당하여, 상기 서브그래프를 분할하는 단계를 포함하는, GPU를 이용한 그래프 알고리즘 처리 방법.

그래프 데이터의 입력에 연동하여,상기 그래프 데이터를 GPU의 캐시를 고려하여, 복수의 서브그래프로 분할하는 그래프 분할 모듈;상기 복수의 서브그래프 각각의 도착 정점을 확인하고, 상기 확인된 도착 정점의 개수가 임계치 이상인 제1 서브그래프를 상기 GPU로 전송하되, 상기 확인된 도착 정점의 개수가 임계치 미만인 제2 서브그래프에 대해서는 간선 데이터 만을 상기 GPU로 전송하는 분배 모듈; 및상기 복수의 서브그래프 각각에 대한, 상기 GPU에서의 처리를 위한 스케줄링을 수행하는 차등 서브그래프 분할 모듈를 포함하고,상기 차등 서브그래프 분할 모듈은,ⅰ)상기 제1 서브그래프에 대해 High-Value Subgraph Process를 수행하여, 상기 제1 서브그래프를 연산한 후, 상기 제1 서브그래프를 상기 GPU의 전역 메모리에 저장하고,ⅱ)상기 간선 데이터에 대해 Low-Value Subgraph Process를 수행하여, 상기 간선 데이터를 한번만 연산하고 상기 GPU의 전역 메모리에 저장하지 않는,GPU를 이용한 그래프 알고리즘 처리 장치.

삭제

삭제

삭제

제8항에 있어서,상기 차등 서브그래프 분할 모듈은,상기 High-value subgraph Process에 의해, 상기 제1 서브그래프 내 UD(Useful Data), PUD(Potentially Useful Data), 및 간선 데이터를 추출하고,상기 제1 서브그래프가 전역 메모리에 기존재하는지 확인하며,상기 확인 결과, 존재하지 않으면, 상기 UD, 상기 PUD, 및 상기 간선 데이터를 연산하여, 상기 제1 서브그래프를 상기 GPU에서 처리하는 스케줄을 결정하고,상기 확인 결과, 존재하면, 상기 UD, 상기 PUD, 및 상기 간선 데이터를 큐에 할당하여, 상기 제1 서브그래프를 상기 GPU에서 처리하는 스케줄을 결정하지 않고 지연하는,GPU를 이용한 그래프 알고리즘 처리 장치.

제8항에 있어서,상기 그래프 분할 모듈은,Cache-blocking Vertex-cut을 통해, 상기 그래프 데이터를, 상기 GPU의 L2 Cache 보다 작은 크기를 갖는, 상기 복수의 서브그래프로 분할하는GPU를 이용한 그래프 알고리즘 처리 장치.

제8항에 있어서,상기 그래프 분할 모듈은,서브그래프 마다 정점 개수를 균등하게 하여, 상기 서브그래프를 분할하거나, 또는 시작 정점과 도착 정점이 같은 서브그래프에 간선 데이터를 할당하여, 상기 서브그래프를 분할하는,GPU를 이용한 그래프 알고리즘 처리 장치.

제1항, 제5항 내지 제7항 중 어느 한 항의 방법을 실행시키기 위한 프로그램을 기록한 컴퓨터 판독 가능한 기록매체.