Parallel - modrpc/info GitHub Wiki
- wikipedia: https://en.wikipedia.org/wiki/Work_stealing
- scheduling strategy for:
- dynamically threaded computation, one that can spawn new threads of execution
- statically multithreaded computer
- fixed number of processors (or cores)
- each processor has a queue of work items to perform -- on spawning of a thread in one of its work item, it puts to its queue
- when a processor has finished working and has a empty queue, it steals work item from other processor
- typically, a thread itself has the scheduler inside
- alternative to work stealing
- when a thread (work item) is spawned, it is scheduled to the (final) processor on its creation time
- Unlike work stealing, process migration (i.e. workload balancing) may be needed
- wikipedia: https://en.wikipedia.org/wiki/Fork-join_model
- fork: thread creation
- join: this is about how control merges at one point (rather than data merging)
- MapReduce is based on fork-join pattern
- D. Lea. Java Fork/Join Framework
- wikipedia: https://en.wikipedia.org/wiki/Memory_barrier
- Why multi-core?
- rather than using silicon area to increase single-threaded performance (speculation, branch prediction, etc.), use it to add additional core with a potential to do twice the amount of work
- A computer consists of processors (= chip = socket)
- A processor can contain multiple cores
- A core is control + datapath
- A core can contain multiple virtual CPUs (= HW thread = logical CPU = strand = hyperthread)
- virtual CPUs are not physically countable but, to OS, they are entities where work can be scheduled
- e.g. Intel hyperthreadding = 2 HW threads per core
- Allows multiple instructions in flight at the same time
- One instruction finished in one cycle
- Allows faster clock (shorter critical path by inserting pipeline registration)
- Execute multiple instructions per cycle
- e.g. two pipelines, each of which can execute one instruction every cycle