Montag, Oktober 24, 2016

Compiling shaders: dynamically uniform variables and "convergent" intrinsics

There are some program transformations that are obviously correct when compiling regular single-threaded or even multi-threaded code, but that cannot be used for shader code. For example:

 v = texture(u_sampler, texcoord);  
 if (cond) {  
   gl_FragColor = v;  
 } else {  
   gl_FragColor = vec4(0.);  
 ... cannot be transformed to ...
 if (cond) {
   // The implicitly computed derivate of texcoord
   // may be wrong here if neighbouring pixels don't
   // take the same code path.
   gl_FragColor = texture(u_sampler, texcoord);
 } else {
   gl_FragColor = vec4(0.);  

 ... but the reverse transformation is allowed.

Another example is:

 if (cond) {
   v = texelFetch(u_sampler[1], texcoord, 0);
 } else {
   v = texelFetch(u_sampler[2], texcoord, 0);

 ... cannot be transformed to ...

 v = texelFetch(u_sampler[cond ? 1 : 2], texcoord, 0);
 // Incorrect, unless cond happens to be dynamically uniform.

 ... but the reverse transformation is allowed.

Using GL_ARB_shader_ballot, yet another example is:

 bool cond = ...;
 uint64_t v = ballotARB(cond);
 if (other_cond) {

 ... cannot be transformed to ...

 bool cond = ...;
 if (other_cond) {
   // Here, ballotARB returns 1-bits only for threads/work items
   // that take the if-branch.

 ... and the reverse transformation is also forbidden.

These restrictions are all related to the GPU-specific SPMD/SIMT execution model, and they need to be taught to the compiler. Unfortunately, we partially fail at that today.

Here are some types of restrictions to think about (each of these restrictions should apply on top of any other restrictions that are expressible in the usual, non-SIMT-specific ways, of course):

  1. An instruction can be moved from location A to location B only if B dominates or post-dominates A.

    This restriction applies e.g. to instructions that take derivatives (like in the first example) or that explicitly take values from neighbouring threads (like in the third example). It also applies to barrier instructions.

    This is LLVM's convergent function attribute as I understand it.

  2. An instruction can be moved from location A to location B only if A dominates or post-dominates B.

    This restriction applies to the ballot instruction above, but it is not required for derivative computations or barrier instructions.

    This is in a sense dual to LLVM's convergent attribute, so it's co-convergence? Divergence? Not sure what to call this.

  3. Something vague about not introducing additional non-uniformity in the arguments of instructions / intrinsic calls.

    This last one applies to the sampler parameter of texture intrinsics (for the second example), to the ballot instruction, and also to the texture coordinates on sampling instructions that implicitly compute derivatives.

For the last type of restriction, consider the following example:

 uint idx = ...;
 if (idx == 1u) {
   v = texture(u_sampler[idx], texcoord);
 } else if (idx == 2u) {
   v = texture(u_sampler[idx], texcoord);

 ... cannot be transformed to ...

 uint idx = ...;
 if (idx == 1u || idx == 2u) {
   v = texture(u_sampler[idx], texcoord);

In general, whenever an operation has this mysterious restriction on its arguments, then the second restriction above must apply: we can move it from A to B only if A dominates or post-dominates B, because only then can we be certain that the move introduces no non-uniformity. (At least, this rule applies to transformations that are not SIMT-aware. A SIMT-aware transformation might be able to prove that idx is dynamically uniform even without the predication on idx == 1u or idx == 2u.)

However, the control flow rule is not enough:

 v1 = texture(u_sampler[0], texcoord);
 v2 = texture(u_sampler[1], texcoord);
 v = cond ? v1 : v2;

 ... cannot be transformed to ...

 v = texture(u_sampler[cond ? 0 : 1], texcoord);

The transformation does not break any of the CFG-related rules, and it would clearly be correct for a single-threaded program (given the knowledge that texture(...) is an operation without side effects). So the CFG-based restrictions really aren't sufficient to model the real set of restrictions that apply to the texture instruction. And it gets worse:

 v1 = texelFetch(u_sampler, texcoord[0], 0);
 v2 = texelFetch(u_sampler, texcoord[1], 0);
 v = cond ? v1 : v2;

 ... is equivalent to ...

 v = texelFetch(u_sampler, texcoord[cond ? 0 : 1], 0);

After all, texelFetch computes no implicit derivatives.

Calling the three kinds of restrictions 'convergent', 'co-convergent', and 'uniform', we get:

 texture(uniform sampler, uniform texcoord) convergent (co-convergent)
 texelFetch(uniform sampler, texcoord, lod) (co-convergent)
 ballotARB(uniform cond) convergent co-convergent
 barrier() convergent

For the texturing instructions, I put 'co-convergent' in parentheses because these instructions aren't inherently 'co-convergent'. The attribute is only there because of the 'uniform' function argument.

Actually, looking at the examples, it seems that co-convergent only appears when a function has a uniform argument. Then again, the texelFetch function can be moved freely in the CFG by a SIMT-aware pass that can prove that the move doesn't introduce non-uniformity to the sampler argument, so being able to distinguish functions that are inherently co-convergent (like ballotARB) from those that are only implicitly co-convergent (like texture and texelFetch) is still useful.

For added fun, things get muddier when you notice that in practice, AMDGPU doesn't even flag texturing intrinsics as 'convergent' today. Conceptually, the derivative-computing intrinsics need to be convergent to ensure that the texture coordinates for neighbouring pixels are preserved (as in the very first example). However, the AMDGPU backend does register allocation after the CFG has been transformed into the wave-level control-flow graph. So register allocation automatically preserves neighbouring pixels even when a texture instruction is sunk into a location with additional control-flow dependencies.

When we reach a point where vector register allocation happens with respect to the thread-level control-flow graph, then texture instructions really need to be marked as convergent for correctness. (This change would be beneficial overall, but is tricky because scalar register allocation must happen with respect to the wave-level control flow graph. LLVM currently wants to allocate all registers in one pass.)

Samstag, September 03, 2016

Exec masks in LLVM

Like is usual in GPUs, Radeon executes shaders in waves that execute the same program for many threads or work-items simultaneously in lock-step. Given a single program counter for up to 64 items (e.g. pixels being processed by a pixel shader), branch statements must be lowered to manipulation of the exec mask (unless the compiler can prove the branch condition to be uniform across all items). The exec mask is simply a bit-field that contains a 1 for every thread that is currently active, so code like this:
    if (i != 0) {
        ... some code ...
gets lowered to something like this:
    v_cmp_ne_i32_e32 vcc, 0, v1
    s_and_saveexec_b64 s[0:1], vcc
    s_xor_b64 s[0:1], exec, s[0:1]

    ... some code ...

    s_or_b64 exec, exec, s[0:1]
(The saveexec assembly instructions apply a bit-wise operation to the exec register, storing the original value of exec in their destination register. Also, we can introduce branches to skip the if-block entirely if the condition happens to be uniformly false, )

This is quite different from CPUs, and so a generic compiler framework like LLVM tends to get confused. For example, the fast register allocator in LLVM is a very simple allocator that just spills all live registers at the end of a basic block before the so-called terminators. Usually, those are just branch instructions, so in the example above it would spill registers after the s_xor_b64.

This is bad because the exec mask has already been reduced by the if-condition at that point, and so vector registers end up being spilled only partially.

Until recently, these issues were hidden by the fact that we lowered the control flow instructions into their final form only at the very end of the compilation process. However, previous optimization passes including register allocation can benefit from seeing the precise shape of the GPU-style control flow earlier. But then, some of the subtleties of the exec masks need to be taken account by those earlier optimization passes as well.

A related problem arises with another GPU-specific specialty, the "whole quad mode". We want to be able to compute screen-space derivatives in pixel shaders - mip-mapping would not be possible without it - and the way this is done in GPUs is to always run pixel shaders on 2x2 blocks of pixels at once and approximate the derivatives by taking differences between the values for neighboring pixels. This means that the exec mask needs to be turned on for pixels that are not really covered by whatever primitive is currently being rendered. Those are called helper pixels.

However, there are times when helper pixels absolutely must be disabled in the exec mask, for example when storing to an image. A separate pass deals with the enabling and disabling of helper pixels. Ideally, this pass should run after instruction scheduling, since we want to be able to rearrange memory loads and stores freely, which can only be done before adding the corresponding exec-instructions. The instructions added by this pass look like this:
    s_mov_b64 s[2:3], exec
    s_wqm_b64 exec, exec

    ... code with helper pixels enabled goes here ...

    s_and_b64 exec, exec, s[2:3]

    ... code with helper pixels disabled goes here ...
Naturally, adding the bit-wise AND of the exec mask must happen in a way that doesn't conflict with any of the exec manipulations for control flow. So some careful coordination needs to take place.

My suggestion is to allow arbitrary instructions at the beginning and end of basic blocks to be marked as "initiators" and "terminators", as opposed to the current situation, where there is no notion of initiators, and whether an instruction is a terminator is a property of the opcode. An alternative, that Matt Arsenault is working on, adds aliases for certain exec-instructions which act as terminators. This may well be sufficient, I'm looking forward to seeing the result.

Samstag, Juni 18, 2016

Wie man eine Privatisierung von Autobahnen bewertet

Heute erfahre ich, wohl mit etwas Verspätung, dass in Deutschland mal wieder die Privatisierung der Autobahnen diskutiert wird. Wozu soll diese Privatisierung gut sein?

Soweit ich sehe, gibt es in der aktuellen Diskussion grob skizziert zwei Argumente. Erstens, die Zinsen sind niedrig und private Investoren sehnen sich nach Möglichkeiten, Gewinne zu erzielen. Private Autobahnen wären eine solche Möglichkeit. Dieses Argument finde ich ziemlich unverschämt. Private Investoren - vor allem die individuellen Investoren, die bei Privatisierungen in der Regel am meisten profitieren - gehören definitionsgemäß zu den Leuten, die nun wirklich als Allerletztes Hilfe vom Staat brauchen. Sich von deren Interessen leiten zu lassen geht gar nicht.

Kommen wir also zum zweiten Argument. Die Deutschen sehen zwar, dass Investitionen in das Autobahnnetz nötig sind, lieben aber auch die schwarze Null. Aber auch das ist kein stimmiges Argument. Um die Privatisierung der Autobahnen sinnvoll bewerten zu können, ist es hilfreich, sich die Nettogeldflüsse anzusehen:
Egal wie die Autobahn finanziell organisiert wird, letztendlich kommen die Einnahmen für das System zum einen von den Nutzern und zum anderen aus allgemeinen Steuern (manche Einnahmequellen können irgendwo dazwischen liegen, zum Beispiel Benzinsteuern). Und letztendlich landen die Ausgaben zum einen beim eigentlichen Bau und Betrieb der Autobahnen - das ist offensichtlich - und bei privaten Investoren. Letzteres ist nicht ganz so offensichtlich: auch eine Autobahn, die rein in Staatshand ist, hat Ausgaben an private Investoren wenn der Staat sich für Bau und Betrieb "verschuldet".

Aus Sicht des Gemeinwohls gibt es mit Blick auf die Geldflüsse vor allem zwei Fragen: Wie viel muss von der linken Seite gezahlt werden, und wie wird die Rechnung zwischen Autobahnnutzern und Bürgern allgemein aufgeteilt? Von links kommt zwangsläufig genau so viel Geld, wie rechts wieder herausfließt. Sinnvollerweise konzentriert sich die Politik also auf die rechte Seite. Hilft die Privatisierung dabei, die Ausgaben auf der rechten Seite zu reduzieren?

Meine kurze Einschätzung: Bei Bau und Betrieb lässt sich durch Privatisierung kaum etwas erreichen. Der größte Brocken ist der Bau, und der wird schon lange an private Unternehmen ausgeschrieben. Wenn es hier also Effizienz durch privates Wirtschaften geben sollte, so wird diese schon längst erreicht.

Spannender wird es bei den Ausgaben an private Investoren. Die erwartete Rendite bei privaten Unternehmungen liegt deutlich höher als die Zinsen auf Bundesanleihen. Man kennt das von anderen Privatisierungen: wenn die privaten Investoren nicht von einem höheren Gewinn als bei Bundesanleihen ausgehen können, dann kaufen sie eben lieber Bundesanleihen. Es ist also davon auszugehen, dass bei einer Privatisierung der Autobahnen die Ausgaben insgesamt eher steigen werden, wodurch das ganze System für die Bürger und Nutzer teurer wird. Privatisierung ist ein Verlustgeschäft.

Die zweite Frage, nämlich ob die Einnahmen mehr aus allgemeinen Steuern oder mehr direkt von den Nutzen kommen sollten, ist ganz offensichtlich unabhängig von der Frage der Privatisierung. Man muss nur bedenken (so wenig ich persönlich ein Freund des Autofahrens bin), dass eine verstärkte Finanzierung über die Nutzer in der Tendenz die Ausgabenseite erhöht und so das gesamte System teurer macht - Maut zu erheben ist ein Bürokratieaufwand. Ob die durch Maut verringerte Effizienz ein angemessener Preis ist für höhere Gerechtigkeit muss jeder für sich selbst entscheiden. Man beachte auch die Analogie zur Forderung nach kostenlosem ÖPNV!

Übrigens: Selbst wenn die Ausgaben mit der Privatisierung überraschend sinken sollten, gibt es noch zusätzliche Erwägungen, die in der Tendenz gegen eine Privatisierung sprechen. Zum einen stellt sich die Frage der Kontrolle: selbst wenn der Staat Mehrheitseigner des Autobahnnetzes bleibt erhöht sich doch der Einfluss demokratisch nicht legitimierter Kräfte auf den Betrieb wichtiger Infrastruktur des Landes. Wie hoch der finanzielle Zugewinn sein müsste, um diesen Kontrollverlust zu rechtfertigen, muss jeder selbst für sich entscheiden.

Zum anderen spielt auch die Zusammensetzung der privaten Investoren eine Rolle - wie weit werden die Ausgaben an private Investoren effektiv in der Bevölkerung gestreut? Bei der standardisierten, "langweiligen" Bundesanleihe sind die privaten Investoren oft langweilige Fonds an denen auch "normalere", weniger reiche Bürger z.B. zur Altersvorsorge beteiligt sind. Die Ausgaben für private Investoren gehen somit zwar nicht an alle Bürger gleichmässig, aber sie sind doch relativ weit gestreut. Bei einer Privatisierung wird aber nicht mit derart "langweiligen" Finanzinstrumenten gearbeitet, wodurch sie sich tendenziell eher in der Hand von Menschen sammeln, die ohnehin schon reich sind. Somit sorgen die Ausgaben an private Investoren also in der Tendenz für stärkere Ungleichheit im Land - auch das ein Argument gegen die Privatisierung.

Heißt das denn, das jede Privatisierung schlecht ist? Schließlich lassen sich die genannten Argumente auch auf andere Privatisierungen übertragen. Tatsächlich ist der Blick auf die Nettogeldflüsse immer hilfreich, und ja, das Fazit sieht bei allen Privatisierungsprojekten, die heutzutage diskutiert werden, ähnlich aus. Das liegt aber vor allem daran, dass sich der Staat bei uns schon weitgehend aus dem exekutiven Geschäft herausgezogen hat. Wäre die Stahlindustrie oder die Produktion von Industrierobotern heute in staatlicher Hand, dann sähe die Analyse einer Privatisierung der entsprechenden Unternehmen sicher anders aus, weil es dort glaubwürdige Argumente für einen Effizienzgewinn durch Marktöffnung gibt. Im Fall von Infrastruktur gibt es aber in der Regel keine sinnvolle Marktöffnung, und daher auch kaum Argumente für Privatisierung.

Donnerstag, Mai 19, 2016

A little 5-to-8-bit mystery

Writing the accelerated glReadPixels path for reads to PBOs for Gallium, I wanted to make sure the various possible format conversions are working correctly. They do, but I noticed something strange: when reading from a GL_RGB565 framebuffer to GL_UNSIGNED_BYTE, I was getting tiny differences in the results depending on the code path that was taken. What was going on?

Color values are conceptually floating point values, but most of the time, so-called normalized formats are used to store the values in memory. In fact, many probably think of color values as 8-bit normalized values by default, because of the way many graphics programs present color values and because of the #cccccc color format of HTML.

Normalized formats generalize this well-known notion to an arbitrary number of bits. Given a normalized integer value x in N bits, the corresponding floating point value is x / (2**N - 1) - for example, x / 255 for 8 bits and x / 31 for 5 bits. When converting between normalized formats with different bit depths, the values cannot be mapped perfectly. For example, since 255 and 31 are coprime, the only floating point values representable exactly in both 5- and 8-bit channels are 0.0 and 1.0.

So some imprecision is unavoidable, but why was I getting different values in different code paths?

It turns out that the non-PBO path first blits the requested framebuffer region to a staging texture, from where the result is then memcpy()d to the user's buffer. It is the GPU that takes care of the copy from VRAM, the de-tiling of the framebuffer, and the format conversion. The blit uses the normal 3D pipeline with a simple fragment shader that reads from the "framebuffer" (which is really bound as a texture during the blit) and writes to the staging texture (which is bound as the framebuffer).

Normally, fragment shaders operate on 32-bit floating point numbers. However, Radeon hardware allows an optimization where color values are exported from the shader to the CB hardware unit as 16-bit half-precision floating point numbers when the framebuffer does not require the full floating point precision. This is useful because it reduces the bandwidth required for shader exports and allows more shader waves to be in flight simultaneously, because less memory is reserved for the exports.

And it turns out that the value 20 in a 5-bit color channel, when first converted into half-float (fp16) format, becomes 164 in an 8-bit color channel, even though the 8-bit color value that is closest to the floating point number represented by 20 in 5-bit is actually 165. The temporary conversion to fp16 cuts off a bit that would make the difference.

Intrigued, I wrote a little script to see how often this happens. It turns out that 20 in a 5-bit channel and 32 in a 6-bit channel are the only cases where the temporary conversion to fp16 leads to the resulting 8-bit value to be off by one. Luckily, people don't usually use GL_RGB565 framebuffers... and as a general rule, taking a value from an N-bit channel, converting it to fp16, and then storing the value again in an N-bit value (of the same bit depth!) will always result in what we started out with, as long as N <= 11 (figuring out why is an exercise left to the reader ;-)) - so the use cases we really care about are fine.