How is parallelism on a single thread/core possible?

Question

Modern programming languages provide parallelism and concurrency mechanisms as first class citizens to their users. I understand how parallel algorithms are programmed and can well imagine how two threads on a multi-core CPU can run in parallel.

Yet, most of these platforms also support running parallel processes on a single thread.

• Do these processes really run in parallel?
• How, on an assembly level can two different routines be executed simultaneously on a single thread?

Answer 1

TLTR; : parallelism (in the sense of true simultanenous execution) on a single, non-hyperthreaded CPU core, is NOT possible.

---

Hardware (<- EDIT) Paralellism can be achieved at several levels. Ordered by decreasing granularity :

1. multi-host
2. multi-processor
3. multi-core
4. multi-threads ("Hyper-Threading", i.e. "HT") (EDIT: I voluntarity omit the case of vectorized compuations where several ALUs can be driven by the same core)

Your question relates to running two software threads in cases 3. (in case HT is unavailable / disabled) or 4.

• In both cases, the processes actually do NOT run in parallel. The user has an impression of simultaneity due to the extremely fast context switches performed at the CPU level, that tend to allocate, sequentially, the physical core (resp. thread) time to one or the other software thread

• In both cases, those routines are simply not executed simultaneously, but sequentially

The relative priority allocated to each of those 2 routines can be set on various OSes by the "Priority" you give to the process, that will be handled by the OS's scheduler, which in turn will allocate CPU time.

HTH.

To perform tests to better understand this topic, you may want to google "cpu affinity". This will let you run a two-threaded process on one physical single core of a multi-core CPU, and time the time taken by each of the threads, while modifying their priority, etc...

Answer 2

Yes, there is parallelism in each thread and you get it for free, no matter which programming language you use (although the amount of parallelism may vary).

It's called instruction-level parallelism. The details are quite complex and differ between different processor micro-architectures.

Computer Architecture: A Quantitative Approach is a brilliant book which includes a chapter on instruction-level parallelism and the book's examples teach how to think rationally about engineering.

Check out the following links for more information:

http://en.wikipedia.org/wiki/Superscalar

http://en.wikipedia.org/wiki/Instruction_pipelining

http://en.wikipedia.org/wiki/Out-of-order_execution