Green-Marl : a domain specific language for graph analysis
Abstract/Contents
- Abstract
- Graph is a fundamental data structure that captures arbitrary relationship between data entities. In recent years, the importance of efficient and scalable processing of large graph instances has been growing due to emerging applications such as social network services and computational biology, where large graph data-sets are heavily used. Fortunately, recent proliferation of parallel (e.g. multi-core CPUs and GPUs) and distributed (e.g. Amazon's EC2) computing environment has provided ways to exploit inherent parallelism in large graph data processing. However, it is still burdensome for a single programmer to implement graph algorithms correctly and efficiently while exploiting parallelism in a different way for each parallel or distributed environment. In this thesis, we present how this burden can be lightened up by the means of a Domain-Specific Language (DSL). First, we introduce Green-Marl, a domain specific language which allows the users to program their graph algorithms in an intuitive manner. However, the language is also designed in such a way that the underlying data-parallelism in the given graph analysis program is easily exposed to the Green-Marl compiler. Then, I will explain how the compiler can exploit such high-level semantic information to optimize the given user algorithm and to produce an efficient parallel implementation out of it. Experimental results show that the compiler-generated codes are as efficient as hand-coded versions in parallel graph libraries. Next, we explain how the Green-Marl compiler can produce an implementation for a distributed environment from the same Green-Marl program. Again the Green-Marl compiler uses high-level semantic knowledge to transform the given Green-Marl program into another one which is based on completely different programming model. Again the performance of compiler-generated code closely matches with hand-coded version. In summary, I show that the Green-Marl DSL can provide benefits of productivity, performance and portability to the users in the domain of large graph analysis.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2013 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Hong, Sungpack |
|---|---|
| Associated with | Stanford University, Department of Electrical Engineering. |
| Primary advisor | Olukotun, Oyekunle Ayinde |
| Thesis advisor | Olukotun, Oyekunle Ayinde |
| Thesis advisor | Kozyrakis, Christoforos, 1974- |
| Thesis advisor | Leskovec, Jurij |
| Advisor | Kozyrakis, Christoforos, 1974- |
| Advisor | Leskovec, Jurij |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Sungpack Hong. |
|---|---|
| Note | Submitted to the Department of Electrical Engineering. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2013. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2013 by Sungpack Hong
- License
- This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC BY).
Also listed in
Loading usage metrics...