Friday, August 5, 2011

PEDAGOGY: How to Design an x86-like Processor

In switching from RISC to x86 with our Introduction to Computer Systems course, we had an advantage over traditional computer architecture courses in that we didn’t have to worry about how to actually implement a processor.  We could skip all the complexities of instruction formats and instruction encoding, which is definitely not pretty with x86.  When it came time to write our chapter on processor design (Chapter 4) of Computer Systems:  A Programmer's Perspective, we had to confront this unpleasant aspect of x86.  Here we did a bit of a sleight of hand, creating a new instruction set we called “Y86” (get it?).  The idea was to have a notation that looked like x86, but was simple to decode and could be executed by an in-order pipelined processor.  Thus, we limited the addressing modes and made it so that arithmetic instructions could only operate on registers, but we retained the stack-oriented procedure execution conventions.  We also used a very simple encoding.  This made it feasible to go through the entire implementation of two processors---one executing a complete instruction every clock cycle, and one based on a 5-stage pipeline---in a single chapter.  We could even generate complete a Verilog implementation of the pipelined processor and map it through synthesis tools onto an FPGA.  I’ll admit that this approach is a compromise from our goal of presenting real machines executing real programs, but it seems to have worked fairly well.

Interestingly, in their textbook Digitaltechnik—Eine praxisnahe Einführung (Digital Technology, a Practical Introduction), Armin Biere and Daniel Kroening present the design of a processor that executes a subset of the Y86 instructions using the actual IA32 encodings of the instructions.

Apparently, we weren’t the only ones to think of the name “Y86” as a variant of “x86.”  Randall Hyde introduces a stripped down 16-bit instruction set, which he names “Y86” in his book Write Great Code, published in 2004, several years after the first edition of CS:APP came out.

The domain names “” and “” are already taken, but it looks like they’re been occupied by a cybersquatter named Richard Strickland since 2003.  Perhaps he’s just waiting for us to buy him out!

Randy Bryant

No comments:

Post a Comment