Distributed training basics in MLOps - Time & Space Complexity

Time Complexity: Distributed training basics

O(n)

Understanding Time Complexity

When training machine learning models across many machines, it is important to understand how the training time changes as we add more data or machines.

We want to know how the total work grows when we split tasks in distributed training.

Scenario Under Consideration

Analyze the time complexity of the following distributed training loop.

for epoch in range(num_epochs):
    for batch in data_batches:
        distribute_batch_to_workers(batch)
        workers_train_on_batch()
        gather_results_from_workers()
    update_model_parameters()

This code splits data into batches, sends each batch to workers, trains in parallel, then collects results to update the model.

Identify Repeating Operations

Look for loops or repeated steps that take most time.

• Primary operation: Training on each batch by workers.
• How many times: Once per batch, repeated for all batches in all epochs.

How Execution Grows With Input

As the number of batches grows, the total training time grows roughly in proportion.

Input Size (n = batches)	Approx. Operations
10	10 training steps per epoch
100	100 training steps per epoch
1000	1000 training steps per epoch

Pattern observation: Doubling batches roughly doubles the training steps, so time grows linearly with data size.

Final Time Complexity

Time Complexity: O(n)

This means training time grows linearly with the number of data batches processed.

Common Mistake

[X] Wrong: "Adding more machines always makes training time go down proportionally."

[OK] Correct: Communication and coordination between machines add overhead, so time does not always shrink perfectly with more workers.

Interview Connect

Understanding how training time scales with data and machines helps you explain real-world trade-offs in distributed machine learning.

Self-Check

"What if we increased the number of workers instead of batches? How would the time complexity change?"

Practice

1. What is the main purpose of distributed training in machine learning?

easy

A. To avoid using GPUs during training

B. To split the training workload across multiple machines or GPUs

C. To increase the learning rate automatically

D. To reduce the size of the training dataset

Solution

1. Step 1: Understand distributed training goal

   Distributed training is designed to share the training task among several machines or GPUs to speed up the process.

2. Step 2: Analyze options

   Only To split the training workload across multiple machines or GPUs correctly describes this purpose. Options A, B, and C do not relate to workload distribution.

3. Final Answer:

   To split the training workload across multiple machines or GPUs -> Option B

4. Quick Check:

   Distributed training = workload split [OK]

Hint: Distributed training means sharing work across machines [OK]

Common Mistakes:

• Thinking distributed training reduces dataset size
• Confusing distributed training with hyperparameter tuning
• Believing distributed training avoids GPU use

2. Which of the following is the correct way to initialize a process group for distributed training in PyTorch?

easy

A. torch.distributed.init_process_group(backend='nccl', rank=0, world_size=1)

B. torch.init_process_group(backend='nccl', rank=0, world_size=1)

C. torch.distributed.start_process_group(backend='nccl', rank=0, world_size=1)

D. torch.distributed.init_group(backend='nccl', rank=0, world_size=1)

Solution

1. Step 1: Identify correct function name

   The correct function to initialize communication is torch.distributed.init_process_group.

2. Step 2: Check syntax correctness

   torch.distributed.init_process_group(backend='nccl', rank=0, world_size=1) uses the correct module and function name with proper parameters. Other options use incorrect function names or modules.

3. Final Answer:

   torch.distributed.init_process_group(backend='nccl', rank=0, world_size=1) -> Option A

4. Quick Check:

   Correct init function = torch.distributed.init_process_group(backend='nccl', rank=0, world_size=1) [OK]

Hint: Use torch.distributed.init_process_group to start communication [OK]

Common Mistakes:

• Using wrong function names like start_process_group
• Calling init_process_group from wrong module
• Misspelling function or module names

3. Given the following code snippet for distributed training setup, what is the output of print(rank, world_size)?

import torch.distributed as dist
rank = 2
world_size = 4
print(rank, world_size)

medium

A. 4 2

B. Error: rank and world_size undefined

C. 0 1

D. 2 4

Solution

1. Step 1: Analyze variable assignments

   Variables rank and world_size are assigned values 2 and 4 respectively before the print statement.

2. Step 2: Understand print output

   Printing rank and world_size will output '2 4' exactly as assigned.

3. Final Answer:

   2 4 -> Option D

4. Quick Check:

   Print rank, world_size = 2 4 [OK]

Hint: Print variables as assigned to see output [OK]

Common Mistakes:

• Confusing rank with world_size order
• Assuming variables are undefined
• Expecting automatic values without assignment

4. You wrote this code to initialize distributed training but get an error:

import torch.distributed as dist
dist.init_process_group(backend='nccl', rank=0)

What is missing that causes the error?

medium

A. The rank parameter should be a string

B. The backend parameter is incorrect

C. The world_size parameter is missing

D. The import statement is wrong

Solution

1. Step 1: Check init_process_group parameters

   The function requires both rank and world_size parameters to know the total number of processes.

2. Step 2: Identify missing parameter

   The code misses world_size, which causes the error.

3. Final Answer:

   The world_size parameter is missing -> Option C

4. Quick Check:

   Missing world_size causes error [OK]

Hint: Always provide world_size with rank in init_process_group [OK]

Common Mistakes:

• Omitting world_size parameter
• Using wrong backend names
• Passing rank as string instead of int

5. In a distributed training setup with 4 GPUs, you want each process to know its rank and the total number of processes. Which code snippet correctly sets this up and prints the rank and world size?

hard

A. import torch.distributed as dist
dist.init_process_group(backend='nccl')
rank = dist.get_rank()
world_size = dist.get_world_size()
print(rank, world_size)

B. import torch.distributed as dist
world_size = 4
rank = dist.get_rank()
dist.init_process_group(backend='nccl', rank=rank, world_size=world_size)
print(rank, world_size)

C. import torch.distributed as dist
rank = 0
world_size = 4
dist.init_process_group(backend='nccl', rank=rank, world_size=world_size)
print(rank, world_size)

D. import torch.distributed as dist
rank = dist.get_rank()
world_size = dist.get_world_size()
dist.init_process_group(backend='nccl', rank=rank, world_size=world_size)
print(rank, world_size)

Solution

1. Step 1: Understand correct initialization order

   dist.init_process_group must be called before calling dist.get_rank() or dist.get_world_size() to initialize communication.

2. Step 2: Analyze each option

   import torch.distributed as dist dist.init_process_group(backend='nccl') rank = dist.get_rank() world_size = dist.get_world_size() print(rank, world_size) initializes the process group first, then gets rank and world size, then prints them. Other options either get rank before initialization or pass rank manually without initialization.

3. Final Answer:

   import torch.distributed as dist dist.init_process_group(backend='nccl') rank = dist.get_rank() world_size = dist.get_world_size() print(rank, world_size) -> Option A

4. Quick Check:

   Init first, then get rank/world_size = import torch.distributed as dist dist.init_process_group(backend='nccl') rank = dist.get_rank() world_size = dist.get_world_size() print(rank, world_size) [OK]

Hint: Initialize before getting rank and world size [OK]

Common Mistakes:

• Calling get_rank before init_process_group
• Passing rank manually without init
• Not calling init_process_group at all