지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학위논문
- 저자정보
- 지도교수
- 안형찬
- 발행연도
- 2023
- 저작권
- 연세대학교 논문은 저작권에 의해 보호받습니다.
이용수12
이 논문의 연구 히스토리 (2)
- 이 논문의 후속연구가 궁금하신가요?
- 연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
- 이 논문의 연구 히스토리 확인하기
초록· 키워드
오류제보하기
그래프 채색 문제는, 그래프 G=(V,E)가 주어졌을 때 모든 간선 (u,v)∈E에 대해 C(u)≠C(v)를 만족하는 사상 C:V→N을 찾는 문제이다. 이 문제는 컴퓨터과학 내에서뿐만 아니라 컴퓨터과학 외에서도 널리 응용되는데, 이에 따라 그래프 채색 문제를 효율적으로 해결하는 알고리즘이 지속적으로 연구되었다.
본 논문에서는 그래프 채색 알고리즘의 GPGPU 상에서의 구현을 최적화하는 새로운 휴리스틱을 제시한다. GPGPU는 병렬 처리에 특화되어 있는 플랫폼이지만, 한편으로는 기존의 병렬 컴퓨팅 모델과는 차별화된 구조를 갖는다. 따라서 그래프 채색 알고리즘과 같이 병렬성을 띠는 알고리즘을 GPGPU 상에 구현하여 성능 향상을 얻을 수 있으나, 이를 위해서는 GPGPU 구조의 특징을 최대한 고려하여야 한다.
첫째, 본 논문에서는 입력에 따라 최적의 그래프 표현 방식을 선택하는 휴리스틱을 제시한다. 기존에 Alabandi et al.이 GPGPU에 적합한 그래프 채색 알고리즘을 제시한 바 있으나, 단일한 자료 구조만을 사용한다는 제한으로 인해 GPGPU의 최대 성능을 이끌어 내는 것에는 한계가 있었다. 이에 본 논문에서는 GPGPU에 알맞은 복수의 자료 구조를 채택하고, 이로써 개선된 성능을 실험적으로 측정하였다. 이 실험은 공개 리파지터리들의 그래프를 벤치마크로 사용해 RTX 3090과 RTX 2060 및 GTX 1050 Ti에서 수행하였다. 이 결과를 바탕으로, 입력 그래프의 차수 등을 토대로 적합한 그래프 표현 방식을 자동으로 선택해주는 휴리스틱을 개발하였고, 이는 RTX 3090, RTX 2060 및 GTX 1050 Ti에서 각각 기존 알고리즘의 수행 시간 대비 평균 7.85%, 8.01%, 10.43%의 수행 속도 개선 효과를 나타내었다. 또, 휴리스틱을 적용했음에도 수행 속도 개선 효과가 저조한 인스턴스들에 대한 개별 분석을 시행하였다.
둘째, 입력에 따라 수행할 알고리즘의 종류를 선택할 수 있도록 휴리스틱을 개선하는 방법을 검토한다. 휴리스틱이 선택할 수 있는 대체 알고리즘으로는 극대 독립 집합을 반복적으로 찾아 색을 칠하는 Luby의 병렬 알고리즘을 고려하였다. 위에서와 마찬가지로 같은 벤치마크를 사용하여 RTX 3090과 RTX 2060 및 GTX 1050 Ti에서 수행 속도가 얼마나 개선되는지를 실험적으로 확인하였으나, 실험 결과 이 알고리즘은 수행 속도 개선 효과를 얻기 어려운 것으로 나타나, Luby의 알고리즘 외의 새로운 알고리즘을 적용해야 함을 시사하였다.
마지막으로, 본 논문 이후의 향후 연구 방향에 대해 간략히 논의할 것이다.
본 논문에서는 그래프 채색 알고리즘의 GPGPU 상에서의 구현을 최적화하는 새로운 휴리스틱을 제시한다. GPGPU는 병렬 처리에 특화되어 있는 플랫폼이지만, 한편으로는 기존의 병렬 컴퓨팅 모델과는 차별화된 구조를 갖는다. 따라서 그래프 채색 알고리즘과 같이 병렬성을 띠는 알고리즘을 GPGPU 상에 구현하여 성능 향상을 얻을 수 있으나, 이를 위해서는 GPGPU 구조의 특징을 최대한 고려하여야 한다.
첫째, 본 논문에서는 입력에 따라 최적의 그래프 표현 방식을 선택하는 휴리스틱을 제시한다. 기존에 Alabandi et al.이 GPGPU에 적합한 그래프 채색 알고리즘을 제시한 바 있으나, 단일한 자료 구조만을 사용한다는 제한으로 인해 GPGPU의 최대 성능을 이끌어 내는 것에는 한계가 있었다. 이에 본 논문에서는 GPGPU에 알맞은 복수의 자료 구조를 채택하고, 이로써 개선된 성능을 실험적으로 측정하였다. 이 실험은 공개 리파지터리들의 그래프를 벤치마크로 사용해 RTX 3090과 RTX 2060 및 GTX 1050 Ti에서 수행하였다. 이 결과를 바탕으로, 입력 그래프의 차수 등을 토대로 적합한 그래프 표현 방식을 자동으로 선택해주는 휴리스틱을 개발하였고, 이는 RTX 3090, RTX 2060 및 GTX 1050 Ti에서 각각 기존 알고리즘의 수행 시간 대비 평균 7.85%, 8.01%, 10.43%의 수행 속도 개선 효과를 나타내었다. 또, 휴리스틱을 적용했음에도 수행 속도 개선 효과가 저조한 인스턴스들에 대한 개별 분석을 시행하였다.
둘째, 입력에 따라 수행할 알고리즘의 종류를 선택할 수 있도록 휴리스틱을 개선하는 방법을 검토한다. 휴리스틱이 선택할 수 있는 대체 알고리즘으로는 극대 독립 집합을 반복적으로 찾아 색을 칠하는 Luby의 병렬 알고리즘을 고려하였다. 위에서와 마찬가지로 같은 벤치마크를 사용하여 RTX 3090과 RTX 2060 및 GTX 1050 Ti에서 수행 속도가 얼마나 개선되는지를 실험적으로 확인하였으나, 실험 결과 이 알고리즘은 수행 속도 개선 효과를 얻기 어려운 것으로 나타나, Luby의 알고리즘 외의 새로운 알고리즘을 적용해야 함을 시사하였다.
마지막으로, 본 논문 이후의 향후 연구 방향에 대해 간략히 논의할 것이다.
목차
그림 차례 ⅲ표 차례 ⅴ국문 요약 ⅶ1. 서론 11.1. 기존 관련 연구 32. 각종 정의 및 기존 알고리즘 62.1. 문제 및 용어의 정의 62.2. 기존의 알고리즘 72.2.1. 탐욕 알고리즘의 얼개 82.2.2. Jones and Plassmann의 알고리즘 92.2.3. Alabandi et al.의 알고리즘 122.2.4. 극대 독립 집합을 이용하는 알고리즘 153. 자료 구조를 선택하는 휴리스틱 183.1. 휴리스틱 설계 193.1.1. 휴리스틱 설계에 고려될 GPGPU 플랫폼의 특성 193.1.2. 희소 행렬 표현 방식 203.1.3. 구현 최적화 및 실험 설계 253.2. 실험 결과 및 분석 293.2.1. 실험 환경 및 데이터 세트 293.2.2. 수행 시간 측정 및 결과 분석 323.2.2.1. 수행 시간 측정 결과 323.2.2.2. 최대 차수에 따른 수행 시간 개선 413.2.2.3. 평균 차수에 따른 수행 시간 개선 433.2.2.4. ELL 방식과 하이브리드 방식의 비교 453.2.2.5. 하이브리드 방식 파라미터 결정 463.2.3. 희소 행렬 표현 방법 결정 휴리스틱 533.2.4. 휴리스틱의 인스턴스별 성능 개선 효과 583.2.5. 밀집 그래프에서의 실험 결과 624. 알고리즘을 선택하는 휴리스틱 714.1. 알고리즘 구현 및 실험 설계 714.2. 실험 결과 및 분석 724.2.1. 수행 시간 측정 결과 734.2.2. 최선의 결과와 3장의 휴리스틱 비교 774.2.3. 결과 분석 795. 향후 연구 805.1. 휴리스틱의 성능 향상 805.2. 휴리스틱의 응용 806. 결론 827. 참고문헌 83영문 초록 89
최근 본 자료
댓글(0)
0