22

I am implementing an image filtering operation in C using multiple threads and making it as optimized as possible. I have one question though: If a memory is accessed by thread-0, and concurrently if the same memory is accessed by thread-1, will it get it from the cache ? This question stems from the possibility that these two threads could be running into two different cores of the CPU. So another way of putting this is: do all the cores share the same common cache memory ?

Suppose i have a memory layout like the following

int output[100];

Assume there are 2 CPU cores and hence I spawn two threads to work concurrently. One scheme could be to divide the memory into two chunks, 0-49 and 50-99 and let each thread work on each chunk. Another way could be to let thread-0 work on even indices, like 0 2 4 and so on.. while the other thread work on odd indices like 1 3 5 .... This later technique is easier to implement (specially for 3D data) but I am not sure if I could use the cache efficiently this way.

2
  • In the end, this knowledge won't help you much. Although I agree that being able to interpret observations accordingly to the knowledge of the CPU's innards is good, in the end you are down to measuring what is faster, and apply what you observed no matter whether it fits any theory.
    – sbi
    Jan 26, 2011 at 8:53
  • 1
    I see no reason this has a c++ tag (you did write this in C, you said), so I removed it. Feel free to yell at me if that was stupid.
    – sbi
    Jan 26, 2011 at 8:54

4 Answers 4

26

The answer to this question strongly depends upon the architecture and the cache level, along with where the threads are actually running.

For example, recent Intel multi core CPUs have a L1 caches that are per-core, and an L2 cache that is shared among cores that are in the same CPU package; however different CPU packages will have their own L2 caches.

Even in the case when your threads are running on two cores within the one package though, if both threads access data within the same cacheline you will have that cacheline bouncing between the two L1 caches. This is very inefficient, and you should design your algorithm to avoid this situation.


A few comments have asked about how to go about avoiding this problem.

At heart, it's really not particularly complicated - you just want to avoid two threads from simultaneously trying to access data that is located on the same cache line, where at least one thread is writing to the data. (As long as all the threads are only reading the data, there's no problem - on most architectures, read-only data can be present in multiple caches).

To do this, you need to know the cache line size - this varies by architecture, but currently most x86 and x86-64 family chips use a 64 byte cache line (consult your architecture manual for other architectures). You will also need to know the size of your data structures.

If you ask your compiler to align the shared data structure of interest to a 64 byte boundary (for example, your array output), then you know that it will start at the start of a cache line, and you can also calculate where the subsequent cache line boundaries are. If your int is 4 bytes, then each cacheline will contain exactly 8 int values. As long as the array starts on a cacheline boundary, then output[0] through output[7] will be on one cache line, and output[8] through output[15] on the next. In this case, you would design your algorithm such that each thread works on a block of adjacent int values that is a multiple of 8.

If you are storing complicated struct types rather than plain int, the pahole utility will be of use. It will analyse the struct types in your compiled binary, and show you the layout (including padding) and total size. You can then adjust your structs using this output - for example, you may want to manually add some padding so that your struct is a multiple of the cache line size.

On POSIX systems, the posix_memalign() function is useful for allocating a block of memory with a specified alignment.

7
  • @caf: out of curiosity, how would you avoid this situation? Jan 26, 2011 at 8:57
  • One more question: do u just create threads to run codes on different cores ? Is there anyway to explicitly tell the threads to run on different cores or this is something lies on the mercy of the OS ? Jan 26, 2011 at 9:06
  • @caf: what would you do to avoid such situation as a programmer ? Jan 26, 2011 at 9:06
  • mercy of OS - but when running a multithreaded program on a multi-core system, the threads will most likely run on more than 1 core, unless the user tells the OS he doesnt want that to happen (many os let users specify on which cores a program may run. e.g. this can be done in windows task manager)
    – smerlin
    Jan 26, 2011 at 9:14
  • @Zahid Hossain and @Tony: I've update the answer with some more information. It is possible to manually assign threads to cores, but it is usually better to simply let the OS scheduler do this.
    – caf
    Jan 26, 2011 at 9:35
10

In general it is a bad idea to share overlapping memory regions like if one thread processes 0,2,4... and the other processes 1,3,5... Although some architectures may support this, most architectures will not, and you probably can not specify on which machines your code will run on. Also the OS is free to assign your code to any core it likes (a single one, two on the same physical processor, or two cores on separate processors). Also each CPU usually has a separate first level cache, even if its on the same processor.

In most situations 0,2,4.../1,3,5... will slow down performance extremely up to possibly being slower than a single CPU. Herb Sutters "Eliminate False Sharing" demonstrates this very well.

Using the scheme [...n/2-1] and [n/2...n] will scale much better on most systems. It even may lead to super linear performance as the cache size of all CPUs in sum can be possibly used. The number of threads used should be always configurable and should default to the number of processor cores found.

1
  • Thanks a lot. Since I will be using a 3D array, as in int output[z_size][y_size][x_size], for an example and assuming the memory is laid out with the x first, y second and z last, i can assign few z planes/sheets to each cores. For example, thread-0 gets output[0..9][y_size][x_size] to process and thread-1 gets output[10..19][y_size][x_size] to process. This way, its always made sure that each core cache line lies only in its own L1. Jan 26, 2011 at 19:56
0

I might be mistaking, but whether the core's cache is shared or not depends on the implementation of the CPU. You'd have to look up the technical sheets on the manufacturer's page to check whether each core in your CPU has their own cache or whether the cache was shared.

I was working on image manipulation as well for a security company and sometimes we got corrupted images after running batch operations on threads. After long investigations we came to the conclusion that the cache was shared between CPU Core's and that in rare cases the data was beeing overwritten or replaced with incorrect data.

Whether this is something to keep into account or is rather a rare event I cannot anwser.

2
  • One more question: do u just create threads to run codes on different cores ? Is there anyway to explicitly tell the threads to run on different cores or this is something lies on the mercy of the OS ? Jan 26, 2011 at 9:04
  • I beleive this is at the mercy of the OS. Perhaps if you dive under the OS you could have an influence on it, but it's not something I'd explore with. Jan 28, 2011 at 11:53
0

Intel documentation

Intel publishes per-generation datasheets which may contain this kind of information.

For example, for the processor i5-3210M which I had on my older computer, I look up the 3rd generation - Datasheet Volume 1 3.3 "Intel Hyper-Threading Technology (Intel HT Technology)" says:

The processor supports Intel Hyper-Threading Technology (Intel HT Technology) that allows an execution core to function as two logical processors. While some execution resources such as caches, execution units, and buses are shared, each logical processor has its own architectural state with its own set of general-purpose registers and control registers.

which confirms that caches are shared in a given hyperthread for that generation of CPUs.

See also:

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.