Arithmetic Logic Unit Wiki

Overview

An arithmetic logic unit (ALU) is a hardware block that performs arithmetic and logical operations on integer binary numbers. In a conventional processor pipeline, the ALU is the execute-stage functional block that combines register values, immediate data from the instruction, and numeric constants to produce a result that is then consumed by the memory and write-back stages. Specialized implementations reported in the literature include reversible ALUs for quantum arithmetic and superconductor-based ALUs. Empirical fuzzing of processor RTL has additionally shown that incorrect ALU flag-generation logic is a non-trivial source of security-relevant defects. [ALU overview]

Symbolic representation

An ALU is commonly described with two N-bit input operands A and B, an operation select OP, and an N-bit result R. The result R is the value produced by applying the operation indicated by OP to the operands A and B. ALUs of varying complexity may additionally expose status and control bits beyond the inputs and outputs shown above. [Symbolic representation]

Typical ALU operations

Reported verification workloads target two arithmetic operations — addition with carry (ADD) and subtraction (SUB) — and four bitwise operations: AND, OR, XOR, and NOT. The principles used to generate stimuli for these operations can be generalized to other arithmetic or bitwise operations and to operations such as cyclic redundancy check (CRC) generation. [Typical ALU operations]

Role in a conventional processor (Y86-64)

In the Y86-64 reference designs documented in CMU-CS-18-122, the ALU is the data-path block in the execute stage of the SEQ sequential implementation. The execute stage has inputs labeled ALU A and ALU B, an ALU fun. control input, a condition-code output (CC), and an ALU result output valE. The condition codes are also used for branch-condition evaluation in the execute stage. [ALU role in SEQ]

Inputs

The ALU operates on some combination of:

values read from the register file,
immediate data carried in the instruction, and
numeric constants (for example, those used to compute the next sequential PC or a branch target). [ALU operands]

Operations

The ALU can perform either addition or the operation called for by an arithmetic or logical instruction. [ALU operations]

Place in the per-cycle flow

Within a SEQ clock cycle, the overall flow proceeds as follows: ten bytes are fetched from instruction memory (not all are used), the address of the next sequential instruction is computed by incrementing the PC, up to two values are read from the register file, the ALU is executed, a value can optionally be written to or read from data memory, some combination of the memory result and the ALU result is written back to the registers, and finally the PC is set to the address of the next instruction (the incremented old PC, a branch target, or a return address read from memory). The ALU sits between the register-read stage and memory access/write-back. [ALU position in flow]

Pipelined variant

PIPE is a five-stage pipelined implementation of the Y86-64 instruction set. Both SEQ and PIPE partition the computation into similar stages and use the same set of functional blocks, including the ALU. PIPE adds pipeline registers so that up to five instructions can be in the pipeline simultaneously, each in a different stage, and adds data connections and control logic to resolve data- and control-hazards. [PIPE / Y86-64 implementation context]

ALU flag-generation logic and correctness

In addition to producing the arithmetic/logical result, ALUs compute condition flags such as the carry and overflow flags. Empirical fuzzing of processor RTL against a golden reference model, as reported in TheHuzz (USENIX Security '22), found several flag-generation defects in OpenRISC ALUs:

Bug B5 (mor1kx): incorrect implementation of the carry-flag logic for subtract operations. Mutating subtract-instruction data bits triggered a mismatch between the RTL and the golden reference model, which can cause incorrect computations including those used in cryptographic functions. Detected with 20 inputs; classified as a core-and-compute issue (CWE-1201). [Bug B5 carry flag]
Bug B9 (mor1kx): incomplete update logic for the overflow bit on multiply-and-subtract (MSB) and multiply-and-accumulate (MAC) instructions, so software relying on overflow detection fails to detect overflow events. Detected with 3.35 × 10³ inputs (CWE-1201). [Bug B9 overflow MSB/MAC]
Bug B10 (mor1kx): incorrect implementation of the overflow-flag logic for subtract instructions, which can compromise security mechanisms that rely on the overflow flag. Detected with 2.21 × 10⁴ inputs (CWE-1201). [Bug B10 overflow subtract]

These results indicate that ALU flag logic is a non-trivial source of defects with security-relevant consequences.

ALU functional verification

Functional verification checks the correctness of a system by comparing its inputs and outputs against a reference model that implements the same specification. A verification environment for an ALU measures code coverage through metrics such as statements, branches, expressions, conditions, and states, and determines when the ALU is sufficiently verified. Corner cases (e.g., all zeros or all ones in operands and result) are also checked, and probability values can be tuned to increase the ability to generate these combinations. [Functional verification of ALU]

Stimulus generation with a probabilistic constrained grammar

A universal stimuli generator (USG) has been developed that, in addition to generating random input operands, can also generate the expected result in the same stimulus, using a probabilistic constrained grammar (PCG). For ALU verification, an 8-bit operand width is used and the grammar is divided into three sections — Input values, Logic, and Result — with rules applied sequentially and a context that is preserved between bits. For the addition with carry (ADD) operation, the truth table for each result bit depends on the two operand bits and on whether the carry-in bit is set; rules for the carry-out are generated accordingly. [PCG stimulus generation]

Instruction-template–based stimulus generation

An alternative verification approach uses instruction templates combined with design equations for system registers, general registers, and instructions to generate expected results specific to the integrated-circuit design under test. The method can incorporate the behavior of system elements such as arithmetic logic units, integer units, floating-point units, load/store units, cache and memory units, and input–output controllers so that the verification covers both the execution pipeline and the cooperating system elements. A representative ADDC template, for example, specifies operands and a sequence of operand values covering boundary cases such as 0x00000000, 0x00000001, 0x80000000, 0x80000001, 0xFFFFFFFF, 0x7FFFFFFF, and 0xa5a5a5a5. [Instruction-template–based stimulus generation]

Specialized ALU implementations

Reversible ALU for quantum arithmetic

Reversible logic has been used to construct a reversible arithmetic logic unit for quantum arithmetic (arXiv:1107.3924). The proposed reversible ALU provides explicit constructions that effect basic arithmetic operations. With the corresponding control unit, the reversible ALU can combine classical arithmetic and logic operations in a reversible integrated system. The work is cited as actual evidence of the realizability of a reversible programmable logic device (RPLD). [Reversible ALU for quantum arithmetic]

Superconductor ALU

A 4-bit ALU has been implemented in superconductor technology using a bit-parallel architecture designed for minimal fan-in/fan-out and optimal latency (arXiv:2312.09386). Reported characteristics include:

a clock frequency exceeding 30 GHz;
power consumption of 4.75 mW, including applied reverse current and encompassing static and dynamic components;
more than 9000 Josephson junctions, of which approximately 7000 are used for wiring, delay lines, and path balancing;
a bias margin above 18%;
operation inside a 4 K pulse-tube cryocooler;
a co-processor design that interfaces with external CMOS memory and processors via interface circuits.

The ALU was fabricated using a standard commercial process. Digital and analog simulations were used to validate the design, and experimental verification confirmed successful operation of both the arithmetic and logic units. [Superconductor ALU]