Group GPUs by node and partition by links

Problem: GPU graph grouping and link-maximizing partition

You are given a cluster of GPUs represented as a graph:

• Each GPU has a unique gpuId and belongs to a physical machine identified by nodeId .
• GPUs can be connected by bidirectional links (edges). A link (u, v) indicates GPU u and v have a direct high-speed connection.
• The graph may be disconnected.

Part 1 — Group GPUs by nodeId

Return a grouping of GPUs such that all GPUs belonging to the same nodeId appear in the same output group.

Input (one possible representation)

• gpus : list of GPU objects, each with fields {gpuId, nodeId}
• links : list of undirected edges (gpuId1, gpuId2)

Output

• A mapping (or list of groups) where each group contains all gpuId s with the same nodeId .

Notes

• Assume you may need to traverse via the link graph to discover all GPUs if the input is not presented as a fully materialized list.

Part 2 (Follow-up) — Partition into exactly X groups to maximize internal links

Now ignore nodeId for grouping, and instead partition all GPUs into exactly X disjoint groups.

Goal: maximize the total number of links whose endpoints fall within the same group (i.e., maximize intra-group edges).

Output

• A partition assignment group[gpuId] in {1..X} (or X lists of gpuId s).

Clarifications/constraints to discuss

• Are groups required to be balanced in size? (If not specified, assume no.)
• Expected approach: explain an algorithmic strategy and its trade-offs (exact vs heuristic/approximation), and analyze time complexity.