# 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 

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-Mbqrh1miNj-DsddWzCi%2F-MbqyuHmMrVWhtIP6ehU%2Fimage.png?alt=media\&token=3407d7f9-7f8a-421d-bc26-ff4dd0e7fe8f)

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

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-Mbqrh1miNj-DsddWzCi%2F-Mbr-9DjG4CRZXdvMzxz%2Fimage.png?alt=media\&token=714979c8-8acf-4da0-828d-cc274b43953d)

* 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 

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-Mbqrh1miNj-DsddWzCi%2F-Mbr2GhBNsEragBDKw4I%2Fimage.png?alt=media\&token=289c8561-6595-4cbf-a9f1-3787e51c79de)

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

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-Mbqrh1miNj-DsddWzCi%2F-Mbr3174Riup_Ew-CAzg%2Fimage.png?alt=media\&token=c61ccaac-8e69-411a-81f3-93c550ec918f)

* Not supported multiple combines 

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-Mbqrh1miNj-DsddWzCi%2F-Mbr3l1TFKg-1aChlhcT%2Fimage.png?alt=media\&token=3f90a57e-b228-47f9-81b0-f5613e5d3557)

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-Mbqrh1miNj-DsddWzCi%2F-Mbr4mAMHsY4MB1n7ivD%2Fimage.png?alt=media\&token=f0a946f3-bf84-4c2c-bac5-9783fd57a571)

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-Mbqrh1miNj-DsddWzCi%2F-Mbr4xRGxGUncJZSOjKW%2Fimage.png?alt=media\&token=43252a97-e663-49c0-945a-79d97ca7d7bf)

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

### Conclusion 

![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVORxAomcgtzVVUqmws%2F-Mbqrh1miNj-DsddWzCi%2F-Mbr5jkhx97XmGOha3yF%2Fimage.png?alt=media\&token=c0b47712-84fc-4ad6-a870-af85878a65a5)

* 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.