Difference between revisions of "Computer task switching from an analogy perspective"

From Helpful
Jump to: navigation, search
m
m
 
Line 1: Line 1:
 
{{stub}}
 
{{stub}}
  
a.k.a. '''"but how many cores do I make this program use?"'''  
+
a.k.a. '''"but how many cores do I make this program use?"''' or "what's this about MPIs and threads?"
 
+
...or "what's this about MPIs and threads?"
+
  
  
 
===Analogies===
 
===Analogies===
 
<!--
 
<!--
People's eyes glaze over when you tell them that you should set MPI to half the amount of CPU cores because HyperThreading means task will contend for the FPUs which are shared between cores, so you should think in physical rather than virtual cores - and threads-per-process to 2 at least on platter disk because contending for their spins (but IOPS is an imperfect idea) is likely to make things worse due to seek overhead, though this is much less relevant when you have SSDs or have application-tweaked readahead, though cache contention and memory saturation can also make or break some of that, and that can work out differently on server boards because of local versus QPI-accessed memory, and last but not least the relatively localized caches.
+
When you tell people you should set that MPI field to half the amount of CPU cores because HyperThreading means tasks will contend for the FPUs which are shared between HT cores, so you should think in physical rather than virtual cores - and threads-per-process to 2 at least on platter disk because contending for their spins (but IOPS is an imperfect idea) is likely to make things worse due to seek overhead, though this is much less relevant when you have SSDs or have application-tweaked readahead, though cache contention and memory saturation can also make or break some of that, and delays can work out differently on Xeons boards because of local-versus-QPI-accessed memory, and last but not least the relatively localized CPU caches.
  
And rightly so. No one wants to think about all that.
+
...then people's eyes glaze over. And rightly so. No one wants to think about all that.
 
Just to generally do the right thing.
 
Just to generally do the right thing.
  
Line 19: Line 17:
 
Soooo, for a moment, think back to the first computers, which were a room full of people.
 
Soooo, for a moment, think back to the first computers, which were a room full of people.
  
The pragmatic side to that allows for various decent analogy of various details.
+
The pragmatic side to that allows for a decent analogy of various details.
 
(And yes, we can twist and break the analogy, and certainly will)
 
(And yes, we can twist and break the analogy, and certainly will)
  
  
  
 +
The computer is analogous to a building, with work rooms, archive rooms, hallways with people carting around information, etc.
  
 
The '''CPU''' as a whole is analogous to a floor of people and rooms they can use.
 
The '''CPU''' as a whole is analogous to a floor of people and rooms they can use.
 
: In broad terms you don't need to know exactly how many people there are and what they do
 
: In broad terms you don't need to know exactly how many people there are and what they do
: ...though sometimes knowing will helps split up a task better
+
: ...though sometimes knowing will often help split up a task better
  
  
Line 35: Line 34:
  
 
A '''process''' is like a single project's ledger with overall details, instructions, and intermediate work.
 
A '''process''' is like a single project's ledger with overall details, instructions, and intermediate work.
 +
: a person can switch between them, because the information and work to be done on it is fully described
  
  
 
'''Multi-threading''' is the case where that ledger has multiple,
 
'''Multi-threading''' is the case where that ledger has multiple,
 
entirely-distinct tasks, each with its own progress.  
 
entirely-distinct tasks, each with its own progress.  
Say, one task is walking to a warehouse to to do inventory, another is to do the balance, etc.
+
Say one task is walking to a warehouse to to do inventory, another is to do the balance, etc.
 
Sometimes you'll want to peek at another task, but most of the work is entirely your own.
 
Sometimes you'll want to peek at another task, but most of the work is entirely your own.
  
And when one task is held up by something, a person could continue with another.  
+
And when one task is held up by something, a person could continue with another.
 +
For example, you can tell someone to fetch something from then warehouse,
 +
and instead of waiting for it to continue the same takes, do another task
 +
until they return.
  
  
'''Multiprocessing''' is splitting tasks into multiple ledgers, so that involving multiple people is easier.
 
  
Often done when that larger goal is pretty easy to chunk up,  
+
'''Multiprocessing''' is splitting tasks into multiple ledgers,
and often because it lessens the need for people to talk to others before they can continue.
+
so that involving multiple people is easier.
  
When (and only when) it's easy to split up, this makes it a lot easier to manage.
+
Only really done when it's practically easy to split into smaller chunks
 +
of independent and non-redundant work,  
 +
because that means people don't wait on each other and don't waste man-hours.
  
 
+
In many real-world cases most tasks they do is at least a ''little'' entangled,
In many real-world cases all the different tasks they do is at least a entangled,
+
 
meaning that either you you must tell them to continually communicate what they are doing,  
 
meaning that either you you must tell them to continually communicate what they are doing,  
and/or write in the same single ledger, or copy it.  
+
copy the part of the ledger, or ''maybe'' write in the same ledger.
  
Exactly how (you decribe that) that communication / use of shared notes will work,
+
Exactly how (you decribe that) that communication / sharing
will have an effect on how efficient they can work,  
+
will have an effect on how efficient they can work,
 
and on possible mistakes made (e.g. by not knowing what the other was doing, on having old information).
 
and on possible mistakes made (e.g. by not knowing what the other was doing, on having old information).
 
Sometimes the extra management gives very little benefit, and is not worth it.
 
Sometimes the extra management gives very little benefit, and is not worth it.
Line 64: Line 67:
  
  
'''Disk''' is like a document warehouse nextdoor.
+
'''Disk''' is like a document warehouse next door.
Large amounts of space for long-term storage, but it takes a while to move things to or from,
+
Large amounts of space for long-term storage,
 +
but it takes a while to move things to or from,
 
so you use it for things you want to keep, but don't frequently need.
 
so you use it for things you want to keep, but don't frequently need.
  
  
'''Memory''' could be seen as your desk and personal cupboard next to it,  
+
'''Memory''' could be seen as your desk and personal cabinet next to it,  
 
that you actively need to work on a project,
 
that you actively need to work on a project,
 
say for books and articles and yesterday's notes.
 
say for books and articles and yesterday's notes.
  
As long as there's ''enough'' to work in, you don't care much.
+
As long as there's ''enough'' to work in, you don't care much, and you can
Though if other people took all the space (their desk starts threatening to take over yours),
+
share it if you need to.
then you suddenly spend much of your time shoving things into a the warehouse,
+
 
 +
Though if all such cabinets are full and you can't do much about yours (and can't really touch others anyway),
 +
then the only solution is to spend more of your time shoving only-slightly-old things into a the warehouse,
 
and getting them back (see also [[swapping]]).
 
and getting them back (see also [[swapping]]).
  
If you have a ridiculous shortage of space (and/or are continuously told by respective bosses to ''no, work on their thing right now''. No wait that. No wait that.), you would spend almost all your time waiting on the warehouse and barely get any actual work done (see also [[trashing]])
+
If you have a ridiculous shortage of space (and/or are told every five minutes by respective bosses to ''no, work on their thing right now. No wait that. No wait that.''), you would spend ''most'' of your time waiting on the warehouse and barely get any actual work done (see also [[trashing]]).
  
  
 
'''CPU Registers''' are like the top page on your notebook.
 
'''CPU Registers''' are like the top page on your notebook.
Immediately available, but can't be large or it you start needing to make a complex index on it.
+
Immediately available, but can't be large or finding things in it starts getting slower.
  
  
  
  
'''IO''' can be seen as telling a librarian to find someone in that warehouse,
+
'''IO''' is needing anything that is ''elsewhere'' - an article from the library, emailed advice from a colleague, a request from your helpdesk. You request it from a librartian, since only they knew where they put it for you, and it blocks you from doing work on this project until it gets back/done.
since only they know where they put it for you.  
+
 
  
 
'''memory / IO throughput''' is like the size of the hallways.
 
'''memory / IO throughput''' is like the size of the hallways.
Can ten librarians pass each other with carts, or do they have to wait on each other?
+
Can ten librarians pass each other with carts, or is it so narrow that they have to wait on each other?
  
'''IO contention''' is like having too few librarians for all requests to happen within
 
sensible time, or too overly narrow hallways.
 
(regardless of whether you have enough room in the warehouse)
 
  
 +
'''IO contention''' is like overly narrow hallways in or to/from the warehouse,
 +
for all requests to happen within sensible time. (regardless of whether you have enough filing space in the warehouse)
  
 +
This can stop ''multiple'' people in their track, and can make the librarian spend even more of their time just walking around, and so less efficient as well.
  
'''Cacheing''' is like the librarian making copies of the most common/recent stuff and tacking it on a shared whiteboard in the room.
+
Your choices are to enlist more librarians (more disk systems) and considering IO (hallways) doing so,
 +
or someone at their front desk planning things like the same person for fetches near each other (clever IO scheduling),
 +
or to stop trying to force so many projects on so few librarians.
  
If this is typically required for your work, this lets you do your work faster than if it needs to be fetched all the time.
 
  
Not strictly necessary to have these copies, but it can help a lot.
 
  
Though you must care to keep it in sync with the thing in the warehouse, or you are doing nonsense.
 
(which is why you'ld always have the librarian do it for you)
 
  
Cacheing has value when you come back the next day to find them still there.
 
Whereas if you share your room with a lot of people doing distinct things, it's more likely it got thrown away.
 
  
 +
'''Cacheing''' is having copies of things you needed (or remembering things you calculated just for yourself), rather than always going to the source.
 +
 +
 +
'''Disk cache''' is basically the librarians keeping track of what's recently been requested a lot, and keeping photocopies of it to hand out - at least until a change to it is made.
 +
 +
If you know these scribbles are things that may change (e.g. not the value of pi, but certainly recent projections of whatnot)
 +
then you ''must'' care to throw it away when it is changed in the warehouse (cache invalidation).
 +
 +
This means '''CPU caches''' (L1, L2, L3) are more like whiteboards in your room that are kept updated by the librarian, because
 +
they much more easily know know when other people changed it.
 +
 +
Cacheing has value when you come multiple times, and on next day, and still find your useful information there.
 +
A whiteboard is only so large, so when your room is dealing with hundreds of ledgers, that whiteboard content will get dismissed for newer stuff much more quickly.
 +
 +
'''Cache contention''' is usually caused by having too many jobs, which means you run out of desk for the notes, they may be old, you spend more time managing them than using them, or throw them out a lot.
  
  
Line 116: Line 133:
  
 
'''HyperThreading''' is, hmmm, like a conjoined twin at a single desk.
 
'''HyperThreading''' is, hmmm, like a conjoined twin at a single desk.
They work well together when they work mostly independently, in less space than two people with two desks,
+
They work well together when they work mostly independently,
because they know how the other does things and cooperates well.
+
in less space than two people with two desks and two cupboards,
 +
because they know how the other does things and cooperate well.
  
Yet when they e.g. share only one calculator, and both need it for all of their work,
+
Yet when they e.g. share only one calculator,
they won't work any faster than a single person. (HyperThreaded cores often share an FPU)
+
and both need it for all of their work, then they won't work ''any'' faster than a single person.
 +
(HyperThreaded cores often share an FPU)
  
  
  
'''The scheduler''' is the person who hands out the project ledger everyday - and may  
+
'''The scheduler''' is the person who hands out project ledger,
swap them around during the day if that seems more efficient.
+
and may swap them around during the day as people finish work.
  
 
Few people need to care about details of what they do, as long as they do it well.
 
Few people need to care about details of what they do, as long as they do it well.
Line 134: Line 153:
 
More specific terms
 
More specific terms
  
'''MPI''' is a scheduler that can be told to be aware of the size of hallways,
+
'''MPI''' is a scheduler that ''can'' be told to be aware of different buildings,
the different buildings, the paths between them, etc. to try to minimize people
+
the size of their hallways, the paths between them, etc. to try to minimize people
 
running around rather than doing work.
 
running around rather than doing work.
  
 
The idea of having a person capable of this planning is nice,
 
The idea of having a person capable of this planning is nice,
though only really has value when there is a lot of stuff ''to'' be carted around in nontrivial ways.
+
though only really has value when there is a lot of stuff ''to''
 +
be carted around in nontrivial ways ''and'' all that information is precise.
  
 +
It's often used much more roughly than that.
  
SMP is like putting all the cupboards (memory) in the center to be shared.
 
  
NUMA is like having the cupboards distributed between people/desks.
+
 
 +
 
 +
 
 +
'''SMP''' is like putting all the cupboards (memory) in the center to be shared.
 +
 
 +
'''NUMA''' is like having the cupboards distributed between people/desks.
 
This means you can get to your own a little faster (no management to its use),
 
This means you can get to your own a little faster (no management to its use),
 
but to most other memory a little slower.
 
but to most other memory a little slower.
  
  
Shared memory is sharing information multiple people need in a cupboard.  
+
'''Shared memory''' is sharing information multiple people need in a cupboard.  
 
You better have some conventions or protocols to when you change things,
 
You better have some conventions or protocols to when you change things,
 
or will make mistakes, unknowingly.
 
or will make mistakes, unknowingly.
Line 159: Line 184:
  
 
<!--
 
<!--
---
 
  
  
Line 166: Line 190:
 
'''Threading''' is the funny one, both in analogy and in computing practive.
 
'''Threading''' is the funny one, both in analogy and in computing practive.
  
Consider that you ''could'' throw ten projects at a researcher and tell them to split their time between them. If each it all brainwork, you can expect each project to go at 1/10th speed.
+
Consider that you ''could'' throw ten projects at a researcher (processes at a CPU)
 +
and tell them to split their time between them.
 +
If each it all brainwork, you can expect each project to go at close to 1/10th speed.
  
A '''thread''' is a distinct-enough task within a project. Say your instructons are doing statistics on ten projects, then tabulate them, and independently sometimes clear your desk of what you don't need anymore. When you don't have all the results yet, you can still do some of the other parts.
+
A '''thread''' is a distinct-enough task ''within'' a project.
 +
Say your instructions are doing statistics on ten projects, then tabulate them, and independently sometimes clear your desk of what you don't need anymore. When you don't have all the results yet, you can still do some of the other parts.
  
 
In other words, threading makes sense when one thing can be held up, and there is typically something else to do. (Which in pure hard calculation on a large chunk of data is regularly ''not'' the case)  
 
In other words, threading makes sense when one thing can be held up, and there is typically something else to do. (Which in pure hard calculation on a large chunk of data is regularly ''not'' the case)  
Line 174: Line 201:
  
  
'''Memory''' could be seen as the physical space you need to set up a project, for the books and articles and instruments.
 
  
As long as there's ''enough'' to work in, you don't care at all.
+
Synchronous IO is twiddling thumbs until they get back.
If you get less than you objectively need, and you ''must'' manage, then you will suddenly spend much of your time shoving things into a corner and getting them back from said corner (see also [[swapping]], [[trashing]]).
+
Asynchronous IO is doing something else until they get back.
If you have a ridiculous shortage of space and are told to manage, you can barely work and probably quit your job.
+
(Single-threaded async IO is basically looking up every now and then whether they've returned. Using an IO thread is like relying on your scheduler to alert you)
  
'''Memory contention''' is like having enough room, but too few doors for all the people that need to get there.
 
  
 
+
IO being a fact of life is an argument for multitasking (multiprocessing or multithreading):
'''CPU caches''' (L1, L2, L3) are like scribbled notes on your desk, of things you knew were out there yet you had to look up in your books or at the library. You know what the notes mean, they are immediately available so sometimes make your immediate work ''much'' faster.
+
 
+
'''Cache contention''' is usually caused by having too many jobs, which means you run out of desk for the notes, they may be old, you spend more time managing them than using them, or throw them out a lot.
+
 
+
 
+
 
+
'''IO''' is like needing anything that is ''elsewhere'' - an article from the library, emailed advice from a colleague, a request from your helpdesk. It blocks you from doing science on this project until it gets back/done.
+
 
+
In the analogy, it's shouting for a librarian to go fetch it, because in most practice you could find another thread or process to work on while they do.
+
 
+
So IO being a fact of everyday life is an argument for multitasking (multiprocessing or multithreading):
+
 
: If all parts of your project are purely thinking, then assigning two projects only splits attention between them, and there is actually nothing to gain.
 
: If all parts of your project are purely thinking, then assigning two projects only splits attention between them, and there is actually nothing to gain.
 
: If one task would normally take a week and you assign two (and say 'be fair, spend equal time'), it means both projects get only half the time and ''both'' will be done in ''two'' weeks.
 
: If one task would normally take a week and you assign two (and say 'be fair, spend equal time'), it means both projects get only half the time and ''both'' will be done in ''two'' weeks.
Line 199: Line 213:
 
: ...but when a job involves IO (waiting around), then it can help to assign two projects to a researcher (processes to a core), because chances are that while doing the boring mechanical task of walking to the library for one project, you can think about the other.
 
: ...but when a job involves IO (waiting around), then it can help to assign two projects to a researcher (processes to a core), because chances are that while doing the boring mechanical task of walking to the library for one project, you can think about the other.
  
 
'''IO contention''' is like said library having only one librarian, and multiple people needing them at the same time.
 
 
This can stops ''multiple'' people in their track, and can make the librarian spend even more of their time just walking around, and so less efficient as well.
 
 
Your choices are to enlist more librarians (more disk systems),
 
or someone at their front desk planning things like the same person for fetches near each other (clever IO scheduling),
 
or to stop trying to force so many projects on so few librarians.
 
  
  
Line 212: Line 218:
 
'''The difference between multiprocessing and multithreading breaks the analogy a bit.'''
 
'''The difference between multiprocessing and multithreading breaks the analogy a bit.'''
  
You could say that '''multithreading''' is like having a well organized room - no more room than anyone else, but with many clearly designated jobs (some thinking, some doing). The whiteboard's there, the lab journal's there, a computer with bookmarks to all the articles you want.
+
You could say that '''multithreading''' is like having a ledger with parts that are through out well,
 +
e.g. have a slide-out page for the stuff you need for all tasks, so you can flip to another page and continue immediately
  
Going between tasks is relatively cheap
+
...and '''multiprocessing''' is more like having the same basic tasks handed to you all in separate ledgers,
(compared to coming into work a mess or a blank slate each day and having to clean up or set up)
+
without much consideration on how you can smoothly do both.
That researcher can think about one part while doing another (waiting for IO / the librarian)
+
  
How much this helps in practice depends primarily on how much time you would or would not waste.
+
The thing is that if little communication is necessary (e.g. most work is long stretches of dumb work),
If your job is all thinking, then it probably doesn't help at all.
+
then there may be almost no difference.
  
  
...and '''multiprocessing''' is more like having two separate rooms doing related and coordinated work, but that typically does not need to communicate so much.
 
  
Rote work they can do independently is put on more people so goes faster.
 
 
If it depends significantly on communication, particularly time-sensitive communication, it may get no added value over a single person.
 
 
 
 
'''Cacheing''' is analogous to coming into work as you left it -- rather than a shared room, or one used by other people while you were gone, where people put your stuff back into the library because it was in the way
 
 
If you needed your stuff a lot to do your work, having it nearer lets you work faster.
 
  
  
Line 281: Line 277:
  
  
 
+
-->
 
===Okay, so....===
 
===Okay, so....===
 
+
<!--
What does that mean, concretely, to answre '''"how many cores do I make this program use?"'''
+
What does that mean, concretely, to answer '''"how many cores do I make this program use?"'''
  
  
 
Mainly: '''saturate your cores, but avoid contention'''
 
Mainly: '''saturate your cores, but avoid contention'''
 
: assigning ''much'' more work than you can actually do at once can only cause more (disk and other IO, FPU, CPUcache, and/or memory) contention than necessary, and this ''may'' slow you more than you think
 
: assigning ''much'' more work than you can actually do at once can only cause more (disk and other IO, FPU, CPUcache, and/or memory) contention than necessary, and this ''may'' slow you more than you think
: a ''little'' more work (e.g. a few more processes than cores) can help your CPUs go to 100%, though
+
: when processes ''sometimes'' do some non-CPU work, then a ''little'' more work (e.g. a few more processes than cores) can help your CPUs go to 100%, though
  
  

Latest revision as of 14:38, 13 June 2019

This article/section is a stub — probably a pile of half-sorted notes, is not well-checked so may have incorrect bits. (Feel free to ignore, fix, or tell me)

a.k.a. "but how many cores do I make this program use?" or "what's this about MPIs and threads?"


Analogies

Okay, so....