Scalability-Based Manycore Partitioning∗

Hiroshi Sasaki

Teruo Tanimoto

Kyushu University
744 Motooka Nishi-ku
Fukuoka, JapanThe University of Tokyo
7-3-1 Bunkyo-ku, Hongo
Tokyo, Japansasaki@soc.ait.kyushuu.ac.jp
Koji Inouetanimoto@hal.ipc.i.utokyo.ac.jp
Hiroshi Nakamura

Kyushu University
744 Motooka Nishi-ku
Fukuoka, JapanThe University of Tokyo
7-3-1 Bunkyo-ku, Hongo
Tokyo, Japaninoue@ait.kyushu-u.ac.jp

nakamura@hal.ipc.i.utokyo.ac.jp

ABSTRACT

Categories and Subject Descriptors

Multicore processors have been popular for years, and theindustry is gradually shifting towards the era of manycore
processors. Single-thread performance of microprocessors is
not growing at a historical rate, but the existence of a number of active processes in the computer system and the continuing development of multi-threaded applications benefit
from the growing core counts to sustain system throughput.
This trend brings us a situation where a number of parallel applications simultaneously being executed on a single
system. Since multi-threaded applications try to maximize
its throughput by utilizing the whole system, each of themusually create equal or larger number of threads compared
to underlying logical core counts. This introduces muchgreater number of threads to be co-scheduled in the entire
system. However, each program has different characteristics(or scalability) and contends for shared resources, which are
the CPU cores and memory hierarchies, with each other.
Therefore, it is clear that OS thread scheduling will play amajor role in achieving high system performance under suchconditions. We develop a sophisticated scheduler that (1)dynamically predicts the scalability of programs via the useof hardware performance monitoring units, (2) decides the
optimal number of cores to be allocated for each program,and (3) allocates the cores to programs while maximizing
the system utilization to achieve fair and maximum performance. The evaluation results on a 48-core AMD Opteronsystem show improvements over the Linux scheduler for avariety of multiprogramming workloads.

D.4.1 [Operating Systems]: Process Management—scheduling, multiprocessing/multiprogramming/multitasking∗The author is currently with FUJITSU LABORATORIESLTD.

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
PACT’12, September 19–23, 2012, Minneapolis, Minnesota, USA.
Copyright 2012 ACM 978-1-4503-1182-3/12/09 ...$15.00.

General Terms
Experimentation, Measurement, Performance

Keywords
Multicore/manycore processors, process scheduling, multithreaded applications, scalability, performance prediction,
dynamic optimization

1. INTRODUCTION
The end of clock frequency scaling has led the processor
architecture design towards multiple processors on a chip(known as multicore processors or CMPs) which exploits
thread level parallelism to improve performance [14]. The
trend of increasing the core count tends to continue and push
the industry and researchers to face manycore processors in
the near future [24, 27]. The shift from single-core to multicore has broaden the range of applications, and the focusof research has shifted from executing one single-threaded
application on a system to either (1) concurrently executing multiple single-threaded applications or (2) running one
multi-threaded application on a system. However, considering that not all programs can best utilize the potentialof manycore architectures, further shift towards manycore
processors will force us to manage dozens of simultaneously
executed programs which are heavily multi-threaded.
In such a scenario, shared resource contention is one of themost fundamental and important problems which have to besolved. Prior work have showed that contention should be
minimized by (1) isolating (or partitioning) shared resource
accesses as much as possible, and at the same time, (2)allocating appropriate amount of shared resources to eachprogram [23]. For single-threaded multiprogramming workloads, trying to reduce contention at the last level cache (LLC),
memory controller or the prefetcher which lie down in thememory hierarchy is the main objective [2, 5, 6, 12, 15, 19,

30]. However, memory hierarchy is not the only shared resource when scheduling multi-threaded applications. Parallel programs tend to be executed by creating equal or larger
number of threads than the underlying logical core counts
to fully make use of the system. Therefore, the computing resources (i.e., CPU cores) which directly contribute toperformance is the most important shared resource that wehave to carefully allocate to each program in order to achieve
high performance.
Allocation should be done dynamically according to program’s characteristics at the point of creation or terminationof programs, and therefore the runtime layer such as the OS
scheduler or the programming language runtime system [16,21] will play a major role in it. Traditional OS scheduler tries
to assign equal CPU time to each thread to ensure the fairness property. Therefore, we can consider that CPU cores
are evenly shared among each program, controlled by the
OS scheduler. This approach is simple and fair from an OS
point of view, however, there is still room for improvement
and we can still perform better in terms of performance bytaking the scalability of each program into account.
In this paper, we propose a sophisticated OS scheduler
for multi-threaded multiprogramming workloads on manycore processors. The proposed scheduler is able to optimize against various performance metrics which can be determined by either the user or the system software. Several performance metrics are used to evaluate the multiprogramming workloads in the literature: total throughput, weighted speedup [28], harmonic mean of the per program speedup [18], or average normalized turnaround time(i.e., execution time) or ANTT [11]. We insist that the
manycore OS scheduler should be flexible enough to optimize against different needs (or metrics) and the key toachieve this is to take the scalability of each program into
account. The principle behind our technique is that the
speedup obtained from multi-threading on manycore processors heavily depends on several details of the program, andare quite different between them. For example, some program might double its performance by doubling the numberof cores, while other might achieve no performance improvement or even degrade its performance. Therefore, we canachieve better performance than the evenly (or fairly) partitioned allocation which is achieved in the Linux scheduler
by allocating optimal number of cores to each program according to their scalability.
The main contributions of this paper include the following:• We find that state-of-the-art Linux default scheduler
performs poorly in a multi-threaded multiprogramming
environment because of lacking the consideration ofscalability of its scheduled programs.
• We propose a scheduling algorithm which predicts thescalability of multi-threaded applications to dynamically allocate the appropriate number of cores to eachprogram in order to optimize system performance. We
also introduce a couple of sophisticated enhancements
to the scheduler which attempt to get the most out ofmanycore environments.
• We implement a practical user level scheduler called
SBMP (pronounced S-Bump) scheduler which (1) requires no changes to the OS kernel, (2) works on existing Linux systems and uses existing hardware perfor-

mance monitoring units (PMUs), and (3) works withany unmodified application binaries.
• We evaluate the proposed SBMP scheduler with an
AMD 48-core system, which shows our design well outperforms the Linux default scheduler for a series ofmultiprogramming workloads comprised of emerging
PARSEC benchmark suite [4].
The remainder of the paper is structured as follows. Next
section motivates our work on developing scalability-basedmanycore partitioning scheduler (SBMP scheduler) by showing the poor performance of Linux default scheduler when
multiple multi-threaded workloads are simultaneously executed on a manycore environment. Section 3 describes ourscheduler algorithm and implementation in detail along withsome novel improvements added to enhance our scheduler
design. Section 4 explains our evaluation framework andSection 5 shows the performance of the proposed scheduler
with wide variety of evaluations. Section 6 introduces related work, and finally the conclusions and future work arestated in Section 7.

2. MOTIVATION
Figure 1 shows how Linux default scheduler performs poorly
in a multi-threaded multiprogramming environment. The
figure shows performance result of four multi-threaded applications (canneal, ferret, raytrace and streamcluster
chosen from PARSEC benchmark suite) when they are simultaneously executed on a 48-core symmetric multi-processor
system∗ . Bars in Figure 1 indicate the normalized turnaroundtime (NTT) [11]. NTT is a lower-is-better metric which
has a value larger than or equal to one† , and quantifies theturnaround time slowdown due to multiprogrammed execution. Right most group of bars shows the average NTT (ANTT).
ANTT is a reciprocal of the commonly used harmonic mean
metric of the relative throughputs under multiprogramming
environment compared to their solo-runs [18]. ANTT has asystem-level meaning rather than the harmonic mean metric, and we believe it is a good indicator to represent system
performance in multiprogramming environments. Therefore, we use this metric throughout this work. The results ofLinux default scheduler and the best static partitioning areshown in the figure.
For these applications, the best partitioning (or core allocation) is: 12 cores for canneal and raytrace each, 18 coresfor ferret, and six cores for streamcluster. Note that all
programs create 48 threads (or more, according to the program) in order to fully utilize the processor, and threadsof each program are packed onto the specified number ofcores [7] when partitioned. The best partitioning was obtained by trying all the possible allocations. There are several ways to assign the cores to programs even the numberof cores to be assigned are the same. Figure 3 shows two
possible assignments which are (a) distributing or (b) centralizing the threads on the system. We have compared the
ANTT for these two types of assignments for all the workloads and found that centralizing the threads gives higher or∗

Figure 2 shows the base node architecture of the evaluation system we use throughout this paper. It consists of four CMPs witheach CMP having 12 core multi-chip module processor consisting of
two six core dies. Further details of the experimental environment is
described in Section 4.
†
Note that the origin of all the graphs which show the NTT begins
with one.

3.0

Linux

Best static partitioning

NTT

2.5
2.0
1.5
1.0
cannealferretraytrace

streamcluster

ANTT

Figure 1: Normalized turnaround time (NTT) of
Linux scheduler and static space sharing.
48-core AMD four socket system
CPU0
P0

CPU1
P1

P2

P5

P6

CPU2
P4

P3
CPU3
P7

C0

C1

C2

C3

C4

C5

L2

L2

L2

L2

L2

L2

Shared L3
Memory controller

Each processor die (e.g. P0) integrates six cores (e.g. C0)
Memory controller is located on each processor die

Figure 2: Node architecture of the evaluation platform.
APP0: canneal APP1: ferret APP2: raytrace APP3: streamcluster

A
P
P
0

A
P
P
2

A
P
P
0

APP1

A
P
P
2

A
P
P
0

A
P
P
2

A
P
P
0

A
P
P
2

A
P
P
1

A
P
P
3

A
P
P
1

A
P
P
3

(a) distributed

APP0

APP2

APP1

APP3

(b) centralized

Figure 3: Two possible program-to-core assignmentsof best partitioning.
at least the same performance in most cases. This is quite
intuitive because of the low latency of accessing the shareddata (including coherency messages) and minimized interference or contention between programs. Therefore, we use
the centralized assignment of cores throughout this work.
Also, we decided to use the processor die in Figure 2 asa minimum unit of allocation to programs. That is, eachprogram is provided a number of cores which is a multipleof six in the experimental platform. This restriction stillleaves us plenty of room for optimization, while eliminating
the unexpected contention by potentially giving exclusive
use of the portion of LLC which is on the same die. We cansay that the memory subsystem is partitioned as well as thecores, which means that the program with a greater number of cores also gets larger amount of LLC. More sophisticated memory managements such as applying page coloring
technique [17] in order to give larger amount of LLC to a
program with fewer number of cores can be considered, but
those optimizations are left for future work, and we focus
on the scheduling of CPU cores in this study. Note that
we dedicate each core to only a single program at a time,

which means that no two programs share the same core‡ .
These partitioning methods are also used in the proposedscheduler.
We can see the poor ANTT of the Linux default scheduler from Figure 1 which is 2.04, where the ANTT of best
static core allocation is 1.38, and significantly improves over
the Linux scheduler. To understand the reason of the result
shown in Figure 1, we display the scalability of the PARSEC
applications in Figure 4. The x-axis indicates the number ofcores allocated and y-axis shows relative performance to the
maximum. The benchmarks are classified into three groups
named with colors according to their scalability characteristics, namely Green, Yellow and Red, which are used in thelater section for discussions. The numbers on top of eachgraph show the maximum speedup obtained compared tothe case when a single core is assigned.
The key factor of this improvement is to appropriately
controlling the number of cores to be assigned to each application by considering their scalability. This can be seenfrom the scalability curve of the evaluated four programs, especially ferret and streamcluster. The best partitioning
allocates 18 cores to ferret and six cores to streamcluster. Streamcluster achieves its maximum performance at
six cores so there is no reason to allocate greater number ofcores from a performance point of view. Other three programs show similar shapes of scalability curve, however, thenumber on top of the graph showing the maximum speedup
against a single core assignment is the largest for ferretwhich is 17.22x. Therefore, it is beneficial to give the resource to ferret to maximize the multiprogramming performance. This result motivates us that the scalability of
programs should be taken into account by the OS scheduler
to achieve good performance.
We have seen the potential performance improvement ofstatic partitioning approach thus far, however, it is not practical to apply the static scheduling in a general purpose OS
scheduler because: (1) the best core assignment cannot beeasily obtained in advance without the knowledge of thescalability of programs a priori, (2) the best core allocation might change during runtime because applications canbe composed of several phases which shows different scalability characteristics, and (3) applications are dynamically
executed on a general purpose OS so that we do not know
which applications will be co-scheduled at what time. We
address the above issues by dynamically detecting the program’s scalability along with several enhancements which
are stated in Section 3.

3. SCHEDULER DESIGNWe designed and implemented SBMP scheduler, a scalabilitybased manycore partitioning scheduler which achieves highsystem performance under multi-threaded multiprogramming
execution. SBMP scheduler dynamically predicts the scalability of each multi-threaded application by using a simple performance model and select the appropriate amountof cores to be assigned. The model is obtained by slightly
modifying the Amdahl’s law equation. The key idea behind
this allocation is that, we do not give fair amount of CPU
time and resources as in the traditional OS scheduler, instead we provide the resources considering their scalability,‡

Later in Section 3, we propose an enhancement to the scheduler
which relaxes this constraint to allow up to two programs sharing
each core to improve performance.

GREEN37.49x
1.00

blackscholesRED
18.72x

6.66x

20.06xﬂuidanimate

freqmine

6

6

4.77x

0.75
0.50
0.25

canneal0
1

6

12 18 24 30 36 42 48 1

12 18 24 30 36 42 48 1

12 18 24 30 36 42 48

15.07x17.22x1

6

12 18 24 30 36 42 48 1

13.77xstreamcluster
6

12 18 24 30 36 42 48

8.88x

8.85x

1.00
0.75

ferret0.50

x264

raytrace

bodytrack

dedup

0.25
0
1

6

12 18 24 30 36 42 48 1

6

12 18 24 30 36 42 48 1

6

12 18 24 30 36 42 48

16

12 18 24 30 36 42 48 1

6

12 18 24 30 36 42 48

YELLOW

Figure 4: Scalability of the evaluated PARSEC benchmarks.
giving more resources to programs that make more use ofthem. That is, SBMP scheduler attempts to balance the utilization of resources, not the physical amount of resources.
This section provides the scheduling overview, as well as thedescription of the prediction model and its usage, and thescheduling algorithm and implementation of SBMP scheduler in detail.

3.1 Scheduler Overview
The basic overview of the scheduling algorithm is shown in
Figure 5. The top view of the algorithm is fairly simple constructing a loop which consists of the following: (1) SBMP
scheduler decides to change the core partitioning when it
detects that the optimal partitioning has changed, (2) predicts the scalability of the target program, and (3) calculates
the optimal core allocation based on the optimization metricand re-schedules the programs according to it. The detailof (1) through (3) is discussed in Subsections 3.3, 3.2, andin the following paragraphs of this subsection, respectively.
Subsection 3.4 describes a key improvement technique tothe SBMP scheduler which is called Core Donation whichaims to maximize the CPU utilization ratio by relaxing theconstraint that each core is exclusively used by a single program.
As stated in Section 2, we target in optimizing (minimizing) the average normalized turnaround time or ANTT metric because we believe it is a good metric to represent system
performance of multiprogramming workloads. However, thekey idea of the proposed scheduler which predicts and utilizes the scalability is not only restricted for optimizing thesystem against ANTT, but can be used to target different
performance metrics such as the weighted speedup metric, if
required. This can easily be accomplished by changing thefunction which seeks for the optimal allocation inside thescheduler.
ANTT is computed as
AN T T =n
1X
N T Ti =
n i=1

n
1X
CiM P
n i=1 CiSP

(1)

where CiSP and CiM P denote the number of clock cycles
to execute a program i under solo and multiprogrammed
runs, respectively. Minimizing ANTT means that all the
programs are fairly achieving high performance compared
to its peak performance (achievable only when occupying

(1)

(2)
Need to predict
scalability?

(3)

Yes
Predict scalability

Core partitioning (allocation)

Figure 5: Algorithm overview of SBMP.

the whole system by itself). Therefore, programs that scalealmost linearly (such as the applications labeled Green in
Figure 4) are removed from the co-scheduling candidate andrun in isolation, or gang-scheduling [3].
SBMP scheduler maintains a table called scalability-tablefor each multi-threaded program which consists of pairs ofvalues: each pair consists of a key and a value where key
stores the number of cores to be allocated, and the value
stores the relative performance against its peak when executed at the key number of cores. Note that having thistable is identical with being able to draw the scalability
curve shown in Figure 4. The value in the table represents
CiM P /CiSP in Equation (1), so the scheduler is able to compute ANTT for different core allocations during runtime.
The number of possible core assignments is computed as(Ncore − 1)!/(Ncore − Napp )!(Napp − 1)! where Ncore > Nappholds, Ncore and Napp being the number of cores in thesystem and number of programs that are being scheduled,respectively. It becomes unpractical to calculate and searchthrough all the possible ANTT values to find the optimal allocation when Ncore and/or Napp grow. Therefore, we use a
simple hill climbing algorithm similar to the technique usedin [8] to find the near optimal assignment.

3.2 Predicting the Scalability
SBMP scheduler needs to know the relative performanceagainst its best solo run for all the co-scheduled programs
during runtime to perform its scheduling. We propose to use
the number of cumulative retired instructions of the program
to indicate the performance. That is, we store the cumulative retired instructions per second (IPS) to the value ofthe scalability-table associated with each program. The key
notion behind this is the fact that changing the core assignments does not affect the total number of instructions.
Figure 6 supports our idea. It shows the number of cores
allocated on the x-axis and the number of total instructions
on the y-axis for PARSEC benchmarks. All the bars are ob-Number of cores:

1

6

12

18

24

30

36

42

48

110%
100%
90%
blackscholes

bodytrackcannealdedupferretﬂuidanimate

freqmine

raytrace

streamcluster

x264

Figure 6: Total number of dynamic instructions of PARSEC benchmarks for different core assignments.
tained by spawning 48 threads, assuming SBMP scheduling.
We can see that the applications whose number of instructions varies the most are canneal and dedup which showsslight variation of up to 8% in the worst case, which is still
acceptable for our purpose considering measurement errors.
Instruction counts of all the other programs are stable withrespect to the number of cores. Therefore, IPS is a perfectindicator to measure the scalability of a program.
As IPS values can be easily obtained by performance monitoring units (PMUs) which come with most of today’s microprocessors, it is possible for the scheduler to directly measure the values to fill the scalability-table. For example,
the scheduler can dynamically change the allocations duringruntime, and run the program for a fixed amount of time toobtain the values. However, we found out that the overhead of measuring the IPS in this manner is not negligible:
earning a stable IPS value for a new assignment requires the
OS to actually migrate the threads to the new allocation andrun for a while to warm up the caches and branch predictors.
This requires up to few hundred milliseconds per assignment
in the evaluated environment. Recall that we use the processor die in Figure 2 as a minimum unit of allocation, so
there are eight (48 divided by six) possible allocations to asingle program. Even after careful tuning of the software, it
took over three seconds to fill the table, and this overhead
will become larger according to the increasing number ofcores in the future. Therefore, we introduce a simple model
to predict the IPS values. By using the model, we can compute the IPS to fill the scalability-table by sampling the IPS
for only a few allocations.
The prediction model we use in this work is the following.
β
IP SN1+ γNcore=α+
IP SNcore
Ncore(α + β + γ = 1)

(2)

IP SN1 and IP SNcore indicate the IPS when allocated a single core and N cores, respectively. The left side of the equation represents the relative turnaround time against single
core execution, and the left two terms of the right side is
the same as that of Amdahl’s law equation [1]. Recall thatAmdahl’s law is a simple yet powerful model that models
the scalability of a parallel program. The formula is quite
intuitive and the scalability curve is known to fit well withreal world programs. However, as can be seen from Figure 4,
the scalability of some applications tend to not only saturate
at some point but also degrade its performance by adding
more number of cores. This cannot be represented by theoriginal Amdahl’s law. Therefore, we added the last term
γNcore which we expect to represent some overhead associated with adding more number of cores. The condition
equation in the parentheses follows the original condition of
the Amdahl’s law that the sum of the coefficients equals one,and this is because we assume that the parallel portion of
the program represented as β in the original equation, canbe divided into two sections where one can be parallelizedβ) and the other adds an overhead (γNcore ). There( Ncore

fore, we set the condition as the sum of α, β and γ equalsone.
To obtain the values of the coefficients, we use the leastsquares approach. Therefore, we need to at least collect the
IPS with three configurations (two different configurationsin addition to single core execution) in order to obtain thethree coefficients because Equation (2) has two individual
parameters.

3.3 Re-partitioning Algorithm
As seen from Figure 5, SBMP scheduler tries to change
the core partitioning when it considers that the optimal allocation has changed during the multiprogramming execution.
There are mainly two events that invokes the SBMP scheduler to re-partition during execution. Those events are (1)creation or termination of a program and (2) phase transition detected in any of the programs.
The first is natural, because it means that the multiprogramming workload has changed, and thus there is a chance
to find a better partitioning. When any of the program finishes its execution, SBMP simply calculates the optimal allocation using the existing scalability-table and allocates thecores according to it. When a new program is created, then
SBMP scheduler predicts the scalability of it as described in
Subsection 3.2, and performs the partitioning.
The second is more aggressive which utilizes the information obtained online to dynamically find a better core
assignment. Programs are typically composed of different
execution phases which show different characteristics, and
SBMP scheduler attempts to keep up with the optimal core
partitioning. Researchers have tried to detect phases to perform dynamic optimization, and there exists different definition of phases according to the optimization techniques. In
this paper, we consider phase as a region of program having
different scalability.
Figure 7 shows an example execution trace of x264 showing the execution phases having different scalability. x-axis
and y-axis of Figure 7 (a) represents time in milliseconds
and the cumulative execution cycles, respectively. The thickdotted line on top of the figure shows the maximum available cumulative cycles which is equivalent to the cumulative
execution cycles when the CPU is 100% utilized. The cumulative cycles is sampled every 50 ms. CPU utilization ratio
is obtained by dividing the cumulative execution cycles by
the maximum available cumulative cycles. We can see fromthe figure that the trace can be divided into three regions orphases by focusing on the cumulative execution cycles (identical to CPU utilization), which we named phase A, B and C.
Three figures of Figure 7 (b) on the right side show the scalability for those three phases. X-axis indicates the number ofcores allocated and the y-axis shows the relative performanceagainst a single-core execution. We can see similar trends forphases A and C which show a gentle curve giving the maximum performance at the maximum number of cores, anda much steeper scalability curve for phase B showing theRelative Performance

Cumulative cycles

Maximum available cumulative cycles

Phase C

Phase A
Phase BTime [ms](a)Phase A

Phase B

Phase C

30.0
22.5
15.0
7.5
0
1

6

12 18 24 30 36 42 48

16

12 18 24 30 36 42 48

16

12 18 24 30 36 42 48

Number of cores(b)

Figure 7: Execution trace of x264 showing the relationships between CPU utilization ratio and scalability.
(a) Time series plots of cumulative cycles and (b) scalability of different points are shown.

Table 1: CPU utilization ratio (%) of PARSEC
benchmarks
# of
cores
6
12
18
24
30
36
42
48

bl

fl

fr

fe

x2

ra

bo

de

ca

st

98.6
93.6
89.8
85.3
84.4
80.5
69.6
85.7

96.7
90.4
83.4
74.8
68.0
62.0
58.8
54.5

96.4
86.8
65.4
68.6
61.3
43.1
34.9
44.5

99.9
92.7
95.4
87.9
74.7
82.2
72.6
72.1

99.5
97.2
83.9
72.2
59.3
46.1
38.7
33.3

89.0
78.4
71.9
62.9
60.2
50.5
43.8
37.6

73.7
55.5
46.4
39.0
32.5
29.9
26.8
24.1

73.9
59.0
51.1
44.8
38.8
34.9
31.4
28.7

82.1
71.1
68.5
69.8
67.3
66.2
70.4
65.9

92.6
80.7
67.3
56.7
50.6
45.7
42.3
37.7

highest performance at 12 cores. These graphs motivate us
to detect the phase changes online and dynamically performa re-partitioning. Also, we can see that the CPU utilization
ratio which can be obtained from cumulative execution cycles is a good indicator to detect phase transition. Therefore,
SBMP scheduler detects the phase change by monitoring
its cumulative execution cycles. SBMP scheduler monitors
the PMUs every epoch (or time window), and whenever achange of the counter values greater than a certain thresholdcompared to the previous epoch has been observed, SBMP
scheduler enters the scalability prediction process to perform
re-scheduling.

3.4 Core Donation
The design of SBMP scheduler is described in the above
subsections, and here we introduce Core Donation, a sophisticated technique to improve the system performancein SBMP scheduler. As we have shown in Figure 7, different programs have different CPU utilization ratios. Table 1
shows the average CPU utilization ratio of PARSEC benchmarks (benchmark names are represented with their first two
letters) for different number of cores being allocated. We cansee a trend across benchmarks that by allocating more number of cores, the CPU utilization tends to decrease. This is afundamental problem in multi-threaded applications which
does not have linear scalability, so we have to overcome thistendency to achieve high performance. In addition, there arevariability in the utilization ratio that some programs havehigh utilization (blackscholes, ferret, and fluidanimate)while others have poor utilization (bodytrack and canneal).
One of the most important aspects of the OS scheduler is tokeep the CPU as busy as possible by continuously assigning
threads that are ready to execute. However, SBMP scheduler partitions the processor, and only a single program isallowed to run on each core which tends to waste the precious CPU time.
We provide a solution to this problem by letting a program
which has a utilization ratio lower than a certain thresholdto be a “donor” of CPU cores (or CPU time). After allo-

cating the cores to each program, SBMP scheduler checks if
any of the program meets the requirement of a donor. If it
finds a correspondent program, SBMP scheduler picks another program which benefits the most by getting additionalcores (which has a high utilization ratio and good scalability) from the scalability-table, and sets the program as a“donee”. SBMP scheduler allows the donee program to be
executed on the donor’s cores by allocating the program toits original partition and also the donor’s partition. Therefore, there are two multi-threaded applications which canrun on donor’s cores. Donee is kept from interfering withthe donor’s threads by executing its threads only when thedonor cannot utilize the CPU. We use the thread priority
mechanism to achieve this requirement by making the priority of donee program much lower than that of the donor.
This makes the situation where donor can preempt donee’s
execution while the opposite is not possible. Core Donation
is applied after core partitioning (see (3) of Figure 5).
The interesting point of Core Donation is that it works
in synergy with the SBMP scheduler by optimizing against
different granularities. SBMP scheduler assigns the cores toprograms by using the processor die as a minimal unit, which
is six cores in the evaluation platform. This is rather a coarse
grain spatial optimization while Core Donation tries to fillin the gap and apply finer granularity optimization after arough optimization done by SBMP scheduler. Also, Core
Donation works in a much finer time granularity than theoriginal SBMP, and is possible to increase the CPU utilization to improve system performance. Therefore, by applying
the partitioning of SBMP scheduler and the optimization ofCore Donation, the proposed set of techniques make themost out of manycore architectures to achieve high performance.
We have to be careful that the utilization ratio to detect aphase change for donee programs should be only measured
at its original partition (there might be some disturbanceby the donor program at the donor’s cores). Note that eachprogram is allowed to either be a donor or donee but notboth, and a donor is only allowed to have one donee.

4. EXPERIMENTAL SETUP
4.1 Hardware Platform
We perform experiments on a quad socket IBM System
x3755 M3 server which consists of four 12-core AMD Opteron6172 microprocessors running at 2.1 GHz forming a 48-coresystem. Each socket integrates two six-core dies with eachcore having its own private L1 and L2 caches along with ashared 12 MB L3 cache. Table 2 shows relevant hardware
parameters of the evaluation platform.

Table 2: Parameters of the evaluation platform
Processor:# of dies per processor# of cores per die:
Total # of cores:
L3 cache size:
Main memory:

4 × AMD Opteron 6172
2648
12 MB per socket
96 GB DDR3 PC3-10600

Table 3: Parameters of the SBMP scheduler
Threshold ofphase change detection:
Length of epoch:
Length of the first epoch
after re-scheduling:# of samples for prediction:(# of cores)
Overhead of prediction:
Threshold of becoming a “donor”
in Core Donation:

Utilization ratio more thandoubles or gets smaller thanhalf of the previous epoch
2.5 seconds
10 seconds
four points(1, 12, 24 and 48)≈ 550 milliseconds
70%

4.2 SBMP Scheduler Implementation
We have implemented a prototype of SBMP scheduler as auser level software. The evaluation system runs Linux kernel
2.6.37.6, and the modified version of perf-tools toolset isused to allow periodical access to the PMUs. CPU clock
frequency scaling is disabled to avoid measurement variance.
We use standard Linux API (sched_setaffinity(2) andsetpriority(2)) to control the CPU affinity of processes
to bind the programs to specific cores and to manage thepriority (niceness) of each program in order to apply Core
Donation technique.
Detailed values of parameters used inside the SBMP scheduler are shown in Table 3. Threshold to detect phase change
and its length of sampling epoch is experimentally obtainedby taking the overhead of prediction into account. Also, we
set the first epoch after re-scheduling to 10 seconds to prevent oscillation of re-scheduling. For the sampling points,
increasing the number of samples tends to increase the fitting accuracy but the associated overhead of sampling also
becomes larger (≈150ms for each sample). Therefore, weconstructed a model of all the possible combinations for eachbenchmark in advance and compared the fitting accuracy tothe plot shown in Figure 4. As a result, four sample points
with 1, 12, 24 and 48 cores gave us a good balance between
fitting accuracy (coefficient of determination over 0.99) andthe overhead on average and we chose them as shown in thetable. We apply Core Donation if the utilization of any ofthe programs being executed is below 70%.

cluded because we could not correctly compile them on theevaluation platform. Additionally, we exclude blackscholes
and fluidanimate which are categorized as Green in Figure 4. Highly scalable applications prefer being executedin a gang-scheduling manner as shown in other work [3],where SBMP scheduler can detect these applications as having good scalability by checking the scalability-table, and remove from co-scheduling in order to perform gang-scheduling.
Although categorized as Green, we left freqmine in the evaluation workloads because it has a reduction operation whichshows multiple phase changes during its execution and isused to show the effectiveness of our phase detection capability.
We evaluate SBMP scheduler with variety of workloads
where each workload is composed of four benchmark programs. SBMP scheduler is designed to optimize the scheduling under multiprogramming environment with a number ofparallel programs with wide varieties of scalability, however,increasing the number of applications within each workload
reduces the possible allocations resulting in no space to optimize. For example, as we give each program at least six
cores, having more than four programs within a workload
results in giving at least one program to only stick on theminimum allocation of six cores. Therefore, we chose four
as a number to create each workload because it gives us agood balance between the optimization flexibility as well as
enough load on the target system.
Because the main target of SBMP scheduler is efficient
co-scheduling of parallel regions of multi-threaded multiprogramming workloads, we use Berkeley Lab Checkpoint/Restart(BLCR) tools [13] to set up an environment which enables
checkpoint and restart of programs to evaluate only the parallel region called the region of interest (ROI) of PARSEC,
which is marked in the original source code. Our evaluationis conducted using this system running from the beginning
till the end of ROI for all benchmarks.
The evaluation methodology is similar to the one originally proposed for SMT job scheduling [26], and a numberof following work have been evaluated in a similar manner [2,12, 15, 29]. To account for the varieties of execution times(from tens to hundreds of seconds), we restart an application instantaneously when it finishes execution until all the
programs are executed at least three times to completion.
We measure the execution time of each application using
the time command in Linux.

5. EVALUATION RESULTS
5.1 Programs with a Single Phase

First, we show the results with the workloads which does
not include applications that have multiple phases withinprograms. For this purpose, we have set up six workloads
We use PARSEC benchmark suite 2.1 [4] to evaluate SBMP
which include two applications classified as Red (canneal
scheduler against the Linux default scheduler. PARSEC
and streamcluster), and the other two from Yellow benchbenchmark suite is designed to evaluate shared-memory commarks (bodytrack, dedup, ferret and raytrace). The Red
puters, and is composed of a set of emerging workloads
applications have low scalability and thus assigning a large
for future manycore processors. We compile PARSEC with
GCC-4.1 with “-O3 -funroll-loops -fprefetch-loop-arrays” number of cores will hurt system performance. Therefore,
we can see if SBMP scheduler can accurately predict theoptions. We use native input sets for all benchmarks except
scalability of the program. Evaluated workloads are shown
dedup. Because the execution time of dedup was too shortin Table 4.
compared to other programs, we use a larger input (the FeFigure 8 shows the ANTT for each workload of SBMPdora 16 x86 64 DVD ISO).
base, which is the simplest implementation of SBMP schedWe have shown 10 out of 13 PARSEC benchmarks in figuler which does not have the ability of phase prediction nor
ures 4 and 6 where facesim, swaptions and vips are ex-

4.3 Workloads

Table 4: Multiprogrammed workloads to evaluate
SBMP-base
ID
1
2
3
4
5
6

Benchmarks
bo-ca-de-stbo-ca-fe-stbo-ca-ra-st
ca-de-fe-st
ca-de-ra-st
ca-fe-ra-st

Type
YYRR
YYRR
YYRR
YYRR
YYRR
YYRR

Table 5: Multiprogrammed workloads to evaluate
SBMP-PP
ID
7
8
9
10
11
12
13
14
15

Benchmarks
bo-ca-fe-fr
bo-ca-fr-x2
bo-fe-fr-st
bo-fr-st-x2
ca-de-fe-fr
ca-de-fr-x2
ca-fe-fr-ra
ca-fr-ra-x2
de-fe-fr-st

Type
GYYR
GYYR
GYYR
GYYR
GYYR
GYYR
GYYR
GYYR
GYYR

ID
16
17
18
19
20
21
22
23
24

Benchmarks
de-fr-st-x2
fe-fr-ra-st
fr-ra-st-x2
bo-ca-fe-x2
bo-fe-st-x2
ca-de-fe-x2
ca-fe-ra-x2
de-fe-st-x2
fe-ra-st-x2

Type
GYYR
GYYR
GYYR
YYYR
YYYR
YYYR
YYYR
YYYR
YYYR

Table 6: Multiprogrammed workloads to evaluate
SBMP-CD
ID
25
26
27
28
29
30
31

Benchmarks
bo-de-fe-fr
bo-de-fe-x2
bo-de-fr-ra
bo-de-fr-x2
bo-ca-de-fr
bo-de-fr-st
bo-de-fe-ra

Type
GYYY
GYYY
GYYY
GYYY
GYYR
GYYR
YYYY

ID
32
33
34
35
36
37
38

Benchmarks
bo-de-ra-x2
bo-ca-de-fe
bo-ca-de-rabo-ca-de-x2
bo-de-fe-stbo-de-ra-stbo-de-st-x2

Type
YYYY
YYYR
YYYR
YYYR
YYYR
YYYR
YYYR

2.5

Linux

SBMP-base

ANTT

2.0

1.5

1.0
1

2

3

4

5

6

GEOMEAN

Figure 8: ANTT of Linux and SBMP-base schedulers for applications with a single phase.
Core Donation, is compared against Linux scheduler. Average ANTT of Linux scheduler is 1.88, and SBMP-base whose
average ANTT is 1.54 well outperforms Linux scheduler for
all the workloads evaluated. The results show that effectively choosing the core allocation based on the scalabilityof each program gives performance benefit over Linux scheduler. From these results, we can conclude that the proposed
scalability prediction algorithm described in Subsection 3.2
succeeds in predicting the scalability of programs.

5.2 Programs with Multiple Phases
Next, we present the results by evaluating the workloads
which contain applications that have multiple phases within
the program such as x264 shown in Figure 7. The evaluatedworkloads are shown in Table 5. All the workloads include
two out of three applications which have multiple phases(freqmine, ferret and x264), one from Yellow applications,and another from Red applications.

Figure 9 shows the result of the Linux scheduler, SBMPbase and SBMP-PP which is SBMP-base with phase prediction enabled. Average ANTT of the Linux scheduler,
SBMP-base and SBMP-PP are 1.89, 2.09 and 1.77, respectively. We can see that while SBMP-base shows lower performance than the Linux scheduler, SBMP-PP significantly
outperforms both, showing the superiority of SBMP-PP.
The representative contribution of SBMP-PP can be seen
in many workloads such as 10, 11, 12, 13 and so on, where
SBMP-base has the worst case ANTT. Because SBMP-baseonly predicts the scalability of each program at the point ofcreation/termination, it tremendously suffers from making
a wrong decision at the point of re-scheduling. However, because SBMP-PP has the ability to dynamically detect phasetransition, it can recover from making a bad decision. Thisreveals us that the aggressive re-scheduling based on phasedetection is beneficial for programs which are composed ofmultiple phases. We have presented that detecting and optimizing against the scalability, which is the key insight of
SBMP scheduling, is effective in scheduling multi-threaded
multiprogramming workloads.

5.3 Programs with Various CPU Utilizations
Now, we show whether Core Donation can improve performance against the Linux scheduler and SBMP-PP. The
14 workloads which are evaluated are presented in Table 6.
These workloads are comprised of two applications whichhave low CPU utilization (bodytrack and dedup as can beseen from Table 1), and all the other applications.
Figure 10 shows the performance results of the Linuxscheduler, SBMP-PP and SBMP-CD which utilizes Core
Donation technique along with SBMP-PP. The average ANTT
among the workloads of the Linux scheduler, SBMP-PP and
SBMP-CD are 2.06, 1.68 and 1.60, respectively. SBMPCD shows the best performance on average across the workloads. Because the workloads are composed of applications
which have low CPU utilization, the Linux scheduler has
the advantage of effectively utilizing the CPUs by assigning
ready-to-execute threads one after another for some workloads. However, SBMP-CD performs better than the Linuxscheduler by utilizing the CPU time given by the donor applications. This is well confirmed by comparing SBMP-PP
against SBMP-CD, which shows that SBMP-CD achieves
better or at least comparable performance over SBMP-PP.
This shows that the idea of donors giving the CPU time
to donees without interfering donor’s threads gives performance improvement. Although ANTT difference between
SBMP-PP and SBMP-CD is not so large compared to otherresults (Linux and SBMP-base in Figure 8, and SBMP-baseand SBMP-pp in Figure 9), we believe that by having morenumber of cores on the system and broader optimization
space will widen this gap between SBMP-PP and SBMPCD. Also, another optimization to be considered is that adonor having more than one donees at the same time, whichis left for future work.

5.4 Overall Performance with All Programs
Figure 11 presents the ANTT comparison of all the schedulers for all 70 workloads we have evaluated. The figure
shows the workloads on the x-axis and the ANTT on the
y-axis. We present the curves independently sorted for eachscheduler. The overall average ANTT for the Linux, SBMPbase, SBMP-PP and SBMP-CD schedulers are 1.83, 1.99,

2.83

ANTT

2.5

Linux

SBMP-base

SBMP-PP

2.0
1.5
1.0

&

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24 GEOMEAN

Figure 9: ANTT of Linux and SBMP-PP schedulers for applications with multiple phases.
4.14

ANTT

2.5

Linux

SBMP-PP

SBMP-CD

2.0
1.5
1.0
25

26

27

28

29

30

31

32

33

34

35

36

37

38

GEOMEAN

Figure 10: ANTT of Linux and SBMP-CD schedulers for applications with low CPU utilization.
2.25

ANTT

2.00

1.75

1.50

Linux

SBMP-base

SBMP-PP

SBMP-CD

1.25
0

14

28

42

56

70

Workloads

Figure 11: ANTT of all workloads.
1.70 and 1.65, respectively. As can be seen from the figure, SBMP-base scheduler shows the worst performance, andshows 8% degradation against the Linux scheduler. Interestingly, the lowest ANTT values are achieved by SBMP-base,showing the superiority of it when there is only a single phasewithin the applications. By adding the capability of phaseprediction and adaptation to SBMP-base, performance significantly improves and outperforms the Linux scheduler for
8%. Finally, SBMP-CD shows better ANTT over SBMP-PP
for 3%, which can clearly seen from the right hand side of
figure.

6.

RELATED WORK

Scheduling for multiprogrammed multi-threaded
applications: The work most close to ours is the HOLISYN
schedulers by Bhadauria and McKee [3]. The base concept ofapplying dynamic space-sharing for applications that do notscale is the same, however, they aim at dealing with scalability limitation caused by hardware resource contention,and the optimization target of their work is energy delay
product, and therefore the policy of deciding the numberof cores to allocate differs from our work. Our techniqueconsiders the scalability of a program limited by the software nature by predicting its scalability, and evaluated witha 48-core system to show the effectiveness. Dynamic space-sharing techniques are well studied in the HPC area [10,25], and approaches to dynamically adjust the scalability ofa program is also examined [9]. Recent work called Thread
Tailor [16] proposes a dynamic compilation system that can
automatically adjusts the number of threads by combining
multiple threads together.
Avoiding contention through scheduling: OS scheduling approaches to avoid contention in multicore processors
have been studied as well [12, 22, 30]. Contention in sharedresources other than LLC such as the memory controller,
prefetcher or the memory bus is also a big cause of performance degradation. In some study, LLC miss rate is shown
to be a good indicator of shared resource intensiveness andsensitiveness [30]. A cache model which predicts the performance impact of process-to-core assignment is used in auser level scheduler to improve performance [2]. Our work
differs from these studies in several ways but the most important point is that we target multi-threaded applications
while they concentrate on single-threaded applications.
NUMA aware systems: Recently, several work have focused on optimizing process scheduling on NUMA systems
by taking the physical locations of cores, LLC, and memory
controller into account. A simple model proposed to characterize the local and remote memory system performance of
NUMA system has been evaluated [20]. In NUMA systems,
even when LLC competing threads are on the same die, theoptimal scheduling might not be separating these threads
apart because a thread being migrated will incur higher
latency for memory accesses [6, 19]. The shared resource
contention as well as data locality should be considered together to find the optimal scheduling. Our platform is alsoa NUMA and NUCA system, however, SBMP scheduler has
not focused on thread migration to reduce shared resource
contention. SBMP scheduler applies a centralized thread assignment which minimizes the shared resource contention at
the memory hierarchy in nature. However, we have not evaluated throughly by considering NUMA characteristics andwe believe there is still room left for optimization. Thoseare left for future work.

7.

CONCLUSIONS AND FUTURE WORKIn this work, we investigate the OS scheduling for the
manycore era where various parallel applications with diverse scalability are co-scheduled. Traditional OS scheduler
maintains fairness by giving fair amount of CPU time toeach thread or process, however we believe that there are
two key factors that the scheduler has to be concerned: scalability and CPU utilization. We have shown that scalabilityof applications should be taken into account to achieve highsystem performance, where the key idea is to allocate the appropriate amount of shared resources to programs according
to their scalability, in order to maintain high system performance. We have proposed a technique to dynamically predict the scalability of the program, as well as a sophisticatedphase recognition technique. We have also found that CPU
utilization of multi-threaded applications have diverse characteristics, and proposed Core Donation technique whichtries to maximize the CPU utilization of the system whilestill keeping the scalability into account.
We have built a prototype SBMP scheduler and compared the performance with the Linux scheduler for variety
of workloads. SBMP scheduler shows higher system performance compared to the Linux scheduler, indicating each
optimization technique presented in the paper is quite effective. We have not done any optimizations to avoid sharedresource contention, and there might be better schedulingwhen carefully considering the NUCA and NUMA architecture characteristics in detail. Exploration of the scheduler
on NUCA and NUMA architectures are left for future work.

8.

ACKNOWLEDGMENTS

This research was supported in part by New Energy andIndustrial Technology Development Organization, and JSPS
Grant-in-Aid for Challenging Exploratory Research (22650008).

9.

REFERENCES[1] G. Amdahl. Validity of the single processor approachto achieving large scale computing capabilities. In
AFIPS ’67 (Spring), 1967.
[2] M. Banikazemi et al. PAM: a novel
performance/power aware meta-scheduler for
multi-core systems. In SC ’08, 2008.
[3] M. Bhadauria and S. McKee. An approach toresource-aware co-scheduling for CMPs. In ICS ’10,
2010.
[4] C. Bienia. Benchmarking modern multiprocessors.
PhD thesis, Princeton University, 2011.
[5] S. Blagodurov et al. Contention-aware scheduling on
multicore systems. ACM Transactions on Computer
Systems (TOCS), 28(4), 2010.
[6] S. Blagodurov et al. A case for NUMA-aware
contention management on multicore systems. In
USENIXATC ’11, 2011.
[7] R. Cochran et al. Pack & Cap: adaptive DVFS andthread packing under power caps. In MICRO 44,
pages 175–185. ACM Request Permissions, Dec. 2011.
[8] J. Corbalán et al. Performance-driven processor
allocation. In OSDI ’00, 2000.
[9] J. Corbalán et al. Improving Gang Scheduling throughjob performance analysis and malleability. In ICS ’01,
2001.

[10] J. Corbalán et al. Performance-driven processor
allocation. IEEE Transactions on Parallel andDistributed Systems, 16(7):599–611, 2005.
[11] S. Eyerman and L. Eeckhout. System-level
performance metrics for multiprogram workloads.
IEEE Micro, 28(3):42–53, 2008.
[12] A. Fedorova et al. Improving performance isolation on
chip multiprocessors via an operating systemscheduler. In PACT ’07, 2007.
[13] P. Hargrove and J. Duell. Berkeley lab
checkpoint/restart (BLCR) for linux clusters. Journalof Physics: Conference Series, 46:494, 2006.
[14] J. Huh et al. Exploring the Design Space of Future
CMPs. In PACT ’01, 2001.
[15] R. Knauerhase et al. Using OS observations toimprove performance in multicore systems. IEEE
Micro, 28(3), 2008.
[16] J. Lee et al. Thread tailor: dynamically weaving
threads together for efficient, adaptive parallel
applications. In ISCA ’10, 2010.
[17] J. Lin et al. Gaining insights into multicore cachepartitioning: Bridging the gap between simulation andreal systems. In HPCA ’08, pages 367–378, 2008.
[18] K. Lun et al. Balancing thoughput and fairness in
SMT processors. In ISPASS ’01, 2001.
[19] Z. Majo and T. Gross. Memory management in
NUMA multicore systems: trapped between cache
contention and interconnect overhead. In ISMM ’11,
2011.
[20] Z. Majo and T. Gross. Memory system performance ina NUMA multicore multiprocessor. In SYSTOR ’11,
2011.
[21] C. Pheatt. Intel R threading building blocks. Journalof Computing Sciences in Colleges, 23(4), 2008.
[22] K. Pusukuri et al. FACT: a framework for adaptive
contention-aware thread migrations. In CF ’11, 2011.
[23] M. Qureshi and Y. Patt. Utility-based cachepartitioning: a low-overhead, high-performance,
runtime mechanism to partition shared caches. In
MICRO 39, 2006.
[24] K. Sankaralingam et al. Exploiting ILP, TLP, and
DLP with the polymorphous TRIPS architecture. In
ISCA ’03, 2003.
[25] C. Severance and R. Enbody. Comparing Gang
Scheduling with dynamic space sharing on symmetricmultiprocessors using automatic self-allocating threads(ASAT). In IPPS ’97, 1997.
[26] A. Snavely and D. Tullsen. Symbiotic jobschedulingfor a simultaneous multithreaded processor. In
ASPLOS-IX, 2000.
[27] M. Taylor et al. The raw microprocessor: acomputational fabric for software circuits andgeneral-purpose programs. IEEE Micro, 22(2), 2002.
[28] J. Weinberg and A. Snavely. User-guided symbiotic
space-sharing of real workloads. In ICS ’06, 2006.
[29] S. Zhuravlev et al. Addressing shared resource
contention in multicore processors via scheduling. In
ASPLOS ’10, 2010.
[30] S. Zhuravlev et al. AKULA: a toolset forexperimenting and developing thread placement
algorithms on multicore systems. In PACT ’10, 2010.