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

  • Notes on Multiplication

    greg.ewing06/27/2018 at 12:57 0 comments

    This is another subject that required quite a lot of thought. I believe I've found a way to make it all work, but there are a number of subtleties involved that I'll try to explain here.

    The basic algorithm I'll be using is simple: for each bit of the first operand, multiply the second operand by it, shifted by an appropriate number of places, and add up the results. This is particularly easy to do in binary, since multiplying by a single bit can be accomplished with an AND gate.

    In what follows, I'm going to call the first operand the multiplicand and the second operand the multiplier, because the second operand (the one that gets added to the product) will be the one held in the Multiplier Register.

    Scaling

    EDSAC numbers are meant to be interpreted as fractions in the range -1 to 1, and the multiplication algorithm needs to produce results consistent with this interpretation. Given two signed n bit operands with an assumed point between bits n-1 and n-2, we want a 2n-1 bit result with an assumed point between bits 2n-2 and 2n-3.

    Here's an example with n = 5:

    0.75 * 0.6875 = 0.515625
    
    0.1 1 0 0
    0.1 0 1 1
    -----------------
            0 0 0 0 0
          0 0 0 0 0
        0 1 0 1 1
      0 1 0 1 1
    0 0 0 0 0
    -----------------
    0.1 0 0 0 0 1 0 0
    

    From this we can see that to get a correctly aligned result, the most significant bit of the multiplier (i.e. its sign bit) needs to be aligned with the bit from the multiplicand that we are multiplying it by.

    Negative numbers

    We need to make sure we get the right results with negative operands.

    As long as the multiplicand is positive, we don't need to do anything special -- the multiplier can be of either sign, and as long as we sign-extend it  when shifting, two's-complement arithmetic will produce the correct result. For example,

    0.75 * -0.3125 = -0.234375
    
    0.1 1 0 0
    1.1 0 1 1
    -----------------
            0 0 0 0 0
          0 0 0 0 0
    1 1 1 1 0 1 1
    1 1 1 0 1 1
    0 0 0 0 0
    -----------------
    1.1 1 0 0 0 1 0 0
    

    The bits resulting from sign extension are shown in red.

    But, we need to be careful when the multiplicand is negative -- naively treating the sign bit of the multiplicand the same way as its other bits will not give the right result.

    To see what needs to be done, consider that a number in the range -1 <= x < 0 can be written as -1 + y, where y is what results from taking the bits after the point and interpreting them as a positive number. In other words, we can take the bits after the point as having positive binary weights for both positive and negative numbers, as long as we give the sign bit a weight of -1.

    What this means is that we can carry out the multiplication algorithm as usual for the bits of the multiplicand after the point, ignoring its sign; then, if the multiplicand is negative, subtract the multplier from the product. Example:

    -0.25 * 0.6875 = -0.171875
    
    1.1 1 0 0
    0.1 0 1 1
    -----------------
            0 0 0 0 0
          0 0 0 0 0
        0 1 0 1 1
      0 1 0 1 1
    1 0 1 0 1
    -----------------
    1.1 1 0 1 0 1 0 0

    Here, the bits shown in red result from taking the two's complement of the multiplicand.

    Shifting strategy

    The above examples are presented as though the multiplier is being shifted to the right by varying amounts, but I'm actually going to do it slightly differently: at each step, shift the product one place right and then add the multiplier to the most significant bits of the product.

    This avoids having to shift the multiplier, leaving the contents of the Multiplier Register undisturbed. It also allows me to process the multiplicand bits in order from least significant to most significant, so that I can keep the multiplicand in the S-register and make use of its right-shift capability.

    What's more, it turns out that, with a slight modification to the circuitry I already have, I can perform the shifting and adding together in one pass.

    Where to put the unused bit?

    For simplicity, BREDSAC is based on 18-bit cycles. But a short word has only 17 bits, and a long word 35 bits, meaning...

    Read more »

  • Right Shift Instruction

    greg.ewing06/24/2018 at 13:28 0 comments

    I spent quite a long time thinking about how to implement this instruction. The strategy I eventually came up with is to add 1 to the register file address during the read phase of each bit time. So it reads bit 1 and writes it to bit 0, reads bit 2 and writes it to bit 1, etc. A fair bit of extra circuitry will be required to achieve this, and I don't really like the idea of adding that much complexity just to support one operation, but I haven't been able to think of a simpler way without radically changing the whole design.

    This is the subcircuit I designed to carry out the address incrementing. When the INC input is activated, a 5-bit adder adds 1 to BITNO. If the result is 18 (0x12) the result is forced to zero and a carry is added to RFA

    Here's where it fits into the main circuit. A new control signal RSH enables right-shifting behaviour. It is gated with RUNCLK so that the register file address is incremented during the read phase of each bit time. Incrementing is disabled during T17 of the most significant word, so that the most significant bit is unaltered. This makes the operation an arithmetic shift (i.e. with sign extension)

    Microcode

    This is the microcode for the right shift instruction. It uses the same technique as the left shift for keeping track of the number of places to shift.

    # OPCODE L STAT : FETCH MASEL SHS EOI RFA WRF XSEL YSEL  CMX SS1 CY1 CYP ODD MSW LSW HALT WMEM UBCOND UBADDR RSH
    
    # R - Right shift
       00100 x 0001 :   0     0    0   0   00  10   10   00   0   0   0   0   0   0   1   0    0    000    0000   1
       00100 x 0010 :   0     0    0   0   10  10   10   00   0   0   0   0   0   0   0   0    0    000    0000   1
       00100 x 0011 :   0     0    0   0   01  10   10   00   0   0   0   0   0   0   0   0    0    000    0000   1
       00100 x 0100 :   0     0    0   1   11  10   10   00   0   1   0   0   0   1   0   0    0    100    1000   1
    

    Glitches, Will Robinson!

    Testing in Logisim revealed a problem with this arrangement. Previously, the register address only changed on the rising edge of BITCLK, and was stable at the leading edge of the WRITE signal to the register file, but now the register address can also change on the falling edge of BITCLK. This was causing spurious bits in the accumulator to change.

    To fix this, I changed the clocking arrangement. The simulation is now clocked at twice the BITCLK rate, and a timing signal TWRITE is derived that is active during the last quarter of each bit period. This is used to gate the WRF1-WRF3 signals, which delays writing to the register file until a quarter of a bit period after any potential address change

    Revised register file timing:

  • Left Shift Instruction

    greg.ewing06/23/2018 at 11:20 0 comments

    Shifting the accumulator one bit to the left can be easily accomplished by adding it to itself. To shift by a variable number of bits, however, we will need to have a loop in the microcode, which brings us to the subject of microcode branching.

    Microcode Branching

    To support branching in the microcode, I added two new control fields: UBCOND (Microcode Branch Condition) and UBADDR (Microcode Branch Address).

    UBCOND selects one of a number of branch conditions. The branching logic is as follows:

    • When the branch condition is true, the next value for STATENO is taken from the UBADDR field.
    • When the branch condition is false and EOI is true, STATENO is reset to zero.
    • Otherwise, STATENO is incremented.

    I made some additions to the State Counter subcircuit to implement this logic.

    UBRANCH is a new input to the State Counter that is 1 when the selected branch condition is true. It is generated by a multiplexer in the main circuit:

    Note that I changed how the LAST signal is generated again. It is now an output from the State Counter subcircuit, and is only activated if EOI is true and UBRANCH is false.

    I have defined two UBCOND values so far:

    UBCOND Branch condition
    000 Always false
    001 Bit 0 of the S Register = 0

    Left Shift Instruction

    The number of places to shift is encoded in the Shift Left and Shift Right instructions by the position of the rightmost 1 bit in the instruction. This means we can take advantage of the fact that the instruction is left in the S Register at the end of the fetch cycle. Here's the strategy:

    To do this, I added a control signal SS1 that shifts the S register only during T17. I used the bit that became spare when AND was removed.

    Left Shift Microcode

    The microcode for the Left Shift instruction takes 4 microinstructions, because it needs to shift all four short words of the accumulator. Shifting the S register is overlapped with both shifting the most significant accumulator short word, and with the branch back to the beginning if there is more shifting to be done. Note that the branch condition is testing the state of the S register before it is shifted.

    # OPCODE L STAT : FETCH MASEL SHS EOI RFA WRF XSEL YSEL  CMX SS1 CY1 CYP ODD MSW LSW HALT WMEM UBCOND UBADDR
    
    # L - Left shift
       11001 x 0001 :   0     0    0   0   00  10   10   10   0   0   0   0   0   0   1   0    0    000    0000
       11001 x 0010 :   0     0    0   0   10  10   10   10   0   0   0   0   0   0   0   0    0    000    0000
       11001 x 0011 :   0     0    0   0   01  10   10   10   0   0   0   0   0   0   0   0    0    000    0000
       11001 x 0100 :   0     0    0   1   11  10   10   10   0   1   0   0   0   1   0   0    0    100    1000
    
    

  • Register File Revision

    greg.ewing06/23/2018 at 06:19 0 comments

    I replaced the output flip flop in the register file subcircuit with a transparent latch. This is mainly to aid debugging, so I can pause the simulation during phase 1 of a bit cycle and see the data read from the registers.


    Revised timing diagram:

  • Load Multiplier and Collate Instructions

    greg.ewing06/21/2018 at 11:17 0 comments

    Rearranging Registers and ALU Functions

    Until now I thought that I could keep the Multiplier and the Accumulator in the same register file because they wouldn't both need to be read at the same time. But it turns out that the Collate instruction is supposed to do this:

        Accumulator <-- (Memory AND Multiplier) + Accumulator

    so I need to add an additional register file to hold the Multiplier.

    It also means the logical AND function isn't in the right place where I had it. I decided to move it out of the ALU and add an X input option that selects the AND of the Multiplier register and data read from memory. The ALU can then be configured to add this to the Accumulator, accomplishing the Collate operation in one short or long word cycle.

    This is the relevant part of the revised data path. There are now separate register files for the Accumulator and Multiplier, and I also added one for the Product register while I was at it. The RFA1 microinstruction field has been reduced to 2 bits and renamed simply RFA, since it supplies the high-order address bits for all the register files. The AND control signal has been removed.


    The WRF1 field has been replaced with a 2-bit field that is decoded to produce write signals for the three register files:


    Revised ALU with logical AND function removed:

    Microcode

    We can now microcode the H instruction, which loads a word from memory into the Multiplier register, and the C (Collate) instruction.

    # OPCODE L STAT : FETCH MASEL SHS EOI RFA WRF XSEL YSEL CMX     CY1 CYP ODD MSW LSW HALT WMEM
    
    # H - Load Multiplier
       10101 0 0001 :   0     1    0   1   11  01   01   00   0   0   0   0   0   1   1   0    0
    
       10101 1 0001 :   0     1    0   0   01  01   01   00   0   0   0   0   0   0   1   0    0
       10101 1 0010 :   0     1    0   1   11  01   01   00   0   0   0   0   0   1   0   0    0
    
    # C - Collate
       11110 0 0001 :   0     1    0   1   11  10   10   01   0   0   0   0   0   1   1   0    0
    
       11110 1 0001 :   0     1    0   0   01  10   10   01   0   0   0   0   0   0   1   0    0
       11110 1 0010 :   0     1    0   1   11  10   10   01   0   0   0   0   1   1   0   0    0
    

  • Transfer Instructions

    greg.ewing06/20/2018 at 10:56 0 comments

    The two Transfer instructions, T and U, transfer the contents of the accumulator to the main memory. The difference between them is that T also clears the accumulator, whereas U does not.

    These are the first instructions we've implemented so far that write to main memory, so we need a new control signal, WMEM. This is gated with phase 2 of the bit clock so that writing to memory occurs only during the write phase of each bit time.

    Updated main memory subcircuit:

    I also made a change to the data path in the main circuit. Instead of the data input to the main memory coming from the output of the ALU, it now comes from the multiplexer feeding the X input of the ALU. This will enable me to clear the accumulator at the same time as writing it to main memory for implementing the T instruction.

    Revision to the main circuit:

    Microcode

    The T instruction selects the accumulator as the source for both inputs to the ALU, and enables writing to memory. It also sets the ALU to perform subtraction, thereby subtracting the accumulator from itself, giving zero, and writes this back to the accumulator.

    The U instruction simply selects the accumulator as the X input and writes it to memory.

    # OPCODE L STAT : FETCH MASEL SHS EOI RFA1 WRF1 XSEL YSEL CMX AND CY1 CYP ODD MSW LSW HALT WMEM
    
    # T - Transfer and clear
       00101 0 0001 :   0     1    0   1   110   1   10   10   1   0   1   0   0   1   1   0    1
    
       00101 1 0001 :   0     1    0   0   010   1   10   10   1   0   1   0   0   0   1   0    1
       00101 1 0010 :   0     1    0   1   110   1   10   10   1   0   0   1   1   1   0   0    1
    
    # U - Transfer without clear
       00111 0 0001 :   0     1    0   1   110   0   10   00   0   0   0   0   0   0   0   0    1
    
       00111 1 0001 :   0     1    0   0   010   0   10   00   0   0   0   0   0   0   0   0    1
       00111 1 0010 :   0     1    0   1   110   0   10   00   0   0   0   0   1   0   0   0    1
    

  • Subtract and Halt Instructions

    greg.ewing06/19/2018 at 12:55 0 comments

    Subtract

    Microcode for the Subtract and Subtract Long instructions is very similar to the Add instructions, the only differences being the activation of CMX and CY1.

    # OPCODE L STAT : FETCH MASEL SHS EOI RFA1 WRF1 XSEL YSEL CMX AND CY1 CYP ODD MSW LSW
    
    # S - Subtract
       01100 0 0001 :   0     1    0   1   110   1   01   10   1   0   1   0   0   1   1
    
       01100 1 0001 :   0     1    0   0   010   1   01   10   1   0   1   0   0   0   1
       01100 1 0010 :   0     1    0   1   110   1   01   10   1   0   0   1   1   1   0
    

    Halt

    To facilitate running test programs of more than one or two instructions, it seemed like it would be helpful to implement the Halt instruction next. I added a HALT control signal that becomes a new input to the Run Control subcircuit. I also tidied up the Run Control logic a bit, renaming some of its inputs for consistency, and moving generation of the LAST signal from the main circuit into the Run Control subcircuit.

    This is the new Run Control circuit:

    This is how it fits into the main circuit:

    Microcode for the Halt instruction is now straightforward.

    # OPCODE L STAT : FETCH MASEL SHS EOI RFA1 WRF1 XSEL YSEL CMX AND CY1 CYP ODD MSW LSW HALT
    
    # Z - Halt
       01101 0 0001 :   0     0    0   1   000   0   00   00   0   0   0   0   0   0   0   1
    

  • Sign and Zero Flags

    greg.ewing06/18/2018 at 12:57 0 comments

    A small revision

    While thinking about the features below, I realised that I needed separate signals indicating the most significant word of an operation and  forcing the memory address to be odd, so I renamed the signal I was previously calling MSW to ODD, and added a new MSW signal.

    Sign and Zero Flags

    There are two more things we will want the ALU to do for us, and that is to provide outputs indicating the sign of a result, and whether the result was negative. The revised ALU subcircuit below implements these.

    The Sign FF captures the sign bit, which is bit 16 of the most significant short word of the result. The sign bit is also replicated into the most significant bit of the result, thereby sign-extending it from 17 to 18 bits (or from 35 to 36 bits for a long word). The extra bit is usually ignored, but will play a role in multiplication later.

    The Zero FF keeps track of whether thre are any non-zero bits in the result. It is set equal to the result during T0 of the least significant word, and then set to 1 if any 1 bit occurs thereafter. At the end of the operation, its complement becomes the ZERO output of the ALU.

    There are two new control inputs to the ALU. LSW is activated during the least significant word of an operation, and MSW during the most significant word. For a short word operation, both are activated.

    Microcode

    Here is the revised microcode for the Add instructions.

    # OPCODE L STAT : FETCH MASEL SHS EOI RFA1 WRF1 XSEL YSEL CMX AND CY1 CYP ODD MSW LSW
    
    # A - Add
       11100 0 0001 :   0     1    0   1   110   1   01   10   0   0   0   0   0   1   1
    
       11100 1 0001 :   0     1    0   0   010   1   01   10   0   0   0   0   0   0   1
       11100 1 0010 :   0     1    0   1   110   1   01   10   0   0   0   1   1   1   0
    

  • Add Long Instruction

    greg.ewing06/17/2018 at 13:57 0 comments

    A small addition to the memory addressing logic is needed to support long word instructions. A new control signal MSW indicates that the most significant short word of a long word is being addressed, and forces the LSB of the address to 1.

    We can now microcode the long-word variant of the Add instruction as follows.

    # OPCODE L STAT : FETCH MASEL SHS EOI RFA1 WRF1 XSEL YSEL CMX AND CY1 CYP MSW
    
    # Add Long
       11100 1 0001 :   0     1    0   0   010   1   01   10   0   0   0   0  0
       11100 1 0010 :   0     1    0   1   110   1   01   10   0   0   0   1  1
    

    Add Long Test Video

  • Microcoding and Testing the Add Instruction

    greg.ewing06/17/2018 at 02:43 0 comments

    Microcode for the Add instruction

    Here's the microcode for the short-word version of the Add instruction.

    # OPCODE L STAT : FETCH MASEL SHS EOI RFA1 WRF1 XSEL YSEL CMX AND CY1 CYP
    # A - Add
       11100 0 0001 :   0     1    0   1   110   1   01   10   0   0   0   0
    

    MASEL = 1 selects the address field of the instruction as the main memory address. RFA1 = 011 (remember the data bits are backwards in the microcode source) selects the most significant short word of the accumulator. XSEL = 10 and YSEL = 01 route data read from main memory and register file 1 to the ALU, which is set up for addition with carry in = 0. WRF1 = 1 writes the output from the ALU into register file 1. EOI = 1 indicates that this is the last microinstruction for this instruction.

    Test Loader

    I wrote a Python program to generate memory images for loading into Logisim. It accepts a subset of the EDSAC Initial Orders 2 input format, with a few extensions.

    Here's an example for testing the Add instruction.

    0: A 2 F
    1: A 3 F
    2: 123
    3: 456
    

    The numbers on the left are memory addresses, in decimal. Lines starting with a letter represent instructions, and consist of an opcode, a memory address, and a length indicator (F for short word, D for long word). A line can also contain a number to be stored in memory, written in decimal, hex (prefixed by $) or binary (prefixed by %).

    Assuming the accumulator starts out containing zero, if the test is successful it should end with the accumulator containing 579 decimal (10 0100 0011).

    Add Test Video

    Here's a video of the Add test running in Logisim. Note that the numbers appear LSB first in Logisim's memory display windows.

View all 21 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