What is a bank conflict? (Doing Cuda/OpenCL programming)

Question

I have been reading the programming guide for CUDA and OpenCL, and I cannot figure out what a bank conflict is. They just sort of dive into how to solve the problem without elaborating on the subject itself. Can anybody help me understand it? I have no preference if the help is in the context of CUDA/OpenCL or just bank conflicts in general in computer science.

Lenticel

Answer 1

For Nvidia (and AMD for that matter) GPUs the local memory is divided into memory banks. Each bank can only address one dataset at a time, so if a half warp tries to load/store data from/to the same bank the access has to be serialized (this is a bank conflict). For GT200 GPUs there are 16 banks (32 banks for Fermi), 16 or 32 banks for AMD GPUs (57xx or higher: 32, everything below: 16), which are interleaved with a granularity of 32 bit (so bytes 0-3 are in bank 1, 4-7 in bank 2, ..., 64-69 in bank 1 and so on). For a better visualization it basically looks like this:

Bank    |      1      |      2      |      3      |     ...     |      16     |
Address |  0  1  2  3 |  4  5  6  7 |  8  9 10 11 |     ...     | 60 61 62 63 |
Address | 64 65 66 67 | 68 69 70 71 | 72 73 74 75 |     ...     |     ...     |
...

So if each thread in a half warp accesses successive 32-bit values there are no bank conflicts.

An exception from this rule (every thread must access its own bank) is broadcasting: if all threads access the same address, the value is only read once and broadcasted to all threads (for GT200 it has to be all threads in the half warp accessing the same address, IIRC Fermi and AMD GPUs can do this for any number of threads accessing the same value).

Assail

Sweet thanks for the visual and the explanation. I didn't know about broadcasts and that seems like an important bit of information :) How would I go about verifying that my loads and stores don't cause bank conflicts in shared memory? Do I have to get at the assembly code somehow or are there other ways? – Lenticel

since the occurence of bank conflict is somethink which will be determined at runtime (meaning the compiler doesn't know about it, after all most addresses are generated at runtime), getting the compiled version wouldn't help much. I typically do this the old fashined way, menaing I take a pen and paper and start thinking about what my code stores where. Afterall the rules governing the occurence of bank conflicts aren't that complex. Otherwise you can use the nvidia OpenCL profiler (should be bundled with the sdk, iirc). I think it has a counter for warp serializes. – Assail

Thanks for pointing out warp serializes. One of the readme text files that comes with the compute profiler said this, – Lenticel

Ack, excuse the comment above, for some reason I can't re-edit it. Anyways, I found this in the compute profiler's readme, " warp_serialize: Number of thread warps that serialize on address conflicts to either shared or constant memory." This is great that I can easily see if there are conflicts just by looking at the profiler output. How do you figure out if there are bank conflicts on pen and paper. Did you learn from any examples or tutorials? – Lenticel

As I said the mapping from addresses to banks is relatively simple, so it isn't that hard to figure out which accesses go to which bank and therefore if there are bank conflicts. The paper is only for more conflict access patterns, where I can't do it without. – Assail

Answer 2

The shared memory that can be accessed in parallel is divided into modules (also called banks). If two memory locations (addresses) occur in the same bank, then you get a bank conflict during which the access is done serially, losing the advantages of parallel access.

Jarid

So is this related to when a half-warp wants to store or load memory? 16 threads will be trying to do a memory transaction and thus accessing the same bank with more than one thread causes serialised processing? Also, how does one make sure your not storing/loading data in the same bank? – Lenticel

Answer 3

In simple words, bank conflict is a case when any memory access pattern fails to distribute IO across banks available in the memory system. The following examples elaborates the concept:-

Let us suppose we have two dimensional 512x512 array of integers and our DRAM or memory system has 512 banks in it. By default the array data will be layout in a way that arr[0][0] goes to bank 0, arr[0][1] goes to bank 1, arr[0][2] to bank 2 ....arr[0][511] goes to bank 511. To generalize arr[x][y] occupies bank number y. Now some code (as shown below) start accessing data in column major fashion ie. changing x while keeping y constant, then the end result will be that all consecutive memory access will hit the same bank--hence bank conflict.

int arr[512][512];
  for ( j = 0; j < 512; j++ ) // outer loop
    for ( i = 0; i < 512; i++ ) // inner loop
       arr[i][j] = 2 * arr[i][j]; // column major processing

Such problems, usually, are avoided by compilers by buffering the array or using prime number of elements in the array.

Volsung

your code example seems to imply sequential execution but the question is about GPU programming. Can you elaborate how your answer is applicable? – Yon

Answer 4

(CUDA Bank Conflict) I hope this will help.. this is very good explaination ...

http://www.youtube.com/watch?v=CZgM3DEBplE

Villasenor

Note that link-only answers are discouraged, SO answers should be the end-point of a search for a solution (vs. yet another stopover of references, which tend to get stale over time). Please consider adding a stand-alone synopsis here, keeping the link as a reference. – Monarch

Please elaborate over the link in an effort to better assist the OP. – Ainu

This video is really helpful! And I dont know why the down vote! It is a very good input! +1 – Reasonable

Answer 5

http://en.wikipedia.org/wiki/Memory_bank
and http://mprc.pku.cn/mentors/training/ISCAreading/1989/p380-weiss/p380-weiss.pdf

from this page, you can find the detail about memory bank. but it is a little different from what is said by @Grizzly. in this page, the bank is like this

bank 1 2 3

address|0, 3, 6...| |1, 4, 7...| | 2, 5,8...|

hope this would help

Schizont