Source-linked AI summary
Beyond Edge Cuts: Activity-Weighted Multicast Hypergraph Mapping for Spiking Neural Networks on Mesh NoCs
Amirreza Khorasanian
TL;DR
Conventional graph and pairwise placement objectives do not match one-to-many spike delivery and shared mesh routes. M-HySMap models source fanout as activity-weighted hyperedges, refines strong graph/QAP seeds with route-aware multicast search, and reduces routed multicast hops across its evidence suite. The paper also shows that local dependency enables exact incremental refinement, while the evidence remains bounded to scaled Potjans-inspired workloads and heuristic search.
Problem
Conventional graph partitioning and pairwise placement costs do not represent multicast fanout and shared mesh links in SNN communication.
Method
M-HySMap uses activity-weighted directed hyperedges, route-union objectives, strong graph/QAP seeds, local incremental updates, and portfolio neighborhoods.
Results
10.6–19.6% lower routed multicast hops than the strongest activity-aware graph/QAP baseline across the 115-job evidence suite.
Takeaways & Limitations
Matching the communication object to hardware multicast semantics can matter as much as improving the optimizer applied to the older graph abstraction.
Takeaways & Limitations
The evaluation uses scaled Potjans-inspired recurrent workloads, and the heuristic search does not guarantee global optimality.
Abstract
from arXiv · showhide
Mapping spiking neural networks (SNNs) onto neuromorphic many-core platforms is often formulated with graph partitioning and pairwise placement costs. That abstraction is convenient, but it does not match the physical communication event: one spike from a source neuron is delivered to a set of postsynaptic destinations, and routes to several destinations can share mesh links. We present M-HySMap, a route-aware, activity-weighted multicast hypergraph mapping framework. Each source neuron induces a directed hyperedge to its postsynaptic fanout, weighted by profiled activity. The mapper starts from strong activity-aware graph/QAP seeds and then optimizes distinct destination-core fanout, the union of deterministic mesh routes, and link congestion. The central algorithmic observation is locality: moving one neuron can change only its own source-rooted hyperedge and the hyperedges of its predecessors. This permits exact incremental gain evaluation while caching every unaffected route contribution. We expose this combinatorial structure in detail, derive a conservative placement lower bound, and describe a portfolio of partition and placement neighborhoods that preserves the best incumbent. Across a 115-job evidence suite on Potjans-inspired recurrent SNNs and mesh NoCs from 4 x 4 to 6 x 6, plus a 7 x 7 stress case, M-HySMap reduces routed multicast hops by 10.6-19.6% over Activity+QAP and 19.7-41.1% over Edge+QAP. Incremental updates accelerate refinement by 4.7-12.7x while matching full recomputation to numerical precision.
1 Introduction
SNN mapping must account for one-to-many spike delivery and shared mesh routes, not only pairwise graph edges. M-HySMap retains classical seeds while optimizing a route-aware multicast representation.
- Partitioning assigns neurons to cores, while placement assigns logical cores to physical mesh locations.
- Pairwise graph and QAP objectives are convenient, but graph edges do not represent the hardware communication event.
- Equal synaptic edge cuts can produce different destination-core fanout, routed-hop counts, and bottleneck loads because spikes are multicast and routes can share links.
- M-HySMap begins with activity-aware graph partitioning and QAP placement, then refines the mapping under a route-aware multicast objective.
- Its representation uses one directed, activity-weighted hyperedge per source and counts shared mesh links once per multicast event.
- The extended preprint adds combinatorial derivations, search neighborhoods, incremental-update invariants, and worked examples without adding unsupported hardware timing or energy claims.
2 The Combinatorial Anatomy of SNN Mapping
SNN mapping differs from ordinary graph partitioning because multicast traffic depends on destination-core fanout and shared routed links, not only remote synapse counts. M-HySMap models these events explicitly and uses conservative bounds to guide placement.
- Mapping space: The joint mapping space combines neuron-to-core assignments with core-to-mesh permutations, becoming prohibitive even for modest n and k.The raw space contains k^n assignments and k! placement permutations before balance and symmetry reductions.
- Communication abstraction: Edge-cut objectives count remote synapses independently, whereas multicast fanout counts distinct remote destination cores.Multiple targets on one remote core collapse to a single destination-core entry.
- Communication abstraction: Two mappings with identical edge cut can therefore produce different packet replication, routed-hop counts, and bottleneck loads.The mismatch arises because source spikes reach destination sets and routes can share links.
- Route-aware objective: M-HySMap represents each source and its postsynaptic targets as an activity-weighted directed hyperedge, then optimizes its routed mesh links and congestion.The objective uses deterministic XY route unions, with shared links counted once per source spike.
- Route-aware objective: A 2 × 2 example shows that colocating destination cores can halve a source's routed-hop contribution from 10 to 5 without changing the four remote synapses.The example uses source activity ru = 5 and route-union sizes of two versus one link.
- Placement bound: For fixed partitions, the placement lower bound is conservative: each connected route union needs at least one link per distinct destination, while maximum load is at least average load.It is intended as a sanity check and for tiny exact-placement experiments, not as a tight optimum bound.
4 Algorithms
M-HySMap builds a classical activity-aware partition and QAP placement seed, then refines it with boundary-focused, route-aware local search. Its algorithm combines constrained candidate moves with complementary neighborhoods while retaining the strong pairwise seed.
- Search architecture: The search treats a strong pairwise solution as a warm start and explores neighborhoods defined by the multicast objective.The architecture uses the pairwise solution as a valuable seed rather than a straw-man baseline.
- Profiling: The experiments use a 0.20 s profiling run, 6 Hz external input, and a 150k processed-event cap, with one shared activity vector across activity-aware methods.Using the same activity vector prevents improvements from being attributed to different profiling traces.
- Partition seed: The partition seed applies greedy boundary-node refinement first under edge cut and then under activity-weighted edge cut.Boundary nodes have at least one predecessor or successor on another core.
- Placement seed: The QAP seed uses pairwise flow times Manhattan distance, with source weights set to 1 for Edge+QAP or ru for Activity+QAP.For reported k ≥16 cases, an anytime multi-start greedy 2-swap search produces the Activity+QAP seed.
- Local refinement: Candidate moves for a boundary neuron prioritize cores occupied by incoming and outgoing neighbors while excluding its current core.Additional cores are sampled when the candidate set is very small, and moves must satisfy hard balance bounds.
- Local refinement: Within each pass, feasible candidate cores are scored and the best improving move is immediately applied until no improvement remains or the budget expires.This is FM-inspired boundary refinement, but it does not reproduce the classical bucket/locking algorithm exactly.
4.4 The affected-hyperedge locality theorem
The affected-hyperedge locality theorem shows that moving one neuron changes only its own source-rooted hyperedge and those rooted at its predecessors, enabling exact incremental evaluation while caching unrelated contributions.
- Affected-source locality: A move of neuron v affects only the hyperedge rooted at v and hyperedges rooted at its predecessors.All other source-rooted multicast objects retain their destination sets, route unions, and link-load contributions.
- Incremental evaluation: The incremental evaluator subtracts cached contributions, recomputes affected routes, evaluates the objective, and commits or restores the tentative move.The affected set is A(v) = {v} ∪ N−(v).
- Exactness: Exactness follows because replacing precisely the affected cached contributions reproduces complete recomputation up to floating-point arithmetic.Global maximum-load and variance terms are recomputed from the updated counters.
- Complexity reduction: A full candidate evaluation scans all fanouts and forms source route unions globally, whereas incremental evaluation scans only sources in A(v).Both approaches still perform mesh-link summarization work.
- Complexity reduction: 4.7–12.7× speedups align with only 2.32–2.71 affected sources on average in the reported configurations.The structural saving is avoiding re-routing unrelated source-rooted multicast objects, not making every implementation operation constant-time.
4.7 Multicast-aware placement neighborhood
The placement neighborhood searches multicast-aware core-location swaps, alternates placement and partition refinement, and preserves the best feasible incumbent across complementary schedules.
- Placement swaps: Fixed-partition placement uses strictly improving 2-swaps of logical core locations, seeded by strong pairwise-QAP placements and additional restarts.Row-major and randomized permutations are used if the search budget permits.
- Placement swaps: The anytime placement search always retains a feasible incumbent, while exhaustive permutation enumeration is available only for very small diagnostic cases.The main experiments use heuristic multi-start search rather than exhaustive enumeration.
- Alternating schedules: Joint cycles improve placement, refine the partition under the physical placement, and preserve the best mapping encountered.Heavy runs use two joint cycles followed by a final placement polish.
- Portfolio selection: The portfolio evaluates complementary partition, placement, and joint-search schedules and selects the minimum-objective candidate.This design addresses different local-search basins without claiming global optimality.
5 Experimental Methodology
The evaluation uses controlled Potjans-inspired recurrent SNN workloads on deterministic two-dimensional mesh NoCs, comparing activity-aware graph/QAP baselines with multicast-aware variants across 115 jobs.
- Workloads and hardware: The workloads are Potjans-inspired recurrent SNNs that preserve layered excitatory/inhibitory population structure.They are scaled to support many paired mapping runs under controlled conditions.
- Compared methods: The baselines and variants use the same generated SNN, profile, mesh, routing rule, and workload seed for each job.The progression isolates representation and search effects rather than changing the underlying workload.
- Metrics and protocol: The heavy configuration uses two edge-refinement passes, four hypergraph-refinement passes, five placement restarts, 0.50 s per placement call, and two joint cycles.These settings define the main experimental search budget.
- Metrics and protocol: 115 completed jobs are evaluated primarily by routed multicast hops, with maximum link load and the composite objective providing congestion context.Incremental speedup measures cached move evaluation rather than equal end-to-end runtime against simpler baselines.
6 Results
M-HySMap consistently reduces routed multicast hops and maximum link load relative to graph/QAP baselines, with most hop improvement appearing when multicast communication is first optimized and incremental evaluation providing substantial speedups.
- Routed multicast traffic: 19.7–41.1% fewer routed multicast hops than Edge+QAP and 10.6–19.6% fewer than Activity+QAP are reported across every configuration.The pattern includes the 7 × 7 stress case with fewer seeds.
- Routed multicast traffic: Activity+QAP already includes source activity and pairwise topology awareness, so the additional gain comes from optimizing distinct destination-core delivery and shared routed links.The controlled baseline isolates the communication-object change from simply adding activity weights or topology awareness.
- Ablation: 1.000, 0.857, and 0.848 are the averaged normalized hop costs for Activity+QAP, QAP-seeded multicast refinement, and the final portfolio, respectively.Most improvement appears at multicast refinement, while the portfolio adds a smaller robustness gain.
- Congestion: 20.5% lower averaged maximum-link load than Activity+QAP and 25.5% lower than Edge+QAP accompany the hop reductions.Worst-link and variance terms prevent interpreting the result as traffic concentration on one link.
- Incremental evaluation: 4.7–12.7× speedups are achieved by incremental affected-hyperedge evaluation while full-objective validation remains at floating-point scale.The average affected-source set is roughly 2.3–2.7 source hyperedges per evaluated boundary node.
7 Related Work and Positioning
M-HySMap builds on graph partitioning, QAP placement, and prior source-rooted hypergraph work while distinguishing itself through route-aware multicast optimization and exact local search updates.
- Existing SNN mapping flows commonly partition or cluster communication and then place logical cores using topology-aware or pairwise objectives.
- Prior work has already argued for source-rooted hypergraph abstractions in SNN mapping, so hypergraphs themselves are not presented as new here.
- M-HySMap instead translates destination-core sets into unions of deterministic mesh routes and explicitly models worst-link and load-variance terms.
- The method specializes local refinement to source-rooted spike delivery by exploiting the exact dependency structure of affected hyperedges.
- QAP remains useful as both a strong graph baseline and a seed generator, but pairwise flow costs are correlated with, rather than equivalent to, shared-link multicast costs.
8 Limitations and What the Results Do Not Claim
The evaluation supports mapping-level routed-hop comparisons in controlled, relatively small workloads, but does not establish broader system-level performance or global optimality.
- The evidence uses scaled Potjans-inspired recurrent networks with 79–163 neurons and approximately 238–1028 synapses rather than a broad standard neuromorphic benchmark suite.
- Larger full-system SNNs remain outside the reported scope and are identified as future work.
- Routed-hop reductions are mapping-level traffic proxies and are not converted into energy, latency, throughput, or cycle claims without a calibrated target architecture.
- The route-set operator assumes deterministic XY routing, so adaptive routing or different hardware multicast policies would change the modeled objective.
- Profiled activity comes from a finite interval and may vary across application phases, motivating scenario-aware or robust objectives as an extension.
- The heuristic search guarantees monotone improvement only for accepted moves, not global optimality, and time-budgeted placement can mildly affect exact incumbents.
9 Conclusion
The paper argues that SNN mapping should model each source spike as an activity-weighted multicast hyperedge and optimize its routed mesh footprint. Local dependency caching makes this objective tractable, while portfolio search yields lower routed-hop costs than graph/QAP mapping.
- SNN mapping is framed as a one-to-many communication problem whose cost depends on destination cores and the union of links used by each source spike.
- Exact incremental gains exploit the fact that one neuron move affects only its own and predecessor-rooted hyperedges, producing 4.7–12.7× faster refinement.
- The search combines Activity+QAP seeds, route-aware partition moves, placement swaps, and safe-best portfolio selection.
- Across 115 jobs, the resulting mappings reduce routed multicast hops by 10.6–19.6% relative to the strongest activity-aware graph/QAP baseline while also lowering average worst-link load.
Reproducibility Notes
The implementation emphasizes reproducible, isolated experiments with fixed configurations and per-run result logging.
- Experiments use fixed workload seeds, JSON configurations, subprocess-isolated jobs, and per-run CSV logging.
- The heavy evidence configuration records profiling time, partition passes, placement restarts and budgets, joint cycles, and balance slack.
- A public release should include source code and the exact evidence configuration and result files needed to reproduce the preprint.