Schaltnetze

Aus Gattern werden Bausteine: Ein Decoder wählt eine von vielen Leitungen, ein Multiplexer lässt genau ein Signal durch, eine Kette von Volladdierern rechnet mit ganzen Zahlen – und aus allem zusammen entsteht die ALU, das Rechenwerk der CPU.

Lesestand

Ein Schaltnetz (kombinatorische Schaltung) ist eine Verschaltung von Gattern ohne Rückkopplung: Die Ausgänge hängen nur von den aktuellen Eingängen ab, nach einer kurzen Laufzeit stellt sich das Ergebnis ein. Ein Schaltnetz hat kein Gedächtnis – das kommt erst mit den Schaltwerken in H5.

Aus wenigen Grundbausteinen entsteht alles Weitere: Ein Decoder macht aus einer Binärzahl genau eine aktive Leitung, ein Multiplexer wählt eines von mehreren Signalen aus, ein Volladdierer addiert drei Bits. Viele Volladdierer hintereinander addieren ganze Zahlen; mehrere Recheneinheiten nebeneinander plus ein Multiplexer ergeben die ALU – und der Opcode eines Maschinenbefehls ist nichts anderes als die Auswahlleitung dieses Multiplexers.

Decoder und Multiplexer

Ein Decoder mit n Eingängen hat 2ⁿ Ausgänge, von denen immer genau einer 1 ist – der, dessen Nummer an den Eingängen anliegt. Jeder Ausgang ist ein UND der passend negierten Eingänge, genau die Minterme aus H3. Ein Multiplexer nutzt den Decoder, um von mehreren Dateneingängen genau einen zum Ausgang durchzulassen: Jeder Dateneingang geht durch ein UND mit „seiner“ Decoderleitung, dann ein ODER über alle.

Der Multiplexer ist das switch der Hardware: Die Auswahlbits entscheiden, was durchkommt. Sein Gegenstück, der Demultiplexer, verteilt umgekehrt ein Signal auf eine von mehreren Leitungen – etwa einen Schreibbefehl auf genau eine Speicherzelle. Arbeitet man mit 16 Bit breiten Werten, legt man einfach 16 Multiplexer nebeneinander, die dieselben Auswahlbits teilen. Ein solches Bündel paralleler Leitungen heißt Bus.

Addieren: Volladdierer und Übertragskette

Ein Volladdierer addiert drei Bits – zwei Ziffern und den Übertrag von rechts – und liefert ein Summenbit und einen neuen Übertrag. Mit den Funktionen aus H3: Die Summe ist die ungerade Parität der drei Bits, der Übertrag ihre Mehrheit. Schaltet man acht Volladdierer hintereinander, wobei jeder seinen Übertrag an den linken Nachbarn weitergibt, entsteht ein 8-Bit-Addierer – ein Ripple-Carry-Addierer. Der Übertrag „rieselt“ dabei von rechts nach links:

Das Problem der Kette: Im schlimmsten Fall muss der Übertrag durch alle Stufen laufen, bevor das oberste Bit stimmt. Bei 64 Bit wären das 64 Stufen hintereinander – zu langsam für einen Prozessor, der Milliarden Additionen pro Sekunde schaffen soll. Echte Addierer berechnen die Überträge deshalb vorab (Carry-Lookahead): Aus a und b sieht man jeder Stelle an, ob sie einen Übertrag erzeugt (beide 1) oder weiterreicht (genau eine 1). Daraus lassen sich alle Überträge in Gruppen parallel bestimmen; die Laufzeit wächst dann nur noch logarithmisch mit der Bitbreite – auf Kosten von mehr Gattern.

Subtrahieren ohne Subtrahierer

Für die Subtraktion braucht es keine eigene Schaltung. Im Zweierkomplement (H1) ist −b dasselbe wie „alle Bits von b umdrehen, plus 1“. Also: a − b = a + ¬b + 1. Die Bits dreht man mit XOR-Gattern um, die 1 kommt als Übertrag in die unterste Stufe. Eine einzige Steuerleitung schaltet so zwischen Addieren und Subtrahieren um.

Die ALU

Die arithmetisch-logische Einheit fasst alles zusammen: Addierer, Subtrahierer, bitweise Logik und Schieber liegen nebeneinander und rechnen alle gleichzeitig mit denselben Eingängen. Ein Multiplexer wählt am Ende das gewünschte Ergebnis aus. Die Auswahlleitung ist der Opcode – hier dieselben Nummern wie bei der Lehrmaschine aus H2:

Das ist die Antwort auf die Frage, wie ein Befehl wie 1CAB ausgeführt wird: Die Steuerung schaltet RA und RB auf die Eingänge der ALU, legt die Ziffer 1 an den Multiplexer und das Ergebnis nach RC. Wie das Ergebnis dort gespeichert wird und wer die Leitungen im richtigen Moment schaltet, zeigen H5 und H6.

Für Entwickler übersetzt

Viele Bausteine haben eine direkte Entsprechung in Java – und der JIT-Compiler nutzt manche davon, um Sprünge zu vermeiden:

// Multiplexer: der Bedingungsoperator
int m = sel ? x : y;              // JIT: oft bedingter Move (cmov), kein Sprung

// Multiplexer ohne Verzweigung, rein mit Bitlogik
int maske = -(sel ? 1 : 0);        // alle Bits 1 oder alle 0
int m2 = (x & maske) | (y & ~maske);

// Decoder: aus einer Zahl genau ein gesetztes Bit
int eins = 1 << nummer;

// Volladdierer aus Bitoperationen
int summe   = a ^ b ^ cin;
int uebertr = (a & b) | (a & cin) | (b & cin);   // Mehrheit

// Direkt in Hardware – der JIT setzt einzelne Befehle ein
Integer.bitCount(x);               // Anzahl gesetzter Bits (Parität: bitCount & 1)
Integer.numberOfLeadingZeros(x);   // höchstes gesetztes Bit
Math.multiplyHigh(a, b);           // obere 64 Bit eines 128-Bit-Produkts

Methoden wie Integer.bitCount sind sogenannte Intrinsics: Der Java-Code dahinter ist nur der Ersatz. Auf Prozessoren, die einen passenden Befehl haben, ersetzt der JIT den ganzen Aufruf durch genau diesen einen Befehl – also durch ein spezielles Schaltnetz in der CPU.

Häufige Irrtümer

„Die ALU berechnet nur die gewählte Operation.“ – Meist rechnen alle Einheiten parallel, und der Multiplexer wählt aus. Das ist einfacher und schneller, als erst zu entscheiden und dann zu rechnen.

„Schaltnetze liefern ihr Ergebnis sofort.“ – Jedes Gatter braucht eine winzige Zeit, bis sein Ausgang umschaltet. Die längste Gatterkette bestimmt, wie hoch die Taktfrequenz sein darf.

„Für Subtraktion, Vergleich und Negation braucht man jeweils eigene Schaltungen.“ – Alles läuft über den Addierer: Subtrahieren ist Addieren des Komplements, Vergleichen ist Subtrahieren und auf Vorzeichen und Null prüfen.

„Multiplikation ist einfach eine weitere Einheit wie die Addition.“ – Ein Multiplizierer ist um Größenordnungen aufwendiger, im Grunde viele Addierer übereinander. Lange hatten kleine Prozessoren gar keinen und multiplizierten in Software.