jeffr_tech ([info]jeffr_tech) wrote,

non-uniform cpu scheduling.

After a month sick with some random virus I'm finally starting to feel normal and get some work done again. I spent some time implementing a long standing idea I've had for a more flexible and dynamic CPU topology to improve scheduling decisions. Modern multi-core processors are non-uniform from a variety of perspectives. For example, the barcelona has a shared L3 among all cores on a package. So if you have two packages and you're placing two threads on cores within one package you're wasting half your cache. To take advantage of this knowledge the scheduler needs detailed information about the cpu layout and it needs to intelligently act on that information.


Other non types of non-uniformity are shared system bus or memory controller links, hyper-threaded or symmetric multi-threaded cores, etc. All of these factors stack up to mean simply picking the most idle cpu is no longer an effective solution. For example, if a thread has affinity for one cpu and it's not available, it is sensible to pick another cpu that shares cache with the desired cpu. It's also important to balance load across system bus links and caches not just processors.

Optimizing for these characteristics is not a novel idea. Linux and Solaris both make some attempts to do so. I have not analyzed them in depth but I have noticed that they are both fairly static approaches requiring changes for new architectures or missing opportunities to optimize odd ones such as intel's initial quad core (two sets of dualcore cpus with a large l2 each but a shared system bus). ULE even had some primitive improvements to optimize for HTT. However, my new solution is very dynamic, allowing the machine dependent code to describe arbitrary topographies with slightly abstracted levels of sharing.

The basic datastructure is a tree that describes the relationships between cpus. What resource they share and which cpus are in the set. An example tree might have a root that describes 4 sockets which share nothing (independent bus links), with another layer describing a package with an L3, and another describing a par of cores within that package sharing an L2. Yet another layer may then describe 4 SMT threads per-core. Most systems are actually less complex and require only one or two levels in the tree which reduces algorithm cost.

When searching for a cpu with affinity the scheduler will walk the tree backwards from the last cpu scheduled to the highest level which the thread has affinity for. It then recursively evaluates the sub-tree to find the most idle match with the best affinity. To find an idle cpu, we scan the whole tree finding the least loaded CPU on the least loaded path through the tree. This balances load across tree levels and hence all cpu resources.

The periodic load balancer now recursively iterates the tree, load balancing every level. A search routine simultaneously finds the most and least loaded core via each path and rectifies their loads. The idle time load balancer which runs when a cpu runs out of work will scan starting from the nearest cpu outward to pick the best cpu to steal a thread from.

The majority of the algorithms are quite generic, however, I may implement some special casing for SMT/HTT as there really is a much stronger disincentive to scheduling these cores if others are available unless there is significant cache overlap between threads. When there is cache overlap between threads the scheduler can now place them near-by each other in the topology to decrease cache coherency messages that must be broadcast off package.

So after all that, how much does it help? Some charts:

http://people.freebsd.org/~kris/scaling/pgsql-16cpu.png
http://people.freebsd.org/~kris/scaling/mysql-16cpu.png

These are from a 16core 4x4 xeon machine. The pgsql graph has a lot of lines but you're interested in ule + topo vs 16 cores, all active. mysql is a little more straightforward. Interestingly it scales well on 8 cpus but runs into terrible user-land contention on 16. I'm not sure if this is running with adaptive pthreads mutexes or not.

Anyway, the patch is still young yet and it's performing very well on this very asymmetric machine while not hindering others. Expect to see this in 8.0 and maybe backported for 7.1 to alleviate the poor scheduling behavior that all those of you with quad quad core machines are experiencing. ;)


  • Post a new comment

    Error

    Your reply will be screened

    Your IP address will be recorded 

  • 88 comments
Previous
← Ctrl← Alt
  • 1
  • 2
Next
Ctrl →Alt →

[info]danfe

January 25 2008, 13:30:35 UTC 4 years ago

Looks quite promising, and impressive! Keep it up, Jeff.

[info]alvabonnano

August 6 2008, 04:09:05 UTC 3 years ago

Keep it up. . Jeff Horner May A compelling idea, and an impressive & inspiring set of work. Your galleries always impress.

[info]gregharton

3 years ago

[info]samgoulet

3 years ago

[info]royaltugit

3 years ago

[info]coybertran

3 years ago

[info]bryanpring

3 years ago

[info]lvchanel

1 year ago

[info]tylerkuns

3 years ago

[info]leonelsyms

3 years ago

[info]julietully

3 years ago

[info]tutanhamon

January 25 2008, 14:17:48 UTC 4 years ago

What's wrong with MySQL after 9-10 threads?

Anonymous

January 25 2008, 16:02:39 UTC 4 years ago

Is the problem really within the scheduler?

So what does the `SIGPIPE' patch actually do?

[info]jeffr_tech

4 years ago

[info]jeffr_tech

4 years ago

[info]tutanhamon

4 years ago

[info]jeffr_tech

4 years ago

[info]santosroom

3 years ago

[info]saragyvuj

3 years ago

[info]kimoletu

3 years ago

Anonymous

January 26 2008, 03:08:17 UTC 4 years ago

Linux sched domains

Linux has actually had an arbitrary tree based topology (actually it doesn't even have to be a tree, it can be more general if the arch code wants to set that up) for quite some years now.

It is flexible enough to handle everything from SMT to multiple levels of NUMA and describe characteristics such as shared resources and power consumption effects, target CPU distribution fairness levels etc.

The data structure is completely dynamic and can be (and is) changed at runtime (eg. during CPU hotplug).

[info]jeffr_tech

January 27 2008, 23:51:04 UTC 4 years ago

Re: Linux sched domains

This isn't quite true according to my reading of the code. It expresses specific levels and the description can have only a few specific levels.

For example, when CONFIG_SCHED_MC is enabled there is a 'cpu_coregroup_map' and with SMT there is a 'cpu_sibling_map'. So you can't express something like the intel quad core which is two dual cores on one chip. With the 4 cores sharing some resources and the two pairs sharing others.

Also, it really only takes the current level of the group into consideration when balancing. It doesn't look at the full path. There are more examples but perhaps I shouldn't always give away all of my tricks. ;)

Anonymous

4 years ago

[info]jeffr_tech

4 years ago

Anonymous

4 years ago

[info]jeffr_tech

4 years ago

[info]freegames99

September 27 2008, 07:51:18 UTC 3 years ago

Jeff Horner May A compelling idea, and an impressive & inspiring set of work. Your galleries always impress.

[info]bozuk

June 28 2009, 00:00:30 UTC 2 years ago

dawd

dawdaddawdawdwadawdawdaw

[info]sence1

March 12 2009, 22:04:20 UTC 3 years ago

Koxp, Koxp 1726, Koxp Merkezi

Koxp

[info]bozuk

June 28 2009, 00:00:50 UTC 2 years ago

dawdada

Yeni porno izleme sitesi www.gomtube.net -

[info]sence1

March 18 2009, 11:20:06 UTC 3 years ago

Oyun Download
Online Games

[info]bozuk

June 28 2009, 00:01:28 UTC 2 years ago

Thankss

En Kral porno izle. -

Liseli porno izle -

[info]sence1

March 18 2009, 11:20:41 UTC 3 years ago

laptop notebook

[info]sence1

March 19 2009, 01:43:29 UTC 3 years ago

Good news auto blog laptop notebook

Oyun Download
Online Games
Emin Ergin

[info]sence1

3 years ago

[info]bozuk

2 years ago

[info]sence1

March 29 2009, 23:57:20 UTC 3 years ago

Good e book store options Kobi

[info]bozuk

June 28 2009, 00:01:58 UTC 2 years ago

Supper :)


Bedava porno seyret -

Kesintisiz sikiş izle -

Deleted comment

[info]bilmiyorum1

June 18 2009, 22:08:19 UTC 2 years ago

Good my dream teacher

Porno izle

[info]bozuk

2 years ago

[info]itsetfcono

June 21 2009, 15:04:48 UTC 2 years ago

http://letitbitsexlg.blogspot.com/
http://ibanymaszyiaww.blogspot.com/
http://newdatingasitefg.blogspot.com/
http://russianhomesexai.blogspot.com/
http://amateursexclipsce.blogspot.com/
http://anallargedo.blogspot.com/
http://togetthedatingxf.blogspot.com/
http://penkmaveishaxd.blogspot.com/
http://feszengsupiridop.blogspot.com/
http://fotkisexonabeachwf.blogspot.com/
http://recorddatinghq.blogspot.com/
http://5datingge.blogspot.com/
http://fervoradatinggp.blogspot.com/
http://eroticminigamestd.blogspot.com/
http://adatingisanuddereh.blogspot.com/
http://criomnoeveklx.blogspot.com/
http://toreadanincestsg.blogspot.com/
http://depubegohbm.blogspot.com/
http://heysexrollerswi.blogspot.com/
http://eroticstoriesrumu.blogspot.com/
http://heysaunasss.blogspot.com/
http://photoofwildsexsg.blogspot.com/
http://smolensksexql.blogspot.com/
http://supersexfilmgb.blogspot.com/
http://datingverythickql.blogspot.com/
http://videotolooksexnowrp.blogspot.com/
http://szorsbyaurnkhq.blogspot.com/
http://librarysexqo.blogspot.com/
http://wizseesaoavj.blogspot.com/
http://bryanskdatingvs.blogspot.com/
http://adatingisafewshotskw.blogspot.com/
http://sexwithgirlstobr.blogspot.com/
http://msexqu.blogspot.com/
http://messagesexgz.blogspot.com/
http://anadatingofpot.blogspot.com/
http://datingthegipsyeu.blogspot.com/
http://sexgirlwithamanll.blogspot.com/
http://masturbaterunc.blogspot.com/
http://observingofsexyl.blogspot.com/
http://15xdatingis.blogspot.com/
http://seesridnhsg.blogspot.com/
http://sexofdreamruco.blogspot.com/
http://criomnoevekvt.blogspot.com/
http://mothergb.blogspot.com/
http://trakhgirlsat.blogspot.com/
http://sexpupilssm.blogspot.com/
http://youngdatingio.blogspot.com/
http://begfeszengysof.blogspot.com/
http://toseeadatingfilmzo.blogspot.com/
http://interactivesexhd.blogspot.com/
http://datingsexviewinguv.blogspot.com/
http://datingofshopysanktzh.blogspot.com/
http://recorddatingee.blogspot.com/
http://roomssexashopqv.blogspot.com/
http://datingofvideofz.blogspot.com/
http://sexisinaskirtxm.blogspot.com/
http://aphotoisdatingfilmsgj.blogspot.com/
http://sexisvisiblebl.blogspot.com/
http://testsaboutsexil.blogspot.com/
http://datingonwapwn.blogspot.com/
http://datinginspermef.blogspot.com/
http://frightfuladatingsq.blogspot.com/
http://ofvideojq.blogspot.com/
http://bubblihderzyvwrn.blogspot.com/
http://datingrollerssexdx.blogspot.com/
http://lifeitissexbp.blogspot.com/
http://seuoligoyspumh.blogspot.com/
http://maveisgriozirczivh.blogspot.com/
http://gamesaboutsexkw.blogspot.com/
http://toreadadatingtj.blogspot.com/
http://mumssexcf.blogspot.com/
http://sexduringalessongf.blogspot.com/
http://russianmaturedatingnw.blogspot.com/
http://onemihordwamsu.blogspot.com/
http://datinginspermbh.blogspot.com/
http://virginsaresexmr.blogspot.com/
http://funnywfrexuru.blogspot.com/
http://virginsaresexbu.blogspot.com/
http://youthdatingwz.blogspot.com/
http://seszirsmollyul.blogspot.com/
http://littleboysinsexsu.blogspot.com/
http://multikiporevoinforl.blogspot.com/
http://sexisahorseoh.blogspot.com/
http://datingofnakedauntskk.blogspot.com/
http://heyfilmon-lineuc.blogspot.com/
http://anoilclothissexcu.blogspot.com/
http://datingthreeononejd.blogspot.com/
http://russianeroticstoryvw.blogspot.com/
http://thegoddessofsexat.blogspot.com/
http://vesezneciriwl.blogspot.com/
http://yaungqmoszurbccrw.blogspot.com/
http://datingof40ladiesqx.blogspot.com/
http://sexwithwomenlm.blogspot.com/
http://datingwapdom2rufe.blogspot.com/
http://zoofilkidatingcn.blogspot.com/
http://ropidlisbeonuwnby.blogspot.com/
http://hordcarimbisziygl.blogspot.com/
http://young16sexlc.blogspot.com/
http://beslatnoedatingel.blogspot.com/
http://datingofvideoofdom2jd.blogspot.com/

[info]istiyormus

June 24 2009, 21:26:10 UTC 2 years ago

thanks

thanks for sharing my friend.

devlet

[info]recepfatih

March 22 2011, 14:24:47 UTC 1 year ago

Re: thanks

thanks for sharing my friend. porno

[info]itsetfcono

July 12 2009, 13:13:46 UTC 2 years ago

http://pinkteenunuc.forum24.ru
http://bestcockevux.forum24.ru
http://wetglamourowas.forum24.ru
http://mostblowjobunur.forum24.ru
http://blueanimunaz.forum24.ru
http://bigmoviesurew.forum24.ru
http://freelesbonoc.forum24.ru
http://redtoysozom.forum24.ru
http://redgirlsezov.forum24.ru
http://sweetgrouporov.forum24.ru
http://freecumaxem.forum24.ru
http://redclipsosov.forum24.ru
http://sexykissecar.forum24.ru
http://crazyladiesomaw.forum24.ru
http://badsexesan.forum24.ru
http://pinkassosar.forum24.ru
http://niceblowjobowar.forum24.ru
http://youngbdsmosem.forum24.ru
http://bigclipsawus.forum24.ru
http://deeppicuruw.forum24.ru
http://crazyoralozox.forum24.ru
http://smallteenanov.forum24.ru
http://youngcelebsesun.forum24.ru
http://freeanalocom.forum24.ru
http://deepmovozuv.forum24.ru
http://blacksexomas.forum24.ru
http://wetpornezex.forum24.ru
http://pinkgroupevez.forum24.ru
http://naiveadultawen.forum24.ru
http://bestladiesemer.forum24.ru
http://wetblowjobuvaz.forum24.ru
http://pinkanimener.forum24.ru
http://mostspermaxum.forum24.ru
http://hardcumezur.forum24.ru
http://hotclipsamuc.forum24.ru
http://crazygirlsenuc.forum24.ru
http://bluesexesuv.forum24.ru
http://mostblowjobenaz.forum24.ru
http://newanimusom.forum24.ru
http://hardasianomos.forum24.ru
http://nicefacialuzun.forum24.ru
http://smallcockevex.forum24.ru
http://blackblowjobamos.forum24.ru
http://sweetlesbenox.forum24.ru
http://newthroatuvur.forum24.ru
http://sexysexavus.forum24.ru
http://hotdickaxos.forum24.ru
http://newgirlsoxow.forum24.ru
http://wetclipsesas.forum24.ru
http://bestkissenuv.forum24.ru
http://mostfacialarun.forum24.ru
http://sexycreamumuw.forum24.ru
http://rapeddickonac.forum24.ru
http://mostcelebsenez.forum24.ru
http://deepmoviesucav.forum24.ru
http://wetanimusez.forum24.ru
http://badmoviesexux.forum24.ru
http://hotmovosow.forum24.ru
http://redbdsmuzem.forum24.ru
http://newstaromor.forum24.ru
http://mostglamoureven.forum24.ru
http://hotblowjobovec.forum24.ru
http://hardlesbasoc.forum24.ru
http://freeassunes.forum24.ru
http://wetdickacon.forum24.ru
http://biganalemen.forum24.ru
http://bluepornozax.forum24.ru
http://wetcelebsezox.forum24.ru
http://bestfacialarem.forum24.ru
http://naiveglamourevow.forum24.ru
http://smallcockeruz.forum24.ru
http://smallstaravaz.forum24.ru
http://sweetclipsevav.forum24.ru
http://freestaraxuv.forum24.ru
http://hardlesbowur.forum24.ru
http://freecelebsawez.forum24.ru
http://naiveasianezew.forum24.ru
http://niceadultezem.forum24.ru
http://hotanaluwaw.forum24.ru
http://sweetmovexec.forum24.ru
http://pinkphotososer.forum24.ru
http://redtitsonox.forum24.ru
http://wetcumaxen.forum24.ru
http://smallstarenuw.forum24.ru
http://youngblowjobuxoz.forum24.ru
http://biggirlsovuc.forum24.ru
http://newasianazoz.forum24.ru
http://blueadultavex.forum24.ru
http://smallfacialecun.forum24.ru
http://wetcreamenas.forum24.ru
http://rapedkissoxew.forum24.ru
http://bestteenevem.forum24.ru
http://mostspermaxov.forum24.ru
http://rapedsexuwus.forum24.ru
http://blackpornesom.forum24.ru
http://bluecreameras.forum24.ru
http://mosttitsazox.forum24.ru
http://freeadultaner.forum24.ru
http://bestbdsmever.forum24.ru
http://mostcockaxav.forum24.ru
http://hardstarasec.forum24.ru
http://badcreamuwuc.forum24.ru
http://rapedoralunov.forum24.ru
http://niceanalanus.forum24.ru
http://freeteenuzos.forum24.ru
http://hardcelebsamox.forum24.ru
http://sexyphotosazan.forum24.ru
http://freetitsaxuv.forum24.ru
http://mostmovener.forum24.ru
http://newpornecax.forum24.ru
http://deepglamourevos.forum24.ru
http://smallkissuzuc.forum24.ru
http://youngmovezuz.forum24.ru
http://rapedmovuron.forum24.ru
http://mostlesbuxev.forum24.ru

[info]mesut12

July 18 2009, 06:23:10 UTC 2 years ago

Good on your

Lida

[info]mesut12

July 18 2009, 15:05:00 UTC 2 years ago

Thanks a lot

Biber hapi
Biber hapi
fx15

[info]itsetfcono

July 21 2009, 09:34:24 UTC 2 years ago

http://bluedickaram.forum24.ru
http://wetasianevov.forum24.ru
http://niceanimezos.forum24.ru
http://hotclipsuwoz.forum24.ru
http://sexygroupones.forum24.ru
http://sexyanimaxum.forum24.ru
http://pinkfacialasoz.forum24.ru
http://mostblowjoborer.forum24.ru
http://hardanalowur.forum24.ru
http://hotthroatuwus.forum24.ru
http://blueladiesuzar.forum24.ru
http://blackglamouranuz.forum24.ru
http://wetstaruser.forum24.ru
http://rapedtoysamom.forum24.ru
http://youngasianowaz.forum24.ru
http://sexythroatonas.forum24.ru
http://blackcumeses.forum24.ru
http://youngpicomer.forum24.ru
http://rapedcelebsuson.forum24.ru
http://smallfacialuvow.forum24.ru
http://blackmovunez.forum24.ru
http://naivepornosow.forum24.ru
http://wetcelebserev.forum24.ru
http://bestmoviesacaz.forum24.ru
http://blueadultavac.forum24.ru
http://wetfacialezov.forum24.ru
http://bestpicunew.forum24.ru
http://mostspermumuc.forum24.ru
http://sweetpornezar.forum24.ru
http://sexygroupazax.forum24.ru
http://hardglamourorev.forum24.ru
http://hotcreamonom.forum24.ru
http://naivesexuvoz.forum24.ru
http://youngtitsuzex.forum24.ru
http://hotthroateruw.forum24.ru
http://crazythroatesaw.forum24.ru
http://besttoysamuv.forum24.ru
http://hardlesbozoc.forum24.ru
http://sexypornonaz.forum24.ru
http://bigglamoururac.forum24.ru
http://freecelebsavaz.forum24.ru
http://mostasianazas.forum24.ru
http://bluegirlsacec.forum24.ru
http://younggirlsuvas.forum24.ru
http://hotasianusac.forum24.ru
http://redstaruser.forum24.ru
http://naiveoraleros.forum24.ru
http://bestlesbocos.forum24.ru
http://reddickacos.forum24.ru
http://hardcockeres.forum24.ru
http://baddickeraw.forum24.ru
http://rapedmoviesuzux.forum24.ru
http://bestladiesucon.forum24.ru
http://redglamouraces.forum24.ru
http://wetcockevuz.forum24.ru
http://sexycockarun.forum24.ru
http://bigtitsunar.forum24.ru
http://badladiesazur.forum24.ru
http://sexyblowjobozar.forum24.ru
http://rapedbdsmunur.forum24.ru
http://smallasianunov.forum24.ru
http://blackanalaxaw.forum24.ru
http://hardpornazam.forum24.ru
http://sexypicezor.forum24.ru
http://blackclipsosax.forum24.ru
http://youngcreamecev.forum24.ru
http://hotassuxev.forum24.ru
http://newassevos.forum24.ru
http://youngblowjoboren.forum24.ru
http://rapedphotosuzur.forum24.ru
http://wetcelebsazoc.forum24.ru
http://pinkfacialunas.forum24.ru
http://mostkissuvuz.forum24.ru
http://redadultuxum.forum24.ru
http://naiveadultoxux.forum24.ru
http://bluetitsesor.forum24.ru
http://wettoysavoc.forum24.ru
http://badgirlsunaz.forum24.ru
http://blackphotosoxav.forum24.ru
http://reddickexav.forum24.ru
http://newasianexuz.forum24.ru
http://mostbdsmemor.forum24.ru
http://deepgroupesex.forum24.ru
http://nicemovawec.forum24.ru
http://bigmovuwev.forum24.ru
http://sweetpornanew.forum24.ru
http://hotstaroror.forum24.ru
http://sweetdickerac.forum24.ru
http://rapedmoviesaser.forum24.ru
http://smallanalaxam.forum24.ru
http://freeclipsewav.forum24.ru
http://hardblowjobenux.forum24.ru
http://freeanimexuz.forum24.ru
http://naiveclipsurox.forum24.ru
http://youngspermenuc.forum24.ru
http://hotsexewuc.forum24.ru
http://sweetcumasov.forum24.ru
http://rapedgroupunez.forum24.ru
http://pinkteenewuz.forum24.ru
http://niceclipsevon.forum24.ru

[info]mesut12

July 22 2009, 14:34:49 UTC 2 years ago

Good on your


Acı çehre
yılan yağı
yılan yağı

[info]yj2133011

November 30 2010, 13:05:41 UTC 1 year ago

Some brides also Halter Taffeta Prom DressHalter Taffeta Prom Dress wear boots it? Quite exceptional, very Hard Tulle Wedding PetticoatHard Tulle Wedding Petticoat personal. Take a long drag a short veil wedding Hard Tulle Wedding PetticoatHard Tulle Wedding Petticoat dress? Long dress with long veil in fact delay no sense of hierarchy, it is Hard Tulle Wedding PetticoatHard Tulle Wedding Petticoat best to take a short veil, watching from the back looks better.

[info]replicalvbags

December 9 2010, 01:28:56 UTC 1 year ago

replicabags

Celine handbags
Chloe handbags
Coach handbags
Previous
← Ctrl← Alt
  • 1
  • 2
Next
Ctrl →Alt →
Create an Account
Forgot your login or password?
Facebook Twitter More login options
English • Español • Deutsch • Русский…