Runtime Model

Dynamic Repartitioning/Balancing

Mizan (Ravi)

• 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.
• TODO: Read PAGE on how giraph has poorer performance for metis. (Ravi)