Date:	Fri, 06 Nov 2015 15:02:34 +0300
From:	Arseniy Krasnov <a.krasnov@...sung.com>
To:	linux@....linux.org.uk, mingo@...hat.com, peterz@...radead.org
Cc:	a.krasnov@...sung.com, v.tyrtov@...sung.com,
	s.rogachev@...sung.com, linux-kernel@...r.kernel.org
Subject: [PATCH 00/13] High performance balancing logic for big.LITTLE

				Prologue

The patch set introduces an extension to the default Linux CPU scheduler (CFS).
The main purpose of the extension is utilization of a big.LITTLE CPU for maximum
performance. Such solution may be useful for users of OdroidXU-3 board
(supporting 8 cores) who doesn't care about power efficiency.

Maximum utilization was reached using the following policies:

1) A15 cores must be utilized as much as possible e.g. idle A15 cores always
   pull some task from A7 core.

2) After execution of a task on A7 core for some period of time it should be
   swapped with an appropriate task from A15 cluster in order to achieve
   fairness.

3) Load of big and little clusters is balanced according to frequency and
   A15/A7 slowdown coefficient.

			Approach Description

The scheduler creates a hierarchy of two domains: MC and HMP. The MC domain is a
default domain for SCHED_MC config. The HMP domain contains two clusters: A15
and A7 CPUs. Balancing between HMP domains is performed by the new logic, in MC
domains, in turn, balancing is done by the default logic of the 'load_balance()'
function.

To perform balancing between HMP domains, the load of each cluster is calculated
in scheduler's softirq handler. Then, this value is scaled according to each
cluster's frequency and slowdown coefficient which is a ratio of busy-loop
performance on A15 and A7. There are three ways of migration between two
clusters: from A15 cluster to A7 cluster (if load on A15 cluster is too high),
from A7 cluster to A15 cluster (otherwise) and task swapping when load on both
clusters is the same. To migrate some task from one cluster to another firstly
this task should be selected. To find a task suitable for migration the
scheduler uses a special per-task metric called 'druntime'. It is based on CFS's
vruntime metric but its grow direction depends on a core where the task is
executed: for A15 core it grows up, for A7 core, in turn, it goes down. So,
being the druntime value close to zero means that the task is executed on both
clusters for the same amount of time. As a result, to get a task for migration
it scans each runqueue to find a task with highest/lowest druntime depending on
which cluster is scanned; after, when the task is found, it is moved to another
cluster. These balancing steps are performed in each scheduler balancing
operation executed by softirq.

To get maximum performance A15 cores must be fully utilized; this means that
idle A15 cores are always able to pull tasks from A7 cores while A7 cores cannot
do that from A15 cores.

An finally, let's look to fairness - it is provided by swapping of tasks during
every softirq balancing: when balance is broken it tries to repair the balance
moving tasks from one cluster to another, then when the clusters are balanced,
the tasks are swapped during each softirq balancing. In addition to this logic,
'select_task_rq_fair' was modified in order to place woken tasks to least loaded
CPU, because it won't break the balance between A15 and A7 cores.

				Test results

Several test kits were used for performance measurement of the solution.
All comparision is done against the Linaro MP scheduler.

The first test case is a parsec benchmark suite. It contains different types of
tasks like cluster searching or pattern recognition in order to test scheduler
performance. Results of some benchmarks are listed in the text below (in
seconds):

Streamcluster:

Developed by Princeton University and solves the online clustering problem.
Streamcluster was included in the PARSEC benchmark suite because of the
importance of data mining algorithms and the prevalence of problems with
streaming characteristics.

	Threads		HPERF_HMP	Linaro MP
	1		27,333		27,422
	2		14,162		14,197
	3		10,099		10,168
	4		8,227		8,332
	5		10,922		23,349
	6		10,85		22,507
	7		11,39		22,041
	8		12,307		21,181
	9		20,339		22,115
	10		21,33		23,746
	11		23,289		24,831
	12		25,363		26,699
	13		34,091		34,84
	14		34,758		38,661
	15		35,743		38,688
	16		38,1		44,735
	17		41,165		77,098
	18		44,223		102,633
	19		46,177		113,748
	20		48,22		119,146
	21		52,372		135,499
	22		54,319		136,454
	23		56,218		141,924
	24		57,843		145,727
	25		61,759		158,754
	26		63,179		163,915
	27		64,987		167,559
	28		67,329		171,203
	29		70,489		185,171
	30		73,084		189,303
	31		75,264		192,487
	32		77,015		197,27
	avg		40,373		87,543

Bodytrack:

This computer vision application is an Intel RMS workload which tracks a human
body with multiple cameras through an image sequence. This benchmark was
included due to the increasing significance of computer vision algorithms in
areas such as video surveillance, character animation and computer interfaces.

	Threads		HPERF_HMP	Linaro MP
	1		15,884		16,632
	2		8,536		9,42
	3		6,037		7,257
	4		4,84		6,076
	5		8,835		5,739
	6		4,437		5,513
	7		4,119		5,474
	8		3,992		5,115
	9		3,854		5,164
	10		3,92		4,911
	11		3,854		4,932
	12		3,83		4,816
	13		3,839		5,643
	14		3,861		4,816
	15		3,889		4,896
	16		3,845		4,854
	17		3,872		4,837
	18		3,852		4,876
	19		4,304		4,868
	20		3,915		4,928
	21		3,87		4,841
	22		3,858		4,995
	23		3,881		4,97
	24		3,876		4,899
	25		3,854		4,96
	26		3,869		4,902
	27		3,874		4,979
	28		3,88		4,928
	29		3,914		5,008
	30		3,889		5,216
	31		3,898		5,242
	32		3,894		5,199
	avg		4,689		5,653

Blackscholes:

This application is an Intel RMS benchmark. It calculates the prices for a
portfolio of European options analytically with the Black-Scholes partial
differential equation. There is no closed-form expression for the blackscholes
equation and as such it must be computed numerically.

	Threads		HPERF_HMP	Linaro MP
	1		7,293		6,807
	2		3,886		4,044
	3		2,906		2,911
	4		2,429		2,427
	5		2,58		2,985
	6		2,401		2,672
	7		2,205		2,411
	8		2,132		2,293
	9		2,074		2,41
	10		2,067		2,264
	11		2,054		2,205
	12		2,091		2,222
	13		2,042		2,28
	14		2,035		2,222
	15		2,026		2,25
	16		2,024		2,177
	17		2,021		2,173
	18		2,033		2,09
	19		2,03		2,05
	20		2,024		2,158
	21		2,002		2,175
	22		2,026		2,179
	23		2,017		2,134
	24		2,01		2,156
	25		2,009		2,155
	26		2,013		2,179
	27		2,017		2,177
	28		2,019		2,189
	29		2,013		2,158
	30		2,002		2,162
	31		2,016		2,16
	32		2,012		2,159
	avg		2,328		2,469

Also, well known Antutu benchmark was executed on Exynos 5433 board:

					HPERF_HMP	Linaro MP
	Integral benchmark result  	42400		36860 
	Result: hperf_hmp is 15% better.


Arseniy Krasnov (13):
  hperf_hmp: add new config for arm and arm64.
  hperf_hmp: introduce hew domain flag.
  hperf_hmp: add sched domains initialization.
  hperf_hmp: scheduler initialization routines.
  hperf_hmp: introduce druntime metric.
  hperf_hmp: is_hmp_imbalance introduced.
  hperf_hmp: migration auxiliary functions.
  hperf_hmp: swap tasks function.
  hperf_hmp: one way balancing function.
  hperf_hmp: idle pull function.
  hperf_hmp: task CPU selection logic.
  hperf_hmp: rest of logic.
  hperf_hmp: cpufreq routines.

 arch/arm/Kconfig           |   21 +
 arch/arm/kernel/topology.c |    6 +-
 arch/arm64/Kconfig         |   21 +
 include/linux/sched.h      |   17 +
 kernel/sched/core.c        |   65 +-
 kernel/sched/fair.c        | 1553 ++++++++++++++++++++++++++++++++++++++++----
 kernel/sched/sched.h       |   16 +
 7 files changed, 1586 insertions(+), 113 deletions(-)

-- 
1.9.1

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

Powered by blists - more mailing lists