Abstract
This study presents the first analytical model for Pipelined Circuit Switching (PCS) in hypercube networks. By integrating Markov chains to model backtracking behavior with M/G/1 queueing theory for source node delays, the proposed model accurately predicts message latency under various traffic loads and message lengths. Validation against discrete-event simulations demonstrates high predictive accuracy for both 64-node and 256-node hypercube configurations.
Introduction
In high-performance computing, interconnection network performance is a critical bottleneck. Traditional methods like circuit switching and wormhole switching offer different trade-offs between resource reservation and contention management. Pipelined Circuit Switching (PCS) attempts to combine the benefits of both by reserving paths while employing a backtracking mechanism to handle contention. When a header flit encounters a busy channel, it backtracks to the previous node to attempt an alternative route, enabling deadlock-free, fully adaptive routing.
Despite its advantages, the non-deterministic nature of backtracking and virtual channel (VC) multiplexing makes mathematical latency prediction challenging. Prior to this work, no reliable analytical model existed that accounted for these complex dynamics in hypercube networks.
Methodology
The analytical model decomposes message latency into two primary components: source node waiting time and network traversal time.
Markov Chain for Path Setup
The core innovation lies in using a Markov chain to model the path search phase. Each state represents the number of hops a header flit has progressed from the source. Forward transitions represent successful virtual channel reservations, while backward transitions represent backtracking due to channel contention. This framework allows for the calculation of the expected duration ($C$) required to establish a complete path.
M/G/1 Queueing and VC Multiplexing
The source node's injection channel is modeled as an M/G/1 queueing system. The authors approximate service time variance based on network latency to account for congestion-induced jitter. Additionally, a scaling factor ($ar{V}$) is introduced to account for virtual channel multiplexing, where multiple logical paths share physical bandwidth, effectively slowing flit transmission as traffic increases.
Experimental Validation
The model was validated using a custom discrete-event simulator under a uniform traffic pattern. Two hypercube configurations were tested:
- 2-ary 6-cube: A 64-node network.
- 2-ary 8-cube: A 256-node network.
Results and Discussion
The analytical model's predictions were compared against simulation results across a range of traffic rates and message lengths ($M=32$ and $M=48$ flits).
As shown in the figure above, the mathematical model closely tracks the simulation data. Latency remains stable at low traffic rates but increases sharply as the network approaches saturation. The model accurately captures the impact of message length, showing that longer messages ($M=48$) lead to higher latency and earlier saturation due to increased resource occupancy.
The results confirm that a Markovian approach can effectively capture the behavior of complex, non-deterministic routing protocols like PCS. The model also quantifies the overhead of the setup phase, noting that the acknowledgment flit adds a constant factor proportional to the distance $d$.
Conclusion and Future Work
This research provides a robust framework for analyzing PCS in hypercube networks. While the current model assumes uniform traffic and is tailored to hypercube topologies, it sets the stage for broader applications. Future work aims to generalize this model for high-radix $k$-ary $n$-cubes, such as tori and grids, and to explore non-uniform, bursty traffic patterns characteristic of real-world supercomputing workloads.
Summary updated