<commit_before>---
title: Resource Bin Packing Priority Function
  - "@sudeshsh"
owning-sig: sig-scheduling
participating-sigs:
  - sig-scheduling
reviewers:
  - "@k82cn"
  - "@Huang-Wei"
approvers:
  - "@k82cn"
creation-date: 2019-03-11
last-updated: 2019-03-11
status: provisional
---

# Resource Bin Packing Priority Function

## Table of Contents

- [Summary](#summary)
- [Motivation](#motivation)
  - [Goals](#goals)
  - [Non-Goals](#non-goals)
- [Proposal](#proposal)
  - [User Stories](#user-stories)
    - [Story 1](#story-1)
- [Design Details](#design-details)
  - [Examples](#examples)
  - [Test Plan](#test-plan)
  - [Graduation Criteria](#graduation-criteria)
- [Implementation History](#implementation-history)

## Summary

Resource Bin Packing Priority Function allows users to use the best fit polices during scheduling. It allows users to apply [bin packing](https://en.wikipedia.org/wiki/Bin_packing_problem) on core resources like CPU, Memory as well as extended resources like accelerators.

## Motivation

While running Machine Learning workloads on kubernetes which use accelerator devices the default scheduler spreads pods across nodes resulting in fragmentation of extended resources. This fragmentation prevents scheduling pods with larger device resource requirements, and they remain in pending state.

### Goals

- Schedule Jobs using BestFit Policy using Resource Bin Packing Priority Function
- Reduce Fragmentation of scarce resources on the Cluster

### Non-Goals

-

## Proposal

The plan is to modify  `requested_to_capacity_ratio` priority function to support an additional priority function `resource_bin_packing` along with `most_requested` and `least_requested`. Add another argument resources of type `map[v1.ResourceName]int64{}` .This would allow users who want to bin pack a resource to use the function by setting the argument resources which would require them to specify weights for bin packing. For example

```yaml
"priorities": [
    ... {
        "name": "ResourceBinPackingPriority",
        "weight": 5,
        "argument": {
            "resourceBinPacking": {
                "resources": [{
                    "resource": "intel.com/foo",
                    "weight": 5
                }, {
                    "resource": "intel.com/bar",
                    "weight": 2
                }, {
                    "resource": "cpu",
                    "weight": 1
                }]
            }
        }
    ],

```

The node score would be calculated as (requested+used) / available. The weights would be used to calculate the resulting node score in the following way.

```go
resources := make(map[v1.ResourceName]weight)
nodeScore := 0
weightSum := 0
for resource, weight := range resources {
  nodeScore += ((requested[resource]+ used[resource])/available[resource]) * weight
  weightSum += weight
}
nodeScore = (nodeScore / weightSum)* 10
```

### User Stories

#### Story 1

Let's consider a cluster with `intel.com/foo` as a scarce resource. A user needs to submit 3 `jobs` with specs as shown below

![Test Scenario](20190311-resource_bin_packing_priority_function_scenario.png)

#### Default Behavior

The default scheduler in most cases will schedule the Jobs as follows as there is no priority function for an extended resource for bin packing.

![Default Behavior](20190311-resource_bin_packing_priority_function_default.png)

#### Extender Resource Scheduler Behavior

The Scheduler should submit the 2 resource job on Node 3 as the utilization is higher. This would reduce the fragmentation of extended resource and reduce jobs in the pending state.

![Extended Scheduler Behavior](20190311-resource_bin_packing_priority_function_extended.png)

<commit_msg>Addressing comments<commit_after>---
title: Extending RequestedToCapacityRatio Priority Function to support Resource Bin Packing of Extended Resources
  - "@sudeshsh"
owning-sig: sig-scheduling
participating-sigs:
  - sig-scheduling
reviewers:
  - "@k82cn"
  - "@Huang-Wei"
  - "@bsalamat"
approvers:
  - "@k82cn"
  - "@bsalamat"
creation-date: 2019-03-11
last-updated: 2019-03-11
status: provisional
---

# ExtendingRequestedToCapacityRatio Priority Function to support Resource Bin Packing of Extended Resources

## Table of Contents

- [Summary](#summary)
- [Motivation](#motivation)
  - [Goals](#goals)
  - [Non-Goals](#non-goals)
- [Proposal](#proposal)
  - [User Stories](#user-stories)
    - [Story 1](#story-1)
- [Design Details](#design-details)
  - [Examples](#examples)
  - [Test Plan](#test-plan)
  - [Graduation Criteria](#graduation-criteria)
- [Implementation History](#implementation-history)

## Summary

Extend RequestedToCapacityRatio Priority Function to allow users to use the best fit polices during scheduling. It will allow users to apply [bin packing](https://en.wikipedia.org/wiki/Bin_packing_problem) on core resources like CPU, Memory as well as extended resources like accelerators.

## Motivation

While running workloads on kubernetes which use accelerator devices the default scheduler spreads pods across nodes resulting in fragmentation of extended resources. This fragmentation prevents scheduling pods with larger device resource requirements, and they remain in the pending state.

### Goals

- Schedule Jobs using BestFit Policy using RequestedToCapacityRatio Priority Function for extended Resources
- Reduce Fragmentation of scarce resources on the Cluster

### Non-Goals

-

## Proposal

The plan is to modify  `requested_to_capacity_ratio` priority function to support `resource_bin_packing` of extended resources. Add another argument `resources` of type `map[v1.ResourceName]int64{}` .This would allow users who want to bin pack a resource to use the function by setting the argument resources which would require them to specify weights for bin packing. For example

```yaml
"priorities": [
   ...{
      "name":"RequestedToCapacityRatioPriority",
      "weight":5,
      "argument":{
         "requestedToCapacityRatioArguments":{
            "shape":[
               {
                  "utilization":100,
                  "score":10
               },
               {
                  "utilization":0,
                  "score":0
               }
            ],
            "resources":[
               {
                  "resource":"intel.com/foo",
                  "weight":5
               },
               {
                  "resource":"intel.com/bar",
                  "weight":2
               },
               {
                  "resource":"cpu",
                  "weight":1
               }
            ]
         }
      }
   }
]
```

The argument `resources` is optional and by default will be set to the value

```go
resources := map[v1.ResourceName]int64{
  v1.ResourceMemory : 1,
  v1.ResourceCPU    : 1,
}
```

### Argument Input Scenarios

1. If the resource does not exist the score for that resources defaults to 0
2. As we are storing resources as a map there can be a single weight for every resource type.
3. Negative weights are not allowed, this would be filtered inside the function and an appropriate error would be thrown.


### Design Details

The node score would be calculated as (podRequest + requested) / allocatable. The weights would be used to calculate the resulting node score in the following way.

```go
resources := make(map[v1.ResourceName]weight)
nodeScore := 0
weightSum := 0
for resource, weight := range resources {
  nodeScore += ((podRequest[resource]+ requested[resource])/allocatable[resource]) * weight
  weightSum += weight
}
nodeScore = (nodeScore / weightSum)* 10
```

Update the  function `buildRequestedToCapacityRatioScorerFunction` defination as

```go
func buildRequestedToCapacityRatioScorerFunction(scoringFunctionShape FunctionShape, resources []Resources) func(nodeInfo *schedulercache.NodeInfo) int64
```


### User Stories

#### Story 1

Let's consider a cluster with `intel.com/foo` as a scarce resource. A user needs to submit 3 `jobs` with specs as shown below

![Test Scenario](20190311-resource_bin_packing_priority_function_scenario.png)

#### Default Behavior

The default scheduler in most cases will schedule the Pods as follows as there is no priority function for an extended resource for bin packing.

![Default Behavior](20190311-resource_bin_packing_priority_function_default.png)

#### Extender Resource Scheduler Behavior

The Scheduler should submit the 2 resource job on Node 3 as the utilization is higher. This would reduce the fragmentation of extended resource and reduce pods in the pending state.

![Extended Scheduler Behavior](20190311-resource_bin_packing_priority_function_extended.png)


{'fraction_non_alphanumeric': 0.09150703900300024, 'fraction_numerical': 0.01661666282021694, 'mean_word_length': 3.3972602739726026, 'pattern_counts': {'":': 29, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '376592', 'n_tokens_mistral': 2492, 'n_tokens_neox': 2234, 'n_words': 842}