rcutorture: Do better bin packing

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 <paulmck@linux.vnet.ibm.com>
Reviewed-by: Josh Triplett <josh@joshtriplett.org>

1 files changed, 36 insertions, 1 deletions

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 \