PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimal Deadlock-Free Routing for Degree-Six Triangular-Lattice Meshes and Tori with Two Forbidden Turns

Zibo Diao, Rongxi Sun

arXiv:2609.09746v1cs.ARcs.NI

TL;DR

Wormhole routing on degree-six triangular lattices must preserve minimal paths while preventing cycles in channel dependencies. This paper constructs turn-restricted mesh and torus routes, using one VC for the mesh and two for the torus. It proves deadlock-free resource orders and extends them to a restricted single-link failure setting.

  • Problem

    Degree-six triangular lattices have shortest-path diversity and periodic channel cycles that require topology-specific deadlock-free routing under wormhole flow control.

    Source: §1 · p. 1

  • Method

    The paper combines two forbidden turns with one-VC mesh routing, and uses two VCs with Hamiltonian coordinates and datelines for torus routing.

    Source: §1 · pp. 1–2

  • Results

    For n ≥3, the torus two-turn relation is cyclic with one VC, while the proposed one-VC mesh and two-VC torus constructions have acyclic complete resource CDGs.

    Source: §4.1 · p. 6, §4.2 · p. 7, §8 · p. 14

  • Takeaways & Limitations

    Both physical routing relations preserve minimal all-pairs connectivity, and the torus construction addresses the periodic cycle with two VC phases and a global resource rank.

    Source: §8 · p. 14

    The fault extension covers one static, globally known bidirectional link failure and does not cover multiple failures, node failures, or dynamic reconfiguration with old and new configurations in flight.

    Source: §7 · p. 14

Abstract

from arXiv · show

Degree-six triangular-lattice interconnection networks offer substantial minimal-path diversity, but their additional directions complicate deadlock-free routing under wormhole flow control. We study a finite hexagon-shaped mesh and its periodic torus quotient in a common six-direction coordinate system. For the finite mesh, we construct a minimal partially adaptive routing relation that uses one virtual channel and forbids only two directed turns. For the torus, we prove that every source-destination pair has a unique closest lattice lift, but that the same two-turn physical routing relation still has a cyclic one-VC resource CDG for every n >= 3. We eliminate this residual periodic dependency by combining two virtual channels with Hamiltonian coordinates and group-specific datelines. Each same-group segment crosses its dateline at most once, which permits a global rank on VC-labelled channel resources. We prove minimal all-pairs connectivity for both physical routing relations and acyclicity of the complete resource CDG for the proposed one-VC mesh and two-VC torus constructions. For a single static bidirectional link failure known before a routing epoch, we further rotate the turn rule toward the failed orientation and replace a failed hop by a same-group two-hop triangle bypass. This restricted extension preserves all-pairs connectivity and the original VC counts, with at most one additional hop relative to the healthy shortest-path distance.

1 Introduction

Wormhole routing must provide paths while preventing cycles in the union of permitted channel dependencies. This paper develops topology-specific routing for a finite triangular-lattice mesh and its periodic torus.

1 Introduction

  • The paper unifies a finite degree-six mesh and its periodic torus in a six-direction coordinate system.It characterizes lattice geodesics and proves every torus source-destination pair has a unique closest lift.Source: §1 · p. 1
  • The mesh uses one virtual channel and two forbidden directed turns while preserving minimal all-pairs connectivity and partial adaptivity.The proposed mesh routing also has an acyclic complete resource CDG.Source: §1 · p. 1
  • On the torus, the same two-turn relation has a cyclic one-VC resource CDG for n ≥3; two VCs and Hamiltonian datelines yield an acyclic resource order.The paper also extends the constructions to one static, globally known bidirectional link failure, with at most one extra hop and the original VC counts.Source: §1 · p. 2
  • The authors implement the routing relations in gem5/Garnet and evaluate performance, restricted-sector pressure, dateline behavior, and scaling.The main text states formal results, with complete proofs deferred to the appendix.Source: §1 · p. 2

2 Related Work

Prior work establishes turn restrictions, virtual channels, and hexagonal-network routing, but the paper distinguishes its topology-specific constructions from those approaches. It also reports a permitted resource cycle in a reconstruction of a published three-VC torus scheme, while limiting what that cycle establishes.

2 Related Work

  • Prior deadlock-free routing work uses turn restrictions, virtual-channel classes, or escape subnetworks, whereas this paper certifies acyclicity of the complete resource CDG.The paper also situates its approach among fault-tolerant turn restrictions for orthogonal meshes.Source: §2 · p. 2
  • Earlier degree-six mesh work includes minimal partially adaptive turn models and shortest-path algorithms, but not this two-turn, one-VC relation with an analytic complete-CDG certificate.The paper distinguishes degree-six triangular lattices from other topologies also called hexagonal networks.Source: §2 · p. 2

2.1 Reassessing the prior three-VC scheme

  • The comparison is scoped to the published routing and VC-assignment rules; the paper contrasts that three-VC proposal with its own partially adaptive, two-VC construction.The paper does not infer packet-level deadlock reachability from the CDG cycle alone.Source: §2 · p. 2, §2.1 · p. 3
  • For the stated rules of Shamaei et al. (2013), the reconstructed H4 resource CDG contains a directed cycle induced by permitted minimal wraparound routes.The paper says this contradicts the claimed complete-CDG acyclicity, but does not establish reachable packet-level deadlock from the cycle alone.Source: §2.1 · p. 3

3 Network Model and Preliminaries

The paper models the finite mesh and periodic torus in integer coordinates, using lattice geodesics to define minimal paths. It then formalizes routing relations and resource dependencies for proving deadlock freedom.

3.1 Six-direction coordinates and the finite mesh

  • Every geodesic in the triangular lattice uses steps from at most two adjacent directions.The six-direction coordinate system represents the degree-six lattice, and the finite mesh restricts its nodes to a hexagonal region.Source: §3.1 · p. 3
  • The finite mesh contains multiple minimal paths; Figure 1 shows two distinct six-hop routes for n = 4 from s = (−3, 0) to t = (1, 2).The figure illustrates path diversity within the finite boundary.Source: Figure 1 · p. 4, §3.1 · p. 4

3.2 The periodic torus

  • The torus identifies nodes differing by period-lattice vectors, and every ordered node pair has a unique closest lattice lift.Thus minimal routes share the same destination lift and vary only in the ordering of minimal direction steps.Source: §3.2 · pp. 4–5

3.3 Routing relations and channel dependencies

  • Routing relations specify permitted paths, while the complete resource CDG records dependencies between consecutive channel-and-VC resources.An acyclic complete resource CDG is the paper's deadlock-freedom certificate under wormhole flow control.Source: §3.3 · pp. 5–6

4 Deadlock-Free Routing

The paper restricts minimal paths to avoid two directed turns, then uses one VC for the finite mesh and two VC phases for the torus. A restricted, globally known single-link failure is handled through rotated turn rules and controlled triangle bypasses.

4.1 Mesh routing with two forbidden turns and one VC

  • For every n ≥2, the mesh relation is minimal, all-pairs connected, partially adaptive, and deadlock-free with one VC.It retains direction interleavings within within-group sectors and the L-before-U order in cross-group sectors.Source: §4.1 · p. 6

4.2 Torus routing with two forbidden turns and two VCs

  • The torus VC rule fixes the unique closest lift at injection and selects only minimal directions whose prefixes remain extendible to permitted routes.The one-bit crossed flag is the only dynamic state used specifically by the VC phase rule.Source: §4.2 · pp. 6–8
  • Two VCs, Hamiltonian coordinates, and group-specific datelines give the torus relation an acyclic complete resource CDG.A one-bit crossed state tracks whether the current same-group segment has crossed its dateline; the VC word changes class at most three times per route.Source: §4.2 · pp. 7–8
  • The torus relation remains minimal and all-pairs connected, but assigning one VC to every permitted hop leaves a cyclic complete resource CDG for every n ≥3.The result concerns this two-turn physical relation, not every possible torus routing relation.Source: §4.2 · pp. 7–8

4.3 Restricted single-link fault extension

  • The fault extension assumes one static, globally known bidirectional link failure and a shared fault-aware configuration at the start of a routing epoch.Packets using an older configuration are absent during that epoch.Source: §4.3 · p. 8
  • For a failed hop, the extension uses a controlled same-group two-hop triangle substitution, with mesh substitutions restricted to intermediate nodes inside the finite mesh.Both geometric bypass orders are available on the torus, while the selected first hop fixes the second.Source: §4.3 · p. 8
  • Under the restricted failure model, the fault-aware relations remain all-pairs connected and every route is at most one hop longer than the healthy shortest-path distance.The one-VC mesh and two-VC torus resource CDGs remain acyclic.Source: §4.3 · p. 9

5 Implementation

The implementation realizes the mesh and torus routing relations in gem5 and independently checks their resource-dependency graphs. Candidate-selection policies affect performance, while the routing relation and torus VC assignment provide deadlock freedom.

5 Implementation

  • The gem5 implementation instantiates HexMesh with 3n^2 − 3n + 1 routers and HexTorus with quotient links from the stated period vectors.Both use the same representative vertex set and six directions.Source: §5 · p. 9
  • The mesh filters minimal candidates that would make either prohibited turn; the torus selects a closest lift and applies the L*U* restriction with per-hop dateline VC assignment.The torus VC phase resets before the first U-group hop after an L-to-U transition; assigning one VC per packet is not equivalent.Source: §5 · p. 9
  • Fixed, random, and credit policies choose among legal minimal candidates, but deadlock freedom comes from the routing relation and torus VC assignment.Credit selects the candidate with the most downstream output credits.Source: §5 · p. 9
  • An independent checker constructs the complete mesh and torus resource CDGs, while the simulator records latency, throughput, hops, VC activity, and stalls.The checker tests acyclicity for the finite sizes evaluated.Source: §5 · p. 9

6 Evaluation

The evaluation uses Garnet synthetic traffic to measure routing performance, compare the hex topologies with Mesh_XY, probe sector pressure and torus VC behavior, and assess scaling. Results show lower zero-load latency for the torus, a throughput advantage for credit-selected mesh routing, and increased performance costs in restricted sectors and at larger sizes.

6.1 Methodology

  • Each run averages three seeds over 10,000 cycles; uniform traffic uses an all-node pair-list generator, and a negligible number of boundary sources are relaxed when no strict sector-and-distance pair exists.Runs were checked for nonempty statistics, normal exit, finite measures, and no fatal, assertion, or deadlock messages.Source: §6.1 · pp. 9–10, Table 1 · p. 10

6.2 Routing performance

  • 0.2456 is the mesh credit peak accepted throughput, 1.34× the mesh fixed result; torus credit reaches 0.1744 versus 0.1671 for fixed, while torus zero-load latency is about 16.7 cycles versus mesh's 20.4.Figure 3 and Table 2 cover all-node pair-list uniform traffic at n = 8.Source: §6.2 · p. 10, Figure 3 · p. 10, Table 2 · p. 10

6.3 Comparison with conventional 2D mesh XY routing

  • 1.18× (HexMesh) and 1.44× (HexTorus) are the zero-load latency reductions versus Mesh_XY; HexMesh credit peaks at 0.2456 versus 0.1853, while HexTorus peaks at 0.1744.The comparison matches node count and traffic, not router radix, link count, wiring budget, or area.Source: §6.3 · p. 11, Figure 4 · p. 11, Table 3 · p. 11

6.4 Pressure in the restricted sectors

  • Boundary-sector latency ratios are often above one at high load, and fixed and credit selection yield higher maximum throughput for internal than boundary traffic on both topologies.Boundary and internal traffic use matched distance distributions; random-selection results are less regular.Source: §6.4 · p. 11, Table 4 · p. 12, Figure 5 · p. 12

6.5 Torus dateline VC behavior

  • 0.76–0.78 of torus channel hops use VC1 under dateline-heavy traffic, compared with about 0.28 under uniform traffic; dateline VC stalls rise by more than an order of magnitude.All runs complete without deadlock; the experiment's restricted injection-rate range does not measure global saturation throughput.Source: §6.5 · p. 12, Figure 6 · p. 12, Table 5 · p. 13

6.6 Scaling

  • Zero-load latency increases with n, while the torus remains lower at every evaluated size; maximum accepted throughput decreases as both topologies grow from n = 4 to n = 12.For n = 4, 8, and 12, mesh credit peaks at 0.4025, 0.2456, and 0.1477; torus credit peaks at 0.4012, 0.1744, and 0.1040.Source: §6.6 · p. 13, Figure 7 · p. 13, Table 6 · p. 13

7 Discussion and Limitations

The mesh’s linear potential does not extend to a strict order on the periodic torus, where one VC leaves a directed resource cycle. The proposed two-VC construction resolves this for its stated setting, while the evaluation and fault results remain bounded in scope.

7 Discussion and Limitations

  • The mesh potential cannot order the periodic torus because directed non-contractible cycles preclude a strictly increasing single-valued node function.The torus construction instead uses Hamiltonian coordinates and two VC phases to create an acyclic resource ranking.Source: §7 · p. 14
  • The main routing guarantees assume reliable bidirectional links, no U-turns, and the specified period lattice.The single-failure extension covers only one static, globally known bidirectional failure with prescribed same-group triangle substitutions; it does not cover multiple faults or dynamic reconfiguration.Source: §7 · p. 14
  • The evaluation uses synthetic traffic and omits application traces, power, area, timing closure, and router critical-path measurements.It also omits hotspot traffic and application-driven burstiness; the single-link extension has no fault-injection performance experiments.Source: §7 · p. 14
  • For n ≥3, the particular one-VC torus relation has a cyclic complete CDG, while two VCs suffice for the Hamiltonian-dateline construction.The paper does not claim that two VCs are necessary across other routing relations or flow-control mechanisms.Source: §7 · p. 14

8 Conclusion

The conclusion presents deadlock-free minimal routing for finite triangular-lattice meshes and their periodic tori, with different resource-ordering mechanisms for each. The appendix’s lattice facts establish why shortest paths use only adjacent directions.

8 Conclusion

  • The mesh uses one VC and two forbidden turns, while the torus needs two VC phases and Hamiltonian datelines to order resources acyclically.Both physical relations preserve minimal all-pairs connectivity; the one-VC torus relation instead has a cyclic resource CDG for n ≥3.Source: §8 · p. 14

AI use statement

  • The authors report using generative AI for language editing, literature discovery, consistency checks, and experiment-script development, while retaining responsibility for verification.They state that no experimental measurements or empirical claims in the draft were generated or fabricated by an AI system.Source: AI use statement · p. 15

Ethics statement

  • The work involves no human participants, personal data, or deployment of a decision-making system.The authors identify accurate reporting of proofs, implementation details, and experimental results as the relevant general ethical concern.Source: Ethics statement · p. 15

Reproducibility statement

  • The paper states that topology, routing rules, VC transitions, and theorem assumptions appear in the main text, with complete proofs in the appendix.Its implementation includes an independent CDG checker and scripts for generating traffic pairs, running experiments, checking results, and summarizing the simulation configuration.Source: Reproducibility statement · p. 15

A Basic Triangular-Lattice Facts

  • Every lattice geodesic uses steps from at most two adjacent directions, since nonadjacent steps can be shortened or canceled.A separation-two pair can be replaced by one step, and opposite steps can be deleted.Source: A Basic Triangular-Lattice Facts · p. 17

B Proof of the Mesh Routing Theorem

The proof establishes that the mesh routing relation remains minimal and connected despite forbidding two directed turns. Its one-VC resource CDG is acyclic because permitted direction groups are ordered and dependencies within each group are monotone under a linear potential.

B Proof of the Mesh Routing Theorem

  • Every source-destination pair has a permitted mesh route of lattice-geodesic length, and every such route stays inside the finite mesh.Adjacent-direction paths make each of x, y, and x + y monotone or constant, so intermediate vertices remain within the defining strips.Source: B Proof of the Mesh Routing Theorem · p. 17
  • When both adjacent directions occur, a within-group sector permits every ordering, while cross-group sectors retain only lower-group-before-upper-group words.On sector boundary rays, the minimal direction word is unique.Source: B Proof of the Mesh Routing Theorem · p. 17
  • The mesh relation is partially adaptive for n ≥2, with two distinct shortest direction words available for one source-destination pair.For displacement from (−1, 0) to (0, 1), both d0d1 and d1d0 are legal.Source: B Proof of the Mesh Routing Theorem · p. 18
  • The forbidden turns force every permitted path’s group sequence to be L∗U∗, excluding CDG cycles that would need an edge from U back to L.A cycle confined to either group is excluded by strict potential change along each dependency chain.Source: B Proof of the Mesh Routing Theorem · p. 18
  • Within-group dependencies strictly increase Φ(x, y) = x + 2y in U and strictly decrease it in L, so neither group can contain a cycle.Together with the cross-group ordering, this proves acyclicity of the complete one-VC resource CDG.Source: B Proof of the Mesh Routing Theorem · p. 18

C Geometry of the Periodic Torus

The torus geometry provides a complete nonredundant representative set and a unique closest lift for every quotient pair. Its diameter is n −1, and Hamiltonian coordinates induce cyclic orders over all quotient nodes.

C Geometry of the Periodic Torus

  • The quotient period lattice is invariant under 60° rotations, which cyclically permute the directions while preserving the hexagonal norm.The rotation sends T1 to T2 and T2 to T2 − T1.Source: C Geometry of the Periodic Torus · p. 18
  • Every nonzero period vector has hexagonal norm at least 2n −1, which makes the representatives in Vn distinct and complete for the quotient.The quotient and Vn each contain 3n^2 −3n + 1 nodes.Source: C Geometry of the Periodic Torus · p. 18
  • The torus diameter is n −1, attained by the quotient class represented by v = (n −1, 0).That representative is the unique closest representative of its quotient class.Source: C Geometry of the Periodic Torus · p. 18
  • Every ordered quotient-node pair has a unique closest lattice lift.If two distinct period translates both minimized distance, their difference would violate the lower bound on nonzero period-vector norm.Source: C Geometry of the Periodic Torus · pp. 18–19
  • The Hamiltonian coordinate HU is well-defined and bijective on the quotient, and HL is also bijective.Repeated d0 channels visit every quotient node in HU order, while repeated d3 channels visit every node in HL order.Source: C Geometry of the Periodic Torus · p. 19

D Proof of the Torus Routing Theorem

The torus routing relation is minimal and all-pairs connected, but its one-VC resource graph contains a directed cycle for n ≥ 3. Two VCs, Hamiltonian datelines, and a global resource rank yield an acyclic complete resource CDG.

One-VC cycle

  • For every n ≥ 3, a one-VC assignment admits a directed resource cycle formed by channels along the Hamiltonian cycle.The two-hop route d0d0 for each ordered pair induces consecutive dependencies around that cycle.Source: D Proof of the Torus Routing Theorem · p. 19

Minimal all-pairs connectivity

  • The torus relation is minimal and all-pairs connected because each pair has a unique closest lift and at least one permitted shortest route.Geodesics use at most two adjacent directions; cross-group sectors enforce the L-before-U order.Source: D Proof of the Torus Routing Theorem · p. 19

Partial adaptivity

  • The relation is partially adaptive if and only if n ≥ 3: for n ≥ 3, d0d1 and d1d0 offer distinct first channels, while n = 2 has unique minimal next channels.The n ≥ 3 example uses displacement d0 + d1; the n = 2 torus has diameter one.Source: D Proof of the Torus Routing Theorem · pp. 19–20

Single-dateline property

  • Each maximal same-group segment crosses its Hamiltonian dateline at most once, so its VC state changes from 0 to 1 at most once.The unwrapped coordinate advances positively by less than N over the segment.Source: D Proof of the Torus Routing Theorem · p. 20

Acyclicity of the complete resource CDG

  • Two VCs and a global rank make every edge of the complete torus resource CDG increase strictly, proving the routing relation deadlock-free.The rank accounts for group order and each segment's dateline crossing.Source: D Proof of the Torus Routing Theorem · p. 20

Resource order

E Proof of the Restricted Single-Link Fault Extension

A single static, globally known bidirectional link failure can be handled by rotating the turn rule toward the failed orientation and substituting a same-group triangle bypass. The resulting relations preserve connectivity, stay within the original VC counts, and retain deadlock freedom under the stated fault scope.

Rotation covariance

  • Rotation maps each failure orientation's vertex set, torus, direction groups, and forbidden turns to the base routing construction.The rotated healthy relations therefore inherit the original minimal all-pairs connectivity conclusions.Source: E Proof of the Restricted Single-Link… · p. 21

Local triangle bypass

  • A failed hop can be replaced by an available two-hop triangle bypass in either direction, without introducing a U-turn or repeated vertex.At least one candidate intermediate node lies in the finite mesh; both substitutions exist on the torus.Source: E Proof of the Restricted Single-Link… · pp. 21–22

Fault transformation

  • The bypass preserves the route's group word, while the rotated healthy relation supplies a shortest path before substitution.An affected route replaces exactly one hop by two; an unaffected route remains unchanged.Source: E Proof of the Restricted Single-Link… · p. 22

Connectivity and path length

  • Both fault-aware relations remain all-pairs connected, and every permitted route is at most one hop longer than the healthy shortest-path distance.The bound is relative to the healthy distance, not a claim of shortestness in the faulted graph.Source: E Proof of the Restricted Single-Link… · pp. 21–22

Mesh deadlock freedom

  • The fault-aware mesh resource CDG is acyclic with one VC because the rotated potential increases within Uj, decreases within Lj, and cross-group dependencies only go Lj to Uj.The argument includes channels inserted by either bypass order.Source: E Proof of the Restricted Single-Link… · p. 22

Single-dateline preservation

  • Each fault-aware same-group segment retains its healthy parent's total unwrapped advance, so its VC phase changes at most once despite the added hop.Positive per-hop increments and the unchanged advance preserve the single-dateline property.Source: E Proof of the Restricted Single-Link… · pp. 22–23

Torus resource-CDG acyclicity

  • The fault-aware torus resource CDG is acyclic with two VCs because every within-group and cross-group dependency strictly increases the rank.The argument includes the new bypass turns and VC resets at group boundaries.Source: E Proof of the Restricted Single-Link… · p. 23

Scope

  • The result covers only one static bidirectional link failure under a globally consistent routing epoch.Multiple failures, node failures, and in-flight configuration changes are outside the proof's scope.Source: E Proof of the Restricted Single-Link… · p. 23

F Reassessment of the Three-VC Scheme of Shamaei et al.

The reassessment reconstructs the prior H4 routing and VC assignment, then exhibits a directed resource cycle assembled from distinct minimal packets. This contradicts the prior complete-CDG acyclicity claim, but does not establish a reachable packet-level deadlock.

Witness minimality

Cycle verification

  • Seven minimal witness packets induce a closed directed resource cycle because each contributes a consecutive dependency and all use VC class 1.Each witness has at least one wraparound hop, which assigns every hop of that packet to VC class 1.Source: F Reassessment of the Three-VC Scheme… · pp. 24–25

Reassessment

  • The cycle contradicts the published complete-CDG acyclicity claim, whose argument does not rule out dependencies assembled from distinct minimal packets.The witnesses are no longer than the H4 diameter of three hops.Source: F Reassessment of the Three-VC Scheme… · p. 25

Limitation

  • A cycle in the union CDG alone does not prove that the fully adaptive three-VC algorithm can reach a packet-level deadlock.Packets may retain alternative outputs or an escape structure not represented by one selected witness route.Source: F Reassessment of the Three-VC Scheme… · p. 25
Loading 2609.09746v1…