Logicworks

2023-03-26

Logicworks was a project to make a logic simulator, similar to Turing Complete, with a focus on emulation performance. I worked on it for my A level computer science project, but ultimately switched to working on Hypertunnel instead.

It consisted of three programs:

A node-based drag-and-drop editor. This was initially Svelte+Pixi.js, then it was Godot with GDScript, then it was Godot with Rust, and finally I settled on Rust with Bevy.

An optimising compiler, which makde decisions about multithreading points, converted components into higher level representations, and performed boolean algebra simplification. It also formed a DAG (Directed Acyclic Graph), then carried out a topological sort and stored the result to reduce runtime overhead. This was written in Rust.

An executor that ingested build artifacts from the compiler and executed them, written in Rust.

I ultimately didn't get to the point of actually executing circuits before switching to Hypertunnel, which I found far more interesting. I worked on the UI first, so the executor and compiler didn't get particularly far.

I have some rough notes on ideas for optimisations, which may be useful for people working on similar projects:

• Compile to LLVM IBC?
• Have a clear distinction between fundamental, stateful, and deterministic components
• Stateless components can be executed backwards, cached, etc
• Stateful ones must be executed in-order
• Look into Verilog's codegen approach: https://www.youtube.com/watch?v=en8JMz7v3LU
• Build evaluation order at compilation time
• We can link the outputs of one function to a pointer, which is the input of another, then place the elements-to-evaluate in a vector. We can iterate linearly with piping for free and good cache coherency.
• GPU compute could be useful
• We can make decisions on where to multithread at compile time
• See https://docs.rs/slotmap/latest/slotmap/ https://docs.rs/phf https://rust-unofficial.github.io/patterns/ https://nnethercote.github.io/perf-book/benchmarking.html
• https://en.wikipedia.org/wiki/Topological_sorting
• Compiler optimisation:
  • If below a certain size, premake a hashmap cache
  • If a hashmap cache matches a known truth table turn it into a fundamental component
  • Identify ALUs based on control bits/input-output, and try to optimise away most operations.
  • Boolean algebra optimisation
  • Identify components that are never run because everything they're used in is fully optimised, and tell the executor not to load them into memory, but keep the build artifact
• Executor optimisation:
  • Multithreading in expensive components
  • Store serialised types as ints
  • Cache truth tables on-the-fly with some form of cache clearance