Partitioning

3.4 Partitioning

When running a model across multiple processes or machines (via MCPBackend or DaskBackend), agents must be assigned to partitions. The partitioning strategy determines which agents share a process. A good partition minimises cross-partition message traffic (which requires network communication) while maintaining balanced load (so no single partition becomes a bottleneck).

Three Strategies

All strategies implement the PartitionStrategy abstract base class:

class PartitionStrategy(ABC):
    @abstractmethod
    def partition(self, model: ABMModel, num_partitions: int) -> Dict[str, int]
    def get_partition(self, agent_id: str) -> int

TypeBasedPartition assigns all agents of the same type to the same partition. This is the simplest strategy and is effective when messaging is predominantly between types (e.g., all Banks send to all Traders, so having all Banks on one partition means Bank-to-Bank messages are local). However, it can produce severely unbalanced partitions if agent types have very different population sizes.

TopologyAwarePartition uses a greedy BFS algorithm that traverses the link graph and assigns connected clusters to the same partition. Starting from distant seed nodes (selected by BFS-based diameter approximation), it grows partitions by absorbing adjacent agents, balancing partition sizes as it goes. This minimises the cut ratio (fraction of cross-partition edges) which directly determines the volume of inter-partition message traffic. Time complexity is O(N + E) where N is agents and E is links.

ManualPartition takes a user-provided dictionary mapping agent IDs to partition indices. This is the most flexible strategy and is appropriate when domain knowledge dictates the partitioning (e.g., geographic regions for a spatial model, or regulatory jurisdictions for a compliance model).

class ManualPartition(PartitionStrategy):
    def __init__(self, mapping: Dict[str, int]) -> None

Partition Metrics

The PartitionMetrics class provides static methods to evaluate partition quality:

class PartitionMetrics:
    @staticmethod
    def compute_cut_ratio(model: ABMModel, partition_map: Dict[str, int]) -> float
    @staticmethod
    def compute_balance(partition_map: Dict[str, int], num_partitions: int) -> float
    @staticmethod
    def report(model: ABMModel, partition_map: Dict[str, int]) -> Dict[str, Any]

The report() method returns a dictionary with:

Key	Type	Description
cut_ratio	float	Fraction of total edges that cross partition boundaries (0.0 = perfect, 1.0 = worst)
balance	float	Ratio of smallest to largest partition size (1.0 = perfectly balanced)
num_partitions	int	Number of partitions
per_partition_counts	Dict[int, int]	Agent count per partition
total_agents	int	Total agent count
total_links	int	Total link count
cross_partition_links	int	Number of links crossing partition boundaries

Example usage:

from simudyne.engine.partition import TopologyAwarePartition, PartitionMetrics

strategy = TopologyAwarePartition()
partition_map = strategy.partition(model, num_partitions=4)
report = PartitionMetrics.report(model, partition_map)
print(f"Cut ratio: {report['cut_ratio']:.3f}")
print(f"Balance:   {report['balance']:.3f}")
print(f"Cross-partition links: {report['cross_partition_links']} / {report['total_links']}")

---