high performance computing on graphics processing units: hgpu.org

Graph mining and data management has become a significant area because more and more new applications to various data mining problems in social networking, computational biology, chemical data analysis and drug discovery are emerging recently. Although traditional mining methods have been extended to process graphs, many graph applications still confront huge challenges due to continuous and overwhelming edges to be processed with limited resources. Social networks, web graphs and protein interaction graphs are difficult to handle because they cannot be easily decomposed into small parts that could be further processed in parallel. As graphs grow larger and larger, new processing techniques with higher computing power are demanded for mining massive graphs. Designing scalable systems for analyzing, processing and mining huge real-world graphs has also become one of the most emerging problems. The research in this thesis has explored and utilized the state-of-the-art GPGPU techniques over large graph mining. By understanding the limitations of heterogeneous hardware, triangulation, as a representative of graph mining algorithms, was implemented to be accelerated by many-core GPUs in Chapter 3. Associated graph data structures and blended algorithm structures were designed in this chapter as well. This is the first and successful attempt to accelerate graph triangulation using GPGPU techniques. Afterwards, a synchronous iterative GPU-accelerated graph processing model was abstracted and proposed in Chapter 4. A generic system (SIGPS) was then implemented based on this model. Specifically, a vertex API was provided for users who want to design their own algorithms with the assistance of a functional library of mining algorithms. Together with the vertex API and algorithm library, several system supporting modules marked off the system hierarchy. This system could bring an impressive impact over the graph mining community since it provided a systematic solution for implementing efficient graph mining algorithms on GPU-accelerated computing platforms. Moreover, in order to further enhance the system performance, an asynchronous disk-based model was then designed to support asynchronous computing over GPUs in Chapter 5. A novel parallel sliding windows method was employed on GPU memory. Two newer operational APIs named "sync" and "update" replaced the vertex API. Asynchronous-SIGPS (ASIGPS) could be used to execute several advanced data mining, graph mining, and machine learning algorithms on very large graphs. It is noted that there may be a few problematic issues involved in the system since designing effective and efficient systems across heterogeneous platform is complicated. As a potential solution for large scale domain applications on personal computers, more graph mining algorithms need to be implemented to constitute the library of the system and more efforts need to be paid to solve all the problems related to the implementation of the hybrid system.