Design a GPU-Aware Pod Scheduler and Cluster Manager

Problem Description

You are tasked with designing a simplified, object-oriented cluster manager that includes a GPU-aware pod scheduler. The system manages a collection of nodes, each providing a fixed number of GPUs. Pods, which represent workloads, request a fixed number of GPUs and must be placed entirely on a single node that has sufficient free GPUs.

Core Assumptions

• Pods cannot be split across multiple nodes.
• GPUs are fungible; there is no awareness of GPU topology or NUMA architecture.

Data Structures

• Node: Each node is defined by its name (string), total_gpu (integer representing total GPUs available on the node), and a list of running_pods (array of Pod objects currently assigned to it).
• Pod: Each pod is defined by its name (string) and gpu_required (integer representing the number of GPUs it needs).

Required APIs

Implement the following APIs for the cluster manager:

• add_node(name: string, total_gpu: int): Adds a new node to the cluster.
• remove_node(name: string): Removes an existing node from the cluster.
• add_pod(name: string, gpu_required: int): Registers a new pod definition with the system.
• schedule_pod(pod_name: string): Assigns the specified pod to a suitable node with enough free GPUs.
• remove_pod(pod_name: string): Removes a pod from its assigned node and the system.
• get_node_utilization(name: string): Returns the current GPU utilization for a given node.
• list_nodes(): Returns a list of all nodes in the cluster.
• list_pods(): Returns a list of all pods managed by the system.

Additional Design Considerations

Your design must also address the following aspects:

• Efficient Data Structures: Propose and justify data structures to support efficient lookups of nodes by available GPUs and pods by name.
• Placement Strategy: Define and justify a pod placement strategy (e.g., best-fit, first-fit).
• Index Management: Describe how internal indexes and data structures are updated on every add, remove, schedule, and evict operation.
• Concurrency and Failure Handling: Detail your approach to concurrency control for simultaneous add_node, add_pod, and schedule_pod operations. Address idempotency and failure scenarios, such as attempting to remove a node that still has running pods, or the need for pod rescheduling if a node is removed.
• Complexity Analysis: Provide the time and space complexity for each implemented API.
• Pseudocode: Present pseudocode for the schedule_pod method, demonstrating your chosen placement strategy.
• Edge Cases: Discuss how your design handles edge cases, including:
  • A pod requiring more GPUs than any single node can provide (gpu_required > total_gpu).
  • Resource fragmentation, where multiple small pods occupy a large node, preventing larger pods from being scheduled even if total free GPUs are sufficient.