[RFC PATCH 00/13] sched: Integrating Per-entity-load-tracking with the core scheduler

[RFC PATCH 00/13] sched: Integrating Per-entity-load-tracking with the core scheduler

[Preeti U Murthy]

This patchset uses the per-entity-load-tracking patchset which will soon be
available in the kernel.It is based on the tip/master tree before the
(HEAD at b654f92c06e562c)integration of per-entity-load-tracking patchset.
The first 8 latest patches of sched:per-entity-load-tracking alone have
been imported to the tree from the quilt series of Peter(when they were
present) to avoid the complexities of task groups and to hold back the
optimizations of this patchset for now.This patchset is based at this level.
Refer https://lkml.org/lkml/2012/10/12/9.This series is a continuation
of the patchset in this link.

This patchset is an attempt to begin the integration of PJT's
metric with the load balancer in a step wise fashion,and progress based
on the consequences.This patchset has been tested with the config excluding
CONFIG_FAIR_GROUP_SCHED.

The following issues have been considered towards this:
[NOTE:an x% task referred to in the logs and below is calculated over a
duty cycle of 10ms.]

1.Consider a scenario,where there are two 10% tasks running on a cpu.The
  present code will consider the load on this queue to be 2048,while
  using PJT's metric the load is calculated to be <1000,rarely exceeding this
  limit.Although the tasks are not contributing much to the cpu load,they are
  decided to be moved by the scheduler.

  But one could argue that 'not moving one of these tasks could throttle
  them.If there was an idle cpu,perhaps we could have moved them'.While the
  power save mode would have been fine with not moving the task,the
  performance mode would prefer not to throttle the tasks.We could strive
  to strike a balance by making this decision tunable with certain parameters.
  This patchset includes such tunables.This issue is addressed in Patch[1/2].

  *The advantage of this behavior of PJT's metric has been demonstrated via
   an experiment*.Please see the reply to this cover letter to be posted right
   away.

2.We need to be able to do this cautiously,as the scheduler code is too
  complex.This patchset is an attempt to begin the integration of PJT's
  metric with the load balancer in a step wise fashion,and progress based on
  the consequences.
  *What this patchset essentially does is in two primary places of the
   scheduler,PJT's metric has replaced the existing metric to make decisions for load
   balancing*.
  1.load_balance()
  2.select_task_rq_fair()

  This description of the patches are below:

         Patch[1/13]: This patch aims at detecting short running tasks and
	 prevent their movement.In update_sg_lb_stats,dismiss a sched group
         as a candidate for load balancing,if load calculated by PJT's metric
	 says that the average load on the sched_group <= 1024+(.15*1024).
	 This is a tunable,which can be varied after sufficient experiments.

         Patch[2/13]:In the current scheduler greater load would be analogous
         to more number of tasks.Therefore when the busiest group is picked
         from the sched domain in update_sd_lb_stats,only the loads of the
         groups are compared between them.If we were to use PJT's metric,a
         higher load does not necessarily mean more number of tasks.This
	 patch addresses this issue.

	 Patch[3/13] to Patch[13/13] : Replacement of the existing metrics
	 deciding load balancing and selecting a runqueue for load
         placement,with the PJT's metric and subsequent usage of PJT's metric
         for schduling.

3.The Primary advantage that I see in integrating PJT's metric with the core
  scheduler is listed below:

  1. Excluding short running tasks from being candidates for load balancing.
     This would avoid unnecessary migrations when the CPU is not sufficiently
     loaded.This advantage has been portrayed in the results of the
     experiment.

     Run the workload attached.There are 8 threads spwaned each being 10%
     tasks.
     The number of migrations was measured from /proc/schedstat

     Machine: 1 socket 4 core pre-nehalem.

     Experimental Setup:
     cat /proc/schedstat > stat_initial
     gcc -Wall -Wshadow -lpthread  -o test test.c
     cat /proc/schedstat > stat_final
     The difference in the number of pull requests from both these files have
     been calculated and are as below:

     Observations:
					With_Patchset	Without_patchset
     ---------------------------------------------------------------------
     Average_number_of_migrations	    0		 46
     Average_number_of_records/s          9,71,114	9,45,158

  With more memory intensive workloads, a higher difference in the number of
  migrations is seen without any performance compromise.

---

Preeti U Murthy (13):
      sched:Prevent movement of short running tasks during load balancing
      sched:Pick the apt busy sched group during load balancing
      sched:Decide whether there be transfer of loads based on the PJT's metric
      sched:Decide group_imb using PJT's metric
      sched:Calculate imbalance using PJT's metric
      sched:Changing find_busiest_queue to use PJT's metric
      sched:Change move_tasks to use PJT's metric
      sched:Some miscallaneous changes in load_balance
      sched:Modify check_asym_packing to use PJT's metric
      sched:Modify fix_small_imbalance to use PJT's metric
      sched:Modify find_idlest_group to use PJT's metric
      sched:Modify find_idlest_cpu to use PJT's metric
      sched:Modifying wake_affine to use PJT's metric


 kernel/sched/fair.c |  262 ++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 186 insertions(+), 76 deletions(-)

-- 
Preeti U Murthy

[RFC PATCH 01/13] sched:Prevent movement of short running tasks during load balancing

[Preeti U Murthy]

Prevent sched groups with low load as tracked by PJT's metrics
from being candidates of the load balance routine.This metric is chosen to be
1024+15%*1024.But using PJT's metrics it has been observed that even when
three 10% tasks are running,the load sometimes does not exceed this
threshold.The call should be taken if the tasks can afford to be throttled.

This is why an additional metric has been included,which can determine how
long we can tolerate tasks not being moved even if the load is low.

Signed-off-by:  Preeti U Murthy <preeti@linux.vnet.ibm.com>
---
 kernel/sched/fair.c |   16 ++++++++++++++++
 1 file changed, 16 insertions(+)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index dbddcf6..e02dad4 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4188,6 +4188,7 @@ struct sd_lb_stats {
  */
 struct sg_lb_stats {
 	unsigned long avg_load; /*Avg load across the CPUs of the group */
+	u64 avg_cfs_runnable_load; /* Equivalent of avg_load but calculated using PJT's metric */
 	unsigned long group_load; /* Total load over the CPUs of the group */
 	unsigned long sum_nr_running; /* Nr tasks running in the group */
 	unsigned long sum_weighted_load; /* Weighted load of group's tasks */
@@ -4504,6 +4505,7 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 	unsigned long load, max_cpu_load, min_cpu_load;
 	unsigned int balance_cpu = -1, first_idle_cpu = 0;
 	unsigned long avg_load_per_task = 0;
+	u64 group_load = 0; /* computed using PJT's metric */
 	int i;
 
 	if (local_group)
@@ -4548,6 +4550,7 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 		if (idle_cpu(i))
 			sgs->idle_cpus++;
 
+		group_load += cpu_rq(i)->cfs.runnable_load_avg;
 		update_sg_numa_stats(sgs, rq);
 	}
 
@@ -4572,6 +4575,19 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 	sgs->avg_load = (sgs->group_load*SCHED_POWER_SCALE) / group->sgp->power;
 
 	/*
+	 * Check if the sched group has not crossed the threshold.
+	 *
+	 * Also check if the sched_group although being within the threshold,is not
+	 * queueing too many tasks.If yes to both,then make it an
+	 * invalid candidate for load balancing
+	 *
+	 * The below condition is included as a tunable to meet performance and power needs
+	 */
+	sgs->avg_cfs_runnable_load = (group_load * SCHED_POWER_SCALE) / group->sgp->power;
+	if (sgs->avg_cfs_runnable_load <= 1178 && sgs->sum_nr_running <= 2)
+		sgs->avg_cfs_runnable_load = 0;
+
+	/*
 	 * Consider the group unbalanced when the imbalance is larger
 	 * than the average weight of a task.
 	 *

[RFC PATCH 02/13] sched:Pick the apt busy sched group during load balancing

[Preeti U Murthy]

If a sched group has passed the test for sufficient load in
update_sg_lb_stats,to qualify for load balancing,then PJT's
metrics has to be used to qualify the right sched group as the busiest group.

The scenario which led to this patch is shown below:
Consider Task1 and Task2 to be a long running task
and Tasks 3,4,5,6 to be short running tasks

			Task3
			Task4
Task1			Task5
Task2			Task6
------			------
SCHED_GRP1		SCHED_GRP2

Normal load calculator would qualify SCHED_GRP2 as
the candidate for sd->busiest due to the following loads
that it calculates.

SCHED_GRP1:2048
SCHED_GRP2:4096

Load calculator would probably qualify SCHED_GRP1 as the candidate
for sd->busiest due to the following loads that it calculates

SCHED_GRP1:3200
SCHED_GRP2:1156

This patch aims to strike a balance between the loads of the
group and the number of tasks running on the group to decide the
busiest group in the sched_domain.

This means we will need to use the PJT's metrics but with an
additional constraint.

Signed-off-by: Preeti U Murthy <preeti@linux.vnet.ibm.com>
---
 kernel/sched/fair.c |   25 ++++++++++++++++++++++---
 1 file changed, 22 insertions(+), 3 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index e02dad4..aafa3c1 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -165,7 +165,8 @@ void sched_init_granularity(void)
 #else
 # define WMULT_CONST	(1UL << 32)
 #endif
-
+#define NR_THRESHOLD 2
+#define LOAD_THRESHOLD 1
 #define WMULT_SHIFT	32
 
 /*
@@ -4169,6 +4170,7 @@ struct sd_lb_stats {
 	/* Statistics of the busiest group */
 	unsigned int  busiest_idle_cpus;
 	unsigned long max_load;
+	u64 max_sg_load; /* Equivalent of max_load but calculated using pjt's metric*/
 	unsigned long busiest_load_per_task;
 	unsigned long busiest_nr_running;
 	unsigned long busiest_group_capacity;
@@ -4628,8 +4630,24 @@ static bool update_sd_pick_busiest(struct lb_env *env,
 				   struct sched_group *sg,
 				   struct sg_lb_stats *sgs)
 {
-	if (sgs->avg_load <= sds->max_load)
-		return false;
+	/* Use PJT's metrics to qualify a sched_group as busy
+ 	 *
+ 	 * But a low load sched group may be queueing up many tasks
+ 	 * So before dismissing a sched group with lesser load,ensure
+ 	 * that the number of processes on it is checked if it is
+ 	 * not too less loaded than the max load so far
+ 	 *
+ 	 * But as of now as LOAD_THRESHOLD is 1,this check is a nop.
+ 	 * But we could vary LOAD_THRESHOLD suitably to bring in this check
+ 	 */
+	if (sgs->avg_cfs_runnable_load <= sds->max_sg_load) {
+		if (sgs->avg_cfs_runnable_load > LOAD_THRESHOLD * sds->max_sg_load) {
+			if (sgs->sum_nr_running <= (NR_THRESHOLD + sds->busiest_nr_running))
+				return false;
+		} else {
+			return false;
+		}
+	}
 
 	if (sgs->sum_nr_running > sgs->group_capacity)
 		return true;
@@ -4708,6 +4726,7 @@ static inline void update_sd_lb_stats(struct lb_env *env,
 			sds->this_idle_cpus = sgs.idle_cpus;
 		} else if (update_sd_pick_busiest(env, sds, sg, &sgs)) {
 			sds->max_load = sgs.avg_load;
+			sds->max_sg_load = sgs.avg_cfs_runnable_load;
 			sds->busiest = sg;
 			sds->busiest_nr_running = sgs.sum_nr_running;
 			sds->busiest_idle_cpus = sgs.idle_cpus;

[RFC PATCH 03/13] sched:Decide whether there be transfer of loads based on the PJT's metric

[Preeti U Murthy]

Additional parameters relevant to sched group load balancing statistics and
sched domain's load balancing statistics which are calculated using the per
entity load tracking are used.

The intention is to begin to use PJT's metric in the first level of load
balancing to see if the current sched group is capable of pulling tasks upon itself.

Signed-off-by: Preeti U Murthy <preeti@linux.vnet.ibm.com>
---
 kernel/sched/fair.c |   33 +++++++++++++++++++++++++--------
 1 file changed, 25 insertions(+), 8 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index aafa3c1..67a916d 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4157,12 +4157,16 @@ struct sd_lb_stats {
 	struct sched_group *busiest; /* Busiest group in this sd */
 	struct sched_group *this;  /* Local group in this sd */
 	unsigned long total_load;  /* Total load of all groups in sd */
+	u64 total_sgs_load;	 /* Equivalent to total_load except using PJT's metrics */
 	unsigned long total_pwr;   /*	Total power of all groups in sd */
 	unsigned long avg_load;	   /* Average load across all groups in sd */
+	u64 avg_sgs_load;	  /* Equivalent to avg_load but calculated with PJT's metrics */
 
 	/** Statistics of this group */
 	unsigned long this_load;
+	u64 this_sg_load;	/* Equivalent to this_load but calculated using PJT's metric*/
 	unsigned long this_load_per_task;
+	u64 this_sg_load_per_task; /* Equivalent to this_load_per_task but using PJT's metric*/
 	unsigned long this_nr_running;
 	unsigned long this_has_capacity;
 	unsigned int  this_idle_cpus;
@@ -4170,8 +4174,9 @@ struct sd_lb_stats {
 	/* Statistics of the busiest group */
 	unsigned int  busiest_idle_cpus;
 	unsigned long max_load;
-	u64 max_sg_load; /* Equivalent of max_load but calculated using pjt's metric*/
+	u64 max_sg_load; /* Equivalent of max_load but calculated using PJT's metric*/
 	unsigned long busiest_load_per_task;
+	u64 busiest_sg_load_per_task; /*Equivalent of busiest_load_per_task but using PJT's metric*/
 	unsigned long busiest_nr_running;
 	unsigned long busiest_group_capacity;
 	unsigned long busiest_has_capacity;
@@ -4192,6 +4197,7 @@ struct sg_lb_stats {
 	unsigned long avg_load; /*Avg load across the CPUs of the group */
 	u64 avg_cfs_runnable_load; /* Equivalent of avg_load but calculated using PJT's metric */
 	unsigned long group_load; /* Total load over the CPUs of the group */
+	u64 group_cfs_runnable_load; /* Equivalent of group_load but calculated using PJT's metric */
 	unsigned long sum_nr_running; /* Nr tasks running in the group */
 	unsigned long sum_weighted_load; /* Weighted load of group's tasks */
 	unsigned long group_capacity;
@@ -4507,7 +4513,6 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 	unsigned long load, max_cpu_load, min_cpu_load;
 	unsigned int balance_cpu = -1, first_idle_cpu = 0;
 	unsigned long avg_load_per_task = 0;
-	u64 group_load = 0; /* computed using PJT's metric */
 	int i;
 
 	if (local_group)
@@ -4552,7 +4557,8 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 		if (idle_cpu(i))
 			sgs->idle_cpus++;
 
-		group_load += cpu_rq(i)->cfs.runnable_load_avg;
+		/* Tracking load using PJT's metric */
+		sgs->group_cfs_runnable_load += cpu_rq(i)->cfs.runnable_load_avg;
 		update_sg_numa_stats(sgs, rq);
 	}
 
@@ -4585,8 +4591,8 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 	 *
 	 * The below condition is included as a tunable to meet performance and power needs
 	 */
-	sgs->avg_cfs_runnable_load = (group_load * SCHED_POWER_SCALE) / group->sgp->power;
-	if (sgs->avg_cfs_runnable_load <= 1178 && sgs->sum_nr_running <= 2)
+	sgs->avg_cfs_runnable_load = (sgs->group_cfs_runnable_load * SCHED_POWER_SCALE) / group->sgp->power;
+	if (sgs->avg_cfs_runnable_load <= 1178 && sgs->sum_nr_running <= 2 && !local_group)
 		sgs->avg_cfs_runnable_load = 0;
 
 	/*
@@ -4702,6 +4708,8 @@ static inline void update_sd_lb_stats(struct lb_env *env,
 			return;
 
 		sds->total_load += sgs.group_load;
+		/* Tracking load using PJT's metrics */
+		sds->total_sgs_load += sgs.group_cfs_runnable_load;
 		sds->total_pwr += sg->sgp->power;
 
 		/*
@@ -4719,9 +4727,11 @@ static inline void update_sd_lb_stats(struct lb_env *env,
 
 		if (local_group) {
 			sds->this_load = sgs.avg_load;
+			sds->this_sg_load = sgs.avg_cfs_runnable_load;
 			sds->this = sg;
 			sds->this_nr_running = sgs.sum_nr_running;
 			sds->this_load_per_task = sgs.sum_weighted_load;
+			sds->this_sg_load_per_task = sgs.group_cfs_runnable_load;
 			sds->this_has_capacity = sgs.group_has_capacity;
 			sds->this_idle_cpus = sgs.idle_cpus;
 		} else if (update_sd_pick_busiest(env, sds, sg, &sgs)) {
@@ -4732,6 +4742,7 @@ static inline void update_sd_lb_stats(struct lb_env *env,
 			sds->busiest_idle_cpus = sgs.idle_cpus;
 			sds->busiest_group_capacity = sgs.group_capacity;
 			sds->busiest_load_per_task = sgs.sum_weighted_load;
+			sds->busiest_sg_load_per_task = sgs.group_cfs_runnable_load;
 			sds->busiest_has_capacity = sgs.group_has_capacity;
 			sds->busiest_group_weight = sgs.group_weight;
 			sds->group_imb = sgs.group_imb;
@@ -4972,6 +4983,7 @@ find_busiest_group(struct lb_env *env, int *balance)
 		goto out_balanced;
 
 	sds.avg_load = (SCHED_POWER_SCALE * sds.total_load) / sds.total_pwr;
+	sds.avg_sgs_load = (SCHED_POWER_SCALE * sds.total_sgs_load) / sds.total_pwr;
 
 	/*
 	 * If the busiest group is imbalanced the below checks don't
@@ -4990,14 +5002,16 @@ find_busiest_group(struct lb_env *env, int *balance)
 	 * If the local group is more busy than the selected busiest group
 	 * don't try and pull any tasks.
 	 */
-	if (sds.this_load >= sds.max_load)
+	/* The following metrics has been changed to test PJT's metric */
+	if (sds.this_sg_load >= sds.max_sg_load)
 		goto out_balanced;
 
 	/*
 	 * Don't pull any tasks if this group is already above the domain
 	 * average load.
 	 */
-	if (sds.this_load >= sds.avg_load)
+	/* The following metrics has been changed to test PJT's metric */
+	if (sds.this_sg_load >= sds.avg_sgs_load)
 		goto out_balanced;
 
 	if (env->idle == CPU_IDLE) {
@@ -5015,7 +5029,10 @@ find_busiest_group(struct lb_env *env, int *balance)
 		 * In the CPU_NEWLY_IDLE, CPU_NOT_IDLE cases, use
 		 * imbalance_pct to be conservative.
 		 */
-		if (100 * sds.max_load <= env->sd->imbalance_pct * sds.this_load)
+		/* The following metrics has been changed to test PJT's
+		 * metric
+		 */
+		if (100 * sds.max_sg_load <= env->sd->imbalance_pct * sds.this_sg_load)
 			goto out_balanced;
 	}
 

[RFC PATCH 04/13] sched:Decide group_imb using PJT's metric

[Preeti U Murthy]

Additional parameters for deciding a sched group's imbalance status
which are calculated using the per entity load tracking are used.

Signed-off-by: Preeti U Murthy <preeti@linux.vnet.ibm.com>
---
 kernel/sched/fair.c |   22 ++++++++++++++++++++--
 1 file changed, 20 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 67a916d..77363c6 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -3748,6 +3748,7 @@ struct lb_env {
 	int			new_dst_cpu;
 	enum cpu_idle_type	idle;
 	long			imbalance;
+	long long               load_imbalance; /* PJT metric equivalent of imbalance */
 	/* The set of CPUs under consideration for load-balancing */
 	struct cpumask		*cpus;
 
@@ -4513,6 +4514,11 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 	unsigned long load, max_cpu_load, min_cpu_load;
 	unsigned int balance_cpu = -1, first_idle_cpu = 0;
 	unsigned long avg_load_per_task = 0;
+
+	/* Decide imb based on PJT's metric */
+	u64 cpu_runnable_load, max_cpu_runnable_load, min_cpu_runnable_load;
+	u64 avg_sg_load_per_task = 0;
+
 	int i;
 
 	if (local_group)
@@ -4521,6 +4527,8 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 	/* Tally up the load of all CPUs in the group */
 	max_cpu_load = 0;
 	min_cpu_load = ~0UL;
+	max_cpu_runnable_load = 0;
+	min_cpu_runnable_load = ~0ULL;
 	max_nr_running = 0;
 	min_nr_running = ~0UL;
 
@@ -4545,6 +4553,12 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 			if (min_cpu_load > load)
 				min_cpu_load = load;
 
+			cpu_runnable_load = cpu_rq(i)->cfs.runnable_load_avg;
+			if (cpu_runnable_load > max_cpu_runnable_load)
+				max_cpu_runnable_load = cpu_runnable_load;
+			if (min_cpu_runnable_load > cpu_runnable_load)
+				min_cpu_runnable_load = cpu_runnable_load;
+
 			if (nr_running > max_nr_running)
 				max_nr_running = nr_running;
 			if (min_nr_running > nr_running)
@@ -4604,10 +4618,13 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 	 *      normalized nr_running number somewhere that negates
 	 *      the hierarchy?
 	 */
-	if (sgs->sum_nr_running)
+	if (sgs->sum_nr_running) {
 		avg_load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running;
+		avg_sg_load_per_task = sgs->group_cfs_runnable_load / sgs->sum_nr_running;
+	}
 
-	if ((max_cpu_load - min_cpu_load) >= avg_load_per_task &&
+	/* The following decision is made on PJT's metric */
+	if ((max_cpu_runnable_load - min_cpu_runnable_load) >= avg_sg_load_per_task &&
 	    (max_nr_running - min_nr_running) > 1)
 		sgs->group_imb = 1;
 
@@ -5047,6 +5064,7 @@ out_balanced:
 
 ret:
 	env->imbalance = 0;
+	env->load_imbalance = 0;
 	return NULL;
 }
 

[RFC PATCH 05/13] sched:Calculate imbalance using PJT's metric

[Preeti U Murthy]

Additional parameters which decide the amount of imbalance in the sched domain
calculated using PJT's metric are used.

Signed-off-by: Preeti U Murthy <preeti@linux.vnet.ibm.com>
---
 kernel/sched/fair.c |   36 +++++++++++++++++++++++-------------
 1 file changed, 23 insertions(+), 13 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 77363c6..fca6606 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4892,12 +4892,14 @@ void fix_small_imbalance(struct lb_env *env, struct sd_lb_stats *sds)
  */
 static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *sds)
 {
-	unsigned long max_pull, load_above_capacity = ~0UL;
+	/* Additional parameters introduced to use PJT's metric */
+	u64 max_load_pull, load_above_busiest_capacity = ~0ULL;
 
-	sds->busiest_load_per_task /= sds->busiest_nr_running;
+	/* Calculation using PJT's metric */
+	sds->busiest_sg_load_per_task /= sds->busiest_nr_running;
 	if (sds->group_imb) {
-		sds->busiest_load_per_task =
-			min(sds->busiest_load_per_task, sds->avg_load);
+		sds->busiest_sg_load_per_task =
+			min(sds->busiest_sg_load_per_task, sds->avg_sgs_load);
 	}
 
 	/*
@@ -4905,21 +4907,24 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
 	 * max load less than avg load(as we skip the groups at or below
 	 * its cpu_power, while calculating max_load..)
 	 */
-	if (sds->max_load < sds->avg_load) {
+	if (sds->max_sg_load < sds->avg_sgs_load) {
 		env->imbalance = 0;
+		env->load_imbalance = 0;
 		return fix_small_imbalance(env, sds);
 	}
 
 	if (!sds->group_imb) {
 		/*
 		 * Don't want to pull so many tasks that a group would go idle.
+		 * Also the below change due to the integration with PJT's
+		 * metric
 		 */
-		load_above_capacity = (sds->busiest_nr_running -
+		load_above_busiest_capacity = (sds->busiest_nr_running -
 						sds->busiest_group_capacity);
 
-		load_above_capacity *= (SCHED_LOAD_SCALE * SCHED_POWER_SCALE);
+		load_above_busiest_capacity *= (SCHED_LOAD_SCALE * SCHED_POWER_SCALE);
 
-		load_above_capacity /= sds->busiest->sgp->power;
+		load_above_busiest_capacity /= sds->busiest->sgp->power;
 	}
 
 	/*
@@ -4932,11 +4937,16 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
 	 * Be careful of negative numbers as they'll appear as very large values
 	 * with unsigned longs.
 	 */
-	max_pull = min(sds->max_load - sds->avg_load, load_above_capacity);
+	/*
+	 * The below maximum load to be pulled is based on the PJT's metric
+ 	 */
+	max_load_pull = min(sds->max_sg_load - sds->avg_sgs_load, load_above_busiest_capacity);
 
-	/* How much load to actually move to equalise the imbalance */
-	env->imbalance = min(max_pull * sds->busiest->sgp->power,
-		(sds->avg_load - sds->this_load) * sds->this->sgp->power)
+	/* How much load to actually move to equalise the imbalance
+ 	 * Calculated using PJT's metric
+	 */
+	env->load_imbalance = min(max_load_pull * sds->busiest->sgp->power,
+		(sds->avg_sgs_load - sds->this_sg_load) * sds->this->sgp->power)
 			/ SCHED_POWER_SCALE;
 
 	/*
@@ -4945,7 +4955,7 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
 	 * a think about bumping its value to force at least one task to be
 	 * moved
 	 */
-	if (env->imbalance < sds->busiest_load_per_task)
+	if (env->load_imbalance < sds->busiest_sg_load_per_task)
 		return fix_small_imbalance(env, sds);
 
 }

[RFC PATCH 06/13] sched: Changing find_busiest_queue to use PJT's metric

[Preeti U Murthy]

Additional parameters which decide the busiest cpu in the chosen sched group
calculated using PJT's metric are used

Signed-off-by: Preeti U Murthy <preeti@linux.vnet.ibm.com>
---
 kernel/sched/fair.c |   13 +++++++++----
 1 file changed, 9 insertions(+), 4 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index fca6606..bb1c71b 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5085,7 +5085,7 @@ static struct rq *find_busiest_queue(struct lb_env *env,
 				     struct sched_group *group)
 {
 	struct rq *busiest = NULL, *rq;
-	unsigned long max_load = 0;
+	u64 max_cpu_load = 0;
 	int i;
 
 	for_each_cpu(i, sched_group_cpus(group)) {
@@ -5093,6 +5093,7 @@ static struct rq *find_busiest_queue(struct lb_env *env,
 		unsigned long capacity = DIV_ROUND_CLOSEST(power,
 							   SCHED_POWER_SCALE);
 		unsigned long wl;
+		u64 runnable_load;/* Equivalent of wl,calculated using PJT's metric */
 
 		if (!capacity)
 			capacity = fix_small_capacity(env->sd, group);
@@ -5102,12 +5103,14 @@ static struct rq *find_busiest_queue(struct lb_env *env,
 
 		rq = cpu_rq(i);
 		wl = weighted_cpuload(i);
+		runnable_load = cpu_rq(i)->cfs.runnable_load_avg;
 
 		/*
 		 * When comparing with imbalance, use weighted_cpuload()
 		 * which is not scaled with the cpu power.
+		 * The below decision is based on PJT's metric
 		 */
-		if (capacity && rq->nr_running == 1 && wl > env->imbalance)
+		if (capacity && rq->nr_running == 1 && runnable_load > env->load_imbalance)
 			continue;
 
 		/*
@@ -5117,9 +5120,11 @@ static struct rq *find_busiest_queue(struct lb_env *env,
 		 * running at a lower capacity.
 		 */
 		wl = (wl * SCHED_POWER_SCALE) / power;
+		runnable_load = (runnable_load * SCHED_POWER_SCALE) / power;
 
-		if (wl > max_load) {
-			max_load = wl;
+		/* Below decision has been changed to use PJT's metric */
+		if (runnable_load > max_cpu_load) {
+			max_cpu_load = runnable_load;
 			busiest = rq;
 		}
 	}

[RFC PATCH 07/13] sched: Change move_tasks to use PJT's metric

[Preeti U Murthy]

Make decisions based on PJT's metrics and the dependent metrics
about which tasks to move to reduce the imbalance.

Signed-off-by: Preeti U Murthy <preeti@linux.vnet.ibm.com>
---
 kernel/sched/fair.c |   14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index bb1c71b..bd7b69d 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -3957,7 +3957,7 @@ static int move_tasks(struct lb_env *env)
 	unsigned long load;
 	int pulled = 0;
 
-	if (env->imbalance <= 0)
+	if (env->load_imbalance <= 0)
 		return 0;
 
 again:
@@ -3984,7 +3984,8 @@ again:
 		if (sched_feat(LB_MIN) && load < 16 && !env->sd->nr_balance_failed)
 			goto next;
 
-		if ((load / 2) > env->imbalance)
+		/* The below being changed to use the PJT's metric */
+		if ((load / 2) > env->load_imbalance)
 			goto next;
 
 		if (!can_migrate_task(p, env))
@@ -3992,7 +3993,8 @@ again:
 
 		move_task(p, env);
 		pulled++;
-		env->imbalance -= load;
+		/* Using PJT's metric */
+		env->load_imbalance -= load;
 
 #ifdef CONFIG_PREEMPT
 		/*
@@ -4007,8 +4009,9 @@ again:
 		/*
 		 * We only want to steal up to the prescribed amount of
 		 * weighted load.
+		 * But the below modification is to use PJT's metric
 		 */
-		if (env->imbalance <= 0)
+		if (env->load_imbalance <= 0)
 			goto out;
 
 		continue;
@@ -4145,7 +4148,8 @@ static inline void update_h_load(long cpu)
 
 static unsigned long task_h_load(struct task_struct *p)
 {
-	return p->se.load.weight;
+	/* The below is changed to use PJT's metric*/
+	return p->se.avg.load_avg_contrib;
 }
 #endif
 

[RFC PATCH 08/13] sched: Some miscallaneous changes in load_balance

[Preeti U Murthy]

Modify certain decisions in load_balance to use the imbalance
amount as calculated by the PJT's metric.

Signed-off-by: Preeti U Murthy <preeti@linux.vnet.ibm.com>
---
 kernel/sched/fair.c |    5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index bd7b69d..68a6b1d 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5284,7 +5284,10 @@ more_balance:
 		 * moreover subsequent load balance cycles should correct the
 		 * excess load moved.
 		 */
-		if ((env.flags & LBF_SOME_PINNED) && env.imbalance > 0 &&
+		/*
+		 * The following decision based on PJT's metric
+ 		 */
+		if ((env.flags & LBF_SOME_PINNED) && env.load_imbalance > 0 &&
 				lb_iterations++ < max_lb_iterations) {
 
 			env.dst_rq	 = cpu_rq(env.new_dst_cpu);

[RFC PATCH 09/13] sched: Modify check_asym_packing to use PJT's metric

[Preeti U Murthy]

Make appropriate modifications in check_asym_packing to reflect PJT's
metric.

Signed-off-by: Preeti U Murthy <preeti@linux.vnet.ibm.com>
---
 kernel/sched/fair.c |    2 ++
 1 file changed, 2 insertions(+)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 68a6b1d..3b18f5f 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -4814,6 +4814,8 @@ static int check_asym_packing(struct lb_env *env, struct sd_lb_stats *sds)
 
 	env->imbalance = DIV_ROUND_CLOSEST(
 		sds->max_load * sds->busiest->sgp->power, SCHED_POWER_SCALE);
+	env->load_imbalance = DIV_ROUND_CLOSEST(
+		sds->max_sg_load * sds->busiest->sgp->power, SCHED_POWER_SCALE);
 
 	return 1;
 }

[RFC PATCH 10/13] sched: Modify fix_small_imbalance to use PJT's metric

[Preeti U Murthy]

Additional parameters which aid in taking the decisions in
fix_small_imbalance which are calculated using PJT's metric are used.

Signed-off-by: Preeti U Murthy <preeti@linux.vnet.ibm.com>
---
 kernel/sched/fair.c |   54 +++++++++++++++++++++++++++++++--------------------
 1 file changed, 33 insertions(+), 21 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 3b18f5f..a5affbc 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -2936,8 +2936,9 @@ static unsigned long cpu_avg_load_per_task(int cpu)
 	struct rq *rq = cpu_rq(cpu);
 	unsigned long nr_running = ACCESS_ONCE(rq->nr_running);
 
-	if (nr_running)
+	if (nr_running) {
 		return rq->load.weight / nr_running;
+	}
 
 	return 0;
 }
@@ -4830,27 +4831,38 @@ static int check_asym_packing(struct lb_env *env, struct sd_lb_stats *sds)
 static inline
 void fix_small_imbalance(struct lb_env *env, struct sd_lb_stats *sds)
 {
-	unsigned long tmp, pwr_now = 0, pwr_move = 0;
+	/* Parameters introduced to use PJT's metrics */
+	u64 tmp, pwr_now = 0, pwr_move = 0;
 	unsigned int imbn = 2;
 	unsigned long scaled_busy_load_per_task;
+	u64 scaled_busy_sg_load_per_task; /* Parameter to use PJT's metric */
+	unsigned long nr_running = ACCESS_ONCE(cpu_rq(env->dst_cpu)->nr_running);
 
 	if (sds->this_nr_running) {
-		sds->this_load_per_task /= sds->this_nr_running;
-		if (sds->busiest_load_per_task >
-				sds->this_load_per_task)
+		sds->this_sg_load_per_task /= sds->this_nr_running;
+		if (sds->busiest_sg_load_per_task >
+				sds->this_sg_load_per_task)
 			imbn = 1;
 	} else {
-		sds->this_load_per_task =
-			cpu_avg_load_per_task(env->dst_cpu);
+		if (nr_running) {
+			sds->this_sg_load_per_task =
+			/* The below decision based on PJT's metric */
+			cpu_rq(env->dst_cpu)->cfs.runnable_load_avg / nr_running;
+		} else {
+			sds->this_sg_load_per_task = 0;
+		}
 	}
 
 	scaled_busy_load_per_task = sds->busiest_load_per_task
 					 * SCHED_POWER_SCALE;
+	scaled_busy_sg_load_per_task = sds->busiest_sg_load_per_task
+					 * SCHED_POWER_SCALE;
 	scaled_busy_load_per_task /= sds->busiest->sgp->power;
+	scaled_busy_sg_load_per_task /= sds->busiest->sgp->power;
 
-	if (sds->max_load - sds->this_load + scaled_busy_load_per_task >=
-			(scaled_busy_load_per_task * imbn)) {
-		env->imbalance = sds->busiest_load_per_task;
+	if (sds->max_sg_load - sds->this_sg_load + scaled_busy_sg_load_per_task >=
+			(scaled_busy_sg_load_per_task * imbn)) {
+		env->load_imbalance = sds->busiest_sg_load_per_task;
 		return;
 	}
 
@@ -4861,33 +4873,33 @@ void fix_small_imbalance(struct lb_env *env, struct sd_lb_stats *sds)
 	 */
 
 	pwr_now += sds->busiest->sgp->power *
-			min(sds->busiest_load_per_task, sds->max_load);
+			min(sds->busiest_sg_load_per_task, sds->max_sg_load);
 	pwr_now += sds->this->sgp->power *
-			min(sds->this_load_per_task, sds->this_load);
+			min(sds->this_sg_load_per_task, sds->this_sg_load);
 	pwr_now /= SCHED_POWER_SCALE;
 
 	/* Amount of load we'd subtract */
-	tmp = (sds->busiest_load_per_task * SCHED_POWER_SCALE) /
+	tmp = (sds->busiest_sg_load_per_task * SCHED_POWER_SCALE) /
 		sds->busiest->sgp->power;
-	if (sds->max_load > tmp)
+	if (sds->max_sg_load > tmp)
 		pwr_move += sds->busiest->sgp->power *
-			min(sds->busiest_load_per_task, sds->max_load - tmp);
+			min(sds->busiest_sg_load_per_task, sds->max_sg_load - tmp);
 
 	/* Amount of load we'd add */
-	if (sds->max_load * sds->busiest->sgp->power <
-		sds->busiest_load_per_task * SCHED_POWER_SCALE)
-		tmp = (sds->max_load * sds->busiest->sgp->power) /
+	if (sds->max_sg_load * sds->busiest->sgp->power <
+		sds->busiest_sg_load_per_task * SCHED_POWER_SCALE)
+		tmp = (sds->max_sg_load * sds->busiest->sgp->power) /
 			sds->this->sgp->power;
 	else
-		tmp = (sds->busiest_load_per_task * SCHED_POWER_SCALE) /
+		tmp = (sds->busiest_sg_load_per_task * SCHED_POWER_SCALE) /
 			sds->this->sgp->power;
 	pwr_move += sds->this->sgp->power *
-			min(sds->this_load_per_task, sds->this_load + tmp);
+			min(sds->this_sg_load_per_task, sds->this_sg_load + tmp);
 	pwr_move /= SCHED_POWER_SCALE;
 
 	/* Move if we gain throughput */
 	if (pwr_move > pwr_now)
-		env->imbalance = sds->busiest_load_per_task;
+		env->load_imbalance = sds->busiest_sg_load_per_task;
 }
 
 /**

[RFC PATCH 11/13] sched: Modify find_idlest_group to use PJT's metric

[Preeti U Murthy]

Additional parameters introduced to perform this function which are
calculated using PJT's metrics and its helpers.

Signed-off-by: Preeti U Murthy <preeti@linux.vnet.ibm.com>
---
 kernel/sched/fair.c |   14 ++++++++++----
 1 file changed, 10 insertions(+), 4 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index a5affbc..c64be1c1 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -3173,11 +3173,13 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,
 		  int this_cpu, int load_idx)
 {
 	struct sched_group *idlest = NULL, *group = sd->groups;
-	unsigned long min_load = ULONG_MAX, this_load = 0;
+	unsigned long this_load = 0;
+	u64 min_sg_load = ~0ULL, this_sg_load = 0;/* Helpers for PJT's metrics */
 	int imbalance = 100 + (sd->imbalance_pct-100)/2;
 
 	do {
 		unsigned long load, avg_load;
+		u64 avg_sg_load;/* Helpers for PJT's metrics */
 		int local_group;
 		int i;
 
@@ -3191,6 +3193,7 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,
 
 		/* Tally up the load of all CPUs in the group */
 		avg_load = 0;
+		avg_sg_load = 0;
 
 		for_each_cpu(i, sched_group_cpus(group)) {
 			/* Bias balancing toward cpus of our domain */
@@ -3200,20 +3203,23 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,
 				load = target_load(i, load_idx);
 
 			avg_load += load;
+			avg_sg_load += cpu_rq(i)->cfs.runnable_load_avg;
 		}
 
 		/* Adjust by relative CPU power of the group */
 		avg_load = (avg_load * SCHED_POWER_SCALE) / group->sgp->power;
+		avg_sg_load = (avg_sg_load * SCHED_POWER_SCALE) / group->sgp->power;
 
 		if (local_group) {
 			this_load = avg_load;
-		} else if (avg_load < min_load) {
-			min_load = avg_load;
+			this_sg_load = avg_sg_load;
+		} else if (avg_sg_load < min_sg_load) {/* Decision changed to suit PJT's metric */
+			min_sg_load = avg_sg_load;
 			idlest = group;
 		}
 	} while (group = group->next, group != sd->groups);
 
-	if (!idlest || 100*this_load < imbalance*min_load)
+	if (!idlest || 100*this_sg_load < imbalance*min_sg_load)
 		return NULL;
 	return idlest;
 }

[RFC PATCH 12/13] sched: Modify find_idlest_cpu to use PJT's metric

[Preeti U Murthy]

Additional parameters introduced to perform this function which are
calculated using PJT's metrics and its helpers.

Signed-off-by: Preeti U Murthy <preeti@linux.vnet.ibm.com>
---
 kernel/sched/fair.c |    8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index c64be1c1..15ec528 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -3230,16 +3230,18 @@ find_idlest_group(struct sched_domain *sd, struct task_struct *p,
 static int
 find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
 {
-	unsigned long load, min_load = ULONG_MAX;
+	unsigned long load;
+	u64 cpu_load, min_cpu_load = ~0ULL;
 	int idlest = -1;
 	int i;
 
 	/* Traverse only the allowed CPUs */
 	for_each_cpu_and(i, sched_group_cpus(group), tsk_cpus_allowed(p)) {
 		load = weighted_cpuload(i);
+		cpu_load = cpu_rq(i)->cfs.runnable_load_avg;
 
-		if (load < min_load || (load == min_load && i == this_cpu)) {
-			min_load = load;
+		if (cpu_load < min_cpu_load || (cpu_load == min_cpu_load && i == this_cpu)) {
+			min_cpu_load = cpu_load;
 			idlest = i;
 		}
 	}

[RFC PATCH 13/13] sched: Modifying wake_affine to use PJT's metric

[Preeti U Murthy]

Additional parameters introduced to perform this function which are
calculated using PJT's metrics and its helpers.

Signed-off-by: Preeti U Murthy <preeti@linux.vnet.ibm.com>
---
 kernel/sched/fair.c |   34 +++++++++++++++-------------------
 1 file changed, 15 insertions(+), 19 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 15ec528..b4b572c 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -2931,19 +2931,6 @@ static unsigned long power_of(int cpu)
 	return cpu_rq(cpu)->cpu_power;
 }
 
-static unsigned long cpu_avg_load_per_task(int cpu)
-{
-	struct rq *rq = cpu_rq(cpu);
-	unsigned long nr_running = ACCESS_ONCE(rq->nr_running);
-
-	if (nr_running) {
-		return rq->load.weight / nr_running;
-	}
-
-	return 0;
-}
-
-
 static void task_waking_fair(struct task_struct *p)
 {
 	struct sched_entity *se = &p->se;
@@ -3085,16 +3072,18 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 {
 	s64 this_load, load;
 	int idx, this_cpu, prev_cpu;
-	unsigned long tl_per_task;
+	u64 tl_per_task; /* Modified to reflect PJT's metric */
 	struct task_group *tg;
-	unsigned long weight;
+	unsigned long weight, nr_running;
 	int balanced;
 
 	idx	  = sd->wake_idx;
 	this_cpu  = smp_processor_id();
 	prev_cpu  = task_cpu(p);
-	load	  = source_load(prev_cpu, idx);
-	this_load = target_load(this_cpu, idx);
+	/* Both of the below have been modified to use PJT's metric */
+	load      = cpu_rq(prev_cpu)->cfs.runnable_load_avg;
+	this_load = cpu_rq(this_cpu)->cfs.runnable_load_avg;
+	nr_running = cpu_rq(this_cpu)->nr_running;
 
 	/*
 	 * If sync wakeup then subtract the (maximum possible)
@@ -3104,6 +3093,7 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 	if (sync) {
 		tg = task_group(current);
 		weight = current->se.load.weight;
+		weight = current->se.avg.load_avg_contrib;
 
 		this_load += effective_load(tg, this_cpu, -weight, -weight);
 		load += effective_load(tg, prev_cpu, 0, -weight);
@@ -3111,6 +3101,8 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 
 	tg = task_group(p);
 	weight = p->se.load.weight;
+	/* The below change to reflect PJT's metric */
+	weight = p->se.avg.load_avg_contrib;
 
 	/*
 	 * In low-load situations, where prev_cpu is idle and this_cpu is idle
@@ -3146,11 +3138,15 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 		return 1;
 
 	schedstat_inc(p, se.statistics.nr_wakeups_affine_attempts);
-	tl_per_task = cpu_avg_load_per_task(this_cpu);
+	/* Below modification to use PJT's metric */
+	if (nr_running)
+		tl_per_task = cpu_rq(this_cpu)->cfs.runnable_load_avg / nr_running;
+	else
+		tl_per_task = 0;
 
 	if (balanced ||
 	    (this_load <= load &&
-	     this_load + target_load(prev_cpu, idx) <= tl_per_task)) {
+	     this_load + cpu_rq(prev_cpu)->cfs.runnable_load_avg <= tl_per_task)) {
 		/*
 		 * This domain has SD_WAKE_AFFINE and
 		 * p is cache cold in this domain, and

Re: [RFC PATCH 00/13] sched: Integrating Per-entity-load-tracking with the core scheduler

[Peter Zijlstra]

OK, so I tried reading a few patches and I'm completely failing.. maybe
its late and my brain stopped working, but it simply doesn't make any
sense.

Most changelogs and comments aren't really helping either. At best they
mention what you're doing, not why and how. This means I get to
basically duplicate your entire thought pattern and I might as well do
the patches myself.

I also don't see the 'big' picture of what you're doing, you start out
by some weird avoid short running task movement.. why is that a good
start?

I would have expected a series like this to replace rq->cpu_load /
rq->load with a saner metric and go from there.. instead it looks like
its going about at things completely backwards. Fixing small details
instead of the big things.

Do explain..

Re: [RFC PATCH 00/13] sched: Integrating Per-entity-load-tracking with the core scheduler

[Preeti U Murthy]

Hi Peter,
Thank you very much for your feedback.

On 10/25/2012 09:26 PM, Peter Zijlstra wrote:
> OK, so I tried reading a few patches and I'm completely failing.. maybe
> its late and my brain stopped working, but it simply doesn't make any
> sense.
> 
> Most changelogs and comments aren't really helping either. At best they
> mention what you're doing, not why and how. This means I get to
> basically duplicate your entire thought pattern and I might as well do
> the patches myself.
> 
> I also don't see the 'big' picture of what you're doing, you start out
> by some weird avoid short running task movement.. why is that a good
> start?
> 


> I would have expected a series like this to replace rq->cpu_load /
> rq->load with a saner metric and go from there.. instead it looks like
> its going about at things completely backwards. Fixing small details
> instead of the big things.

Let me see if I get what you are saying here right.You want to replace for example cfs_rq->load.weight with a saner metric because it does not consider the run time of the sched entities queued on it,merely their priorities.If this is right,in this patchset I believe cfs_rq->runnable_load_avg would be that right metric because it considers the run time of the sched entities queued on it.

So why didnt I replace? I added cfs_rq->runnable_load_avg as an additional metric instead of replacing the older metric.I let the old metric be as a dead metric and used the newer metric as an alternative.so if this alternate metric does not do us good we have the old metric to fall back on.

> At best they mention what you're doing, not why and how.
So the above explains *what* I am doing.

*How* am i doing it: Everywhere the scheduler needs to make a decision on:

 a.find_busiest_group/find_idlest_group/update_sg_lb_stats:use sum of cfs_rq->runnable_load_avg to decide this instead of sum of cfs_rq->load.weight.

 b.find_busiest_queue/find_idlest_queue: use cfs_rq->runnable_load_avg to decide this instead of cfs_rq->load.weight
 
 c.move_tasks: use se->avg.load_avg_contrib to decide the weight of of each task instead of se->load.weight as the former reflects the runtime of the sched entity and hence its actual load.

This is what my patches3-13 do.Merely *Replace*.

*Why am I doing it*: Feed the load balancer with a more realistic metric to do load balancing and observe the consequences.

> you start out by some weird avoid short running task movement.
> why is that a good start?

The short running tasks are not really burdening you,they have very little run time,so why move them?
Throughout the concept of load balancing the focus is on *balancing the *existing* load* between the sched groups.But not really evaluating the *absolute load* of any given sched group.

Why is this *the start*? This is like a round of elimination before the actual interview round ;) Try to have only those sched groups as candidates for load balancing that are sufficiently loaded.[Patch1]
This *sufficiently loaded* is decided by the new metric explained in the *How* above.

> I also don't see the 'big' picture of what you're doing

Patch1: is explained above.*End result:Good candidates for lb.*
Patch2: 
         10%
         10%
         10%                100%
        ------             ------
        SCHED_GP1          SCHED_GP2
   
Before Patch               After Patch
-----------------------------------
SCHED_GP1 load:3072        SCHED_GP1:512
SCHED_GP2 load:1024        SCHED_GP2:1024

SCHED_GP1 is busiest       SCHED_GP2 is busiest:
                       
But Patch2 re-decides between GP1 and GP2 to check if the latency of tasks is getting affected although there is less load on GP1.If yes it is a better *busy * gp.

*End Result: Better candidates for lb*

Rest of the patches: now that we have our busy sched group,let us load balance with the aid of the new metric.
*End Result: Hopefully a more sensible movement of loads*
This is how I build the picture.

Regards
Preeti

Re: [RFC PATCH 00/13] sched: Integrating Per-entity-load-tracking with the core scheduler

[Preeti U Murthy]

Hi Peter,
Thank you very much for your feedback.Please ignore the previous post.I
am extremely sorry about the word wrap issues with it.

On 10/25/2012 09:26 PM, Peter Zijlstra wrote:
> OK, so I tried reading a few patches and I'm completely failing.. maybe
> its late and my brain stopped working, but it simply doesn't make any
> sense.
> 
> Most changelogs and comments aren't really helping either. At best they
> mention what you're doing, not why and how. This means I get to
> basically duplicate your entire thought pattern and I might as well do
> the patches myself.
> 
> I also don't see the 'big' picture of what you're doing, you start out
> by some weird avoid short running task movement.. why is that a good
> start?
> 
> I would have expected a series like this to replace rq->cpu_load /
> rq->load with a saner metric and go from there.. instead it looks like
> its going about at things completely backwards. Fixing small details
> instead of the big things.
> 
> Do explain..
> 
Let me see if I get what you are saying here right.You want to replace
for example cfs_rq->load.weight with a saner metric because it does not
consider the run time of the sched entities queued on it,merely their
priorities.If this is right,in this patchset I believe
cfs_rq->runnable_load_avg would be that right metric because it
considers the run time of the sched entities queued on it.

So why didnt I replace? I added cfs_rq->runnable_load_avg as an
additional metric instead of replacing the older metric.I let the old
metric be as a dead metric and used the newer metric as an
alternative.so if this alternate metric does not do us good we have the
old metric to fall back on.

> At best they mention what you're doing, not why and how.
So the above explains *what* I am doing.

*How* am i doing it: Everywhere the scheduler needs to make a decision on:

 a.find_busiest_group/find_idlest_group/update_sg_lb_stats:use sum of
cfs_rq->runnable_load_avg to decide this instead of sum of
cfs_rq->load.weight.

 b.find_busiest_queue/find_idlest_queue: use cfs_rq->runnable_load_avg
to decide this instead of cfs_rq->load.weight

 c.move_tasks: use se->avg.load_avg_contrib to decide the weight of of
each task instead of se->load.weight as the former reflects the runtime
of the sched entity and hence its actual load.

This is what my patches3-13 do.Merely *Replace*.

*Why am I doing it*: Feed the load balancer with a more realistic metric
to do load balancing and observe the consequences.

> you start out by some weird avoid short running task movement.
> why is that a good start?

The short running tasks are not really burdening you,they have very
little run time,so why move them?
Throughout the concept of load balancing the focus is on *balancing the
*existing* load* between the sched groups.But not really evaluating the
*absolute load* of any given sched group.

Why is this *the start*? This is like a round of elimination before the
actual interview round  Try to have only those sched groups as
candidates for load balancing that are sufficiently loaded.[Patch1]
This *sufficiently loaded* is decided by the new metric explained in the
*How* above.

> I also don't see the 'big' picture of what you're doing

Patch1: is explained above.*End result:Good candidates for lb.*
Patch2:
         10%
         10%
         10%                100%
        ------             ------
        SCHED_GP1          SCHED_GP2

Before Patch               After Patch
-----------------------------------
SCHED_GP1 load:3072        SCHED_GP1:512
SCHED_GP2 load:1024        SCHED_GP2:1024

SCHED_GP1 is busiest       SCHED_GP2 is busiest:

But Patch2 re-decides between GP1 and GP2 to check if the latency of
tasks is getting affected although there is less load on GP1.If yes it
is a better *busy * gp.

*End Result: Better candidates for lb*

Rest of the patches: now that we have our busy sched group,let us load
balance with the aid of the new metric.
*End Result: Hopefully a more sensible movement of loads*
This is how I build the picture.

Regards
Preeti U Murthy

Re: [RFC PATCH 00/13] sched: Integrating Per-entity-load-tracking with the core scheduler

[Preeti Murthy]

The benchmark:

/*
 * test.c - Simulate workloads that load the CPU differently
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; version 2 of the License.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307
 * USA
 */

/*
 * This workload spawns threads which request for allocation of a
 * memory chunk,write to it and free it.The duty cycle of these threads
 * can be varied.The idea is to simulate tasks which load the cpu
 * to different extents.
 */

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <pthread.h>
#include <string.h>
#include <time.h>
#include <sys/time.h>
#include <sys/resource.h>
#include "malloc.h"

/* Variable entities */
static unsigned int seconds;
static unsigned int threads;
static unsigned int mem_chunk_size;
static unsigned int sleep_at;
static unsigned int sleep_interval;

typedef size_t mem_slot_t;/* 8 bytes */
static unsigned int slot_size = sizeof(mem_slot_t);

/* Other parameters */
static volatile int start;
static time_t start_time;
static unsigned int records_read;
pthread_mutex_t records_count_lock = PTHREAD_MUTEX_INITIALIZER;


static unsigned int write_to_mem(void)
{
    int i, j;
    mem_slot_t *scratch_pad, *temp;
    mem_chunk_size = slot_size * 256;
    mem_slot_t *end;

    /* The below two parameters ensure that it is 10% workload
     * with a duty cycle of 10ms.The number of records read in
     * 1s without sleep was observed and appropriately calculated
     * for 1ms.This number turned out to be 1228.
     */
    sleep_at = 1228; /* sleep for every 1228 records */
    sleep_interval = 9000; /* sleep for 9 ms */

    for (i=0; start == 1; i++)
    {
        scratch_pad = (mem_slot_t *)malloc(mem_chunk_size);
        if (scratch_pad == NULL) {
            fprintf(stderr,"Could not allocate memory\n");
            exit(1);
        }
        end = scratch_pad + (mem_chunk_size / slot_size);
        for (temp = scratch_pad, j=0; temp < end; temp++, j++)
            *temp = (mem_slot_t)j;

        free(scratch_pad);

        if (sleep_at && !(i % sleep_at))
            usleep(sleep_interval);
    }
    return (i);
}

static void *
thread_run(void *arg)
{

    unsigned int records_local;

    /* Wait for the start signal */

    while (start == 0);

    records_local = write_to_mem();

    pthread_mutex_lock(&records_count_lock);
    records_read += records_local;
    pthread_mutex_unlock(&records_count_lock);

    return NULL;
}

static void start_threads()
{
    double diff_time;
    unsigned int i;
    int err;
    threads = 8;
    seconds = 10;

    pthread_t thread_array[threads];
    for (i = 0; i < threads; i++) {
        err = pthread_create(&thread_array[i], NULL, thread_run, NULL);
        if (err) {
            fprintf(stderr, "Error creating thread %d\n", i);
            exit(1);
        }
    }
    start_time = time(NULL);
    start = 1;
    sleep(seconds);
    start = 0;
    diff_time = difftime(time(NULL), start_time);

    for (i = 0; i < threads; i++) {
        err = pthread_join(thread_array[i], NULL);
        if (err) {
            fprintf(stderr, "Error joining thread %d\n", i);
            exit(1);
        }
    }
     printf("%u records/s\n",
        (unsigned int) (((double) records_read)/diff_time));

}
int main()
{
    start_threads();
    return 0;
}

Regards
Preeti U Murthy

Re: [RFC PATCH 00/13] sched: Integrating Per-entity-load-tracking with the core scheduler

[Peter Zijlstra]

On Thu, 2012-10-25 at 23:42 +0530, Preeti U Murthy wrote:

> > Do explain..
> > 
> Let me see if I get what you are saying here right.You want to replace
> for example cfs_rq->load.weight with a saner metric because it does not
> consider the run time of the sched entities queued on it,merely their
> priorities.If this is right,in this patchset I believe
> cfs_rq->runnable_load_avg would be that right metric because it
> considers the run time of the sched entities queued on it.

firstly, cfs_rq is the wrong place for a per-cpu load measure, secondly
why add another load field instead of fixing the one we have? 

> So why didnt I replace? I added cfs_rq->runnable_load_avg as an
> additional metric instead of replacing the older metric.I let the old
> metric be as a dead metric and used the newer metric as an
> alternative.so if this alternate metric does not do us good we have the
> old metric to fall back on.

That's wrong.. either it works and we can apply the patches or it
doesn't and we won't. What you did makes it very hard to see you
preserve the current balancer -- which afaict you don't, you change the
balancer with the very first patch.

Why not update weighted_cpuload(), update_idle_cpu_load() and
update_cpu_load_active() to use another metric and go from there. If you
do that the whole balancer will auto-magically use the new weight
measure.

Once you have that running, you can look at modifying it.

> > At best they mention what you're doing, not why and how.
> So the above explains *what* I am doing.
> 
> *How* am i doing it: Everywhere the scheduler needs to make a decision on:
> 
>  a.find_busiest_group/find_idlest_group/update_sg_lb_stats:use sum of
> cfs_rq->runnable_load_avg to decide this instead of sum of
> cfs_rq->load.weight.

But the first patches are about adding new balancing conditions, that's
a complete fail..

>  b.find_busiest_queue/find_idlest_queue: use cfs_rq->runnable_load_avg
> to decide this instead of cfs_rq->load.weight

See, if you would have changed the input function (weighted_cpuload),
you wouldn't have needed to touch any of this.

>  c.move_tasks: use se->avg.load_avg_contrib to decide the weight of of
> each task instead of se->load.weight as the former reflects the runtime
> of the sched entity and hence its actual load.

The changelog in that patch (7) is completely devoid of any useful
information.

> This is what my patches3-13 do.Merely *Replace*.
> 
> *Why am I doing it*: Feed the load balancer with a more realistic metric
> to do load balancing and observe the consequences.

I know why you're doing the entire thing, but you fail to motivate each
individual change. A changelog should read something like:

  current code does blah, this has a problem when blah, we can improve
this doing blah because blah.



> > you start out by some weird avoid short running task movement.
> > why is that a good start?
> 
> The short running tasks are not really burdening you,they have very
> little run time,so why move them?

The most important part is why this would be a good start to the series,
it is not.

The patch is also dubious at best; short running might be all you have,
your definition of 'short' is also iffy.

> Throughout the concept of load balancing the focus is on *balancing the
> *existing* load* between the sched groups.But not really evaluating the
> *absolute load* of any given sched group.

Which is why you're going to change the metrics.. the balancer really
only cares about making load equal, flipping the metric of the load
doesn't change anything fundamental.

> Why is this *the start*? This is like a round of elimination before the
> actual interview round  Try to have only those sched groups as
> candidates for load balancing that are sufficiently loaded.[Patch1]
> This *sufficiently loaded* is decided by the new metric explained in the
> *How* above.

No, this is absolutely wrong.


So a sane series would introduce maybe two functions: cpu_load() and
task_load() and use those where we now use rq->load.weight and
p->se.load.weight for load balancing purposes. Implement these functions
using those two expression. So effectively this patch is a NOP.

Secondly, switch these two functions over to the per-task based
averages.

Tada! all done. The load balancer will then try and equalize effective
load instead of instant load.

It will do the 3x10% vs 100% thing correctly with just those two
patches. Simply because it will report a lower cpu-load for the 3x10%
case than it will for the 100% case, no need to go fudge about in the
load-balance internals.

Once you've got this correctly done, you can go change balancing to
better utilize the new metric, like use the effective load instead of
nr_running against the capacity and things like that. But for every such
change you want to be very careful and run all the benchmarks you can
find -- in fact you want to do that after the 2nd patch too.

Re: [RFC PATCH 00/13] sched: Integrating Per-entity-load-tracking with the core scheduler

[Ingo Molnar]

* Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:

> [...]
> 
> So a sane series would introduce maybe two functions: 
> cpu_load() and task_load() and use those where we now use 
> rq->load.weight and p->se.load.weight for load balancing 
> purposes. Implement these functions using those two 
> expression. So effectively this patch is a NOP.
> 
> Secondly, switch these two functions over to the per-task 
> based averages.
> 
> Tada! all done. The load balancer will then try and equalize 
> effective load instead of instant load.
> 
> It will do the 3x10% vs 100% thing correctly with just those 
> two patches. Simply because it will report a lower cpu-load 
> for the 3x10% case than it will for the 100% case, no need to 
> go fudge about in the load-balance internals.
> 
> Once you've got this correctly done, you can go change 
> balancing to better utilize the new metric, like use the 
> effective load instead of nr_running against the capacity and 
> things like that. But for every such change you want to be 
> very careful and run all the benchmarks you can find -- in 
> fact you want to do that after the 2nd patch too.

If anyone posted that simple two-patch series that switches over 
to the new load metrics I'd be happy to test the performance of 
those.

Having two parallel load metrics is really not something that we 
should tolerate for too long.

Thanks,

	Ingo

Re: [RFC PATCH 00/13] sched: Integrating Per-entity-load-tracking with the core scheduler

[Preeti U Murthy]

On 10/26/2012 05:59 PM, Peter Zijlstra wrote:
> On Thu, 2012-10-25 at 23:42 +0530, Preeti U Murthy wrote:

> firstly, cfs_rq is the wrong place for a per-cpu load measure, secondly
> why add another load field instead of fixing the one we have? 
Hmm..,rq->load.weight is the place.

>> So why didnt I replace? I added cfs_rq->runnable_load_avg as an
>> additional metric instead of replacing the older metric.I let the old
>> metric be as a dead metric and used the newer metric as an
>> alternative.so if this alternate metric does not do us good we have the
>> old metric to fall back on.
> 
> That's wrong.. either it works and we can apply the patches or it
> doesn't and we won't. What you did makes it very hard to see you
> preserve the current balancer -- which afaict you don't, you change the
> balancer with the very first patch.
You are right on this Peter.
> 
> Why not update weighted_cpuload(), update_idle_cpu_load() and
> update_cpu_load_active() to use another metric and go from there. If you
> do that the whole balancer will auto-magically use the new weight
> measure.
> 
> Once you have that running, you can look at modifying it.
Hmm...Correct.

>>  a.find_busiest_group/find_idlest_group/update_sg_lb_stats:use sum of
>> cfs_rq->runnable_load_avg to decide this instead of sum of
>> cfs_rq->load.weight.
> 
> But the first patches are about adding new balancing conditions, that's
> a complete fail..
> 
>>  b.find_busiest_queue/find_idlest_queue: use cfs_rq->runnable_load_avg
>> to decide this instead of cfs_rq->load.weight
> 
> See, if you would have changed the input function (weighted_cpuload),
> you wouldn't have needed to touch any of this.
> 
I see your point.
>>  c.move_tasks: use se->avg.load_avg_contrib to decide the weight of of
>> each task instead of se->load.weight as the former reflects the runtime
>> of the sched entity and hence its actual load.
> 
> The changelog in that patch (7) is completely devoid of any useful
> information.
> 
>> This is what my patches3-13 do.Merely *Replace*.
>>
>> *Why am I doing it*: Feed the load balancer with a more realistic metric
>> to do load balancing and observe the consequences.
> 
> I know why you're doing the entire thing, but you fail to motivate each
> individual change. A changelog should read something like:
> 
>   current code does blah, this has a problem when blah, we can improve
> this doing blah because blah.
> 
Ah! I get it.

>>> you start out by some weird avoid short running task movement.
>>> why is that a good start?
>>
>> The short running tasks are not really burdening you,they have very
>> little run time,so why move them?
> 
> The most important part is why this would be a good start to the series,
> it is not.
> 
> The patch is also dubious at best; short running might be all you have,
> your definition of 'short' is also iffy.
My definition of 'short' was bursty loads.What I observed from using the
new metric to study the effective load calculation was,when there are
around 2-3 such bursty loads the effective load stays below the
threshold that i have stated,and I thought this would be a good enough
excuse to let the loads stay on the cpu.

Bursty being a load that sleeps for 9ms every 10ms for a duration of
10s.(a 10% load) in my experiments.
> 
>> Throughout the concept of load balancing the focus is on *balancing the
>> *existing* load* between the sched groups.But not really evaluating the
>> *absolute load* of any given sched group.
> 
> Which is why you're going to change the metrics.. the balancer really
> only cares about making load equal, flipping the metric of the load
> doesn't change anything fundamental.
Ok.
> 
>> Why is this *the start*? This is like a round of elimination before the
>> actual interview round  Try to have only those sched groups as
>> candidates for load balancing that are sufficiently loaded.[Patch1]
>> This *sufficiently loaded* is decided by the new metric explained in the
>> *How* above.
> 
> No, this is absolutely wrong.
> 
> 
> So a sane series would introduce maybe two functions: cpu_load() and
> task_load() and use those where we now use rq->load.weight and
> p->se.load.weight for load balancing purposes. Implement these functions
> using those two expression. So effectively this patch is a NOP.
> 
> Secondly, switch these two functions over to the per-task based
> averages.
> 
> Tada! all done. The load balancer will then try and equalize effective
> load instead of instant load.
> 
> It will do the 3x10% vs 100% thing correctly with just those two
> patches. Simply because it will report a lower cpu-load for the 3x10%
> case than it will for the 100% case, no need to go fudge about in the
> load-balance internals.
> 
> Once you've got this correctly done, you can go change balancing to
> better utilize the new metric, like use the effective load instead of
> nr_running against the capacity and things like that. But for every such
> change you want to be very careful and run all the benchmarks you can
> find -- in fact you want to do that after the 2nd patch too.
> 
I agree with this entire suggestion.Perhaps I was hesitant with
introducing the new metric into the scheduler which led to this two
faced approach.I will try out this approach suggested and post out the
results very soon.

Thank you very much for such a comprehensive and helpful feedback!

Regards
Preeti U Murthy

Re: [RFC PATCH 00/13] sched: Integrating Per-entity-load-tracking with the core scheduler

[Preeti U Murthy]

On 10/26/2012 06:37 PM, Ingo Molnar wrote:
> 
> * Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
> 
>> [...]
>>
>> So a sane series would introduce maybe two functions: 
>> cpu_load() and task_load() and use those where we now use 
>> rq->load.weight and p->se.load.weight for load balancing 
>> purposes. Implement these functions using those two 
>> expression. So effectively this patch is a NOP.
>>
>> Secondly, switch these two functions over to the per-task 
>> based averages.
>>
>> Tada! all done. The load balancer will then try and equalize 
>> effective load instead of instant load.
>>
>> It will do the 3x10% vs 100% thing correctly with just those 
>> two patches. Simply because it will report a lower cpu-load 
>> for the 3x10% case than it will for the 100% case, no need to 
>> go fudge about in the load-balance internals.
>>
>> Once you've got this correctly done, you can go change 
>> balancing to better utilize the new metric, like use the 
>> effective load instead of nr_running against the capacity and 
>> things like that. But for every such change you want to be 
>> very careful and run all the benchmarks you can find -- in 
>> fact you want to do that after the 2nd patch too.
> 
> If anyone posted that simple two-patch series that switches over 
> to the new load metrics I'd be happy to test the performance of 
> those.
> 
> Having two parallel load metrics is really not something that we 
> should tolerate for too long.
> 
> Thanks,
> 
> 	Ingo
> 
Right Ingo.I will incorporate this approach and post out very soon.

Thank you

Regards
Preeti