3
$\begingroup$

I got onto the topic of HDLs (Hardware Description Languages) from a comment elsewhere on this site.

The Wikipedia article states, rather tantalizingly:

One important difference between most programming languages and HDLs is that HDLs explicitly include the notion of time.

I tried to dig deeper in the article to better understand this statement, but I didn't get far.

One thing I did find was this great diagram of a flip flop, which certainly demonstrates the need to consider timing in hardware design. Rather than dealing with explicit on/off states, you are also dealing with high/low voltage propagation.

enter image description here

Naively, though, my immediate thought was, "Huh? All imperative languages include the notion of time. Only declarative or functional programming languages could be said to exclude the notion of time, and only by certain specific interpretations."

I think there is a valid point being made here, though, and I would very much like to better understand it. It's even stated to be an "important" difference. :)


So, again, what does it mean that HDLs "explicitly include the notion of time"? How does that distinguish them from programming languages in general from a CS standpoint?

$\endgroup$
  • $\begingroup$ Not sure if I've tagged this question appropriately. If I've missed better tags, I apologize! :) $\endgroup$ – Wildcard Jul 4 '17 at 4:38
5
$\begingroup$

Programming languages usually don't have a notion of time. They describe how things are sequenced, but usually they don't go further. When they do, that's relegated to the library part of the language, and it is to handle time computation or to handle real time measurement and delay.

HDL are used for two purposes: synthesis and simulation. For the first purpose, there is no more use of time than for a programming language. For the second purpose, time is inherently part of what is to be simulated. You need to know after which delay $Q$ will change after a change of $R$, and after which delay $\bar Q$ will do the same. The time here is thus not the real time, but a simulated one, which has no easy relationship with the real time during which the simulation will occurs.

Your circuit will be described in a VHDL-like syntax:

Q <= not (R or QBar) delay 1ns;
QBar <= not (S or Q) delay 1ns;

You can also write an oscillator, with no stable state:

Clock <= not Clock delay 5ns;

Time is thus present in the syntax of the language, and in its semantic as well (the language clearly states that $\bar Q$ will change 2ns of simulated time after $R$ does).

$\endgroup$
2
$\begingroup$

Imperative languages only implicitly have a notion of time. Primarily, demarcated by mutation of state, i.e. there's a before some variable was mutated and an after some variable was mutated. Declarative languages, as you say, don't have a notion of time unless they explicitly model it. There are a variety of ways of modeling time. Ptolemy II has a rather comprehensive framework and analysis, so I highly recommend looking at it and reading the book System Design, Modeling, and Simulation using Ptolemy II.

Hardware description languages (HDLs) are typically synchronous reactive (SR) languages like Lucid Synchrone, Esterel, and Sig. (Note, these are not HDLs but languages with a similar programming model.) The Dedalus language can be thought of as a synchronous reactive language, though that wasn't really the intent behind it. It nevertheless gives a concrete model of what's happening. Discrete functional reactive programming is a similar but distinct approach.

Another class of languages that are complementary is synchronous (or static) dataflow (SDF) languages such as StreamIt. The word "synchronous" here is being used in a different sense than in "synchronous reactive". Synchronous dataflow languages are probably better thought of as stream processing languages and they are widely used for signal processing tasks of various sorts. There are connections between these two models. A synchronous reactive program with no feedback corresponds to a homogeneous synchronous dataflow program. In a synchronous dataflow program, we have a bunch of stream processing functions where we know statically how many elements in each input stream each function consumes to produce a given number of elements in their output streams. If the rates are consistent — which can be statically checked — then it is possible to schedule the code so the inputs are always available and buffers with fixed, statically known sizes can be used. This model doesn't actually have a notion of time, but if the overall input streams represent regularly timed events, then the rates gain temporal significance.

The synchronous reactive model does have an explicit notion of time. In this model, there's a global (logical) clock. Every function is called on each tick. We can think of this as like the synchronous dataflow model except every stream processing function has a 1:1 rate. However, unlike the synchronous dataflow model, values can be absent and we can detect this. Another difference from the synchronous dataflow model in some synchronous reactive languages is that calculating a value at a particular time may (conceptually) require a fixed point calculation because the scheduling (within a tick) is data dependent. It's typically possible to do static checks to avoid this situation entirely.

Usually synchronous reactive systems allow different rates for different stream processing functions and this is what the absent values are typically used for. Conceptually, there's a "fastest" logical clock and every stream processing function is executed on every tick of that clock and running on a different (slower) clock means producing absent values for some ticks of the faster clock. To avoid needing to actually represent the absence/presence of values, static analyses can be done to make sure every stream processing function only attempts to read present values. Lucid Synchrone has a fairly sophisticated approach involving a type system and clock variables. It does also support explicitly reifying the absence/presence via its signal feature.

All the discussion above has used a logical notion of time. It's easy to go from there to a notion of real time by simply specifying a rate for the top-level fastest clock(s). However, the logical time model treats calculations as happening instantaneously. The execution time can be modeled by inserting delays into operations and/or using clocks running at different rates. However, while VHDL and Verilog do use a programming model similar to what I've described above, and they do provide annotations to specify timing, the latter are more descriptive than prescriptive. A functional simulation doesn't need them and the synthesizer ignores them (i.e. it assumes they accurately describe the chosen hardware). The annotations get used for timing simulations. In a functional simulation, the delays that need to exist for situations like your flip-flop to have a well-defined behavior are called delta delays and are conceptualized as "infinitesimal" time delays. In the SDF model, these delays would happen automatically. In a synchronous reactive model delays would need to be inserted (though will typically be embedded in primitives) and the delta delays correspond to ticks of the global logical clock. The notion of superdense time described in the Ptolemy II book in section 1.7.2 may also be a useful tool here.

So, in a hardware description language time enters in two distinct but correlated way. One is as an implicit part of the programming model and as a more logical notion. Another as explicit annotations to be used for timing simulation that can interact with the programming model. The latter can be coupled to the former by modeling the timing annotations as finite delays in terms of a sufficiently fine-grained logical clock. This requires delays be specified for everything (directly or indirectly) and is more computationally-intensive to model than the functional simulation (if for no other reason) because it's doing essentially the same thing at a finer grain. Sometimes the functional simulation is described as a Discrete Event (DE) simulation (another model of time described in the Ptolemy II book), but for synchronous sequential logic this more or less reduces to SDF or SR. (In general, in the DE model you can schedule an event to happen at any time in the future and simulation of it involves repeatedly processing the earliest unprocessed event in a priority queue. In [synchronous] sequential logic, events are being produced regularly and for a HDL "scheduling" something for the [distant, i.e. more than a cycle away] future would be explicitly modeled by, say, decrementing a counter until it reached 0.)

$\endgroup$
1
$\begingroup$

HDL's incorporate a notion of time in the following sense: they may allow you to talk about the current value of the circuit's state (e.g., registers) and the next value of its state. So, you might be able to write something

next(v) := x XOR y

where x represents the current value of x (in the current clock cycle) and next(v) represents what the value of v will be in the next clock cycle.

I'm not sure what the Wikipedia author meant when they said that most programming languages don't explicitly include a notion of time. Most programming languages don't have a next() operator, so perhaps that is what was meant.

$\endgroup$
  • $\begingroup$ How is what you're describing different from assignment in imperative languages? I don't think slightly different syntax is enough. $\endgroup$ – svick Jul 5 '17 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.