CUDA Pro Tip: Optimize for Pointer Aliasing

http://devblogs.nvidia.com/parallelforall/cuda-pro-tip-optimize-pointer-aliasing/

by luckysahaf • 12 years ago

61 17 12 years ago

devblogs.nvidia.com

foxhill• 12 years ago

OpenCL Pro Tip: the __restrict keyword behaves as normal in OpenCL C, so adding it to kernel code may not move read only data into the constant cache.

to achieve this, try using the __constant address space.

Hansi• 12 years ago

Interesting but I'm very glad I don't need to worry about issues at that a low level in my work.

lordvon• 12 years ago

Thank you for submitting this article! I have always heard that FORTRAN is faster and commonly used in Aerospace, and I am glad to finally know why, as well as how to bridge the performance gap.

luckysahaf• 12 years ago

Welcome lordvon

possibilistic• 12 years ago

Is there any way to work out a priori whether or not two variables alias the same memory? (I assume that aliasing pertains to memory overlap within widths the maximum size of memory addressable by the CPU in one instruction.)

DannyBee4• 12 years ago

Aliasing is statically undecidable for all cases in any reasonable programming language.

However, the general analysis you are looking for is known as "points-to analysis".

It is a very large and complicated topic. Happy to try to answer anything more specific though.

Ono-Sendai• 12 years ago

In a functional programming language, aliasing either doesn't matter (as accesses will be read-only for function arguments), or is easy, as the function result is not the same array as either of the arguments.

tgb• 12 years ago

A very quick google didn't make it obvious how Fortran avoids this issue. Can anyone explain?

robmccoll• 12 years ago

Fortran has bound arrays and more explicit pointers. If bounds checking isn't enabled, it is still possible for some level of aliasing to happen, but it would most likely be an error, not the intention of the programmer. In general, there are far fewer places in Fortran code where the compiler must make the assumption that array references could be aliases of each other.

noahl• 12 years ago

I believe the Fortran standard requires that all function arguments point to non-overlapping pieces of memory. Therefore, the compiler can assume that pointers don't alias when compiling.

If you choose to pass arguments that do alias to a function, that becomes your problem.

DannyBee4• 12 years ago

Speaking as the guy who wrote the points-to analysis passes for GCC (and other compilers):

"By giving a pointer the restrict property, the programmer is promising the compiler that any data accessed through that pointer is not accessed in any other way. In other words, the compiler doesn’t have to worry about aliasing when using a pointer with the restrict property."

This is false. Entirely. Believing it will get you into trouble.

restrict is, as written in at least C99 and C11 (It's not in C++03 or C++11 standard, though compilers have imported the semantics from C99 to there to allow its use), is completely broken, in the sense that it doesn't do what you want (say two pointers can't alias).

This is being fixed in C++ (though no plans to fix in C), but as a completely trivial example:

  void example1(restrict float *a, restrict float *b, float *c, int i) {
     c[i] = a[i] + b[i];
  }

In this example, a and b may alias, despite the restrict, because restrict says the storage must be modified:

"During each execution of B, let L be any lvalue that has &L based on P. If L is used to access the value of the object X that it designates, and X is also modified (by any means), then the following requirements apply"

(the standard then gives the above as an example of how two pointers may be aliased with restrict)

kevinastock• 12 years ago

Shouldn't it be 'float * restrict a'?

When could one get into trouble thinking that "restrict == this will not alias"? If X is never modified during B it seems like aliasing wouldn't cause any problems.

Since restrict means nothing if no value in it is modified, would it be reasonable and possible for the compiler to issue a warning in cases like example1?

Barden• 12 years ago

I guess one could get in trouble if you were writing a compiler, as users could write conforming code that you thought was undefined.

I don't see how one could get into trouble as a developer though. It seems to me that, while technically incorrect, the blog imposes more restrictions than is actually neccessary on the user.

DannyBee4• 12 years ago

In this specific case you will get into trouble if you expect the compiler to be able to reorder loads, and it doesn't.

IE you will get into performance trouble :)

In general, there are some complicated scope related cases where you will get into trouble (the rules deal with "based on" and "scope" all over the place, and not in ways that always make sense).

Shugyousha• 12 years ago

If I remember correctly, the C99 standard forbids pointer aliasing. That means if you use a C99-standard-conform compiler, it will automatically assume that you do not alias any pointers (and produce more efficient code). Making sure that you actually do NOT alias any pointers is up to the programmer of course (there exist compiler warning options that can detect such aliasing though)...

readerrrr• 12 years ago

You may not alias incompatible types. In the example every type passed in the function is the same. Float. Those types are compatible( every type is to itself ) and may alias. Therefore the need to use restrict.

DannyBee4• 12 years ago

"If I remember correctly, the C99 standard forbids pointer aliasing. "

No, it doesn't :) It forbids some forms of type casting if they are later dereferenced, but that's not really the same.

CUDA Pro Tip: Optimize for Pointer Aliasing

Related Stories