Withdraw
Loading…
Breadth-first search for social network graphs on heterogenous platforms
Remis, Luis Carlos Maria
Loading…
Permalink
https://hdl.handle.net/2142/90537
Description
- Title
- Breadth-first search for social network graphs on heterogenous platforms
- Author(s)
- Remis, Luis Carlos Maria
- Issue Date
- 2016-04-21
- Director of Research (if dissertation) or Advisor (if thesis)
- Garzaran, Maria Jesus
- Department of Study
- Computer Science
- Discipline
- Computer Science
- Degree Granting Institution
- University of Illinois at Urbana-Champaign
- Degree Name
- M.S.
- Degree Level
- Thesis
- Keyword(s)
- Breadth-first search (BFS)
- Graphs
- Social networks
- Heterogenous
- Graphics processing unit (GPU)
- Abstract
- Breadth-First Search (BFS) is the core of many graph analysis algorithms, and it is useful in many problems including social network, computer network analysis, and data organization, but, due to its irregular behav- ior, its parallel implementation is very challenging. There are several approaches that implement efficient algorithms for BFS in multicore architectures and in Graphics Processors, but an efficient implementation of BFS for heterogeneous systems is even more complicated, as the task of distributing the work among the main cores and the accelerators becomes a big challenge. As part of this work, we have assessed different heterogenous shared-memory architectures (from high- end processors to embedded mobile processors, both composed by a multi-core CPU and an integrated GPU) and implemented different approaches to perform BFS. This work introduces three heterogeneous approaches for BFS: Selective, Concurrent, and Async. Contributions of this work includes both the analysis of BFS performance on Heterogenous platforms, as well as in depth analysis of social network graphs and its implications on the BFS algorithm. The results show that BFS is very input dependent, and that the structure of the graph is one of the prime factors to analyze in order to develop good and scalable algorithms. The results also show that heterogenous platforms can provide acceleration to even irregular algorithms, reaching speed-ups of 2.2x in the best case. It is also shown how the different system configurations and capabilities impact the performance and how the shared-memory system can reach bandwidth limitations that prevent performance improvements despite having higher utilization of the resources.
- Graduation Semester
- 2016-05
- Type of Resource
- text
- Permalink
- http://hdl.handle.net/2142/90537
- Copyright and License Information
- Copyright 2016 Luis Carlos Maria Remis
Owning Collections
Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at IllinoisManage Files
Loading…
Edit Collection Membership
Loading…
Edit Metadata
Loading…
Edit Properties
Loading…
Embargoes
Loading…