상세정보
Export to Refworks부가기능
High-Performance Linear Algebra-based Graph Framework on the GPU
상세 프로파일
| 자료유형 | 학위논문 |
|---|---|
| 서명/저자사항 | High-Performance Linear Algebra-based Graph Framework on the GPU. |
| 개인저자 | Yang, Carl Yue. |
| 단체저자명 | University of California, Davis. Electrical and Computer Engineering. |
| 발행사항 | [S.l.]: University of California, Davis., 2019. |
| 발행사항 | Ann Arbor: ProQuest Dissertations & Theses, 2019. |
| 형태사항 | 96 p. |
| 기본자료 저록 | Dissertations Abstracts International 81-04B. Dissertation Abstract International |
| ISBN | 9781085797658 |
| 학위논문주기 | Thesis (Ph.D.)--University of California, Davis, 2019. |
| 일반주기 |
Source: Dissertations Abstracts International, Volume: 81-04, Section: B.
Advisor: Owens, John D. |
| 이용제한사항 | This item must not be sold to any third party vendors. |
| 요약 | High-performance implementations of graph algorithms are challenging to implement on new parallel hardware such as GPUs, because of three challenges: (1) difficulty of coming up with graph building blocks, (2) load imbalance on parallel hardware, and (3) graph problems having low arithmetic ratio. To address these challenges, GraphBLAS is an innovative, on-going effort by the graph analytics community to propose building blocks based in sparse linear algebra, which will allow graph algorithms to be expressed in a performant, succinct, composable and portable manner. Initial research efforts in implementing GraphBLAS on GPUs has been promising, but performance still trails by an order of magnitude compared to state-of-the-art graph frameworks using the traditional graph-centric approach of describing operations on vertices or edges.This dissertation examines the performance challenges of a linear algebra-based approach to building graph frameworks and describes new design principles for overcoming these bottlenecks. Among the new design principles is making exploiting input sparsity a first-class citizen in the framework. This is an especially important optimization, because it allows users to write graph algorithms without specifying certain implementation details thus permitting the software backend to choose the optimal implementation based on the input sparsity. Exploiting output sparsity allows users to tell the backend which values of the output in a single vectorized coputation they do not want computed. We examine when it is profitable to exploit this output sparsity to reduce computational complexity. Load-balancing is an important feature for balancing work amongst parallel workers. We describe the important load-balancing features for handling graphs with different characteristics.The design principles described in the thesis have been implemented in GraphBLAST, an open-source high-performance graph framework on GPU developed as part of this dissertation. It is notable for being the first graph framework based in linear algebra to get comparable or faster performance compared to the traditional, vertex-centric backends. The benefits of design principles described in this thesis have been shown to be important for single GPU, and it will grow in importance when it serves as a building block for distributed implementation in the future and as a single GPU backend for higher-level languages such as Python. A graph framework based in linear algebra not only improves performance of existing graph algorithms, but in quickly prototyping new algorithms as well. |
| 일반주제명 | Computer science. Computer engineering. Electrical engineering. Applied mathematics. |
| 언어 | 영어 |
| 바로가기 | 
: 이 자료의 원문은 한국교육학술정보원에서 제공합니다. |
