# Energy-Aware Profit Maximizing Scheduling Algorithm for Heterogeneous Computing Systems

1Department of Electrical and Computer Engineering
2Department of Computer Science

Fort Collins, Colorado, USA

### Outline

• problem statement
• optimization problem formulation
• algorithm description
• results

## Problem Statement

• static scheduling
• task assigned to only one machine (task indivisibility)
• machine runs one task at a time
• known deterministic execution times
• large number of heterogeneous tasks and machines
• goal: maximize profit per time
• minimize operating cost (energy)
• minimize makespan: process the next bag-of-tasks after this one

## Introduction

• work has been done in minimizing
• execution time
• energy consumption
• reliability
• our focus is on maximizing profit
• important for businesses
• combines the makespan, energy, and other cost factors
• contributions
• monetary model for provider and client HPC
• algorithm to efficiently find
• maximum profit schedule
• bounds on profit

## Motivation

• software as a service (SaaS) providers maximize profits by increasing revenue and controlling costs
• example: SaaS web-based video trans-coding
• charges customers per minute of video converted
• task execution time is well known due to repetitive tasks executed by the provider
• objective: minimize cost of processing workload and process tasks as fast as possible

## Pareto Fronts

• energy and makespan optimization
• good for system operators
• does not provide a concrete decision space for automated schedulers
• need efficient algorithms for very large-scale systems

## Problem Formulation

• let $p$ be the price (revenue) per bag-of-tasks
• let $c$ be the cost per unit of energy
• let $E$ be the energy consumed
• let $MS$ be the makespan
• profit per bag-of-tasks is $p - c E$
• profit per unit time (to be maximized) is $\frac{p - c E}{\mathit{MS}} =$ $\frac{p}{\mathit{MS}}$ $- c$ $\frac{E}{\mathit{MS}}$
• revenue per unit time $-c$ times average power consumption

## Solution Approach

• computationally expensive to compute optimal solutions for
• minimizing makespan
• maximizing profit (function of makespan)
• need scalable and efficient algorithms to find good schedules
• proposed 3 phase algorithm:
• solve linear optimization problem assuming tasks are divisible
• round the solution
• assign tasks to machines

## Preliminaries

• simplifying approximation: each task is divisible among machines
• $T_i$ — number of tasks of type $i$
• $M_j$ — number of machines of type $j$
• $\ETC$ — estimated time to compute for a task of type $i$ running on a machine of type $j$
• $\mu_{ij}$ — number of tasks of type $i$ assigned to machines of type $j$
• matrix $\boldsymbol{\mu}$ is a resource allocation
• decision variable
• not binary but integer valued ($\mu_{ij} \gg 1$)
• finishing time of machine type $j$ is (lower bound) $$F_j = \frac{1}{M_j} \sum_i \mu_{ij} \ETC$$

## Energy and Power

• $\APC$ — average power consumption for a task of type $i$ running on a machine of type $j$
• $\ELB(\boldsymbol{\mu}) = \sum_i \sum_j \mu_{ij} \ETC \APC$
• in the paper $\ELB$ includes consideration of idle power
• let $P_\text{max}$ be the maximum average power consumption
• models long running average power consumption
• useful for modeling cooling capacity

## Optimization Problem

$$\underset{\boldsymbol{\mu},\,\MSLB}{\text{maximize}} \quad \frac{p - c \ELB(\boldsymbol{\mu})}{\MSLB} \\ \begin{array}{lll} \text{subject to:} & & \\ \forall i & \sum_j \mu_{ij} = T_i & \text{task constraint} \\ \forall j & F_j \le \MSLB & \text{machine finishing time constraint} \\ \forall i,j & \mu_{ij} \ge 0 & \text{assignments must be non-negative} \\ & \frac{\ELB}{\MSLB} \le P_\text{max} & \text{power constraint (optional)} \end{array}$$
• recall:
• $F_j$ is finishing time
• $\mu_{ij}$ is number of tasks

## Conversion to a Linear Program

• objective and power constraint are non-linear
• ratios of decision variables, $\mu_{ij}$ and $\MSLB$
• constraints can be converted to use ratios of $\mu_{ij}$ and $\MSLB$
• variable substitution
• $z_{ij} \leftarrow \frac{\mu_{ij}}{\MSLB}$ is the average tasks per unit time
• $r \leftarrow \frac{1}{\MSLB}$ is the number of bag-of-tasks per unit time
• average power consumption becomes $\bar{P} = \sum_i \sum_j z_{ij} \ETC \APC$

## Transformed Linear Program

### Non-Linear Problem

$$\underset{\boldsymbol{\mu},\,\MSLB}{\text{maximize}} \quad \frac{p - c \ELB(\boldsymbol{\mu})}{\MSLB} \\ \begin{array}{ll} \text{subject to:} & \\ \forall i & \sum_j \mu_{ij} = T_i \\ \forall j & F_j \le \MSLB \\ \forall i,j & \mu_{ij} \ge 0 \\ & \frac{\ELB}{\MSLB} \le P_\text{max} \end{array}$$

$$\implies$$

### Linear Problem

$$\underset{\boldsymbol{z},\,r}{\text{maximize}} \quad p r - c \bar{P} \\ \begin{array}{ll} \text{subject to:} &\\ \forall i & \sum_j z_{ij} = T_i r \\ \forall j & \frac{1}{M_j} \sum_i z_{ij} \ETC \le 1 \\ \forall i,j & z_{ij} \ge 0 \\ & r \ge 0 \\ & \bar{P} \le P_\text{max} \end{array}$$

## Algorithm

• solve linear program and compute
$\mu_{ij} = \frac{z_{ij}}{r}$ and $\MSLB = \frac{1}{r}$
• rounding algorithm (per task type)
• rounds the number of tasks of each type assigned to each machine type
• find nearest integer solution while satisfying constraints
• local assignment algorithm (per machine type)
• assign tasks to individual machines
• greedy algorithm to minimize makespan
• recall:
• $z_{ij}$ is average tasks per unit time
• $r$ is number of bag-of-tasks per unit time

## Bounds

• upper bound
• many Pareto efficient solutions to the relaxation of the energy and makespan optimization problem
• maximum profit of all those solutions

## Alternative Objective Formulation

• collapse $p$ and $c$ into a single intuitive parameter
• let $E_\text{min}$ be the energy of the minimum energy solution
• let profit ratio $\gamma = \frac{p}{c E_\text{min}}$
• $\gamma$ is unitless
• $\gamma \ge 0$ is realizable
• $\gamma > 1$ ⇒ positive profit is achievable
• recall:
• $p$ is price per bag-of-tasks
• $c$ is cost per unit of energy

## Simulation Setup

• heterogeneous tasks and machines
• 11,000 tasks each is one of 30 task types
• 360 machines each is one of 9 machine types

## Max Profit Solutions

### Sweeping Profit Ratio

Pareto front lower bound

## Max Profit Solutions

### Sweeping Profit Ratio

• recall: $\gamma = \frac{p}{c E_\text{min}}$ is the profit ratio

Pareto front lower bound

▢ profit upper bound (infeasible)

## Max Profit Solutions

### Sweeping Profit Ratio

• recall: $\gamma = \frac{p}{c E_\text{min}}$ is the profit ratio

Pareto front lower bound

▢ profit upper bound (infeasible)

◆ profit lower bound (feasible)

## Max Profit Solutions

### Sweeping Profit Ratio

• recall: $\gamma = \frac{p}{c E_\text{min}}$ is the profit ratio

Pareto front lower bound

▢ profit upper bound (infeasible)

◆ profit lower bound (feasible)

| profit per unit time

## Max Profit Solutions

### Sweeping Profit Ratio

• recall: $\gamma = \frac{p}{c E_\text{min}}$ is the profit ratio

Pareto front lower bound

▢ profit upper bound (infeasible)

◆ profit lower bound (feasible)

| profit per unit time

-- power constraint (55 KW)

## Profit Rate vs Makespan

• profit ratio = 1.2
• Pareto front generation: 173 ms

## Profit Rate vs Makespan

• profit ratio = 1.2
• Pareto front generation: 173 ms
• single max profit solve: 2 ms
• if 1 million tasks: 70 ms

## Relative Profit Rate vs Number of Tasks

• 100 Monte Carlo runs sampling over the task types
• relative decrease in profit = $100 \frac{\mathit{profit}_\text{DL} - \mathit{profit}_\text{full}}{\mathit{profit}_\text{DL}}$
• width of glyphs represent the probability density

## Finishing Times

profit ratio = 1.2

profit ratio = 1.5

• machine type 1 and 2 are less power efficient
• use when price is high thus emphasizing makespan minimization

## Applicability

• millions of tasks and tens of thousands of machines
• scheduler execution times are sub-second
• online batch mode scheduling for uncertain
• execution times
• arrival rates
• schedule to cores instead of machines

## Conclusions

• fast profit maximizing scheduling algorithm
• scalable to very large systems
• provides tight lower and upper bounds on the profit per unit time
• easily applied to online batch mode scheduling

/