Gsim: Digital Circuit Simulator

[hearty rover]

Greetings!

For the last couple of months I've been working on a digital circuit simulator.
There is already software like this available, namely "Logisim Evolution" and "Digital", however both of these require a Java runtime and are kinda slow.
So I decided to start from scratch with the following goals:

• High speed parallel simulation
• As lightweight as possible
• Run on both native and WASM
  What this isn't:
• A general electronics simulation (Gsim only simulates tri-state digital logic)
• A PCB-editor/CAD tool

I have split the projects into two crates: the simulator backend and the UI.

The backend is already in a good state and basically only needs more circuit components to be implemented.
Although if you feel up to it, I'd be grateful for someone to comb through it and check for any soundness issues or possible optimizations. I'm confident in my Rust skills but with stuff this complicated two pairs of eyes see more than one.
You can find the backend here: https://github.com/Artentus/gsim

The UI however is not very far along. I'm not a particularily good UI developer, especially when using Rust.
I've been using egui + drawing the circuit itself directly with wgpu. If anyone has a better solution I'm open for it, as long as it is a Rust solution and works on both native and WASM.
Or if you think this approach is workable just helping me get it functional is also highly appreciated.
You can find the frontend here: https://github.com/Artentus/gsim-gui

[ionic shell]

Hi, this project sounds really cool!

I looked at the code, and correct me if I'm wrong but you seem to have a misconception about what soundness means in Rust.
https://doc.rust-lang.org/nomicon/working-with-unsafe.html?highlight=sound#working-with-unsafe
Functions not marked unsafe shouldn't be able to cause UB, and generally code that uses safe abstractions over unsafe code shouldn't be able to trigger UB if that unsafe code is sound. That's why we craft safe abstractions over unsafe code in the first place, so Rusts guarantees can be upheld in safe code.
Apparently, every update function in components.rs is unsound since empty wire lists could be supplied as arguments while you always use get_unchecked, and you also unsafely implement Send and Sync on types which are not safe to use across threads. Safe code elsewhere could use those to cause UB.

[hearty rover]

Those update functions aren't part of the public API. But I guess you're saying I should mark them as unsafe? Seems reasonable.
And I'm aware those types are unsafe as well. I need them to avoid Mutexes (which is ok as long as my algorithm works). I'm not aware of a way to mark an entire type as unsafe.

[ionic shell]

imo you shouldn't have to use _unchecked there, but yea you should at least mark them unsafe if they can cause ub from safe code.
As for the types, if you are going to unsafely impl Send/Sync, you should also mark the methods that can cause ub if used wrongly as unsafe.
I understand that that unsound stuff may not be part of the public api, but having those kinds of pitfalls for even safe code within your crate definitely puts me off contributing. I wouldn't be able to rely on the promises Rust makes in safe code.
Generally I wouldn't rely on unsafe to get marginal perf benefits until you can measure that synchronisation/checks are a real problem.

[quaint canyon]

😦 don't do things like this preemptively

even if the bottleneck is found to be there these marginal changes are probably not why

[hearty rover]

So I did test this, right. Using Mutexes instead of these unsafe sync cells is about 40% slower.
That is an unacceptable performance loss for me since this synchronization is not actually required by the algorithm.

The core of the problem is that I am using a list of indices (called the update queue) to index into another list, in parallel.
Now the reason why that is ok is because beforehand I use sort_unstable + dedup to ensure all indices are unique.
That means no one index is ever accessed by more than one thread, so using a Mutex is not necessary.
However I do not believe there is any way to make the compiler understand this, it's an inherently unsafe operation.

[hearty rover]

I've been thinking about this.
If I change the signature of update to this

    pub(crate) fn update(
        &mut self,
        wire_widths: &WireWidthList,
        wire_states: &WireStateList,
        outputs: &mut [LogicState],
    ) -> inline_vec!(WireId)

then it becomes a safe function.
But then I have to supply mutable references, and I'm pretty sure &mut *(shared_ref as *const _ as *mut _) is UB so how would I get one?

Guess I'll discuss this in #dark-arts

[ionic shell]

good idea, they'll have a better idea what you can do to make your project more safe or sound there

[hearty rover]

I've updated the code. All of the unsafe stuff is now constrained to just two functions. That hopefully makes it easier to reason about.

[wise grail]

more of a meta comment but have you thought about generating verilog code? It's industry standard so there's already somewhat of an ecosystem aroudn it

[hearty rover]

Generating Verilog is definitely on the "nice to have" list for the UI.

[wise grail]

I'm actually working on a schematic capture project (focus on analog circuit) and I imagined using xspice/verilog to do the digital simulation instead of writing my own simulator

it's actually right under your post haha

[hearty rover]

Yea I saw it. This is digital simulation only, no analog components, currents, voltages etc. which allows it to be much faster.
Writing this simulator was not unmanagable. I imagine it would be much more difficult to create ffi for Verilator, especially because you first have to compile every circuit.

[wise grail]

fair assessment

[hearty rover]

Verilator will most likely be faster tho, so there is that

[wise grail]

I'm thinking maybe there may be problems in timing sensitive circuits

im not sure, i have some contact with digital stuff mostly through coworkers, its not really what I work on

im thinking like this kind of flip flop

i guess for you you'd just have a single thing that's the flip flop

Im probably overthinking it

[hearty rover]

All of these kinds of lockstep simulators have trouble with timing sensitive circuits.
Simulating propagation delay accurately is computationally very expensive. Look at how much slower Icarus Verilog is compared to Verilator.
In my simulator there is just a singular component that simulates a flip-flop, then timing doesn't matter.

[hearty rover]

I've been thinking that it would be nice to have some way of defining circuits in the backend in a more conceise way.
The tests atm are extremely verbose, and that's only tests for individual components. It would be nice to test larger circuits, but currently that is not really feasable.
Eventually large circuits can be defined through the GUI but I feel like it's still a long way before that becomes viable.

[hearty rover]

I think I will be working on importing circuits generated by Yosys. That way the simulator can effectively be programmed using Verilog.

[hearty rover]

Basic importing works, but due to how different the Yosys output is to how I represent net graphs, the resulting graph is pretty dumb.
Yosys outputs a separate net for every individual bit, so I'm doing a lot of splitting and merging into individual bits, which makes the performance much worse than it really has to be.
If someone wants to write a better algorithm that merges the nets together into fewer Gsim wires, the code is all yours.

[hearty rover]

A little progress report:
I've spent the last couple of weeks refactoring large parts of the codebase to remove some annoying limitations of the simulation engine.
It is now possible to simulate wires and components of up to 255 bits wide. The previous limit was 32 bits, which turned out to be too restrictive for actual designs.
I have also rewritten a lot of the code responsible for importing Yosys netgraphs. It will now generate graphs that are a lot more efficient than the previous implementation.

[hearty rover]

I added the ability to export the simulation graph into Graphviz format.
This proved to be invaluable in optimizing the import of Yosys netgraphs. There is now barely any dumb conversion overhead left in the graph.
Oh and also the pictures look pretty (as long as the graph isn't too big). This is a basic 4-op adder circuit:

[hearty rover]

The simulation can now write VCD files

[hearty rover]

A little bit of progress on the GUI

There is still tons of stuff to be done though