Runtime Model

Dynamic Repartitioning/Balancing

Imbalance due to graph structure, algo behavior
Algo
Stationary
Predictable Messages in supersteps, vertex activation is known beforehand, e.g. PR,
Non-stationary
Messages not predictable, variable vertex activation, e.g. Spanning tree,
Partitioning impacts different graphs differently. Pick appropriate partitioning for different algos. e.g. hash better than metis for PR on kgraph. Edge balanced.
Decentralized (no master coordination), transparent, simple
Migration planning at end of sstep.
Use stats on out and in messages from partition, and response time. All workers b'cast stats to all others. They decide independently by pairing most loaded with least loaded worker for exchange.
Maintain DHT for location of workers for a vertex to give new location.
Delay migration of large vertices over multiple supersteps. (1) Messaging/migration, (2)compute on old/mesaging to new, (3) computing on new.
Features
Different partitioning for different graphs, algos.
Decentralized, no master.
Giraph does partition rebalance between ssteps using Master. Could master approach be better if migration is less freq, avoiding lot of stats exchange?
What stats are useful for migration? in/out msg, in msg for next sstep?
When do you migrate? Are stats temporally sensitive? Knowing activation schedule can help decide.
No analysis of migration overhead.
TODO Reading
Read PAGE on how giraph has poorer performance for metis. (Ravi)
IL paper on hashing and migration