ML System Optimisation 

Prof. Madhusudhanan

               SYSTEM OPTIMIZATION
                    │
         ┌──────────┴──────────┐
         │                          │
     HARDWARE                 SOFTWARE
         │                     │
   CPU/GPU/TPU            PARALLELIZATION
                               │
         ┌─────────────────────┼─────────────────────┐
         │                     │                             │
   DATA LEVEL             TASK LEVEL              ALGORITHM LEVEL
         │                     │                     │
   Same operation         Different tasks         Redesign algorithm
   different data         concurrently          for parallelism
         │                     │                     │
   Batch processing       Pipelines              Divide & conquer
   GPU/CUDA               Scheduling             Merge sort
   CNN                    Dependencies           Matrix multiplication
                          Load imbalance         Strassen
                          Locks/barriers         MapReduce
         │                     │                     │
         └─────────────────────┴─────────────────────┘
                               │
                          PERFORMANCE
                               │
                ┌──────────────┼──────────────┐
                │              │              │
             Speedup       Efficiency      Bottlenecks
                │              │              │
           Amdahl's Law    Overhead         I/O
                                          Memory
                                          Network
                                          Sync
                                          Load imbalance

Theme

Don’t automatically solve performance problems by buying more hardware. First understand whether the software, data, tasks, or algorithm can be parallelized and optimized.

System optimisation broadly divided into:

1. Hardware-based optimization
   • CPU
   • GPU
   • TPU
   • More cores/processors
   • Memory and storage considerations
2. Software/algorithm-based optimization
   1. Data-level parallelism
   2. Task-level parallelism
   3. Algorithm-specific parallelism

Amdahl’s Law and Speedup

This was one of the important foundations.

a program is made of:

• Parallelizable portion
• Serial/non-parallelizable portion

For example, if 80% of a workload can be parallelized:

• Parallel portion = 80%
• Serial portion = 20%

Adding processors does not mean you get unlimited/linear speedup because that 20% serial component remains.

The concept is essentially:

Speedup(N)=1 / [(1−P)+P/N]​

where:

• P = fraction that can be parallelized
• N = number of processors

Important takeaway

Parallelism(adding processors) has diminishing returns.

Even if you add 100 processors, the serial portion, communication, synchronization and other overheads prevent perfect scaling.

Below is detailed three forms of parallelism.

Data-level parallelism

Same operation : different pieces of data.

Example:

1 billion records
Processor 1 → records 1–50M
Processor 2 → records 50M–100M
Processor 3 → records 100M–150M
...

Example 2 :

Image 1 ──┐
Image 2 ──┤
Image 3 ──┤
… ├──> Same convolution operation
Image 128 ─┘

Every processor performs the same operation on its own data.

GPU – Instead of one extremely powerful processor, you have a huge number of relatively simple processing units doing work concurrently.

The key principle:

GPU acceleration works especially well when the workload has massive data-level parallelism.

Ideal complexity

If: Tserial​=O(N) and you have P processors: T(parallel​)≈O(N/P)

In the ideal case where: P=N

you theoretically approach: O(1)

this is an ideal case, not something you should expect in real systems.

I/O and memory bottlenecks

prefetching as one way of addressing I/O-related waiting.

The cooking analogy was used:

Serial:
Cook → wait → ingredient      
→ wait → ingredient      
→ wait → ingredient

Parallel/prepared:
Cooking  +
ingredient preparation  +
other activities

The idea was to keep the expensive processor/workflow busy rather than waiting unnecessarily.

Task-level parallelism

Different tasks – executed simultaneously.

Example:

Task 1 → calculate mean
Task 2 → calculate median
Task 3 → calculate mode

If they are independent, they can execute concurrently.

Parallel efficiency

The professor introduced efficiency approximately as: E(N)=S(N)/N​

where:

• S(N) = speedup
• N = number of processors

Ideal: E=1

or 100%.

Real systems are lower because of:

• Serial work
• Communication
• Synchronization
• Load imbalance
• Memory/I/O
• Scheduling overhead

Achieving something like 92–94% efficiency can be a very good practical result

Algorithm-specific parallelism

Instead of simply splitting data/tasks, redesign the algorithm itself so that more of its work can execute concurrently.

Examples discussed:

• Divide and conquer
• Merge sort
• Matrix multiplication
• Strassen’s algorithm
• Recursive decomposition
• FFT-type decomposition

This is the most algorithmically interesting part of the lecture.

Strassen’s Algorithm

You can change the algorithm to reduce the amount of expensive computation and expose parallelism.

Trade-offs of Strassen

The professor also pointed out that optimization isn’t free.

Strassen:

Advantages

• Fewer matrix multiplications
• Better asymptotic complexity
• Exposes recursive parallelism

Costs

• More matrix additions
• More temporary storage
• More complicated memory access

This is an important engineering lesson:

Optimizing one resource can make another resource worse.

Calculations (rearrange below)

Speedup

S=Tparallel​/Tserial​​

Efficiency

E=N/S​

Amdahl’s Law

S(N)=(1−P)+P/N1​

Data-parallel ideal time

Tparallel​≈NT​

Sequential tasks

Tserial​=T1​+T2​+…+Tn​

Independent parallel tasks

Approximately: Tparallel​=max(T1​,T2​,…,Tn​)

for one parallel stage.

Dependent task

If:

T1 ──┐     ├──> T3T2 ──┘

then: T=Tparallel−stage​+T3​

Q- a numercial