Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Kim, Min Soo | - |
dc.contributor.author | Yuk, Ji Hwan | - |
dc.date.accessioned | 2017-05-10T08:53:45Z | - |
dc.date.available | 2017-01-18T00:00:00Z | - |
dc.date.issued | 2017 | - |
dc.identifier.uri | http://dgist.dcollection.net/jsp/common/DcLoOrgPer.jsp?sItemId=000002326441 | en_US |
dc.identifier.uri | http://hdl.handle.net/20.500.11750/1506 | - |
dc.description.abstract | Sparse matrices are widely used to analyze a complex system which requires lots of linear algebraic operations such as computer graphics, recommender systems, machine learning, and information retrieval. As the size of real graphs are increasing rapidly, fast and scalable methods for handling such large-scale sparse matrices have become harder than before since the size of matrices increases as well. There have been various studies on implementing GPU-based methods for SpGEMM. However, most of those methods have faced two major challenges. First, the irregularity of matrices causes poor load balancing among threads. Second, many matrices do not fit in the GPU device memory.We propose a scalable and efficient GPU-based sparse-sparse matrices multiplication method called MStream which exploits streaming technology, which could hide memory latency of copy between main memory and device memory. To fully exploit GPU streams technology, we explore the design choice of an efficient data structure called slotted page format which divides a matrix into small fixed-size units instead of performing on Compressed Sparse Row (CSR) or Compressed Sparse Column (CSC) formats which are widely used to represent graphs with a sparse matrix in memory. ⓒ 2017 DGIST | - |
dc.description.tableofcontents | Ⅰ. INTRODUCTION 1 -- II. PRELIMINARIES . 5 -- 2.1 Many-core GPU 5 -- 2.2 Sparse Format for Matrix 6 -- 2.3 Slotted Page for Representing Sparse Matrix 6 -- 2.4 Two general schemes for matrix multiplication 8 -- 2.5 Observations 10 -- III. MSTREAM METHOD . 14 -- 3.1 Analysis of Algorithms for MStream 14 -- 3.2 Streaming Technique using GPU streams 20 -- 3.3 Overall Framework of MStream 22 -- IV. EXPERIMENTS . 25 -- 4.1 Experimental setup 25 -- 4.2 Comparison with cuSparse 26 -- 4.3 Characteristic of MStream . 27 -- V. CONCLUSIONS 29 |
- |
dc.format.extent | 32 | - |
dc.language | eng | - |
dc.publisher | DGIST | - |
dc.subject | Matrix multiplication | - |
dc.subject | Large-scale sparse matrix | - |
dc.subject | GPGPU | - |
dc.subject | Stream | - |
dc.subject | 행렬 곱셈 | - |
dc.subject | 대규모 희소 행렬 | - |
dc.subject | 스트림 | - |
dc.title | A large-scale sparse matrix multiplication method based on streaming matrix to GPUs | - |
dc.title.alternative | GPU 에서 대규모 희소 행렬 곱셈을 처리하기 위한 스트리밍 방법 | - |
dc.type | Thesis | - |
dc.identifier.doi | 10.22677/thesis.2326441 | - |
dc.description.alternativeAbstract | 희소행렬은 다양한 선형대수 연산이 필요한 컴퓨터 그래픽스 분야, 추천 시스템, 최근 화두가 되는 기계학습, 및 정보 검색에 이르기까지 다양하게 활용되고 있다. 또한, 사회연결망과 같은 실제 그래프 데이터를 압축된 형태로 표현되므로, 그래프의 규모가 증가함에 따라 대규모 희소행렬을 빠르게 처리하는 방법이 중요해고 있다. 이와 같은 복잡한 시스템을 분석하기 위한 기본적이며 핵심 연산인 희소 행렬간 곱셈을 GPU로 빠르게 처리하는 방법에 대한 많은 연구가 이루어졌다. 하지만, GPU의 제한된 장치메모리와 불규칙한 그래프 구조로 인해 GPU의 성능을 활용하지 못했다. 우리는 대규모 희소행렬 효율적이고 빠르게 처리 할 수 있는 GPU 기반의 희소 행렬 곱셈 방식을 제안하며 뿐만 아니라, 디바이스 메모리와 메인 메모리간의 잦은 전송 오버헤드를 비동기적인 GPU 스트림을 이용함으로 매우 효율적으로 처리함을 보인다. 또한 기존의 희소행렬을 나타내는 CSR과 CSC를 대체하는GPU에 적합한 데이터 포맷을 제안한다. 실험 결과, 제안하는 방식은 NVIDIA에서 제공하는 cuSparse에 비해 240배 가량 성능 향상을 보여준다. ⓒ 2017 DGIST | - |
dc.description.degree | Master | - |
dc.contributor.department | Information and Communication Engineering | - |
dc.contributor.coadvisor | Hwang, Dae Hee | - |
dc.date.awarded | 2017. 2 | - |
dc.publisher.location | Daegu | - |
dc.description.database | dCollection | - |
dc.date.accepted | 2017-01-18 | - |
dc.contributor.alternativeDepartment | 대학원 정보통신융합공학전공 | - |
dc.contributor.affiliatedAuthor | Yuk, Ji Hwan | - |
dc.contributor.affiliatedAuthor | Kim, Min Soo | - |
dc.contributor.affiliatedAuthor | Daehee Hwang | - |
dc.contributor.alternativeName | 육지환 | - |
dc.contributor.alternativeName | 김민수 | - |
dc.contributor.alternativeName | 황대희 | - |