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]

if_block:
    ... some code ...

join:
    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.

Donnerstag, April 28, 2016

Using LLVM bugpoint to hunt radeonsi compiler crashes

Shaders can be huge, and tracking down compiler crashes (or asserts) in LLVM with a giant shader isn't a lot of fun. Luckily, LLVM has a tool called Bugpoint. It takes a given piece of LLVM IR and tries a bunch of simplifications such as removing instructions or basic blocks, while checking that a given condition is still satisfied. Make the given condition something like "llc asserts with message X", and you have a very useful tool for reducing test cases. Unfortunately, its documentation isn't the greatest, so let me briefly dump how I have used it in the past.

I have a little script called run_llc.sh that looks like this:
#!/bin/bash

if ! llc -mtriple=amdgcn-- -verify-machineinstrs "$@" 2>&1 | grep "error message here"; then
  exit 0
else
  exit $?
fi
When I encounter a compiler assertion, I first make sure to collect the offending shader from our driver using R600_DEBUG=ps,vs,gs,tcs,tes and extract it into a file like bug.ll. (In very rare cases, one may need the preoptir option in R600_DEBUG.) Then I edit run_llc.sh with the correct error message and run
bugpoint -compile-custom -compile-command ./run_llc.sh bug.ll
It'll churn for some time and produce a hopefully much smaller .bc file that one can use the usual tools on, such as llc, opt, and llvm-dis.

Occasionally, it can be useful to run the result through opt -instnamer or to simplify it further by hand, but usually, bugpoint provides a good starting point.