Sonntag, Dezember 18, 2016

Consciousness is not a quantum phenomenon

Consciousness is weird. Quantum physics is weird. There's this temptation to conclude that therefore, they must be related, but they're almost certainly not. In fact, I want to explore an argument that consciousness cannot be a quantum phenomenon but must necessarily be classical.

We don't really understand consciousness, but many people have tried. A compelling argument pushed by Douglas Hofstadter is that consciousness is a product of certain sufficiently complex "strange loops", self-reflexive processes. Put simply, the mind observes the body, but it also observes itself observing the body, and it observes itself observing itself observing the body, and so on. On some level, this endlessly reflexive process of self-observation is consciousness.

Part of this self-reflexive process is the simulation of simplified models of the world, including ourselves and other people. This allows us to anticipate the effects of possible actions, which helps us choose the actions that we ultimately take. (Much or even most of our daily decision making doesn't use this complicated process and simply uses subconscious pattern matching. But we're focusing on the conscious part of the mind here.) Running multiple simulations to choose from a set of possible actions requires starting the simulation with the same initial state multiple times. In other words, it requires copying the initial state.

If consciousness were a quantum phenomenon, this would imply copying some quantum states. However, it is physically impossible to copy a quantum state due to the no-cloning theorem, just like it is impossible to change the amount of energy in the universe.

This immediately gives us a very nice explanation for why we are unable to perceive quantum states. Nothing can copy quantum states, and so a conscious mind that perceives quantum states cannot develop, since perception and memory of states of the world certainly requires making copies of those states (at least partial ones).

There is some wiggle-room in this argument. Even a mind that only perceives, remembers, and computes on internal representations of classical states might still use quantum physical processes for this computation. And at a certain level, it is actually obviously true that our brains do this: our brains are full of chemistry, and chemistry is full of quantum physics. The point is that this is just an irrelevant implementation detail. Those quantum processes could just as well be simulated by something classical.

And keep in mind that if we believe in the importance of "strange loops", then the mind itself is one of the things that the mind perceives. The mind cannot perceive quantum states, and so any kind of quantum-ness in the operation of the mind must be purely incidental. It cannot be a part of the "strange loop", and so it must ultimately be of limited importance.

There is yet more wiggle-room. We know that some computational tasks can be implemented much more efficiently on a quantum computer than on a classical computer - at least in theory. Nobody has ever built a true quantum computer that is big enough to demonstrate a speed-up over classical computers and lived to tell the tale published it. Perhaps consciousness requires the solution of computational tasks that can only be solved efficiently using quantum computing?

I doubt it. It looks increasingly like even in theory, quantum computers can only speed up a few very specialized mathematical problems, and that's not what our minds are particularly good at.

It's always possible that this whole argument will turn out to be wrong, once we learn more about consciousness in the future (and wouldn't that be interesting!), but for now, the bottom line for me is: Strange information processing loops most likely play an important role in consciousness. Such loops cannot involve quantum states due to the no-cloning theorem. Hence, consciousness is not a quantum phenomenon.

Mittwoch, Dezember 07, 2016

Bedingungsloses Grundeinkommen: Die Finanzierung ist nicht das Problem

Gestern hat Joerg Wellbrock auf dem Spiegelfechter einen Beitrag geschrieben, in dem er einige Kritik am Konzept des Bedingungslosen Grundeinkommen (BGE) übt. Ich teile vieles der Kritik zumindest als Skepsis.

Aber wenn er die Finanzierung des BGE hinterfragt, steige ich aus. Er sieht ein Finanzierungsproblem, wo in Wirklichkeit keins ist. Denn der Staat, zumindest der monetär souveräne Staat, kann finanzieren was und wie viel er will. Zu glauben, ein monetär souveräner Staat könne irgendwo ein Finanzierungsproblem haben ist ungefähr so, als würde man glauben, dass beim Spiel Monopoly die Bank pleite gehen kann. Kann sie nicht - und wenn das gedruckte Geld ausgeht, dann behilft man sich eben irgendwie anders. So steht es in den Regeln.

Moment! ruft der geneigte Leser jetzt innerlich, aber ist das nicht Gelddrucken und kommt dann nicht die Inflation? Nein, Gelddrucken ist das nicht. Auch beim Monopoly-Spielen würde man das "Problem" eher nicht durch Gelddrucken lösen. Aber ja, natürlich kann Geldausgeben grundsätzlich immer zu Inflation führen, den Umständen entsprechend. Diese Möglichkeit führt ja auch Wellbrock schon als potentielles Problem des BGE an.

Aber es ist eben wichtig, dass das Potential für Inflation das einzige Problem ist. Es gibt kein Finanzierungsproblem. Vielleicht gibt es ein Inflationsproblem. Der Unterschied ist wichtig, und zwar aus zwei Gründen.

Erstens geben wir den sogenannten Kreditgebern und Finanzmärkten zu viel Macht, wenn wir an ein Finanzierungsproblem glauben. Dieser Glaube führt dazu, dass unsere Politiker in Angst leben vor den sogenannten Finanzmärkten. Und weil diese so diffus sind und nicht klar definiert, gibt diese Angst dann de facto Macht an die Hohepriester bei Banken und Think Tanks, die als Interpreten des Marktwillens gelten. Neutrale Beobachter sind das auf keinen Fall, und das Wohl der breiten Bevölkerung haben die meisten von ihnen auch nicht im Blick. Wir leben aber in einer Demokratie. Deren Politik muss natürlich die Beschränkungen der Realität anerkennen, aber sie darf nicht grundlos Macht an nicht legitimierte Gruppen abgeben.

Zweitens schwingt beim Gedanken an Finanzierung und Kredite immer automatisch mit, dass das Geld zurück gezahlt werden soll, womöglich noch mit Gewinn. Effizienz ist natürlich auch für demokratische Politik ein sinnvolles Ziel, aber Profitwirtschaft darf kein Ziel sein. Außerdem gibt es gute Gründe dafür, dass der Staatsaushalt im langfristigen Mittel gar nicht ausgeglichen werden darf. Es kann vereinzelt Perioden geben, in denen ein Überschuss im Staatshaushalt sinnvoll ist. Aber im langfristigen Mittel muss ein inflationsneutraler Staatshaushalt von normalen, monetär souveränen Staaten im Defizit sein.

Besser also, wenn man erkennt, dass der Kaiser keine Kleider hat. Inflationsprobleme kann es für monetär souveräne Staaten geben, Finanzierungsprobleme nicht.

Zurück zum BGE. Ich finde das Konzept sympathisch, aber ich teile die Bedenken, dass ein BGE vermutlich wegen der Inflationsproblematik nicht so realisierbar ist, wie sich die Befürworter das wünschen. Je näher die Roboterutopie kommt, um so realitischer wird ein BGE natürlich. Ich bezweifle, dass wir heute schon so weit sind, muss aber zugeben, dass es letztlich eine empirische Frage ist, die man nur experimentell beantworten kann.

Und als kleines Nachwort noch: Die Überlegungen zum Staatshaushalt oben gehen von einem monetär souveränen Staat aus. Deutschland ist nicht mehr monetär souverän, sondern Mitglied der Eurozone. Diese hat keinen Souverän, und ich würde sagen, dass genau darin das Kernproblem der Eurozone liegt. Um die Eurozone langfristig politisch zu stabilisieren, bräuchte es einen Haushalt auf Euroebene, der wichtige Stabilisatorenaufgaben übernimmt. Dazu gehören auch Elemente des Sozialstaats, und die BGE-Befürworter täten gut daran, für ein BGE auf Euro-Ebene zu werben. Aber all das ist ein anderes Thema.

Freitag, November 11, 2016

Was Trump und Hitler (vielleicht) gemeinsam haben

Den zukünftigen US-Präsidenten mit Faschisten zu vergleichen ist nicht neu, aber eine Facette des Vergleichs habe ich bisher selten gesehen. In seiner Rede zum Wahlsieg hat Trump von groß angelegten Investitionsprogrammen gesprochen. Tatsächlich kann die USA das sehr gut gebrauchen. Schon seit Jahren beklagen Bauingenieure dort den schlechten Zustand der Infrastruktur, und natürlich wäre ein solches Investitionsprogramm gut für die Wirtschaft und könnte flächendeckend die Nachfrage nach Arbeit stärken.

Das ist wichtig, denn man muss sich klar machen, dass es ganze Schichten in den USA gibt, an denen die Erholung von der Wirtschaftskrise vollkommen vorbeigegangen ist. Diese Menschen beklagen sich zurecht über den Status Quo.

Das vermischt sich dann oft mit den für mich illegitimen Klagen von Weißen, die einfach nur Angst vor dem Verlust des gefühlten Privilegs der Mehrheit haben. Werdet endlich erwachsen!, möchte ich diesen Menschen zurufen. Aber wer sie dann deswegen als Rassisten abstempelt und den legitimen Teil ihrer Beschwerden schlicht ignoriert macht es sich auch zu einfach. Man riskiert damit nämlich genau den Aufstieg von Gefährdern wie Trump.

Die Parallele zu Hitler, dessen Regierungsprogramm ja trotz allem Negativen tatsächlich auch durch massive Investitionen erst einmal die Leben vieler Menschen verbessert hat, ist mir deswegen so wichtig, weil sie so unglaublich traurig ist. Warum konnten sich die Demokraten der Weimarer Republik nicht zu großen Investitionsprogramm zusammenreißen? Warum gelang es in den USA in den letzten Jahren nicht? Und warum gelingt es auch heute in Deutschland wieder nicht und schafft so den Nährboden für die AfD? Warum lassen liberale, progressive Parteien und Politiker ihre Flanken so ungeschützt? Man könnte ja durchaus die positiven Seiten eines expansiven und inklusiven Wirtschaftsprogramms übernehmen ohne deswegen gleich dem globalen Klimawandel die Tür zu öffnen, alle Juden zu vernichten, oder einen Weltkrieg anzuzetteln.

Wenn ich heute mit Menschen darüber rede, begegne ich leider immer wieder Fehlinformationen über unser Wirtschaftssystem. Bei Hitler heißt es sofort, das wäre ja alles in Wirklichkeit schlecht gewesen wegen der Schuldenaufnahme (dem zweiten beliebten Argument bei Hitler, nämlich der Kritik am Rüstungsfokus, stimme ich zu - aber es gibt so viele sinnvolle Dinge, in die man investieren kann, es muss wirklich nicht das Militär sein!). Auch im heutigen Deutschland ist die Ideologie der schwarzen Null das große Hindernis. Genauso haben in den USA in den letzten Jahren die Republikaner gerne mit Verweis auf das Haushaltsdefizit blockiert. Letzteres mag Zweifel aufbringen, ob es unter Trump große Investitionsprogramme geben wird, aber die Republikaner haben ja auch immer wieder bewiesen, dass ihnen Haushaltsdefizite nur so lange wichtig sind, wie sie damit demokratische Vorschläge blockieren können. Paul Ryans (republikanischer Speaker of the House) eigene Budgetentwürfe enthalten, wenn man sie nüchtern analysiert, immer gigantische Haushaltsdefizite. Vielleicht kommt Trump mit seinem Investitionsprogramm trotzdem nicht durch den Kongress, aber die Chancen stehen nicht schlecht.

In Wirklichkeit sind Schulden und Defizite für monetär souveräne Staaten schlicht kein Problem - zumindest nicht so, wie die meisten Menschen das zu wissen glauben. In der Eurozone verkompliziert die fehlende Souveränität die Situation, aber das ist ein Thema für ein andermal.

Natürlich ist ein Investitionsprogramm alleine nicht genug. Auch an Bildung muss gearbeitet werden und an regionalen Strukturen, und sicherlich an noch mehr. Aber ein Investitionsprogramm ist ein guter, klar sichtbarer und medienwirksamer Anfang, mit dem es einfach ist, in die richtige Richtung zu gehen.

Unsere Demokratie ist zu wichtig, um sie einer ökonomischen Ideologie zu opfern.

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) {
   use(v);
 }

 ... cannot be transformed to ...

 bool cond = ...;
 if (other_cond) {
   use(ballotARB(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]

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.

Sonntag, Januar 24, 2016

History of internet culture in acronyms

I've been on the internet for a pretty long time now. At least for me, getting on the internet back in the 90s meant making myself familiar with its "local" culture, customs and traditions. I'm sure that is still the case for many today. Curiously, I started to notice the appearance of acronyms that I wasn't familiar with, and I thought it interesting to consider how changing acronyms reflect broader changes of internet culture.

Back in the old days, a large fraction of what the internet was about was more or less serious, text-based discussion among relatively small groups. This shows in acronyms that facilitate such discussion, like AFAIK (as far as I know) or IM(H)O (in my (humble) opinion). Of course, social interactions could be rough back then as well: for every IMHO there's an IMNSHO (in my not so humble opinion), and of course there is the tradition of telling people to RTFM (read the f{ine, ucking} manual).

The acronyms that I did not recognize at first reflect an internet that has changed. MFW (my face when) reflects a culture of image reaction macros that were made possible by higher bandwidth. ICYMI (in case you missed it) certainly developed as the internet became a mass communication medium where shared stories and memes roll around. Similarly, ITT (in this thread) is a pattern where the author of a posting tries to set themselves apart from the "herd" of others in the thread, clearly a reaction to the increased size of groups and increasing anonymity in which the interactions often take place.