Problem set 2

In this problem set we start designing the logic of five x86 instructions.
Do not consider prefixes for any of the instructions.

Part 1

Describe, using register transfer notation (RTN), the functionality of the following subset of the Intel x86 architecture:

• Instructions: ADD, OR, MOV, BTC, JMP.
• Addressing Modes, using ModR/M : Immediate, Register, Base+Displacement.
• Data Types: Double Word (at least one operand must be 32 bits).
• MOV Do not implement moffs variations, nor Control Register variants.
• You must specify the RTN for each variant of each instruction that meets the previous requirements.

For detailed information about addressing modes/instructions refer to the x86 ISA manuals.

Additional Clarifications:
SIB byte addressing modes are not required for this problem set.
We always use 32-bit addressing, never 16-bit addressing.
We also simplify x86 memory addressing by avoiding the GDT. Any time an instruction accesses memory, you have to build the address based on base+displacement as specified in the Mod R/M byte of the instruction, and add the Segment Register shifted 16 bits. The Segment Register is always DS unless the stack is being accessed (e.g., push and pop instructions or any other instruction using EBP or ESP as the base register) in which case SS is the default. Note that the default Segment Register can also be overridden with a specific instruction prefix (not used in this problem set).

Example

ADD (opcode 81 /0 id): ADD r/m32, imm32

MEM[GPR + SegR<<16] <- MEM[GPR + SegR<<16] + imm32
GPR <- GPR + imm32
MEM[GPR + disp32 + SegR<<16] <- MEM[GPR + disp32 + SegR<<16] + imm32 
MEM[GPR + SEXT(disp8) + SegR<<16] <- MEM[GPR + SEXT(disp8) + SegR<<16] + imm32
MEM[disp32 + SegR<<16] <- MEM[disp32 + SegR<<16] + imm32

Part 2

On paper, design the data path and an accompanying state diagram to implement the subset of the x86 architecture described in Part 1 above.

Your state diagram should show all the relevant states.
That is, pay careful attention to each phase of the instruction cycle, and all the processing that must go on to implement these instructions.
All addressing modes stated above need to be considered.

For this assignment you do not have to implement fetch or decode. Your data path may begin using decoded signals as input. Also, no cache memory is required.

For this assignment, we will not be concerned with interrupts or traps/faults for illegal situations. (That comes later!)

Part 3

Now, implement your design from Part 2 in Verilog. You may use any available library parts for this assignment. All available libraries are in the following directory:

Use Verilog to simulate and verify that your design works for at least one instruction. You can choose any instruction and addressing mode. You may add dummy modules (for example memory) to test your datapath. Submit waveforms to demonstrate the working of your datapath.

Part 4

For the design in Part 2, select an instance of each of the five instructions and choose an appropriate addressing mode for each. Calculate the expected number of cycles required to execute each of those five instructions. Start counting cycles at the beginning of an instruction's fetch cycle and end with that instruction's completion (for example, destination write). For purposes of this assignment only, assume 10 ns cycle time, single cycle cache access, 100 ns memory access time, data cache hit ratio of 0.80, instruction cache hit ratio of 0.95. Do not consider any tlb and page faults. Please show your calculations.

Note that the actual number of cycles required to execute your program will be substantially fewer, since you will be able to overlap instruction execution. (That's what pipelining has been all about for more than 30 years). But, for this assignment only, we will examine the execution times of each instruction individually.