Is this a BUG REPORT or FEATURE REQUEST?:
/kind feature

Today, kube-scheduler checks feasibility of all of the nodes in a cluster for every pod in every scheduling attempt. All of those feasible pods are then scored. Our performance data shows that 90th percentile of running predicate and priority functions takes about 30ms per pod and 99th percentile is as high as 60ms/pod.

We would like to build a feature in the scheduler that once the scheduler finds a certain number of feasible nodes in a cluster, it stops and passes those nodes for scoring. This can help improve the scheduler's performance.
Such a feature must ensure that nodes from various regions and zones are considered for each pod. It must also avoid considering the same set of nodes every time, for example, it should avoid trying the first 100 nodes every time. It must instead try to consider various nodes of the cluster in different scheduling cycles.

Today, kube-scheduler checks all the feasible nodes and picks the highest score in the whole cluster. Once this feature is built, the chosen node may not be the best node in the whole cluster. The chosen node will be the highest score among those nodes found feasible.

/sig scheduling
/assign