Concept of Time

[fgarci03]

The concept of memory can only exist if we have a concept of time.

At the moment tests are simply testing components in a static fashion, but when dealing with components that have memory, we will probably need to have some sort of clocking mechanism to simulate the passage of time inside the CPU.

I was thinking of a very basic infinite loop that would change a global variable CLOCK (alternating between 0 and 1), which would feed any memory-related component (such as FlipFlops, Registers, etc).

How could something like this be implemented, looking at the ultimate goal of building an actual CPU?

[thequux]

While you can use a clock signal like you suggested, you'll very quickly run into sequencing issues (does the address/data arrive before the clock goes high? How can you ensure that?), and with a pull-based evaluator, you'll additionally need to be very careful to always be able to terminate the recursion. This turns out to be much more work than it first appears. Also, real logic elements have some amount of delay and components like flip flops and ring oscillators depend on this delay to function.

To solve this, there are two common approaches used in circuit simulation: time slicing and discrete event simulation.

Time slicing is very simple to implement, and it's ideal when a significant portion of the gates will change values on each tick. Essentially, rather than each component recalculating it's output as necessary, each component has two member functions. prepare calculates what a component's outputs will be given its current inputs, and commit copies the prepared output to the actual output. Notably, prepare doesn't affect any of the outputs, and commit doesn't look at the inputs, so you never need to worry about infinite loops. (You can also model this with explicit wire objects: prepare puts a value on the wire, and commit is a function on the wire to compute the actual logic level. This lets you model tristate inputs, wired and/or connections, etc). Your main loop becomes something like

while True:
    for part in components:
        part.prepare()
    for part in components:
        part.commit()

Discrete event simulation is similar, but instead of evaluating every component on every tick, components schedule themselves to be updated at some point in the future by inserting a callback into a priority queue. There are a number of designs for this: the separation between what is queued and what is computed immediately, how updates propagate, how (and whether!) to coalesce multiple changes in a single tick into a single event, etc.

My recommendation is to start with simple time slicing, and if you end up needing the peformence (which you probably will eventually), you can move to DES.

[fgarci03]

Wow, this is wonderful!

Now, there's a lot to unpack here. Pardon my ignorance, but how should the components be iterated? For example, a FullAdder depends on 2 HalfAdders, which in turn depend on and AND and XOR Gates, which depend on...............

By updating the FullAdder, I would expect all its "dependencies" to be updated on the same input change of the Adder on a single "tick" of the clock. Meaning I wouldn't need to iterate all these components, just the "big one" that "uses" all the others.

As for the delay being necessary for certain components like FlipFlops to work, it does make sense in my head, but I will need to further read and learn about them in order to be able to translate that into code.

One question though: Does it make sense to believe the prepare/commit phases could be implemented ONLY at the transistor level, and be abstracted away from the "higher-order" components? I ask this because I was aiming (as much as possible) to have any "simulated physics" only on the transistors, and have the Logic Gates and other components having no such "simulation", and simply switching the inputs at each tick of the clock.

Maybe I'm not making sense, I'm sorry for that :sweat_smile:

[thequux]

Within ~6 hours, you'll have a pull request. I'm building the time-sliced version with explicit wires and variable drive strengths; trust me, you'll want it when you get to memories.

Normally, a component's prepare method would simply call the prepare method of its subcomponents. However, this can be optimized by collecting all of the components with logic (i.e., the transistors) up front and then simply iterating over those. This is how I'll organize the main loop in my PR (and as a side effect, you're one step closer to solving #3)

[thequux]

I need to step away from my computer for a bit, but you can see my WIP changes here: thequux/pylectronics@7d806afb59e5172ae710a13eb370ac64afa77a6d . I'll port some of the tests later tonight so that we can see it in action. (Memories and adders may need to wait, because they're a bit on the complicated side)

[fgarci03]

From what I could understand, you switched from BJT to MOSFET, and actually implemented the VCC/GND wires and logic into the transistors. I'll have to read a bit on the drive strengths to further understand it.

Not that I'm against it (it actually makes the transistor closer to its real-life counterpart), but what benefit will there be regarding the VCC/GND wires? I was pretty much treating any VCC as any other input, it could be high or low. Would I run into problems with that approach later?

All in all seems a step in the right direction. While the components are becoming a bit more complex than I expected at first, the core logic seems to be aligned with what I envisioned (simulated physics only at the transistor level, and all the components simply implement the transistors in different configurations to allow them to work as expected).

[thequux]

In your previous design, you still had Vcc and ground rails; they were just called True and False, respectively. This works fine until you start having tristate drivers, which can also be high-impedance (aka Z). While you can design a full CPU without any tristates, it means that you can't correctly model a transistor, which doesn't output low when it's turned off; rather, it disconnects its drain from the source. (well, not quite. It's a very high resistance, on the order of 10's to 100's of MΩ. But disconnected is close enough)

The design that I've used for the gates is a CMOS process, which only needs 0, 1, and Z. However, as long as we're modeling drive strength at all, we may as well also model weakly-driven inputs, which can be thought of as connecting a wire to a rail through a ~10kΩ resistor. If you have a strong drive on a wire, then the weak drive is ignored. However, if you only have high impedance and weak drives, the weak drives provide a valid voltage level. (BTW, normally, weak drives are referred to as H and L). This would allow us to base our gates on an NMOS or PMOS process, where the high and low side, respectively, are handled by resistors.

I'll admit that I stole that design from VHDL's std_logic_1164 module, where you actually have 8 different signal levels:

• Strong drives: 0, 1, and a forcing unknown X
• Weak drives: H, L, and a weak unknown W
• High impedance: Z
• Uninitialized: U

I'm on the fence about including the unknowns; they provide a nice solution for when two drivers conflict, but propagation of them can get irritating. That said, considering that we're implementing everything in terms of transistors, that only leaves two places that we'd need to consider them.