[YUNIKORN-21] Optimize node sorting algorithms

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Duplicate
• Fix Version/s: 0.12.1
• Component/s: core - scheduler
• Labels: pull-request-available
• Target Version: 0.12.1
• Assignee: Unassigned
• Reporter: Wangda Tan
• Created: 04/Mar/20 11:49
• Updated: 21/Jan/22 21:48
• Resolved: 28/Sep/21 17:16

Description

Currently, we're using DominantRatio for the node sorting algorithm

func CompUsageShares(left, right *Resource) int {
 lshares := getShares(left,nil) rshares := getShares(right,nil)
 return compareShares(lshares, rshares) 
}

Which is not good, two reasons:

1. Dominate resource compare is about 8X more expensive than single float compares for two resource types.

1. Dominate resource is not stable when we have scarce resource types like GPU. A node with 192GB mem, 32 vcores, and 1 GPU available, compared to 168GB mem, 64 vcore and 8 GPU available; the prior one can go first because of the following logic:

if total == nil || total.Resources[k] == 0 {
 // negative share is logged
 if v < 0 {
  log.Logger().Debug("usage is negative no total, share is also negative", zap.Int64("resource quantity", int64(v))) 
 }
 shares[idx] = float64(v) idx++ continue
}

I think we should discard dominate resource compare for node resource. Instead, we just use one resource type (like vcores) to compare available resource.

Issue Links

• is related to: YUNIKORN-807 Improve performance of node sorting
• is superceded by: YUNIKORN-847 Use resource weighting for node sorting
• relates to: YUNIKORN-780 Refactor node sorting policies into separate implementations
• links to: GitHub Pull Request #139