[PATCH tip/core/rcu 11/55] rcutorture: Do better bin packing

[Paul E. McKenney]

From: "Paul E. McKenney" <paul...@linux.vnet.ibm.com>

Running the standard set of rcutorture tests on 24 CPUs results in
the following sub-optimal schedule:

        ----start batch----
         TREE07 16
        ----start batch----
         TREE08 16
         SRCU-P 8
        ----start batch----
         TREE01 8
         TREE02 8
         TREE03 8
        ----start batch----
         TREE04 8
         TREE05 8
         TREE06 8
        ----start batch----
         SRCU-N 4
         TINY01 1
         TINY02 1
         TREE09 1

If one of the eight-CPU runs were to be moved into the first batch,
the test suite would complete in four batches rather than five.

This commit therefore uses a greedy algorithm to re-order the test
entries so that the sequential batching will produce an optimal schedule
in this case:

        ----start batch----
         TREE07 16
         SRCU-P 8
        ----start batch----
         TREE08 16
         TREE01 8
        ----start batch----
         TREE02 8
         TREE03 8
         TREE04 8
        ----start batch----
         TREE05 8
         TREE06 8
         SRCU-N 4
         TINY01 1
         TINY02 1
         TREE09 1

Please note that this is still not an optimal bin-packing algorithm,
however, it does produce optimal solutions for most common scenarios.

Signed-off-by: Paul E. McKenney <paul...@linux.vnet.ibm.com>
---
 tools/testing/selftests/rcutorture/bin/kvm.sh | 37 ++++++++++++++++++++++++++-
 1 file changed, 36 insertions(+), 1 deletion(-)

diff --git a/tools/testing/selftests/rcutorture/bin/kvm.sh 
b/tools/testing/selftests/rcutorture/bin/kvm.sh
index ad3779cefdb8..18649b87ea6c 100644
--- a/tools/testing/selftests/rcutorture/bin/kvm.sh
+++ b/tools/testing/selftests/rcutorture/bin/kvm.sh
@@ -214,7 +214,42 @@ do
 done
 sort -k2nr $T/cfgcpu > $T/cfgcpu.sort
 
-awk < $T/cfgcpu.sort \
+awk < $T/cfgcpu.sort > $T/cfgcpu.pack -v ncpus=$cpus '
+BEGIN {
+       njobs = 0;
+}
+
+{
+       cf[njobs] = $1;
+       cpus[njobs] = $2;
+       njobs++;
+}
+
+END {
+       alldone = 0;
+       batch = 0;
+       nc = -1;
+       while (nc != ncpus) {
+               batch++;
+               nc = ncpus;
+               for (i = 0; i < njobs; i++) {
+                       if (done[i])
+                               continue;
+                       if (nc >= cpus[i] || nc == ncpus) {
+                               done[i] = batch;
+                               nc -= cpus[i];
+                               if (nc <= 0)
+                                       break;
+                       }
+               }
+       }
+       for (b = 1; b <= batch; b++)
+               for (i = 0; i < njobs; i++)
+                       if (done[i] == b)
+                               print cf[i], cpus[i];
+}'
+
+awk < $T/cfgcpu.pack \
        -v CONFIGDIR="$CONFIGFRAG/$kversion/" \
        -v KVM="$KVM" \
        -v ncpus=$cpus \
-- 
1.8.1.5

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/