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

https://dl.acm.org/doi/pdf/10.1145/3064176.3064191

  • 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

  • Xeon: host CPU

    • 8 GB of high bandwidth memory

  • Access pattern

  • 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

  • Re-run the preprocessing step

  • Generate incrementally?

    • No

  • Not supported multiple combines

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

Conclusion

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

PreviousGaraph: Efficient GPU-accelerated GraphProcessing on a Single Machine with Balanced ReplicationNextFluid: Resource-aware Hyperparameter Tuning Engine

Last updated

Was this helpful?