Consider the following very simple computer program:
for i = 1 to n:
y[i] = x[p[i]]
Here $x$ and $y$ are $n$-element arrays of bytes, and $p$ is an $n$-element array of words. Here $n$ is large, e.g., $n = 2^{31}$ (so that only a negligible fraction of the data fits in any kind of cache memory).
Assume that $p$ consists of random numbers, uniformly distributed between $1$ and $n$.
From the perspective of modern hardware, this should mean the following:
- reading $p[i]$ is cheap (sequential read)
- reading $x[p[i]]$ is very expensive (random reads; almost all reads are cache misses; we will have to fetch each individual byte from the main memory)
- writing $y[i]$ is cheap (sequential write).
And this is indeed what I am observing. The program is very slow in comparison with a program that does only sequential reads and writes. Great.
Now comes the question: how well does this program parallelise on modern multi-core platforms?
My hypothesis was that this program does not parallelise well. After all, the bottleneck is the main memory. A single core is already wasting most of its time just waiting for some data from the main memory.
However, this was not what I observed when I started experimenting with some algorithms where the bottleneck was this kind of operation!
I simply replaced the naive for-loop with an OpenMP parallel for-loop (in essence, it will just split the range $[1,n]$ to smaller parts and run these parts on different CPU cores in parallel).
On low-end computers, speedups were indeed minor. But on higher-end platforms I was surprised that I was getting excellent near-linear speedups. Some concrete examples (the exact timings may be a bit off, there is a lot of random variation; these were just quick experiments):
2 x 4-core Xeon (in total 8 cores): factor 5-8 speedups in comparison to single-threaded version.
2 x 6-core Xeon (in total 12 cores): factor 8-14 speedups in comparison to single-threaded version.
Now this was totally unexpected. Questions:
Precisely why does this kind of program parallelise so well? What happens in the hardware? (My current guess is something along these lines: the random reads from different thread are "pipelined" and the average rate of getting answers to these is much higher than in the case of a single thread.)
Is it necessary to use multiple threads and multiple cores to obtain any speedups? If some kind of pipelining indeed takes place in the interface between the main memory and the CPU, couldn't a single-threaded application let the main memory know that it will soon need $x[p[i]]$, $x[p[i+1]]$, ... and the computer could start fetching the relevant cache lines from the main memory? If this is possible in principle, how do I achieve it in practice?
What is the right theoretical model that we could use to analyse this kind of programs (and make correct predictions of the performance)?
Edit: There is now some source code and benchmark results available here: https://github.com/suomela/parallel-random-read
Some examples of ballpark figures ($n = 2^{32}$):
- approx. 42 ns per iteration (random read) with a single thread
- approx. 5 ns per iteration (random read) with 12 cores.