Skip to content
STIMSMITH

Bryant-O'Hallaron Computer Systems Textbook

Paper WIKI v1 · 5/26/2026

The Bryant-O’Hallaron textbook is cited as the source for the Y86-64 instruction set, its sequential SEQ processor, and a five-stage pipelined PIPE implementation. In the cited verification report, the textbook’s Y86-64 material serves as the basis for formal verification of seven PIPE variants against SEQ.

Overview

The Bryant-O’Hallaron textbook presents the Y86-64 instruction set and a pipelined implementation of a Y86-64 processor. It also includes homework problems that modify the pipeline, yielding a total of seven variants considered in a later formal verification report. [C1]

Y86-64 architecture coverage

The textbook’s Y86-64 model includes programmer-visible state similar to x86-64: program registers, condition codes, the program counter, and data memory. The model also includes an exception status word for exceptional conditions. [C2]

The Y86-64 instruction encodings range from one to ten bytes. An instruction consists of a one-byte instruction specifier and may also include a one-byte register specifier and an eight-byte constant word. The standard instruction set shown in the cited material includes operations such as halt, nop, register moves, immediate moves, memory moves, arithmetic/logical operations, jumps, calls, returns, stack operations, and conditional moves. [C3]

The textbook also uses function codes to distinguish ALU operations, jump conditions, and conditional move conditions. The optional iaddq instruction is described as a homework-extension instruction rather than part of the standard Y86-64 instruction set; it adds an immediate value to a destination register. [C4]

Instruction-set characteristics

The Y86-64 design has several CISC-like features: variable-length instruction encodings, condition-code side effects for arithmetic and logical instructions, condition-code-controlled branching and conditional moves, stack-based procedure calls, and instructions such as pushq and popq that both operate on memory and alter registers. [C5]

It also has RISC-like simplifications: arithmetic and logical instructions operate only on register data, addressing is limited to simple base-plus-displacement addressing, and instruction fields are encoded in simple and consistent ways across multiple instructions. [C6]

SEQ sequential implementation

The textbook presents SEQ as a sequential implementation of the Y86-64 ISA in which each execution cycle completes one instruction. In SEQ, the only state elements are those holding the Y86-64 architectural state; the datapath includes blocks for instruction decoding, PC incrementing, and ALU operations. Its control logic is described in HCL, a simple hardware control language. [C7]

During a SEQ cycle, execution starts with the current program counter, fetches up to ten instruction bytes, computes the next sequential PC, reads up to two register values, performs an ALU operation using register values, immediate data, or constants, accesses data memory when needed, writes results back to registers, and updates the PC from the incremented PC, a branch target, or a return address. [C8]

PIPE pipelined implementation and variants

The textbook’s PIPE implementation is a five-stage pipeline for the Y86-64 instruction set. PIPE partitions computation into stages similar to SEQ and uses the same functional blocks, but adds pipeline registers so that up to five instructions can be in flight simultaneously. It also requires extra data connections and control logic to handle data and control hazards. [C9]

The cited report identifies seven PIPE variants derived from the textbook material. The basic STD implementation handles execute-stage data hazards by forwarding into decode, stalls one cycle on load/use hazards, stalls three cycles for ret, and predicts branches as taken. Other variants add, modify, or remove instructions, forwarding paths, branch prediction policies, or register ports. [C10]

Role in formal verification work

In the cited verification report, SEQ is used as the reference implementation of the Y86-64 ISA, and the verification task is to determine whether SEQ and all seven PIPE variants are functionally equivalent. The task is simplified because SEQ and PIPE share many functional elements, such as instruction decoding logic and the ALU, differing mainly in PIPE’s additional pipeline registers and pipeline-specific control logic. [C11]

The report also notes that HCL descriptions of the control logic can be translated into multiple targets, including C simulation models, Verilog for synthesis, and UCLID/UCLID5 models for formal verification. Generating these artifacts from a common HCL representation helps maintain consistency between simulation, hardware descriptions, and formal models. [C12]

CITATIONS

12 sources
12 citations
[1] Textbook presents Y86-64, a pipelined implementation, and homework modifications yielding seven variants Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[2] Y86-64 programmer-visible state includes registers, condition codes, PC, data memory, and an exception status word Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[3] Y86-64 instruction encodings range from one to ten bytes and include instruction, register, and constant fields Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[4] Function codes specify ALU operations, branch conditions, and conditional move conditions; iaddq is an optional homework instruction Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[5] Y86-64 has CISC-like features including variable-length encodings, condition-code side effects, and stack-based calls Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[6] Y86-64 has RISC-like simplifications including register-only arithmetic/logical operations and simple base-plus-displacement addressing Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[7] SEQ executes a complete Y86-64 instruction per cycle and uses HCL-described control logic Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[8] SEQ cycle flow fetches bytes, reads registers, uses the ALU, accesses memory, writes registers, and updates the PC Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[9] PIPE is a five-stage Y86-64 pipeline with pipeline registers and hazard-handling logic Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[10] PIPE variants include STD, FULL, STALL, and other variants modifying instructions, forwarding, branch prediction, or register ports Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[11] Verification uses SEQ as the Y86-64 reference and checks functional equivalence against all seven PIPE variants Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5
[12] HCL translation supports consistency across simulation models, synthesizable hardware descriptions, and formal verification Formal Verification of Pipelined Y86-64 Microprocessors with UCLID5