rcutorture: Do better bin packing
authorPaul E. McKenney <paulmck@linux.vnet.ibm.com>
Fri, 17 Jan 2014 22:18:05 +0000 (14:18 -0800)
committerPaul E. McKenney <paulmck@linux.vnet.ibm.com>
Tue, 18 Feb 2014 20:26:52 +0000 (12:26 -0800)
commit53954671033dc878acbeef1ecf9ac653c7b1a58f
treecf1605094cd114483887cac885d0188fdd72f6f8
parent0ae3f73af5ba8025abcb328913643b291698af35
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>
tools/testing/selftests/rcutorture/bin/kvm.sh