PROBLEM STATEMENT

An intelligent compu ng cluster innova vely adopts OXC (op cal circuit switch) as the core layer to
enable ultra-large-scale interconnec on for tens of thousands of compu ng cards.

While OXC demonstrates advantages in latency, power efficiency, and bandwidth compared to
electrical switches, its switching capability degrades from all-to-all to one-to-one. This makes it
challenging to fully u lize OXC bandwidth.

Please develop a strategy to determine the op mal OXC configura on and rou ng schemes in
response to AI tasks in real- me.

All links appearing in this problem can be considered as bidirec onal edges.

What is OXC?

OXC can freely establish an op cal connec on between ports by rota ng micro-mirrors to reflect light. An OXC
op cal connec on refers to a connec on between one internal port and another internal port of the OXC,
forming a bidirec onal pathway.

In the illustrated OXC, one op cal connec on is established between ports 0 and 2, while another connects
ports 1 and 4. This allows the device connected to port 0 to have a communica on link with the device
connected to port 2, and similarly for ports 1 and 4. Note that op cal connec ons are one-to-one
 PROBLEM STATEMENT

In the network scenario shown in the figure above, OXC #0 establishes an op cal connec on between port 0
and port 2, crea ng a communica on link between Spine #0 and Spine #1. By establishing an op cal
connec on between port 1 and port 5, it creates a communica on link between Spine #0 and Spine #2

Overview of Two-Tier Electrical and One-Tier Op cal Network

A Group contains two ers of electrical switches (referred to as Leaf and Spine, as shown in the figure) and
several NPUs (Neural Processing Units). Communica on between NPUs within a Group can be completed solely
through the electrical switches.

The OXC is only used to route traffic between different Groups. Such traffic is transmi ed via the following
path: NPU – Leaf – Spine – OXC – Spine – Leaf – NPU.
 PROBLEM STATEMENT

For each Spine, let Up be the number of links to OXCs and Down be the number of links to Leaves. We define
the convergence ra o as Up:Down. It is guaranteed that this ra o is 1:1, 1:3, or 1:7.

Introduc on to Mul -Plane Network

 Spines and OXCs are divided into several independent plane sets (in the industry, this is done to scale
the network size).

 In each plane, between each Spine and each OXC belonging to this plane, there are exactly K links.

 There are no links between Spines and OXCs in different planes.

 Within each Group, there is exactly one physical link between each Leaf and each Spine.

Specific Network Descrip on

 There are M OXCs numbered from 0 to M−1. OXC number i belongs to the plane numbered ⌊i/(M/P)⌋.

 Each Group has S Spines numbered from 0 to S−1. Spine number i belongs to the plane
numbered ⌊i(S/P)⌋.

 Each Group has L Leaves, numbered from 0 to L−1.

 Within the same plane, each OXC and each Spine have exactly K links, numbered from 0 to K−1.
 PROBLEM STATEMENT

 There are P planes numbered from 0 to P−1. The number of OXCs M and the number of Spines S are
both divisible by P.

 From this, it follows that the number of ports per OXC is R=N*(S/P)*K. The ports of each OXC are
numbered from 0 to R−1.

The port corresponding to OXC number m, Group number i, Spine number j, and link number k has the
number (i*(S/P)*K)+((j*mod(S/P))*K)+k.

For OXC number m, port number i corresponds to Group number ⌊i/((S/P)*K)⌋, Spine
number ⌊{i*mod((S/P)*K)}/K⌋+⌊m/(M/P)⌋*(S/P), and link number (i*(mod(K)).

Leaf-Level Communica on Flow Demand

Specifically, each query can be considered as several bidirec onal flows. Each flow goes between some two
leaves, LeafA and LeafB.

A flow is transmi ed via a bidirec onal path: LeafA – SpineA – OXC – SpineB – LeafB. It is guaranteed that, for
all given flows, the Group numbers of LeafA and LeafB are different.

Now it is required to assign routes to all flows. We define the maximum flow conflict as the maximum number
of flows passing through any link in the network.

Minimize the maximum flow conflict as much as possible.

OXC Physical Topology Adjustment

We define the OXC adjustment cost as a kind of edit distance between the target physical topology and the
current physical topology. Specifically, we adjust an OXC by performing the following ac ons, each of which has
a cost of 1:

 Establish a new connec on between a pair of ports.

 Remove an exis ng connec on between a pair of ports.

Minimize the OXC adjustment cost as much as possible.

Ini ally, before any queries, no ports of any OXC have established connec ons. Before each query a er the first
one, the physical topology is exactly as it was a er the previous query.

Here is an example of edit distance calcula on:

 Original topology: Port 1 is connected to port 2, port 0 is idle and unconnected.

 New topology: Port 1 is connected to port 0, port 2 is idle and unconnected.

 Removing the connec on between port 1 and port 2, and establishing the connec on between port 1
and port 0, results in an OXC adjustment cost of 2.
 PROBLEM STATEMENT

Input
The first line contains three posi ve integers N, S, and L, represen ng the number of Groups, the number of
Spines per Group, and the number of Leaves per Group, respec vely (2≤N≤2^5; 1≤S≤2^5; 1≤L≤2^6;
addi onally, 2≤N⋅S⋅L≤2^14).

The second line contains three posi ve integers M, K, and P, represen ng the number of OXCs, the number of
links between each OXC and each Spine within the same plane, and the number of planes
(1≤M≤2^8; 1≤K≤2; 1≤P≤2^4).

Then five queries are given. For each query, the input format is as follows:

 The first line of a descrip on contains a posi ve integer Q, indica ng the number of bidirec onal flow
demands (1 ≤ Q ≤ (1/2)*(N⋅S⋅L)).

 Each of the next Q lines describes a bidirec onal flow demand between LeafA and LeafB. The i-th line,
represen ng the i-th bidirec onal flow demand, contains four integers, in order:

1. gA, number of Group of LeafA

2. LeafA number

3. gB, number of Group of LeafB

4. LeafB number

The group numbers sa sfy 0≤gA<gB≤N−1, and the leaf numbers are from 0 to L−1.

It is guaranteed that S and M are divisible by P, and that N−1 ≤ S*(M/P)*K.

It is guaranteed that the convergence ra o {(M/P)⋅K}/L is either 1:1 or 1:3 or 1:7.

It is guaranteed that each leaf appears no more than S mes in each query.

Output
For each query, the output format is as follows:

 First, output M lines. The i-th line (0≤i≤M−1) should contain R=N*(S/P)*K integers, represen ng the
port connec on rela onships of OXC number i. The j-th integer vj (0≤j≤R−1) indicates that the j-th port
of this OXC is connected to the vj-th port. If vj is −1, the port is idle.

 Then output Q lines. For the i-th line (0≤i≤Q−1), output the planned rou ng path for the i-th flow
demand, containing five integers, in order:

1. Spine number x (0≤x<S) connected to LeafA

2. Link number kx (0≤kx<K) of x connected to the OXC

3. OXC number m (0≤m<M)

4. Spine number y (0≤y<S) connected to LeafB

5. Link number ky (0≤ky<K) of y connected to the OXC