CHDL Internals 0: node, nodeimpl, and tickable
As a companion to the CHDL tutorial series, I would like to expose some of the details of the CHDL design in a series of in-depth technical articles. The intended audience of the tutorials consists of those wanting to use CHDL for their own hardware designs. The internals articles is for those wishing to extend, alter, or simply understand CHDL at a lower level.
There are three basic datatypes upon which all of the rest of CHDL is built:
- The nodeimpl, handling the simulation and output behavior of
- the node, the user-facing interface for manipulating nodes, and
- the tickable, representing objects which react to clock signals.
In this article, we will focus on these types and some of the more obvious types built around them, leaving the higher-level details for next week. Because the codebase we are discussing is a constantly-changing work in progress, I will not cite data structures and functions by line number, instead referring to them by name and file.
node and nodeimpl
In a CHDL design, you type:
What actually happens? Let’s trace the function calls. First, we get to operator!(node y) in gateops.h. This is merely a wrapper for Inv(y). Inv(y) is declared in gates.h and defined in gates.cpp. All of the combinational logic functions in CHDL are implemented as combinations of (for now; there’s some desire to move to the industry standard And/Inverter Graph format) nand gates and inverters. The Inv() function, therefore, represents one of these fundamental gate types. Its implementation, then, will hopefully shed some light on the implementation of CHDL nodes. The meat of the implementation of Inv() in gates.cpp is:
node r((new invimpl(in))->id);
This seems odd. We’re creating this thing called an “invimpl” by allocating it on the heap, but despite the fact that we’re allocating it here, we’re not keeping the pointer here. Instead, we’re simply taking this “id” value and passing it to the node constructor. This reveals something about the true nature of node objects: they don’t so much represent nodes themselves as much as identify a nodeimpl. Why call them “node” and not “noderef” or similar? This is entirely for the benefit of users of the CHDL API. To the hardware implementer they certainly do represent nodes.
The nodes Vector
So, why aren’t we keeping a pointer to our node and what’s this “id” field about? The astute reader will have read the title of this section and understood. Pointers to all nodeimpl objects are stored in a global C++ vector<nodeimpl> called nodes, declared in nodeimpl.h. Indices into this vector have their own type, too, nodeid_t, an integer type typedef found in node.h. What’s the difference between nodeid_t and node, then? Consider the following:
node x = Foo(); // x has node id 100 node y = Reg(x); // y has node id 101 node z = Bar(); // z has node id 200 x = z; // now x and z both have node id 200
So, will y be the time-shifted-by-one-cycle output of Foo() or Bar()? Remember from the tutorial and the documentation that node assignments are transitive. All of the previous things given the value of x will now have its new value. This is useful because it means that CHDL designs can rewrite themselves. This is how optimization is implemented. It is also useful simply because hardware designs are not acyclic. Combinational logic may be, but as soon as registers are involved it will sometimes be necessary to use values before they are defined.
This behavior is implemented with a data structure called the node directory or node_dir, local to nodeimpl.cpp. The node directory keeps track of the node objects associated with each node ID. The node constructor adds a node to this directory and the node destructor removes it. The node assignment operator consults the node directory and updates all of the nodes to point to the new node ID. This means that node assignments necessarily, by design, completely remove all users of a given node ID. This is why the dead node elimination optimization is vital.
Finally, we have the issue of node sources. If I create an Inv(x), once this function has returned, a new invimpl object will have been created with x as the source. How do we store the source in such a way that, if x is overwritten later, the inverter’s source will be updated to match. We simply make the src field of nodeimpl a std::vector. This leads to the expected result without introducing a cyclic type dependency; remember, nodes don’t directly point to nodeimpls. They only contain indices.
We’ve dealt with the problem of how nodes are created, linked together, and evaluated, but this only allows us to create structures which evaluate Boolean functions, not systems which evolve over time. CHDL was not designed to evaluate low-level designs including implementations of sequential logic at the gate level, including stateful asynchronous logic. Cycles in the node graph lead to undefined behavior in both simulation and optimization, and can be detected with the cycdet() function in chdl/analysis.h.
The tickable type is completely unrelated to node and provides an orthogonal feature to node. It is only later, when we get to the register; the most useful instance of a tickable, that these two concepts are merged. In general, the node interface provides a mechanism for implementing arbitrary Boolean functions that may depend on other nodes or other parts of the program, and the tickable interface provides a mechanism for implementing time stepped simulations. The combination of these two behaviors leads to the CHDL simulation model.
The class tickable itself is a virtual class that defines four member functions:
tickable::pre_tick() tickable::tick() tickable::tock() tickable::post_tock()
During simulation, each of these is executed once per clock cycle. During each clock cycle, first all of the pre_tick() functions are called, then all of the tick() functions, etc. This somewhat ungainly state of affairs arose because the original simulator demanded both a tick() and tock() function, so that register state would not be updated until all register inputs had been read. Subsequent additions to CHDL required yet more priority levels to handle the updating of values both prior to and following the execution of user code when the simulation was being advanced one step at a time.
tickable is not a pure virtual class. It can itself be instantiated, although there is no practical reason to do so. Any combination of the four tick functions can be overridden or omitted from a tickable subclass. Most override only one or two.
The example from Tutorial 0:
node x; x = Reg(!x); TAP(x);
makes use of two types of node: the register node and the inverter node. The implementation of the inverter node type, invimpl, was explained in the previous section. So what about x itself, a register node. Its node type is regimpl, a type which inherits from both nodeimpl and tickable. Its tick() function reads the state of its input (a variable unique to regimpl, q, not src; remember, the node graph made using src should not have any cycles). The tock() function writes the value read from q to the output, another bool variable that is returned by the eval() function.
With only nandimpl, invimpl, and regimpl, a world of practical and useful digital logic circuits could be constructed and simulated. A ton of software would have to be written to make this practical. This software, of course, has already been written and represents the rest of CHDL and its companion library the CHDL STL. There has been some serious thought about moving the non-fundamental software out of CHDL and into a separate library, but for the sake of the user, this would only make sense once CHDL has stabilized and packages are provided for major distributions.