Reading Notes for Green Marl: A DSL for easy and efficient graph analysis

Green Marl: A DSL for easy and efficient graph analysis

  1. Motivation
    1. graph applications
  2. Problem Statement
    1. Capacity (graph does not fit into a single physical memory address space)
      1. not really true now
    2. Performance (poor performance)
      1. still true
      2. random access behavior of most graph analytics
      3. use parallelism to hide latency, (limited y the available memory bandwidth — NOT TRUE)
    3. Implementation
      1. Not easy to develop a correct and efficient implementation
        1. correctness part is hard to argue
  3. Contributions
    1. user can describe graph analysis algorithm in a very intuitive way (can’t agree, still working with foreach, no one use BFS as a basic operator)
    2. optimizations and parallelizations enabled by the high-level semantic information of the DSL and produces an optimized parallel implementation
    3. interdisciplinary DSL approach to solving computational problems [no idea where this claim comes from, any parallel graph framework can claim at least three of these]
      1. graph theory
      2. compilers
      3. parallel programming
      4. computer architecture
  4. Approach
    1. Assumptions
      1. graph is immutable
      2. no aliases between graph instances or properties
    2. Parallelism
      1. foreach
    3. Travesrsal
      1. BFS
      2. DFS
    4. Compiler
      1. Type checking
      2. Parsing and Checking
    5. Optimizations
      1. deferred assignment
      2. fusion
    6. Code Generation
    7. Discussions
      1. Why compiler?
        1. “discuss the benefit of using a compiler to apply the optimizations that have been previously presented in the previous sections. Each of the optimization techniques is not completely novel in itself. It is either an application of a classic compiler optimization or a technique has been discussed in previous work. However, using a compiler allows optimization without requiring significant effort from a graph algorithms experts, and allow optimizations that are difficult with fixed function libraries —> BFS + RBFS. “
  5. Applications
    1. Computing scalar value from (G,) (conductance)
    2. Computing a new property from Graph (PageRank)
    3. Selecting a subgraph of interest (strongly connected components)
  6. Evaluation
  7. RelatedWorks
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s