[GSOC] Add SMT/HT awareness to DragonFlyBSD scheduler

Fri Mar 30 10:24:22 PDT 2012

--14dae934069f85e46f04bc791c8d
Content-Type: text/plain; charset=ISO-8859-1

Hello,

My name is Mihai Carabas and I am a first year student at a master program
from Politehnica University of Bucharest, Romania, Computer Science and
Engineering Department. After browsing through all the projects, I've
notice the "Add SMT/HT awareness to DragonFlyBSD scheduler" project on GSOC
page and I would be really happy to work on it.

I will talk a little of my background and then I will describe the project.

As a research project for master program, I am working at a microkernel
from L4 family (the research is done only during the school time, as part
of the master program). The target is to create a High Available system,
but we are currently adding to the microkernel different mechanisms and
services that we need in order to accomplish our goal (eg. porting a MMC
driver and a FAT filesystem, from u-boot, in order to be able to store the
checkpoints on a permanent memory location, add a featue to start at
runtime different services [for now, the services are included from the
build step only], etc). I graduated bachelor also at Politehnica University
of Bucharest. I had different classes regarding operating systems design.
In one of the classes we studied the interface to the kernel (how to use
system calls) and have done the following projects in user-space (with
POSIX and Win32 API): mini-shell, swapper&demmand pager (using virtual
memory mechanisms), a client-server protocol using IPC and a generic
monitor (using locking mechanisms). We also had a class where we had
studied operating systems internals and had some projects that implied
kernel programming: driver for a serial port (UART16550), a minimal
software RAID, a filesystem using linux VFS, syscall interceptor (that
monitors and logs data about the calling processes), a new protocol for
network and transport layer based on datagrams (the protocol have the role
of a transport layer protocol but it was implemented at layer 3, over the
data link layer. As you can see, I worked on various platforms and I am
able to adapt to changes. I worked on different flavours of kernels
(microkernel and monolithic kernel). There will not be a problem adapting
to DragonFlyBSD kernel programming.

About this project, after browsing the article [3] you recomanded and linux
sources, I elaborated some impotant steps to follow.

In order to add support for the SMT to the scheduler, I have to establish
answers for the following basic questions:
1. which CPUs are siblings (share the same core)
2. which is the status of each core
3. where to schedule

Before I begin, I must get a strong understanding of the current scheduler
implementation [1]. Also I have to take a good look in the initialization
of the CPU information that the kernel is holding. For this I will start
and dig from the entry point of the kernel [2] [6]. As for documenting, a
good start is the article [3] mentioned in your project proposal and
current linux implementation of the scheduler [4]. Also I have found a
technical report from 2005, written by James R. Bulpin which describes the
entire hyper-threading technology (from hardware to software) [8]. Though
is an old paper and there are current advanced SMT-aware schedulers, the
theoretical base is the same and is a good place to understand well how I
can reach my final goal. In this article, there is a section provinding
different tests from where I can start developing the testing suite.

After a brief documentation I can start working on the following goals:

A. Detect how many threads have each core
 -  adding a generic way of detecting how many threads each core has
(create a map of siblings for example)
 -  guard all new added the information regarding HyperThreading. For this,
I will add an option (Enable HT) in the config file [5].

B. Effective SMT aware scheduling task
   In order to achieve the final goal, I have to make a design of how
threads will get scheduled. I will have to treat different cases:
- "passive" scheduling - select a free physical CPU (if available) for the
next thread to schedule
- "active" scheduling - if a physical CPU becomes idle and on another CPU
are running two threads, migrate one of them on the idle physical cpu
- what task to get from a list - get the one that was scheduled on that
domain (physical CPU), no matter on what logical CPU has run before
- tasks should stick to the same domain (physical CPU)

In order to achieve all cases presented above, a shared runqueue per
physical CPU will fulfill al the requirements, as stated in the paper
presenting the linux implementation [3].

C. Testing and testing again
- benchmarks with different types of loads
- intensive CPU long jobs
- much more CPU short jobs
- each benchmark will run on
-a kernel compiled without HT support (SMT un-aware)
-a kernel compiled with HT support (SMT aware)

- at this step, not only test the performance of the SMT aware scheduler,
but discover any unknown bugs introduced by this feature

I would be glad to know your opinion on the above.

Best regards,
Mihai

[1]
http://gitweb.dragonflybsd.org/dragonfly.git/blob/master:/sys/kern/kern_usched.c
[2]
http://gitweb.dragonflybsd.org/dragonfly.git/blob/master:/sys/kern/init_main.c
[3] http://lwn.net/Articles/8553/
[4] http://lxr.linux.no/linux+v3.3/kernel/sched/core.c
[5]
http://gitweb.dragonflybsd.org/dragonfly.git/blob/master:/sys/config/GENERIC
[6] http://www.freebsd.org/doc/en/books/arch-handbook/boot-kernel.html
[7] http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-619.pdf

--14dae934069f85e46f04bc791c8d
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div>Hello,</div><div><br></div><div>My name is Mihai Carabas and I am a fi=
rst year student at a master program from Politehnica University of Buchare=
st, Romania, Computer Science and Engineering Department. After browsing th=
rough all the projects, I've notice the "Add SMT/HT awareness to D=
ragonFlyBSD scheduler" project on GSOC page and I would be really happ=
y to work on it.</div>
<div><br></div><div>I will talk a little of my background and then I will d=
escribe the project.</div><div><br></div><div>As a research project for mas=
ter program, I am working at a microkernel from L4 family (the research is =
done only during the school time, as part of the master program). The targe=
t is to create a High Available system, but we are currently adding=A0to th=
e microkernel=A0different mechanisms and services that we need in order to =
accomplish our goal (eg. porting a MMC driver and a FAT filesystem, from u-=
boot, in order to be able to store the checkpoints on a permanent memory lo=
cation, add a featue to start at runtime different services [for now, the s=
ervices are included from the build step only], etc). I graduated bachelor =
also at Politehnica University of Bucharest. I had different classes regard=
ing operating systems design. In one of the classes we studied the interfac=
e to the kernel (how to use system calls) and have done the following proje=
cts in user-space (with POSIX and Win32 API): mini-shell, swapper&demma=
nd pager (using virtual memory mechanisms), a client-server protocol using =
IPC and a generic monitor (using locking mechanisms). We also had a class w=
here we had studied operating systems internals and had some projects that =
implied kernel programming: driver for a serial port (UART16550), a minimal=
 software RAID, a filesystem using linux VFS, syscall interceptor (that mon=
itors and logs data about the calling processes), a new protocol for networ=
k and transport layer based on datagrams (the protocol have the role of a t=
ransport layer protocol but it was implemented at layer 3, over the data li=
nk layer. As you can see, I worked on various platforms and I am able to ad=
apt to changes. I worked on different flavours of kernels (microkernel and =
monolithic kernel). There will not be a problem adapting to DragonFlyBSD ke=
rnel programming.</div>
<div><br></div><div>About this project, after browsing the article [3] you =
recomanded and linux sources, I elaborated some impotant steps to follow.</=
div><div><br></div><div>In order to add support for the SMT to the schedule=
r, I have to establish answers for the following basic questions:</div>
<div>1. which CPUs are siblings (share the same core)</div><div>2. which is=
 the status of each core</div><div>3. where to schedule</div><div><br></div=
><div>Before I begin, I must get a strong understanding of the current sche=
duler implementation [1]. Also I have to take a good look in the initializa=
tion of the CPU information that the kernel is holding. For this I will sta=
rt and dig from the entry point of the kernel [2] [6]. As for documenting, =
a good start is the article [3] mentioned in your project proposal and curr=
ent linux implementation of the scheduler [4]. Also I have found a technica=
l report from 2005, written by James R. Bulpin which describes the entire h=
yper-threading technology (from hardware to software) [8]. Though is an old=
 paper and there are current advanced SMT-aware schedulers, the theoretical=
 base is the same and is a good place to understand well how I can reach my=
 final goal. In this article, there is a section provinding different tests=
 from where I can start developing the testing suite.=A0</div>
<div><br></div><div>After a brief documentation I can start working on the =
following goals:</div><div><br></div><div>A. Detect how many threads have e=
ach core</div><div>=A0- =A0adding a generic way of detecting how many threa=
ds each core has (create a map of siblings for example)</div>
<div>=A0- =A0guard all new added the information regarding HyperThreading. =
For this, I will add an option (Enable HT) in the config file [5].</div><di=
v><br></div><div>B. Effective SMT aware scheduling task</div><div>=A0 =A0In=
 order to achieve the final goal, I have to make a design of how threads wi=
ll get scheduled. I will have to treat different cases:</div>
<div>- "passive" scheduling - select a free physical CPU (if avai=
lable) for the next thread to schedule</div><div>- "active" sched=
uling - if a physical CPU becomes idle and on another CPU are running two t=
hreads, migrate one of them on the idle physical cpu</div>
<div>- what task to get from a list - get the one that was scheduled on tha=
t domain (physical CPU), no matter on what logical CPU has run before</div>=
<div>- tasks should stick to the same domain (physical CPU)</div><div><br>
</div><div><span class=3D"Apple-tab-span" style=3D"white-space:pre">	</span=
>In order to achieve all cases presented above, a shared runqueue per physi=
cal CPU will fulfill al the requirements, as stated in the paper presenting=
 the linux implementation [3].</div>
<div><br></div><div>C. Testing and testing again</div><div>- benchmarks wit=
h different types of loads</div><div><span class=3D"Apple-tab-span" style=
=3D"white-space:pre">	</span>- intensive CPU long jobs</div><div><span clas=
s=3D"Apple-tab-span" style=3D"white-space:pre">	</span>- much more CPU shor=
t jobs</div>
<div>- each benchmark will run on</div><div><span class=3D"Apple-tab-span" =
style=3D"white-space:pre">	</span>-a kernel compiled without HT support (SM=
T un-aware)</div><div><span class=3D"Apple-tab-span" style=3D"white-space:p=
re">	</span>-a kernel compiled with HT support (SMT aware)</div>
<div><br></div><div>- at this step, not only test the performance of the SM=
T aware scheduler, but discover any unknown bugs introduced by this feature=
</div><div><br></div><div>I would be glad to know your opinion on the above=
.</div>
<div><br></div><div>Best regards,</div><div>Mihai</div><div><br></div><div>=
[1] <a href=3D"http://gitweb.dragonflybsd.org/dragonfly.git/blob/master:/sy=
s/kern/kern_usched.c">http://gitweb.dragonflybsd.org/dragonfly.git/blob/mas=
ter:/sys/kern/kern_usched.c</a></div>
<div>[2] <a href=3D"http://gitweb.dragonflybsd.org/dragonfly.git/blob/maste=
r:/sys/kern/init_main.c">http://gitweb.dragonflybsd.org/dragonfly.git/blob/=
master:/sys/kern/init_main.c</a><span class=3D"Apple-tab-span" style=3D"whi=
te-space:pre">	</span></div>
<div>[3] <a href=3D"http://lwn.net/Articles/8553/">http://lwn.net/Articles/=
8553/</a></div><div>[4] <a href=3D"http://lxr.linux.no/linux+v3.3/kernel/sc=
hed/core.c">http://lxr.linux.no/linux+v3.3/kernel/sched/core.c</a></div><di=
v>
[5] <a href=3D"http://gitweb.dragonflybsd.org/dragonfly.git/blob/master:/sy=
s/config/GENERIC">http://gitweb.dragonflybsd.org/dragonfly.git/blob/master:=
/sys/config/GENERIC</a></div><div>[6] <a href=3D"http://www.freebsd.org/doc=
/en/books/arch-handbook/boot-kernel.html">http://www.freebsd.org/doc/en/boo=
ks/arch-handbook/boot-kernel.html</a></div>
<div>[7] <a href=3D"http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-619.pdf"=
>http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-619.pdf</a></div>

--14dae934069f85e46f04bc791c8d--