BitBash


SUBLEQ-OISC: single instruction computing


This project has been featured on Hack-a-Day on 7/27/2011.

    An OISC (one instruction set computer) is an extremely simplified computer architecture. Instead of a fully-featured instruction set (also known as a complex instruction set), a OISC has only one operation; it is the RISC approach to computing taken to the extreme.

    A SUBLEQ computer based on the OISC model has only one instruction, eliminating the need for an opcode field in the instruction. The model specified below has a datapath width of 8 bits, but the instruction word is 24 bits wide, and is formatted in terms of memory locations it addresses.

    Instruction Byte Ordering
    SUBLEQ Instruction Format

    The SUBtract and branch if Less or EQual instruction is a fairly straightforward mathematical operation; It extracts the integers stored in memory at location [a] and location [b], subtracts the value of location [b] from location [a] and writes the result back into location [b]. If the result is an integer less than or equal to zero, the execution jumps to the instruction location pointed to by c, if not the next instruction in the ROM is executed.

    The SUBLEQ computer will be modeled in Xilinx ISE Webpack 13.2 using a schematic as the top-level module. It would be far easier to implement it as one Verilog module, but keeping it simple is the objective here.

    Why an OISC? It's the easiest model of a computer to build from components and still be understandable to a reader with only little experience in computer engineering.

    Design

    This implementation of the SUBLEQ computer will have two stages per instruction, fetch and execute.

    • Fetch: In this state, the computer will fetch the next instruction from the instruction memory (from hereon to be known as the instruction ROM) pointed to by the program counter PC and store it in the instruction register IR.
    • Execute: the computer would use the operands of the instruction to access the data memory (RAM) and extract the operands, subtract operand [b] from operand [a], and store the result in RAM location b. If the result is <= 0, the PC (program counter) is set to c (from the instruction), if not, PC is incremented.

    All integers will be stored in two's complement format. Since the SUBLEQ operation requires subtraction and the possibility that the result will be negative, the compuuter will be using two's complement integers exclusively (a detailed first look at two's complement notation is available.)

    Implementation

    The ALU

    The Arithmetic and Logic Unit is an integral part of a modern computer. For the purposes of the SUBLEQ computer, the design of the ALU is fairly straightforward; it only has to perform the subtraction operation and to signal that the answer is negative or zero. As such, it will be a purely combinational logic element.

    ALU Schematic
    Arithmetic and Logic Unit Schematic

    The implementation uses a ripple-carry adder (ADD8 (8-bit adder)) element to illustrate the ease of performing subtraction in the two's complement format. Simply invert all the bits of the minuend using INV8 and add it to the subtrahend and add in 1 (the carry-in input is wired to +VCC to show that the carry in is permanent - the ALU only does subtraction and comparison.) Overflows are disregarded for the sake of simplicity. The output of the subtraction operation is compared to (00000000 in binary) by the comparator (COMP8) to check if it's zero. A simple OR gate ensures that LEQZERO will only be active when either the output is zero, or the MSB of the answer is positive. (A set MSB will indicate that the output is a negative integer.)

    Testing the ALU is rather simple with a Verilog test fixture. Running the simulation for about 0.2ms in simulation time (or well over 2 million samples) satisfies that there are no errors in logic.

    ALU Testbench.v - Verilog
    1. /* Verilog test fixture created from schematic D:\experimental\subleq\subleq\alu.sch
    2.   - Sun Jul 24 11:10:51 2011
    3. 2011 Hasith Vidanamadura, hasith.vidanamadura.net.*/
    4. `timescale 1ns / 1ps
    5.  
    6. module alu_alu_sch_tb();
    7.  
    8. // Inputs
    9. reg [7:0] B;
    10. reg [7:0] A;
    11. reg CLK;
    12.  
    13. // Output
    14. wire LEQZERO;
    15. wire [7:0] O;
    16.  
    17. // Bidirs
    18.  
    19. // Instantiate the UUT
    20. alu UUT (
    21. .B(B),
    22. .A(A),
    23. .LEQZERO(LEQZERO),
    24. .O(O)
    25. );
    26.  
    27. /* Initialize Inputs. Start A and B from different values to achieve the full coverage.*/
    28. initial begin
    29. B = 0;
    30. A = 8'hf0;
    31. CLK=0;
    32. end
    33.  
    34. /*automated testing block, signals only if there is an error.*/
    35.  
    36. always @(posedge CLK)
    37. begin
    38. A = A+1;
    39. B = B+1;
    40. #1;
    41. /*if the output is NOT the difference between A and B, log an error*/
    42. if (~(O == (A - B)) ||
    43. ~(LEQZERO == (O[7] | (O==8'b0))))
    44. begin
    45. $display("error! A=%b B=%b O=%b", A, B, O);
    46. end
    47. end
    48.  
    49.  
    50. /*generate a clock signal for the testing block to keep track of time.*/
    51. always begin
    52. #10 CLK=~CLK;
    53. end
    54.  
    55.  
    56. endmodule

    Multiplexer

    This piece of logic performs a simple yet critical task. When the select line is HIGH, the outpusst values reflects the input values at port A continuously. When the select line is LOW, the output values mirror the inputs at port B (read more about the mux at Wikipedia.)

    2x1 Multiplexer - Verilog
    1. timescale 1ns / 1ps
    2. ////////////////////////////////////////////////////
    3. // Engineer: Hasith V.
    4. //
    5. // Create Date: 21:17:46 07/20/2011
    6. // Design Name: SUBLEQ-OISC
    7. // Module Name: mux_2x1
    8. // Project Name: SUBLEQ
    9. /////////////////////////////////////////////////////
    10. module mux_2x1(
    11. input [7:0] A,
    12. input [7:0] B,
    13. input sel,
    14. output [7:0] out
    15. );
    16. assign out = (sel)? A: B;
    17. endmodule
    18.  
    19.  
    20.  

    Program Counter:

    This register keeps track of where in the ROM the current instruction is located. Updating the PC is done only when the execution of the current instruction is complete.

    Program Counter - Verilog
    1. `timescale 1ns / 1ps
    2. ////////////////////////////////////////////
    3. // Engineer: Hasith Vidanamadura
    4. //
    5. // Create Date: 21:09:51 07/20/2011
    6. // Design Name: Program Counter Register
    7. // Module Name: pc_reg
    8. // Project Name: SUBLEQ-OISC
    9. /////////////////////////////////////////////
    10.  
    11. module pc_reg(
    12. input [7:0] PCnew,
    13. output [7:0] PC,
    14. input WE,
    15. input RST,
    16. input CLK
    17. );
    18. reg [7:0] PCinternal;
    19. always @(posedge CLK)
    20. //on the positive edge of the clock
    21. begin
    22.  
    23. //if reset signal is asserted, go back to
    24. //Instruction 1
    25. //(instruction 0 is a HLT instruction)
    26.  
    27. if (RST)
    28. PCinternal <= 8'b1;
    29.  
    30. if (WE)
    31. //if WE is held high, update the value of PC
    32. PCinternal <= PCnew;
    33. end
    34.  
    35. //PC (the output) mirrors the internal registers.
    36. assign PC =PCinternal;
    37.  
    38. endmodule
    39.  
    40.  
    41.  

    Instruction Register (IR)

    This registers fetches the current instruction from the ROM whenever the EN line is asserted and latches the value until told to reset (RST) or until EN is asserted again.

    Instruction Register - Verilog
    1. `timescale 1ns / 1ps
    2. //////////////////////////////////////////////////////////////////////////////////
    3. // Engineer: Hasith Vidanamadura
    4. //
    5. // Create Date: 21:22:43 07/20/2011
    6. // Design Name: SUBLEQ-OISC
    7. // Module Name: ireg_24
    8. // Project Name: Instruction Register
    9. //////////////////////////////////////////////////////////////////////////////////
    10. module ireg_24(
    11. input [23:0] instr_in,
    12. input EN,
    13. output reg [23:0] instr_out,
    14. input CLK,
    15. input RST
    16. );
    17.  
    18. /*on the positive edge of the clock,
    19. or if RST is triggered*/
    20.  
    21. always @(posedge CLK or posedge EN) begin
    22. if (RST)
    23. // highest priority
    24. instr_out <=24'b0;
    25. else if (EN)
    26. instr_out <= instr_in;
    27. end
    28.  
    29. endmodule
    30.  
    31.  
    32.  

    Dual Port RAM

    This is a Verilog implementation of a dual port RAM, allowing two RAM locations to be read simultaneously. Only one write can be done at once, and only when WE is held HIGH, and there are 256 bytes of RAM. The initial block initializes the RAM with values read in from a file named 'data.ram'.

    Instruction Register - Verilog
    1. `timescale 1ns / 1ps
    2. ////////////////////////////////////////
    3. // Engineer: Hasith Vidanamadura
    4. // Create Date: 20:48:27 07/20/2011
    5. // Design Name: Dual-port RAM
    6. // Module Name: dp_ram
    7. // Project Name: SUBLEQ-OISC
    8. ////////////////////////////////////////
    9. module dp_ram(
    10. input [7:0] addrA,
    11. input [7:0] addrB,
    12. output [7:0] dataA,
    13. output [7:0] dataB,
    14. input [7:0] addrC,
    15. input [7:0] dataC,
    16. input WE,
    17. input CLK
    18. );
    19. reg [7:0] selA, selB;
    20. reg [7:0] MEM [0:255]; //255 memory entries
    21.  
    22. //read RAM intialization file into memory.
    23. initial begin
    24. $readmemh("basicram.mem", MEM);
    25. end
    26.  
    27. always @(posedge CLK)
    28. begin
    29. //WE strobe on positive edge of clock?
    30. if (WE)
    31. begin
    32.  
    33. //store DataIn at mem[address C]
    34. MEM[addrC] <= dataC;
    35.  
    36. end
    37. //store the addresses on posedge
    38. selA <= addrA
    39. selB <= addrB;
    40. end
    41. //connect the outputs of the inferred BRAM to the outputs DataOutA and DataOutB
    42. assign dataA = MEM[selA];
    43. assign dataB = MEM[selB];
    44.  
    45. endmodule
    46.  

    Instruction ROM

    The instruction ROM holds all the instructions necessary for the SUBLEQ computer to work. Instead of typing them in by hand, the initiad begin block reads in the contents of a text hex file into the registers, which is very convenient. The operational features of the ROM mirrors that of the RAM; it reads the instruction at the location pointed to by addr.

    Instruction ROM - Verilog
    1. `timescale 1ns / 1ps
    2. //////////////////////////////////////////////////////////////////////////////////
    3. // Company:
    4. // Engineer:
    5. //
    6. // Create Date: 21:15:44 07/20/2011
    7. // Design Name:
    8. // Module Name: rom_256
    9. // Project Name:
    10. // Target Devices:
    11. // Tool versions:
    12. // Description:
    13. //
    14. // Dependencies:
    15. //
    16. // Revision:
    17. // Revision 0.01 - File Created
    18. // Additional Comments:
    19. //
    20. //////////////////////////////////////////////////////////////////////////////////
    21. module rom_256(
    22. input [7:0] addr,
    23. input CLK,
    24. output [23:0] data
    25. );
    26. reg [23:0] IMEM [0:255];
    27. initial begin
    28. $readmemh("basicrom.mem", IMEM);
    29.  
    30. end
    31. assign data = IMEM[addr];
    32.  
    33. endmodule
    34.  

    Sequencer

    To arbitrate the rest of the system, the sequencer cycles through the two states fetch and execute in rapid succession, using two D-flip flops to satisfy the need for three defined states (and one unused state.)

    Core Sequencer
    Core Sequencer Schematic

    Asserting RST at any point in time will reset both flip flops to zero, so STATE0 is defined as 00b. The need for a separate post-reset state is to allow the next state (FETCH ) to run for one complete clock cycle. Each flipflop is fed a combination of logic known as the next state equations (for more information, breeze through synchronous logic.)

    At the first positive CLK edge after RST, the sequencer will then transition through STATE1 (01b) and STATE2 (10b), looping back to STATE1 and continuing indefinitely. STATE4 (11b) is unused, however, if by accident (or random gamma ray strike) the state machine transitions to STATE4, it will then transition back to STATE0 and then resume its normal cycle.

    Assembly

    Now that all the components have been introduced, here's how they fit together:

    Core Schematic
    Complete Schematic

    PC_incrementer is a simple module that increments the input by 1 every time the enable signal is asserted. The multiplexer selects either the incremented PC or the c operand of the instruction depending on the value of LEQZERO. Remember that LEQZERO will be asserted only if the output of the ALU is less than or equal to zero, so that the value passed to the new value of PC will be operand c if LEQZERO is HIGH.

    Other than that, the rest of the layout is self-explanatory. ireg_24 only stores the output of the next instruction when FETCH is HIGH, and therefore there is only one instruction per CPU cycle. The RAM is hardwired to write the answer of RAM[a] - RAM[b] back into RAM[b], and only do so on the rising edge of CLK.