# MOSAIC: Processing a Trillion-Edge Graph on a Single Machine

* Limit by disk size not memory 

* Out-of-core 

* Trillion-edge graph (8TB overall) 

* Large-scale graph processing is ubiquitous 
  * Social network, genome analysis, graphs enable machine learning 

* Powerful, heterogeneous machines 
  * Terabytes of RAM on multiple sockets 
  * Powerful many-core coprocessors (Xeon Phi processor) 
    * Specific? Or applicable to GPU as well? 
  * Fast, large-capacity non-volatile memory 
  * Goal: take advantages of heterogeneous machine to process tera-scale graphs 

### Graph Processing: Sample Application 

* Community Detection
* Find Common Friends
* Find Shortest Paths
* Estimate Impact of Vertices (webpages, users, ...) 
* ...

### Design 

* Design space 
  * Single Machine 
    * Out-of-core: cheap, but potentially slow 
    * In memory: fast, but limited graph size 
  * Cluster 
    * Out-of-core: large graphs, but expensive & slow  
    * In memory: large graphs, fast, but expensive 
* Single machine, out-of-core: cost-effective
  * 10? higher memory more expensive? What is the ratio? Any evaluation? 
  * Validate this 
* Goal: good performance and large graphs 
* Goal: Run algorithms on large graphs on a single machine using coprocessors 
  * Enabled by 
    * Common, familiar API (vertex / edge-centric)
    * Encoding: Lossless compression 
    * Cache locality 
    * Processing on isolated subgraphs 
      * Divided into small subgraphs 
      * Do a massively parallel using cores and hyper-threads 

![](/files/-MbqyuHmMrVWhtIP6ehU)

* Xeon: host CPU 
  * 8 GB of high bandwidth memory 
* Access pattern 

![](/files/-Mbr-9DjG4CRZXdvMzxz)

* Subgraphs: tiles 
  * At most 2^16 vertices 
  * Local identifier: 2 bytes + level of indirection 
* Cache locality 
  * Inside subgraphs: sort by access order 
  * Between subgraphs: overlap vertex sets 
* Produce the tiles 

### Evaluation 

![](/files/-Mbr2GhBNsEragBDKw4I)

* Re-run the preprocessing step 
* Generate incrementally? 
  * No

![](/files/-Mbr3174Riup_Ew-CAzg)

* Not supported multiple combines 

![](/files/-Mbr3l1TFKg-1aChlhcT)

![](/files/-Mbr4mAMHsY4MB1n7ivD)

![](/files/-Mbr4xRGxGUncJZSOjKW)

* Execution model (when they place the tiles, inter-core communication? Or independent?) 

### Conclusion 

![](/files/-Mbr5jkhx97XmGOha3yF)

* Same gain to put in the multi-core CPUs? 
  * Use the principle 
  * Spread computation 
  * Hybrid systems? 
    * Taking benefits on tiling 
    * Along with offloading to GPUs 

Think about:

* Workloads, technologies, trends. Design something that benefits the problem they have. 


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://sliu583.gitbook.io/blog/specific-work/shivarams-group/group-papers/mosaic-processing-a-trillion-edge-graph-on-a-single-machine.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.