Close
0%
0%

BREDSAC

Electronic Dynamic Storage Breadboard Computer

Public Chat
Similar projects worth following
This is an attempt to reimplement the historic EDSAC computer on breadboards using 74 series TTL and parts of a similar era.

What possessed me to do this?

Inspiration for this project came from two sources.

One is the effort underway at the National Museum of Computing in
Bletchley Park to build a replica of the EDSAC, one of the earliest
stored-program computers, built at Cambridge University in the late
1940s.

EDSAC Replica Project

The other is a series of videos by Ben Eater about the construction of
a simple computer on breadboards from 74 series logic chips.

Ben Eater's 8-bit Computer

Put these two things together, add in a hankering to do something with
hardware and a pile of parts burning a hole in the bottom of my junk
box, and the conclusion is obvious. I need to build a breadboard
implementation of the EDSAC!

bit_counter.png

Logisim - Bit counter

Portable Network Graphics (PNG) - 15.76 kB - 06/13/2018 at 06:37

Preview
Download

state_counter.png

Logisim - State counter

Portable Network Graphics (PNG) - 6.75 kB - 06/13/2018 at 06:37

Preview
Download

run_control_2.png

Logisim - Run control logic

Portable Network Graphics (PNG) - 15.12 kB - 06/13/2018 at 06:34

Preview
Download

BlockDiagram.png

Overall organisation of the computational logic.

Portable Network Graphics (PNG) - 48.38 kB - 06/07/2018 at 10:53

Preview
Download

BasicCycle.png

Diagram showing the basic short-word timing cycle of BREDSAC.

Portable Network Graphics (PNG) - 18.06 kB - 06/07/2018 at 10:51

Preview
Download

  • Memory Refresh and Scope Display

    greg.ewing11/25/2018 at 00:55 0 comments

    I've now implemented all the important instructions (I'm not going to bother with the Verify instruction, because it seems fairly useless), so it's time to move on to the dynamic memory refresh and oscilloscope display systems, which are closely related.

    The plan is to divide each BITCLK cycle into four phases, of which two are refresh/display cycles, one is a CPU read cycle and one is a CPU write cycle. The following timing diagrams show what happens during one BITCLK period when the CPU performs a read-only cycle and a read-modify-write cycle.
    The required timing and address signals are generated by the Master Timing and Refresh Counter circuits. They contain a bit counter that counts from 0 to 17 and a word counter that counts from 0 to 43. The first 32 word counts address the main memory to refresh it and generate data for the display. The next 12 word counts are used to read display data from the register file.

    Master Timing:
    Refresh Counter:
    The bit and word numbers from the refresh counter are rearranged and combined with a user-selected "tank" (memory page) number to produce addresses for the main memory and register files and control signals for the display. REFMA is the refresh address for the main memory. DSPREG selects one of the three register files and REFRFA selects a word from that file. DSPMR chooses whether to display data from the memory or the registers. DSPROW and DSPCOL indicate the row and column of the display for which data is being sent.
    The purpose of this particular arrangement is to generate a display laid out as illustrated below.
    These subcircuits are connected on the main circut as follows.
    Multiplexers have been inserted into the memory and register file address lines to switch been refresh and CPU addresses, and some other minor changes made to ensure that things happen in the right phases of the BITCLK cycle.
    I moved the latches on the outputs of the register files out of the register file subcircuit and put them before the X and Y ALU inputs, because I need the raw outputs from the registers to send to the display. Also, I realised that I don't need to gate the write input to the static RAMs with RUNCLK, because this is already done when generating TWRITE. The register file simulation subcircuit is now just:

    Testing the display circuit in Logisim

    In the actual machine, DSPROW and DSPCOL will be used to generate X and Y scanning voltages for the oscilloscope, but Logisim doesn't simulate analog circuitry, so I put together a digital display using an LED Matrix component for testing purposes. I built a driver subcircuit consisting of 22 row drivers, each of which contains 18 individually addressable one-bit registers.

    Row driver:
    I made the circuit symbol for the row driver one grid unit high, so that I could stack them up next to a decoder in the matrix driver (although this turned out not to help much, since I couldn't find a compact way to arrange the outputs).
    I designed the circuit symbol for the matrix driver to sit behind the LED matrix and provide a backdrop for it, as well as allowing two 18-wide matrices to be positioned side by side to form a 36 bit wide display.
    It took a bit of fiddling to get this to work properly, because the order in which Logisim draws overlapping components on a schematic seems to vary randomly depending on exactly how things are positioned, and to make things worse, it changes every time the circuit is reloaded from a file. But when the planets are aligned, it looks pretty good.

  • Input Instruction

    greg.ewing11/18/2018 at 22:29 0 comments

    Output Hardware Modification

    I made a small change to the output interface. I realised it was probably a bad idea to connect the OBSY signal from the output device directly to the ubranch multiplexer, because glitches could occur if it changes near a clock edge, so I added a flip-flop to synchronise it with the bit clock.


    Input Hardware

    The Input instruction reads a character from an input device (originally a paper tape reader) and stores it in the lower 5 bits of a memory location. To support this, I designed the following input interface. It consists of a 5-bit parallel-in serial-out shift register, and some logic to manage a pair of handshaking signals. INPUT RDY is asserted by the input device when there is data present, and INPUT ACK is pulsed by the CPU once the data has been accepted. The device is then expected to remove INPUT RDY and start reading the next character.


    Reading the input data is a two-step process: first the data is loaded into the input register in parallel, then it is shifted out serially and written to memory. Rather than use up two MISC values for this, I allocated one MISC value called INPT and used WMEM to distinguish between loading and shifting. This effectively gives me two control signals for the price of one.

    The INPUT RDY signal is synchronised with RUNCLK to produce IRDY, which is connected to an input of the microcode branch multiplexer. The serial output from the input register is connected to an input of the X multiplexer.

    For testing purposes, I connected INPUT RDY to a flip-flop that emulates the handshaking action of an input device.

    Other changes to the main circuit:

    Input Microcode

    INPT  = 011  # Load/shift input register depending on WMEM
    
    BIBSY = 011  # Input data not available
    
    # I - Input
       01000 0 0001 :  -   -   --  ---   -  --    --   --   -   -   -   -   -    -    -   ---     -   BIBSY  1000    # Loop until input data available
       01000 0 0010 :  -   -   --  ---   -  --    --   --   -   -   -   -   -    -    -   INPT    -   ---    ----    # Load data into input register
       01000 0 0011 :  -  EOI  --  XIN   -  --    --   --   -   -   -   -   -    -   WMEM INPT    -   ---    ----    # Write input register to memory
    

  • Output Instruction

    greg.ewing11/18/2018 at 01:07 0 comments

    The Output instruction takes the upper 5 bits of a memory word and sends it to an alphanumeric output device, originally a teleprinter. I'm not sure exactly what kind of output device I'm going to use yet, so at this stage I've just designed a rudimentary parallel output interface with a strobe output OSTRB and a busy input OBSY. It consists of a 5-bit transparent latch fed from outputs 13 to 15 of the S register, and gating to load it and generate the strobe pulse during T17 when MISC = OUTPT. The OBSY input is connected to the microcode branch multiplexer.

    I used a transparent latch instead of an edge-triggered one because I want the outputs to be valid before the trailing edge of the strobe. I found it necessary to gate the strobe with the second half of the bit clock cycle, to ensure that its trailing edge occurs while the inputs to the latch are still valid.

    For testing purposes, I also mocked up an emulation of a 5-bit teleprinter using a Logisim TTY component, a ROM to translate from EDSAC character codes to ASCII, and a flip-flop to keep track of the letters/figures shift state.

    This is how it all fits together on the main circuit.

    And here's the microcode. It loops until OBSY is not active, and then reads from memory into the S-register and loads the output latch.

    OUTPT = 101  # Load output register and send output strobe
    
    BOBSY = 101  # Output device busy
    
    # O - Output
       01001 0 0001 :  -   -   --  ---   -  --    --   --   -   -   -   -   -    -    -   ---     -   BOBSY  1000    # Loop until output device ready
       01001 0 0010 : SHS EOI  --  ---   -  --    --   --   -   -   -   -   -    -    -   OUTPT   -   ---    ----    # Read memory and perform output
    
    

  • A Well-Rounded Instruction

    greg.ewing11/16/2018 at 05:21 0 comments

    The Round instruction is meant to round the accumulator to 34 fractional bits, by adding 1 at bit 36 if bit 35 is 1. I managed to implement this without making any changes to the hardware. The strategy is to first shift word 1 of the accumulator left by one bit (by adding it to itself), so that bit 35 ends up in the carry flag, and then add the carry to words 2 and 3. Finally, words 0 and 1 are cleared.

    # Y - Round accumulator to 34 fractional bits
       00110 0 0001 :  -   -   10  XAC   -  YAC   CY0  --   -   -   -  LSW  -    -    -   ---     -   ---    ----    # Shift word 1 of AC left
       00110 0 0010 :  -   -   01  XAC   -  Y0    --   WAC  -   -   -   -   -    -    -   ---     -   ---    ----    # Add carry to AC words 2 and 3
       00110 0 0011 :  -   -   11  XAC   -  Y0    --   WAC  -   -  MSW  -   -    -    -   ---     -   ---    ----
       00110 0 0100 :  -   -   00  X0    0  Y0    CY0  WAC  -   -   -  LSW  -    -    -   ---     -   ---    ----    # Clear AC words 0 and 1
       00110 0 0101 :  -  EOI  10  X0    0  Y0    --   WAC  -   -   -   -   -    -    -   ---     -   ---    ----
    

  • Jump Instructions, and correcting an error

    greg.ewing11/15/2018 at 10:10 0 comments

    The original EDSAC had two conditional jump instructions (and no unconditional one!), namely Jump if Accumulator >= 0 and Jump if Accumulator < 0. For implementing these, I added a new MISC value called JUMP and two new UBCOND values for testing the SIGN output of the ALU, called BSGN0 and BSGN1.

    However, I didn't want to actually use these to perform microcode branching, because then a jump instruction would require up to two cycles, one to test the sign bit and one to load the PC if the test is true. To save a cycle, I arranged things so that JUMP suppresses microcode branching and instead activates a new signal LDPC during T17 if the microcode branch condition is true. This allows the jump to occur at the end of the same cycle that tests the sign.

    The microcode branch condition circuitry now looks like this:
    LDPC causes the program counter to be loaded from the address field of the instruction register:
    Here is the microcode for the jump instructions. Each one consists of just a single microinstruction that passes the accumulator through the ALU and activates JUMP together with the appropriate condition.

    JUMP  = 010  # Conditionally load PC from address field of instruction
    
    BSGN0 = 110  # Sign FF = 0
    BSGN1 = 001  # Sign FF = 1
    
    # E - Jump if accumulator >= 0
       00011 0 0001 :  -  EOI  11  XAC   -  Y0    CY0  --   -   -  MSW LSW  -    -    -   JUMP    -   BSGN0  ----
    
    # G - Jump if accumulator < 0
       11011 0 0001 :  -  EOI  11  XAC   -  Y0    CY0  --   -   -  MSW LSW  -    -    -   JUMP    -   BSGN1  ----
    

    Update to Transfer and Clear instructions

    While doing some more research into the EDSAC, I realised that my implementations of the Transfer and Clear instructions weren't quite right -- they were only clearing the parts of the accumulator that were being written to memory, whereas they are supposed to clear the whole accumulator. I've fixed them, but it means they now take 4 cycles to execute. This is annoying, but there doesn't seem to be anything I can easily do about it.

    # T - Transfer and clear
       00101 0 0001 :  -   -   00  XAC  CMX YAC   CY1  WAC  -   -   -  LSW  -    -    -   ---     -   ---    ----
       00101 0 0010 :  -   -   10  XAC  CMX YAC   --   WAC  -   -   -   -   -    -    -   ---     -   ---    ----
       00101 0 0011 :  -   -   01  XAC  CMX YAC   --   WAC  -   -   -   -   -    -    -   ---     -   ---    ----
       00101 0 0100 :  -  EOI  11  XAC  CMX YAC   --   WAC  -   -  MSW  -   -    -   WMEM ---     -   ---    ----
    
       00101 1 0001 :  -   -   00  XAC  CMX YAC   CY1  WAC  -   -   -  LSW  -    -    -   ---     -   ---    ----
       00101 1 0010 :  -   -   10  XAC  CMX YAC   --   WAC  -   -   -   -   -    -    -   ---     -   ---    ----
       00101 1 0011 :  -   -   01  XAC  CMX YAC   --   WAC EVN  -   -   -   -    -   WMEM ---     -   ---    ----
       00101 1 0100 :  -  EOI  11  XAC  CMX YAC   --   WAC ODD  -  MSW  -   -    -   WMEM ---     -   ---    ----
    

  • Multiply Instructions

    greg.ewing11/14/2018 at 07:19 0 comments

    Microcode for the single-word Multiply and Add instruction:

    # OPCODE L STAT : SHS EOI  RFA XSEL CMX YSEL CARRY WRF ODD SS1 MSW LSW MMSW MLSW WMEM MISC  INCMS UBCOND UBADDR
    
    # V - Multiply and add
       11111 0 0001 : SHS  -   00  X0    -  Y0    CY0  --   -   -   -   -   -    -    -   ---     -    ---    ----    # Read multiplier into S
       11111 0 0010 :  -   -   01  X0    -  YPR   CY0  WPR  -   -   -  LSW MMSW MLSW  -   RSH     -    ---    ----    # Multiply step word 2
       11111 0 0011 :  -   -   11  XMUL  -  YPR   CY0  WPR  -  SS1 MSW  -  MMSW MLSW  -   RSH   INCMS  010    0100    # Multiply step word 3
       11111 0 0100 :  -   -   01  XAC   -  YPR   CY0  WAC  -   -   -  LSW  -    -    -   ---     -    ---    ----    # Add product to AC word 2
       11111 0 0101 :  -  EOI  11  XAC   -  YPR   CY0  WAC  -   -  MSW  -   -    -    -   ---     -    ---    ----    # Add product to AC word 3
    

    When I came to do the double-word version, I discovered an error in the ALU. It was treating bit 17 of the low word of the multiplicand as a sign bit and triggering subtraction. The following ALU update fixes this by gating MLAST with MMSW.

    The microcode for double-word Multiply and Add consists of two four-cycle loops, one for each half of the multiplicand, followed by a final four cycles to add the Product Register to the Accumulator.

       11111 1 0001 : SHS  -   00  ---   -  --    --   --  EVN  -   -   -   -    -    -   ---     -   ---    ----    # Read LSW of multiplier into S
       11111 1 0010 :  -   -   00  X0    -  YPR   CY0  WPR  -   -   -  LSW  -   MLSW  -   RSH     -   ---    ----    # Multiply step word 0
       11111 1 0011 :  -   -   10  X0    -  YPR   --   WPR  -   -   -   -   -   MLSW  -   RSH     -   ---    ----    # Multiply step word 1
       11111 1 0100 :  -   -   01  XMUL  -  YPR   --   WPR  -   -   -   -   -   MLSW  -   RSH     -   ---    ----    # Multiply step word 2
       11111 1 0101 :  -   -   11  XMUL  -  YPR   --   WPR  -  SS1 MSW  -   -   MLSW  -   RSH   INCMS BNLMS  0100    # Multiply step word 3
       11111 1 0110 : SHS  -   00  ---   -  --    --   --  ODD  -   -   -   -    -    -   ---     -   ---    ----    # Read MSW of multiplier into S
       11111 1 0111 :  -   -   00  X0    -  YPR   CY0  WPR  -   -   -  LSW MMSW  -    -   RSH     -   ---    ----    # Multiply step word 0
       11111 1 1000 :  -   -   10  X0    -  YPR   --   WPR  -   -   -   -  MMSW  -    -   RSH     -   ---    ----    # Multiply step word 1
       11111 1 1001 :  -   -   01  XMUL  -  YPR   --   WPR  -   -   -   -  MMSW  -    -   RSH     -   ---    ----    # Multiply step word 2
       11111 1 1010 :  -   -   11  XMUL  -  YPR   --   WPR  -  SS1 MSW  -  MMSW  -    -   RSH   INCMS BNLMS  1110    # Multiply step word 3
       11111 1 1011 :  -   -   00  XAC   -  YPR   CY0  WAC  -   -   -  LSW  -    -    -   ---     -   ---    ----    # Add product to AC word 0
       11111 1 1100 :  -   -   10  XAC   -  YPR   --   WAC  -   -   -   -   -    -    -   ---     -   ---    ----    # Add product to AC word 1
       11111 1 1101 :  -   -   01  XAC   -  YPR   --   WAC  -   -   -   -   -    -    -   ---     -   ---    ----    # Add product to AC word 2
       11111 1 1110 :  -  EOI  11  XAC   -  YPR   --   WAC  -   -  MSW  -   -    -    -   ---     -   ---    ----    # Add product to AC word 3
    

    The Multiply and Subtract instructions are identical except for subtracting the product from the accumulator.

    # N - Multiply and subtract
       10110 0 0001 : SHS  -   --  ---   -  --    --   --   -   -   -   -   -    -    -   ---     -   ---    ----    # Read multiplier into S
       10110 0 0010 :  -   -   01  X0    -  YPR   CY0  WPR  -   -   -  LSW MMSW MLSW  -   RSH     -   ---    ----    # Multiply step word 2
       10110 0 0011 :  -   -   11  XMUL  -  YPR   --   WPR  -  SS1 MSW  -  MMSW MLSW  -   RSH   INCMS BNLMS  0100    # Multiply step word 3
       10110 0 0100 :  -   -   01  XPR  CMX YAC   CY1  WAC  -   -   -  LSW  -    -    -   ---     -   ---    ----    # Subtract product from AC word 2
       10110 0 0101 :  -  EOI  11  XPR  CMX YAC   --   WAC  -   -  MSW  -   -    -    -   ---     -   ---    ----    # Subtract product from AC word 3
    
       10110 1 0001 : SHS  -   00  ---   -  --    --   --  EVN  -   -   -   -    -    -   ---     -   ---    ----    # Read LSW of multiplier into S
       10110 1 0010 :  -   -   00  X0    -  YPR   CY0  WPR  -   -   -  LSW  -   MLSW  -   RSH     -   ---    ----    # Multiply step word 0
       10110 1 0011 :  -   -   10  X0    -  YPR   --   WPR  -   -   -   -   -   MLSW  -   RSH     -   ---    ----    # Multiply step word 1
       10110 1 0100 :  -   -   01  XMUL  -  YPR   --   WPR  -   -   -   -   -   MLSW  -   RSH     -   ---    ----    # Multiply step word 2
       10110 1 0101 :  -   -   11  XMUL  -  YPR   --   WPR  -  SS1 MSW  -   -   MLSW  -   RSH   INCMS BNLMS  0100    # Multiply step word 3
       10110 1 0110 : SHS  -   00  ---   -  --    --   --  ODD  -   -   -   -    -    -   ---     -   ---    ----    # Read MSW of multiplier into S
       10110 1 0111 :  -   -   00  X0    -  YPR   CY0  WPR  -   -   -  LSW MMSW  -    -   RSH     -   ---    ----    # Multiply step word 0
       10110 1 1000 :  -   -   10  X0    -  YPR   --   WPR  -   -   -   -  MMSW  -    -   RSH     -   ---    ----    # Multiply step word 1
     10110 1 1001...
    Read more »

  • Improving the Microassembler

    greg.ewing11/11/2018 at 04:53 0 comments

    In an effort to make the microcode source more readable, I added the ability to define named constants to the microassembler. They can be referenced anywhere in the source file, and they simply get textually expanded into their definitions.

    This is what the microcode looks like now. While still not exactly crystal clear to the uninitiated, I hope you'll agree it's better than it was.

    AddressBits := 10
    DataBits := 32
    
    # Unused field values
    - = 0
    -- = 00
    --- = 000
    ---- = 0000
    
    # Single bit values
    SHS = 1  # Shift S Register
    EOI = 1  # End of Instruction
    CMX = 1  # Complement X
    ODD = 1  # MSW of double word memory reference
    MSW = 1  # Most significant word
    LSW = 1  # Least significant word
    SS1 = 1  # Shift S Register by one bit
    WMEM = 1  # Write memory
    INCMS = 1 # Increment multiplication step counter
    MMSW = 1  # MSW of multiplicand
    MLSW = 1  # LSW of multiplicand
    
    # WRF values
    WAC = 10  # Write Accumulator
    WMR = 01  # Write Multiplier Register
    WPR = 11  # Write Product Register
    
    # XSEL values
    X0   = ---  # Zero
    XAC  = 100  # Accumulator
    XMEM = 010  # Memory
    XMUL = 110  # S Register * Nultiplier
    XPR  = 001  # Product Register
    
    # YSEL values
    Y0   = 00  # Zero
    YAC  = 10  # Accumulator
    YAND = 01  # Multiplier & Memory
    YPR  = 11  # Product Register, or zero if first multiplication step
    
    # Carry control values (CY1, CYP)
    CY0 = 00
    CY1 = 10
    CYP = 01
    
    # MISC values
    FETCH = 100  # Instruction fetch
    RSH   = 110  # Right shift
    HALT  = 001  # Halt at end of instruction
    
    # OPCODE L STAT : SHS EOI  RFA XSEL CMX YSEL CARRY WRF ODD SS1 MSW LSW MMSW MLSW WMEM MISC  INCMS UBCOND UBADDR
    
    # Fetch
       xxxxx x 0000 : SHS  -   --  ---   -  --    --   --   -   -   -   -   -    -    -   FETCH   -    ---    ----
    
    # A - Add
       11100 0 0001 :  -  EOI  11  XMEM  -  YAC   CY0  WAC  -   -  MSW LSW  -    -    -   ---     -    ---    ----
    
       11100 1 0001 :  -   -   01  XMEM  -  YAC   CY0  WAC  -   -   -  LSW  -    -    -   ---     -    ---    ----
       11100 1 0010 :  -  EOI  11  XMEM  -  YAC   CYP  WAC ODD  -  MSW  -   -    -    -   ---     -    ---    ----
    
    # S - Subtract
       01100 0 0001 :  -  EOI  11  XMEM CMX YAC   CY1  WAC  -   -  MSW LSW  -    -    -   ---     -    ---    ----
    
       01100 1 0001 :  -   -   01  XMEM CMX YAC   CY1  WAC  -   -   -  LSW  -    -    -   ---     -    ---    ----
       01100 1 0010 :  -  EOI  11  XMEM CMX YAC   CYP  WAC ODD  -  MSW  -   -    -    -   ---     -    ---    ----
    
    # Z - Halt
       01101 0 0001 :  -  EOI  --  ---   -   --   --   --   -   -   -   -   -     -    -  HALT    -    ---    ----
    
    # T - Transfer and clear
       00101 0 0001 :  -  EOI  11  XAC  CMX  YAC  CY1  WAC  -   -  MSW LSW  -     -   WMEM ---    -    ---    ----
    
       00101 1 0001 :  -   -   01  XAC  CMX  YAC  CY1  WAC  -   -   -  LSW  -     -   WMEM ---    -    ---    ----
       00101 1 0010 :  -  EOI  11  XAC  CMX  YAC  CYP  WAC ODD  -  MSW  -   -     -   WMEM ---    -    ---    ----
    
    # U - Transfer without clear
       00111 0 0001 :  -  EOI  11  XAC   -   Y0   CY0   --   -   -   -   -   -    -   WMEM ---    -    ---    ----
    
       00111 1 0001 :  -   -   01  XAC   -   Y0   CY0   --   -   -   -   -   -    -   WMEM
       00111 1 0010 :  -  EOI  11  XAC   -   Y0   CY0   --  ODD  -   -   -   -    -   WMEM ---    -    ---    ----
    
    # H - Load Multiplier
       10101 0 0001 :  -   -   01  X0    -  Y0    CY0   WMR  -   -   -  LSW  -    -    -   ---    -    ---    ----
       10101 0 0010 :  -  EOI  11  XMEM  -  Y0    CY0   WMR  -   -  MSW  -   -    -    -   ---    -    ---    ----
    
       10101 1 0001 :  -   -   01  XMEM  -  Y0    CY0   WMR  -   -   -  LSW  -    -    -   ---    -    ---    ----
       10101 1 0010 :  -  EOI  11  XMEM  -  Y0    CY0   WMR ODD  -  MSW  -   -    -    -   ---    -    ---    ----
    
    # C - Collate 
       11110 0 0001 :  -  EOI  11  XAC   -  YAND  CY0   WAC  -   -  MSW LSW  -    -    -   ---    -    ---    ----
     
       11110 1 0001 :  -   -   01  XAC   -  YAND  CY0   WAC  -   -   -  LSW  -    -    -   ---    -    ---    ----
       11110 1 0010 :  -  EOI  11  XAC   -  YAND  CY0   WAC ODD  -  MSW  -   -    -    -   ---    -    ---    ----
    
    # L - Left shift
       11001 x 0001 :  -   -   00  XAC   -  YAC   CY0   WAC  -   -   -  LSW  -    -    -   ---    -    ---    ----
       11001 x 0010 :  -   -   10  XAC   -  YAC   CY0   WAC  -   -   -   -   -    -    -   ---    -    ---    ----
       11001 x 0011 :  -   -   01  XAC   -  YAC   CY0   WAC  -   -   -   -   -    -    -   ---    -    ---    ----
       11001 x 0100 :  -  EOI  11  XAC   -  YAC   CY0   WAC  -  SS1 MSW  -   -    -    -   ---    -    100    1000
    
    # R - Right shift
       00100 x 0001 :  -   -   00  XAC   -  Y0    CY0   WAC  -   -   -  LSW  -    -    -   RSH    -    ---    ----   
       00100 x 0010 :  -   -   10  XAC   -  Y0    CY0   WAC  -   -   -   -   -    -    -   RSH    -    ---    ----   
       00100 x 0011 :  -   -   01  XAC   -  Y0    CY0   WAC  -   -   -   -   -    -    -   RSH    -    ---    ----   
       00100 x 0100 :  -  EOI  11  XAC   -  Y0    CY0   WAC  -  SS1 MSW  -   -    -    -   RSH    -    100    1000   
    
    
    

  • Fixing the Multiplication Algorithm

    greg.ewing11/11/2018 at 03:03 1 comment

    When I tried to implement the multiplication scheme I described earlier, I found that it didn't work properly. It turns out my assumption that shifting the product right would be equivalent to shifting the multiplier left is not quite true.

    To see the problem, let's do this example again using the product-shifting technique:

    0.75 * 0.6875 = 0.515625
    

    The initial S-register and Multiplier values are:

                      17 16 15 14 13 12
    S Register:        0. 1  1  0  0  0  ...
    Multiplier:        0. 1  0  1  1  0  ...
    

    The product register is zero until multiplication step 15, where the multiplier is added to it for the first time.

    Product:           0. 0  0  0  0  0  ...
    Multiplier:        0. 1  0  1  1  0  ...
                       ---------------------
    New Product:       0. 1  0  1  1  0  ...
    

    The product is then shifted right and the multiplier is added to it again.

    Shifted Product:   0. 0  1  0  1  1  0  ...
    Multiplier:        0. 1  0  1  1  0  0  ...
                       ------------------------
    New Product:       1. 0  0  0  0  1  0  ...
    

    Note that the sign bit of the product is now 1. However, the product is not negative -- it can't be, since it was obtained by adding two positive numbers! If we continue and perform the final step of the multiplication, the product register is shifted right again with sign extension and we obtain a negative result, which is incorrect.

    Final Product:     1. 1  0  0  0  0  1  0  ... Wrong
    

    In essence, the problem is that the product register overflows. To avoid this, we need an extra bit of precision on the left, between the binary point and the sign bit. Here's how that looks:

                      17 16 15 14 13 12 11
    S Register:        0  0. 1  1  0  0  0  ...
    Multiplier:        0  0. 1  0  1  1  0  ...
    
    Product:           0  0. 0  0  0  0  0  ...
    Multiplier:        0  0. 1  0  1  1  0  ...
                       ------------------------
    New Product:       0  0. 1  0  1  1  0  ...
    
    Shifted Product:   0  0. 0  1  0  1  1  0  ...
    Multiplier:        0  0. 1  0  1  1  0  0  ...
                       ---------------------------
    New Product:       0  1. 0  0  0  0  1  0  ...
    
    Final Product:     0  0. 1  0  0  0  0  1  0  ...
    

    Moving the Unused Bit (Again)

    To provide the required extra bit of precision in the product register, I've decided to move the unused bit back to the most significant end. The reason I moved it before -- to get the final product aligned correctly -- turns out not to be a problem as long as multiplication is stopped once the sign bit (now the next-most-significant bit) of the multiplicand (in the S-register) has been processed.

    So I have undone most of the modifications I made earlier to put the unused bit at the least significant end. However, the ALU treats it as an ordinary bit -- I am not forcing it to be equal to the sign bit as I did before. That shouldn't be necessary, since they will end up equal anyway unless an overflow occurs, and I may want to implement overflow detection later by comparing them.

    Revised ALU

    In the process of updating the ALU I discovered some other mistakes that were no doubt contributing to my messed-up multiplication results. This is the new ALU subcircuit.

    Revised Multiplication Step Counter

    The MSC subcircuit now signals MLAST (last multiplication step) and wraps to zero on T16 of MMSW (most significant word of multiplicand). On the least significant word of the multiplicand, it wraps on T17.

    Changes to Microcode Encoding

    I discovered that encoding MMSW and MLSW as values of the MISC field wasn't going to work, because I need them both at once during a single word multiplication. I could have used yet another MISC value to represent the combination, but I realised a couple of things. I don't really need the MASEL field, because it's only ever used during an instruction fetch, and FETCH is never used together with any other MISC values. So I decided to allocate a MISC value for FETCH, and use it to control both memory address selection and PC incrementing, freeing up two microcode bits to use for MMSW and MLSW. This also simplified some of the other logic a bit, because MMSW and MLSW no longer need to imply RSH.

    I also shuffled some of the microcode bits around, resulting in the following version of the main...

    Read more »

  • Microcode Breakpoints

    greg.ewing10/26/2018 at 12:10 0 comments

    While debugging my multiplication instructions, I decided that I needed a way to set a breakpoint in the microcode. I added some manually-controlled inputs to specify the microcode address, multiplication step count and bit number to break at, and a breakpoint enable signal. To make the wiring a bit tidier in the main circuit, I also grouped all the microcode address lines into a bus.


    The Microcode Breakpoint subcircuit compares the current values of the microcode address, multiplication step and bit number with the breakpoint values. When they match, and breakpoints are enabled, the UBREAK output is activated.


    UBREAK is connected to the Run Control subcircuit, where it disables the RUN output, freezing the rest of the machine. To allow continuing after a break, I made some other changes to the run control circuit. When the CONTINUE button is pressed, a pulse lasting a single clock cycle is generated by Cont FF 1 and Cont FF 2. This pulse temporarily overrides the UBREAK input and allows a BITCLK cycle through. Since this advances the bit counter, the break condition will no longer be met in the next cycle, so execution continues until the breakpoint is reached again or the nachine is stopped by other means.

    The Stop FF is no longer needed and has been removed. The Run FF is now set directly by the Continue pulse.

  • Multiplication Hardware

    greg.ewing10/26/2018 at 12:02 0 comments

    Moving the Unused Bit

    Here are the changes I made to move the unused bit to the least significant end.

    • The carry-in logic and initialisation of the Zero FF now takes place at T1 of an LSW instead of T0.
    • The logic for extending bit 16 to bit 17 of an MSW has been removed, and the sign is captured in the Sign FF during T17 instead of T16.
    • The Z ouput of the ALU is now forced to zero during T0 of an LSW.
    • Inputs to the Instruction Register are taken from outputs Q2-18 of the S Register (where Q18 is the same as the serial input).
    • Shift Left and Shift Right instructions are now terminated when bit 1 of the S Register is 1 instead of bit 0.

    This is the revised ALU subcircuit:


    Multiplication Step Counter

    We need a way to tell when we've carried out the required number of shift-and-add cycles when multiplying. The Multiplication Step Counter (MSC) does this. It counts up to 17 and then wraps back to 0 ready for another multiplication. A new control signal INCMS enables incrementing the MSC, and a new microcode branch condition (number 2) tests whether the MSC has reached 17.


    Multiplication Flowchart

    Here's a flowchart showing the general strategy for implementing the Multiply and Add (V) instruction.

    We can combine some of the operations that are shown as separate steps in the above flowchart. Not only will this save time, it will be necesessary if we want to stay within our 15-microinstruction budget for the long-word versions of the multiplication instructions.

    Other changes to support multiplication

    I changed the register file addressing so that the output of the Register Address Incrementer goes only to the Accumulator and Product Register, with the Multiplier Register receiving the unmodified register address. Activating RSH while adding the multiplier to the product then causes bit i+1 of the product to be added to bit i of the multiplier and written back to bit i of the product, thereby performing Product <-- (Product >> 1) + Multiplier.

    An AND gate computes the product of the Multiplier with bit 0 of the S Register, and this is made available as an X input to the ALU.

    The Product is made available as a Y input through a gate that forces it to zero during the first multiplication step. This allows clearing the Product to be overlapped with the first multiplication step.

    The Product is also available as an X input, so that it can be either added to or subtracted from the Accumulator at the end of a Multiply and Add or Multiply and Subtract. The XSEL field had to be widened to 3 bits to allow for this.

    I added two control signals MLSW and MMSW to indicate when the least or most significant words of a multiplicand are being processed. To save microinstruction bits, these have been combined with RSH and HALT in a decoded field called MISC:

    001 MMSW
    010 MLSW
    011 RSH
    100 HALT
    

    Logic has been added to the ALU to perform subtraction during the last bit period of a multiplication if the MSB of the multiplicand is set.

    Revised ALU

    Revised Main Circuit

View all 31 project logs

Enjoy this project?

Share

Discussions

Similar Projects

Does this project spark your interest?

Become a member to follow this project and never miss any updates