지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers 정보과학회 컴퓨팅의 실제 논문지 정보과학회 컴퓨팅의 실제 논문지 제28권 제12호
- 발행연도
- 2022.12
- 수록면
- 594 - 614 (21page)
- DOI
- 10.5626/KTCP.2022.28.12.594
이용수
이 논문의 연구 히스토리 (2)
- 이 논문의 후속연구가 궁금하신가요?
- 연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
- 이 논문의 연구 히스토리 확인하기
초록· 키워드
오류제보하기
본 논문에서는 그래프 채색 알고리즘의 GPGPU상 구현을 최적화하는 새로운 기법으로서, 입력에 따라 최적의 그래프 표현방식을 선택하는 휴리스틱을 제시한다. 기존에 Alabandi et al.이 GPGPU에 적합한 그래프 채색 알고리즘을 제시한 바 있으나, 단일한 자료 구조만을 사용한다는 제한으로 인해 GPGPU의 최대 성능을 이끌어 내는 것에는 한계가 있었다. 본 논문에서는 GPGPU에 알맞은 복수의 자료구조를 채택하고, 이로써 개선된 성능을 실험적으로 측정하였다. 실험은 공개 리파지터리들의 그래프를 벤치마크로 사용해 RTX 2060과 GTX 1050Ti에서 수행하였다. 이 결과를 바탕으로, 입력 그래프의 차수 등을 토대로 적합한 그래프 표현방식을 자동으로 선택해주는 휴리스틱을 개발하였고, 이는 기존 대비 평균 8.01%(RTX 2060)～10.43%(GTX 1050Ti)의 수행 속도 개선 효과를 나타내었다. 끝으로, 휴리스틱의 효과가 저조한 경우에 대한 개별 분석을 수행하였다.
목차
요약
Abstract
1. 서론
2. 각종 정의 및 기존 알고리즘
3. 제안하는 휴리스틱
4. 실험 결과 및 분석
5. 결론 및 향후 연구
References
참고문헌 (30)
참고문헌 신청
M. Javedankherad, Z. Zeinalpour-Yazdi, and F. Ashtiani, "Content Placement in Cache Networks Using graph coloring," IEEE Systems Journal, Vol. 14, pp. 3129-3138, 2020.
G. J. Chaitin, "Register allocation & spilling via graph colouring," Proc. 1982 SIGPLAN Symposium on Compiler Construction, pp. 98-105, 1982.
K. Chon, K. Chong, and Y. Won, "Implementation of Register Allocator Using Priority - Based Graph Coloring," Proc. of the KIISE, Vol. 19, No. 2, pp. 321-324, 1992. (in Korean)
D. Gómez, J. Montero, J. Yáñez, and C. Poidomani, "A graph coloring approach for image segmentation," Omega, Vol. 35, No. 2, pp. 173-183, 2007.
J. H. Kim and H. S. Chang, "Graph Coloring based Clustering Algorithm for Wireless Sensor Network," Proc. of the KIISE, Vol. 34, No. 2(D), pp. 306-311, 2007. (in Korean)
G. J. Chaitin, "Register allocation & spilling via graph colouring," Proc. 1982 SIGPLAN Symposium on Compiler Construction, pp. 98-105, 1982.
K. Chon, K. Chong, and Y. Won, "Implementation of Register Allocator Using Priority - Based Graph Coloring," Proc. of the KIISE, Vol. 19, No. 2, pp. 321-324, 1992. (in Korean)
D. Gómez, J. Montero, J. Yáñez, and C. Poidomani, "A graph coloring approach for image segmentation," Omega, Vol. 35, No. 2, pp. 173-183, 2007.
J. H. Kim and H. S. Chang, "Graph Coloring based Clustering Algorithm for Wireless Sensor Network," Proc. of the KIISE, Vol. 34, No. 2(D), pp. 306-311, 2007. (in Korean)
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
그래프 중심성들을 이용한 그래프 유사도 측정
한국컴퓨터정보학회논문지
2018 .12
-
그래프의 정점 연결성에 대한 최소 범위 할당
한국정보통신학회논문지
2017 .11
-
A Graph Embedding Technique for Weighted Graphs Based on LSTM Autoencoders
JIPS(Journal of Information Processing Systems)
2020 .01
-
The Classification of random graph models using graph centralities
한국컴퓨터정보학회논문지
2019 .07
-
그래프 정보를 이용한 그래프 구조 간략화 알고리즘
제어로봇시스템학회 국내학술대회 논문집
2016 .03
-
그래프데이터베이스 기반 통신망 운영관리 방안
한국정보통신학회 종합학술대회 논문집
2022 .05
-
중심성이 높은 정점의 변화에 따른 네트워크 특성 분석
한국컴퓨터정보학회논문지
2017 .03
-
A new meta-heuristic optimization algorithm using star graph
Smart structures and systems
2017 .01
-
Unified Graph Clustering via Learning Robust and Structured Graph
대한전자공학회 학술대회
2019 .06
-
Graph Structure Analysis and Classification Framework using Graph Convolutional Network
대한산업공학회 춘계공동학술대회 논문집
2023 .05
-
Graph R-CNN을 이용한 Auto-Encoding Scene Graphs
한국정보과학회 학술발표논문집
2020 .12
-
특허 지식그래프를 위한 지식 그래프 임베딩 모델 분석 연구
Proceedings of KIIT Conference
2020 .10
-
관계형데이터를 이용한 그래프 데이터베이스의 모델별 구조 분석과 쿼리 성능 비교 연구
멀티미디어학회논문지
2019 .09
-
On the Unfriendliness of Symmetric Graphs
제어로봇시스템학회 국내학술대회 논문집
2021 .06
-
요약 그래프 상에서 효과적인 그래프 압축 기법
한국정보과학회 학술발표논문집
2016 .06
-
An Embedding Technique for Weighted Graphs using LSTM Autoencoders
Journal of KIISE
2021 .01
-
동적 그래프에서 효율적인 그래프 요약 기법
한국정보과학회 학술발표논문집
2015 .12
-
외부 지식 그래프 결합을 위한 그래프 트랜스포머 알고리즘
한국정보과학회 학술발표논문집
2023 .06
-
서비스 로봇을 위한 그래프 구조 맵에서의 작업 계획
대한기계학회 춘추학술대회
2019 .11
-
그래프 오더링을 활용한 그래프 병렬 처리의 성능 향상
한국정보과학회 학술발표논문집
2017 .12
이 논문의 저자 정보
최근 본 자료
댓글(0)
0