19
$\begingroup$

I came to know that the graphic processing unit have something called memory coalescing. On reading on it I was not clear on the topic. Is this any way related to Memory Level Parallelism.

I have searched in Google but was not able to obtain a satisfactory answer.

It would be helpful if someone gives a more comprehensive, easy-to-understand explanation.

$\endgroup$
1
  • $\begingroup$ Memory-Level Parallelism (MLP) is the ability to perform multiple memory transactions at once. In many architectures, this manifests itself as the ability to perform both a read and write operation at once, although it also commonly exists as being able to perform multiple reads at once. It is rare to perform multiple write operations at once, because of the risk of potential conflicts (trying to write two different values to the same location). Notice that this is not the same as vectorized memory operations, such as reading 4 separate but contiguous 8-bit values in a single 32-bit read. $\endgroup$
    – sai kiran grandhi
    Nov 22, 2013 at 5:05

2 Answers 2

Reset to default
14
$\begingroup$

"Coalescing" can also refer to coalescing memory access patterns. In this usage, coalescing is used to mean making sure that threads run simultaneously, try to access memory that is nearby. This is usually because:

  • Memory is usually retrieved in large blocks from RAM.
  • Some processing units will try to predict future memory accesses and cache ahead, while yet processing older parts of memory.
  • Memory is cached in a hierarchy of successively larger-but-slower caches.

Therefore, making programs that can use predictable memory patterns is important. It is even more important with a threaded program, so that the memory requests do not jump all over; otherwise the processing unit will be waiting for memory requests to be fulfilled.

Diagrams inspired by Introduction to Parallel Programming: Lesson 2 GPU Hardware and Parallel Communication Patterns:

Below: Four threads, with uniform memory access. The black dashed rectangle represents a single 4-word memory request.

enter image description here

The memory accesses are close, and can be retrieved in one go/block (or the least number of requests).

However, if we increase the "stride" of the access between the threads, it will require many more memory accesses. Below: four more threads, with a stride of two.

4 memory coalesced threads, and 4 threads with a stride of 2

Here you can see that these 4 threads require 2 memory block requests. The smaller the stride the better. The wider the stride, the more requests are potentially required.

Of course, worse than a large memory stride is a random memory access pattern. These will be nearly impossible to pipeline, cache or predict.

TikZ sources:

$\endgroup$
2
  • 2
    $\begingroup$ Multiple threads can also access the same data item (not just an element within the same larger chunk), somewhat similar to (but more generic than) SPLAT operations in SIMD architectures. As latency-tolerant throughput processors, GPUs can afford to increase access latency when such allows increased effective bandwidth. $\endgroup$
    – Paul A. Clayton
    Nov 22, 2013 at 15:58
  • $\begingroup$ The link given is broken. $\endgroup$
    – Daniel Soutar
    Nov 13, 2019 at 15:03
4
$\begingroup$

I think I see two uses of the word "coalescing" around the net, both having to do with memory. One is coalescing freed memory allocations, which is what is referred to in the wikipedia page linked in the question.

Coalescing freed memory allocations

When allocating memory, sometimes the memory manager can have a situation where there are two adjacent memory blocks that are freed. Combining these would make them a single freed memory block - this is called "coalescing". Example:

Starting with 4 allocated blocks:

4 allocated blocks

Later, one of them is freed:

Now 1 free block

And later another is freed:

Now 2 adjacent free blocks

Now, why have two adjacent free blocks? Coalescing them:

Coalescing the freed blocks, now 2 allocated blocks, 1 freed

Coalescing can occur as soon as it is possible, or, for example, in a garbage collector, when the collector runs.

TikZ sources:

$\endgroup$
2
  • $\begingroup$ I think this answer does not suit what I want. Memory coalescing is reading contiguous blocks of memory as you provided in other answer. If possible please remove this answer and the link in question which you edited $\endgroup$
    – sai kiran grandhi
    Nov 22, 2013 at 5:08
  • $\begingroup$ @saikirangrandhi I'll keep the answer for reference. You can revise/undo the edit to your question as you want to; you can just press "edit" under the question. $\endgroup$
    – Realz Slaw
    Nov 22, 2013 at 5:27

Your Answer

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

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