Linux numa evolution

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam 2

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://storage.pardot.com/6342/95370/lf_pub_top500report.pdf

http://upload.wikimedia.org/wikipedia/commons/e/e1/Linus_Torvalds,_2002,

_Australian_Linux_conference.jpg

UNIX Linux

3

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam 4

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

`diff -up`

https://www.kernel.org/doc/Documentation/SubmittingPatches (20.11.2014)

5

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam http://thread.gmane.org/gmane.linux.kernel/1392753 6

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://upload.wikimedia.org/wikipedia/commons/e/e1/Linus_Torvalds,_2002,_Australian_Linux_conference.jpg

…

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

https://www.kernel.org/doc/Documentation/development-process/2.Process, http://www.linuxfoundation.org/sites/main/files/publications/whowriteslinux.pdf

8

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

https://www.kernel.org/doc/Documentation/development-process/2.Process

“9

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam 10

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam 11

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam 12

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://en.wikipedia.org/wiki/Scheduling_%28computing%29

13

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://lwn.net/Articles/254445/

?

14

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam 15

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

✔

✘

https://www.cs.sfu.ca/~fedorova/papers/usenix-numa.pdf

16

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

✔

✔

✘

https://www.cs.sfu.ca/~fedorova/papers/asplos284-dashti.pdf

Traffic Imbalance

17

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

→

18

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam 19

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

…

20

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://lse.sourceforge.net/numa/topology_api/in-kernel/

21

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

asm/topology.h

int __cpu_to_node(int cpu);

int __memblk_to_node(int memblk);

unsigned long __node_to_cpu_mask(int node);

int __parent_node(int node); # /!\ supports hierarchies

http://lse.sourceforge.net/numa/topology_api/in-kernel/

22

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam 23

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

int __cpu_to_node(int cpu);

http://home.arcor.de/efocht/sched/

keep task

& mem on same node

24

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

⇒

L = local_node();

# regular load balancing as for multicore

# (O(1) scheduler):

balance_node(L);

N = most_loaded_node();

C = most_loaded_cpu(N);

if load(L) <= system_load()

steal_tasks_from_cpu(C);

http://home.arcor.de/efocht/sched/

25

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam 26

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://lwn.net/Articles/67005/

27

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

→

http://lwn.net/Articles/80911/

Node

Physical CPU

CPU0 CPU1

Physical CPU

CPU2 CPU3

Node Node Node

minimize cost

of moving task (& mem)

28

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

node node

node node

29

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

…

node

node node

node

node

node

30

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

…

node

node node

node

node

node

31

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

…

node

node node

node

node

node

32

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

…

33

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

?

34

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

…

mem

node

mem

node

35

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

…

mem

node

mem

node

36

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

…

mem

node

mem

node

37

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

…

mem mem

nodenode

38

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

…

mem

node

mem

node

39

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

…

mem

node

mem

node

40

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

…

mem

node

mem

node

41

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

⇒

http://lwn.net/Articles/486858/

42

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://lwn.net/Articles/486858/

mem follows task

43

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://lwn.net/Articles/486858/

task follows mem

44

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://lwn.net/Articles/486858/tasks w/ shared

mem on same node

45

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://lwn.net/Articles/488709/

46

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://lwn.net/Articles/488709/

memmem

nodenode

⚡

⚡⚡

47

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

Unless you're going to listen to feedback I give you, I'm going to completely stop reading your patches, I don't give a rats arse you work for the same company anymore. You're impossible to work with.

http://lwn.net/Articles/522093/

“48

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://lwn.net/Articles/522093/, http://lwn.net/Articles/524535/

49

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam 50

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://lwn.net/Articles/524977/, http://thread.gmane.org/gmane.linux.kernel/1392753

51

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam 52

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

autonuma

53

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

⚡

http://lwn.net/Articles/568870/scheduling: NUMA

and load balancing and groups

54

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://thread.gmane.org/gmane.linux.kernel/1631332

mem

node

mem

node

55

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://thread.gmane.org/gmane.linux.kernel/1631332

mem

node

mem

node

56

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://thread.gmane.org/gmane.linux.kernel/1631332

57

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam 58

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam 59

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://thread.gmane.org/gmane.linux.kernel/1808344

60

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

⇔

∃

http://thread.gmane.org/gmane.linux.kernel/1808344

node node

node node

61

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

⇔

http://thread.gmane.org/gmane.linux.kernel/1808344

backplanecontroller

node

backplanecontroller

backplanecontroller

backplane

node

node

node

node

node 62

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

…

http://lwn.net/Articles/591995/

63

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://lwn.net/Articles/591995/

64

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://lwn.net/Articles/591995/

65

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

http://lwn.net/Articles/591995/

node node

mem

NIC

DMA?IO

adapter

mem

66

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam 67

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam 68

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

Fredrik Teschke, Lukas Pirl seminar on NUMA, Hasso Plattner Institue, Potsdam

→ ≈ →

CPU

CPU

CPU CPU

CPU

node

node

node node

node