Runtime Prediction Engine

[aalhadsawane]

Problem

We need to schedule a batch of functions across a heterogeneous cluster such that total batch runtime (makespan) is minimized.

To make good scheduling decisions, we must predict runtime for a given (function, machine) pair.

Challenge:

• Historical runtime data is sparse.
• Many (function, machine) combinations will not have prior observations.
• Machines are highly heterogeneous.
• Functions have different sensitivities to CPU, memory bandwidth, and network bandwidth.
• Input size is assumed fixed and does not affect runtime prediction.

Available Signals

We can benchmark both functions and machines.

Function profiling (on Benchmarking Environment Machine - BEM)

We estimate total resource demand per function:

• CPU demand in total cycles
• memory demand in MB
• network demand as total data transfer (MB)

We also estimate resource sensitivity weights for each function by throttling:

• CPU cycles
• memory bandwidth
• network bandwidth

This allows us to understand how strongly runtime depends on each resource dimension.

Machine profiling

We benchmark each machine to obtain:

• CPU performance (cycles per second)
• memory bandwidth (MB/s)
• network bandwidth (MB/s)
• relative performance normalized to the BEM

Historical runtime observations

When available, we have runtime samples for specific (function, machine) pairs.

These can be used via:

• linear moving average
• exponential moving average
• variance-aware smoothing

Historical data is often sparse but may still help improve prediction accuracy.

Goal

Design a prediction model that:

• predicts runtime for unseen (function, machine) pairs
• leverages benchmarking data
• incorporates historical data when available
• handles heterogeneous machines
• produces sufficiently accurate estimates for scheduling decisions

We are evaluating:

• pure ML models using function + machine features
• hybrid models combining ML prediction with historical moving averages
• approaches that dynamically weight empirical vs predicted runtime based on confidence

At the same time, we also must account for the latency and overhead of the model.