Skip to contentSkip to conversation

Minature NUMA scheduler

PATCH In review Martin J. Bligh 14 participants 96 messages Jan 9, 2003 – Feb 4, 2003

Subsystems (11)
lore
Share & tools
lore
#0 lore raw

I tried a small experiment today - did a simple restriction of the O(1) scheduler to only balance inside a node. Coupled with the small initial load balancing patch floating around, this covers 95% of cases, is a trivial change (3 lines), performs just as well as Erich's patch on a kernel compile, and actually better on schedbench.

This is NOT meant to be a replacement for the code Erich wrote, it's meant to be a simple way to get integration and acceptance. Code that just forks and never execs will stay on one node - but we can take the code Erich wrote, and put it in seperate rebalancer that fires much less often to do a cross-node rebalance. All that would be under #ifdef CONFIG_NUMA, the only thing that would touch mainline is these three lines of change, and it's trivial to see they're completely equivalent to the current code on non-NUMA systems.

I also believe that this is the more correct approach in design, it should result in much less cross-node migration of tasks, and less scanning of remote runqueues.

Opinions / comments?

M.

Kernbench:

                                   Elapsed        User      System         CPU
                   2.5.54-mjb3      19.41s     186.38s     39.624s     1191.4%
          2.5.54-mjb3-mjbsched     19.508s    186.356s     39.888s     1164.6%

Schedbench 4:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                   2.5.54-mjb3        0.00       35.14       88.82        0.64
          2.5.54-mjb3-mjbsched        0.00       31.84       88.91        0.49

Schedbench 8:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                   2.5.54-mjb3        0.00       47.55      269.36        1.48
          2.5.54-mjb3-mjbsched        0.00       41.01      252.34        1.07

Schedbench 16:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                   2.5.54-mjb3        0.00       76.53      957.48        4.17
          2.5.54-mjb3-mjbsched        0.00       69.01      792.71        2.74

Schedbench 32:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                   2.5.54-mjb3        0.00      145.20     1993.97       11.05
          2.5.54-mjb3-mjbsched        0.00      117.47     1798.93        5.95

Schedbench 64:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                   2.5.54-mjb3        0.00      307.80     4643.55       20.36
          2.5.54-mjb3-mjbsched        0.00      241.04     3589.55       12.74

-----------------------------------------

kernel/sched.c +4 -3
diff -purN -X /home/mbligh/.diff.exclude virgin/kernel/sched.c mjbsched/kernel/sched.c
@@ -654,7 +654,7 @@ static inline unsigned int double_lock_b
 /*
  * find_busiest_queue - find the busiest runqueue.
  */
-static inline runqueue_t *find_busiest_queue(runqueue_t *this_rq, int this_cpu, int idle, int *imbalance)
+static inline runqueue_t *find_busiest_queue(runqueue_t *this_rq, int this_cpu, int idle, int *imbalance, unsigned long cpumask)
 {
 	int nr_running, load, max_load, i;
 	runqueue_t *busiest, *rq_src;
@@ -689,7 +689,7 @@ static inline runqueue_t *find_busiest_q
 	busiest = NULL;
 	max_load = 1;
 	for (i = 0; i < NR_CPUS; i++) {
-		if (!cpu_online(i))
+		if (!cpu_online(i) || !((1 << i) & cpumask) )
 			continue;
 
 		rq_src = cpu_rq(i);
@@ -764,7 +764,8 @@ static void load_balance(runqueue_t *thi
 	struct list_head *head, *curr;
 	task_t *tmp;
 
-	busiest = find_busiest_queue(this_rq, this_cpu, idle, &imbalance);
+	busiest = find_busiest_queue(this_rq, this_cpu, idle, &imbalance, 
+				__node_to_cpu_mask(__cpu_to_node(this_cpu)) );
 	if (!busiest)
 		goto out;
 

---------------------------------------------------

A tiny change in the current ilb patch is also needed to stop it using a macro from the first patch:

kernel/sched.c +5 -2
diff -purN -X /home/mbligh/.diff.exclude ilbold/kernel/sched.c ilbnew/kernel/sched.c
@@ -2213,6 +2213,7 @@ static void sched_migrate_task(task_t *p
 static int sched_best_cpu(struct task_struct *p)
 {
 	int i, minload, load, best_cpu, node = 0;
+	unsigned long cpumask;
 
 	best_cpu = task_cpu(p);
 	if (cpu_rq(best_cpu)->nr_running <= 2)
@@ -2226,9 +2227,11 @@ static int sched_best_cpu(struct task_st
 			node = i;
 		}
 	}
+
 	minload = 10000000;
-	loop_over_node(i,node) {
-		if (!cpu_online(i))
+	cpumask = __node_to_cpu_mask(node);
+	for (i = 0; i < NR_CPUS; ++i) {
+		if (!(cpumask & (1 << i)))
 			continue;
 		if (cpu_rq(i)->nr_running < minload) {
 			best_cpu = i;
#1 lore raw
Quoted 7 lines · Martin J. Bligh

I tried a small experiment today - did a simple restriction of the O(1) scheduler to only balance inside a node. Coupled with the small initial load balancing patch floating around, this covers 95% of cases, is a trivial change (3 lines), performs just as well as Erich's patch on a kernel compile, and actually better on schedbench.

Quoted 5 lines

This is NOT meant to be a replacement for the code Erich wrote, it's meant to be a simple way to get integration and acceptance. Code that just forks and never execs will stay on one node - but we can take the code Erich wrote, and put it in seperate rebalancer that fires much less often to do a cross-node rebalance.

I tried this on my 4 node NUMAQ (16 procs, 16GB memory) and got similar results. Also, added in the cputime_stats patch and am attaching the matrix results from the 32 process run. Basically, all runs show that the initial load balancer is able to place the tasks evenly across the nodes, and the better overall times show that not migrating to keep the nodes balanced over time results in better performance - at least on these boxes.

Obviously, there can be situations where load balancing across nodes is necessary, but these results point to less load balancing being better, at least on these machines. It will be interesting to repeat this on boxes with other interconnects.

$ reportbench hacksched54 sched54 stock54
Kernbench:
                        Elapsed       User     System        CPU
         hacksched54    29.406s    282.18s    81.716s    1236.8%
             sched54    29.112s   283.888s     82.84s    1259.4%
             stock54    31.348s   303.134s    87.824s    1247.2%

Schedbench 4:

                        AvgUser    Elapsed  TotalUser   TotalSys
         hacksched54      21.94      31.93      87.81       0.53
             sched54      22.03      34.90      88.15       0.75
             stock54      49.35      57.53     197.45       0.86

Schedbench 8:

                        AvgUser    Elapsed  TotalUser   TotalSys
         hacksched54      28.23      31.62     225.87       1.11
             sched54      27.95      37.12     223.66       1.50
             stock54      43.14      62.97     345.18       2.12

Schedbench 16:

                        AvgUser    Elapsed  TotalUser   TotalSys
         hacksched54      49.29      71.31     788.83       2.88
             sched54      55.37      69.58     886.10       3.79
             stock54      66.00      81.25    1056.25       7.12

Schedbench 32:

                        AvgUser    Elapsed  TotalUser   TotalSys
         hacksched54      56.41     117.98    1805.35       5.90
             sched54      57.93     132.11    1854.01      10.74
             stock54      77.81     173.26    2490.31      12.37

Schedbench 64:

                        AvgUser    Elapsed  TotalUser   TotalSys
         hacksched54      56.62     231.93    3624.42      13.32
             sched54      72.91     308.87    4667.03      21.06
             stock54      86.68     368.55    5548.57      25.73

hacksched54 = 2.5.54 + Martin's tiny NUMA patch +

              03-cputimes_stat-2.5.53.patch +
              02-numa-sched-ilb-2.5.53-21.patch
sched54 = 2.5.54 + 01-numa-sched-core-2.5.53-24.patch + 
          02-ilb-2.5.53-21.patch02 +
          03-cputimes_stat-2.5.53.patch

stock54 - 2.5.54 + 03-cputimes_stat-2.5.53.patch

Detailed results from running numa_test 32:

Executing 32 times: ./randupdt 1000000 Running 'hackbench 20' in the background: Time: 4.557

Job  node00 node01 node02 node03 | iSched MSched | UserTime(s)
  1   100.0    0.0    0.0    0.0 |    0     0    |  57.12
  2     0.0  100.0    0.0    0.0 |    1     1    |  55.89
  3   100.0    0.0    0.0    0.0 |    0     0    |  55.39
  4     0.0    0.0  100.0    0.0 |    2     2    |  56.67
  5     0.0    0.0    0.0  100.0 |    3     3    |  57.08
  6     0.0  100.0    0.0    0.0 |    1     1    |  56.31
  7   100.0    0.0    0.0    0.0 |    0     0    |  57.11
  8     0.0    0.0    0.0  100.0 |    3     3    |  56.66
  9     0.0  100.0    0.0    0.0 |    1     1    |  55.87
 10     0.0    0.0  100.0    0.0 |    2     2    |  55.83
 11     0.0    0.0    0.0  100.0 |    3     3    |  56.01
 12     0.0  100.0    0.0    0.0 |    1     1    |  56.56
 13     0.0    0.0  100.0    0.0 |    2     2    |  56.31
 14     0.0    0.0    0.0  100.0 |    3     3    |  56.40
 15   100.0    0.0    0.0    0.0 |    0     0    |  55.82
 16     0.0  100.0    0.0    0.0 |    1     1    |  57.47
 17     0.0    0.0  100.0    0.0 |    2     2    |  56.76
 18     0.0    0.0    0.0  100.0 |    3     3    |  57.10
 19     0.0  100.0    0.0    0.0 |    1     1    |  57.26
 20     0.0    0.0  100.0    0.0 |    2     2    |  56.48
 21     0.0    0.0    0.0  100.0 |    3     3    |  56.65
 22     0.0  100.0    0.0    0.0 |    1     1    |  55.81
 23     0.0    0.0  100.0    0.0 |    2     2    |  55.77
 24     0.0    0.0    0.0  100.0 |    3     3    |  56.91
 25     0.0  100.0    0.0    0.0 |    1     1    |  56.86
 26     0.0    0.0  100.0    0.0 |    2     2    |  56.62
 27     0.0    0.0    0.0  100.0 |    3     3    |  57.16
 28     0.0    0.0  100.0    0.0 |    2     2    |  56.36
 29   100.0    0.0    0.0    0.0 |    0     0    |  55.72
 30   100.0    0.0    0.0    0.0 |    0     0    |  56.00
 31   100.0    0.0    0.0    0.0 |    0     0    |  55.48
 32   100.0    0.0    0.0    0.0 |    0     0    |  55.59
AverageUserTime 56.41 seconds
ElapsedTime     117.98
TotalUserTime   1805.35
TotalSysTime    5.90

Runs with 4, 8, 16, and 64 processes all showed the same even distribution across all nodes and 100% time on node for each process.

Signature · 2 lines
Michael Hohnbaum            503-578-5486
[email protected]         T/L 775-5486
#2 lore raw

Hi Martin & Michael,

indeed, restricting a process to the node on which it was started helps, as the memory will always be local. The NUMA scheduler allows a process to move away from it's node, if the load conditions require it, but in the current form the process will not come back to its homenode. That's what the "node affine scheduler" tried to realise.

The miniature NUMA scheduler relies on the quality of the initial load balancer, and that one seems to be good enough. As you mentioned, multithreaded jobs are disadvantaged as their threads have to stick on the originating node.

Having some sort of automatic node affinity of processes and equal node loads in mind (as design targets), we could:
- take the minimal NUMA scheduler
- if the normal (node-restricted) find_busiest_queue() fails and certain conditions are fulfilled (tried to balance inside own node for a while and didn't succeed, own CPU idle, etc... ???) rebalance over node boundaries (eg. using my load balancer)
This actually resembles the original design of the node affine scheduler, having the cross-node balancing separate is ok and might make the ideas clearer.

I made some measurements, too, and found basically what I expected. The numbers are from a machine with 4 nodes of 2 CPUs each. It's on ia64, so 2.5.52 based.

As the minsched cannot make mistakes (by moving tasks away from their homenode), it leads to the best results with numa_test. OTOH hackbench suffers a lot from the limitation to one node. The hackbench tasks are not latency/bandwidth limited, the faster they spread over the whole machine, the quicker finishes the job. That's why NUMA-sched is slightly worse than a stock kernel. But minsched looses >50%. Funilly, on my machine kernbench is slightly faster with the normal NUMA scheduler.

Regards,
Erich

Results on a 8 CPU machine with 4 nodes (2 CPUs per node).

kernbench:

                elapsed       user          system
      stock52   134.52(0.84)  951.64(0.97)  20.72(0.22)
      sched52   133.19(1.49)  944.24(0.50)  21.36(0.24)
   minsched52   135.47(0.47)  937.61(0.20)  21.30(0.14)

schedbench/hackbench: time(s)

               10         25         50         100
      stock52  0.81(0.04) 2.06(0.07) 4.09(0.13) 7.89(0.25)
      sched52  0.81(0.04) 2.03(0.07) 4.14(0.20) 8.61(0.35)

minsched52 1.28(0.05) 3.19(0.06) 6.59(0.13) 13.56(0.27)

numabench/numa_test 4

               AvgUserTime ElapsedTime TotUserTime TotSysTime
      stock52  ---         27.23(0.52) 89.30(4.18) 0.09(0.01)
      sched52  22.32(1.00) 27.39(0.42) 89.29(4.02) 0.10(0.01)

minsched52 20.01(0.01) 23.40(0.13) 80.05(0.02) 0.08(0.01)

numabench/numa_test 8

               AvgUserTime ElapsedTime TotUserTime  TotSysTime
      stock52  ---         27.50(2.58) 174.74(6.66) 0.18(0.01)
      sched52  21.73(1.00) 33.70(1.82) 173.87(7.96) 0.18(0.01)

minsched52 20.31(0.00) 23.50(0.12) 162.47(0.04) 0.16(0.01)

numabench/numa_test 16

               AvgUserTime ElapsedTime TotUserTime   TotSysTime
      stock52  ---         52.68(1.51) 390.03(15.10) 0.34(0.01)
      sched52  21.51(0.80) 47.18(3.24) 344.29(12.78) 0.36(0.01)

minsched52 20.50(0.03) 43.82(0.08) 328.05(0.45) 0.34(0.01)

numabench/numa_test 32

               AvgUserTime ElapsedTime  TotUserTime   TotSysTime
      stock52  ---         102.60(3.89) 794.57(31.72) 0.65(0.01)
      sched52  21.93(0.57) 92.46(1.10)  701.75(18.38) 0.67(0.02)

minsched52 20.64(0.10) 89.95(3.16) 660.72(3.13) 0.68(0.07)

Quoted 71 lines · Michael Hohnbaum
Quoted 7 lines · Martin J. Bligh

I tried a small experiment today - did a simple restriction of the O(1) scheduler to only balance inside a node. Coupled with the small initial load balancing patch floating around, this covers 95% of cases, is a trivial change (3 lines), performs just as well as Erich's patch on a kernel compile, and actually better on schedbench.

Quoted 5 lines

This is NOT meant to be a replacement for the code Erich wrote, it's meant to be a simple way to get integration and acceptance. Code that just forks and never execs will stay on one node - but we can take the code Erich wrote, and put it in seperate rebalancer that fires much less often to do a cross-node rebalance.

I tried this on my 4 node NUMAQ (16 procs, 16GB memory) and got similar results. Also, added in the cputime_stats patch and am attaching the matrix results from the 32 process run. Basically, all runs show that the initial load balancer is able to place the tasks evenly across the nodes, and the better overall times show that not migrating to keep the nodes balanced over time results in better performance - at least on these boxes.

Obviously, there can be situations where load balancing across nodes is necessary, but these results point to less load balancing being better, at least on these machines. It will be interesting to repeat this on boxes with other interconnects.

$ reportbench hacksched54 sched54 stock54
Kernbench:
                        Elapsed       User     System        CPU
         hacksched54    29.406s    282.18s    81.716s    1236.8%
             sched54    29.112s   283.888s     82.84s    1259.4%
             stock54    31.348s   303.134s    87.824s    1247.2%

Schedbench 4:

                        AvgUser    Elapsed  TotalUser   TotalSys
         hacksched54      21.94      31.93      87.81       0.53
             sched54      22.03      34.90      88.15       0.75
             stock54      49.35      57.53     197.45       0.86

Schedbench 8:

                        AvgUser    Elapsed  TotalUser   TotalSys
         hacksched54      28.23      31.62     225.87       1.11
             sched54      27.95      37.12     223.66       1.50
             stock54      43.14      62.97     345.18       2.12

Schedbench 16:

                        AvgUser    Elapsed  TotalUser   TotalSys
         hacksched54      49.29      71.31     788.83       2.88
             sched54      55.37      69.58     886.10       3.79
             stock54      66.00      81.25    1056.25       7.12

Schedbench 32:

                        AvgUser    Elapsed  TotalUser   TotalSys
         hacksched54      56.41     117.98    1805.35       5.90
             sched54      57.93     132.11    1854.01      10.74
             stock54      77.81     173.26    2490.31      12.37

Schedbench 64:

                        AvgUser    Elapsed  TotalUser   TotalSys
         hacksched54      56.62     231.93    3624.42      13.32
             sched54      72.91     308.87    4667.03      21.06
             stock54      86.68     368.55    5548.57      25.73

hacksched54 = 2.5.54 + Martin's tiny NUMA patch +

              03-cputimes_stat-2.5.53.patch +
              02-numa-sched-ilb-2.5.53-21.patch
sched54 = 2.5.54 + 01-numa-sched-core-2.5.53-24.patch +
          02-ilb-2.5.53-21.patch02 +
          03-cputimes_stat-2.5.53.patch

stock54 - 2.5.54 + 03-cputimes_stat-2.5.53.patch

#3 lore raw
Quoted 10 lines

Having some sort of automatic node affinity of processes and equal node loads in mind (as design targets), we could:
- take the minimal NUMA scheduler
- if the normal (node-restricted) find_busiest_queue() fails and certain conditions are fulfilled (tried to balance inside own node for a while and didn't succeed, own CPU idle, etc... ???) rebalance over node boundaries (eg. using my load balancer)
This actually resembles the original design of the node affine scheduler, having the cross-node balancing separate is ok and might make the ideas clearer.

This seems like the right approach to me, apart from the trigger to do the cross-node rebalance. I don't believe that has anything to do with when we're internally balanced within a node or not, it's whether the nodes are balanced relative to each other. I think we should just check that every N ticks, looking at node load averages, and do a cross-node rebalance if they're "significantly out".

The definintion of "N ticks" and "significantly out" would be a tunable number, defined by each platform; roughly speaking, the lower the NUMA ratio, the lower these numbers would be. That also allows us to wedge all sorts of smarts in the NUMA rebalance part of the scheduler, such as moving the tasks with the smallest RSS off node. The NUMA rebalancer is obviously completely missing from the current implementation, and I expect we'd use mainly Erich's current code to implement that. However, it's suprising how well we do with no rebalancer at all, apart from the exec-time initial load balance code.

Another big advantage of this approach is that it *obviously* changes nothing at all for standard SMP systems (whereas your current patch does), so it should be much easier to get it accepted into mainline ....

M.

#4 lore raw
Quoted 6 lines · Martin J. Bligh

This seems like the right approach to me, apart from the trigger to do the cross-node rebalance. I don't believe that has anything to do with when we're internally balanced within a node or not, it's whether the nodes are balanced relative to each other. I think we should just check that every N ticks, looking at node load averages, and do a cross-node rebalance if they're "significantly out".

OK, I changed my mind about the trigger and made some experiments with the cross-node balancer called after every N calls of load_balance. If we make N tunable, we can even have some dynamics in case the nodes are unbalanced: make N small if the current node is less loaded than the average node loads, make N large if the node is averagely loaded. I'll send the patches in a separate email.

Quoted 5 lines

The NUMA rebalancer
is obviously completely missing from the current implementation, and I expect we'd use mainly Erich's current code to implement that. However, it's suprising how well we do with no rebalancer at all, apart from the exec-time initial load balance code.

The fact that we're doing fine on kernbench and numa_test/schedbench is (I think) understandeable. In both benchmarks a process cannot change its node during its lifetime, therefore has minimal memory latency. In numa_test the "disturbing" hackbench just cannot move away any of the tasks from their originating node. Therefore the results are the best possible.

Regards,
Erich

#5 lore raw

NUMA scheduler 2nd approach

In reply to Martin J. Bligh

Hi Martin & Michael,

as discussed on the LSE call I played around with a cross-node balancer approach put on top of the miniature NUMA scheduler. The patches are attached and it seems to be clear that we can regain the good performance for hackbench by adding a cross-node balancer.

The patches are:

01-minisched-2.5.55.patch : the miniature scheduler from Martin. Balances strictly within a node. Added an inlined function to make the integration of the cross-node balancer easier. The added code is optimised away by the compiler.

02-initial-lb-2.5.55.patch : Michael's initial load balancer at exec().

03-internode-lb-2.5.55.patch : internode load balancer core. Called after INTERNODE_LB calls of the inter-node load balancer. The most loaded node's cpu-mask is ORed to the own node's cpu-mask and find_busiest_in_mask() finds the most loaded CPU in this set.

04-smooth-node-load-2.5.55.patch : The node load measure is smoothed by adding half of the previous node load (and 1/4 of the one before, etc..., as discussed in the LSE call). This should improve a bit the behavior in case of short timed load peaks and avoid bouncing tasks between nodes.

05-var-intnode-lb2-2.5.55.patch : Replaces the fixed INTERNODE_LB interval (between cross-node balancer calls) by a variable node-specific interval. Currently only two values used. Certainly needs some tweaking and tuning.

01, 02, 03 are enough to produce a working NUMA scheduler, when including all patches the behavior should be better. I made some measurements which I'd like to post in a separate email tomorrow.

Comments? Ideas?

Regards,
Erich

kernel/sched.c +13 -3
diff -urNp linux-2.5.55/kernel/sched.c linux-2.5.55-ms/kernel/sched.c
@@ -652,9 +652,9 @@ static inline unsigned int double_lock_b
 }
 
 /*
- * find_busiest_queue - find the busiest runqueue.
+ * find_busiest_in_mask - find the busiest runqueue among the cpus in cpumask
  */
-static inline runqueue_t *find_busiest_queue(runqueue_t *this_rq, int this_cpu, int idle, int *imbalance)
+static inline runqueue_t *find_busiest_in_mask(runqueue_t *this_rq, int this_cpu, int idle, int *imbalance, unsigned long cpumask)
 {
 	int nr_running, load, max_load, i;
 	runqueue_t *busiest, *rq_src;
@@ -689,7 +689,7 @@ static inline runqueue_t *find_busiest_q
 	busiest = NULL;
 	max_load = 1;
 	for (i = 0; i < NR_CPUS; i++) {
-		if (!cpu_online(i))
+		if (!cpu_online(i) || !((1UL << i) & cpumask) )
 			continue;
 
 		rq_src = cpu_rq(i);
@@ -730,6 +730,16 @@ out:
 }
 
 /*
+ * find_busiest_queue - find the busiest runqueue.
+ */
+static inline runqueue_t *find_busiest_queue(runqueue_t *this_rq, int this_cpu, int idle, int *imbalance)
+{
+	unsigned long cpumask = __node_to_cpu_mask(__cpu_to_node(this_cpu));
+	return find_busiest_in_mask(this_rq, this_cpu, idle, imbalance,
+				    cpumask);
+}
+
+/*
  * pull_task - move a task from a remote runqueue to the local runqueue.
  * Both runqueues must be locked.
  */
fs/exec.c +2 -0
diff -urNp linux-2.5.55-ms/fs/exec.c linux-2.5.55-ms-ilb/fs/exec.c
@@ -1027,6 +1027,8 @@ int do_execve(char * filename, char ** a
 	int retval;
 	int i;
 
+	sched_balance_exec();
+
 	file = open_exec(filename);
 
 	retval = PTR_ERR(file);
include/linux/sched.h +14 -1
diff -urNp linux-2.5.55-ms/include/linux/sched.h linux-2.5.55-ms-ilb/include/linux/sched.h
@@ -160,7 +160,6 @@ extern void update_one_process(struct ta
 extern void scheduler_tick(int user_tick, int system);
 extern unsigned long cache_decay_ticks;
 
-
 #define	MAX_SCHEDULE_TIMEOUT	LONG_MAX
 extern signed long FASTCALL(schedule_timeout(signed long timeout));
 asmlinkage void schedule(void);
@@ -444,6 +443,20 @@ extern void set_cpus_allowed(task_t *p, 
 # define set_cpus_allowed(p, new_mask) do { } while (0)
 #endif
 
+#ifdef CONFIG_NUMA
+extern void sched_balance_exec(void);
+extern void node_nr_running_init(void);
+#define nr_running_inc(rq) atomic_inc(rq->node_ptr); \
+	rq->nr_running++
+#define nr_running_dec(rq) atomic_dec(rq->node_ptr); \
+	rq->nr_running--
+#else
+#define sched_balance_exec() {}
+#define node_nr_running_init() {}
+#define nr_running_inc(rq) rq->nr_running++
+#define nr_running_dec(rq) rq->nr_running--
+#endif
+
 extern void set_user_nice(task_t *p, long nice);
 extern int task_prio(task_t *p);
 extern int task_nice(task_t *p);
init/main.c +1 -0
diff -urNp linux-2.5.55-ms/init/main.c linux-2.5.55-ms-ilb/init/main.c
@@ -495,6 +495,7 @@ static void do_pre_smp_initcalls(void)
 
 	migration_init();
 #endif
+	node_nr_running_init();
 	spawn_ksoftirqd();
 }
 
kernel/sched.c +89 -4

130 lines not on this page · raw message

include/linux/sched.h +2 -0
diff -urNp linux-2.5.55-ms-ilb/include/linux/sched.h linux-2.5.55-ms-ilb-nb/include/linux/sched.h
@@ -450,11 +450,13 @@ extern void node_nr_running_init(void);
 	rq->nr_running++
 #define nr_running_dec(rq) atomic_dec(rq->node_ptr); \
 	rq->nr_running--
+#define decl_numa_int(ctr) int ctr
 #else
 #define sched_balance_exec() {}
 #define node_nr_running_init() {}
 #define nr_running_inc(rq) rq->nr_running++
 #define nr_running_dec(rq) rq->nr_running--
+#define decl_numa_int(ctr) {}
 #endif
 
 extern void set_user_nice(task_t *p, long nice);
kernel/sched.c +28 -0
diff -urNp linux-2.5.55-ms-ilb/kernel/sched.c linux-2.5.55-ms-ilb-nb/kernel/sched.c
@@ -154,6 +154,7 @@ struct runqueue {
 	prio_array_t *active, *expired, arrays[2];
 	int prev_nr_running[NR_CPUS];
 	atomic_t * node_ptr;
+	decl_numa_int(lb_cntr);
 
 	task_t *migration_thread;
 	struct list_head migration_queue;
@@ -703,6 +704,23 @@ void sched_balance_exec(void)
 			sched_migrate_task(current, new_cpu);
 	}
 }
+
+static int find_busiest_node(int this_node)
+{
+	int i, node = this_node, load, this_load, maxload;
+	
+	this_load = maxload = atomic_read(&node_nr_running[this_node]);
+	for (i = 0; i < numnodes; i++) {
+		if (i == this_node)
+			continue;
+		load = atomic_read(&node_nr_running[i]);
+		if (load > maxload && (4*load > ((5*4*this_load)/4))) {
+			maxload = load;
+			node = i;
+		}
+	}
+	return node;
+}
 #endif /* CONFIG_NUMA */
 
 #if CONFIG_SMP
@@ -816,6 +834,16 @@ out:
 static inline runqueue_t *find_busiest_queue(runqueue_t *this_rq, int this_cpu, int idle, int *imbalance)
 {
 	unsigned long cpumask = __node_to_cpu_mask(__cpu_to_node(this_cpu));
+#if CONFIG_NUMA
+	int node;
+#       define INTERNODE_LB 10
+
+	/* rebalance across nodes only every INTERNODE_LB call */
+	if (!(++(this_rq->lb_cntr) % INTERNODE_LB)) {
+		node = find_busiest_node(__cpu_to_node(this_cpu));
+		cpumask |= __node_to_cpu_mask(node);
+	}
+#endif
 	return find_busiest_in_mask(this_rq, this_cpu, idle, imbalance,
 				    cpumask);
 }
include/linux/sched.h +2 -0
diff -urNp linux-2.5.55-ms-ilb-nb/include/linux/sched.h linux-2.5.55-ms-ilb-nba/include/linux/sched.h
@@ -451,12 +451,14 @@ extern void node_nr_running_init(void);
 #define nr_running_dec(rq) atomic_dec(rq->node_ptr); \
 	rq->nr_running--
 #define decl_numa_int(ctr) int ctr
+#define decl_numa_nodeint(v) int v[MAX_NUMNODES]
 #else
 #define sched_balance_exec() {}
 #define node_nr_running_init() {}
 #define nr_running_inc(rq) rq->nr_running++
 #define nr_running_dec(rq) rq->nr_running--
 #define decl_numa_int(ctr) {}
+#define decl_numa_nodeint(v) {}
 #endif
 
 extern void set_user_nice(task_t *p, long nice);
kernel/sched.c +13 -2
diff -urNp linux-2.5.55-ms-ilb-nb/kernel/sched.c linux-2.5.55-ms-ilb-nba/kernel/sched.c
@@ -155,6 +155,7 @@ struct runqueue {
 	int prev_nr_running[NR_CPUS];
 	atomic_t * node_ptr;
 	decl_numa_int(lb_cntr);
+	decl_numa_nodeint(prev_node_load);
 
 	task_t *migration_thread;
 	struct list_head migration_queue;
@@ -705,15 +706,25 @@ void sched_balance_exec(void)
 	}
 }
 
+/*
+ * Find the busiest node. All previous node loads contribute with a geometrically
+ * deccaying weight to the load measure:
+ *      load_{t} = load_{t-1}/2 + nr_node_running_{t}
+ * This way sudden load peaks are flattened out a bit.
+ */
 static int find_busiest_node(int this_node)
 {
 	int i, node = this_node, load, this_load, maxload;
 	
-	this_load = maxload = atomic_read(&node_nr_running[this_node]);
+	this_load = maxload = (this_rq()->prev_node_load[this_node] >> 1)
+		+ atomic_read(&node_nr_running[this_node]);
+	this_rq()->prev_node_load[this_node] = this_load;
 	for (i = 0; i < numnodes; i++) {
 		if (i == this_node)
 			continue;
-		load = atomic_read(&node_nr_running[i]);
+		load = (this_rq()->prev_node_load[i] >> 1)
+			+ atomic_read(&node_nr_running[i]);
+		this_rq()->prev_node_load[i] = load;
 		if (load > maxload && (4*load > ((5*4*this_load)/4))) {
 			maxload = load;
 			node = i;
kernel/sched.c +16 -4
diff -urNp linux-2.5.55-ms-ilb-nba/kernel/sched.c linux-2.5.55-ms-ilb-nbav/kernel/sched.c
@@ -629,6 +629,9 @@ static inline void double_rq_unlock(runq
 
 #if CONFIG_NUMA
 static atomic_t node_nr_running[MAX_NUMNODES] ____cacheline_maxaligned_in_smp = {[0 ...MAX_NUMNODES-1] = ATOMIC_INIT(0)};
+#define MAX_INTERNODE_LB 40
+#define MIN_INTERNODE_LB 4
+static int internode_lb[MAX_NUMNODES] ____cacheline_maxaligned_in_smp = {[0 ...MAX_NUMNODES-1] = MAX_INTERNODE_LB};
 
 __init void node_nr_running_init(void)
 {
@@ -715,21 +718,31 @@ void sched_balance_exec(void)
 static int find_busiest_node(int this_node)
 {
 	int i, node = this_node, load, this_load, maxload;
+	int avg_load;
 	
 	this_load = maxload = (this_rq()->prev_node_load[this_node] >> 1)
 		+ atomic_read(&node_nr_running[this_node]);
 	this_rq()->prev_node_load[this_node] = this_load;
+	avg_load = this_load;
 	for (i = 0; i < numnodes; i++) {
 		if (i == this_node)
 			continue;
 		load = (this_rq()->prev_node_load[i] >> 1)
 			+ atomic_read(&node_nr_running[i]);
+		avg_load += load;
 		this_rq()->prev_node_load[i] = load;
 		if (load > maxload && (4*load > ((5*4*this_load)/4))) {
 			maxload = load;
 			node = i;
 		}
 	}
+	avg_load = avg_load / (numnodes ? numnodes : 1);
+	if (this_load < (avg_load / 2)) {
+		if (internode_lb[this_node] == MAX_INTERNODE_LB)
+			internode_lb[this_node] = MIN_INTERNODE_LB;
+	} else
+		if (internode_lb[this_node] == MIN_INTERNODE_LB)
+			internode_lb[this_node] = MAX_INTERNODE_LB;
 	return node;
 }
 #endif /* CONFIG_NUMA */
@@ -846,11 +859,10 @@ static inline runqueue_t *find_busiest_q
 {
 	unsigned long cpumask = __node_to_cpu_mask(__cpu_to_node(this_cpu));
 #if CONFIG_NUMA
-	int node;
-#       define INTERNODE_LB 10
+	int node, this_node = __cpu_to_node(this_cpu);
 
-	/* rebalance across nodes only every INTERNODE_LB call */
-	if (!(++(this_rq->lb_cntr) % INTERNODE_LB)) {
+	/* rarely rebalance across nodes */
+	if (!(++(this_rq->lb_cntr) % internode_lb[this_node])) {
 		node = find_busiest_node(__cpu_to_node(this_cpu));
 		cpumask |= __node_to_cpu_mask(node);
 	}
#6 lore raw

Re: NUMA scheduler 2nd approach

Quoted 6 lines · Erich Focht

Hi Martin & Michael,

as discussed on the LSE call I played around with a cross-node balancer approach put on top of the miniature NUMA scheduler. The patches are attached and it seems to be clear that we can regain the good performance for hackbench by adding a cross-node balancer.

The changes look fine to me. But I think there's some conding style issues that need cleaning up (see below). Also is there a reason patches 2/3 and 4/5 aren't merged into one patch each?

/*
- * find_busiest_queue - find the busiest runqueue.
+ * find_busiest_in_mask - find the busiest runqueue among the cpus in cpumask
*/
-static inline runqueue_t *find_busiest_queue(runqueue_t *this_rq, int this_cpu, int idle, int *imbalance) +static inline runqueue_t *find_busiest_in_mask(runqueue_t *this_rq, int this_cpu, int idle, int *imbalance, unsigned long cpumask)

find_busiest_queue has just one caller in 2.5.56, I'd suggest just changing the prototype and updating that single caller to pass in the cpumask opencoded.

@@ -160,7 +160,6 @@ extern void update_one_process(struct ta
extern void scheduler_tick(int user_tick, int system); extern unsigned long cache_decay_ticks;

-
#define MAX_SCHEDULE_TIMEOUT LONG_MAX
extern signed long FASTCALL(schedule_timeout(signed long timeout)); asmlinkage void schedule(void);

I don't think you need this spurious whitespace change :)

+#ifdef CONFIG_NUMA
+extern void sched_balance_exec(void);
+extern void node_nr_running_init(void); +#define nr_running_inc(rq) atomic_inc(rq->node_ptr); \
+ rq->nr_running++
+#define nr_running_dec(rq) atomic_dec(rq->node_ptr); \
+ rq->nr_running--

	static inline void nr_running_inc(runqueue_t *rq)
	{
		atomic_inc(rq->node_ptr);
		rq->nr_running++
	}

	etc.. would look a bit nicer.
kernel/sched.c +1 -0
diff -urNp linux-2.5.55-ms/kernel/sched.c linux-2.5.55-ms-ilb/kernel/sched.c
@@ -153,6 +153,7 @@ struct runqueue {
 	task_t *curr, *idle;
 	prio_array_t *active, *expired, arrays[2];
 	int prev_nr_running[NR_CPUS];
+	atomic_t * node_ptr;
 

atomic_t *node_ptr; would match the style above.

+#if CONFIG_NUMA
+static atomic_t node_nr_running[MAX_NUMNODES] ____cacheline_maxaligned_in_smp = {[0 ...MAX_NUMNODES-1] = ATOMIC_INIT(0)};

Maybe wants some linewrapping after 80 chars?

+__init void node_nr_running_init(void)
+{
+ int i;
+
+ for (i = 0; i < NR_CPUS; i++) {
+ cpu_rq(i)->node_ptr = &node_nr_running[__cpu_to_node(i)];
+ }
+ return;
+}

The braces and the return are superflous. Also kernel/sched.c (or mingo codein general) seems to prefer array + i instead of &array[i] (not that I have a general preferences, but you should try to match the surrounding code)

+static void sched_migrate_task(task_t *p, int dest_cpu) +{
+ unsigned long old_mask;
+
+ old_mask = p->cpus_allowed;
+ if (!(old_mask & (1UL << dest_cpu)))
+ return;
+ /* force the process onto the specified CPU */
+ set_cpus_allowed(p, 1UL << dest_cpu);
+
+ /* restore the cpus allowed mask */
+ set_cpus_allowed(p, old_mask);

	This double set_cpus_allowed doesn't look nice to me.  I don't
	have a better suggestion of-hand, though :(

+#define decl_numa_int(ctr) int ctr

This is ugly as hell. I'd prefer wasting one int in each runqueue or even an ifdef in the struct declaration over this obsfucation all the time.

@@ -816,6 +834,16 @@ out:
static inline runqueue_t *find_busiest_queue(runqueue_t *this_rq, int this_cpu, int idle, int *imbalance) {
unsigned long cpumask = __node_to_cpu_mask(__cpu_to_node(this_cpu));
+#if CONFIG_NUMA
+ int node;
+# define INTERNODE_LB 10

This wants to be put to the other magic constants in the scheduler and needs an explanation there.

#define nr_running_dec(rq) atomic_dec(rq->node_ptr); \
rq->nr_running--
#define decl_numa_int(ctr) int ctr
+#define decl_numa_nodeint(v) int v[MAX_NUMNODES]

Another one of those.. You should reall just stick the CONFIG_NUMA ifdef into the actual struct declaration.

+/*
+ * Find the busiest node. All previous node loads contribute with a geometrically
+ * deccaying weight to the load measure:

Linewrapping again..

#7 lore raw

Re: NUMA scheduler 2nd approach

Hi Christoph,

thanks for reviewing the code and the helpful comments!

Quoted 9 lines · Christoph Hellwig
Quoted 4 lines · Erich Focht

as discussed on the LSE call I played around with a cross-node balancer approach put on top of the miniature NUMA scheduler. The patches are attached and it seems to be clear that we can regain the good performance for hackbench by adding a cross-node balancer.

The changes look fine to me. But I think there's some conding style issues that need cleaning up (see below). Also is there a reason patches 2/3 and 4/5 aren't merged into one patch each?

The patches are separated by their functionality. Patch 2 comes from Michael Hohnbaum, so I kept that separate for that reason. Right now we can exchange the single components but when we decide that they are doing the job, I'd also prefer to have just one patch.

Quoted 10 lines

/*
- * find_busiest_queue - find the busiest runqueue.
+ * find_busiest_in_mask - find the busiest runqueue among the cpus in cpumask */
-static inline runqueue_t *find_busiest_queue(runqueue_t *this_rq, int this_cpu, int idle, int *imbalance) +static inline runqueue_t *find_busiest_in_mask(runqueue_t *this_rq, int this_cpu, int idle, int *imbalance, unsigned long cpumask)

Quoted 3 lines

find_busiest_queue has just one caller in 2.5.56, I'd suggest just changing the prototype and updating that single caller to pass in the cpumask opencoded.

Having find_busiest_queue() and find_busiest_in_mask() as separate function makes it simpler to merge in the cross-node balancer (patch 3). Otherwise we'd have to add two #ifdef CONFIG_NUMA blocks into load_balance() (one for new variable declarations, the other one for selecting the target node mask). We might have several calls to find_busiest_in_mask() later, if we decide to add multi-level node hierarchy support...

Quoted 1 line

I don't think you need this spurious whitespace change :)

:-) slipped in somehow.

Quoted 8 lines
(quoted diff) +7 -0
+#ifdef CONFIG_NUMA
+extern void sched_balance_exec(void);
+extern void node_nr_running_init(void);
+#define nr_running_inc(rq) atomic_inc(rq->node_ptr); \
+	rq->nr_running++
+#define nr_running_dec(rq) atomic_dec(rq->node_ptr); \
+	rq->nr_running--
Quoted 7 lines
	static inline void nr_running_inc(runqueue_t *rq)
	{
		atomic_inc(rq->node_ptr);
		rq->nr_running++
	}

	etc.. would look a bit nicer.

We can change this. Michael, ok with you?

Quoted 5 lines
(quoted diff) +2 -0
+#if CONFIG_NUMA
+static atomic_t node_nr_running[MAX_NUMNODES]

____cacheline_maxaligned_in_smp = {[0 ...MAX_NUMNODES-1] = ATOMIC_INIT(0)};

Maybe wants some linewrapping after 80 chars?

Yes.

Quoted 10 lines
(quoted diff) +5 -0
+	for (i = 0; i < NR_CPUS; i++) {
+		cpu_rq(i)->node_ptr = &node_nr_running[__cpu_to_node(i)];
+	}
+	return;
+}

The braces and the return are superflous. Also kernel/sched.c (or mingo codein general) seems to prefer array + i instead of &array[i] (not that I have a general preferences, but you should try to match the surrounding code)

Will change the braces and remove the return. I personally find &array[i] more readable.

Quoted 13 lines
(quoted diff) +12 -0
+static void sched_migrate_task(task_t *p, int dest_cpu)
+{
+	unsigned long old_mask;
+
+	old_mask = p->cpus_allowed;
+	if (!(old_mask & (1UL << dest_cpu)))
+		return;
+	/* force the process onto the specified CPU */
+	set_cpus_allowed(p, 1UL << dest_cpu);
+
+	/* restore the cpus allowed mask */
+	set_cpus_allowed(p, old_mask);
Quoted 2 lines
	This double set_cpus_allowed doesn't look nice to me.  I don't
	have a better suggestion of-hand, though :(

This is not that bad. It involves only one single wakeup of the migration thread, and that's more important. Doing it another way would mean to replicate the set_cpus_allowed() code.

Quoted 5 lines

+#define decl_numa_int(ctr) int ctr

This is ugly as hell. I'd prefer wasting one int in each runqueue or even an ifdef in the struct declaration over this obsfucation all the time.

Agreed :-) Just trying to avoid #ifdefs in sched.c as much as possible. Somehow had the feeling Linus doesn't like that. On the other hand: CONFIG_NUMA is a special case of CONFIG_SMP and nobody has anything against CONFIG_SMP in sched.c...

Review out: · line 842

Quoted 10 lines
(quoted diff) +3 -0
@@ -816,6 +834,16 @@ out:
 static inline runqueue_t *find_busiest_queue(runqueue_t *this_rq, int
 this_cpu, int idle, int *imbalance) {
 	unsigned long cpumask = __node_to_cpu_mask(__cpu_to_node(this_cpu));
+#if CONFIG_NUMA
+	int node;
+#       define INTERNODE_LB 10
 
 	This wants to be put to the other magic constants in the scheduler
 	and needs an explanation there.

We actually get rid of this in patch #5 (variable internode_lb, depending on the load of the current node). But ok, I'll move the MIN_INTERNODE_LB and MAX_INTERNODE_LB variables to the magic constants. They'll be outside the #ifdef CONFIG_NUMA block...

Thanks,

best regards,
Erich

#8 lore raw

Re: [Lse-tech] Re: NUMA scheduler 2nd approach

Anyone interested in this cleaned up minimal numa scheduler? This is basically Erich's patches 1-3 with my suggestions applied.

This does not mean I don't like 4 & 5, but I'd rather get a small, non-intrusive patch into Linus' tree now and do the fine-tuning later.

fs/exec.c +2 -0
@@ -1031,6 +1031,8 @@
 	int retval;
 	int i;
 
+	sched_balance_exec();
+
 	file = open_exec(filename);
 
 	retval = PTR_ERR(file);
include/linux/sched.h +8 -0
@@ -444,6 +444,14 @@
 # define set_cpus_allowed(p, new_mask) do { } while (0)
 #endif
 
+#ifdef CONFIG_NUMA
+extern void sched_balance_exec(void);
+extern void node_nr_running_init(void);
+#else
+# define sched_balance_exec()	do { } while (0)
+# define node_nr_running_init()	do { } while (0)
+#endif
+
 extern void set_user_nice(task_t *p, long nice);
 extern int task_prio(task_t *p);
 extern int task_nice(task_t *p);
init/main.c +1 -0
@@ -495,6 +495,7 @@
 
 	migration_init();
 #endif
+	node_nr_running_init();
 	spawn_ksoftirqd();
 }
 
kernel/sched.c +163 -10

248 lines not on this page · raw message

#9 lore raw

Re: [Lse-tech] Re: NUMA scheduler 2nd approach

Hi Christoph,

I just finished some experiments which show that the finetuning can really be left for later. So this approach is ok for me. I hope we can get enough support for integrating this tiny numa scheduler.

I didn't do all possible measurements, the interesting ones are with patches 1-4 (nb-smooth) and 1-5 (nb-sm-var1, nb-sm-var2) applied. They show pretty consistent results (within error bars). The fine-tuning in patch #5 doesn't buy us much right now (on my platform), so we can leave it out.

Here's the data:

Results on a 8 CPU ia64 machine with 4 nodes (2 CPUs per node).

kernbench:

                elapsed       user          system
      stock52   134.52(0.84)  951.64(0.97)  20.72(0.22)
      sched52   133.19(1.49)  944.24(0.50)  21.36(0.24)
   minsched52   135.47(0.47)  937.61(0.20)  21.30(0.14)
    nb-smooth   133.61(0.71)  944.71(0.35)  21.22(0.22)
   nb-sm-var1   135.23(2.07)  943.78(0.54)  21.54(0.17)
   nb-sm-var2   133.87(0.61)  944.18(0.62)  21.32(0.13)

schedbench/hackbench: time(s)

               10         25         50         100
      stock52  0.81(0.04) 2.06(0.07) 4.09(0.13) 7.89(0.25)
      sched52  0.81(0.04) 2.03(0.07) 4.14(0.20) 8.61(0.35)
   minsched52  1.28(0.05) 3.19(0.06) 6.59(0.13) 13.56(0.27)
    nb-smooth  0.77(0.03) 1.94(0.04) 3.80(0.06) 7.97(0.35)
   nb-sm-var1  0.81(0.05) 2.01(0.09) 3.89(0.21) 8.20(0.34)
   nb-sm-var2  0.82(0.04) 2.10(0.09) 4.19(0.14) 8.15(0.24)

numabench/numa_test 4

               AvgUserTime ElapsedTime TotUserTime TotSysTime
      stock52  ---         27.23(0.52) 89.30(4.18) 0.09(0.01)
      sched52  22.32(1.00) 27.39(0.42) 89.29(4.02) 0.10(0.01)
   minsched52  20.01(0.01) 23.40(0.13) 80.05(0.02) 0.08(0.01)
    nb-smooth  21.01(0.79) 24.70(2.75) 84.04(3.15) 0.09(0.01)
   nb-sm-var1  21.39(0.83) 26.03(2.15) 85.56(3.31) 0.09(0.01)
   nb-sm-var2  22.18(0.74) 27.36(0.42) 88.72(2.94) 0.09(0.01)

numabench/numa_test 8

               AvgUserTime ElapsedTime TotUserTime  TotSysTime
      stock52  ---         27.50(2.58) 174.74(6.66) 0.18(0.01)
      sched52  21.73(1.00) 33.70(1.82) 173.87(7.96) 0.18(0.01)
   minsched52  20.31(0.00) 23.50(0.12) 162.47(0.04) 0.16(0.01)
    nb-smooth  20.46(0.44) 24.21(1.95) 163.68(3.56) 0.16(0.01)
   nb-sm-var1  20.45(0.44) 23.95(1.73) 163.62(3.49) 0.17(0.01)
   nb-sm-var2  20.71(0.82) 23.78(2.42) 165.74(6.58) 0.17(0.01)

numabench/numa_test 16

               AvgUserTime ElapsedTime TotUserTime   TotSysTime
      stock52  ---         52.68(1.51) 390.03(15.10) 0.34(0.01)
      sched52  21.51(0.80) 47.18(3.24) 344.29(12.78) 0.36(0.01)
   minsched52  20.50(0.03) 43.82(0.08) 328.05(0.45)  0.34(0.01)
    nb-smooth  21.12(0.69) 47.42(4.02) 337.99(10.99) 0.34(0.01)
   nb-sm-var1  21.18(0.77) 48.19(5.05) 338.94(12.38) 0.34(0.01)
   nb-sm-var2  21.69(0.91) 49.05(4.36) 347.03(14.49) 0.34(0.01)

numabench/numa_test 32

               AvgUserTime ElapsedTime  TotUserTime   TotSysTime
      stock52  ---         102.60(3.89) 794.57(31.72) 0.65(0.01)
      sched52  21.93(0.57) 92.46(1.10)  701.75(18.38) 0.67(0.02)
   minsched52  20.64(0.10) 89.95(3.16)  660.72(3.13)  0.68(0.07)
    nb-smooth  20.95(0.19) 86.63(1.74)  670.56(6.02)  0.66(0.02)
   nb-sm-var1  21.47(0.54) 90.95(3.28)  687.12(17.42) 0.67(0.02)
   nb-sm-var2  21.45(0.67) 89.91(3.80)  686.47(21.37) 0.68(0.02)

The kernels used:
- stock52 : 2.5.52 + ia64 patch
- sched52 : stock52 + old numa scheduler
- minisched52 : stock52 + miniature NUMA scheduler (cannot load balance across nodes)
- nb-smooth : minisched52 + node balancer + smooth node load patch
- nb-sm-var1 : nb-smooth + variable internode_lb, (MIN,MAX) = (4,40)
- nb-sm-var2 : nb-smooth + variable internode_lb, (MIN,MAX) = (1,16)

Best regards,
Erich

Quoted 6 lines · Christoph Hellwig

Anyone interested in this cleaned up minimal numa scheduler? This is basically Erich's patches 1-3 with my suggestions applied.

This does not mean I don't like 4 & 5, but I'd rather get a small, non-intrusive patch into Linus' tree now and do the fine-tuning later.

[...]

#10 lore raw

Re: NUMA scheduler 2nd approach

In reply to Erich Focht
Quoted 11 lines · Erich Focht

Hi Christoph,

thanks for reviewing the code and the helpful comments!

Quoted 6 lines · Christoph Hellwig
Quoted 4 lines · Erich Focht

as discussed on the LSE call I played around with a cross-node balancer approach put on top of the miniature NUMA scheduler. The patches are attached and it seems to be clear that we can regain the good performance for hackbench by adding a cross-node balancer.

Quoted 8 lines
Quoted 3 lines

The changes look fine to me. But I think there's some conding style issues that need cleaning up (see below). Also is there a reason patches 2/3 and 4/5 aren't merged into one patch each?

The patches are separated by their functionality. Patch 2 comes from Michael Hohnbaum, so I kept that separate for that reason. Right now we can exchange the single components but when we decide that they are doing the job, I'd also prefer to have just one patch.

I'm not opposed to combining the patches, but isn't it typically preferred to have patches as small as possible? The initial load balance patch (patch 2) applies and functions fairly independent of the the other patches, so has been easy to maintain as a separate patch.

Quoted 16 lines
Quoted 16 lines
(quoted diff) +7 -0
+#ifdef CONFIG_NUMA
+extern void sched_balance_exec(void);
+extern void node_nr_running_init(void);
+#define nr_running_inc(rq) atomic_inc(rq->node_ptr); \
+	rq->nr_running++
+#define nr_running_dec(rq) atomic_dec(rq->node_ptr); \
+	rq->nr_running--
	static inline void nr_running_inc(runqueue_t *rq)
	{
		atomic_inc(rq->node_ptr);
		rq->nr_running++
	}
Quoted 3 lines
Quoted 1 line

etc.. would look a bit nicer.

We can change this. Michael, ok with you?

Fine with me.

Quoted 17 lines
Quoted 7 lines
(quoted diff) +2 -0
+#if CONFIG_NUMA
+static atomic_t node_nr_running[MAX_NUMNODES]

____cacheline_maxaligned_in_smp = {[0 ...MAX_NUMNODES-1] = ATOMIC_INIT(0)};

Maybe wants some linewrapping after 80 chars?

Yes.

Quoted 6 lines
(quoted diff) +5 -0
+	for (i = 0; i < NR_CPUS; i++) {
+		cpu_rq(i)->node_ptr = &node_nr_running[__cpu_to_node(i)];
+	}
+	return;
+}
Quoted 7 lines
Quoted 4 lines

The braces and the return are superflous. Also kernel/sched.c (or mingo codein general) seems to prefer array + i instead of &array[i] (not that I have a general preferences, but you should try to match the surrounding code)

Will change the braces and remove the return. I personally find &array[i] more readable.

I agree with Erich here - &array[i] is clearer.

Quoted 14 lines
Quoted 14 lines
(quoted diff) +12 -0
+static void sched_migrate_task(task_t *p, int dest_cpu)
+{
+	unsigned long old_mask;
+
+	old_mask = p->cpus_allowed;
+	if (!(old_mask & (1UL << dest_cpu)))
+		return;
+	/* force the process onto the specified CPU */
+	set_cpus_allowed(p, 1UL << dest_cpu);
+
+	/* restore the cpus allowed mask */
+	set_cpus_allowed(p, old_mask);
Quoted 6 lines
Quoted 2 lines
	This double set_cpus_allowed doesn't look nice to me.  I don't
	have a better suggestion of-hand, though :(

This is not that bad. It involves only one single wakeup of the migration thread, and that's more important. Doing it another way would mean to replicate the set_cpus_allowed() code.

While this shows up in the patch credited to me, it was actually Erich's idea, and I think a quite good one. My initial impression of this was that it was ugly, but upon closer examination (and trying to implement this some other way) realized that Erich's implementation, which I borrowed from, was quite good.

Good work Erich in getting the internode balancer written and working. I'm currently building a kernel with these patches and will post results later in the day. Thanks.

Signature · 2 lines
Michael Hohnbaum                      503-578-5486
[email protected]                   T/L 775-5486
#11 lore raw

Re: NUMA scheduler 2nd approach

In reply to Erich Focht
Quoted 6 lines · Erich Focht

Hi Martin & Michael,

as discussed on the LSE call I played around with a cross-node balancer approach put on top of the miniature NUMA scheduler. The patches are attached and it seems to be clear that we can regain the good performance for hackbench by adding a cross-node balancer.

Erich,

I played with this today on my 4 node (16 CPU) NUMAQ. Spent most of the time working with the first three patches. What I found was that rebalancing was happening too much between nodes. I tried a few things to change this, but have not yet settled on the best approach. A key item to work with is the check in find_busiest_node to determine if the found node is busier enough to warrant stealing from it. Currently the check is that the node has 125% of the load of the current node. I think that, for my system at least, we need to add in a constant to this equation. I tried using 4 and that helped a little. Finally I added in the 04 patch, and that helped a lot. Still, there is too much process movement between nodes.

Tomorrow, I will continue experiments, but base them on the first 4 patches. Two suggestions for minor changes:

* Make the check in find_busiest_node into a macro that is defined in the arch specific topology header file. Then different NUMA architectures can tune this appropriately.

* In find_busiest_queue change:

	cpumask |= __node_to_cpu_mask(node); 
  to:
	cpumask = __node_to_cpu_mask(node) | (1UL << (this_cpu));

There is no reason to iterate over the runqueues on the current node, which is what the code currently does.

Some numbers for anyone interested:Kernbench:

All numbers are based on a 2.5.55 kernel with the cputime stats patch:
* stock55 = no additional patches
* mini+rebal-44 = patches 01, 02, and 03
* rebal+4+fix = patches 01, 02, 03, and the cpumask change described above, and a +4 constant added to the check in find_busiest_node
* rebal+4+fix+04 = above with the 04 patch added

Elapsed User System CPU

   rebal+4+fix+04-55    29.302s   285.136s    82.106s      1253%
      rebal+4+fix-55    30.498s   286.586s    88.176s    1228.6%
       mini+rebal-55    30.756s   287.646s    85.512s    1212.8%
             stock55    31.018s   303.084s    86.626s    1256.2%

Schedbench 4:
AvgUser Elapsed TotalUser TotalSys

   rebal+4+fix+04-55      27.34      40.49     109.39       0.88
      rebal+4+fix-55      24.73      38.50      98.94       0.84
       mini+rebal-55      25.18      43.23     100.76       0.68
             stock55      31.38      41.55     125.54       1.24

Schedbench 8:
AvgUser Elapsed TotalUser TotalSys

   rebal+4+fix+04-55      30.05      44.15     240.48       2.50
      rebal+4+fix-55      34.33      46.40     274.73       2.31
       mini+rebal-55      32.99      52.42     264.00       2.08
             stock55      44.63      61.28     357.11       2.22

Schedbench 16:
AvgUser Elapsed TotalUser TotalSys

   rebal+4+fix+04-55      52.13      57.68     834.23       3.55
      rebal+4+fix-55      52.72      65.16     843.70       4.55
       mini+rebal-55      57.29      71.51     916.84       5.10
             stock55      66.91      85.08    1070.72       6.05

Schedbench 32:
AvgUser Elapsed TotalUser TotalSys

   rebal+4+fix+04-55      56.38     124.09    1804.67       7.71
      rebal+4+fix-55      55.13     115.18    1764.46       8.86
       mini+rebal-55      57.83     125.80    1850.84      10.19
             stock55      80.38     181.80    2572.70      13.22

Schedbench 64:
AvgUser Elapsed TotalUser TotalSys

   rebal+4+fix+04-55      57.42     238.32    3675.77      17.68
      rebal+4+fix-55      60.06     252.96    3844.62      18.88
       mini+rebal-55      58.15     245.30    3722.38      19.64
             stock55     123.96     513.66    7934.07      26.39

And here is the results from running numa_test 32 on rebal+4+fix+04:

Executing 32 times: ./randupdt 1000000 Running 'hackbench 20' in the background: Time: 8.383

Job  node00 node01 node02 node03 | iSched MSched | UserTime(s)
  1   100.0    0.0    0.0    0.0 |    0     0    |  56.19
  2   100.0    0.0    0.0    0.0 |    0     0    |  53.80
  3     0.0    0.0  100.0    0.0 |    2     2    |  55.61
  4   100.0    0.0    0.0    0.0 |    0     0    |  54.13
  5     3.7    0.0    0.0   96.3 |    3     3    |  56.48
  6     0.0    0.0  100.0    0.0 |    2     2    |  55.11
  7     0.0    0.0  100.0    0.0 |    2     2    |  55.94
  8     0.0    0.0  100.0    0.0 |    2     2    |  55.69
  9    80.6   19.4    0.0    0.0 |    1     0   *|  56.53
 10     0.0    0.0    0.0  100.0 |    3     3    |  53.00
 11     0.0   99.2    0.0    0.8 |    1     1    |  56.72
 12     0.0    0.0    0.0  100.0 |    3     3    |  54.58
 13     0.0  100.0    0.0    0.0 |    1     1    |  59.38
 14     0.0   55.6    0.0   44.4 |    3     1   *|  63.06
 15     0.0  100.0    0.0    0.0 |    1     1    |  56.02
 16     0.0   19.2    0.0   80.8 |    1     3   *|  58.07
 17     0.0  100.0    0.0    0.0 |    1     1    |  53.78
 18     0.0    0.0  100.0    0.0 |    2     2    |  55.28
 19     0.0   78.6    0.0   21.4 |    3     1   *|  63.20
 20     0.0  100.0    0.0    0.0 |    1     1    |  53.27
 21     0.0    0.0  100.0    0.0 |    2     2    |  55.79
 22     0.0    0.0    0.0  100.0 |    3     3    |  57.23
 23    12.4   19.1    0.0   68.5 |    1     3   *|  61.05
 24     0.0    0.0  100.0    0.0 |    2     2    |  54.50
 25     0.0    0.0    0.0  100.0 |    3     3    |  56.82
 26     0.0    0.0  100.0    0.0 |    2     2    |  56.28
 27    15.3    0.0    0.0   84.7 |    3     3    |  57.12
 28   100.0    0.0    0.0    0.0 |    0     0    |  53.85
 29    32.7   67.2    0.0    0.0 |    0     1   *|  62.66
 30   100.0    0.0    0.0    0.0 |    0     0    |  53.86
 31   100.0    0.0    0.0    0.0 |    0     0    |  53.94
 32   100.0    0.0    0.0    0.0 |    0     0    |  55.36
AverageUserTime 56.38 seconds
ElapsedTime     124.09
TotalUserTime   1804.67
TotalSysTime    7.71

Ideally, there would be nothing but 100.0 in all non-zero entries. I'll try adding in the 05 patch, and if that does not help, will try a few other adjustments.

Thanks for the quick effort on putting together the node rebalance code. I'll also get some hackbench numbers soon.

Signature · 2 lines
Michael Hohnbaum                      503-578-5486
[email protected]                   T/L 775-5486
#12 lore raw

Re: [Lse-tech] Re: NUMA scheduler 2nd approach

Quoted 12 lines

Erich,

I played with this today on my 4 node (16 CPU) NUMAQ. Spent most of the time working with the first three patches. What I found was that rebalancing was happening too much between nodes. I tried a few things to change this, but have not yet settled on the best approach. A key item to work with is the check in find_busiest_node to determine if the found node is busier enough to warrant stealing from it. Currently the check is that the node has 125% of the load of the current node. I think that, for my system at least, we need to add in a constant to this equation. I tried using 4 and that helped a little.

Michael,

in:

+static int find_busiest_node(int this_node)
+{
+ int i, node = this_node, load, this_load, maxload;
+
+ this_load = maxload = atomic_read(&node_nr_running[this_node]);
+ for (i = 0; i < numnodes; i++) {
+ if (i == this_node)
+ continue;
+ load = atomic_read(&node_nr_running[i]);
+ if (load > maxload && (4*load > ((5*4*this_load)/4))) {
+ maxload = load;
+ node = i;
+ }
+ }
+ return node;
+}

You changed ((5*4*this_load)/4) to:
(5*4*(this_load+4)/4)
or
(4+(5*4*(this_load)/4)) ?

We def need some constant to avoid low load ping pong, right?

Finally I added in the 04 patch, and that helped

Quoted 1 line

a lot. Still, there is too much process movement between nodes.

perhaps increase INTERNODE_LB?

-Andrew Theurer

#13 lore raw

Re: [Lse-tech] Re: NUMA scheduler 2nd approach

Quoted 37 lines
Quoted 10 lines

I played with this today on my 4 node (16 CPU) NUMAQ. Spent most of the time working with the first three patches. What I found was that rebalancing was happening too much between nodes. I tried a few things to change this, but have not yet settled on the best approach. A key item to work with is the check in find_busiest_node to determine if the found node is busier enough to warrant stealing from it. Currently the check is that the node has 125% of the load of the current node. I think that, for my system at least, we need to add in a constant to this equation. I tried using 4 and that helped a little.

Michael,

in:

kernel/sched.c +16 -0
+static int find_busiest_node(int this_node)
+{
+ int i, node = this_node, load, this_load, maxload;
+ 
+ this_load = maxload = atomic_read(&node_nr_running[this_node]);
+ for (i = 0; i < numnodes; i++) {
+  if (i == this_node)
+   continue;
+  load = atomic_read(&node_nr_running[i]);
+  if (load > maxload && (4*load > ((5*4*this_load)/4))) {
+   maxload = load;
+   node = i;
+  }
+ }
+ return node;
+}

You changed ((5*4*this_load)/4) to:
(5*4*(this_load+4)/4)
or
(4+(5*4*(this_load)/4)) ?

Quoted 6 lines

We def need some constant to avoid low load ping pong, right?

Finally I added in the 04 patch, and that helped

Quoted 1 line

a lot. Still, there is too much process movement between nodes.

perhaps increase INTERNODE_LB?

Before we tweak this too much, how about using the global load average for this? I can envisage a situation where we have two nodes with 8 tasks per node, one with 12 tasks, and one with four. You really don't want the ones with 8 tasks pulling stuff from the 12 ... only for the least loaded node to start pulling stuff later.

What about if we take the global load average, and multiply by num_cpus_on_this_node / num_cpus_globally ... that'll give us roughly what we should have on this node. If we're significantly out underloaded compared to that, we start pulling stuff from the busiest node? And you get the damping over time for free.

I think it'd be best if we stay fairly conservative for this, all we're trying to catch is the corner case where a bunch of stuff has forked, but not execed, and we have a long term imbalance. Agressive rebalance might win a few benchmarks, but you'll just cause inter-node task bounce on others.

M.

#14 lore raw

Re: [Lse-tech] Re: NUMA scheduler 2nd approach

Hi Martin,

Quoted 6 lines

Before we tweak this too much, how about using the global load average for this? I can envisage a situation where we have two nodes with 8 tasks per node, one with 12 tasks, and one with four. You really don't want the ones with 8 tasks pulling stuff from the 12 ... only for the least loaded node to start pulling stuff later.

Hmmm, yet another idea from the old NUMA scheduler coming back, therefore it has my full support ;-). Though we can't do it as I did it there: in the old NUMA approach every cross-node steal was delayed, only 1-2ms if the own node was underloaded, a lot more if the own node's load was average or above average. We might need to finally steal something even if we're having "above average" load, because the cpu mask of the tasks on the overloaded node might only allow them to migrate to us... But this is also a special case which we should solve later.

Quoted 5 lines

What about if we take the global load average, and multiply by num_cpus_on_this_node / num_cpus_globally ... that'll give us roughly what we should have on this node. If we're significantly out underloaded compared to that, we start pulling stuff from the busiest node? And you get the damping over time for free.

Patch 05 is going towards this direction but the constants I chose were very aggressive. I'll update the whole set of patches and try to send out something today.

Best regards,
Erich

#15 lore raw

PATCH 1/1 new NUMA scheduler

Here's the new version of the NUMA scheduler built on top of the miniature scheduler of Martin. I incorporated Michael's ideas and Christoph's suggestions and rediffed for 2.5.58.

The whole patch is really tiny: 9.5k. This time I attached the numa scheduler in form of two patches:

numa-sched-2.5.58.patch (7k) : components 01, 02, 03
numa-sched-add-2.5.58.patch (3k) : components 04, 05

The single components are also attached in a small tgz archive:

01-minisched-2.5.58.patch : the miniature scheduler from Martin. Balances strictly within a node. Removed the find_busiest_in_mask() function.

02-initial-lb-2.5.58.patch : Michael's initial load balancer at exec(). Cosmetic corrections sugegsted by Christoph.

03-internode-lb-2.5.58.patch : internode load balancer core. Called after NODE_BALANCE_RATE calls of the inter-node load balancer. Tunable parameters:
NODE_BALANCE_RATE (default: 10)
NODE_THRESHOLD (default: 125) : consider only nodes with load
above NODE_THRESHOLD/100 * own_node_load
I added the constant factor of 4 suggested by Michael, but I'm not really happy with it. This should be nr_cpus_in_node, but we don't have that info in topology.h

04-smooth-node-load-2.5.58.patch : The node load measure is smoothed by adding half of the previous node load (and 1/4 of the one before, etc..., as discussed in the LSE call). This should improve a bit the behavior in case of short timed load peaks and avoid bouncing tasks between nodes.

05-var-intnode-lb-2.5.58.patch : Replaces the fixed NODE_BALANCE_RATE interval (between cross-node balancer calls) by a variable node-specific interval. Currently only two values used:
NODE_BALANCE_MIN : 10
NODE_BALANCE_MAX : 40
If the node load is less than avg_node_load/2, we switch to NODE_BALANCE_MIN, otherwise we use the large interval.
I also added a function to reduce the number of tasks stolen from remote nodes.

Regards,
Erich

fs/exec.c +2 -0
diff -urNp 2.5.58/fs/exec.c 2.5.58-ms-ilb-nb/fs/exec.c
@@ -1031,6 +1031,8 @@ int do_execve(char * filename, char ** a
 	int retval;
 	int i;
 
+	sched_balance_exec();
+
 	file = open_exec(filename);
 
 	retval = PTR_ERR(file);
include/linux/sched.h +22 -1
diff -urNp 2.5.58/include/linux/sched.h 2.5.58-ms-ilb-nb/include/linux/sched.h
@@ -160,7 +160,6 @@ extern void update_one_process(struct ta
 extern void scheduler_tick(int user_tick, int system);
 extern unsigned long cache_decay_ticks;
 
-
 #define	MAX_SCHEDULE_TIMEOUT	LONG_MAX
 extern signed long FASTCALL(schedule_timeout(signed long timeout));
 asmlinkage void schedule(void);
@@ -444,6 +443,28 @@ extern void set_cpus_allowed(task_t *p, 
 # define set_cpus_allowed(p, new_mask) do { } while (0)
 #endif
 
+#ifdef CONFIG_NUMA
+extern void sched_balance_exec(void);
+extern void node_nr_running_init(void);
+
+static inline void nr_running_inc(runqueue_t *rq)
+{
+	atomic_inc(rq->node_ptr);
+	rq->nr_running++;
+}
+
+static inline void nr_running_dec(runqueue_t *rq)
+{
+	atomic_dec(rq->node_ptr);
+	rq->nr_running--;
+}
+#else
+#define sched_balance_exec() {}
+#define node_nr_running_init() {}
+#define nr_running_inc(rq) rq->nr_running++
+#define nr_running_dec(rq) rq->nr_running--
+#endif
+
 extern void set_user_nice(task_t *p, long nice);
 extern int task_prio(task_t *p);
 extern int task_nice(task_t *p);
init/main.c +1 -0
diff -urNp 2.5.58/init/main.c 2.5.58-ms-ilb-nb/init/main.c
@@ -495,6 +495,7 @@ static void do_pre_smp_initcalls(void)
 
 	migration_init();
 #endif
+	node_nr_running_init();
 	spawn_ksoftirqd();
 }
 
kernel/sched.c +130 -9

202 lines not on this page · raw message

kernel/sched.c +38 -5

90 lines not on this page · raw message

#16 lore raw

Re: [Lse-tech] [PATCH 2.5.58] new NUMA scheduler

Quoted 3 lines · Erich Focht

Here's the new version of the NUMA scheduler built on top of the miniature scheduler of Martin. I incorporated Michael's ideas and Christoph's suggestions and rediffed for 2.5.58.

This one looks a lot nicer. You might also want to take the different nr_running stuff from the patch I posted, I think it looks a lot nicer.

The patch (not updated yet) is below again for reference.

fs/exec.c +2 -0
@@ -1031,6 +1031,8 @@
 	int retval;
 	int i;
 
+	sched_balance_exec();
+
 	file = open_exec(filename);
 
 	retval = PTR_ERR(file);
include/linux/sched.h +8 -0
@@ -444,6 +444,14 @@
 # define set_cpus_allowed(p, new_mask) do { } while (0)
 #endif
 
+#ifdef CONFIG_NUMA
+extern void sched_balance_exec(void);
+extern void node_nr_running_init(void);
+#else
+# define sched_balance_exec()	do { } while (0)
+# define node_nr_running_init()	do { } while (0)
+#endif
+
 extern void set_user_nice(task_t *p, long nice);
 extern int task_prio(task_t *p);
 extern int task_nice(task_t *p);
init/main.c +1 -0
@@ -495,6 +495,7 @@
 
 	migration_init();
 #endif
+	node_nr_running_init();
 	spawn_ksoftirqd();
 }
 
kernel/sched.c +163 -10

248 lines not on this page · raw message

#17 lore raw

PATCH 1/1 new NUMA scheduler: fix

In reply to Erich Focht

In the previous email the patch 02-initial-lb-2.5.58.patch had a bug and this was present in the numa-sched-2.5.58.patch and numa-sched-add-2.5.58.patch, too. Please use the patches attached to this email! Sorry for the silly mistake...

Christoph, I used your way of coding nr_running_inc/dec now.

Regards,
Erich

Quoted 45 lines · Erich Focht

Here's the new version of the NUMA scheduler built on top of the miniature scheduler of Martin. I incorporated Michael's ideas and Christoph's suggestions and rediffed for 2.5.58.

The whole patch is really tiny: 9.5k. This time I attached the numa scheduler in form of two patches:

numa-sched-2.5.58.patch (7k) : components 01, 02, 03
numa-sched-add-2.5.58.patch (3k) : components 04, 05

The single components are also attached in a small tgz archive:

01-minisched-2.5.58.patch : the miniature scheduler from Martin. Balances strictly within a node. Removed the find_busiest_in_mask() function.

02-initial-lb-2.5.58.patch : Michael's initial load balancer at exec(). Cosmetic corrections sugegsted by Christoph.

03-internode-lb-2.5.58.patch : internode load balancer core. Called after NODE_BALANCE_RATE calls of the inter-node load balancer. Tunable parameters:
NODE_BALANCE_RATE (default: 10)
NODE_THRESHOLD (default: 125) : consider only nodes with load
above NODE_THRESHOLD/100 * own_node_load
I added the constant factor of 4 suggested by Michael, but I'm not really happy with it. This should be nr_cpus_in_node, but we don't have that info in topology.h

04-smooth-node-load-2.5.58.patch : The node load measure is smoothed by adding half of the previous node load (and 1/4 of the one before, etc..., as discussed in the LSE call). This should improve a bit the behavior in case of short timed load peaks and avoid bouncing tasks between nodes.

05-var-intnode-lb-2.5.58.patch : Replaces the fixed NODE_BALANCE_RATE interval (between cross-node balancer calls) by a variable node-specific interval. Currently only two values used:
NODE_BALANCE_MIN : 10
NODE_BALANCE_MAX : 40
If the node load is less than avg_node_load/2, we switch to NODE_BALANCE_MIN, otherwise we use the large interval.
I also added a function to reduce the number of tasks stolen from remote nodes.

Quoted 2 lines

Regards,
Erich

fs/exec.c +2 -0
diff -urNp 2.5.58/fs/exec.c 2.5.58-ms-ilb-nb/fs/exec.c
@@ -1031,6 +1031,8 @@ int do_execve(char * filename, char ** a
 	int retval;
 	int i;
 
+	sched_balance_exec();
+
 	file = open_exec(filename);
 
 	retval = PTR_ERR(file);
include/linux/sched.h +7 -1
diff -urNp 2.5.58/include/linux/sched.h 2.5.58-ms-ilb-nb/include/linux/sched.h
@@ -160,7 +160,6 @@ extern void update_one_process(struct ta
 extern void scheduler_tick(int user_tick, int system);
 extern unsigned long cache_decay_ticks;
 
-
 #define	MAX_SCHEDULE_TIMEOUT	LONG_MAX
 extern signed long FASTCALL(schedule_timeout(signed long timeout));
 asmlinkage void schedule(void);
@@ -444,6 +443,13 @@ extern void set_cpus_allowed(task_t *p, 
 # define set_cpus_allowed(p, new_mask) do { } while (0)
 #endif
 
+#ifdef CONFIG_NUMA
+extern void sched_balance_exec(void);
+extern void node_nr_running_init(void);
+#else
+#define sched_balance_exec() {}
+#endif
+
 extern void set_user_nice(task_t *p, long nice);
 extern int task_prio(task_t *p);
 extern int task_nice(task_t *p);
init/main.c +1 -0
diff -urNp 2.5.58/init/main.c 2.5.58-ms-ilb-nb/init/main.c
@@ -495,6 +495,7 @@ static void do_pre_smp_initcalls(void)
 
 	migration_init();
 #endif
+	node_nr_running_init();
 	spawn_ksoftirqd();
 }
 
kernel/sched.c +148 -9

226 lines not on this page · raw message

kernel/sched.c +38 -5

90 lines not on this page · raw message

#18 lore raw

PATCH 1/1 new NUMA scheduler: fix

Aargh, I should have gone home earlier...
For those who really care about patch 05, it's attached. It's all untested as I don't have a ia32 NUMA machine running 2.5.58...

Erich

Quoted 9 lines · Erich Focht

In the previous email the patch 02-initial-lb-2.5.58.patch had a bug and this was present in the numa-sched-2.5.58.patch and numa-sched-add-2.5.58.patch, too. Please use the patches attached to this email! Sorry for the silly mistake...

Christoph, I used your way of coding nr_running_inc/dec now.

Regards,
Erich

kernel/sched.c +26 -4
diff -urNp 2.5.58-ms-ilb-nb-sm/kernel/sched.c 2.5.58-ms-ilb-nb-sm-var/kernel/sched.c
@@ -67,8 +67,9 @@
 #define INTERACTIVE_DELTA	2
 #define MAX_SLEEP_AVG		(2*HZ)
 #define STARVATION_LIMIT	(2*HZ)
-#define NODE_BALANCE_RATIO	10
 #define NODE_THRESHOLD          125
+#define NODE_BALANCE_MIN	10
+#define NODE_BALANCE_MAX	40
 
 /*
  * If a task is 'interactive' then we reinsert it in the active
@@ -186,6 +187,8 @@ static struct runqueue runqueues[NR_CPUS
 #if CONFIG_NUMA
 static atomic_t node_nr_running[MAX_NUMNODES] ____cacheline_maxaligned_in_smp =
 	{[0 ...MAX_NUMNODES-1] = ATOMIC_INIT(0)};
+static int internode_lb[MAX_NUMNODES] ____cacheline_maxaligned_in_smp =
+	{[0 ...MAX_NUMNODES-1] = NODE_BALANCE_MAX};
 
 static inline void nr_running_inc(runqueue_t *rq)
 {
@@ -735,15 +738,18 @@ void sched_balance_exec(void)
 static int find_busiest_node(int this_node)
 {
 	int i, node = -1, load, this_load, maxload;
+	int avg_load;
 	
 	this_load = maxload = (this_rq()->prev_node_load[this_node] >> 1)
 		+ atomic_read(&node_nr_running[this_node]);
 	this_rq()->prev_node_load[this_node] = this_load;
+	avg_load = this_load;
 	for (i = 0; i < numnodes; i++) {
 		if (i == this_node)
 			continue;
 		load = (this_rq()->prev_node_load[i] >> 1)
 			+ atomic_read(&node_nr_running[i]);
+		avg_load += load;
 		this_rq()->prev_node_load[i] = load;
 		if (load > maxload &&
 		    (100*load > ((NODE_THRESHOLD*100*this_load)/100))) {
@@ -751,10 +757,26 @@ static int find_busiest_node(int this_no
 			node = i;
 		}
 	}
-	if (maxload <= 4+2+1)
+	avg_load = avg_load / (numnodes ? numnodes : 1);
+	if (this_load < (avg_load / 2)) {
+		if (internode_lb[this_node] == NODE_BALANCE_MAX)
+			internode_lb[this_node] = NODE_BALANCE_MIN;
+	} else
+		if (internode_lb[this_node] == NODE_BALANCE_MIN)
+			internode_lb[this_node] = NODE_BALANCE_MAX;
+	if (maxload <= 4+2+1 || this_load >= avg_load)
 		node = -1;
 	return node;
 }
+
+static inline int remote_steal_factor(runqueue_t *rq)
+{
+	int cpu = __cpu_to_node(task_cpu(rq->curr));
+
+	return (cpu == __cpu_to_node(smp_processor_id())) ? 1 : 2;
+}
+#else
+#define remote_steal_factor(rq) 1
 #endif /* CONFIG_NUMA */
 
 #if CONFIG_SMP
@@ -903,7 +925,7 @@ static void load_balance(runqueue_t *thi
 	/*
 	 * Avoid rebalancing between nodes too often.
 	 */
-	if (!(++(this_rq->nr_balanced) % NODE_BALANCE_RATIO)) {
+	if (!(++(this_rq->nr_balanced) % internode_lb[this_node])) {
 		int node = find_busiest_node(this_node);
 		if (node >= 0)
 			cpumask = __node_to_cpu_mask(node) | (1UL << this_cpu);
@@ -967,7 +989,7 @@ skip_queue:
 		goto skip_bitmap;
 	}
 	pull_task(busiest, array, tmp, this_rq, this_cpu);
-	if (!idle && --imbalance) {
+	if (!idle && ((--imbalance)/remote_steal_factor(busiest))) {
 		if (curr != head)
 			goto skip_queue;
 		idx++;
#19 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

Quoted 3 lines · Erich Focht

Aargh, I should have gone home earlier...
For those who really care about patch 05, it's attached. It's all untested as I don't have a ia32 NUMA machine running 2.5.58...

One more minor problem - the first two patches are missing the following defines, and result in compile issues:

#define MAX_INTERNODE_LB 40
#define MIN_INTERNODE_LB 4
#define NODE_BALANCE_RATIO 10

Looking through previous patches, and the 05 patch, I found these defines and put them under the #if CONFIG_NUMA in sched.c that defines node_nr_running and friends.

With these three lines added, I have a kernel built and booted using the first numa-sched and numa-sched-add patches.

Test results will follow later in the day.

Michael

Quoted 14 lines

Erich

Quoted 9 lines · Erich Focht

In the previous email the patch 02-initial-lb-2.5.58.patch had a bug and this was present in the numa-sched-2.5.58.patch and numa-sched-add-2.5.58.patch, too. Please use the patches attached to this email! Sorry for the silly mistake...

Christoph, I used your way of coding nr_running_inc/dec now.

Regards,
Erich

Signature · 2 lines
Michael Hohnbaum                      503-578-5486
[email protected]                   T/L 775-5486
#20 lore raw

Re: [Lse-tech] Re: [PATCH 2.5.58] new NUMA scheduler: fix

Quoted 12 lines · Michael Hohnbaum
Quoted 3 lines · Erich Focht

Aargh, I should have gone home earlier...
For those who really care about patch 05, it's attached. It's all untested as I don't have a ia32 NUMA machine running 2.5.58...

One more minor problem - the first two patches are missing the following defines, and result in compile issues:

#define MAX_INTERNODE_LB 40
#define MIN_INTERNODE_LB 4
#define NODE_BALANCE_RATIO 10

Quoted 8 lines

Looking through previous patches, and the 05 patch, I found these defines and put them under the #if CONFIG_NUMA in sched.c that defines node_nr_running and friends.

With these three lines added, I have a kernel built and booted using the first numa-sched and numa-sched-add patches.

Test results will follow later in the day.

Trying to apply the 05 patch, I discovered that it was already in there. Something is messed up with the combined patches, so I went back to the tgz file you provided and started over. I'm not sure what the kernel is that I built and tested earlier today, but I suspect it was, for the most part, the complete patchset (i.e., patches 1-5). Building a kernel with patches 1-4 from the tgz file does not need the additional defines mentioned in my previous email.

Testing is starting from scratch with a known patch base. The plan is to test with patches 1-4, then add in 05. I should have some numbers for you before the end of my day. btw, the numbers looked real good for the runs on whatever kernel it was that I built this morning.

Quoted 4 lines

Michael

Quoted 1 line

Erich

Signature · 2 lines
Michael Hohnbaum                      503-578-5486
[email protected]                   T/L 775-5486
#21 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

In reply to Michael Hohnbaum

Thanks for the patience with the problems in the yesterday patches. I resend the patches in the same form. Made following changes:

- moved NODE_BALANCE_{RATE,MIN,MAX} to topology.h
- removed the divide in the find_busiest_node() loop (thanks, Martin)
- removed the modulo (%) in in the cross-node balancing trigger
- re-added node_nr_running_init() stub, nr_running_init() and comments from Christoph
- removed the constant factor 4 in find_busiest_node. The find_busiest_queue routine will take care of the case where the busiest_node is running only few processes (at most one per CPU) and return busiest=NULL .

I hope we can start tuning the parameters now. In the basic NUMA scheduler part these are:
NODE_THRESHOLD : minimum percentage of node overload to
trigger cross-node balancing
NODE_BALANCE_RATE : arch specific, cross-node balancing is called
after this many intra-node load balance calls

In the extended NUMA scheduler the fixed value of NODE_BALANCE_RATE is replaced by a variable rate set to :
NODE_BALANCE_MIN : if own node load is less then avg_load/2 NODE_BALANCE_MAX : if load is larger than avg_load/2
Together with the reduced number of steals across nodes this might help us in achieving equal load among nodes. I'm not aware of any simple benchmark which can demonstrate this...

Regards,
Erich

fs/exec.c +2 -0
diff -urNp 2.5.58/fs/exec.c 2.5.58-ms-ilb-nb/fs/exec.c
@@ -1031,6 +1031,8 @@ int do_execve(char * filename, char ** a
 	int retval;
 	int i;
 
+	sched_balance_exec();
+
 	file = open_exec(filename);
 
 	retval = PTR_ERR(file);
include/asm-generic/topology.h +5 -0
diff -urNp 2.5.58/include/asm-generic/topology.h 2.5.58-ms-ilb-nb/include/asm-generic/topology.h
@@ -48,4 +48,9 @@
 #define __node_to_memblk(node)		(0)
 #endif
 
+/* Cross-node load balancing interval. */
+#ifndef NODE_BALANCE_RATE
+#define NODE_BALANCE_RATE 10
+#endif
+
 #endif /* _ASM_GENERIC_TOPOLOGY_H */
include/asm-i386/topology.h +3 -0
diff -urNp 2.5.58/include/asm-i386/topology.h 2.5.58-ms-ilb-nb/include/asm-i386/topology.h
@@ -61,6 +61,9 @@ static inline int __node_to_first_cpu(in
 /* Returns the number of the first MemBlk on Node 'node' */
 #define __node_to_memblk(node) (node)
 
+/* Cross-node load balancing interval. */
+#define NODE_BALANCE_RATE 100
+
 #else /* !CONFIG_NUMA */
 /*
  * Other i386 platforms should define their own version of the 
include/asm-ia64/topology.h +3 -0
diff -urNp 2.5.58/include/asm-ia64/topology.h 2.5.58-ms-ilb-nb/include/asm-ia64/topology.h
@@ -60,4 +60,7 @@
  */
 #define __node_to_memblk(node) (node)
 
+/* Cross-node load balancing interval. */
+#define NODE_BALANCE_RATE 10
+
 #endif /* _ASM_IA64_TOPOLOGY_H */
include/asm-ppc64/topology.h +3 -0
diff -urNp 2.5.58/include/asm-ppc64/topology.h 2.5.58-ms-ilb-nb/include/asm-ppc64/topology.h
@@ -46,6 +46,9 @@ static inline unsigned long __node_to_cp
 	return mask;
 }
 
+/* Cross-node load balancing interval. */
+#define NODE_BALANCE_RATE 10
+
 #else /* !CONFIG_NUMA */
 
 #define __cpu_to_node(cpu)		(0)
include/linux/sched.h +8 -1
diff -urNp 2.5.58/include/linux/sched.h 2.5.58-ms-ilb-nb/include/linux/sched.h
@@ -160,7 +160,6 @@ extern void update_one_process(struct ta
 extern void scheduler_tick(int user_tick, int system);
 extern unsigned long cache_decay_ticks;
 
-
 #define	MAX_SCHEDULE_TIMEOUT	LONG_MAX
 extern signed long FASTCALL(schedule_timeout(signed long timeout));
 asmlinkage void schedule(void);
@@ -444,6 +443,14 @@ extern void set_cpus_allowed(task_t *p, 
 # define set_cpus_allowed(p, new_mask) do { } while (0)
 #endif
 
+#ifdef CONFIG_NUMA
+extern void sched_balance_exec(void);
+extern void node_nr_running_init(void);
+#else
+#define sched_balance_exec()   {}
+#define node_nr_running_init() {}
+#endif
+
 extern void set_user_nice(task_t *p, long nice);
 extern int task_prio(task_t *p);
 extern int task_nice(task_t *p);
init/main.c +1 -0
diff -urNp 2.5.58/init/main.c 2.5.58-ms-ilb-nb/init/main.c
@@ -495,6 +495,7 @@ static void do_pre_smp_initcalls(void)
 
 	migration_init();
 #endif
+	node_nr_running_init();
 	spawn_ksoftirqd();
 }
 
kernel/sched.c +155 -10

238 lines not on this page · raw message

include/asm-generic/topology.h +5 -2
diff -urNp 2.5.58-ms-ilb-nb/include/asm-generic/topology.h 2.5.58-ms-ilb-nb-sm-var/include/asm-generic/topology.h
@@ -49,8 +49,11 @@
 #endif
 
 /* Cross-node load balancing interval. */
-#ifndef NODE_BALANCE_RATE
-#define NODE_BALANCE_RATE 10
+#ifndef NODE_BALANCE_MIN
+#define NODE_BALANCE_MIN 10
+#endif
+#ifndef NODE_BALANCE_MAX
+#define NODE_BALANCE_MAX 50
 #endif
 
 #endif /* _ASM_GENERIC_TOPOLOGY_H */
include/asm-i386/topology.h +2 -1
diff -urNp 2.5.58-ms-ilb-nb/include/asm-i386/topology.h 2.5.58-ms-ilb-nb-sm-var/include/asm-i386/topology.h
@@ -62,7 +62,8 @@ static inline int __node_to_first_cpu(in
 #define __node_to_memblk(node) (node)
 
 /* Cross-node load balancing interval. */
-#define NODE_BALANCE_RATE 100
+#define NODE_BALANCE_MIN 10
+#define NODE_BALANCE_MAX 250
 
 #else /* !CONFIG_NUMA */
 /*
include/asm-ia64/topology.h +2 -1
diff -urNp 2.5.58-ms-ilb-nb/include/asm-ia64/topology.h 2.5.58-ms-ilb-nb-sm-var/include/asm-ia64/topology.h
@@ -61,6 +61,7 @@
 #define __node_to_memblk(node) (node)
 
 /* Cross-node load balancing interval. */
-#define NODE_BALANCE_RATE 10
+#define NODE_BALANCE_MIN 10
+#define NODE_BALANCE_MAX 50
 
 #endif /* _ASM_IA64_TOPOLOGY_H */
include/asm-ppc64/topology.h +2 -1
diff -urNp 2.5.58-ms-ilb-nb/include/asm-ppc64/topology.h 2.5.58-ms-ilb-nb-sm-var/include/asm-ppc64/topology.h
@@ -47,7 +47,8 @@ static inline unsigned long __node_to_cp
 }
 
 /* Cross-node load balancing interval. */
-#define NODE_BALANCE_RATE 10
+#define NODE_BALANCE_MIN 10
+#define NODE_BALANCE_MAX 50
 
 #else /* !CONFIG_NUMA */
 
kernel/sched.c +38 -4

86 lines not on this page · raw message

#22 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

Quoted 12 lines · Erich Focht

Thanks for the patience with the problems in the yesterday patches. I resend the patches in the same form. Made following changes:

- moved NODE_BALANCE_{RATE,MIN,MAX} to topology.h
- removed the divide in the find_busiest_node() loop (thanks, Martin)
- removed the modulo (%) in in the cross-node balancing trigger
- re-added node_nr_running_init() stub, nr_running_init() and comments from Christoph
- removed the constant factor 4 in find_busiest_node. The find_busiest_queue routine will take care of the case where the busiest_node is running only few processes (at most one per CPU) and return busiest=NULL .

These applied clean and looked good. I ran numbers for kernels with patches 1-4 and patches 1-5. Results below.

Quoted 7 lines

I hope we can start tuning the parameters now. In the basic NUMA scheduler part these are:
NODE_THRESHOLD : minimum percentage of node overload to
trigger cross-node balancing
NODE_BALANCE_RATE : arch specific, cross-node balancing is called
after this many intra-node load balance calls

I need to spend a some time staring at this code and putting together a series of tests to try. I think the basic mechanism looks good, so hopefully we are down to finding the best numbers for the architecture.

Quoted 9 lines

In the extended NUMA scheduler the fixed value of NODE_BALANCE_RATE is replaced by a variable rate set to :
NODE_BALANCE_MIN : if own node load is less then avg_load/2 NODE_BALANCE_MAX : if load is larger than avg_load/2
Together with the reduced number of steals across nodes this might help us in achieving equal load among nodes. I'm not aware of any simple benchmark which can demonstrate this...

Quoted 4 lines

Regards,
Erich
----

results:

stock58h: linux 2.5.58 with cputime stats patch
sched14r2-58: stock58h with latest NUMA sched patches 1 through 4
sched15r2-58: stock58h with latest NUMA sched patches 1 through 5
sched1-4-58: stock58h with previous NUMA sched patches 1 through 4

Kernbench:

                        Elapsed       User     System        CPU
        sched14r2-58    29.488s    284.02s    82.132s    1241.8%
        sched15r2-58    29.778s   282.792s    83.478s    1229.8%
            stock58h    31.656s    305.85s    89.232s    1248.2%
         sched1-4-58    29.886s   287.506s     82.94s      1239%

Schedbench 4:

                        AvgUser    Elapsed  TotalUser   TotalSys
        sched14r2-58      22.50      37.20      90.03       0.94
        sched15r2-58      16.63      24.23      66.56       0.69
            stock58h      27.73      42.80     110.96       0.85
         sched1-4-58      32.86      46.41     131.47       0.85

Schedbench 8:

                        AvgUser    Elapsed  TotalUser   TotalSys
        sched14r2-58      30.27      43.22     242.23       1.75
        sched15r2-58      30.90      42.46     247.28       1.48
            stock58h      45.97      61.87     367.81       2.11
         sched1-4-58      31.39      49.18     251.22       2.15

Schedbench 16:

                        AvgUser    Elapsed  TotalUser   TotalSys
        sched14r2-58      52.78      57.28     844.61       3.70
        sched15r2-58      48.44      65.31     775.25       3.30
            stock58h      60.91      83.63     974.71       6.18
         sched1-4-58      54.31      62.11     869.11       3.84

Schedbench 32:

                        AvgUser    Elapsed  TotalUser   TotalSys
        sched14r2-58      56.60     116.99    1811.56       5.94
        sched15r2-58      56.42     116.75    1805.82       6.45
            stock58h      84.26     195.16    2696.65      16.53
         sched1-4-58      61.49     140.51    1968.06       9.57

Schedbench 64:

                        AvgUser    Elapsed  TotalUser   TotalSys
        sched14r2-58      56.48     232.63    3615.55      16.02
        sched15r2-58      56.38     236.25    3609.03      15.41
            stock58h     123.27     511.77    7889.77      27.78
         sched1-4-58      63.39     266.40    4057.92      20.55
Signature · 2 lines
Michael Hohnbaum                      503-578-5486
[email protected]                   T/L 775-5486
#23 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

In reply to Erich Focht

I'm not keen on the way the minisched patch got reformatted. I changed it into a seperate function, which I think is much cleaner by the time you've added the third patch - no #ifdef CONFIG_NUMA in load_balance.

Rejigged patches attatched, no functional changes.

Anyway, I perf tested this, and it comes out more or less the same as the tuned version I was poking at last night (ie best of the bunch). Looks pretty good to me.

M.

PS. The fourth patch was so small, and touching the same stuff as 3 that I rolled it into the third one here. Seems like a universal benefit ;-)

#24 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

Hi Martin and Michael,

thanks for testing again!

Quoted 3 lines · Martin J. Bligh

I'm not keen on the way the minisched patch got reformatted. I changed it into a seperate function, which I think is much cleaner by the time you've added the third patch - no #ifdef CONFIG_NUMA in load_balance.

Fine. This form is also nearer to the codingstyle rule: "functions should do only one thing" (I'm reading those more carefully now ;-)

Quoted 3 lines

Anyway, I perf tested this, and it comes out more or less the same as the tuned version I was poking at last night (ie best of the bunch). Looks pretty good to me.

Great!

Quoted 3 lines

PS. The fourth patch was so small, and touching the same stuff as 3 that I rolled it into the third one here. Seems like a universal benefit ;-)

Yes, it's a much smaller step than patch #5. It would make sense to have this included right from the start.

Regards,
Erich

#25 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

Quoted 2 lines · Erich Focht

Fine. This form is also nearer to the codingstyle rule: "functions should do only one thing" (I'm reading those more carefully now ;-)

Good ;)

This is looking good. Thanks hch for going over it with your fine tooth comb.

Erich and Martin, what more needs to be done prior to inclusion? Do you still want an exec balancer in place?

Robert Love

#26 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

Quoted 5 lines · Erich Focht
Quoted 3 lines

Fine. This form is also nearer to the codingstyle rule: "functions should do only one thing" (I'm reading those more carefully now ;-)

Quoted 7 lines

Good ;)

This is looking good. Thanks hch for going over it with your fine tooth comb.

Erich and Martin, what more needs to be done prior to inclusion? Do you still want an exec balancer in place?

Yup, that's in patch 2 already. I just pushed it ... will see what happens.

M.

#27 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

In reply to Robert Love
Quoted 10 lines · Robert Love
Quoted 2 lines

Fine. This form is also nearer to the codingstyle rule: "functions should do only one thing" (I'm reading those more carefully now ;-)

Good ;)

This is looking good. Thanks hch for going over it with your fine tooth comb.

Erich and Martin, what more needs to be done prior to inclusion? Do you still want an exec balancer in place?

well, it needs to settle down a bit more, we are technically in a codefreeze :-)

Ingo

#28 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

Quoted 2 lines

well, it needs to settle down a bit more, we are technically in a codefreeze :-)

The current codeset is *completely* non-invasive to non-NUMA systems. It can't break anything.

M.

#29 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

In reply to Ingo Molnar
Quoted 2 lines · Ingo Molnar

well, it needs to settle down a bit more, we are technically in a codefreeze :-)

We're in feature freeze. Not sure whether fixing the scheduler for one type of hardware supported by Linux is a feature 8)

Anyway, patch 1 should certainly merged ASAP, for the other we can wait a bit more to settle, but I don't think it's really worth the wait.

#30 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

Quoted 8 lines · Christoph Hellwig
Quoted 2 lines

well, it needs to settle down a bit more, we are technically in a codefreeze :-)

We're in feature freeze. Not sure whether fixing the scheduler for one type of hardware supported by Linux is a feature 8)

Anyway, patch 1 should certainly merged ASAP, for the other we can wait a bit more to settle, but I don't think it's really worth the wait.

agreed, the patch is unintrusive, but by settling down i mean things like this:

+/* XXX(hch): this should go into a struct sched_node_data */

should be decided one way or another.

i'm also not quite happy about the conceptual background of rq->nr_balanced. This load-balancing rate-limit is arbitrary and not neutral at all. The way this should be done is to move the inter-node balancing conditional out of load_balance(), and only trigger it from the timer interrupt, with a given rate. On basically all NUMA hardware i suspect it's much better to do inter-node balancing only on a very slow scale. Making it dependnet on an arbitrary portion of the idle-CPU rebalancing act makes the frequency of inter-node rebalancing almost arbitrarily high.

ie. there are two basic types of rebalancing acts in multiprocessor
environments: 'synchronous balancing' and 'asynchronous balancing'. Synchronous balancing is done whenever a CPU runs idle - this can happen at a very high rate, so it needs to be low overhead and unintrusive. This was already so when i did the SMP balancer. The asynchronous blancing component (currently directly triggered from every CPU's own timer interrupt), has a fixed frequency, and thus can be almost arbitrarily complex. It's the one that is aware of the global scheduling picture. For NUMA i'd suggest two asynchronous frequencies: one intra-node frequency, and an inter-node frequency - configured by the architecture and roughly in the same proportion to each other as cachemiss latencies.

(this all means that unless there's empirical data showing the opposite, ->nr_balanced can be removed completely, and fixed frequency balancing can be done from the timer tick. This should further simplify the patch.)

Ingo

#31 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

Quoted 5 lines
Quoted 5 lines
Quoted 2 lines

well, it needs to settle down a bit more, we are technically in a codefreeze :-)

We're in feature freeze. Not sure whether fixing the scheduler for one type of hardware supported by Linux is a feature 8)

Yes, we are definitely _not_ in a code freeze yet, and I doubt that we will be for at least a few months.

John.

#32 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

In reply to Ingo Molnar
Quoted 4 lines

complex. It's the one that is aware of the global scheduling picture. For NUMA i'd suggest two asynchronous frequencies: one intra-node frequency, and an inter-node frequency - configured by the architecture and roughly in the same proportion to each other as cachemiss latencies.

That's exactly what's in the latest set of patches - admittedly it's a multiplier of when we run load_balance, not the tick multiplier, but that's very easy to fix. Can you check out the stuff I posted last night? I think it's somewhat cleaner ...

M.

#33 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

Quoted 9 lines · Martin J. Bligh
Quoted 4 lines

complex. It's the one that is aware of the global scheduling picture. For NUMA i'd suggest two asynchronous frequencies: one intra-node frequency, and an inter-node frequency - configured by the architecture and roughly in the same proportion to each other as cachemiss latencies.

That's exactly what's in the latest set of patches - admittedly it's a multiplier of when we run load_balance, not the tick multiplier, but that's very easy to fix. Can you check out the stuff I posted last night? I think it's somewhat cleaner ...

yes, i saw it, it has the same tying between idle-CPU-rebalance and inter-node rebalance, as Erich's patch. You've put it into cpus_to_balance(), but that still makes rq->nr_balanced a 'synchronously' coupled balancing act. There are two synchronous balancing acts currently:
the 'CPU just got idle' event, and the exec()-balancing (*) event. Neither must involve any 'heavy' balancing, only local balancing. The inter-node balancing (which is heavier than even the global SMP balancer), should never be triggered from the high-frequency path. [whether it's high frequency or not depends on the actual workload, but it can be potentially _very_ high frequency, easily on the order of 1 million times a second - then you'll call the inter-node balancer 100K times a second.]

I'd strongly suggest to decouple the heavy NUMA load-balancing code from the fastpath and re-check the benchmark numbers.

Ingo

(*) whether sched_balance_exec() is a high-frequency path or not is up to debate. Right now it's not possible to get much more than a couple of thousand exec()'s per second on fast CPUs. Hopefully that will change in the future though, so exec() events could become really fast. So i'd suggest to only do local (ie. SMP-alike) balancing in the exec() path, and only do NUMA cross-node balancing with a fixed frequency, from the timer tick. But exec()-time is really special, since the user task usually has zero cached state at this point, so we _can_ do cheap cross-node balancing as well. So it's a boundary thing - probably doing the full-blown balancing is the right thing.

#34 lore raw

Re: [Lse-tech] Re: [PATCH 2.5.58] new NUMA scheduler: fix

[whether it's high
frequency or not depends on the actual workload, but it can be potentially _very_ high frequency, easily on the order of 1 million times a second - then you'll call the inter-node balancer 100K times a second.]

If this is due to thread creation/death, though, you might want this level of inter-node balancing (or at least checking). It could represent a lot of fork/execs that are now overloading one or more nodes. Is it reasonable to expect this sort of load on a relatively proc/thread-stable machine?

Rick

#35 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

In reply to Ingo Molnar
Quoted 14 lines · Ingo Molnar

Ingo

(*) whether sched_balance_exec() is a high-frequency path or not is up to debate. Right now it's not possible to get much more than a couple of thousand exec()'s per second on fast CPUs. Hopefully that will change in the future though, so exec() events could become really fast. So i'd suggest to only do local (ie. SMP-alike) balancing in the exec() path, and only do NUMA cross-node balancing with a fixed frequency, from the timer tick. But exec()-time is really special, since the user task usually has zero cached state at this point, so we _can_ do cheap cross-node balancing as well. So it's a boundary thing - probably doing the full-blown balancing is the right thing.

The reason for doing load balancing on every exec is that, as you say, it is cheap to do the balancing at this point - no cache state, minimal memory allocations. If we did not balance at this point and relied on balancing from the timer tick, there would be much more movement of established processes between nodes, which is expensive. Ideally, the exec balancing is good enough so that on a well functioning system there is no inter-node balancing taking place at the timer tick. Our testing has shown that the exec load balance code does a very good job of spreading processes across nodes, and thus, very little timer tick balancing. The timer tick internode balancing is there as a safety valve for those cases where exec balancing is not adequate. Workloads with long running processes, and workloads with processes that do lots of forks but not execs, are examples.

An earlier version of Erich's initial load balancer provided for the option of balancing at either fork or exec, and the capability of selecting on a per-process basis which to use. That could be used if workloads that do forks with no execs become a problem on NUMA boxes.

Signature · 2 lines
Michael Hohnbaum                      503-578-5486
[email protected]                   T/L 775-5486
#36 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

In reply to Ingo Molnar
Quoted 6 lines

yes, i saw it, it has the same tying between idle-CPU-rebalance and inter-node rebalance, as Erich's patch. You've put it into cpus_to_balance(), but that still makes rq->nr_balanced a 'synchronously' coupled balancing act. There are two synchronous balancing acts currently:
the 'CPU just got idle' event, and the exec()-balancing (*) event. Neither must involve any 'heavy' balancing, only local balancing. The inter-node

If I understand that correctly (and I'm not sure I do), you're saying you don't think the exec time balance should go global? That would break most of the concept ... *something* has to distribute stuff around nodes, and the exec point is the cheapest time to do that (least "weight" to move. I'd like to base it off cached load-averages, rather than going sniffing every runqueue, but if you're meaning we should only exec time balance inside a node, I disagree. Am I just misunderstanding you?

At the moment, the high-freq balancer is only inside a node. Exec balancing is global, and the "low-frequency" balancer is global. WRT the idle-time balancing, I agree with what I *think* you're saying ... this shouldn't clock up the rq->nr_balanced counter ... this encourages too much cross-node stealing. I'll hack that change out and see what it does to the numbers.

Would appreciate more feedback on the first paragraph. Thanks,

M.

#37 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

Quoted 5 lines · Martin J. Bligh

If I understand that correctly (and I'm not sure I do), you're saying you don't think the exec time balance should go global? That would break most of the concept ... *something* has to distribute stuff around nodes, and the exec point is the cheapest time to do that (least "weight" to move. [...]

the exec()-time balancing is special, since it only moves the task in question - so the 'push' should indeed be a global decision. _But_, exec() is also a natural balancing point for the local node (we potentially just got rid of a task, which might create imbalance within the node), so it might make sense to do a 'local' balancing run as well, if the exec()-ing task was indeed pushed to another node.

Quoted 6 lines

At the moment, the high-freq balancer is only inside a node. Exec balancing is global, and the "low-frequency" balancer is global. WRT the idle-time balancing, I agree with what I *think* you're saying ... this shouldn't clock up the rq->nr_balanced counter ... this encourages too much cross-node stealing. I'll hack that change out and see what it does to the numbers.

yes, this should also further unify the SMP and NUMA balancing code.

Ingo

#38 lore raw

PATCH 1/1 sched-2.5.59-A2

In reply to Martin J. Bligh

Martin, Erich,

could you give the attached patch a go, it implements my cleanup/reorganization suggestions ontop of 2.5.59:

- decouple the 'slow' rebalancer from the 'fast' rebalancer and attach it to the scheduler tick. Remove rq->nr_balanced.

- do idle-rebalancing every 1 msec, intra-node rebalancing every 200 msecs and inter-node rebalancing every 400 msecs.

- move the tick-based rebalancing logic into rebalance_tick(), it looks more organized this way and we have all related code in one spot.

- clean up the topology.h include file structure. Since generic kernel code uses all the defines already, there's no reason to keep them in asm-generic.h. I've created a linux/topology.h file that includes asm/topology.h and takes care of the default and generic definitions. Moved over a generic topology definition from mmzone.h.

- renamed rq->prev_nr_running[] to rq->prev_cpu_load[] - this further unifies the SMP and NUMA balancers and is more in line with the prev_node_load name.

If performance drops due to this patch then the benchmarking goal would be to tune the following frequencies:

#define IDLE_REBALANCE_TICK (HZ/1000 ?: 1) #define BUSY_REBALANCE_TICK (HZ/5 ?: 1) #define NODE_REBALANCE_TICK (BUSY_REBALANCE_TICK * 2)

In theory NODE_REBALANCE_TICK could be defined by the NUMA platform, although in the past such per-platform scheduler tunings used to end 'orphaned' after some time. 400 msecs is pretty conservative at the moment, it could be made more frequent if benchmark results support it.

the patch compiles and boots on UP and SMP, it compiles on x86-NUMA.

Ingo

drivers/base/cpu.c renamed from drivers/base/cpu.c.orig +1 -2
@@ -6,8 +6,7 @@
 #include <linux/module.h>
 #include <linux/init.h>
 #include <linux/cpu.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 
 static int cpu_add_device(struct device * dev)
drivers/base/node.c renamed from drivers/base/node.c.orig +1 -2
@@ -7,8 +7,7 @@
 #include <linux/init.h>
 #include <linux/mm.h>
 #include <linux/node.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 
 static int node_add_device(struct device * dev)
drivers/base/memblk.c renamed from drivers/base/memblk.c.orig +1 -2
@@ -7,8 +7,7 @@
 #include <linux/init.h>
 #include <linux/memblk.h>
 #include <linux/node.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 
 static int memblk_add_device(struct device * dev)
include/asm-generic/topology.h renamed from include/asm-generic/topology.h.orig +0 -56

56 lines not on this page · raw message

include/asm-ppc64/topology.h renamed from include/asm-ppc64/topology.h.orig +0 -12
@@ -46,18 +46,6 @@
 	return mask;
 }
 
-/* Cross-node load balancing interval. */
-#define NODE_BALANCE_RATE 10
-
-#else /* !CONFIG_NUMA */
-
-#define __cpu_to_node(cpu)		(0)
-#define __memblk_to_node(memblk)	(0)
-#define __parent_node(nid)		(0)
-#define __node_to_first_cpu(node)	(0)
-#define __node_to_cpu_mask(node)	(cpu_online_map)
-#define __node_to_memblk(node)		(0)
-
 #endif /* CONFIG_NUMA */
 
 #endif /* _ASM_PPC64_TOPOLOGY_H */
include/linux/topology.h renamed from include/linux/topology.h.orig +43 -0

43 lines not on this page · raw message

include/linux/mmzone.h renamed from include/linux/mmzone.h.orig +1 -3
@@ -255,9 +255,7 @@
 #define MAX_NR_MEMBLKS	1
 #endif /* CONFIG_NUMA */
 
-#include <asm/topology.h>
-/* Returns the number of the current Node. */
-#define numa_node_id()		(__cpu_to_node(smp_processor_id()))
+#include <linux/topology.h>
 
 #ifndef CONFIG_DISCONTIGMEM
 extern struct pglist_data contig_page_data;
include/asm-ia64/topology.h renamed from include/asm-ia64/topology.h.orig +0 -3
@@ -60,7 +60,4 @@
  */
 #define __node_to_memblk(node) (node)
 
-/* Cross-node load balancing interval. */
-#define NODE_BALANCE_RATE 10
-
 #endif /* _ASM_IA64_TOPOLOGY_H */
include/asm-i386/topology.h renamed from include/asm-i386/topology.h.orig +0 -11
@@ -61,17 +61,6 @@
 /* Returns the number of the first MemBlk on Node 'node' */
 #define __node_to_memblk(node) (node)
 
-/* Cross-node load balancing interval. */
-#define NODE_BALANCE_RATE 100
-
-#else /* !CONFIG_NUMA */
-/*
- * Other i386 platforms should define their own version of the 
- * above macros here.
- */
-
-#include <asm-generic/topology.h>
-
 #endif /* CONFIG_NUMA */
 
 #endif /* _ASM_I386_TOPOLOGY_H */
include/asm-i386/cpu.h renamed from include/asm-i386/cpu.h.orig +1 -1
@@ -3,8 +3,8 @@
 
 #include <linux/device.h>
 #include <linux/cpu.h>
+#include <linux/topology.h>
 
-#include <asm/topology.h>
 #include <asm/node.h>
 
 struct i386_cpu {
include/asm-i386/node.h renamed from include/asm-i386/node.h.orig +1 -2
@@ -4,8 +4,7 @@
 #include <linux/device.h>
 #include <linux/mmzone.h>
 #include <linux/node.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 struct i386_node {
 	struct node node;
include/asm-i386/memblk.h renamed from include/asm-i386/memblk.h.orig +1 -1
@@ -4,8 +4,8 @@
 #include <linux/device.h>
 #include <linux/mmzone.h>
 #include <linux/memblk.h>
+#include <linux/topology.h>
 
-#include <asm/topology.h>
 #include <asm/node.h>
 
 struct i386_memblk {
kernel/sched.c renamed from kernel/sched.c.orig +61 -51

194 lines not on this page · raw message

mm/page_alloc.c renamed from mm/page_alloc.c.orig +1 -2
@@ -28,8 +28,7 @@
 #include <linux/blkdev.h>
 #include <linux/slab.h>
 #include <linux/notifier.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 DECLARE_BITMAP(node_online_map, MAX_NUMNODES);
 DECLARE_BITMAP(memblk_online_map, MAX_NR_MEMBLKS);
mm/vmscan.c renamed from mm/vmscan.c.orig +1 -1
@@ -27,10 +27,10 @@
 #include <linux/pagevec.h>
 #include <linux/backing-dev.h>
 #include <linux/rmap-locking.h>
+#include <linux/topology.h>
 
 #include <asm/pgalloc.h>
 #include <asm/tlbflush.h>
-#include <asm/topology.h>
 #include <asm/div64.h>
 
 #include <linux/swapops.h>
#39 lore raw

Re: [patch] sched-2.5.59-A2

Hi Ingo,

I tried your patch on the small NEC TX7 I can access easilly (8 Itanium2 CPUs on 4 nodes). I actually used your patch on top of the 2.5.52-ia64 kernel, but that shouldn't matter.

I like the cleanup of the topology.h. Also the renaming to prev_cpu_load. There was a mistake (I think) in the call to load_balance() in the idle path, guess you wanted to have:
+ load_balance(this_rq, 1, __node_to_cpu_mask(this_node));
instead of
+ load_balance(this_rq, 1, this_cpumask);
otherwise you won't load balance at all for idle cpus.

Here are the results:

kernbench (average of 5 kernel compiles) (standard error in brackets)
---------

           Elapsed       UserTime      SysTime
orig       134.43(1.79)  944.79(0.43)  21.41(0.28)
ingo       136.74(1.58)  951.55(0.73)  21.16(0.32)
ingofix    135.22(0.59)  952.17(0.78)  21.16(0.19)

hackbench (chat benchmark alike) (elapsed time for N groups of 20
--------- senders & receivers, stats from 10 measurements)

          N=10        N=25        N=50        N=100
orig      0.77(0.03)  1.91(0.06)  3.77(0.06)  7.78(0.21)
ingo      1.70(0.35)  3.11(0.47)  4.85(0.55)  8.80(0.98)
ingofix   1.16(0.14)  2.67(0.53)  5.05(0.26)  9.99(0.13)

numabench (N memory intensive tasks running in parallel, disturbed for --------- a short time by a "hackbench 10" call)

numa_test N=4   ElapsedTime  TotalUserTime  TotalSysTime
orig:           26.13(2.54)  86.10(4.47)    0.09(0.01)
ingo:           27.60(2.16)  88.06(4.58)    0.11(0.01)
ingofix:        25.51(3.05)  83.55(2.78)    0.10(0.01)
numa_test N=8   ElapsedTime  TotalUserTime  TotalSysTime
orig:           24.81(2.71)  164.94(4.82)   0.17(0.01)
ingo:           27.38(3.01)  170.06(5.60)   0.30(0.03)
ingofix:        29.08(2.79)  172.10(4.48)   0.32(0.03)
numa_test N=16  ElapsedTime  TotalUserTime  TotalSysTime
orig:           45.19(3.42)  332.07(5.89)   0.32(0.01)
ingo:           50.18(0.38)  359.46(9.31)   0.46(0.04)
ingofix:        50.30(0.42)  357.38(9.12)   0.46(0.01)
numa_test N=32  ElapsedTime  TotalUserTime  TotalSysTime
orig:           86.84(1.83)  671.99(9.98)   0.65(0.02)
ingo:           93.44(2.13)  704.90(16.91)  0.82(0.06)
ingofix:        93.92(1.28)  727.58(9.26)   0.77(0.03)
Quoted 1 line

From these results I would prefer to either leave the numa scheduler

as it is or to introduce an IDLE_NODEBALANCE_TICK and a BUSY_NODEBALANCE_TICK instead of just having one NODE_REBALANCE_TICK which balances very rarely. In that case it would make sense to keep the cpus_to_balance() function.

Best regards,
Erich

Quoted 39 lines · Ingo Molnar

Martin, Erich,

could you give the attached patch a go, it implements my cleanup/reorganization suggestions ontop of 2.5.59:

- decouple the 'slow' rebalancer from the 'fast' rebalancer and attach it to the scheduler tick. Remove rq->nr_balanced.

- do idle-rebalancing every 1 msec, intra-node rebalancing every 200 msecs and inter-node rebalancing every 400 msecs.

- move the tick-based rebalancing logic into rebalance_tick(), it looks more organized this way and we have all related code in one spot.

- clean up the topology.h include file structure. Since generic kernel code uses all the defines already, there's no reason to keep them in asm-generic.h. I've created a linux/topology.h file that includes asm/topology.h and takes care of the default and generic definitions. Moved over a generic topology definition from mmzone.h.

- renamed rq->prev_nr_running[] to rq->prev_cpu_load[] - this further unifies the SMP and NUMA balancers and is more in line with the prev_node_load name.

If performance drops due to this patch then the benchmarking goal would be to tune the following frequencies:

#define IDLE_REBALANCE_TICK (HZ/1000 ?: 1) #define BUSY_REBALANCE_TICK (HZ/5 ?: 1) #define NODE_REBALANCE_TICK (BUSY_REBALANCE_TICK * 2)

In theory NODE_REBALANCE_TICK could be defined by the NUMA platform, although in the past such per-platform scheduler tunings used to end 'orphaned' after some time. 400 msecs is pretty conservative at the moment, it could be made more frequent if benchmark results support it.

the patch compiles and boots on UP and SMP, it compiles on x86-NUMA.

Ingo

#40 lore raw

Re: [patch] sched-2.5.59-A2

Quoted 7 lines · Erich Focht

I like the cleanup of the topology.h. Also the renaming to prev_cpu_load. There was a mistake (I think) in the call to load_balance() in the idle path, guess you wanted to have:
+ load_balance(this_rq, 1, __node_to_cpu_mask(this_node));
instead of
+ load_balance(this_rq, 1, this_cpumask);
otherwise you won't load balance at all for idle cpus.

indeed - there was another bug as well, the 'idle' parameter to load_balance() was 1 even in the busy branch, causing too slow balancing.

Quoted 4 lines

From these results I would prefer to either leave the numa scheduler as it is or to introduce an IDLE_NODEBALANCE_TICK and a BUSY_NODEBALANCE_TICK instead of just having one NODE_REBALANCE_TICK which balances very rarely.

agreed, i've attached the -B0 patch that does this. The balancing rates are 1 msec, 2 msec, 200 and 400 msec (idle-local, idle-global, busy-local, busy-global).

Ingo

drivers/base/cpu.c renamed from drivers/base/cpu.c.orig +1 -2
@@ -6,8 +6,7 @@
 #include <linux/module.h>
 #include <linux/init.h>
 #include <linux/cpu.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 
 static int cpu_add_device(struct device * dev)
drivers/base/node.c renamed from drivers/base/node.c.orig +1 -2
@@ -7,8 +7,7 @@
 #include <linux/init.h>
 #include <linux/mm.h>
 #include <linux/node.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 
 static int node_add_device(struct device * dev)
drivers/base/memblk.c renamed from drivers/base/memblk.c.orig +1 -2
@@ -7,8 +7,7 @@
 #include <linux/init.h>
 #include <linux/memblk.h>
 #include <linux/node.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 
 static int memblk_add_device(struct device * dev)
include/asm-generic/topology.h renamed from include/asm-generic/topology.h.orig +0 -56

56 lines not on this page · raw message

include/asm-ppc64/topology.h renamed from include/asm-ppc64/topology.h.orig +0 -12
@@ -46,18 +46,6 @@
 	return mask;
 }
 
-/* Cross-node load balancing interval. */
-#define NODE_BALANCE_RATE 10
-
-#else /* !CONFIG_NUMA */
-
-#define __cpu_to_node(cpu)		(0)
-#define __memblk_to_node(memblk)	(0)
-#define __parent_node(nid)		(0)
-#define __node_to_first_cpu(node)	(0)
-#define __node_to_cpu_mask(node)	(cpu_online_map)
-#define __node_to_memblk(node)		(0)
-
 #endif /* CONFIG_NUMA */
 
 #endif /* _ASM_PPC64_TOPOLOGY_H */
include/linux/topology.h renamed from include/linux/topology.h.orig +43 -0

43 lines not on this page · raw message

include/linux/mmzone.h renamed from include/linux/mmzone.h.orig +1 -3
@@ -255,9 +255,7 @@
 #define MAX_NR_MEMBLKS	1
 #endif /* CONFIG_NUMA */
 
-#include <asm/topology.h>
-/* Returns the number of the current Node. */
-#define numa_node_id()		(__cpu_to_node(smp_processor_id()))
+#include <linux/topology.h>
 
 #ifndef CONFIG_DISCONTIGMEM
 extern struct pglist_data contig_page_data;
include/asm-ia64/topology.h renamed from include/asm-ia64/topology.h.orig +0 -3
@@ -60,7 +60,4 @@
  */
 #define __node_to_memblk(node) (node)
 
-/* Cross-node load balancing interval. */
-#define NODE_BALANCE_RATE 10
-
 #endif /* _ASM_IA64_TOPOLOGY_H */
include/asm-i386/topology.h renamed from include/asm-i386/topology.h.orig +0 -11
@@ -61,17 +61,6 @@
 /* Returns the number of the first MemBlk on Node 'node' */
 #define __node_to_memblk(node) (node)
 
-/* Cross-node load balancing interval. */
-#define NODE_BALANCE_RATE 100
-
-#else /* !CONFIG_NUMA */
-/*
- * Other i386 platforms should define their own version of the 
- * above macros here.
- */
-
-#include <asm-generic/topology.h>
-
 #endif /* CONFIG_NUMA */
 
 #endif /* _ASM_I386_TOPOLOGY_H */
include/asm-i386/cpu.h renamed from include/asm-i386/cpu.h.orig +1 -1
@@ -3,8 +3,8 @@
 
 #include <linux/device.h>
 #include <linux/cpu.h>
+#include <linux/topology.h>
 
-#include <asm/topology.h>
 #include <asm/node.h>
 
 struct i386_cpu {
include/asm-i386/node.h renamed from include/asm-i386/node.h.orig +1 -2
@@ -4,8 +4,7 @@
 #include <linux/device.h>
 #include <linux/mmzone.h>
 #include <linux/node.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 struct i386_node {
 	struct node node;
include/asm-i386/memblk.h renamed from include/asm-i386/memblk.h.orig +1 -1
@@ -4,8 +4,8 @@
 #include <linux/device.h>
 #include <linux/mmzone.h>
 #include <linux/memblk.h>
+#include <linux/topology.h>
 
-#include <asm/topology.h>
 #include <asm/node.h>
 
 struct i386_memblk {
kernel/sched.c renamed from kernel/sched.c.orig +75 -51

208 lines not on this page · raw message

mm/page_alloc.c renamed from mm/page_alloc.c.orig +1 -2
@@ -28,8 +28,7 @@
 #include <linux/blkdev.h>
 #include <linux/slab.h>
 #include <linux/notifier.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 DECLARE_BITMAP(node_online_map, MAX_NUMNODES);
 DECLARE_BITMAP(memblk_online_map, MAX_NR_MEMBLKS);
mm/vmscan.c renamed from mm/vmscan.c.orig +1 -1
@@ -27,10 +27,10 @@
 #include <linux/pagevec.h>
 #include <linux/backing-dev.h>
 #include <linux/rmap-locking.h>
+#include <linux/topology.h>
 
 #include <asm/pgalloc.h>
 #include <asm/tlbflush.h>
-#include <asm/topology.h>
 #include <asm/div64.h>
 
 #include <linux/swapops.h>
#41 lore raw

Re: [patch] sched-2.5.59-A2

Quoted 11 lines · Ingo Molnar
Quoted 7 lines · Erich Focht

I like the cleanup of the topology.h. Also the renaming to prev_cpu_load. There was a mistake (I think) in the call to load_balance() in the idle path, guess you wanted to have:
+ load_balance(this_rq, 1, __node_to_cpu_mask(this_node));
instead of
+ load_balance(this_rq, 1, this_cpumask);
otherwise you won't load balance at all for idle cpus.

indeed - there was another bug as well, the 'idle' parameter to load_balance() was 1 even in the busy branch, causing too slow balancing.

I didn't see that, but it's impact is only that a busy cpu is stealing at most one task from another node, otherwise the idle=1 leads to more aggressive balancing.

Quoted 8 lines
Quoted 4 lines

From these results I would prefer to either leave the numa scheduler as it is or to introduce an IDLE_NODEBALANCE_TICK and a BUSY_NODEBALANCE_TICK instead of just having one NODE_REBALANCE_TICK which balances very rarely.

agreed, i've attached the -B0 patch that does this. The balancing rates are 1 msec, 2 msec, 200 and 400 msec (idle-local, idle-global, busy-local, busy-global).

This looks good! I'll see if I can rerun the tests today, anyway I'm more optimistic about this version.

Regards,
Erich

#42 lore raw

Re: [patch] sched-2.5.59-A2

In reply to Ingo Molnar
Quoted 3 lines

agreed, i've attached the -B0 patch that does this. The balancing rates are 1 msec, 2 msec, 200 and 400 msec (idle-local, idle-global, busy-local, busy-global).

Hmmm... something is drastically wrong here, looks like we're thrashing tasks between nodes?

Kernbench:

                                   Elapsed        User      System         CPU
                        2.5.59     20.032s     186.66s      47.73s       1170%
                  2.5.59-ingo2     23.578s    198.874s     90.648s     1227.4%

NUMA schedbench 4:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                        2.5.59        0.00       36.38       90.70        0.62
                  2.5.59-ingo2        0.00       47.62      127.13        1.89

NUMA schedbench 8:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                        2.5.59        0.00       42.78      249.77        1.85
                  2.5.59-ingo2        0.00       59.45      358.31        5.23

NUMA schedbench 16:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                        2.5.59        0.00       56.84      848.00        2.78
                  2.5.59-ingo2        0.00      114.70     1430.95       21.21

diffprofile:

44770 total
27840 do_anonymous_page
3180 buffered_rmqueue
1814 default_idle
1534 __copy_from_user_ll
1465 free_hot_cold_page
1172 __copy_to_user_ll
919 page_remove_rmap
881 zap_pte_range
730 do_wp_page
687 do_no_page
601 __alloc_pages
527 vm_enough_memory
432 __set_page_dirty_buffers
426 page_add_rmap
322 release_pages
311 __pagevec_lru_add_active
233 prep_new_page
202 clear_page_tables
181 schedule
132 current_kernel_time
127 __block_prepare_write
103 kmap_atomic
100 __wake_up
97 pte_alloc_one
95 may_open
87 find_get_page
76 dget_locked
72 bad_range
69 pgd_alloc
62 __fput
50 copy_strings
...
-66 open_namei
-68 path_lookup
-115 .text.lock.file_table
-255 .text.lock.dec_and_lock
-469 .text.lock.namei

#43 lore raw

NUMA sched -> pooling scheduler (inc HT)

Andrew, hopefully this'll give you a cleaner integration point to do the HT scheduler stuff ... I basically did a rename of "node" to "pool" on sched.c (OK, it was a little more complex than that), and provided some hooks for you to attatch to. There's a really hacky version of the HT stuff in there that I doubt works at all. (sched.h will need something other than CONFIG_SCHED_NUMA, for starters).

It's not really finished, but I have to go out ... I thought you or someone else might like to have a play with it in the meantime. Goes on top of the second half of Ingo's stuff from yesterday (also attatched).

I think this should result in a much cleaner integration between the HT aware stuff and the NUMA stuff. Pools is a concept Erich had in his scheduler a while back, but it got set aside in the paring down for integration. We should be able to add multiple levels to this fairly easily, at some point (eg HT + NUMA), but let's get the basics working first ;-)

M.

#44 lore raw

Re: [Lse-tech] NUMA sched -> pooling scheduler (inc HT)

Mmm... seems I may have got the ordering of the cpus wrong. Something like this might work better in sched_topo_ht.h (yeah, it's ugly. I don't care).

static inline int pool_to_cpu_mask (int pool)

{
	return ( (1UL << pool) || (1UL << cpu_sibling_map[pool]));
}

static inline cpu_to_pool (int cpu)

{
	return min(cpu, cpu_sibling_map[cpu]);
}

Thanks to Andi, Zwane, and Bill for the corrective baseball bat strike. I changed the macros to inlines to avoid the risk of double eval.

M.

#45 lore raw

Re: [Lse-tech] NUMA sched -> pooling scheduler (inc HT)

Thanks Martin, I'll take a look. One thing I have noticed on B0 numa_sched:
I added node load to /proc/stat and see a problem. look at procs_running compared to the total of node1..4. They do not agree. It looks as if the node load and runqueue lengths may have gotten out of sync. I could not find any obvious place this happened.

cpu 65922 0 4321 650621 560
cpu0 5066 0 665 84545 4
cpu1 21965 0 1402 66796 0
cpu2 26187 0 1553 62290 132
cpu3 12535 0 550 77043 34
cpu4 121 0 116 89581 344
cpu5 38 0 16 90071 36
cpu6 6 0 12 90136 7
cpu7 2 0 4 90156 0
intr 909780 902661 16 0 1 1 0 5 1 0 1 1 1 60 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 4274 2748 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ctxt 32127
btime 1042925625
processes 982
procs_running 1
procs_blocked 0
node0 1
node1 1
node2 0
node3 0

#46 lore raw

Re: [patch] sched-2.5.59-A2

In reply to Ingo Molnar
Quoted 5 lines · Ingo Molnar

agreed, i've attached the -B0 patch that does this. The balancing rates are 1 msec, 2 msec, 200 and 400 msec (idle-local, idle-global, busy-local, busy-global).

Ingo

Ran this patch on a 4 node (16 CPU, 16 GB memory) NUMAQ. Results don't look encouraging. I would suggest not applying this patch until the degradation is worked out.

stock59 = linux 2.5.59
ingo59 = linux 2.5.59 with Ingo's B0 patch

Kernbench:

                        Elapsed       User     System        CPU
             stock59    29.668s   283.762s    82.286s      1233%
              ingo59    37.736s   338.162s   153.486s    1302.6%

Schedbench 4:

                        AvgUser    Elapsed  TotalUser   TotalSys
             stock59       0.00      24.44      68.07       0.78
              ingo59       0.00      62.14     163.32       1.93

Schedbench 8:

                        AvgUser    Elapsed  TotalUser   TotalSys
             stock59       0.00      48.26     246.75       1.64
              ingo59       0.00      68.17     376.85       6.42

Schedbench 16:

                        AvgUser    Elapsed  TotalUser   TotalSys
             stock59       0.00      56.51     845.26       2.98
              ingo59       0.00     114.38    1337.65      18.89

Schedbench 32:

                        AvgUser    Elapsed  TotalUser   TotalSys
             stock59       0.00     116.95    1806.33       6.23
              ingo59       0.00     243.46    3515.09      43.92

Schedbench 64:

                        AvgUser    Elapsed  TotalUser   TotalSys
             stock59       0.00     237.29    3634.59      15.71
              ingo59       0.00     688.31   10605.40     102.71
Signature · 2 lines
Michael Hohnbaum                      503-578-5486
[email protected]                   T/L 775-5486
#47 lore raw

Re: [patch] sched-2.5.59-A2

In reply to Ingo Molnar
Quoted 3 lines · Ingo Molnar

agreed, i've attached the -B0 patch that does this. The balancing rates are 1 msec, 2 msec, 200 and 400 msec (idle-local, idle-global, busy-local, busy-global).

I suspect some of these results may be off on NUMA-Q (or any PAE box) if CONFIG_MTRR was enabled. Michael, Martin, please doublecheck /proc/mtrr and whether CONFIG_MTRR=y. If you didn't enable it, or if you compile times aren't on the order of 5-10 minutes, you're unaffected.

The severity of the MTRR regression in 2.5.59 is apparent from:

$ cat /proc/mtrr
reg00: base=0xc0000000 (3072MB), size=1024MB: uncachable, count=1
reg01: base=0x00000000 (   0MB), size=4096MB: write-back, count=1
$ time make -j bzImage > /dev/null
make -j bzImage > /dev/null  8338.52s user 245.73s system 1268% cpu 11:16.56 total

Fixing it up by hand (after dealing with various bits of pain) to:

$ cat /proc/mtrr
reg00: base=0xc0000000 (3072MB), size=1024MB: uncachable, count=1
reg01: base=0x00000000 (   0MB), size=4096MB: write-back, count=1
reg02: base=0x100000000 (4096MB), size=4096MB: write-back, count=1
reg03: base=0x200000000 (8192MB), size=4096MB: write-back, count=1
reg04: base=0x300000000 (12288MB), size=4096MB: write-back, count=1
reg05: base=0x400000000 (16384MB), size=16384MB: write-back, count=1
reg06: base=0x800000000 (32768MB), size=16384MB: write-back, count=1
reg07: base=0xc00000000 (49152MB), size=16384MB: write-back, count=1
make -j bzImage > /dev/null  361.72s user 546.28s system 2208% cpu 41.109 total
make -j bzImage > /dev/null  364.00s user 575.73s system 2005% cpu 46.858 total
make -j bzImage > /dev/null  366.77s user 568.44s system 2239% cpu 41.765 total

I'll do some bisection search to figure out which patch broke the world.

-- wli

#48 lore raw

Re: [patch] sched-2.5.59-A2

Quoted 9 lines
Quoted 3 lines

agreed, i've attached the -B0 patch that does this. The balancing rates are 1 msec, 2 msec, 200 and 400 msec (idle-local, idle-global, busy-local, busy-global).

I suspect some of these results may be off on NUMA-Q (or any PAE box) if CONFIG_MTRR was enabled. Michael, Martin, please doublecheck /proc/mtrr and whether CONFIG_MTRR=y. If you didn't enable it, or if you compile times aren't on the order of 5-10 minutes, you're unaffected.

Quoted 4 lines

The severity of the MTRR regression in 2.5.59 is apparent from:

$ cat /proc/mtrr
reg00: base=0xc0000000 (3072MB), size=1024MB: uncachable, count=1
reg01: base=0x00000000 (   0MB), size=4096MB: write-back, count=1

Works for me, I have MTRR on.

larry:~# cat /proc/mtrr
reg00: base=0xe0000000 (3584MB), size= 512MB: uncachable, count=1
reg01: base=0x00000000 (   0MB), size=16384MB: write-back, count=1
#49 lore raw

Re: [patch] sched-2.5.59-A2

Quoted 8 lines · At some point in the past, I wrote:
Quoted 8 lines

I suspect some of these results may be off on NUMA-Q (or any PAE box) if CONFIG_MTRR was enabled. Michael, Martin, please doublecheck /proc/mtrr and whether CONFIG_MTRR=y. If you didn't enable it, or if you compile times aren't on the order of 5-10 minutes, you're unaffected. The severity of the MTRR regression in 2.5.59 is apparent from:

$ cat /proc/mtrr
reg00: base=0xc0000000 (3072MB), size=1024MB: uncachable, count=1
reg01: base=0x00000000 (   0MB), size=4096MB: write-back, count=1
Quoted 4 lines · Martin J. Bligh

Works for me, I have MTRR on.

larry:~# cat /proc/mtrr
reg00: base=0xe0000000 (3584MB), size= 512MB: uncachable, count=1
reg01: base=0x00000000 (   0MB), size=16384MB: write-back, count=1

Okay, it sounds like the problem needs some extra RAM to trigger. We can bounce quads back & forth if need be, but I'll at least take a shot at finding where it happened before you probably need to look into it.

Thanks,
Bill

#50 lore raw

Re: [patch] sched-2.5.59-A2

In reply to William Lee Irwin III
Quoted 1 line · William Lee Irwin III

The severity of the MTRR regression in 2.5.59 is apparent from:

This is not a result of userland initscripts botching the MTRR; not only are printk's in MTRR-setting routines not visible but it's also apparent from the fact that highmem mem_map initialization suffers a similar degradation adding almost a full 20 minutes to boot times.

-- wli

#51 lore raw

Re: [patch] sched-2.5.59-A2

In reply to Erich Focht
Quoted 1 line

I like the cleanup of the topology.h.

Any chance we could keep that broken out as a seperate patch? Topo cleanups below:

drivers/base/cpu.c +1 -2
diff -urpN -X /home/fletch/.diff.exclude virgin/drivers/base/cpu.c ingo-A/drivers/base/cpu.c
@@ -6,8 +6,7 @@
 #include <linux/module.h>
 #include <linux/init.h>
 #include <linux/cpu.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 
 static int cpu_add_device(struct device * dev)
drivers/base/memblk.c +1 -2
diff -urpN -X /home/fletch/.diff.exclude virgin/drivers/base/memblk.c ingo-A/drivers/base/memblk.c
@@ -7,8 +7,7 @@
 #include <linux/init.h>
 #include <linux/memblk.h>
 #include <linux/node.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 
 static int memblk_add_device(struct device * dev)
drivers/base/node.c +1 -2
diff -urpN -X /home/fletch/.diff.exclude virgin/drivers/base/node.c ingo-A/drivers/base/node.c
@@ -7,8 +7,7 @@
 #include <linux/init.h>
 #include <linux/mm.h>
 #include <linux/node.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 
 static int node_add_device(struct device * dev)
include/asm-generic/topology.h +0 -56

56 lines not on this page · raw message

include/asm-i386/cpu.h +1 -1
diff -urpN -X /home/fletch/.diff.exclude virgin/include/asm-i386/cpu.h ingo-A/include/asm-i386/cpu.h
@@ -3,8 +3,8 @@
 
 #include <linux/device.h>
 #include <linux/cpu.h>
+#include <linux/topology.h>
 
-#include <asm/topology.h>
 #include <asm/node.h>
 
 struct i386_cpu {
include/asm-i386/memblk.h +1 -1
diff -urpN -X /home/fletch/.diff.exclude virgin/include/asm-i386/memblk.h ingo-A/include/asm-i386/memblk.h
@@ -4,8 +4,8 @@
 #include <linux/device.h>
 #include <linux/mmzone.h>
 #include <linux/memblk.h>
+#include <linux/topology.h>
 
-#include <asm/topology.h>
 #include <asm/node.h>
 
 struct i386_memblk {
include/asm-i386/node.h +1 -2
diff -urpN -X /home/fletch/.diff.exclude virgin/include/asm-i386/node.h ingo-A/include/asm-i386/node.h
@@ -4,8 +4,7 @@
 #include <linux/device.h>
 #include <linux/mmzone.h>
 #include <linux/node.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 struct i386_node {
 	struct node node;
include/asm-i386/topology.h +0 -11
diff -urpN -X /home/fletch/.diff.exclude virgin/include/asm-i386/topology.h ingo-A/include/asm-i386/topology.h
@@ -61,17 +61,6 @@ static inline int __node_to_first_cpu(in
 /* Returns the number of the first MemBlk on Node 'node' */
 #define __node_to_memblk(node) (node)
 
-/* Cross-node load balancing interval. */
-#define NODE_BALANCE_RATE 100
-
-#else /* !CONFIG_NUMA */
-/*
- * Other i386 platforms should define their own version of the 
- * above macros here.
- */
-
-#include <asm-generic/topology.h>
-
 #endif /* CONFIG_NUMA */
 
 #endif /* _ASM_I386_TOPOLOGY_H */
include/asm-ia64/topology.h +0 -3
diff -urpN -X /home/fletch/.diff.exclude virgin/include/asm-ia64/topology.h ingo-A/include/asm-ia64/topology.h
@@ -60,7 +60,4 @@
  */
 #define __node_to_memblk(node) (node)
 
-/* Cross-node load balancing interval. */
-#define NODE_BALANCE_RATE 10
-
 #endif /* _ASM_IA64_TOPOLOGY_H */
include/asm-ppc64/topology.h +0 -12
diff -urpN -X /home/fletch/.diff.exclude virgin/include/asm-ppc64/topology.h ingo-A/include/asm-ppc64/topology.h
@@ -46,18 +46,6 @@ static inline unsigned long __node_to_cp
 	return mask;
 }
 
-/* Cross-node load balancing interval. */
-#define NODE_BALANCE_RATE 10
-
-#else /* !CONFIG_NUMA */
-
-#define __cpu_to_node(cpu)		(0)
-#define __memblk_to_node(memblk)	(0)
-#define __parent_node(nid)		(0)
-#define __node_to_first_cpu(node)	(0)
-#define __node_to_cpu_mask(node)	(cpu_online_map)
-#define __node_to_memblk(node)		(0)
-
 #endif /* CONFIG_NUMA */
 
 #endif /* _ASM_PPC64_TOPOLOGY_H */
include/linux/mmzone.h +1 -3
diff -urpN -X /home/fletch/.diff.exclude virgin/include/linux/mmzone.h ingo-A/include/linux/mmzone.h
@@ -255,9 +255,7 @@ static inline struct zone *next_zone(str
 #define MAX_NR_MEMBLKS	1
 #endif /* CONFIG_NUMA */
 
-#include <asm/topology.h>
-/* Returns the number of the current Node. */
-#define numa_node_id()		(__cpu_to_node(smp_processor_id()))
+#include <linux/topology.h>
 
 #ifndef CONFIG_DISCONTIGMEM
 extern struct pglist_data contig_page_data;
include/linux/topology.h +43 -0

43 lines not on this page · raw message

mm/page_alloc.c +1 -2
diff -urpN -X /home/fletch/.diff.exclude virgin/mm/page_alloc.c ingo-A/mm/page_alloc.c
@@ -28,8 +28,7 @@
 #include <linux/blkdev.h>
 #include <linux/slab.h>
 #include <linux/notifier.h>
-
-#include <asm/topology.h>
+#include <linux/topology.h>
 
 DECLARE_BITMAP(node_online_map, MAX_NUMNODES);
 DECLARE_BITMAP(memblk_online_map, MAX_NR_MEMBLKS);
mm/vmscan.c +1 -1
diff -urpN -X /home/fletch/.diff.exclude virgin/mm/vmscan.c ingo-A/mm/vmscan.c
@@ -27,10 +27,10 @@
 #include <linux/pagevec.h>
 #include <linux/backing-dev.h>
 #include <linux/rmap-locking.h>
+#include <linux/topology.h>
 
 #include <asm/pgalloc.h>
 #include <asm/tlbflush.h>
-#include <asm/topology.h>
 #include <asm/div64.h>
 
 #include <linux/swapops.h>
#52 lore raw

Re: [patch] sched-2.5.59-A2

In reply to Erich Focht
Quoted 1 line

I like the cleanup of the topology.h.

And the rest of Ingo's second version:

kernel/sched.c +75 -51
diff -urpN -X /home/fletch/.diff.exclude ingo-A/kernel/sched.c ingo-B/kernel/sched.c
@@ -153,10 +153,9 @@ struct runqueue {
 			nr_uninterruptible;
 	task_t *curr, *idle;
 	prio_array_t *active, *expired, arrays[2];
-	int prev_nr_running[NR_CPUS];
+	int prev_cpu_load[NR_CPUS];
 #ifdef CONFIG_NUMA
 	atomic_t *node_nr_running;
-	unsigned int nr_balanced;
 	int prev_node_load[MAX_NUMNODES];
 #endif
 	task_t *migration_thread;
@@ -765,29 +764,6 @@ static int find_busiest_node(int this_no
 	return node;
 }
 
-static inline unsigned long cpus_to_balance(int this_cpu, runqueue_t *this_rq)
-{
-	int this_node = __cpu_to_node(this_cpu);
-	/*
-	 * Avoid rebalancing between nodes too often.
-	 * We rebalance globally once every NODE_BALANCE_RATE load balances.
-	 */
-	if (++(this_rq->nr_balanced) == NODE_BALANCE_RATE) {
-		int node = find_busiest_node(this_node);
-		this_rq->nr_balanced = 0;
-		if (node >= 0)
-			return (__node_to_cpu_mask(node) | (1UL << this_cpu));
-	}
-	return __node_to_cpu_mask(this_node);
-}
-
-#else /* !CONFIG_NUMA */
-
-static inline unsigned long cpus_to_balance(int this_cpu, runqueue_t *this_rq)
-{
-	return cpu_online_map;
-}
-
 #endif /* CONFIG_NUMA */
 
 #if CONFIG_SMP
@@ -807,10 +783,10 @@ static inline unsigned int double_lock_b
 			spin_lock(&busiest->lock);
 			spin_lock(&this_rq->lock);
 			/* Need to recalculate nr_running */
-			if (idle || (this_rq->nr_running > this_rq->prev_nr_running[this_cpu]))
+			if (idle || (this_rq->nr_running > this_rq->prev_cpu_load[this_cpu]))
 				nr_running = this_rq->nr_running;
 			else
-				nr_running = this_rq->prev_nr_running[this_cpu];
+				nr_running = this_rq->prev_cpu_load[this_cpu];
 		} else
 			spin_lock(&busiest->lock);
 	}
@@ -847,10 +823,10 @@ static inline runqueue_t *find_busiest_q
 	 * that case we are less picky about moving a task across CPUs and
 	 * take what can be taken.
 	 */
-	if (idle || (this_rq->nr_running > this_rq->prev_nr_running[this_cpu]))
+	if (idle || (this_rq->nr_running > this_rq->prev_cpu_load[this_cpu]))
 		nr_running = this_rq->nr_running;
 	else
-		nr_running = this_rq->prev_nr_running[this_cpu];
+		nr_running = this_rq->prev_cpu_load[this_cpu];
 
 	busiest = NULL;
 	max_load = 1;
@@ -859,11 +835,11 @@ static inline runqueue_t *find_busiest_q
 			continue;
 
 		rq_src = cpu_rq(i);
-		if (idle || (rq_src->nr_running < this_rq->prev_nr_running[i]))
+		if (idle || (rq_src->nr_running < this_rq->prev_cpu_load[i]))
 			load = rq_src->nr_running;
 		else
-			load = this_rq->prev_nr_running[i];
-		this_rq->prev_nr_running[i] = rq_src->nr_running;
+			load = this_rq->prev_cpu_load[i];
+		this_rq->prev_cpu_load[i] = rq_src->nr_running;
 
 		if ((load > max_load) && (rq_src != this_rq)) {
 			busiest = rq_src;
@@ -922,7 +898,7 @@ static inline void pull_task(runqueue_t 
  * We call this with the current runqueue locked,
  * irqs disabled.
  */
-static void load_balance(runqueue_t *this_rq, int idle)
+static void load_balance(runqueue_t *this_rq, int idle, unsigned long cpumask)
 {
 	int imbalance, idx, this_cpu = smp_processor_id();
 	runqueue_t *busiest;
@@ -930,8 +906,7 @@ static void load_balance(runqueue_t *thi
 	struct list_head *head, *curr;
 	task_t *tmp;
 
-	busiest = find_busiest_queue(this_rq, this_cpu, idle, &imbalance,
-					cpus_to_balance(this_cpu, this_rq));
+	busiest = find_busiest_queue(this_rq, this_cpu, idle, &imbalance, cpumask);
 	if (!busiest)
 		goto out;
 
@@ -1006,21 +981,75 @@ out:
  * frequency and balancing agressivity depends on whether the CPU is
  * idle or not.
  *
- * busy-rebalance every 250 msecs. idle-rebalance every 1 msec. (or on
+ * busy-rebalance every 200 msecs. idle-rebalance every 1 msec. (or on
  * systems with HZ=100, every 10 msecs.)
+ *
+ * On NUMA, do a node-rebalance every 400 msecs.
  */
-#define BUSY_REBALANCE_TICK (HZ/4 ?: 1)
 #define IDLE_REBALANCE_TICK (HZ/1000 ?: 1)
+#define BUSY_REBALANCE_TICK (HZ/5 ?: 1)
+#define IDLE_NODE_REBALANCE_TICK (IDLE_REBALANCE_TICK * 2)
+#define BUSY_NODE_REBALANCE_TICK (BUSY_REBALANCE_TICK * 2)
 
-static inline void idle_tick(runqueue_t *rq)
+#if CONFIG_NUMA
+static void balance_node(runqueue_t *this_rq, int idle, int this_cpu)
 {
-	if (jiffies % IDLE_REBALANCE_TICK)
-		return;
-	spin_lock(&rq->lock);
-	load_balance(rq, 1);
-	spin_unlock(&rq->lock);
+	int node = find_busiest_node(__cpu_to_node(this_cpu));
+	unsigned long cpumask, this_cpumask = 1UL << this_cpu;
+
+	if (node >= 0) {
+		cpumask = __node_to_cpu_mask(node) | this_cpumask;
+		spin_lock(&this_rq->lock);
+		load_balance(this_rq, idle, cpumask);
+		spin_unlock(&this_rq->lock);
+	}
 }
+#endif
 
+static void rebalance_tick(runqueue_t *this_rq, int idle)
+{
+#if CONFIG_NUMA
+	int this_cpu = smp_processor_id();
+#endif
+	unsigned long j = jiffies;
+
+	/*
+	 * First do inter-node rebalancing, then intra-node rebalancing,
+	 * if both events happen in the same tick. The inter-node
+	 * rebalancing does not necessarily have to create a perfect
+	 * balance within the node, since we load-balance the most loaded
+	 * node with the current CPU. (ie. other CPUs in the local node
+	 * are not balanced.)
+	 */
+	if (idle) {
+#if CONFIG_NUMA
+		if (!(j % IDLE_NODE_REBALANCE_TICK))
+			balance_node(this_rq, idle, this_cpu);
+#endif
+		if (!(j % IDLE_REBALANCE_TICK)) {
+			spin_lock(&this_rq->lock);
+			load_balance(this_rq, 0, __cpu_to_node_mask(this_cpu));
+			spin_unlock(&this_rq->lock);
+		}
+		return;
+	}
+#if CONFIG_NUMA
+	if (!(j % BUSY_NODE_REBALANCE_TICK))
+		balance_node(this_rq, idle, this_cpu);
+#endif
+	if (!(j % BUSY_REBALANCE_TICK)) {
+		spin_lock(&this_rq->lock);
+		load_balance(this_rq, idle, __cpu_to_node_mask(this_cpu));
+		spin_unlock(&this_rq->lock);
+	}
+}
+#else
+/*
+ * on UP we do not need to balance between CPUs:
+ */
+static inline void rebalance_tick(runqueue_t *this_rq, int idle)
+{
+}
 #endif
 
 DEFINE_PER_CPU(struct kernel_stat, kstat) = { { 0 } };
@@ -1063,9 +1092,7 @@ void scheduler_tick(int user_ticks, int 
 			kstat_cpu(cpu).cpustat.iowait += sys_ticks;
 		else
 			kstat_cpu(cpu).cpustat.idle += sys_ticks;
-#if CONFIG_SMP
-		idle_tick(rq);
-#endif
+		rebalance_tick(rq, 1);
 		return;
 	}
 	if (TASK_NICE(p) > 0)
@@ -1121,11 +1148,8 @@ void scheduler_tick(int user_ticks, int 
 			enqueue_task(p, rq->active);
 	}
 out:
-#if CONFIG_SMP
-	if (!(jiffies % BUSY_REBALANCE_TICK))
-		load_balance(rq, 0);
-#endif
 	spin_unlock(&rq->lock);
+	rebalance_tick(rq, 0);
 }
 
 void scheduling_functions_start_here(void) { }
@@ -1184,7 +1208,7 @@ need_resched:
 pick_next_task:
 	if (unlikely(!rq->nr_running)) {
 #if CONFIG_SMP
-		load_balance(rq, 1);
+		load_balance(rq, 1, __cpu_to_node_mask(smp_processor_id()));
 		if (rq->nr_running)
 			goto pick_next_task;
 #endif
#53 lore raw

Re: [patch] sched-2.5.59-A2

In reply to Erich Focht

Ingo,

I repeated the tests with your B0 version and it's still not satisfying. Maybe too aggressive NODE_REBALANCE_IDLE_TICK, maybe the difference is that the other calls of load_balance() never have the chance to balance across nodes.

Here are the results:

kernbench (average of 5 kernel compiles) (standard error in brackets)
---------

           Elapsed       UserTime      SysTime
orig       134.43(1.79)  944.79(0.43)  21.41(0.28)
ingo       136.74(1.58)  951.55(0.73)  21.16(0.32)
ingofix    135.22(0.59)  952.17(0.78)  21.16(0.19)
ingoB0     134.69(0.51)  951.63(0.81)  21.12(0.15)

hackbench (chat benchmark alike) (elapsed time for N groups of 20
--------- senders & receivers, stats from 10 measurements)

          N=10        N=25        N=50        N=100
orig      0.77(0.03)  1.91(0.06)  3.77(0.06)  7.78(0.21)
ingo      1.70(0.35)  3.11(0.47)  4.85(0.55)  8.80(0.98)
ingofix   1.16(0.14)  2.67(0.53)  5.05(0.26)  9.99(0.13)
ingoB0    0.84(0.03)  2.12(0.12)  4.20(0.22)  8.04(0.16)

numabench (N memory intensive tasks running in parallel, disturbed for --------- a short time by a "hackbench 10" call)

numa_test N=4   ElapsedTime  TotalUserTime  TotalSysTime
orig:           26.13(2.54)  86.10(4.47)    0.09(0.01)
ingo:           27.60(2.16)  88.06(4.58)    0.11(0.01)
ingofix:        25.51(3.05)  83.55(2.78)    0.10(0.01)
ingoB0:         27.58(0.08)  90.86(4.42)    0.09(0.01)	
numa_test N=8   ElapsedTime  TotalUserTime  TotalSysTime
orig:           24.81(2.71)  164.94(4.82)   0.17(0.01)
ingo:           27.38(3.01)  170.06(5.60)   0.30(0.03)
ingofix:        29.08(2.79)  172.10(4.48)   0.32(0.03)
ingoB0:         26.05(3.28)  171.61(7.76)   0.18(0.01)
numa_test N=16  ElapsedTime  TotalUserTime  TotalSysTime
orig:           45.19(3.42)  332.07(5.89)   0.32(0.01)
ingo:           50.18(0.38)  359.46(9.31)   0.46(0.04)
ingofix:        50.30(0.42)  357.38(9.12)   0.46(0.01)
ingoB0:         50.96(1.33)  371.72(18.58)  0.34(0.01)
numa_test N=32  ElapsedTime  TotalUserTime  TotalSysTime
orig:           86.84(1.83)  671.99(9.98)   0.65(0.02)
ingo:           93.44(2.13)  704.90(16.91)  0.82(0.06)
ingofix:        93.92(1.28)  727.58(9.26)   0.77(0.03)
ingoB0:         99.72(4.13)  759.03(29.41)  0.69(0.01)

The kernbench user time is still too large.
Hackbench improved a lot (understandeable, as idle CPUs steal earlier from remote nodes).
Numa_test didn't improve, in average we have the same results.

Hmmm, now I really tend towards letting it the way it is in 2.5.59. Except the topology cleanup and renaming, of course. I have no more time to test a more conservative setting of IDLE_NODE_REBALANCE_TICK today, but that could help...

Regards,
Erich

#54 lore raw

Re: [patch] sched-2.5.59-A2

Quoted 4 lines

I repeated the tests with your B0 version and it's still not satisfying. Maybe too aggressive NODE_REBALANCE_IDLE_TICK, maybe the difference is that the other calls of load_balance() never have the chance to balance across nodes.

Nope, I found the problem. The topo cleanups are broken - we end up taking all mem accesses, etc to node 0.

Use the second half of the patch (the splitup I already posted), and fix the obvious compile error. Works fine now ;-)

Matt, you know the topo stuff better than anyone. Can you take a look at the cleanup Ingo did, and see if it's easily fixable?

M.

PS. Ingo - I love the restructuring of the scheduler bits. I think we need > 2 multipler though ... I set it to 10 for now. Tuning will tell ...

#55 lore raw

Re: [Lse-tech] Re: [patch] sched-2.5.59-A2

Quoted 7 lines
Quoted 4 lines

I repeated the tests with your B0 version and it's still not satisfying. Maybe too aggressive NODE_REBALANCE_IDLE_TICK, maybe the difference is that the other calls of load_balance() never have the chance to balance across nodes.

Nope, I found the problem. The topo cleanups are broken - we end up taking all mem accesses, etc to node 0.

Kernbench:

                                   Elapsed        User      System         CPU
                        2.5.59     20.032s     186.66s      47.73s       1170%
               2.5.59-ingo-mjb     19.986s    187.044s     48.592s     1178.8%

NUMA schedbench 4:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                        2.5.59        0.00       36.38       90.70        0.62
               2.5.59-ingo-mjb        0.00       34.70       88.58        0.69

NUMA schedbench 8:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                        2.5.59        0.00       42.78      249.77        1.85
               2.5.59-ingo-mjb        0.00       49.33      256.59        1.69

NUMA schedbench 16:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                        2.5.59        0.00       56.84      848.00        2.78
               2.5.59-ingo-mjb        0.00       65.67      875.05        3.58

NUMA schedbench 32:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                        2.5.59        0.00      116.36     1807.29        5.75
               2.5.59-ingo-mjb        0.00      142.77     2039.47        8.42

NUMA schedbench 64:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                        2.5.59        0.00      240.01     3634.20       14.57
               2.5.59-ingo-mjb        0.00      293.48     4534.99       20.62

System times are little higher (multipliers are set at busy = 10, idle = 10) .... I'll try setting the idle multipler to 100, but the other thing to do would be into increase the cross-node migrate resistance by setting some minimum imbalance offsets. That'll probably have to be node-specific ... something like the number of cpus per node ... but probably 0 for the simple HT systems.

M.

#56 lore raw

Re: [Lse-tech] Re: [patch] sched-2.5.59-A2

Quoted 9 lines · Martin J. Bligh

System times are little higher (multipliers are set at busy = 10, idle = 10) .... I'll try setting the idle multipler to 100, but the other thing to do would be into increase the cross-node migrate resistance by setting some minimum imbalance offsets. That'll probably have to be node-specific ... something like the number of cpus per node ... but probably 0 for the simple HT systems.

M.

I tried several values for the multipliers (IDLE_NODE_REBALANCE_TICK and BUSY_NODE_REBALANCE_TICK) on a 4 node NUMAQ (16 700MHZ Pentium III CPUs, 16 GB memory). The interesting results follow:

Kernels:

stock59 - linux 2.5.59 with cputime_stats patch
ingoI50B10 - stock59 with Ingo's B0 patch as modified by Martin
with a IDLE_NODE_REBALANCE_TICK multiplier of 50 and a BUSY_NODE_REBALANCE_TICK multiplier of 10
ingoI2B2 - stock59 with Ingos B0 patch with the original multipliers (2)

Kernbench:

                        Elapsed       User     System        CPU
          ingoI50B10    29.574s   284.922s    84.542s      1249%
             stock59    29.498s   283.976s     83.05s    1243.8%
            ingoI2B2    30.212s   289.718s    84.926s      1240%

Schedbench 4:

                        AvgUser    Elapsed  TotalUser   TotalSys
          ingoI50B10      22.49      37.04      90.00       0.86
             stock59      22.25      35.94      89.06       0.81
            ingoI2B2      24.98      40.71      99.98       1.03

Schedbench 8:

                        AvgUser    Elapsed  TotalUser   TotalSys
          ingoI50B10      31.16      49.63     249.32       1.86
             stock59      28.40      42.25     227.26       1.67
            ingoI2B2      36.81      59.38     294.57       2.02

Schedbench 16:

                        AvgUser    Elapsed  TotalUser   TotalSys
          ingoI50B10      52.73      56.61     843.91       3.56
             stock59      52.97      57.19     847.70       3.29
            ingoI2B2      57.88      71.32     926.29       5.51

Schedbench 32:

                        AvgUser    Elapsed  TotalUser   TotalSys
          ingoI50B10      58.85     139.76    1883.59       8.07
             stock59      56.57     118.05    1810.53       5.97
            ingoI2B2      61.48     137.38    1967.52      10.92

Schedbench 64:

                        AvgUser    Elapsed  TotalUser   TotalSys
          ingoI50B10      70.74     297.25    4528.25      19.09
             stock59      56.75     234.12    3632.72      15.70
            ingoI2B2      70.56     298.45    4516.67      21.41

Martin already posted numbers with 10/10 for the multipliers.

It looks like on the NUMAQ the 50/10 values give the best results, at least on these tests. I suspect that on other architectures the optimum numbers will vary. Most likely on machines with lower latency to off node memory, lower multipliers will help. It will be interesting to see numbers from Erich from the NEC IA64 boxes.

Signature · 2 lines
Michael Hohnbaum                      503-578-5486
[email protected]                   T/L 775-5486
#57 lore raw

PATCH 1/1 tunable rebalance rates for sched-2.5.59-B0

Hi,

I'm currently scanning the parameter space of IDLE_NODE_REBALANCE_TICK and BUSY_NODE_REBALANCE_TICK with the help of tunable rebalance rates. The patch basically does:

-#define IDLE_NODE_REBALANCE_TICK (IDLE_REBALANCE_TICK * 2) -#define BUSY_NODE_REBALANCE_TICK (BUSY_REBALANCE_TICK * 2)
+int idle_nodebalance_rate = 10;
+int busy_nodebalance_rate = 10;
+#define IDLE_NODE_REBALANCE_TICK (IDLE_REBALANCE_TICK * idle_nodebalance_rate) +#define BUSY_NODE_REBALANCE_TICK (BUSY_REBALANCE_TICK * busy_nodebalance_rate)

and makes the variables accessible in /proc/sys/kernel

We might want to leave these tunable in case it turns out that different platforms need significantly different values. Right now it's just a tool for tuning.

Regards,
Erich

include/linux/sysctl.h +2 -0
diff -urNp 2.5.59-B0/include/linux/sysctl.h 2.5.59-B0-tune/include/linux/sysctl.h
@@ -129,6 +129,8 @@ enum
 	KERN_CADPID=54,		/* int: PID of the process to notify on CAD */
 	KERN_PIDMAX=55,		/* int: PID # limit */
   	KERN_CORE_PATTERN=56,	/* string: pattern for core-file names */
+  	KERN_NODBALI=57,	/* int: idle cross-node balance rate */
+  	KERN_NODBALB=58,	/* int: busy cross-node balance rate */
 };
 
 
kernel/sched.c +5 -3
diff -urNp 2.5.59-B0/kernel/sched.c 2.5.59-B0-tune/kernel/sched.c
@@ -984,12 +984,14 @@ out:
  * busy-rebalance every 200 msecs. idle-rebalance every 1 msec. (or on
  * systems with HZ=100, every 10 msecs.)
  *
- * On NUMA, do a node-rebalance every 400 msecs.
+ * On NUMA, do a node-rebalance every 10ms (idle) or 2 secs (busy).
  */
 #define IDLE_REBALANCE_TICK (HZ/1000 ?: 1)
 #define BUSY_REBALANCE_TICK (HZ/5 ?: 1)
-#define IDLE_NODE_REBALANCE_TICK (IDLE_REBALANCE_TICK * 2)
-#define BUSY_NODE_REBALANCE_TICK (BUSY_REBALANCE_TICK * 2)
+int idle_nodebalance_rate = 10;
+int busy_nodebalance_rate = 10;
+#define IDLE_NODE_REBALANCE_TICK (IDLE_REBALANCE_TICK * idle_nodebalance_rate)
+#define BUSY_NODE_REBALANCE_TICK (BUSY_REBALANCE_TICK * busy_nodebalance_rate)
 
 #if CONFIG_NUMA
 static void balance_node(runqueue_t *this_rq, int idle, int this_cpu)
kernel/sysctl.c +6 -0
diff -urNp 2.5.59-B0/kernel/sysctl.c 2.5.59-B0-tune/kernel/sysctl.c
@@ -55,6 +55,8 @@ extern char core_pattern[];
 extern int cad_pid;
 extern int pid_max;
 extern int sysctl_lower_zone_protection;
+extern int idle_nodebalance_rate;
+extern int busy_nodebalance_rate;
 
 /* this is needed for the proc_dointvec_minmax for [fs_]overflow UID and GID */
 static int maxolduid = 65535;
@@ -261,6 +263,10 @@ static ctl_table kern_table[] = {
 #endif
 	{KERN_PIDMAX, "pid_max", &pid_max, sizeof (int),
 	 0600, NULL, &proc_dointvec},
+	{KERN_NODBALI, "idle_nodebalance_rate", &idle_nodebalance_rate,
+	 sizeof (int), 0600, NULL, &proc_dointvec},
+	{KERN_NODBALB, "busy_nodebalance_rate", &busy_nodebalance_rate,
+	 sizeof (int), 0600, NULL, &proc_dointvec},
 	{0}
 };
 
#58 lore raw

Re: [patch] sched-2.5.59-A2

In reply to Michael Hohnbaum

The scan through a piece of the parameter space delivered quite unconclusive results. I used the IDLE_NODE_REBALANCE_TICK multipliers 2, 5, 10, 20, 50 and the BUSY_NODE_REBALANCE_TICK multipliers 2, 5, 10, 20.

The benchmarks I tried were kernbench (average and error of 5 kernel compiles) and hackbench (5 runs for each number of chatter groups (10,25,50,100). The 2.5.59 scheduler result is printed first, then a matrix with all combinations of idle and busy rebalance multipliers. Each value is followed by its standard error (coming from the 5 measurements). I didn't measure numa_bench, those values depend mostly on the initial load balancing and showed no clear tendency/difference.

The machine is an NEC TX7 (small version, 8 Itanium2 CPUs in 4 nodes).

The results:
- kernbench UserTime is best for the 2.5.59 scheduler (623s). IngoB0 best value 627.33s for idle=20ms, busy=2000ms.
- hackbench: 2.5.59 scheduler is significantly better for all measurements.

I suppose this comes from the fact that the 2.5.59 version has the chance to load_balance across nodes when a cpu goes idle. No idea what other reason it could be... Maybe anybody else?

Kernbench:
==========
2.5.59 : Elapsed = 86.29(1.24)
ingo B0 : Elapsed
idle 2 5 10 20 50
busy

2       86.25(0.45)  86.62(1.56)  86.29(0.99)  85.99(0.60)  86.91(1.09)
5       86.87(1.12)  86.38(0.82)  86.00(0.69)  86.14(0.39)  86.47(0.68)
10      86.06(0.18)  86.23(0.38)  86.63(0.57)  86.82(0.95)  86.06(0.15)
20      86.64(1.24)  86.43(0.74)  86.15(0.99)  86.76(1.34)  86.70(0.68)

2.5.59 : UserTime = 623.24(0.46)
ingo B0 : UserTime
idle 2 5 10 20 50
busy

2       629.05(0.32)  628.54(0.53)  628.51(0.32)  628.66(0.23)  628.72(0.20)
5       628.14(0.88)  628.10(0.76)  628.33(0.41)  628.45(0.48)  628.11(0.37)
10      627.97(0.30)  627.77(0.23)  627.75(0.21)  627.33(0.45)  627.63(0.52)
20      627.55(0.36)  627.67(0.58)  627.36(0.67)  627.84(0.28)  627.69(0.59)

2.5.59 : SysTime = 21.83(0.16)
ingo B0 : SysTime
idle 2 5 10 20 50
busy

2       21.99(0.26)  21.89(0.12)  22.12(0.16)  22.06(0.21)  22.44(0.51)
5       22.07(0.21)  22.29(0.54)  22.15(0.08)  22.09(0.26)  21.90(0.18)
10      22.01(0.20)  22.42(0.42)  22.28(0.23)  22.04(0.37)  22.41(0.26)
20      22.03(0.20)  22.08(0.30)  22.31(0.27)  22.03(0.19)  22.35(0.33)

Hackbench 10
=============
2.5.59 : 0.77(0.03)
ingo B0:
idle 2 5 10 20 50
busy

2       0.90(0.07)  0.88(0.05)  0.84(0.05)  0.82(0.04)  0.85(0.06)
5       0.87(0.05)  0.90(0.07)  0.88(0.08)  0.89(0.09)  0.86(0.07)
10      0.85(0.06)  0.83(0.05)  0.86(0.08)  0.84(0.06)  0.87(0.06)
20      0.85(0.05)  0.87(0.07)  0.83(0.05)  0.86(0.07)  0.87(0.05)

Hackbench 25
=============
2.5.59 : 1.96(0.05)
ingo B0:
idle 2 5 10 20 50
busy

2       2.20(0.13)  2.21(0.12)  2.23(0.10)  2.20(0.10)  2.16(0.07)
5       2.13(0.12)  2.17(0.13)  2.18(0.08)  2.10(0.11)  2.16(0.10)
10      2.19(0.08)  2.21(0.12)  2.22(0.09)  2.11(0.10)  2.15(0.10)
20      2.11(0.17)  2.13(0.08)  2.18(0.06)  2.13(0.11)  2.13(0.14)

Hackbench 50
=============
2.5.59 : 3.78(0.10)
ingo B0:
idle 2 5 10 20 50
busy

2       4.31(0.13)  4.30(0.29)  4.29(0.15)  4.23(0.20)  4.14(0.10)
5       4.35(0.16)  4.34(0.24)  4.24(0.24)  4.09(0.18)  4.12(0.14)
10      4.35(0.23)  4.21(0.14)  4.36(0.24)  4.18(0.12)  4.36(0.21)
20      4.34(0.14)  4.27(0.17)  4.18(0.18)  4.29(0.24)  4.08(0.09)

Hackbench 100
==============
2.5.59 : 7.85(0.37)
ingo B0:
idle 2 5 10 20 50
busy

2       8.21(0.42)  8.07(0.25)  8.32(0.30)  8.06(0.26)  8.10(0.13)
5       8.13(0.25)  8.06(0.33)  8.14(0.49)  8.24(0.24)  8.04(0.20)
10      8.05(0.17)  8.16(0.13)  8.13(0.16)  8.05(0.24)  8.01(0.30)
20      8.21(0.25)  8.23(0.24)  8.36(0.41)  8.30(0.37)  8.10(0.30)

Regards,
Erich

#59 lore raw

Re: [patch] sched-2.5.59-A2

Quoted 9 lines · Erich Focht

The results:
- kernbench UserTime is best for the 2.5.59 scheduler (623s). IngoB0 best value 627.33s for idle=20ms, busy=2000ms.
- hackbench: 2.5.59 scheduler is significantly better for all measurements.

I suppose this comes from the fact that the 2.5.59 version has the chance to load_balance across nodes when a cpu goes idle. No idea what other reason it could be... Maybe anybody else?

this shows that agressive idle-rebalancing is the most important factor. I think this means that the unification of the balancing code should go into the other direction: ie. applying the ->nr_balanced logic to the SMP balancer as well.

kernelbench is the kind of benchmark that is most sensitive to over-eager global balancing, and since the 2.5.59 ->nr_balanced logic produced the best results, it clearly shows it's not over-eager. hackbench is one that is quite sensitive to under-balancing. Ie. trying to maximize both will lead us to a good balance.

Ingo

#60 lore raw

Re: [patch] sched-2.5.59-A2

Quoted 7 lines · Ingo Molnar
Quoted 6 lines · Erich Focht

The results:
- kernbench UserTime is best for the 2.5.59 scheduler (623s). IngoB0 best value 627.33s for idle=20ms, busy=2000ms.
- hackbench: 2.5.59 scheduler is significantly better for all measurements.

Quoted 8 lines
Quoted 3 lines

I suppose this comes from the fact that the 2.5.59 version has the chance to load_balance across nodes when a cpu goes idle. No idea what other reason it could be... Maybe anybody else?

this shows that agressive idle-rebalancing is the most important factor. I think this means that the unification of the balancing code should go into the other direction: ie. applying the ->nr_balanced logic to the SMP balancer as well.

Could you please explain your idea? As far as I understand, the SMP balancer (pre-NUMA) tries a global rebalance at each call. Maybe you mean something different...

Quoted 5 lines

kernelbench is the kind of benchmark that is most sensitive to over-eager global balancing, and since the 2.5.59 ->nr_balanced logic produced the best results, it clearly shows it's not over-eager. hackbench is one that is quite sensitive to under-balancing. Ie. trying to maximize both will lead us to a good balance.

Yes! Actually the currently implemented nr_balanced logic is pretty
dumb: the counter reaches the cross-node balance threshold after a certain number of calls to intra-node lb, no matter whether these were successfull or not. I'd like to try incrementing the counter only on unsuccessfull load balances, this would give a clear priority to intra-node balancing and a clear and controllable delay for cross-node balancing. A tiny patch for this (for 2.5.59) is attached. As the name nr_balanced would be misleading for this kind of usage, I renamed it to nr_lb_failed.

Regards,
Erich

kernel/sched.c +8 -4
diff -urNp 2.5.59-topo/kernel/sched.c 2.5.59-topo-succ/kernel/sched.c
@@ -156,7 +156,7 @@ struct runqueue {
 	int prev_nr_running[NR_CPUS];
 #ifdef CONFIG_NUMA
 	atomic_t *node_nr_running;
-	unsigned int nr_balanced;
+	unsigned int nr_lb_failed;
 	int prev_node_load[MAX_NUMNODES];
 #endif
 	task_t *migration_thread;
@@ -770,11 +770,11 @@ static inline unsigned long cpus_to_bala
 	int this_node = __cpu_to_node(this_cpu);
 	/*
 	 * Avoid rebalancing between nodes too often.
-	 * We rebalance globally once every NODE_BALANCE_RATE load balances.
+	 * We rebalance globally after NODE_BALANCE_RATE failed load balances.
 	 */
-	if (++(this_rq->nr_balanced) == NODE_BALANCE_RATE) {
+	if (this_rq->nr_lb_failed == NODE_BALANCE_RATE) {
 		int node = find_busiest_node(this_node);
-		this_rq->nr_balanced = 0;
+		this_rq->nr_lb_failed = 0;
 		if (node >= 0)
 			return (__node_to_cpu_mask(node) | (1UL << this_cpu));
 	}
@@ -892,6 +892,10 @@ static inline runqueue_t *find_busiest_q
 		busiest = NULL;
 	}
 out:
+#ifdef CONFIG_NUMA
+	if (!busiest)
+		this_rq->nr_lb_failed++;
+#endif
 	return busiest;
 }
 
#61 lore raw

Re: [patch] sched-2.5.59-A2

Quoted 3 lines · Erich Focht

Could you please explain your idea? As far as I understand, the SMP balancer (pre-NUMA) tries a global rebalance at each call. Maybe you mean something different...

yes, but eg. in the idle-rebalance case we are more agressive at moving tasks across SMP CPUs. We could perhaps do a similar ->nr_balanced logic to do this 'agressive' balancing even if not triggered from the CPU-will-be-idle path. Ie. _perhaps_ the SMP balancer could become a bit more agressive.

ie. SMP is just the first level in the cache-hierarchy, NUMA is the second level. (lets hope we dont have to deal with a third caching level anytime soon - although that could as well happen once SMT CPUs start doing NUMA.) There's no real reason to do balancing in a different way on each level - the weight might be different, but the core logic should be synced up. (one thing that is indeed different for the NUMA step is locality of uncached memory.)

Quoted 6 lines
Quoted 5 lines

kernelbench is the kind of benchmark that is most sensitive to over-eager global balancing, and since the 2.5.59 ->nr_balanced logic produced the best results, it clearly shows it's not over-eager. hackbench is one that is quite sensitive to under-balancing. Ie. trying to maximize both will lead us to a good balance.

Quoted 9 lines

Yes! Actually the currently implemented nr_balanced logic is pretty
dumb: the counter reaches the cross-node balance threshold after a certain number of calls to intra-node lb, no matter whether these were successfull or not. I'd like to try incrementing the counter only on unsuccessfull load balances, this would give a clear priority to intra-node balancing and a clear and controllable delay for cross-node balancing. A tiny patch for this (for 2.5.59) is attached. As the name nr_balanced would be misleading for this kind of usage, I renamed it to nr_lb_failed.

indeed this approach makes much more sense than the simple ->nr_balanced counter. A similar approach makes sense on the SMP level as well: if the current 'busy' rebalancer fails to get a new task, we can try the current 'idle' rebalancer. Ie. a CPU going idle would do the less intrusive rebalancing first.

have you experimented with making the counter limit == 1 actually? Ie. immediately trying to do a global balancing once the less intrusive balancing fails?

Ingo

#62 lore raw

Re: [patch] sched-2.5.59-A2

Quoted 4 lines · Ingo Molnar

ie. SMP is just the first level in the cache-hierarchy, NUMA is the second level. (lets hope we dont have to deal with a third caching level anytime soon - although that could as well happen once SMT CPUs start doing NUMA.)

or as Arjan points out, like the IBM x440 boxes ...

i think we want to handle SMT on a different level, ie. via the shared-runqueue approach, so it's not a genuine new level of caching, it's rather a new concept of multiple logical cores per physical core. (which needs is own code in the scheduler.)

Ingo

#63 lore raw

Re: [patch] sched-2.5.59-A2

Quoted 1 line

or as Arjan points out, like the IBM x440 boxes ...

;-)

Quoted 4 lines

i think we want to handle SMT on a different level, ie. via the shared-runqueue approach, so it's not a genuine new level of caching, it's rather a new concept of multiple logical cores per physical core. (which needs is own code in the scheduler.)

Do you have that code working already (presumably needs locking changes)? I seem to recall something like that existing already, but I don't recall if it was ever fully working or not ...

I think the large PPC64 boxes have multilevel NUMA as well - two real phys cores on one die, sharing some cache (L2 but not L1? Anton?). And SGI have multilevel nodes too I think ... so we'll still need multilevel NUMA at some point ... but maybe not right now.

M.

#64 lore raw

Re: [patch] sched-2.5.59-A2

Quoted 3 lines · Martin J. Bligh

Do you have that code working already (presumably needs locking changes)? I seem to recall something like that existing already, but I don't recall if it was ever fully working or not ...

yes, i have a HT testbox and working code:

http://lwn.net/Articles/8553/

the patch is rather old, i'll update it to 2.5.59.

Quoted 4 lines

I think the large PPC64 boxes have multilevel NUMA as well - two real phys cores on one die, sharing some cache (L2 but not L1? Anton?). And SGI have multilevel nodes too I think ... so we'll still need multilevel NUMA at some point ... but maybe not right now.

Intel's HT is the cleanest case: pure logical cores, which clearly need special handling. Whether the other SMT solutions want to be handled via the logical-cores code or via another level of NUMA-balancing code, depends on benchmarking results i suspect. It will be one more flexibility that system maintainers will have, it's all set up via the sched_map_runqueue(cpu1, cpu2) boot-time call that 'merges' a CPU's runqueue into another CPU's runqueue. It's basically the 0th level of balancing, which will be fundamentally different. The other levels of balancing are (or should be) similar to each other - only differing in weight of balancing, not differing in the actual algorithm.

Ingo

#65 lore raw

Re: [patch] sched-2.5.59-A2

Quoted 5 lines
Quoted 4 lines

I think the large PPC64 boxes have multilevel NUMA as well - two real phys cores on one die, sharing some cache (L2 but not L1? Anton?). And SGI have multilevel nodes too I think ... so we'll still need multilevel NUMA at some point ... but maybe not right now.

Quoted 10 lines

Intel's HT is the cleanest case: pure logical cores, which clearly need special handling. Whether the other SMT solutions want to be handled via the logical-cores code or via another level of NUMA-balancing code, depends on benchmarking results i suspect. It will be one more flexibility that system maintainers will have, it's all set up via the sched_map_runqueue(cpu1, cpu2) boot-time call that 'merges' a CPU's runqueue into another CPU's runqueue. It's basically the 0th level of balancing, which will be fundamentally different. The other levels of balancing are (or should be) similar to each other - only differing in weight of balancing, not differing in the actual algorithm.

I have included a very rough patch to do ht-numa topology. I requires to manually define CONFIG_NUMA and CONFIG_NUMA_SCHED. It also uses num_cpunodes instead of numnodes and defines MAX_NUM_NODES to 8 if CONFIG_NUMA is defined.

I had to remove the first check in sched_best_cpu() to get decent low load performance out of this. I am still sorting through some things, but I though it would be best if I just post what I have now.

-Andrew Theurer

arch/i386/kernel/smpboot.c +13 -1
diff -Naur linux-2.5.59-clean/arch/i386/kernel/smpboot.c linux-2.5.59-A2-HT-clean/arch/i386/kernel/smpboot.c
@@ -61,6 +61,7 @@
 int smp_num_siblings = 1;
 int phys_proc_id[NR_CPUS]; /* Package ID of each logical CPU */
 
+int num_cpunodes = 0;
 /* Bitmask of currently online CPUs */
 unsigned long cpu_online_map;
 
@@ -510,6 +511,10 @@
 static inline void map_cpu_to_node(int cpu, int node)
 {
 	printk("Mapping cpu %d to node %d\n", cpu, node);
+	if (!node_2_cpu_mask[node]) {
+		num_cpunodes++;
+		printk("nodecount is now %i\n", num_cpunodes);
+	}
 	node_2_cpu_mask[node] |= (1 << cpu);
 	cpu_2_node[cpu] = node;
 }
@@ -522,7 +527,11 @@
 	printk("Unmapping cpu %d from all nodes\n", cpu);
 	for (node = 0; node < MAX_NR_NODES; node ++)
 		node_2_cpu_mask[node] &= ~(1 << cpu);
-	cpu_2_node[cpu] = -1;
+	node = cpu_2_node[cpu];
+	if (node_2_cpu_mask[node])
+		num_cpunodes--;
+	cpu_2_node[node] = -1;
+	
 }
 #else /* !CONFIG_NUMA */
 
@@ -540,6 +549,9 @@
 
 	cpu_2_logical_apicid[cpu] = apicid;
 	map_cpu_to_node(cpu, apicid_to_node(apicid));
+	printk("cpu[%i]\tapicid[%i]\tnode[%i]\n", cpu, apicid, 
+			apicid_to_node(apicid));
+	printk("MAXNUMNODES[%i]\n", MAX_NUMNODES);
 }
 
 void unmap_cpu_to_logical_apicid(int cpu)
arch/i386/mach-default/topology.c +2 -2
diff -Naur linux-2.5.59-clean/arch/i386/mach-default/topology.c linux-2.5.59-A2-HT-clean/arch/i386/mach-default/topology.c
@@ -44,11 +44,11 @@
 	int i;
 
 	for (i = 0; i < num_online_nodes(); i++)
-		arch_register_node(i);
+//		arch_register_node(i);
 	for (i = 0; i < NR_CPUS; i++)
 		if (cpu_possible(i)) arch_register_cpu(i);
 	for (i = 0; i < num_online_memblks(); i++)
-		arch_register_memblk(i);
+//		arch_register_memblk(i);
 	return 0;
 }
 
drivers/base/Makefile +1 -1
diff -Naur linux-2.5.59-clean/drivers/base/Makefile linux-2.5.59-A2-HT-clean/drivers/base/Makefile
@@ -2,7 +2,7 @@
 
 obj-y		:= core.o sys.o interface.o power.o bus.o \
 			driver.o class.o intf.o platform.o \
-			cpu.o firmware.o
+			cpu.o firmware.o 
 
 obj-$(CONFIG_NUMA)	+= node.o  memblk.o
 
include/asm-i386/mach-default/mach_apic.h +9 -1
diff -Naur linux-2.5.59-clean/include/asm-i386/mach-default/mach_apic.h linux-2.5.59-A2-HT-clean/include/asm-i386/mach-default/mach_apic.h
@@ -60,7 +60,15 @@
 
 static inline int apicid_to_node(int logical_apicid)
 {
-	return 0;
+	int node = 0;
+
+	logical_apicid >>= 2;
+
+	while(logical_apicid) {
+		logical_apicid >>= 2;
+		node++;
+	}
+	return node;
 }
 
 /* Mapping from cpu number to logical apicid */
include/asm-i386/numnodes.h +1 -1
diff -Naur linux-2.5.59-clean/include/asm-i386/numnodes.h linux-2.5.59-A2-HT-clean/include/asm-i386/numnodes.h
@@ -6,7 +6,7 @@
 #ifdef CONFIG_X86_NUMAQ
 #include <asm/numaq.h>
 #else
-#define MAX_NUMNODES	1
+#define MAX_NUMNODES	8
 #endif /* CONFIG_X86_NUMAQ */
 
 #endif /* _ASM_MAX_NUMNODES_H */
include/linux/mmzone.h +4 -2
diff -Naur linux-2.5.59-clean/include/linux/mmzone.h linux-2.5.59-A2-HT-clean/include/linux/mmzone.h
@@ -11,12 +11,13 @@
 #include <linux/cache.h>
 #include <linux/threads.h>
 #include <asm/atomic.h>
-#ifdef CONFIG_DISCONTIGMEM
+#ifdef CONFIG_NUMA
 #include <asm/numnodes.h>
 #endif
 #ifndef MAX_NUMNODES
 #define MAX_NUMNODES 1
-#endif
+#endif 
+
 
 /* Free memory management - zoned buddy allocator.  */
 #ifndef CONFIG_FORCE_MAX_ZONEORDER
@@ -191,6 +192,7 @@
 } pg_data_t;
 
 extern int numnodes;
+extern int num_cpunodes;
 extern struct pglist_data *pgdat_list;
 
 void get_zone_counts(unsigned long *active, unsigned long *inactive,
kernel/sched.c +3 -3
diff -Naur linux-2.5.59-clean/kernel/sched.c linux-2.5.59-A2-HT-clean/kernel/sched.c
@@ -705,7 +705,7 @@
 		return best_cpu;
 
 	minload = 10000000;
-	for (i = 0; i < numnodes; i++) {
+	for (i = 0; i < num_cpunodes; i++) {
 		load = atomic_read(&node_nr_running[i]);
 		if (load < minload) {
 			minload = load;
@@ -730,7 +730,7 @@
 {
 	int new_cpu;
 
-	if (numnodes > 1) {
+	if (num_cpunodes > 1) {
 		new_cpu = sched_best_cpu(current);
 		if (new_cpu != smp_processor_id())
 			sched_migrate_task(current, new_cpu);
@@ -750,7 +750,7 @@
 	this_load = maxload = (this_rq()->prev_node_load[this_node] >> 1)
 		+ atomic_read(&node_nr_running[this_node]);
 	this_rq()->prev_node_load[this_node] = this_load;
-	for (i = 0; i < numnodes; i++) {
+	for (i = 0; i < num_cpunodes; i++) {
 		if (i == this_node)
 			continue;
 		load = (this_rq()->prev_node_load[i] >> 1)
#66 lore raw

Re: [patch] sched-2.5.59-A2

Quoted 16 lines
Quoted 5 lines
Quoted 4 lines

I think the large PPC64 boxes have multilevel NUMA as well - two real phys cores on one die, sharing some cache (L2 but not L1? Anton?). And SGI have multilevel nodes too I think ... so we'll still need multilevel NUMA at some point ... but maybe not right now.

Quoted 10 lines

Intel's HT is the cleanest case: pure logical cores, which clearly need special handling. Whether the other SMT solutions want to be handled via the logical-cores code or via another level of NUMA-balancing code, depends on benchmarking results i suspect. It will be one more flexibility that system maintainers will have, it's all set up via the sched_map_runqueue(cpu1, cpu2) boot-time call that 'merges' a CPU's runqueue into another CPU's runqueue. It's basically the 0th level of balancing, which will be fundamentally different. The other levels of balancing are (or should be) similar to each other - only differing in weight of balancing, not differing in the actual algorithm.

Quoted 3 lines

I have included a very rough patch to do ht-numa topology. I requires to manually define CONFIG_NUMA and CONFIG_NUMA_SCHED. It also uses num_cpunodes instead of numnodes and defines MAX_NUM_NODES to 8 if CONFIG_NUMA is defined.

Whilst it's fine for benchmarking, I think this kind of overlap is a very bad idea long-term - the confusion introduced is just asking for trouble. And think what's going to happen when you mix HT and NUMA. If we're going to use this for HT, it needs abstracting out.

M.

#67 lore raw

Re: [patch] sched-2.5.59-A2

Quoted 10 lines
Quoted 5 lines

I have included a very rough patch to do ht-numa topology. I requires to manually define CONFIG_NUMA and CONFIG_NUMA_SCHED. It also uses num_cpunodes instead of numnodes and defines MAX_NUM_NODES to 8 if CONFIG_NUMA is defined.

Whilst it's fine for benchmarking, I think this kind of overlap is a very bad idea long-term - the confusion introduced is just asking for trouble. And think what's going to happen when you mix HT and NUMA. If we're going to use this for HT, it needs abstracting out.

I have no issues with using HT specific bits instead of NUMA. Design wise it would be nice if it could all be happy together, but if not, then so be it.

-Andrew Theurer

#68 lore raw

Re: [patch] sched-2.5.59-A2

Quoted 5 lines
Quoted 5 lines
Quoted 4 lines

I have included a very rough patch to do ht-numa topology. I requires to manually define CONFIG_NUMA and CONFIG_NUMA_SCHED. It also uses num_cpunodes instead of numnodes and defines MAX_NUM_NODES to 8 if CONFIG_NUMA is defined.

Quoted 7 lines
Quoted 4 lines

Whilst it's fine for benchmarking, I think this kind of overlap is a very bad idea long-term - the confusion introduced is just asking for trouble. And think what's going to happen when you mix HT and NUMA. If we're going to use this for HT, it needs abstracting out.

I have no issues with using HT specific bits instead of NUMA. Design wise it would be nice if it could all be happy together, but if not, then so be it.

That's not what I meant - we can share the code, we just need to abstract it out so you don't have to turn on CONFIG_NUMA. That was the point of the pooling patch I posted at the weekend. Anyway, let's decide on the best approach first, we can clean up the code for merging later.

M.

#69 lore raw

PATCH 1/1 HT scheduler, sched-2.5.59-D7

the attached patch (against 2.5.59) is my current scheduler tree, it includes two main areas of changes:

- interactivity improvements, mostly reworked bits from Andrea's tree and various tunings.

- HT scheduler: 'shared runqueue' concept plus related logic: HT-aware passive load balancing, active-balancing, HT-aware task pickup, HT-aware affinity and HT-aware wakeup.

the sched-2.5.59-D7 patch can also be downloaded from:

	http://redhat.com/~mingo/O(1)-scheduler/

the NUMA code compiles, but the boot code needs to be updated to make use of sched_map_runqueue(). Usage is very simple, the following call:

	sched_map_runqueue(0, 1);

merges CPU#1's runqueue into CPU#0's runqueue, so both CPU#0 and CPU#1 maps to runqueue#0 - runqueue#1 is inactive from that point on. The NUMA boot code needs to interpret the topology and merge CPUs that are on the same physical core, into one runqueue. The scheduler code will take care of all the rest.

there's a 'test_ht' boot option available on x86, that can be used to trigger a shared runqueue for the first two CPUs, for those who have no genuine HT boxes but want to give it a go.

(it complicates things that the interactivity changes to the scheduler are included here as well, but this was my base tree and i didnt want to go back.)

Ingo

arch/i386/kernel/cpu/proc.c renamed from arch/i386/kernel/cpu/proc.c.orig +8 -0
@@ -1,4 +1,5 @@
 #include <linux/smp.h>
+#include <linux/sched.h>
 #include <linux/timex.h>
 #include <linux/string.h>
 #include <asm/semaphore.h>
@@ -101,6 +102,13 @@
 		     fpu_exception ? "yes" : "no",
 		     c->cpuid_level,
 		     c->wp_works_ok ? "yes" : "no");
+#if CONFIG_SHARE_RUNQUEUE
+{
+	extern long __rq_idx[NR_CPUS];
+
+	seq_printf(m, "\nrunqueue\t: %d\n", __rq_idx[n]);
+}
+#endif
 
 	for ( i = 0 ; i < 32*NCAPINTS ; i++ )
 		if ( test_bit(i, c->x86_capability) &&
arch/i386/kernel/smpboot.c renamed from arch/i386/kernel/smpboot.c.orig +62 -12

107 lines not on this page · raw message

arch/i386/Kconfig renamed from arch/i386/Kconfig.orig +18 -0
@@ -408,6 +408,24 @@
 
 	  If you don't know what to do here, say N.
 
+choice
+
+	prompt "Hyperthreading Support"
+	depends on SMP
+	default NR_SIBLINGS_0
+
+config NR_SIBLINGS_0
+	bool "off"
+
+config NR_SIBLINGS_2
+	bool "2 siblings"
+
+config NR_SIBLINGS_4
+	bool "4 siblings"
+
+endchoice
+
+
 config PREEMPT
 	bool "Preemptible Kernel"
 	help
fs/pipe.c renamed from fs/pipe.c.orig +3 -3
@@ -117,7 +117,7 @@
 	up(PIPE_SEM(*inode));
 	/* Signal writers asynchronously that there is more room.  */
 	if (do_wakeup) {
-		wake_up_interruptible(PIPE_WAIT(*inode));
+		wake_up_interruptible_sync(PIPE_WAIT(*inode));
 		kill_fasync(PIPE_FASYNC_WRITERS(*inode), SIGIO, POLL_OUT);
 	}
 	if (ret > 0)
@@ -205,7 +205,7 @@
 	}
 	up(PIPE_SEM(*inode));
 	if (do_wakeup) {
-		wake_up_interruptible(PIPE_WAIT(*inode));
+		wake_up_interruptible_sync(PIPE_WAIT(*inode));
 		kill_fasync(PIPE_FASYNC_READERS(*inode), SIGIO, POLL_IN);
 	}
 	if (ret > 0) {
@@ -275,7 +275,7 @@
 		free_page((unsigned long) info->base);
 		kfree(info);
 	} else {
-		wake_up_interruptible(PIPE_WAIT(*inode));
+		wake_up_interruptible_sync(PIPE_WAIT(*inode));
 		kill_fasync(PIPE_FASYNC_READERS(*inode), SIGIO, POLL_IN);
 		kill_fasync(PIPE_FASYNC_WRITERS(*inode), SIGIO, POLL_OUT);
 	}
include/linux/sched.h renamed from include/linux/sched.h.orig +46 -1

71 lines not on this page · raw message

include/asm-i386/apic.h renamed from include/asm-i386/apic.h.orig +2 -0
@@ -98,4 +98,6 @@
 
 #endif /* CONFIG_X86_LOCAL_APIC */
 
+extern int phys_proc_id[NR_CPUS];
+
 #endif /* __ASM_APIC_H */
kernel/fork.c renamed from kernel/fork.c.orig +1 -1
@@ -876,7 +876,7 @@
 	 */
 	p->first_time_slice = 1;
 	current->time_slice >>= 1;
-	p->sleep_timestamp = jiffies;
+	p->last_run = jiffies;
 	if (!current->time_slice) {
 		/*
 	 	 * This case is rare, it happens when the parent has only
kernel/sys.c renamed from kernel/sys.c.orig +1 -1
@@ -220,7 +220,7 @@
 
 	if (error == -ESRCH)
 		error = 0;
-	if (niceval < task_nice(p) && !capable(CAP_SYS_NICE))
+	if (0 && niceval < task_nice(p) && !capable(CAP_SYS_NICE))
 		error = -EACCES;
 	else
 		set_user_nice(p, niceval);
kernel/sched.c renamed from kernel/sched.c.orig +391 -112

885 lines not on this page · raw message

init/main.c renamed from init/main.c.orig +7 -7
@@ -354,7 +354,14 @@
 
 static void rest_init(void)
 {
+	/* 
+	 *	We count on the initial thread going ok 
+	 *	Like idlers init is an unlocked kernel thread, which will
+	 *	make syscalls (and thus be locked).
+	 */
+	init_idle(current, smp_processor_id());
 	kernel_thread(init, NULL, CLONE_KERNEL);
+
 	unlock_kernel();
  	cpu_idle();
 } 
@@ -438,13 +445,6 @@
 	check_bugs();
 	printk("POSIX conformance testing by UNIFIX\n");
 
-	/* 
-	 *	We count on the initial thread going ok 
-	 *	Like idlers init is an unlocked kernel thread, which will
-	 *	make syscalls (and thus be locked).
-	 */
-	init_idle(current, smp_processor_id());
-
 	/* Do the rest non-__init'ed, we're now alive */
 	rest_init();
 }
#70 lore raw

Re: [patch] HT scheduler, sched-2.5.59-D7

Quoted 8 lines · Ingo Molnar

the attached patch (against 2.5.59) is my current scheduler tree, it includes two main areas of changes:

- interactivity improvements, mostly reworked bits from Andrea's tree and various tunings.

Thanks for doing this. Initial testing with one workload which is extremely bad with 2.5.59: huge improvement.

The workload is:

workstation> ssh laptop
laptop> setenv DISPLAY workstation:0
laptop> make -j0 bzImage&
laptop> some-x-application &

For some reason, X-across-ethernet performs terribly when there's a kernel compile on the client machine - lots of half-second lags.

All gone now.

wrt this:

	if (SMART_WAKE_CHILD) {
		if (unlikely(!current->array))
			__activate_task(p, rq);
		else {
			p->prio = current->prio;
			list_add_tail(&p->run_list, &current->run_list);
			p->array = current->array;
			p->array->nr_active++;
			nr_running_inc(rq);
		}

for some reason I decided that RT tasks need special handling here. I forget why though ;) Please double-check that.

kernel/sched.c renamed from kernel/sched.c~rcf-simple +15 -0
@@ -452,6 +452,8 @@ int wake_up_process(task_t * p)
 void wake_up_forked_process(task_t * p)
 {
 	runqueue_t *rq = this_rq_lock();
+	struct task_struct *this_task = current;
+	prio_array_t *array = this_task->array;
 
 	p->state = TASK_RUNNING;
 	if (!rt_task(p)) {
@@ -467,6 +469,19 @@ void wake_up_forked_process(task_t * p)
 	set_task_cpu(p, smp_processor_id());
 	activate_task(p, rq);
 
+	/*
+	 * Take caller off the head of the runqueue, so child will run first.
+	 */
+	if (array) {
+		if (!rt_task(current)) {
+			dequeue_task(this_task, array);
+			enqueue_task(this_task, array);
+		} else {
+			list_del(&this_task->run_list);
+			list_add_tail(&this_task->run_list,
+					array->queue + this_task->prio);
+		}
+	}
 	rq_unlock(rq);
 }
 
#71 lore raw

Re: [patch] HT scheduler, sched-2.5.59-D7

Quoted 6 lines · Andrew Morton
Quoted 5 lines · Ingo Molnar

the attached patch (against 2.5.59) is my current scheduler tree, it includes two main areas of changes:

Quoted 7 lines
Quoted 3 lines

- interactivity improvements, mostly reworked bits from Andrea's tree and various tunings.

Thanks for doing this. Initial testing with one workload which is extremely bad with 2.5.59: huge improvement.

Initial testing on my NUMA box looks good. So far, I only have kernbench numbers, but the system time shows a nice decrease, and the CPU % busy time has gone up.

Kernbench:

                        Elapsed       User     System        CPU
           ingoD7-59    28.944s   285.008s    79.998s    1260.8%
             stock59    29.668s   283.762s    82.286s      1233%

I'll try to get more testing in over the next few days.

There was one minor build error introduced by the patch:

#define NODE_THRESHOLD 125

was removed, but the NUMA code uses this.

Signature · 2 lines
Michael Hohnbaum                      503-578-5486
[email protected]                   T/L 775-5486
#72 lore raw

Re: [patch] HT scheduler, sched-2.5.59-D7

In reply to Ingo Molnar
Quoted 10 lines · Ingo Molnar

the attached patch (against 2.5.59) is my current scheduler tree, it includes two main areas of changes:

- interactivity improvements, mostly reworked bits from Andrea's tree and various tunings.

- HT scheduler: 'shared runqueue' concept plus related logic: HT-aware passive load balancing, active-balancing, HT-aware task pickup, HT-aware affinity and HT-aware wakeup.

I ran Erich's numatest on a system with this patch, plus the cputime_stats patch (so that we would get meaningful numbers), and found a problem. It appears that on the lightly loaded system sched_best_cpu is now loading up one node before moving on to the next. Once the system is loaded (i.e., a process per cpu) things even out. Before applying the D7 patch, processes were distributed evenly across nodes, even in low load situations.

The numbers below on schedbench show that on 4 and 8 process runs, the D7 patch gets the same average user time as on the 16 and greater runs. However, without the D7 patch, the 4 and 8 process runs tend to have significantly decreased average user time.

Below I'm including the summarized output, and then the detailed output for the relevant runs on both D7 patched systems and stock.

Overall performance is improved with the D7 patch, so I would like to find out and fix what went wrong on the light load cases and encourage the adoption of the the D7 patch (or at least the parts that make the NUMA scheduler even faster). I'm not likely to have time to chase this down for the next few days, so am posting results to see if anyone else can find the cause.

kernels:
* stock59-stats = stock 2.5.59 with the cputime_stats patch
* ingoD7-59.stats = testD7-59 = stock59-stats + Ingo's D7 patch

Kernbench:

                        Elapsed       User     System        CPU
           testD7-59     28.96s   285.314s    79.616s    1260.6%
     ingoD7-59.stats    28.824s   284.834s    79.164s    1263.6%
       stock59-stats    29.498s   283.976s     83.05s    1243.8%

Schedbench 4:

                        AvgUser    Elapsed  TotalUser   TotalSys
           testD7-59      53.19      53.43     212.81       0.59
     ingoD7-59.stats      44.77      46.52     179.10       0.78
       stock59-stats      22.25      35.94      89.06       0.81

Schedbench 8:

                        AvgUser    Elapsed  TotalUser   TotalSys
           testD7-59      53.22      53.66     425.81       1.40
     ingoD7-59.stats      39.44      47.15     315.62       1.62
       stock59-stats      28.40      42.25     227.26       1.67

Schedbench 16:

                        AvgUser    Elapsed  TotalUser   TotalSys
           testD7-59      52.84      58.26     845.49       2.78
     ingoD7-59.stats      52.85      57.31     845.68       3.29
       stock59-stats      52.97      57.19     847.70       3.29

Schedbench 32:

                        AvgUser    Elapsed  TotalUser   TotalSys
           testD7-59      56.77     122.51    1816.80       7.58
     ingoD7-59.stats      56.54     125.79    1809.67       6.97
       stock59-stats      56.57     118.05    1810.53       5.97

Schedbench 64:

                        AvgUser    Elapsed  TotalUser   TotalSys
           testD7-59      57.52     234.27    3681.86      18.18
     ingoD7-59.stats      58.25     242.61    3728.46      17.40
       stock59-stats      56.75     234.12    3632.72      15.70

Detailed stats from running numatest with 4 processes on the D7 patch. Note how most of the load is put on node 0.

Executing 4 times: ./randupdt 1000000
Running 'hackbench 20' in the background: Time: 5.039

Job  node00 node01 node02 node03 | iSched MSched | UserTime(s)
  1   100.0    0.0    0.0    0.0 |    0     0    |  46.27
  2    58.4    0.0    0.0   41.6 |    0     0    |  41.18
  3   100.0    0.0    0.0    0.0 |    0     0    |  45.72
  4   100.0    0.0    0.0    0.0 |    0     0    |  45.89
AverageUserTime 44.77 seconds
ElapsedTime     46.52
TotalUserTime   179.10
TotalSysTime    0.78

Detailed stats from running numatest with 8 processes on the D7 patch. In this one it appears that node 0 was loaded, then node 1.

Executing 8 times: ./randupdt 1000000
Running 'hackbench 20' in the background: Time: 11.185

Job  node00 node01 node02 node03 | iSched MSched | UserTime(s)
  1   100.0    0.0    0.0    0.0 |    0     0    |  46.89
  2   100.0    0.0    0.0    0.0 |    0     0    |  46.20
  3   100.0    0.0    0.0    0.0 |    0     0    |  46.31
  4     0.0  100.0    0.0    0.0 |    1     1    |  39.44
  5     0.0    0.0   99.9    0.0 |    2     2    |  16.00
  6    62.6    0.0    0.0   37.4 |    0     0    |  42.23
  7     0.0  100.0    0.0    0.0 |    1     1    |  39.12
  8     0.0  100.0    0.0    0.0 |    1     1    |  39.35
AverageUserTime 39.44 seconds
ElapsedTime     47.15
TotalUserTime   315.62
TotalSysTime    1.62

Control run - detailed stats running numatest with 4 processes on a stock59 kernel.

Executing 4 times: ./randupdt 1000000
Running 'hackbench 20' in the background: Time: 8.297

Job  node00 node01 node02 node03 | iSched MSched | UserTime(s)
  1     0.0   99.8    0.0    0.0 |    1     1    |  16.63
  2   100.0    0.0    0.0    0.0 |    0     0    |  27.83
  3     0.0    0.0   99.9    0.0 |    2     2    |  16.27
  4   100.0    0.0    0.0    0.0 |    0     0    |  28.29
AverageUserTime 22.25 seconds
ElapsedTime     35.94
TotalUserTime   89.06
TotalSysTime    0.81

Control run - detailed stats running numatest with 8 processes on a stock59 kernel.

Executing 8 times: ./randupdt 1000000
Running 'hackbench 20' in the background: Time: 9.458

Job  node00 node01 node02 node03 | iSched MSched | UserTime(s)
  1     0.0   99.9    0.0    0.0 |    1     1    |  27.77
  2   100.0    0.0    0.0    0.0 |    0     0    |  29.34
  3     0.0    0.0  100.0    0.0 |    2     2    |  28.03
  4     0.0    0.0    0.0  100.0 |    3     3    |  24.15
  5    13.1    0.0    0.0   86.9 |    0     3   *|  33.36
  6     0.0  100.0    0.0    0.0 |    1     1    |  27.94
  7     0.0    0.0  100.0    0.0 |    2     2    |  28.02
  8   100.0    0.0    0.0    0.0 |    0     0    |  28.58
Signature · 2 lines
Michael Hohnbaum            503-578-5486
[email protected]         T/L 775-5486
#73 lore raw

Re: [patch] HT scheduler, sched-2.5.59-D7

Quoted 6 lines · Ingo Molnar
Quoted 5 lines

the attached patch (against 2.5.59) is my current scheduler tree, it includes two main areas of changes:

- interactivity improvements, mostly reworked bits from Andrea's tree

and

Quoted 6 lines
Quoted 5 lines

various tunings.

- HT scheduler: 'shared runqueue' concept plus related logic: HT-aware passive load balancing, active-balancing, HT-aware task pickup, HT-aware affinity and HT-aware wakeup.

Quoted 7 lines

I ran Erich's numatest on a system with this patch, plus the cputime_stats patch (so that we would get meaningful numbers), and found a problem. It appears that on the lightly loaded system sched_best_cpu is now loading up one node before moving on to the next. Once the system is loaded (i.e., a process per cpu) things even out. Before applying the D7 patch, processes were distributed evenly across nodes, even in low load situations.

Michael, my experience has been that 2.5.59 loaded up the first node before distributing out tasks (at least on kernbench). The first check in sched_best_cpu would almost always place the new task on the same cpu, and intra node balance on an idle cpu in the same node would almost always steal it before a inter node balance could steal it. Also, sched_best_cpu does not appear to be changed in D7. Actually, I expected D7 to have the opposite effect you describe (although I have not tried it yet), since load_balance will now steal a running task if called by an idle cpu.

I'll try to get some of these tests on x440 asap to compare.

-Andrew Theurer

#74 lore raw

Re: [patch] HT scheduler, sched-2.5.59-D7

Quoted 2 lines

Michael, my experience has been that 2.5.59 loaded up the first node before distributing out tasks (at least on kernbench).

Could you throw a printk in map_cpu_to_node and check which cpus come out on which nodes?

Quoted 1 line

I'll try to get some of these tests on x440 asap to compare.

So what are you running on now? the HT stuff?

M.

#75 lore raw

Re: [patch] HT scheduler, sched-2.5.59-D7

Quoted 9 lines · Martin J. Bligh
Quoted 2 lines

Michael, my experience has been that 2.5.59 loaded up the first node before distributing out tasks (at least on kernbench).

Could you throw a printk in map_cpu_to_node and check which cpus come out on which nodes?

Quoted 1 line

I'll try to get some of these tests on x440 asap to compare.

So what are you running on now? the HT stuff?

I am running nothing right now, mainly because I don't have access to that HT system anymore. HT-numa may work better than it did with the new load_balance idle policy, but I'm not sure it's worth persuing with Ingo's HT patch. Let me know if you think it's worth investigating.

-Andrew Theurer

#76 lore raw

Re: [patch] HT scheduler, sched-2.5.59-D7

In reply to Andrew Theurer
Quoted 21 lines · Andrew Theurer
Quoted 6 lines · Ingo Molnar
Quoted 5 lines

the attached patch (against 2.5.59) is my current scheduler tree, it includes two main areas of changes:

- interactivity improvements, mostly reworked bits from Andrea's tree

and

Quoted 6 lines
Quoted 5 lines

various tunings.

- HT scheduler: 'shared runqueue' concept plus related logic: HT-aware passive load balancing, active-balancing, HT-aware task pickup, HT-aware affinity and HT-aware wakeup.

Quoted 7 lines

I ran Erich's numatest on a system with this patch, plus the cputime_stats patch (so that we would get meaningful numbers), and found a problem. It appears that on the lightly loaded system sched_best_cpu is now loading up one node before moving on to the next. Once the system is loaded (i.e., a process per cpu) things even out. Before applying the D7 patch, processes were distributed evenly across nodes, even in low load situations.

Quoted 2 lines

Michael, my experience has been that 2.5.59 loaded up the first node before distributing out tasks (at least on kernbench).

Well the data I posted doesn't support that conclusion - it showed at most two processes on the first node before moving to the next node for 2.5.59, but for the D7 patched system, the current node was fully loaded before putting processes on other nodes. I've repeated this on multiple runs and obtained similar results.

The first check in

Quoted 4 lines

sched_best_cpu would almost always place the new task on the same cpu, and intra node balance on an idle cpu in the same node would almost always steal it before a inter node balance could steal it. Also, sched_best_cpu does not appear to be changed in D7.

That is true, and is the only thing I've had a chance to look at. sched_best_cpu depends on data collected elsewhere, so my suspicion is that it is working with bad data. I'll try to find time this week to look further at it.

Actually, I expected D7 to have the

Quoted 4 lines

opposite effect you describe (although I have not tried it yet), since load_balance will now steal a running task if called by an idle cpu.

I'll try to get some of these tests on x440 asap to compare.

I'm interested in seeing these results. Any chance of getting time on a 4-node x440?

Quoted 4 lines

-Andrew Theurer

Signature · 2 lines
Michael Hohnbaum                      503-578-5486
[email protected]                   T/L 775-5486
#77 lore raw

PATCH 1/1 HT scheduler, sched-2.5.59-E2

In reply to Ingo Molnar

the attached patch (against 2.5.59 or BK-curr) has two HT-scheduler fixes over the -D7 patch:

- HT-aware task pickup did not do the right thing in an important
special-case: when there are 2 tasks running in a 2-CPU runqueue and one of the tasks reschedules but still stays runnable. In this case, instead of running the previous task again, the scheduler incorrectly picked the idle task, which in turn reduced performance.

- active load-balancing only worked in a limited way, due to an indexing bug, now it properly active-balances on all CPUs.

changes in -D7 over 2.5.59:

- interactivity improvements, mostly reworked bits from Andrea's tree and various tunings.

- HT scheduler: 'shared runqueue' concept plus related logic: HT-aware passive load balancing, active-balancing, HT-aware task pickup, HT-aware affinity and HT-aware wakeup.

the sched-2.5.59-E2 patch can also be downloaded from:

    http://redhat.com/~mingo/O(1)-scheduler/

	Ingo
arch/i386/kernel/cpu/proc.c renamed from arch/i386/kernel/cpu/proc.c.orig +8 -0
@@ -1,4 +1,5 @@
 #include <linux/smp.h>
+#include <linux/sched.h>
 #include <linux/timex.h>
 #include <linux/string.h>
 #include <asm/semaphore.h>
@@ -101,6 +102,13 @@
 		     fpu_exception ? "yes" : "no",
 		     c->cpuid_level,
 		     c->wp_works_ok ? "yes" : "no");
+#if CONFIG_SHARE_RUNQUEUE
+{
+	extern long __rq_idx[NR_CPUS];
+
+	seq_printf(m, "\nrunqueue\t: %d\n", __rq_idx[n]);
+}
+#endif
 
 	for ( i = 0 ; i < 32*NCAPINTS ; i++ )
 		if ( test_bit(i, c->x86_capability) &&
arch/i386/kernel/smpboot.c renamed from arch/i386/kernel/smpboot.c.orig +62 -12

107 lines not on this page · raw message

arch/i386/Kconfig renamed from arch/i386/Kconfig.orig +18 -0
@@ -408,6 +408,24 @@
 
 	  If you don't know what to do here, say N.
 
+choice
+
+	prompt "Hyperthreading Support"
+	depends on SMP
+	default NR_SIBLINGS_0
+
+config NR_SIBLINGS_0
+	bool "off"
+
+config NR_SIBLINGS_2
+	bool "2 siblings"
+
+config NR_SIBLINGS_4
+	bool "4 siblings"
+
+endchoice
+
+
 config PREEMPT
 	bool "Preemptible Kernel"
 	help
fs/pipe.c renamed from fs/pipe.c.orig +3 -3
@@ -117,7 +117,7 @@
 	up(PIPE_SEM(*inode));
 	/* Signal writers asynchronously that there is more room.  */
 	if (do_wakeup) {
-		wake_up_interruptible(PIPE_WAIT(*inode));
+		wake_up_interruptible_sync(PIPE_WAIT(*inode));
 		kill_fasync(PIPE_FASYNC_WRITERS(*inode), SIGIO, POLL_OUT);
 	}
 	if (ret > 0)
@@ -205,7 +205,7 @@
 	}
 	up(PIPE_SEM(*inode));
 	if (do_wakeup) {
-		wake_up_interruptible(PIPE_WAIT(*inode));
+		wake_up_interruptible_sync(PIPE_WAIT(*inode));
 		kill_fasync(PIPE_FASYNC_READERS(*inode), SIGIO, POLL_IN);
 	}
 	if (ret > 0) {
@@ -275,7 +275,7 @@
 		free_page((unsigned long) info->base);
 		kfree(info);
 	} else {
-		wake_up_interruptible(PIPE_WAIT(*inode));
+		wake_up_interruptible_sync(PIPE_WAIT(*inode));
 		kill_fasync(PIPE_FASYNC_READERS(*inode), SIGIO, POLL_IN);
 		kill_fasync(PIPE_FASYNC_WRITERS(*inode), SIGIO, POLL_OUT);
 	}
include/linux/sched.h renamed from include/linux/sched.h.orig +46 -1

71 lines not on this page · raw message

include/asm-i386/apic.h renamed from include/asm-i386/apic.h.orig +2 -0
@@ -98,4 +98,6 @@
 
 #endif /* CONFIG_X86_LOCAL_APIC */
 
+extern int phys_proc_id[NR_CPUS];
+
 #endif /* __ASM_APIC_H */
kernel/fork.c renamed from kernel/fork.c.orig +1 -1
@@ -876,7 +876,7 @@
 	 */
 	p->first_time_slice = 1;
 	current->time_slice >>= 1;
-	p->sleep_timestamp = jiffies;
+	p->last_run = jiffies;
 	if (!current->time_slice) {
 		/*
 	 	 * This case is rare, it happens when the parent has only
kernel/sys.c renamed from kernel/sys.c.orig +1 -1
@@ -220,7 +220,7 @@
 
 	if (error == -ESRCH)
 		error = 0;
-	if (niceval < task_nice(p) && !capable(CAP_SYS_NICE))
+	if (0 && niceval < task_nice(p) && !capable(CAP_SYS_NICE))
 		error = -EACCES;
 	else
 		set_user_nice(p, niceval);
kernel/sched.c renamed from kernel/sched.c.orig +389 -108

876 lines not on this page · raw message

init/main.c renamed from init/main.c.orig +7 -7
@@ -354,7 +354,14 @@
 
 static void rest_init(void)
 {
+	/* 
+	 *	We count on the initial thread going ok 
+	 *	Like idlers init is an unlocked kernel thread, which will
+	 *	make syscalls (and thus be locked).
+	 */
+	init_idle(current, smp_processor_id());
 	kernel_thread(init, NULL, CLONE_KERNEL);
+
 	unlock_kernel();
  	cpu_idle();
 } 
@@ -438,13 +445,6 @@
 	check_bugs();
 	printk("POSIX conformance testing by UNIFIX\n");
 
-	/* 
-	 *	We count on the initial thread going ok 
-	 *	Like idlers init is an unlocked kernel thread, which will
-	 *	make syscalls (and thus be locked).
-	 */
-	init_idle(current, smp_processor_id());
-
 	/* Do the rest non-__init'ed, we're now alive */
 	rest_init();
 }
#78 lore raw

Re: [patch] HT scheduler, sched-2.5.59-E2

Quoted 2 lines · Ingo Molnar

the attached patch (against 2.5.59 or BK-curr) has two HT-scheduler fixes over the -D7 patch:

Hi, Ingo. I am running this now, with good results. Unfortunately I do not have an HT-capable processor, so I am only testing the interactivity improvements. They are looking very good - a step in the right direction. Very nice.

A couple bits:

Review

Quoted 8 lines
(quoted diff) +3 -3
-		wake_up_interruptible(PIPE_WAIT(*inode));
+		wake_up_interruptible_sync(PIPE_WAIT(*inode));
...
-		wake_up_interruptible(PIPE_WAIT(*inode));
+		wake_up_interruptible_sync(PIPE_WAIT(*inode));
...
-		wake_up_interruptible(PIPE_WAIT(*inode));
+		wake_up_interruptible_sync(PIPE_WAIT(*inode));

These are not correct, right? I believe we want normal behavior here, no?

kernel/sys.c line 223

Quoted 8 lines
kernel/sys.c renamed from kernel/sys.c.orig +1 -1
@@ -220,7 +220,7 @@
 
 	if (error == -ESRCH)
 		error = 0;
-	if (niceval < task_nice(p) && !capable(CAP_SYS_NICE))
+	if (0 && niceval < task_nice(p) && !capable(CAP_SYS_NICE))

What is the point of this? Left in for debugging?

kernel/sys.c line 225

Quoted 4 lines
kernel/sys.c renamed from kernel/sys.c.orig +2 -2
-#define MAX_SLEEP_AVG		(2*HZ)
-#define STARVATION_LIMIT	(2*HZ)
+#define MAX_SLEEP_AVG		(10*HZ)
+#define STARVATION_LIMIT	(30*HZ)

Do you really want a 30 second starvation limit? Ouch.

kernel/sys.c line 226

Quoted 1 line
kernel/sys.c renamed from kernel/sys.c.orig +1 -0
+	printk("rq_idx(smp_processor_id()): %ld.\n", rq_idx(smp_processor_id()));

This gives a compiler warning on UP:

kernel/sched.c: In function `sched_init':
kernel/sched.c:2722: warning: long int format, int arg (arg 2)

Since rq_idx(), on UP, merely returns its parameter which is an int.

Otherwise, looking nice :)

Robert Love

#79 lore raw

Re: [patch] HT scheduler, sched-2.5.59-E2

In reply to Ingo Molnar

Hi Ingo,

kernel/sched.c line 1104

Quoted 8 lines · Ingo Molnar

-#define
CAN_MIGRATE_TASK(p,rq,this_cpu) \

kernel/sched.c renamed from kernel/sched.c.orig +0 -3
-       ((jiffies - (p)->sleep_timestamp > cache_decay_ticks) &&        \
-               !task_running(rq, p) &&                                 \
-                       ((p)->cpus_allowed & (1UL << (this_cpu)))) +#define

CAN_MIGRATE_TASK(p,rq,cpu) \

kernel/sched.c renamed from kernel/sched.c.orig +2 -0
+       ((idle || (jiffies - (p)->last_run > cache_decay_ticks)) && \
+               !task_running(p) && task_allowed(p, cpu))

at least for NUMA systems this is too aggressive (though I believe normal SMP systems could be hurt, too).

The problem: freshly forked tasks are stolen by idle cpus on the same node before they exec. This actually disables the sched_balance_exec() mechanism as the tasks to be balanced already run alone on other CPUs. Which means: the whole benefit of having balanced nodes (maximize the memory bandwidth) is gone.

The change below is less aggressive but in the same philosophy. Could you please take it instead?

Review

Quoted 3 lines

CAN_MIGRATE_TASK(p,rq,cpu) \

(quoted diff) +2 -0
+       ((jiffies - (p)->last_run > (cache_decay_ticks >> idle)) && \
+               !task_running(p) && task_allowed(p, cpu))

Regards,
Erich

#80 lore raw

Re: [patch] sched-2.5.59-A2

In reply to Ingo Molnar
Quoted 5 lines

yes, but eg. in the idle-rebalance case we are more agressive at moving tasks across SMP CPUs. We could perhaps do a similar ->nr_balanced logic to do this 'agressive' balancing even if not triggered from the CPU-will-be-idle path. Ie. _perhaps_ the SMP balancer could become a bit more agressive.

Do you think it's worth looking at the initial load-balance code for standard SMP?

Quoted 3 lines

ie. SMP is just the first level in the cache-hierarchy, NUMA is the second level. (lets hope we dont have to deal with a third caching level anytime soon - although that could as well happen once SMT CPUs start doing NUMA.)

We have those already (IBM x440) ;-) That's one of the reasons why I prefer the pools concept I posted at the weekend over just "nodes". Also, there are NUMA machines where nodes are not all equidistant ... that can be thought of as multi-level too.

Quoted 4 lines

There's no real reason to do balancing in a different way on each level - the weight might be different, but the core logic should be synced up. (one thing that is indeed different for the NUMA step is locality of uncached memory.)

Right, the current model should work fine, it just needs generalising out a bit.

M

#81 lore raw

Re: [patch] sched-2.5.59-A2

In reply to Ingo Molnar
Quoted 10 lines · Ingo Molnar
Quoted 3 lines · Erich Focht

Could you please explain your idea? As far as I understand, the SMP balancer (pre-NUMA) tries a global rebalance at each call. Maybe you mean something different...

yes, but eg. in the idle-rebalance case we are more agressive at moving tasks across SMP CPUs. We could perhaps do a similar ->nr_balanced logic to do this 'agressive' balancing even if not triggered from the CPU-will-be-idle path. Ie. _perhaps_ the SMP balancer could become a bit more agressive.

Do you mean: make the SMP balancer more aggressive by lowering the 125% threshold?

Quoted 7 lines

ie. SMP is just the first level in the cache-hierarchy, NUMA is the second level. (lets hope we dont have to deal with a third caching level anytime soon - although that could as well happen once SMT CPUs start doing NUMA.) There's no real reason to do balancing in a different way on each level - the weight might be different, but the core logic should be synced up. (one thing that is indeed different for the NUMA step is locality of uncached memory.)

We have an IA64 2-level node hierarchy machine with 32 CPUs (NEC TX7). In the "old" node affine scheduler patch the multilevel feature was in by different cross-node steal delays (longer if node is further away). In the current approach we could just add another counter, such that we call the cross-supernode balancer only if the intra-supernode balancer failed a few times. No idea whether this helps...

Quoted 16 lines
Quoted 9 lines

Yes! Actually the currently implemented nr_balanced logic is pretty
dumb: the counter reaches the cross-node balance threshold after a certain number of calls to intra-node lb, no matter whether these were successfull or not. I'd like to try incrementing the counter only on unsuccessfull load balances, this would give a clear priority to intra-node balancing and a clear and controllable delay for cross-node balancing. A tiny patch for this (for 2.5.59) is attached. As the name nr_balanced would be misleading for this kind of usage, I renamed it to nr_lb_failed.

indeed this approach makes much more sense than the simple ->nr_balanced counter. A similar approach makes sense on the SMP level as well: if the current 'busy' rebalancer fails to get a new task, we can try the current 'idle' rebalancer. Ie. a CPU going idle would do the less intrusive rebalancing first.

Quoted 3 lines

have you experimented with making the counter limit == 1 actually? Ie. immediately trying to do a global balancing once the less intrusive balancing fails?

Didn't have time to try and probably won't be able to check this before the beginning of next week :-( .

Regards,
Erich

#82 lore raw

Re: [patch] sched-2.5.59-A2

In reply to Ingo Molnar
Quoted 3 lines

kernelbench is the kind of benchmark that is most sensitive to over-eager global balancing, and since the 2.5.59 ->nr_balanced logic produced the best results, it clearly shows it's not over-eager.

Careful ... what shows well on one machine may not on another - this depends heavily on the NUMA ratio - for our machine the nr_balanced logic in 59 is still over-agressive (20:1 NUMA ratio). For low-ratio machines it may work fine. It actually works best for us when it's switched off altogether I think (which is obviously not a good solution).

But there's more than one dimension to tune here - we can tune both the frequency and the level of imbalance required. I had good results specifying a minimum imbalance of > 4 between the current and busiest nodes before balancing. Reason (2 nodes, 4 CPUs each): If I have 4 tasks on one node, and 8 on another, that's still one or two per cpu in all cases whatever I do (well, provided I'm not stupid enough to make anything idle). So at that point, I just want lowest task thrash.

Moving tasks between nodes is really expensive, and shouldn't be done lightly - the only thing the background busy rebalancer should be fixing is significant long-term imbalances. It would be nice if we also chose the task with the smallest RSS to migrate, I think that's a worthwhile optimisation (we'll need to make sure we use realistic benchmarks with a mix of different task sizes). Working out which ones have the smallest "on-node RSS - off-node RSS" is another step after that ...

Quoted 2 lines

hackbench is one that is quite sensitive to under-balancing. Ie. trying to maximize both will lead us to a good balance.

I'll try to do some hackbench runs on NUMA-Q as well.

Just to add something else to the mix, there's another important factor as well as the NUMA ratio - the size of the interconnect cache vs the size of the task migrated. The interconnect cache on the NUMA-Q is 32Mb, our newer machine has a much lower NUMA ratio, but effectively a much smaller cache as well. NUMA ratios are often expresssed in terms of latency, but there's a bandwidth consideration too. Hyperthreading will want something different again.

I think we definitely need to tune this on a per-arch basis. There's no way that one-size-fits-all is going to fit a situation as complex as this (though we can definitely learn from each other's analysis).

M.

#83 lore raw

Re: [patch] sched-2.5.59-A2

Quoted 3 lines · Martin J. Bligh

I think we definitely need to tune this on a per-arch basis. There's no way that one-size-fits-all is going to fit a situation as complex as this (though we can definitely learn from each other's analysis).

agreed - although the tunable should be constant (if possible, or boot-established but not /proc exported), and there should be as few tunables as possible. We already tune some of our scheduler behavior to the SMP cachesize. (the cache_decay_ticks SMP logic.)

Ingo

#84 lore raw

Re: [patch] sched-2.5.59-A2

In reply to Martin J. Bligh
Quoted 6 lines · Martin J. Bligh
Quoted 4 lines

I repeated the tests with your B0 version and it's still not satisfying. Maybe too aggressive NODE_REBALANCE_IDLE_TICK, maybe the difference is that the other calls of load_balance() never have the chance to balance across nodes.

Quoted 6 lines

Nope, I found the problem. The topo cleanups are broken - we end up taking all mem accesses, etc to node 0.

Use the second half of the patch (the splitup I already posted), and fix the obvious compile error. Works fine now ;-)

Matt, you know the topo stuff better than anyone. Can you take a look at the cleanup Ingo did, and see if it's easily fixable?

Umm.. most of it looks clean. I'm not really sure what the __cpu_to_node_mask(cpu) macro is supposed to do? it looks to be just an alias for the __node_to_cpu_mask() macro, which makes little sense to me. That's the only thing that immediately sticks out. I'm doubly confused as to why it's defined twice in include/linux/topology.h?

-Matt

Quoted 6 lines

M.

PS. Ingo - I love the restructuring of the scheduler bits. I think we need > 2 multipler though ... I set it to 10 for now. Tuning will tell ...

#85 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

In reply to Ingo Molnar

Hi Ingo,

Quoted 12 lines · Ingo Molnar
Quoted 10 lines · Martin J. Bligh
Quoted 5 lines

complex. It's the one that is aware of the global scheduling picture. For NUMA i'd suggest two asynchronous frequencies: one intra-node frequency, and an inter-node frequency - configured by the architecture and roughly in the same proportion to each other as cachemiss latencies.

That's exactly what's in the latest set of patches - admittedly it's a multiplier of when we run load_balance, not the tick multiplier, but that's very easy to fix. Can you check out the stuff I posted last night? I think it's somewhat cleaner ...

Quoted 6 lines

yes, i saw it, it has the same tying between idle-CPU-rebalance and inter-node rebalance, as Erich's patch. You've put it into cpus_to_balance(), but that still makes rq->nr_balanced a 'synchronously' coupled balancing act. There are two synchronous balancing acts currently:
the 'CPU just got idle' event, and the exec()-balancing (*) event. Neither must involve any 'heavy' balancing, only local balancing.

I prefer a single point of entry called load_balance() to multiple functionally different balancers. The reason is that the later choice might lead to balancers competing or working against each other. Not now but the design could mislead to such developments.

But the main other reasons for calling the cross-node balancer after NODE_BALANCE_RATE calls to the intra-node balancer (you call it synchronous balancing) is performance:

Davide Libenzi showed quite a while ago that one benefits a lot if the idle CPUs stay idle for rather short time. IIRC, his conclusion for the multi-queue scheduler was that an order of magnitude of 10ms is long enough, below you start feeling the balancing overhead, above you waste useful cycles.

On a NUMA system this is even more important: the longer you leave fresh tasks on an overloaded node, the more probable it is that they allocate their memory there. And then they will run with poor performance on the node which stayed idle for 200-400ms before stealing them. So one wastes 200-400ms on each CPU of the idle node and at the end gets tasks which perform poorly, anyway. If the tasks are "old", at least we didn't waste too much time beeing idle. The long-term target should be that the tasks should remember where their memory is and return to that node.

Quoted 3 lines

The inter-node
balancing (which is heavier than even the global SMP balancer), should never be triggered from the high-frequency path.

Hmmm, we made it really slim. Actually the cross-node balancing might even be cheaper than the global SMP balancer:
- it first loops over the nodes (loop length 4 on a 16 CPU NUMA-Q & Azusa)
- then it loops over the cpumask of the most loaded node + the current CPU (loop length 5 on a NUMA-Q & Azusa).
This has to be compared with the loop length of 16 when doing the global SMP rebalance. The additional work done for averaging is minimal. The more nodes, the cheaper the NUMA cross-node balancing compared to the global SMP balancing.

Besides: the CPU is idle anyway! So who cares whether it just unsuccessfully scans its own empty node or looks at the other nodes from time to time? It does this lockless and doesn't modify any variables in other runqueues, so doesn't create cache misses for other CPUs.

Quoted 4 lines

[whether it's high
frequency or not depends on the actual workload, but it can be potentially _very_ high frequency, easily on the order of 1 million times a second - then you'll call the inter-node balancer 100K times a second.]

You mean because cpu_idle() loops over schedule()? The code is:

        while (1) {
                void (*idle)(void) = pm_idle;
                if (!idle)
                        idle = default_idle;
                irq_stat[smp_processor_id()].idle_timestamp = jiffies;
                while (!need_resched())
                        idle();
                schedule();
        }

So if the CPU is idle, it won't go through schedule(), except we get an interrupt from time to time... And then, it doesn't really matter. Or do you want to keep idle CPUs free for serving interrupts? That could be legitimate, but is not the typical load I had in mind and is an issue not related to the NUMA scheduler. But maybe you have something else in mind, that I didn't consider, yet.

Under normal conditions the rebalancing I though about would work the following way:

Busy CPU:
- intra-node rebalance every 200ms (interval timer controlled)
- cross-node rebalance every NODE_BALANCE_RATE*200ms (2s)
- when about to go idle, rebalance internally or across nodes, 10 times more often within the node

Idle CPU:
- intra-node rebalance every 1ms
- cross-node rebalance every NODE_REBALANCE_RATE * 1ms (10ms) This doesn't appear to be too frequent for me... after all the cpu is idle and couldn't steal anything from it's own node.

I don't insist too much on this design, but I can't see any serious reasons against it. Of course, the performance should decide.

I'm about to test the two versions in discussion on an NEC Asama (small configuration with 4 nodes, good memory latency ratio between nodes (1.6), no node-level cache).

Best regards,
Erich

Quoted 39 lines · Ingo Molnar
Quoted 10 lines · Martin J. Bligh
Quoted 5 lines

complex. It's the one that is aware of the global scheduling picture. For NUMA i'd suggest two asynchronous frequencies: one intra-node frequency, and an inter-node frequency - configured by the architecture and roughly in the same proportion to each other as cachemiss latencies.

That's exactly what's in the latest set of patches - admittedly it's a multiplier of when we run load_balance, not the tick multiplier, but that's very easy to fix. Can you check out the stuff I posted last night? I think it's somewhat cleaner ...

yes, i saw it, it has the same tying between idle-CPU-rebalance and inter-node rebalance, as Erich's patch. You've put it into cpus_to_balance(), but that still makes rq->nr_balanced a 'synchronously' coupled balancing act. There are two synchronous balancing acts currently:
the 'CPU just got idle' event, and the exec()-balancing (*) event. Neither must involve any 'heavy' balancing, only local balancing. The inter-node balancing (which is heavier than even the global SMP balancer), should never be triggered from the high-frequency path. [whether it's high frequency or not depends on the actual workload, but it can be potentially _very_ high frequency, easily on the order of 1 million times a second - then you'll call the inter-node balancer 100K times a second.]

I'd strongly suggest to decouple the heavy NUMA load-balancing code from the fastpath and re-check the benchmark numbers.

Ingo

(*) whether sched_balance_exec() is a high-frequency path or not is up to debate. Right now it's not possible to get much more than a couple of thousand exec()'s per second on fast CPUs. Hopefully that will change in the future though, so exec() events could become really fast. So i'd suggest to only do local (ie. SMP-alike) balancing in the exec() path, and only do NUMA cross-node balancing with a fixed frequency, from the timer tick. But exec()-time is really special, since the user task usually has zero cached state at this point, so we _can_ do cheap cross-node balancing as well. So it's a boundary thing - probably doing the full-blown balancing is the right thing.

#86 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

Quoted 2 lines · Erich Focht

I prefer a single point of entry called load_balance() to multiple functionally different balancers. [...]

agreed - my cleanup patch keeps that property.

Quoted 3 lines

[...] IIRC, his conclusion for the multi-queue scheduler was that an order of magnitude of 10ms is long enough, below you start feeling the balancing overhead, above you waste useful cycles.

this is one reason why we do the idle rebalancing at 1 msec granularity right now.

Quoted 8 lines

On a NUMA system this is even more important: the longer you leave fresh tasks on an overloaded node, the more probable it is that they allocate their memory there. And then they will run with poor performance on the node which stayed idle for 200-400ms before stealing them. So one wastes 200-400ms on each CPU of the idle node and at the end gets tasks which perform poorly, anyway. If the tasks are "old", at least we didn't waste too much time beeing idle. The long-term target should be that the tasks should remember where their memory is and return to that node.

i'd much rather vote for fork() and exec() time 'pre-balancing' and then making it quite hard to move a task across nodes.

Quoted 4 lines
Quoted 2 lines

The inter-node balancing (which is heavier than even the global SMP balancer), should never be triggered from the high-frequency path.

Hmmm, we made it really slim. [...]

this is a misunderstanding. I'm not worried about the algorithmic overhead _at all_, i'm worried about the effect of too frequent balancing - tasks being moved between runqueues too often. That has shown to be a problem on SMP. The prev_load type of statistic measurement relies on a constant frequency - it can lead to over-balancing if it's called too often.

Quoted 2 lines

So if the CPU is idle, it won't go through schedule(), except we get an interrupt from time to time... [...]

(no, it's even better than that, we never leave the idle loop except when we _know_ that there is scheduling work to be done. Hence the need_resched() test. But i'm not worried about balancing overhead at all.)

Ingo

#87 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

In reply to Erich Focht

+#ifdef CONFIG_NUMA
+extern void sched_balance_exec(void);
+extern void node_nr_running_init(void);
+#else
+#define sched_balance_exec() {}
+#endif

You accidentally (?) removed the stub for node_nr_running_init. Also sched.h used # define inside ifdefs.

+#ifdef CONFIG_NUMA
+ atomic_t * node_ptr;

The name is still a bit non-descriptive and the * placed wrong :) What about atomic_t *nr_running_at_node?

+#if CONFIG_NUMA
+static atomic_t node_nr_running[MAX_NUMNODES] ____cacheline_maxaligned_in_smp =
+ {[0 ...MAX_NUMNODES-1] = ATOMIC_INIT(0)};
+

I think my two comments here were pretty usefull :)

+static inline void nr_running_dec(runqueue_t *rq) +{
+ atomic_dec(rq->node_ptr);
+ rq->nr_running--;
+}
+
+__init void node_nr_running_init(void)
+{
+ int i;
+
+ for (i = 0; i < NR_CPUS; i++)
+ cpu_rq(i)->node_ptr = &node_nr_running[__cpu_to_node(i)];
+}
+#else

+# define nr_running_init(rq)   do { } while (0)
+# define nr_running_inc(rq)    do { (rq)->nr_running++; } while (0)
+# define nr_running_dec(rq)    do { (rq)->nr_running--; } while (0)

+#endif /* CONFIG_NUMA */
+
/*
@@ -689,7 +811,7 @@ static inline runqueue_t *find_busiest_q
busiest = NULL;
max_load = 1;
for (i = 0; i < NR_CPUS; i++) {
- if (!cpu_online(i))
+ if (!cpu_online(i) || !((1UL << i) & cpumask) )

spurious whitespace before the closing brace.

prio_array_t *array;
struct list_head *head, *curr;
task_t *tmp;
+ int this_node = __cpu_to_node(this_cpu);
+ unsigned long cpumask = __node_to_cpu_mask(this_node);

If that's not to much style nitpicking: put this_node on one line with all the other local ints and initialize all three vars after the declarations (like in my patch *duck*)

+#if CONFIG_NUMA
+ rq->node_ptr = &node_nr_running[0];
+#endif /* CONFIG_NUMA */

I had a nr_running_init() abstraction for this, but you only took it partially. It would be nice to merge the last bit to get rid of this ifdef.

Else the patch looks really, really good and I'm looking forward to see it in mainline real soon!

#88 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

In reply to Erich Focht
Quoted 6 lines · Erich Focht

Here's the new version of the NUMA scheduler built on top of the miniature scheduler of Martin. I incorporated Michael's ideas and Christoph's suggestions and rediffed for 2.5.58.

The whole patch is really tiny: 9.5k. This time I attached the numa scheduler in form of two patches:

Ran tests on three different kernels:

stock58 - linux 2.5.58 with the cputime_stats patch sched1-4-58 - stock58 with the first 4 NUMA scheduler patches sched1-5-58 - stock58 with all 5 NUMA scheduler patches

Kernbench:

                        Elapsed       User     System        CPU
             stock58    31.656s    305.85s    89.232s    1248.2%
         sched1-4-58    29.886s   287.506s     82.94s      1239%
         sched1-5-58    29.994s   288.796s    84.706s      1245%

Schedbench 4:

                        AvgUser    Elapsed  TotalUser   TotalSys
             stock58      27.73      42.80     110.96       0.85
         sched1-4-58      32.86      46.41     131.47       0.85
         sched1-5-58      32.37      45.34     129.52       0.89

Schedbench 8:

                        AvgUser    Elapsed  TotalUser   TotalSys
             stock58      45.97      61.87     367.81       2.11
         sched1-4-58      31.39      49.18     251.22       2.15
         sched1-5-58      37.52      61.32     300.22       2.06

Schedbench 16:

                        AvgUser    Elapsed  TotalUser   TotalSys
             stock58      60.91      83.63     974.71       6.18
         sched1-4-58      54.31      62.11     869.11       3.84
         sched1-5-58      51.60      59.05     825.72       4.74

Schedbench 32:

                        AvgUser    Elapsed  TotalUser   TotalSys
             stock58      84.26     195.16    2696.65      16.53
         sched1-4-58      61.49     140.51    1968.06       9.57
         sched1-5-58      55.23     117.32    1767.71       7.78

Schedbench 64:

                        AvgUser    Elapsed  TotalUser   TotalSys
             stock58     123.27     511.77    7889.77      27.78
         sched1-4-58      63.39     266.40    4057.92      20.55
         sched1-5-58      59.57     250.25    3813.39      17.05

One anomaly noted was that the kernbench system time went up about 5% with the 2.5.58 kernel from what it was on the last version I tested with (2.5.55). This increase is in both stock and with the NUMA scheduler, so is not caused by the NUMA scheduler.

Now that I've got baselines for these, I plan to next look at tweaking various parameters within the scheduler and see how what happens. Also, I owe Erich numbers running hackbench. Overall, I am pleased with these results.

And just for grins, here are the detailed results for running numa_test 32

sched1-4-58:

Executing 32 times: ./randupdt 1000000 Running 'hackbench 20' in the background: Time: 9.044

Job  node00 node01 node02 node03 | iSched MSched | UserTime(s)
  1     0.0  100.0    0.0    0.0 |    1     1    |  55.04
  2     0.0    0.0    4.8   95.2 |    2     3   *|  70.38
  3     0.0    0.0    3.2   96.8 |    2     3   *|  72.72
  4     0.0   26.4    2.8   70.7 |    2     3   *|  72.99
  5   100.0    0.0    0.0    0.0 |    0     0    |  57.03
  6   100.0    0.0    0.0    0.0 |    0     0    |  55.06
  7   100.0    0.0    0.0    0.0 |    0     0    |  57.18
  8     0.0  100.0    0.0    0.0 |    1     1    |  55.38
  9   100.0    0.0    0.0    0.0 |    0     0    |  54.37
 10     0.0  100.0    0.0    0.0 |    1     1    |  56.06
 11     0.0   13.2    0.0   86.8 |    3     3    |  64.33
 12     0.0    0.0    0.0  100.0 |    3     3    |  62.35
 13     1.7    0.0   98.3    0.0 |    2     2    |  67.47
 14   100.0    0.0    0.0    0.0 |    0     0    |  55.94
 15     0.0   29.4   61.9    8.6 |    3     2   *|  78.76
 16     0.0  100.0    0.0    0.0 |    1     1    |  56.42
 17    18.9    0.0   74.9    6.2 |    3     2   *|  70.57
 18     0.0    0.0  100.0    0.0 |    2     2    |  63.01
 19     0.0  100.0    0.0    0.0 |    1     1    |  55.97
 20     0.0    0.0   92.7    7.3 |    3     2   *|  65.62
 21     0.0    0.0  100.0    0.0 |    2     2    |  62.70
 22     0.0  100.0    0.0    0.0 |    1     1    |  55.53
 23     0.0    1.5    0.0   98.5 |    3     3    |  56.95
 24     0.0  100.0    0.0    0.0 |    1     1    |  55.75
 25     0.0   30.0    2.3   67.7 |    2     3   *|  77.78
 26     0.0    0.0    0.0  100.0 |    3     3    |  57.71
 27    13.6    0.0   86.4    0.0 |    0     2   *|  66.55
 28   100.0    0.0    0.0    0.0 |    0     0    |  55.43
 29     0.0  100.0    0.0    0.0 |    1     1    |  56.12
 30    19.8    0.0   62.5   17.6 |    3     2   *|  66.92
 31   100.0    0.0    0.0    0.0 |    0     0    |  54.90
 32   100.0    0.0    0.0    0.0 |    0     0    |  54.70
AverageUserTime 61.49 seconds
ElapsedTime     140.51
TotalUserTime   1968.06
TotalSysTime    9.57

sched1-5-58:

Executing 32 times: ./randupdt 1000000 Running 'hackbench 20' in the background: Time: 9.145

Job  node00 node01 node02 node03 | iSched MSched | UserTime(s)
  1   100.0    0.0    0.0    0.0 |    0     0    |  54.88
  2     0.0  100.0    0.0    0.0 |    1     1    |  54.08
  3     0.0    0.0    0.0  100.0 |    3     3    |  55.48
  4     0.0    0.0    0.0  100.0 |    3     3    |  55.47
  5   100.0    0.0    0.0    0.0 |    0     0    |  53.84
  6   100.0    0.0    0.0    0.0 |    0     0    |  53.37
  7     0.0    0.0    0.0  100.0 |    3     3    |  55.41
  8    90.9    9.1    0.0    0.0 |    1     0   *|  55.58
  9     0.0  100.0    0.0    0.0 |    1     1    |  55.61
 10     0.0  100.0    0.0    0.0 |    1     1    |  54.56
 11     0.0    0.0   98.1    1.9 |    2     2    |  56.25
 12     0.0    0.0    0.0  100.0 |    3     3    |  55.07
 13     0.0    0.0    0.0  100.0 |    3     3    |  54.92
 14     0.0  100.0    0.0    0.0 |    1     1    |  54.59
 15   100.0    0.0    0.0    0.0 |    0     0    |  55.10
 16     5.0    0.0   95.0    0.0 |    2     2    |  56.97
 17     0.0    0.0  100.0    0.0 |    2     2    |  55.51
 18   100.0    0.0    0.0    0.0 |    0     0    |  53.97
 19     0.0    4.7   95.3    0.0 |    2     2    |  57.21
 20     0.0    0.0  100.0    0.0 |    2     2    |  55.53
 21     0.0    0.0  100.0    0.0 |    2     2    |  56.46
 22     0.0    0.0  100.0    0.0 |    2     2    |  55.48
 23     0.0    0.0    0.0  100.0 |    3     3    |  55.99
 24     0.0  100.0    0.0    0.0 |    1     1    |  55.32
 25     0.0    6.2   93.8    0.0 |    2     2    |  57.66
 26     0.0    0.0    0.0  100.0 |    3     3    |  55.60
 27     0.0  100.0    0.0    0.0 |    1     1    |  54.65
 28     0.0    0.0    0.0  100.0 |    3     3    |  56.39
 29     0.0  100.0    0.0    0.0 |    1     1    |  54.91
 30   100.0    0.0    0.0    0.0 |    0     0    |  53.58
 31   100.0    0.0    0.0    0.0 |    0     0    |  53.53
 32    31.5   68.4    0.0    0.0 |    0     1   *|  54.41
AverageUserTime 55.23 seconds
ElapsedTime     117.32
TotalUserTime   1767.71
TotalSysTime    7.78
Signature · 2 lines
Michael Hohnbaum                      503-578-5486
[email protected]                   T/L 775-5486
#89 lore raw

Re: [PATCH 2.5.58] new NUMA scheduler: fix

In reply to Erich Focht

OK, ran some tests on incremental version of the stack. newsched3 = patches 1+2+3 ... etc.
oldsched = Erich's old code + Michael's ilb. newsched4-tune = patches 1,2,3,4 + tuning patch below:

Tuning seems to help quite a bit ... need to stick this into arch topo code. Sleep time now ;-)

Kernbench:

                                   Elapsed        User      System         CPU
                   2.5.58-mjb1     19.522s    186.566s     41.516s     1167.8%
          2.5.58-mjb1-oldsched     19.488s     186.73s     42.382s     1175.6%
         2.5.58-mjb1-newsched2     19.286s    186.418s     40.998s     1178.8%
         2.5.58-mjb1-newsched3      19.58s    187.658s     43.694s     1181.2%
         2.5.58-mjb1-newsched4     19.266s    187.772s     42.984s     1197.4%
    2.5.58-mjb1-newsched4-tune     19.424s    186.664s     41.422s     1173.6%
         2.5.58-mjb1-newsched5     19.462s    187.692s      43.02s       1185%

NUMA schedbench 4:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                   2.5.58-mjb1                                                
          2.5.58-mjb1-oldsched        0.00       35.16       88.55        0.68
         2.5.58-mjb1-newsched2        0.00       19.12       63.71        0.48
         2.5.58-mjb1-newsched3        0.00       35.73       88.26        0.58
         2.5.58-mjb1-newsched4        0.00       35.64       88.46        0.60
    2.5.58-mjb1-newsched4-tune        0.00       37.10       91.99        0.58
         2.5.58-mjb1-newsched5        0.00       35.34       88.60        0.64

NUMA schedbench 8:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                   2.5.58-mjb1        0.00       35.34       88.60        0.64
          2.5.58-mjb1-oldsched        0.00       64.01      338.77        1.50
         2.5.58-mjb1-newsched2        0.00       31.56      227.72        1.03
         2.5.58-mjb1-newsched3        0.00       35.44      220.63        1.36
         2.5.58-mjb1-newsched4        0.00       35.47      223.86        1.33
    2.5.58-mjb1-newsched4-tune        0.00       37.04      232.92        1.14
         2.5.58-mjb1-newsched5        0.00       36.11      223.14        1.39

NUMA schedbench 16:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                   2.5.58-mjb1        0.00       36.11      223.14        1.39
          2.5.58-mjb1-oldsched        0.00       62.60      834.67        4.85
         2.5.58-mjb1-newsched2        0.00       57.24      850.12        2.64
         2.5.58-mjb1-newsched3        0.00       64.15      870.25        3.18
         2.5.58-mjb1-newsched4        0.00       64.01      875.17        3.10
    2.5.58-mjb1-newsched4-tune        0.00       57.84      841.48        2.96
         2.5.58-mjb1-newsched5        0.00       61.87      828.37        3.47

NUMA schedbench 32:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                   2.5.58-mjb1        0.00       61.87      828.37        3.47
          2.5.58-mjb1-oldsched        0.00      154.30     2031.93        9.35
         2.5.58-mjb1-newsched2        0.00      117.75     1798.53        5.52
         2.5.58-mjb1-newsched3        0.00      122.87     1771.71        8.33
         2.5.58-mjb1-newsched4        0.00      134.86     1863.51        8.27
    2.5.58-mjb1-newsched4-tune        0.00      118.18     1809.38        6.58
         2.5.58-mjb1-newsched5        0.00      134.36     1853.94        8.33

NUMA schedbench 64:

                                   AvgUser     Elapsed   TotalUser    TotalSys
                   2.5.58-mjb1        0.00      134.36     1853.94        8.33
          2.5.58-mjb1-oldsched        0.00      318.68     4852.81       21.47
         2.5.58-mjb1-newsched2        0.00      241.11     3603.29       12.70
         2.5.58-mjb1-newsched3        0.00      258.72     3977.50       16.88
         2.5.58-mjb1-newsched4        0.00      252.87     3850.55       18.51
    2.5.58-mjb1-newsched4-tune        0.00      235.43     3627.28       15.90
         2.5.58-mjb1-newsched5        0.00      265.09     3967.70       18.81
sched.c 2003-01-14 22:20:19.000000000 -0800 renamed from sched.c.premjb4 2003-01-14 22:12:36.000000000 -0800 +3 -2
@@ -85,7 +85,7 @@
 #define NODE_THRESHOLD          125
 #define MAX_INTERNODE_LB 40
 #define MIN_INTERNODE_LB 4
-#define NODE_BALANCE_RATIO 10
+#define NODE_BALANCE_RATIO 250
 
 /*
  * If a task is 'interactive' then we reinsert it in the active
@@ -763,7 +763,8 @@
                        + atomic_read(&node_nr_running[i]);
                this_rq()->prev_node_load[i] = load;
                if (load > maxload &&
-                   (100*load > ((NODE_THRESHOLD*100*this_load)/100))) {
+                   (100*load > (NODE_THRESHOLD*this_load))
+                   && load > this_load + 4) {
                        maxload = load;
                        node = i;
                }
#90 lore raw

Re: [Lse-tech] Re: NUMA scheduler 2nd approach

In reply to Andrew Theurer
Quoted 34 lines · Andrew Theurer
Quoted 12 lines

Erich,

I played with this today on my 4 node (16 CPU) NUMAQ. Spent most of the time working with the first three patches. What I found was that rebalancing was happening too much between nodes. I tried a few things to change this, but have not yet settled on the best approach. A key item to work with is the check in find_busiest_node to determine if the found node is busier enough to warrant stealing from it. Currently the check is that the node has 125% of the load of the current node. I think that, for my system at least, we need to add in a constant to this equation. I tried using 4 and that helped a little.

Michael,

in:

kernel/sched.c +16 -0
+static int find_busiest_node(int this_node)
+{
+ int i, node = this_node, load, this_load, maxload;
+ 
+ this_load = maxload = atomic_read(&node_nr_running[this_node]);
+ for (i = 0; i < numnodes; i++) {
+  if (i == this_node)
+   continue;
+  load = atomic_read(&node_nr_running[i]);
+  if (load > maxload && (4*load > ((5*4*this_load)/4))) {
+   maxload = load;
+   node = i;
+  }
+ }
+ return node;
+}
Quoted 4 lines

You changed ((5*4*this_load)/4) to:
(5*4*(this_load+4)/4)
or
(4+(5*4*(this_load)/4)) ?

I suppose I should not have been so dang lazy and cut-n-pasted the line I changed. The change was (((5*4*this_load)/4) + 4) which should be the same as your second choice.

Quoted 2 lines

We def need some constant to avoid low load ping pong, right?

Yep. Without the constant, one could have 6 processes on node A and 4 on node B, and node B would end up stealing. While making a perfect balance, the expense of the off-node traffic does not justify it. At least on the NUMAQ box. It might be justified for a different NUMA architecture, which is why I propose putting this check in a macro that can be defined in topology.h for each architecture.

Quoted 5 lines

Finally I added in the 04 patch, and that helped

Quoted 1 line

a lot. Still, there is too much process movement between nodes.

perhaps increase INTERNODE_LB?

That is on the list to try. Martin was mumbling something about use the system wide load average to help make the inter-node balance decision. I'd like to give that a try before tweaking ITERNODE_LB.

Quoted 3 lines

-Andrew Theurer

Michael Hohnbaum
[email protected]

#91 lore raw

Re: [Lse-tech] Re: NUMA scheduler 2nd approach

Quoted 6 lines

I suppose I should not have been so dang lazy and cut-n-pasted the line I changed. The change was (((5*4*this_load)/4) + 4) which should be the same as your second choice.

Quoted 2 lines

We def need some constant to avoid low load ping pong, right?

Quoted 7 lines

Yep. Without the constant, one could have 6 processes on node A and 4 on node B, and node B would end up stealing. While making a perfect balance, the expense of the off-node traffic does not justify it. At least on the NUMAQ box. It might be justified for a different NUMA architecture, which is why I propose putting this check in a macro that can be defined in topology.h for each architecture.

Yes, I was also concerned about one task in one node and none in the others. Without some sort of constant we will ping pong the task on every node endlessly, since there is no % threshold that could make any difference when the original load value is 0.. Your +4 gets rid of the 1 task case.

-Andrew

#92 lore raw

Re: [Lse-tech] Re: NUMA scheduler 2nd approach

Quoted 14 lines · Andrew Theurer
Quoted 6 lines

I suppose I should not have been so dang lazy and cut-n-pasted the line I changed. The change was (((5*4*this_load)/4) + 4) which should be the same as your second choice.

Quoted 1 line

We def need some constant to avoid low load ping pong, right?

Quoted 7 lines

Yep. Without the constant, one could have 6 processes on node A and 4 on node B, and node B would end up stealing. While making a perfect balance, the expense of the off-node traffic does not justify it. At least on the NUMAQ box. It might be justified for a different NUMA architecture, which is why I propose putting this check in a macro that can be defined in topology.h for each architecture.

Quoted 5 lines

Yes, I was also concerned about one task in one node and none in the others. Without some sort of constant we will ping pong the task on every node endlessly, since there is no % threshold that could make any difference when the original load value is 0.. Your +4 gets rid of the 1 task case.

That won't happen because:
- find_busiest_queue() won't detect a sufficient imbalance (imbalance == 0),
- load_balance() won't be able to steal the task, as it will be running (the rq->curr task)

So the worst thing that happens is that load_balance() finds out that it cannot steal the only task running on the runqueue and returns. But we won't get there because find_busiest_queue() returns NULL. It happens even in the bad case:
node#0 : 0 tasks
node#1 : 4 tasks (each on its own CPU)
where we would desire to distribute the tasks equally among the nodes. At least on our IA64 platform...

Regards,
Erich

#93 lore raw

Re: NUMA scheduler 2nd approach

In reply to Michael Hohnbaum

Hi Michael,

thanks for the many experiments, they help giving some more insight. It's quite clear that we'll have to tune the knobs a bit to make this fit well.

At first a comment on the "target" of the tuning:

Quoted 12 lines
 26     0.0    0.0  100.0    0.0 |    2     2    |  56.28
 27    15.3    0.0    0.0   84.7 |    3     3    |  57.12
 28   100.0    0.0    0.0    0.0 |    0     0    |  53.85
 29    32.7   67.2    0.0    0.0 |    0     1   *|  62.66
 30   100.0    0.0    0.0    0.0 |    0     0    |  53.86
 31   100.0    0.0    0.0    0.0 |    0     0    |  53.94
 32   100.0    0.0    0.0    0.0 |    0     0    |  55.36
AverageUserTime 56.38 seconds
ElapsedTime     124.09
TotalUserTime   1804.67
TotalSysTime    7.71
Quoted 3 lines

Ideally, there would be nothing but 100.0 in all non-zero entries. I'll try adding in the 05 patch, and if that does not help, will try a few other adjustments.

The numa_test is written such that you MUST get numbers below 100% with this kind of scheduler! There is a "disturbing" process started 3 seconds after the parallel tasks are up and running which has the aim to "shake" the system a bit and the scheduler ends up with some of the parallel tasks moved away from their homenode. This is a reallistic situation for long running parallel background jobs. In the min-sched case this cannot happen, therefore you see the 100% all over!

Increasing more and more the barrier for moving a task apart from it's node won't necessarilly help the scheduler as we end up with the min-sched limitations. The aim will be to introduce node affinity for processes such that they can return to their homenode when the exceptional load situation is gone. We should not try to reach the min-sched numbers without having node-affine tasks.

Quoted 3 lines

* Make the check in find_busiest_node into a macro that is defined in the arch specific topology header file. Then different NUMA architectures can tune this appropriately.

I still think that the load balancing condition should be clear and the same for every architecture. But tunable. I understand that the constant added helps but I don't have a clear motivation for it. We could keep the imbalance ratio as a condition for searching the maximum:

Quoted 1 line

+ if (load > maxload && (4*load > ((5*4*this_load)/4))) {

(with tunable barrier height: say replace 5/4 by 11/8 or similar, i.e.
(8*load > ((11*8*this_load)/8))
)
and rule out any special unwanted cases after the loop. These would be cases where it is obvious that we don't have to steal anything, like:
load of remote node is <= number of cpus in remote node.

For making this tunable I suggest something like:
#define CROSS_NODE_BAL 125
(100*load > ((CROSS_NODE_BAL*100*this_load)/100))
and let platforms define their own value. Using 100 makes it easy to understand.

Quoted 9 lines

* In find_busiest_queue change:

	cpumask |= __node_to_cpu_mask(node);
  to:
	cpumask = __node_to_cpu_mask(node) | (1UL << (this_cpu));

There is no reason to iterate over the runqueues on the current node, which is what the code currently does.

Here I thought I'd give the load balancer the chance to balance internally just in case the own node's load jumped up in the mean time. But this should ideally be caught by find_busiest_node(), therefore I agree with your change.

Quoted 9 lines

Some numbers for anyone interested:Kernbench:

All numbers are based on a 2.5.55 kernel with the cputime stats patch:
* stock55 = no additional patches
* mini+rebal-44 = patches 01, 02, and 03
* rebal+4+fix = patches 01, 02, 03, and the cpumask change described above, and a +4 constant added to the check in find_busiest_node
* rebal+4+fix+04 = above with the 04 patch added

Quoted 5 lines

Elapsed User System CPU

   rebal+4+fix+04-55    29.302s   285.136s    82.106s      1253%
      rebal+4+fix-55    30.498s   286.586s    88.176s    1228.6%
       mini+rebal-55    30.756s   287.646s    85.512s    1212.8%
             stock55    31.018s   303.084s    86.626s    1256.2%

The first line is VERY good!

The results below (for Schedbench) are not really meaningful without statistics... But the combination rebal+4+fix+04-55 is the clear winner for me. Still, I'd be curious to know the rebal+fix+04-55 numbers ;-)

Quoted 78 lines

Schedbench 4:
AvgUser Elapsed TotalUser TotalSys

   rebal+4+fix+04-55      27.34      40.49     109.39       0.88
      rebal+4+fix-55      24.73      38.50      98.94       0.84
       mini+rebal-55      25.18      43.23     100.76       0.68
             stock55      31.38      41.55     125.54       1.24

Schedbench 8:
AvgUser Elapsed TotalUser TotalSys

   rebal+4+fix+04-55      30.05      44.15     240.48       2.50
      rebal+4+fix-55      34.33      46.40     274.73       2.31
       mini+rebal-55      32.99      52.42     264.00       2.08
             stock55      44.63      61.28     357.11       2.22

Schedbench 16:
AvgUser Elapsed TotalUser TotalSys

   rebal+4+fix+04-55      52.13      57.68     834.23       3.55
      rebal+4+fix-55      52.72      65.16     843.70       4.55
       mini+rebal-55      57.29      71.51     916.84       5.10
             stock55      66.91      85.08    1070.72       6.05

Schedbench 32:
AvgUser Elapsed TotalUser TotalSys

   rebal+4+fix+04-55      56.38     124.09    1804.67       7.71
      rebal+4+fix-55      55.13     115.18    1764.46       8.86
       mini+rebal-55      57.83     125.80    1850.84      10.19
             stock55      80.38     181.80    2572.70      13.22

Schedbench 64:
AvgUser Elapsed TotalUser TotalSys

   rebal+4+fix+04-55      57.42     238.32    3675.77      17.68
      rebal+4+fix-55      60.06     252.96    3844.62      18.88
       mini+rebal-55      58.15     245.30    3722.38      19.64
             stock55     123.96     513.66    7934.07      26.39

And here is the results from running numa_test 32 on rebal+4+fix+04:

Executing 32 times: ./randupdt 1000000 Running 'hackbench 20' in the background: Time: 8.383

Job  node00 node01 node02 node03 | iSched MSched | UserTime(s)
  1   100.0    0.0    0.0    0.0 |    0     0    |  56.19
  2   100.0    0.0    0.0    0.0 |    0     0    |  53.80
  3     0.0    0.0  100.0    0.0 |    2     2    |  55.61
  4   100.0    0.0    0.0    0.0 |    0     0    |  54.13
  5     3.7    0.0    0.0   96.3 |    3     3    |  56.48
  6     0.0    0.0  100.0    0.0 |    2     2    |  55.11
  7     0.0    0.0  100.0    0.0 |    2     2    |  55.94
  8     0.0    0.0  100.0    0.0 |    2     2    |  55.69
  9    80.6   19.4    0.0    0.0 |    1     0   *|  56.53
 10     0.0    0.0    0.0  100.0 |    3     3    |  53.00
 11     0.0   99.2    0.0    0.8 |    1     1    |  56.72
 12     0.0    0.0    0.0  100.0 |    3     3    |  54.58
 13     0.0  100.0    0.0    0.0 |    1     1    |  59.38
 14     0.0   55.6    0.0   44.4 |    3     1   *|  63.06
 15     0.0  100.0    0.0    0.0 |    1     1    |  56.02
 16     0.0   19.2    0.0   80.8 |    1     3   *|  58.07
 17     0.0  100.0    0.0    0.0 |    1     1    |  53.78
 18     0.0    0.0  100.0    0.0 |    2     2    |  55.28
 19     0.0   78.6    0.0   21.4 |    3     1   *|  63.20
 20     0.0  100.0    0.0    0.0 |    1     1    |  53.27
 21     0.0    0.0  100.0    0.0 |    2     2    |  55.79
 22     0.0    0.0    0.0  100.0 |    3     3    |  57.23
 23    12.4   19.1    0.0   68.5 |    1     3   *|  61.05
 24     0.0    0.0  100.0    0.0 |    2     2    |  54.50
 25     0.0    0.0    0.0  100.0 |    3     3    |  56.82
 26     0.0    0.0  100.0    0.0 |    2     2    |  56.28
 27    15.3    0.0    0.0   84.7 |    3     3    |  57.12
 28   100.0    0.0    0.0    0.0 |    0     0    |  53.85
 29    32.7   67.2    0.0    0.0 |    0     1   *|  62.66
 30   100.0    0.0    0.0    0.0 |    0     0    |  53.86
 31   100.0    0.0    0.0    0.0 |    0     0    |  53.94
 32   100.0    0.0    0.0    0.0 |    0     0    |  55.36
AverageUserTime 56.38 seconds
ElapsedTime     124.09
TotalUserTime   1804.67
TotalSysTime    7.71
Quoted 6 lines

Ideally, there would be nothing but 100.0 in all non-zero entries. I'll try adding in the 05 patch, and if that does not help, will try a few other adjustments.

Thanks for the quick effort on putting together the node rebalance code. I'll also get some hackbench numbers soon.

Best regards,

Erich

#94 lore raw
In reply to Erich Focht
Quoted 10 lines · Erich Focht

Having some sort of automatic node affinity of processes and equal node loads in mind (as design targets), we could:
- take the minimal NUMA scheduler
- if the normal (node-restricted) find_busiest_queue() fails and certain conditions are fulfilled (tried to balance inside own node for a while and didn't succeed, own CPU idle, etc... ???) rebalance over node boundaries (eg. using my load balancer)
This actually resembles the original design of the node affine scheduler, having the cross-node balancing separate is ok and might make the ideas clearer.

Agreed, but honestly just this explanation would make it easier to understand! I'm not sure you have the "balance of nodes" trigger defined quite right, but I'm assuming if this gets implemented as described that some long term umbalance detector mechanism will be run occasionally.

Signature · 3 lines
bill davidsen <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.
#95 lore raw
Quoted 4 lines · Bill Davidsen

Agreed, but honestly just this explanation would make it easier to understand! I'm not sure you have the "balance of nodes" trigger defined quite right, but I'm assuming if this gets implemented as described that some long term umbalance detector mechanism will be run occasionally.

Yes, the current plan is to extend the miniature NUMA scheduler by a inter-node balancer which is called less frequently.

Regards,
Erich