Tetris improves scheduling for photonic switch networks in computing
Tetris: Circuit Scheduling for Rearrangeably Non-Blocking Photonic Interconnects
Networking and Internet Architecture
Summary
Photonic interconnects use light to send data between computers, but managing connections is tricky because new connections can disrupt existing ones. The authors developed Tetris, a clever scheduling method that prioritizes busy parts of the network and tries to avoid unnecessary changes during data transfer. Their approach speeds up communication by up to 6.6 times compared to older methods, especially for all-to-all communication tasks. This work highlights new challenges and solutions for networks that can rearrange their connections dynamically.
What this means in practice
- •For network schedulers: Schedule routes in rearrangeably non-blocking photonic networks to reduce data transfer completion time and avoid unnecessary switch reconfigurations.
- •For high-performance computing teams: Optimize data exchange in distributed computing environments that use photonic interconnects, improving communication speed for intensive tasks.
Authors
Eliezer Amponsah, Deeksha P Rao, Vamsi Addanki
Abstract
Reconfigurable photonic interconnects are emerging as a promising communication architecture for next-generation distributed computing. Yet, most circuit schedulers are designed around an idealized view of the interconnect as either blocking or strictly non-blocking. Practical scalable designs are often rearrangeably non-blocking (RNB), with connections routed through networks of internal $2\times2$ switches. This changes the scheduling problem fundamentally: establishing a new connection can force existing connections to be rerouted, trigger state changes across multiple internal switches, and impose reconfiguration delay on otherwise unrelated traffic. We present Tetris, a circuit scheduling algorithm for RNB photonic interconnects. Tetris builds on two observations. First, All-to-All demands are often not doubly stochastic, leaving a small number of endpoints as communication bottlenecks. Second, reconfiguration delay can be large enough to change which connection should be scheduled next. Tetris prioritizes bottleneck endpoints using their remaining communication and reconfiguration work, while selecting and routing matchings to preserve ongoing connections whenever possible. Matchings ensure progress, but connections are scheduled independently, allowing completed connections to be replaced without matching-wide barriers and incurring delay only at switches whose states change. Our simulation and hardware-emulation results show that Tetris reduces All-to-All demand completion time by up to $6.6$x over Birkhoff--von Neumann-based scheduling and by $30$% over Sunflow. More broadly, RNB interconnects raise new questions in multi-tenant scheduling and routing for partial reconfiguration, which we discuss at the end of the paper.