# A Composable Glitch-Aware Delay Model ††thanks: This research was partially
funded by the Austrian Science Fund (FWF) projects DMAC (P32431) and ADynNet
(P28182), the Centre National de la Recheche Scientifique projects ABIDE and
BACON, the Agence Nationale de la Recherche project FREDDA (ANR-17-CE40-0013),
and by the DigiCosme working group HicDiesMeus under ANR grant agreements
ANR-11-LABEX-0045-DIGICOSME and ANR-11-IDEX-0003-02

Jürgen Maier1  , Daniel Öhlinger1  , Ulrich Schmid1  , Matthias Függer2  ,
Thomas Nowak3  1ECS Group, TU Wien
<EMAIL_ADDRESS>{jmaier<EMAIL_ADDRESS>2CNRS & LSV, ENS
Paris-Saclay, Université Paris-Saclay & Inria
<EMAIL_ADDRESS>3Université Paris-Saclay, CNRS
<EMAIL_ADDRESS>
###### Abstract

We introduce the Composable Involution Delay Model (CIDM) for fast and
accurate digital simulation. It is based on the Involution Delay Model (IDM)
[Függer et al., IEEE TCAD 2020], which has been shown to be the only existing
candidate for faithful glitch propagation known so far. In its present form,
however, it has shortcomings that limit its practical applicability and
utility. First, IDM delay predictions are conceptually based on discretizing
the analog signal waveforms using specific matching input and output
discretization threshold voltages. Unfortunately, they are difficult to
determine and typically different for interconnected gates. Second,
metastability and high-frequency oscillations in a real circuit could be
invisible in the IDM signal predictions. Our CIDM reduces the characterization
effort by allowing independent discretization thresholds, improves
composability and increases the modeling power by exposing canceled pulse
trains at the gate interconnect. We formally show that, despite these
improvements, the CIDM still retains the IDM’s faithfulness, which is a
consequence of the mathematical properties of involution delay functions.

###### Index Terms:

digital timing simulation; composable delay estimation model; faithful glitch
propagation; pulse degradation

##  I Introduction and Context

Accurate prediction of signal propagation is a crucial task in modern digital
circuit design. Although the highest precision is obtained by analog
simulations, e.g., using SPICE, they suffer from excessive simulation times.
Digital timing analysis techniques, which rely on (i) discretizing the analog
waveform at certain thresholds and (ii) simplified interconnect resp. gate
delay models, are hence utilized to verify most parts of a circuit. Prominent
examples of the latter are pure (constant input-to-output delay $\Delta$) and
inertial delays (constant delay $\Delta$, pulses shorter than an upper bound
are removed) [1]. To accurately determine $\Delta$, which stays constant for
all simulation runs, highly elaborate estimation methods like CCSM [2] and
ECSM [3] are required.

Single-history delay models, like the _Degradation Delay Model (DDM)_ [4],
have been proposed as a more accurate alternative. Here, the input-to-output
delay $\delta(T)$ depends on a single parameter, the previous-output-to-input
delay $T$ (see Fig. 1). Still, Függer et al. [5] showed that none of the
existing delay models, including DDM, is faithful, as they fail to correctly
predict the behavior of circuits solving the canonical _short-pulse
filtration_ (SPF) problem.

Függer et al. [7] introduced the Involution Delay Model (IDM) and showed that,
unlike all other digital delay models known so far, it faithfully models
glitch propagation. The distinguishing property of the IDM is that the delay
functions for rising ($\delta_{\uparrow}$) and falling ($\delta_{\downarrow}$)
transitions form an involution, i.e.,
$-\delta_{\uparrow}(-\delta_{\downarrow}(T))=T$. A simulation framework based
on ModelSim, the Involution Tool, confirmed the accuracy of the model
predictions for several simple circuits [8].

Nevertheless, the IDM shows, at the moment, several shortcomings which impair
its composability:

(I) Ensuring the involution property requires specific (“matching”)
_discretization threshold voltages_ $V_{th}^{in*}$ and $V_{th}^{out*}$ to
discretize the analog waveforms at in- and output. These are not only unique
for every single gate in the circuit but also difficult to determine. (II) The
discretization threshold voltages may vary from gate to gate, i.e., the
matching output discretization threshold voltage $V_{th}^{out*}$ of a given
gate $G_{1}$ and the matching input discretization threshold voltage
$V_{th}^{in*}$ of a successor gate $G_{2}$ are not necessarily the same.
Consequently, just adding the delay predictions of the IDM for $G_{1}$ and
$G_{2}$ cannot be expected to accurately model the overall delay of their
composition. This is particularly true for circuits designs where different
transistor threshold voltages [9] are used for tuning the delay-power trade-
off [10] or reliability [11].

(III) Intermediate voltages, caused by creeping or oscillatory metastability,
are expressed differently for various values of $V_{th}^{out*}$: Ultimately, a
single analog trajectory may result in either zero, one or a whole train of
digital transitions.

in($t$)$t$out($t$)$t$$T$$\delta_{\uparrow}(T)$

Figure 1: The delay $\delta_{\uparrow}$ as function of $T$. Taken from [8].

Main contributions:

In the present paper, we address all these shortcomings.

  1. 1)

Based on the empirical analysis of the impact of $V_{th}^{in}$ and
$V_{th}^{out}$ on the delay functions of a real circuit, we introduce CIDM
channels, which are essentially made up of a typically asymmetric (for
rising/falling transitions) pure delay shifter followed by an IDM channel (a
PI channel). CIDM channels can model gates with arbitrarily discretization
threshold $V_{th}^{in*}$ and $V_{th}^{out*}$ and simplify the characterization
of their delay functions. Moreover, the CIDM exposes cancellations at the
interconnect between gates, rather than removing them silently as in the IDM.
Consequently, digital timing simulators can, for example, record trains of
canceled pulses and report it to the user accordingly.

  2. 2)

We prove that CIDM channels are _not_ equivalent to IDM channels per se, in
the sense that their delay functions are not involutions. However, the fact
that both essentially contain the same components allows us to map a CIDM
circuit description to an IDM one: For every circuit modeled with compatible
CIDM channels, modeling matching discretization threshold voltages, there is
an equivalent decomposition into IP channels, consisting of an IDM channel
followed by an arbitrary pure delay shifter. Somewhat surprisingly, the
mathematical properties of involution delay functions reveal that IP channels
are instances of IDM channels. Consequently, the faithfulness of the IDM
carries over literally to the CIDM.

  3. 3)

We present the theoretical foundations and an implementation of a simulation
framework for CIDM, which was incorporated into the Involution Tool [8].
111The original Involution Tool is accessible via
https://github.com/oehlinscher/InvolutionTool, our extended version is
provided at https://github.com/oehlinscher/CDMTool. We also provide a proof of
correctness of our simulation algorithm, which shows that it always terminates
after having produced the unique execution of an arbitrary circuit composed of
gates with compatible CIDM channels.

  4. (4)

We conducted a suite of experiments, both on a custom inverter chain with
varying matching threshold voltages and a standard inverter chain. In the
former case, we observed an impressive improvement of modeling accuracy for
CIDM over IDM in many cases.

Paper organization: We start with some basic properties of the existing IDM in
Section II. In Section III, we empirically analyze the impact of changing
$V_{th}^{out*}$ and $V_{th}^{in*}$ on the delay functions. Section IV
introduces and justifies the CIDM, while Section V proves its faithfulness. In
Section VI, we describe the CIDM simulation algorithm and its implementation,
and prove that its correctness. Section VII provides the results of our
experiments. Some conclusion in Section VIII round-off our paper.

##  II Involution Delay Model Basics

In this section, we briefly discuss the IDM. For further details, the
interested reader is referred to the original publication [7].

The essential benefit of using delay functions which are involutions is their
ability to perfectly cancel zero-time input glitches: In Fig. 1, it is
apparent that the rising input transition causes a rising transition at the
output, after delay $\delta_{\uparrow}(T)$. Now suppose that there is an
additional falling input transition immediately after the rising one, actually
occurring at the same time. Since this constitutes a zero-time input glitch,
which is almost equivalent to no pulse at all, the output should behave as if
it was not there at all.

For this purpose it is required that the delay of the additional falling input
transition to go _back in time_ , i.e., to exactly hit the predicted time of
the previous falling output transition: Note carefully that just canceling the
rising output transition, by generating the falling output transition at or
before the rising one, would not suffice, as the calculation of the parameter
$T$ for the next transition depends on the time of the previous output
transition. It is not difficult to check that this going back is indeed
achieved when $-\delta_{\uparrow}(-\delta_{\downarrow}(T))=T$ and
$-\delta_{\downarrow}(-\delta_{\uparrow}(T))=T$ holds. As the IDM also
requires the delay functions to be strictly increasing and concave, the
involution property enforces them to be symmetric w.r.t. the 2nd median
$y=-x$.

Lemma 3 in [7], restated as Lemma 1 below, shows that _strictly causal_
involution channels, characterized by strictly increasing, concave delay
functions with $\delta_{\uparrow}(0)>0$ and $\delta_{\downarrow}(0)>0$, give
raise to a unique $\delta_{min}>0$ that (i) resides on the 2nd median $y=-x$
and (ii) is shared by $\delta_{\uparrow}$ and $\delta_{\downarrow}$ due to the
involution property.

######  Lemma 1 ([7, Lem. 3]).

A strictly causal involution channel has a unique $\delta_{min}>0$ defined by
$\delta_{\uparrow}(-\delta_{min})=\delta_{min}=\delta_{\downarrow}(-\delta_{min})$.

In [7], Függer et al. have shown that self-inverse delay functions arise
naturally in a (generalized) standard analog model that consists of a pure
delay, a slew-rate limiter with generalized switching waveforms and an ideal
comparator (see Fig. 2). First, the binary-valued input $u_{i}$ is delayed by
$\delta_{min}>0$, which assures causal channels, i.e.,
$\delta_{\uparrow/\downarrow}(0)>0$. For every transition on $u_{d}$, the
generalized slew-rate limiter switches to the corresponding waveform
($f_{\downarrow}/f_{\uparrow}$ for a falling/rising transition). Note that the
value at $u_{r}$ (the analog output voltage) does not jump, i.e., is a
continuous function. Finally, the comparator generates the output $u_{o}$ by
discretizing the value of this waveform w.r.t. the discretization threshold
$V_{th}^{out}$.

Using this representation, the need for
$\delta_{\uparrow}(T),\delta_{\downarrow}(T)<0$ can be explained by the
necessity to cover sub-threshold pulses, i.e., ones that do not reach the
output discretization threshold. In this case, the switching waveform has to
be followed into the past to cross $V_{th}^{out}$, resulting in the seemingly
acausal behavior.

$+$$-$${u_{i}}$$\delta_{min}$$u_{d}$$u_{r}$$+$$-$$V_{th}^{out}$$u_{o}$$V_{DD}$GND$\infty$$V_{DD}$GND$\infty$

$u(t)$$t$$V_{th}$$u_{i}$$u_{d}$$u_{o}$$u_{r}$$f_{\uparrow}$$f_{\downarrow}$$T_{1}$$\delta_{\uparrow}(T_{1})$$T_{2}$$\delta_{\downarrow}(T_{2})$

Figure 2: Analog channel model representation (upper part) with a sample
execution (bottom part). Adapted from [7].

##  III Discretization Threshold Voltages

In this section, we will empirically explore the relation of gate delays and
discretization threshold voltages by means of simulation results.222Our
simulations have been performed for a buffer in the $15\text{\,}\mathrm{nm}$
NanGate library. However, since we are only reasoning about qualitative
aspects common to all technologies, the actual choice has no significance.  In
most of the following observations, we assume that a given physical (analog)
gate is to be characterized as a zero-time Boolean gate with a succeeding IDM
channel that models the delay. In order to accomplish concrete values,
discretization threshold voltages $V_{th}^{in}$ at the input and
$V_{th}^{out}$ at the output of a gate have to be fixed, and the pure delay
component $\delta_{min}$ of the IDM channel as well as the delay functions
$\delta_{\uparrow}$ and $\delta_{\downarrow}$ are determined accordingly.

######  Definition 2.

The input and output discretization voltages $V_{th}^{in}$ and $V_{th}^{out}$
are called _matching_ for a gate, if the induced delay functions
$\delta_{\uparrow}(T)$, $\delta_{\downarrow}(T)$ fulfill the condition
$\delta_{\uparrow}(-\delta_{min})=\delta_{min}=\delta_{\downarrow}(-\delta_{min})$.
To stress that a pair of input and output discretization threshold voltages is
matching, they will be denoted as $V_{th}^{in*}$ and $V_{th}^{out*}$.

We will now characterize properties of matching discretization threshold
voltages. They depend on many factors, including transistor threshold voltages
[9] and the symmetry of the pMOS vs. nMOS stack. Since varying these
parameters is commonly used in advanced circuit design to trade delay for
power consumption [10, 12] and reliability [11], as well as for implementing
special gates (e.g. logic-level conversion [13]), the range of suitable
discretization threshold voltages could differ significantly among gates.

Figure 3: The relationship among $V_{th}^{in*}$, $\delta_{min}$ and
$V_{th}^{out*}$.

Considering these circumstances it seems impossible that output and input
descretization values coincide among connected gates. However, the following
observation shows that there is an unlimited number of matching discretization
threshold pairs for IDM:

######  Observation 3.

For every choice of $V_{th}^{in}$, there is exactly one matching
$V_{th}^{out}$. Fixing either of them uniquely determines the other and, in
addition, also the pure delay $\delta_{min}$.

###### Justification.

Let us fix $V_{th}^{out}$ and investigate how $V_{th}^{in}$ and $\delta_{min}$
can be determined. For this purpose, we consider an analog pulse at $V_{out}$
that barely touches $V_{th}^{out}$, i.e., results in a zero-time glitch in the
digital domain. There is a _unique_ positive and a _unique_ negative analog
output pulse with this shape, which is both confirmed by simulation results
and analytic considerations on the underlying system of differential equations
[14]. Now shift the positive and negative pulses in time such that their
output voltages touch $V_{th}^{out}$, one from below and the other from above,
at time $t_{o}$ (see Fig. 3). Due to the condition
$\delta_{\downarrow}(-\delta_{min})=\delta_{min}=\delta_{\uparrow}(-\delta_{min})$,
this implies that the falling transition of the positive pulse and the rising
transition of the negative pulse at the input must both cross $V_{th}^{in}$ at
time $t_{i}=t_{o}-\delta_{min}$. Thus, fixing $V_{th}^{out*}$ uniquely
determines the matching $V_{th}^{in*}$ and $\delta_{min}=t_{o}-t_{i}$. ∎

Actually determining the matching $V_{th}^{out*}$ for a given $V_{th}^{in*}$
and vice versa is a challenging task. For a start, let us investigate the
static case with $f_{s}$ being the static transfer function of a gate. In this
setup, an output derivative $V_{out}^{\prime}=0$ is achieved for all values
fulfilling the condition $V_{out}=f_{s}(V_{in})$ since $f_{s}$ represents the
stable states of the gate. To obtain high accuracy when discretizing the
analog signal, one typically chooses the output threshold such that the
respective output waveform for a full-range input pulse has a steep slope at
this point. While $V_{th}^{out*}=V_{DD}/2$ is in general a good choice, the
corresponding $V_{th}^{in*}$ will differ significantly between balanced and
high-threshold inverters, for example.

Besides these static considerations, for a dynamic input, coupling
capacitances cause a current at the output, which must be compensated via the
gate-source voltages of the transistors as well. Obviously, the required
overshoot w.r.t. $V_{th}^{in}$, and hence the time until this value is
reached, depends on many parameters like the size of the coupling capacitances
and the slope of the input signal.

It is also worth mentioning that CMOS logic shows an inverse proportionality
between in- and output, i.e., increasing the input increases the conductivity
to GND, which drains the output, and vice versa. This implies that the current
induced by the alternation of the input goes against the change of the output
current, which effectively slows down the switching operation, and thus
increases the pure delay $\delta_{min}>0$.

3 has a severe consequence for the simulation of circuits in any model, like
IDM, where Lemma 1 holds:

######  Observation 4.

Fixing either $V_{th}^{in}$ or $V_{th}^{out}$ for a single gate $G$ fixes the
threshold voltages of all gates in the circuit when it is simulated in a model
where 3 holds.

###### Justification.

For a single gate, the observation follows from the unique relationship
between $V_{th}^{in*}$ and $V_{th}^{out*}$ by 3. For gates in a path, the
ability to just add up their delays requires output and next input
discretization thresholds to be the same. ∎

Since the detailed relation of $V_{th}^{in*}$ and $V_{th}^{out*}$ according to
3 depends on the individual gate, this means that the discretization threshold
voltages across a circuit may vary in _a priori_ arbitrary ways, depending on
the interconnect topology and the gate properties. In the extreme, the
discretization thresholds can exceed the acceptable range for some gates, and
even lead to unsatisfiable assignments in the case of circuits containing
feedback-loops. In any case, it may take a large effort to properly
characterize every gate such that the dependencies among discretization
thresholds are fulfilled. By contrast, an ideally composable delay model uses
a uniform discretization threshold such as
$V_{th}^{out}=V_{th}^{in}=V_{DD}/2$.

To investigate if IDM allows such a uniform choice, we proceed with 5:

######  Observation 5.

Characterizing a gate with non-matching discretization thresholds
$V_{th}^{in}$ and $V_{th}^{out*}$, where matching $V_{th}^{in*}$ and
$V_{th}^{out*}$ lead to an IDM channel with pure delay
$\overline{\delta}_{min}$, results in delay functions $\delta_{\uparrow}(T)$,
$\delta_{\downarrow}(T)$, which satisfy
$\delta_{\uparrow}(-\delta^{\uparrow}_{min})=\delta^{\uparrow}_{min}$ and
$\delta_{\downarrow}(-\delta^{\downarrow}_{min})=\delta^{\downarrow}_{min}$
for
$\delta^{\uparrow}_{min}=\overline{\delta}_{min}+\Delta^{+}\neq\delta^{\downarrow}_{min}=\overline{\delta}_{min}+\Delta^{-}$.
$\Delta^{+}$ and $\Delta^{-}$ have opposite sign, with $\Delta^{+}>0$ for
$V_{th}^{in}<V_{th}^{in*}$.

###### Justification.

The observation follows from refining the argument used for confirming 3,
where it was shown how matching $V_{th}^{in*}$ and $V_{th}^{out*}$ are
achieved. For the non-matching case, we increase resp. decrease $V_{th}^{in}$,
starting from $V_{th}^{in*}$, while keeping everything else, i.e., electronic
characteristics, waveforms and $V_{th}^{out}$, unchanged. As illustrated in
Fig. 3 for $V_{th}^{in}<V_{th}^{in*}$, it still takes
$\overline{\delta}_{min}$ from hitting $V_{th}^{in*}$ (at time
$t_{o}-\overline{\delta}_{min}$) to seeing a zero time glitch (at time
$t_{o}$) at the output. The falling transition has already crossed
$V_{th}^{in*}$ when it hits on $V_{th}^{in}$, whereas the rising transition
still has some way to go: Denoting the switching waveforms of the preceding
gate (driving the input) by $f_{\uparrow}$ and $f_{\downarrow}$, the pure
delay for the rising resp. falling transition evaluates to
$\delta^{\uparrow}_{min}=\overline{\delta}_{min}+\Delta^{+}$ and
$\delta^{\downarrow}_{min}=\overline{\delta}_{min}+\Delta^{-}$ with

$\Delta^{+}=f_{\uparrow}^{-1}(V_{th}^{in*})-f_{\uparrow}^{-1}(V_{th}^{in}),\ \
\
\Delta^{-}=f_{\downarrow}^{-1}(V_{th}^{in*})-f_{\downarrow}^{-1}(V_{th}^{in}).$
(1)

Consequently,
$\delta_{\uparrow}(-\delta^{\uparrow}_{min})=\delta^{\uparrow}_{min}$ and
$\delta_{\downarrow}(-\delta^{\downarrow}_{min})=\delta^{\downarrow}_{min}$
indeed holds. Finally, since $f_{\uparrow}$ must obviously rise and
$f_{\downarrow}$ must fall, it follows that if $\Delta^{+}>0$ (the case in
Fig. 3) then $\Delta^{-}<0$. ∎

Figure 4: Characterizing a gate with $V_{th}^{in}=V_{th}^{out}=V_{DD}/2$.

Fig. 4 shows the derived delay function for non-matching discretization
thresholds. Clearly visible are the different pure delays
$\delta^{\uparrow}_{min}\neq\delta^{\downarrow}_{min}$. Please note, that in
our justification of 5, we focused on $\delta_{min}$ and how it changes with
varying discretization threshold voltages. If the rising and falling switching
waveforms were always the same, as is assumed in the analog channel model Fig.
2, this would result in delay functions that are fixed in shape and are simply
shifted along the 2nd median. The actual delay functions of gates, obtained by
analog simulations, for example, exhibit additional deviations (for
$T\neq\delta^{\uparrow/\downarrow}_{min}$), however, since the shape of the
input switching waveforms also vary. Consequently, the difference between
$V_{th}^{in*}$ and $V_{th}^{in}$ will not always be passed in constant time.

Finally, the dependency of the IDM on the particular choice of the
discretization threshold voltages also reveals a different problem:

######  Observation 6.

Different choices of $V_{th}^{out}$ can significantly change the digital model
prediction of the IDM.

###### Justification.

Sub-threshold pulses are automatically removed by the comparator in Fig. 2,
i.e., they are completely invisible in the digital signal that is fed to the
successor gate. Consequently analog traces, that do not cross $V_{th}^{out}$,
e.g., high-frequency oscillations at intermediate voltage levels, may be
totally suppressed: Assume an oscillatory behavior of a gate output with
minimal voltage $V_{0}$ and maximal $V_{1}$. These oscillations would only be
reflected in the digital discretization if $V_{th}^{out}\in(V_{0},V_{1})$. ∎

##  IV Composable Involution Delays

In this section, we define our _Composable Involution Delay Model_ (CIDM),
which allows to circumvent the problems presented in the previous section:
According to 5, using non-matching thresholds introduces a pure delay shift.
The major building blocks of our CIDM are hence _PI channels_ , which consist
of a pure delay shifter with different shifts $\Delta^{+}$ and $\Delta^{-}$
for rising and falling transitions 333A pure delay shifter with
$\Delta^{+}\neq\Delta^{-}$ causes a constant extension/compression of up/down
input pulses by $\pm(\Delta^{+}-\Delta^{-})$. followed by an IDM channel. In
order to also alleviate the problem of invisible oscillations identified in 6,
we re-shuffle the internal architecture of the original involution channels
shown in Fig. 2 in order to expose trains of canceled transitions on the
interconnecting wires.

######  Theorem 7 (PI channel properties).

Consider a channel PI formed by the concatenation of a pure delay shifter
$(\Delta^{+},\Delta^{-})$ with $\Delta^{+},\Delta^{-}\in\mathbb{R}$ followed
by an involution channel $c$, given via $\overline{\delta}_{\uparrow}(.)$ and
$\overline{\delta}_{\downarrow}(.)$ with minimum delay
$\overline{\delta}_{min}$. Then PI is _not_ an involution channel, but rather
characterized by delay functions defined as

$\delta_{\uparrow}(T)=\Delta^{+}+\overline{\delta}_{\uparrow}(T+\Delta^{+})\qquad\delta_{\downarrow}(T)=\Delta^{-}+\overline{\delta}_{\downarrow}(T+\Delta^{-}).$
(2)

These functions satisfy

$\displaystyle\delta_{\uparrow}\bigl{(}-\delta_{\downarrow}(T)-(\Delta^{+}-\Delta^{-})\bigr{)}$
$\displaystyle=-T+(\Delta^{+}-\Delta^{-})$ (3)
$\displaystyle\delta_{\downarrow}\bigl{(}-\delta_{\uparrow}(T)+(\Delta^{+}-\Delta^{-})\bigr{)}$
$\displaystyle=-T-(\Delta^{+}-\Delta^{-})$ (4)
$\displaystyle\delta_{\uparrow}(-\delta^{\uparrow}_{min})$
$\displaystyle=\delta^{\uparrow}_{min}$ (5)
$\displaystyle\delta_{\downarrow}(-\delta^{\downarrow}_{min})$
$\displaystyle=\delta^{\downarrow}_{min}$ (6)

for $\delta^{\uparrow}_{min}=\overline{\delta}_{min}+\Delta^{+}$ and
$\delta^{\downarrow}_{min}=\overline{\delta}_{min}+\Delta^{-}$.

###### Proof.

Consider an input signal consisting of a simple negative pulse, as depicted in
Fig. 1. Let $t_{i}^{\prime}$ resp. $t_{i}$ be the time of the falling resp.
rising input transition, $t_{p}^{\prime}$ resp. $t_{p}$ the time of the
falling resp. rising transition at the output of the pure delay shifter, and
$t_{o}^{\prime}$ resp. $t_{o}$ the time of the falling resp. rising transition
after the involution channel. With $\overline{T}=t_{p}-t_{o}^{\prime}$, we get
$\overline{\delta}_{\uparrow}(\overline{T})=t_{o}-t_{p}$ as well as
$t_{p}=t_{i}+\Delta^{+}$ and $t_{p}^{\prime}=t_{i}^{\prime}+\Delta^{-}$.

For the delay function $\delta_{\uparrow}(T)$ of the PI channel, if we set
$T=t_{i}-t_{o}^{\prime}=t_{i}-t_{p}+t_{p}-t_{o}^{\prime}=-\Delta^{+}+\overline{T}$,
we find

$\displaystyle\delta_{\uparrow}(T)$
$\displaystyle=t_{o}-t_{i}=t_{o}-t_{p}+t_{p}-t_{i}=\Delta^{+}+\overline{\delta}_{\uparrow}(\overline{T})$
$\displaystyle=\Delta^{+}+\overline{\delta}_{\uparrow}(T+\Delta^{+})$ (7)

as asserted. By setting $T=-\overline{\delta}_{min}-\Delta^{+}$ and using
$\overline{\delta}_{\uparrow}(-\overline{\delta}_{min})=\overline{\delta}_{min}$
the equality
$\delta_{\uparrow}(-\overline{\delta}_{min}-\Delta^{+})=\Delta^{+}+\overline{\delta}_{min}$
is achieved, which confirms 5.

By analogous reasoning for an up-pulse at the input, which results in the same
equations as above with $\Delta^{+}$ exchanged with $\Delta^{-}$ and
$\overline{\delta}_{\uparrow}(\overline{T})$ with
$\overline{\delta}_{\downarrow}(\overline{T})$, we also get

$\displaystyle\delta_{\downarrow}(T)$
$\displaystyle=t_{o}-t_{i}=t_{o}-t_{p}+t_{p}-t_{i}=\Delta^{-}+\overline{\delta}_{\downarrow}(\overline{T})$
$\displaystyle=\Delta^{-}+\overline{\delta}_{\downarrow}(T+\Delta^{-})$ (8)

as asserted. Setting $T=-\overline{\delta}_{min}-\Delta^{-}$ and using
$\overline{\delta}_{\downarrow}(-\overline{\delta}_{min})=\overline{\delta}_{min}$
confirms 6 as well.

Using a simple parameter substitution allows to transform 7 and 8 to

$\displaystyle\overline{\delta}_{\uparrow}(\overline{T})$
$\displaystyle=\delta_{\uparrow}(\overline{T}-\Delta^{+})-\Delta^{+}$ (9)
$\displaystyle\overline{\delta}_{\downarrow}(\overline{T})$
$\displaystyle=\delta_{\downarrow}(\overline{T}-\Delta^{-})-\Delta^{-}.$ (10)

Utilizing these in the involution property of $\overline{\delta}_{\uparrow}$
and $\overline{\delta}_{\downarrow}$ provides

$\displaystyle\overline{T}$
$\displaystyle=-\overline{\delta}_{\uparrow}\bigl{(}-\overline{\delta}_{\downarrow}(\overline{T})\bigr{)}$
$\displaystyle=-\delta_{\uparrow}\bigl{(}-\overline{\delta}_{\downarrow}(\overline{T})-\Delta^{+}\bigr{)}+\Delta^{+}$
$\displaystyle=-\delta_{\uparrow}\bigl{(}-\bigl{(}\delta_{\downarrow}(\overline{T}-\Delta^{-})-\Delta^{-}\bigr{)}-\Delta^{+}\bigr{)}+\Delta^{+}$
$\displaystyle=-\delta_{\uparrow}\bigl{(}-\delta_{\downarrow}(\overline{T}-\Delta^{-})+\Delta^{-}-\Delta^{+}\bigr{)}+\Delta^{+}.$

If we substitute $T=\overline{T}-\Delta^{-}$ in the last line, we arrive at

$T-(\Delta^{+}-\Delta^{-})=-\delta_{\uparrow}\bigl{(}-\delta_{\downarrow}(T)-(\Delta^{+}-\Delta^{-})\bigr{)},$
(11)

which confirms 3.

Doing the same for the reversed involution property of $c$, provides

$\displaystyle\overline{T}$
$\displaystyle=-\overline{\delta}_{\downarrow}\bigl{(}-\overline{\delta}_{\uparrow}(\overline{T})\bigr{)}$
$\displaystyle=-\delta_{\downarrow}\bigl{(}-\overline{\delta}_{\uparrow}(\overline{T})-\Delta^{-}\bigr{)}+\Delta^{-}$
$\displaystyle=-\delta_{\downarrow}\bigl{(}-\bigl{(}\delta_{\uparrow}(\overline{T}-\Delta^{+})-\Delta^{+}\bigr{)}-\Delta^{-}\bigr{)}+\Delta^{-}$
$\displaystyle=-\delta_{\downarrow}\bigl{(}-\delta_{\uparrow}(\overline{T}-\Delta^{+})+\Delta^{+}-\Delta^{-}\bigr{)}+\Delta^{-}.$

If we substitute $T=\overline{T}-\Delta^{+}$ in the last line, we arrive at

$T+(\Delta^{+}-\Delta^{-})=-\delta_{\downarrow}\bigl{(}-\delta_{\uparrow}(T)+\Delta^{+}-\Delta^{-}\bigr{)},$
(12)

which confirms 4.

∎

Eq. 2 implies that $\delta_{\uparrow}(.)$ resp. $\delta_{\downarrow}(.)$ are
the result of shifting $\overline{\delta}_{\uparrow}(.)$ resp.
$\overline{\delta}_{\downarrow}(.)$ along the 2nd median by $\Delta^{+}$ resp.
$\Delta^{-}$. It is apparent from Fig. 4, though, that the choice of
$\Delta^{+}$, $\Delta^{-}$ cannot be arbitrary, as it restricts the range of
feasible values for $T$ via the domain of $\overline{\delta}_{\uparrow}(.)$
resp. $\overline{\delta}_{\downarrow}(.)$ (see Definition 10 for further
details).

This becomes even more apparent in the analog channel model. Fig. 5 (a) shows
an extended block diagram of an IDM channel where we applied two changes:
First, we added a (one-input, one-output) zero-time Boolean gate $G$. Second,
we split the comparator at the end into a thresholder $T\\!h$ and a
cancellation unit $C$. The _thresholder unit_ $T\\!h$ outputs, for each
transition on $u_{d}$, a corresponding $V_{th}$-crossing time of $u_{r}$,
independently of whether it will actually be reached or not. For subthreshold
pulses, the transition might even be scheduled in the past. The _cancellation
unit_ $C$ only propagates transitions that are in the correct temporal order.
The components $T\\!h$ and $C$ together implement the same functionality as a
comparator.

At the beginning of the channel, the Boolean gate $G$ (we assume a single-
input gate for now) evaluates the input signal $u_{i}$ in zero time and
outputs $u_{g}$, which is subsequently delayed by the pure delay shifter
$\Delta^{+/-}$. Here lies the cause of the problem: If either $\Delta^{+}<0$
or $\Delta^{-}<0$ it is possible that transitions $u_{p}$ are in reversed
temporal order which, after being delayed by the constant pure delay
$\overline{\delta}_{min}$, have to be processed in this fashion by the slope
delimiter. The latter is, however, only defined on traces encoded via the
alternating Boolean signal transitions’ _Waveform Switching Times (WST)_ ,
which occur in a strictly increasing temporal order and mark the points in
time when the switching waveforms shall be changed. Placing the delay shifter
in front of the gate, as shown in Fig. 5 (b), does not change the situation,
since the gate also expects transitions in the correct temporal order (note
that this is not equal to WST since the pure delay is still missing).

(a)$G$$u_{i}$$u_{g}$$\Delta^{+/-}$$u_{p}$$\overline{\delta}_{min}$$u_{d}$$u_{r}$$T\\!h$$V_{th}$$u_{s}$$C$${u_{c}}$(b)$\Delta^{+/-}$$u_{i}$$u_{p}$$G$$u_{g}$$\overline{\delta}_{min}$$u_{d}$$u_{r}$$T\\!h$$V_{th}$$u_{s}$$C$${u_{c}}$(c)$\Delta^{+/-}$$u_{i}$$u_{p}$$C$$u_{c}$$G$$u_{g}$$\overline{\delta}_{min}$$u_{d}$$u_{r}$$T\\!h$$V_{th}$${u_{s}}$

Figure 5: Candidate channel models for CIDM.

One possibility to avoid transitions in the wrong temporal order at the
Boolean gate is to move the canceling unit to the front, as shown in Fig. 5
(c). This solves our present problems but has the consequence, that now
transitions are interchanged among gates using the _Threshold Crossing Times
(TCT)_ encoding: The TCT encoding gives, in sequence order, the points in time
when the analog switching waveform would have crossed $V_{th}$ (it is not
required that it actually does). Consequently, a signal given in TCT also
exposes canceled transitions. Actually this is very convenient for us, since
this allows us implicitly to detect oscillations independent of the chosen
output threshold and thus solves design challenge (3) from the introduction.

Not all signals in Fig. 5 can actually be mapped to TCT or WST; by suitably
recombining the components in our CIDM channel, however, these encodings will
be sufficient for our purposes. More specifically, TCT will be created by the
scheduler $S$, subsequently modified by the delay shifter, altered by the
cancellation unit $C$, evaluated by the Boolean gate and finally transformed
to WST by $\overline{\delta}_{min}$.

Now we are finally ready to formally define a CIDM channel (see Fig. 6). Note
that, although a PI channel differs by its internal structure significantly
from the CIDM channel, they are equivalent with respect to Theorem 7.

######  Definition 8.

A CIDM channel comprises in succession of a pure delay shifter, a cancellation
unit, a Boolean gate, a pure-delay unit, a shaping unit and a thresholding
unit [see Fig. 5(c)].

One may wonder whether CIDM channels could be partitioned also in a different
fashion. The answer is yes, several other partitions are possible. For
example, one could transmit signal $u_{g}$ and move the slew-rate limiter and
the scheduler to the succeeding channel. This would, however, mean that
properties of single CIDM channels depend on the properties of both
predecessor and successor gate, which complicates the process of channel
characterization and parametrization based on design parameters.

$\Delta^{+/-}$${u_{i}^{1}}$$u_{p}^{1}$$C$$\Delta^{+/-}$${u_{i}^{n}}$$u_{p}^{n}$$C$$\vdots$$\vdots$$G$$u_{c}^{1}$$u_{c}^{n}$$u_{g}$$\overline{\delta}_{min}$$u_{d}$$u_{r}$$T\\!h$$V_{th}$${u_{s}}$

Figure 6: Channel model for CIDM.

The main practical advantage of a CIDM channel, which is a generalization of
an IDM channel (just set $\Delta^{-}=\Delta^{+}=0$), is the additional degree
of freedom for gate characterization in conjunction with the fact that a
single channel encapsulates a single gate.

##  V Glitch Propagation in the CIDM

Since CIDM channels do not satisfy the involution property, the question about
faithful glitch propagation arises. After all, the proof of faithfulness of
IDM [7] rests on the continuity of IDM channels, which has been proved only
for involution delay functions. In this section, we will show that, for every
modeling of a circuit with our CIDM channels, there is an equivalent modeling
with IDM channels. Consequently, faithfulness of the IDM carries over to the
CIDM.

For this purpose, we consider two successive CIDM channels and investigate the
_logical channel_ , i.e., the interconnection between two gates $G_{1}$ and
$G_{2}$ as shown in Fig. 7. For conciseness, we integrate
$\overline{\delta}_{min}$, the slew-rate limiter and the scheduler $S$ in a
new block $DSS$, and $\Delta^{+/-}$ followed by $T\\!h$ in the new block
$PT\\!h$. Using this notation, the logical channel consists of the $DSS$ block
of the predecessor gate $G_{1}$ and the $PT\\!h$ block of the successor gate
$G_{2}$. Overall, this is just an IDM channel followed by a pure delay
shifter, which will be denoted in the sequel as _IP channel_. The following
Theorem 9 proves the somewhat surprising fact that every IP channel satisfies
the properties of an involution channel:

######  Theorem 9 (IP channel properties).

Consider an IP channel formed by an involution channel given via
$\overline{\delta}_{\uparrow}(.)$, $\overline{\delta}_{\downarrow}(.)$,
followed by a pure delay shifter $(\Delta^{+},\Delta^{-})$ with
$\Delta^{+},\Delta^{-}\in\mathbb{R}$. Then, it is an involution channel,
characterized by some delay functions $\delta_{\uparrow}(.)$,
$\delta_{\downarrow}(.)$.

###### Proof.

Consider an input signal consisting of a single negative pulse, as depicted in
Fig. 1. Let $t_{i}^{\prime}$ resp. $t_{i}$ be the time of the falling resp.
rising input transition, $t_{c}^{\prime}$ resp. $t_{c}$ the time of the
falling resp. rising transition at the output of the involution channel, and
$t_{o}^{\prime}$ resp. $t_{o}$ the time of the falling resp. rising transition
after the pure delay shifter. With $\overline{T}=t_{i}-t_{c}^{\prime}$, we get
$\overline{\delta}_{\uparrow}(\overline{T})=t_{c}-t_{i}$ as well as
$t_{o}^{\prime}=t_{c}^{\prime}+\Delta^{-}$ and $t_{o}=t_{c}+\Delta^{+}$.

By setting
$T=t_{i}-t_{o}^{\prime}=t_{i}-t_{c}^{\prime}+t_{c}^{\prime}-t_{o}^{\prime}=\overline{T}-\Delta^{-}$
for the delay function $\delta_{\uparrow}(T)$ of the IP channel we find

$\displaystyle\delta_{\uparrow}(T)$
$\displaystyle=t_{o}-t_{i}=t_{o}-t_{c}+t_{c}-t_{i}=\Delta^{+}+\overline{\delta}_{\uparrow}(\overline{T})$
$\displaystyle=\Delta^{+}+\overline{\delta}_{\uparrow}(T+\Delta^{-}).$ (13)

By analogous reasoning for a an up-pulse at the input, which results in the
same equations as above with $\Delta^{+}$ exchanged with $\Delta^{-}$ and
$\overline{\delta}_{\uparrow}(\overline{T})$ with
$\overline{\delta}_{\downarrow}(\overline{T})$, we also get

$\displaystyle\delta_{\downarrow}(T)$
$\displaystyle=t_{o}-t_{i}=t_{o}-t_{c}+t_{c}-t_{i}=\Delta^{-}+\overline{\delta}_{\downarrow}(\overline{T})$
$\displaystyle=\Delta^{-}+\overline{\delta}_{\downarrow}(T+\Delta^{+}).$ (14)

Equations (13) and (14) are equivalent to

$\displaystyle\overline{\delta}_{\uparrow}(\overline{T})$
$\displaystyle=\delta_{\uparrow}(\overline{T}-\Delta^{-})-\Delta^{+}$ (15)
$\displaystyle\overline{\delta}_{\downarrow}(\overline{T})$
$\displaystyle=\delta_{\downarrow}(\overline{T}-\Delta^{+})-\Delta^{-}$ (16)

which can be used in the involution property of $\overline{\delta}_{\uparrow}$
and $\overline{\delta}_{\downarrow}$ to achieve

$\displaystyle\overline{T}$
$\displaystyle=-\overline{\delta}_{\uparrow}\bigl{(}-\overline{\delta}_{\downarrow}(\overline{T})\bigr{)}$
$\displaystyle=-\delta_{\uparrow}\bigl{(}-\overline{\delta}_{\downarrow}(\overline{T})-\Delta^{-}\bigr{)}+\Delta^{+}$
$\displaystyle=-\delta_{\uparrow}\bigl{(}-\bigl{(}\delta_{\downarrow}(\overline{T}-\Delta^{+})-\Delta^{-}\bigr{)}-\Delta^{-}\bigr{)}+\Delta^{+}$
$\displaystyle=-\delta_{\uparrow}\bigl{(}-\delta_{\downarrow}(\overline{T}-\Delta^{+})\bigr{)}+\Delta^{+}$
(17)

which confirms that the IP channel is indeed an involution channel. ∎

We note that $\delta_{min}$ of the IP channel is usually different from
$\overline{\delta}_{min}$ of the constituent IDM channel. Indeed, 13 above
shows that $\delta_{min}$ is defined by
$\delta_{min}-\Delta^{+}=\overline{\delta}_{\uparrow}(-\delta_{min}+\Delta^{-})$,
for example, which reveals that we may (but need not) have
$\delta_{min}\neq\overline{\delta}_{min}$. In addition, the IP channel is
strictly causal only if $\Delta^{+}$, $\Delta^{-}$ satisfy certain conditions:
From 13 and 14 and the required conditions
$\delta_{\uparrow}(0)>0\Leftrightarrow\delta_{\downarrow}(0)>0$, we get

$\delta_{\uparrow}(0)=\Delta^{+}+\overline{\delta}_{\uparrow}(\Delta^{-})>0\Leftrightarrow\delta_{\downarrow}(0)=\Delta^{-}+\overline{\delta}_{\downarrow}(\Delta^{+})>0.$
(18)

At this point, the question arises whether it can be ensured that the logical
channels in Fig. 7 are strictly causal. The answer is yes, provided the
interconnected gates are _compatible_ , in the sense that the joined $PT\\!h$
block of $G_{2}$ and the $DSS$ block of $G_{1}$ are compatible w.r.t. 5. More
specifically, the pure delays $\Delta^{+}$, $\Delta^{-}$ embedded in $PT\\!h$
of $G_{2}$ should ideally match (the switching waveforms of) the $DSS$ block
in $G_{1}$: According to 1, $-\Delta^{+}$ is the time the rising input
waveform of $G_{2}$ requires to change from $V_{th}^{in*}$ to the actual
threshold voltage $V_{th}^{in}$, while $-\Delta^{-}$ denotes the same for the
falling input. Assuming $\Delta^{+}>0$ and $\Delta^{-}<0$, it can be seen from
14 that the overall delay function for falling transitions is derived by
shifting the original one to the left and downwards (cp. Fig. 4). Note that
the 2nd median is crossed at the same location since
$\overline{\delta}_{\downarrow}(\overline{\delta}_{min}+\Delta^{+})=\overline{\delta}_{min}-\Delta^{-}$,
and thus results in $\overline{\delta}_{min}=\delta_{min}>0$ (which implies
causality). The case of $\Delta^{+}<0$ and $\Delta^{-}>0$ can be argued
analogously, starting from (13).

These considerations justify the following definition:

$PT\\!h$$u_{i}$$u_{c}$$G_{1}$$u_{g}$$DSS$$V_{th}$${u_{s}}$$u_{i}$$PT\\!h$$u_{c}$$G_{2}$logical
channel$u_{g}$$DSS$$\overline{V_{th}}$${u_{s}}$Gate AGate B

Figure 7: Channel model for proofs of the CIDM. Signals in blue have data type
WST, those in green VCT.

######  Definition 10 (Compatibility of CIDM channels).

Two interconnected CIDM channels are called _compatible_ , if the logical
channel between them is strictly causal.

Consequently, a logical channel connecting $G_{1}$ and $G_{2}$ is strictly
causal if $\Delta^{+}$, $\Delta^{-}$ has been determined in accordance with 5.
If this is not observed, non-causal effects like an output pulse crossing
$V_{th}^{out}$ without the corresponding input pulse crossing $V_{th}^{in}$
could appear.

Every chain of gates properly modeled in the CIDM can be represented by a
chain of Boolean gates interconnected by causal IDM channels, with a
“dangling” $PT\\!h$ block at the very beginning and a $DSS$ block at the very
end. Whereas the latter is just an IDM channel, this is not the case for the
former. Fortunately, this does not endanger the applicability of the existing
IDM results either: As stated in property C2) of a circuit in [7, Sec. III],
the original IDM assumes 0-delay channels for connecting an output port of a
predecessor circuit $C_{1}$ with an input port of a successor circuit $C_{2}$.
In the case of using CIDM for modeling $C_{1}$ and $C_{2}$, this amounts to
combining the $DSS$ block of gate that drives the output port of $C_{1}$ with
the $PT\\!h$ block of the input of the gate in $C_{2}$ that is attached to the
input port. Note that the analogous reasoning also applies to any feedback
loop in a circuit.

On the other hand, for an “outermost” input port of a circuit, we can just
require that the connected gate must have a threshold voltage matching the
external input signal, such that
$\delta^{\uparrow}_{min}=\delta^{\downarrow}_{min}=0$ for the dangling
$PT\\!h$ component. Finally, in hierarchical simulations, where the output
ports of some circuit are connected to the input ports of some other circuits,
the situation explained in the previous paragraph reappears.

As a consequence, all the results and all the machinery developed for the
original IDM [7] could in principle be applied also to circuits modeled with
CIDM channels. Both impossibility results and possibility results, and hence
faithfulness, hold, and even the IDM digital timing simulation algorithm, as
well as the Involution Tool [8], could be used without any change. Using the
CIDM for circuit modeling is nevertheless superior to using the IDM, because
its additional degree of freedom facilitates a more accurate characterization
of the involved channels w.r.t. real circuits. We also note that it is
possible to conduct a proof for the possibility of unbounded SPF directly in
the CIDM (see LABEL:sec:possibility) as well.

##  VI Simulating Executions of Circuits

In this section, we provide Algorithm 1 for timing simulation in the CIDM.
Since our algorithm is supposed to be run in the Involution Tool [8], which
utilizes Mentor® ModelSim® (version 10.5c), our implementation had to be
adapted to its internal restrictions.

The general idea is to replace the gates from standard libraries by custom
gates represented by CIDM channels. According to Fig. 6, a custom gate $C$
consists of three main components: (i) a pure delay shifter
$P_{I}=\Delta^{+/-}$ for each input $I$ (cancellation is done automatically by
ModelSim), (ii) a Boolean function representing the embedded gate $G$, and
(iii) an IDM channel $c$. Note that the output of $G$ is in WST format, which
facilitates direct comparison of the events ($evGO$) occurring in our CIDM
simulation with the gate outputs obtained in classic simulations based on
standard libraries.

Unfortunately, the input and output of a CIDM channel, i.e., the input of
component $P_{I}$ and the output of component $c$, is of type TCT, which is
incompatible with discrete event simulations: In ModelSim signal transitions
are represented by events, which are processed in ascending order of their
scheduled time. Consequently, they cannot be scheduled in the past, which may,
however, be needed for a transition $(t_{n},x_{n},o_{n})$ with $o_{n}<0$.

Therefore, for every CIDM channel $C$ we maintain a dedicated file $F(C)$, in
which the simulation algorithm writes all the transitions
$(t_{n},x_{n},o_{n})$ generated by $C$. The event $evTI(C)$ that ModelSim
inherently assigns to the output signal of $C$ is only used as a _transition
indicator_ : For every edge $(C,I,\Gamma)$, it instantaneously triggers the
occurrence of the “duplicated” ModelSim event $evTI(C,I,\Gamma)$, which
signals to $I$ of $\Gamma$ the event that there is a new transition in the
file $F(C)$. For an input port $i$, exactly the same applies, except that the
input transitions in $F(i)$ and the transition indicator are externally
supplied.

By contrast, both the inputs and output of the gate $G$ embedded in a CIDM
channel $C$, i.e., the output of component $P_{I}$ and the input of component
$c$, are of type WST. Consequently, we can directly use the ModelSim events
$evGI(I,C)$ resp. $evGO(C)$ assigned to the output of $P_{I}$ for input $I$ of
$C$ resp. the output of $G$ of $C$ for conveying WST transitions. Still,
cancellations that would cause occurrence times $t^{\prime}<t_{now}$ must be
prohibited explicitly (see 24 in Algorithm 1).

Our simulation algorithm uses the following functions:

  * •

$(t,ev,Par)\leftarrow getNextEvent()$: Returns the event $ev$ with the
smallest scheduled time $t$ and possibly some additional parameters $Par$. If
$t^{\prime}$ denotes the time of the previous event, then $t\geq t^{\prime}$
is guaranteed to hold. The possible types of events are
$ev\in\\{evTI(\Gamma,I,C),evGI(I,C),evGO(C)\\}$, where $C$ is the channel the
event belongs to, $I$ one of its inputs, and $\Gamma$ the vertex that feeds
$I$. If multiple different events are scheduled for the same time $t$, they
occur in the order first $evTI(\Gamma,I,C)$, then $evGI(I,C)$ and finally
$evGO(C)$. If multiple instance of the same event are scheduled for the same
time $t$, then only the event that has been scheduled last actually occurs.

  * •

$sched(ev,(t,x))$: Schedules a new event $ev$ signaling the transition
$x\in\\{0,1,toggle\\}$ at time $t$; the case $x=toggle$ means $x=1-x^{\prime}$
for $x^{\prime}$ denoting the last (= previous) transition. If the current
simulation time is $t_{now}$, only $t\geq t_{now}$ is allowed.

  * •

$init(ev,(-\infty,x))$: Initializes the initial state of the event $ev$,
without scheduling it.

  * •

$value\leftarrow s(ev,t)$: Returns the value of the state function for event
$ev\in\\{evGI(I,C),evGO(C)\\}$ at time $t$.

  * •

$F(C)\leftarrow(t,x,o)$: Adds a new TCT transition $(t,x,o)$ generated by the
output of $C$ to the file $F(C)$, which buffers the TCT transitions of $C$.

  * •

$(t^{\prime},x)\leftarrow F(\Gamma)$ reads the most recently added TCT
transition $(t,x,o)$ from the file $F(\Gamma)$ and returns it as
$(t^{\prime},x)=(t+o,x)$.

  * •

$Init(\Gamma)$: For both channels and input ports, the a fixed initial value
$(-\infty,Init(\Gamma))$.

  * •

$x\leftarrow G.f(x_{1},\dots,x_{G.d})$: Applies the combinatoric function
$G.f$ (of the $G.d$-ary gate $G$ embedded in some channel $C$) to the list of
logic input values $x_{1},\dots,x_{G.d}$, and returns the result $x$.

  * •

$postprocess()$: Implements internal bookkeeping. For example, it allows to
export the TCT signals contained in our files $F(\Gamma)$ in WST format, for
direct comparison with standard simulation results.

Algorithm 1 conceptually starts at time $t=-\infty$ and first takes care of
ensuring a clean initial state. The simulation of the actual execution
commences at $t=0$, where the conceptual “reset” that froze the initial state
is released: Every channel whose initial state differs from the computation of
its embedded gate in the initial state causes a corresponding transition of
the gate output at $t=0$, which will be processed subsequently in the main
simulation loop.

1:$\triangleright$ Executed at simulation time $t=-\infty$:

2:for all channels $C$ do

3: $F(C)\leftarrow(-\infty,Init(C),0)$ $\triangleright$ init file

4: $init(evTI(C),(-\infty,0))$ $\triangleright$ init toggle indicator

5: $init(evGO(C),(-\infty,Init(C)))$ $\triangleright$ init gate output

6: for all incoming edges $(\Gamma,I,C)$ of $C$: do

7: $init(evGI(I,C),(-\infty,Init(\Gamma)))$ $\triangleright$ init gate inputs

8: end for

9:end for

10:$\triangleright$ Executed at simulation time $t=0$:

11:for all channels $C$, with $d$-ary gate $G$ and incoming edges
$(\Gamma_{1},I_{1},C),\dots,(\Gamma_{d},I_{d},C)$ do

12: $x=G.f(s(evGI(I_{1},C),0),\dots,s(evGI(I_{d},C),0))$

13: if $x\neq Init(C)$ then

14: $sched(evGO(C),(0,x))$ $\triangleright$ add reset transition

15: end if

16:end for

17:$\triangleright$ Main simulation loop:

18:$(t,ev,Par)\leftarrow getNextEvent()$

19:while $t\leq\tau$ do

20: if $ev=evTI(\Gamma,I,C)$ then$\triangleright$ $evTI$ go first

21: $(\Delta^{+},\Delta^{-},G)\leftarrow Par$

22: $(t^{\prime},x)\leftarrow F(\Gamma)$

23: $\delta_{min}\leftarrow calcDelta(G.f,x,\Delta^{+},\Delta^{-})$

24: $sched(evGI(I,C),(\max\\{t,(t^{\prime}+\delta_{min})\\},x)$

25: else if $ev=evGI(I,C)$ then$\triangleright$ $evGI$ come next

26: $(G)\leftarrow Par$

27: $x\leftarrow s(evGO(C),t)$$\triangleright$ Current gate output

28: $y\leftarrow G.f(s(evGI(I_{1},C),t),\dots,s(evGI(I_{G.d},C),t))$

29: if $x\neq y$ then

30: $sched(evGO(C),(t,y))$

31: end if

32: else if $ev=evGO(C)$ then$\triangleright$ and finally $evGO$

33:
$(x,\delta_{\uparrow}(.),\delta_{\downarrow}(.),\Delta^{+},\Delta^{-})\leftarrow
Par$

34: $(t^{\prime},x^{\prime})\leftarrow F(C)$

35: $T\leftarrow t-t^{\prime}$

36: if $x=1$ then

37: $o\leftarrow\delta_{\uparrow}(T-\Delta^{+})-\Delta^{+}$

38: else

39: $o\leftarrow\delta_{\downarrow}(T-\Delta^{-})-\Delta^{-}$

40: end if

41: $F(C)\leftarrow(t,x,o)$

42: $sched(evTI(C),(t,toggle))$ $\triangleright$ triggers
$evTI(C,I,\Gamma^{\prime})$

43: end if

44: $(t,ev,Par)\leftarrow getNextEvent()$

45:end while

46:$postprocess()$

47:

48:procedure $calcDelta$($func,x,\Delta^{+},\Delta^{-}$)

49: if $func=not$ then

50: if $x=1$ then return $\Delta^{-}$

51: else return $\Delta^{+}$

52: end if

53: else if $func=id$ then

54: if $x=1$ then return $\Delta^{+}$

55: else return $\Delta^{-}$

56: end if

57: else

58: assert($\Delta^{+}=\Delta^{-}$)

59: return $\Delta^{+}$

60: end if

61:end procedure

Algorithm 1 CIDM circuit simulation algorithm

The algorithm uses the procedure $calcDelta$ for computing the actual
$\Delta^{+}$, $\Delta^{-}$ employed in the $P_{I}$ component of a channel,
which unfortunately depend on the embedded gate $G$: For an inverter, for
example, a rising transition at the input leads to a falling transition at the
output, so $\delta^{\downarrow}_{min}$ must be used. This is unfortunately not
as easy for multi-input gates $G$, since the effect of any particular input
transition _on the output_ needs to be known in advance. This is difficult in
the case of an XOR gate, for example, as it depends on the (future) state of
the other inputs. Currently, we hence only support $\Delta^{+}=\Delta^{-}$ for
multi-input gates in our simulation algorithm.

Last but not least, we briefly mention a small but important addition to the
Involution Tool, which we have implemented recently. Without knowledge about
the delay channel, for example $\delta_{\infty}$ or
$f_{\uparrow}$/$f_{\downarrow}$, it is impossible to determine if digital
transition are too close, i.e., that pulses degrade. Note that this is not a
problem of CIDM alone, but also appears with the widely used inertial delay,
since the user is not able to tell how far away a certain pulse is from
removal (based on the digital results alone, of course). For this purpose, we
added the possibility to plot the analog trajectory at selected locations of
the circuit. In more detail, we place full-range rising and falling waveforms
such that the discretization thresholds are crossed at the predicted points in
time. The switching between between those is, according to our analog channel
model, instantaneous and thus only continuous in value. Nevertheless, the
resulting waveform provides designers with the possibility to quickly identify
critical timing issues in the circuit, which may need further investigation by
means of accurate analog simulation.

Theorem 14 below will show that Algorithm 1 indeed computes valid executions
for a circuit, provided all its logical channels (cp. Fig. 7) are strictly
causal. As argued in Section V, this is the case if all interconnected CIDM
channels are compatible (see Definition 10), which will be assumed for the
remainder of this section. Let $\delta_{min}^{C}>0$ be the smallest
$\delta_{min}$ of any logical channel in the circuit.

We start with some formal definition for the CIDM.

Signals. Since we are dealing with two data types for signals in CIDM, we need
to distinguish WST and TCT. For WST, we just re-use the original signal
definition of the IDM, namely, a list of alternating transitions represented
as tuples $(t_{n},x_{n})$, $n\geq 0$, where
$t_{n}\in\mathbb{R}\cup\\{-\infty\\}$ denotes the time when a transition
occurs, and $x_{n}\in\\{0,1\\}$ whether it is rising (1) or falling (0). More
formally, every WST signal $s=((t_{n},x_{n}))_{n\geq 0}$ must satisfy the
following properties:

  1. S1)

the initial transition is at time $t_{0}=-\infty$.

  2. S2)

the sequence $(x_{n})_{n\geq 0}$ must be alternating, i.e., $x_{n+1}=1-x_{n}$.

  3. S3)

the sequence $(t_{n})_{n\geq 0}$ must be strictly increasing and, if infinite,
grow without a bound.

To every WST signal $s$ corresponds a _state function_
$s:\mathbb{R}\cup\\{-\infty\\}\to\\{0,1\\}$, with $s(t)$ giving the value of
the most recent transition before or at $t$; it is hence constant in the half-
open interval $[t_{n},t_{n+1}]$.

For TCT, we add an offset to the tuples used in WST. A signal here is a list
of alternating transitions represented as tuples $(t_{n},x_{n},o_{n})$, $n\geq
0$, where $t_{n}\in\mathbb{R}\cup\\{-\infty\\}$ denotes the time when a
transition is _scheduled_ , and $x_{n}\in\\{0,1\\}$ whether it is rising (1)
or falling (0). The offset $o_{n}\in\mathbb{R}\cup\\{-\infty\\}$ specifies
when the transition actually _occurs_ in the signal, namely, at time
$t_{n}^{\prime}=t_{n}+o_{n}$. Formally, every TCT signal
$s=((t_{n},x_{n},o_{n}))_{n\geq 0}$ must satisfy the following properties:

  1. S1)

to S3) are the same as for WST.

  2. S4)

$o_{0}=0$ and the sequence $(t_{n}^{\prime})_{n\geq 2}$ must satisfy
$t_{n-2}^{\prime}\leq t_{n}^{\prime}$.

If $t_{n}^{\prime}\leq t_{n-1}^{\prime}$, then we say that the transition
$(x_{n},t_{n},o_{n})$ _cancels_ the transition $(x_{n-1},t_{n-1},o_{n-1})$.
Property S4) implies that only the most recent, i.e., previous, transition
could be canceled. Since all non-canceled transitions are hence alternating
and have strictly increasing occurrence times, we can define the TCT state
function accordingly: To every TCT signal $s$ corresponds a function
$s:\mathbb{R}\cup\\{-\infty\\}\to\\{0,1\\}$, with $s(t)$ giving the value of
the most recent not canceled transition occurring before or at $t$. Note that
this implies that the TCT state function $s_{tct}(t)$ at the input of a
cancellation unit $C$ and the WST state function $s_{wst}(t)$ at its output
are the same.

Circuits. Circuits are obtained by interconnecting a set of input ports and a
set of output ports, forming the external interface of a circuit, and a set of
combinational gates represented by CIDM channels. Recall from Fig. 6 that
gates are embedded within a channel here. We constrain the way components are
interconnected in a natural way by requiring that any channel input and output
port is attached to only one input port or channel output port.

Formally, a circuit is described by a directed graph where:

  1. C1)

A vertex $\Gamma$ can be either an input port, an output port, or a channel.

  2. C2)

The _edge_ $(\Gamma,I,\Gamma^{\prime})$ represents a $0$-delay connection from
the output of $\Gamma$ to a fixed input $I$ of $\Gamma^{\prime}$.

  3. C3)

Input ports have no incoming edges.

  4. C4)

Output ports have exactly one incoming edge and no outgoing one.

  5. C5)

A channel that embeds a $d$-ary gate has $d$ inputs $I_{1},\dots,I_{d}$, fed
by incoming edges, ordered by some fixed order.

  6. C6)

A channel $C$ that embeds a $d$-ary gate $G$ maps $d$ TCT input signals
$s_{I_{1}},\dots,s_{I_{d}}$ to a TCT output signal
$s_{C}=f_{C}(s_{I_{1}},\dots,s_{I_{d}})$, according to the CIDM channel
function $f_{C}(.)$ of $C$ (which also comprises the Boolean gate function
$G.f$).

Executions. An execution of circuit ${\cal C}$ is a collection of signals
$s_{\Gamma}$ for all vertices $\Gamma$ of ${\cal C}$ that respects the channel
functions and input port signals. Formally, the following properties must
hold:

  1. E1)

If $i$ is an input port, then there are no restrictions on $s_{i}$.

  2. E2)

If $o$ is an output port, then $s_{o}=s_{C}$, where $C$ is the unique channel
connected to $o$.

  3. E3)

If vertex $C$ is a channel with $d$ inputs $I_{1},\dots,I_{d}$, ordered
according to the fixed order condition C5), and channel function $f_{C}$, then
$s_{C}=f_{C}(s_{\Gamma_{1}},\dots,s_{\Gamma_{d}})$, where
$\Gamma_{1},\dots,\Gamma_{d}$ are the vertices the inputs $I_{1},\dots,I_{d}$
of $C$ are connected to via edges
$(\Gamma_{1},I_{1},C),\dotsm(\Gamma_{d},I_{d},C)$.

First, we show that all TCT signals occurring in the CIDM, namely,
$u_{i}^{I}$, $u_{p}^{I}$ (and $u_{s}$, which is, however, the same as
$u_{i}^{I^{\prime}}$ of a successor channel) in Fig. 6, also satisfy property
S4). Note that all that a pure delay shifter component
$P_{I}=(\Delta^{+},\Delta^{-})$ does is to add $\Delta^{+}$ resp. $\Delta^{-}$
to the offset component of every TCT rising resp. falling transition in
$u_{i}^{I}$ to generate $u_{p}^{I}$.

######  Lemma 11 (TCT correctness).

Consider a strictly causal IDM channel fed by a WST input signal. If its
output is interpreted as a TCT signal, it satisfies properties S1)–S4).

###### Proof.

Properties S1)–S3) are immediately inherited from S1)–S3) of the WST input
signal.

Assume that $(t_{n+1},x)$, $n\geq 1$, w.l.o.g. with $x=0$, is the first
transition in the input signal of $c$ that causes the corresponding output
$t_{n+1}^{\prime}$ to violate S4). Let $t_{n-1}^{\prime}$,
$t_{n}^{\prime}=t_{n}+\delta_{\uparrow}(t_{n}-t_{n-1}^{\prime})$ and
$t_{n+1}^{\prime}=t_{n+1}+\delta_{\downarrow}(t_{n+1}-t_{n}^{\prime})$ be the
times the corresponding output transitions occur. By our assumption,
$t_{n+1}^{\prime}<t_{n-1}^{\prime}$. Since $t_{n+1}\geq t_{n}$, we find by
using monotonicity of $\delta_{\downarrow}(.)$ and the involution property
that

$\displaystyle t_{n+1}^{\prime}$
$\displaystyle=t_{n+1}+\delta_{\downarrow}(t_{n+1}-t_{n}-\delta_{\uparrow}(t_{n}-t_{n-1}^{\prime}))$
$\displaystyle\geq
t_{n+1}+\delta_{\downarrow}(-\delta_{\uparrow}(t_{n}-t_{n-1}^{\prime}))$
$\displaystyle=t_{n+1}-t_{n}+t_{n-1}^{\prime}\geq t_{n-1}^{\prime},$

which provides the required contradiction. The proof for $x=1$ is analogous. ∎

Lemma 11 in conjunction with the strict causality established for consistent
CIDM channels in Section V reveals that we can indeed use the inherent
cancellation of out-of-order ModelSim events for implementing the cancellation
unit $C$ in 24 of Algorithm 1. Note that we must explicitly prohibit
scheduling a canceling event before $t_{now}$, however.

The following Lemma 12 shows that the gate input signals $evGI(I,C)$ and gate
output signals $evGO(C)$ as well as every $evTI(\Gamma,I,C)$ are indeed of
type WST. This result is mainly implied by be internal workings of ModelSim
and strict causality.

######  Lemma 12 (WST correctness).

Every signal $evTI(\Gamma,I,C)$, $evGI(I,C)$ and $evGO(C)$ maintained by
Algorithm 1 for a circuit comprising only consistent CIDM channels is of type
WST.

###### Proof.

Condition S1) follows from 4–7. Condition S2) follows for $evTI$ from using
the toggle mode and for $evGO$ from 29. For $evGI$, it is implied by the fact
that the signal $u_{i}^{I}$ of $C$ maintained via $F(\Gamma)$ and
$evTI(\Gamma,I,C)$ is alternating in the absence of cancellations, as it is
generated by the alternating signal $evGO$ in $\Gamma$. Since, by Lemma 11,
cancellations do not destroy this alternation for consistent CIDM channels
either, the claim follows.

As far as condition S3) is concerned, $t_{n+1}-t_{n}>0$ for $n\geq 0$ follows
from the inherent properties of ModelSim, which ensure that only the last of
several instances of the same event $ev$ scheduled for the same time $t$
actually occurs. However, we also need to prove that $t_{n}$ grows without
bound if there are infinitely many transitions in the signal. We first
consider $evGO(C)$ and assume, for a contradiction, that the limit of the
monotonically increasing sequence of occurrence times is
$\lim_{n\to\infty}t_{n}=L<\infty$.

Let $C=C_{0}$. By the pigeonhole principle, there must be an input $I$ of
$C_{0}$ which causes a subsequence of infinitely many of the transitions
$evGO(C_{0})$. Consider the channel $C_{1}$ which feeds this $I$, and consider
any $t_{n}^{0}$. This transition is caused by the, say, $k$-th transition of
$evGI(I,C_{0})$ and hence of $evTI(C_{1},I,C_{0})$, which also occur at time
$t_{n}^{0}$. Obviously, their cause is the $k$-th transition of $evGO(C_{1})$,
which occurs at time $t_{k}^{1}$. Clearly, the latter did not cancel the
$k-1$-st transition of $evTI(C_{1},I,C_{0})$, otherwise the $k$-th transition
of $evTI(C_{1},I,C_{0})$ would not have happened either. From [7, Lem. 4], it
follows that $t_{n}^{0}-t_{k}^{1}>\delta_{min}\geq\delta_{min}^{C}$, where
$\delta_{min}$ is the one of the logical channel between the gate of $C_{1}$
and the gate of $C_{0}$ (which is an IDM channel). Consequently, all the
infinitely many transitions of $evGO(C_{1})$ that cause the subsequence of
transitions of $evGO(C_{0})$ must actually occur by time $L-\delta_{min}^{C}$.

If we delete all the transitions in the signal $evGO(C_{1})$ after time
$L-\delta_{min}^{C}$, we can repeat exactly the same argument inductively.
Repeating this $i$ times, we end up with some channel $C_{i}$ with infinitely
many transitions of $evGO(C_{i})$ by time $L-i\delta_{min}^{C}$. Clearly, for
$i>L/\delta_{min}^{C}$, this is impossible, which provides the required
contradiction.

Since infinitely many transitions of either $evTI(\Gamma,I,C)$ and $evGI(I,C)$
in finite time can be traced back to infinitely many transitions in finite
time of $evGO(\Gamma)$, the above contradiction also rules out these
possibilities, which completes our proof. ∎

We get the following corollaries:

######  Lemma 13 (File consistency).

For every channel $C$, $evTI(C)=evTI(C,I,\Gamma)$ and $F(C)$ can never become
inconsistent, i.e., all successors $\Gamma$ of $C$ can read $F(C)$ when
processing $evTI(C,I,\Gamma)$ in 22 before $evTI(C)$ is toggled again.

###### Proof.

Assume that the processing of $evGO(C)$ of channel $C$, at time $t$, writes a
new transition to $F(C)$ and toggles $evTI(C)$. This causes the scheduling of
$evTI(C,I,\Gamma)$ for time $t$ for $\Gamma$. In order to overwrite $F(C)$
before $\Gamma$ could read it, a canceling transition must have been written
to $F(C)$ by time $t$. This cannot happen strictly before $t$, though, as then
both the original $evGO(C)$ and $evTI(C)$ would have been canceled. It cannot
happen at $t$ either, since this is prohibited by Lemma 13. Hence, we have
established the required contradiction. ∎

######  Theorem 14 (Correctness of simulation).

For any $0\leq\tau<\infty$, the simulation Algorithm 1 applied to a circuit
with compatible CIDM channels always terminates with a unique execution up to
time $\tau$.

###### Proof.

According to Lemma 12, the simulation time $t$ of the main simulation loop
grows without bound, unless the execution consists of finitely many events
only. By Lemma 11 and Lemma 13, the simulation algorithm correctly simulates
the behavior of CIDM channels and thus indeed generates an execution $E$ of
our circuit. To show that $E$ is unique, assume that there is another
execution $E^{\prime}$ that satisfies E1)–E3). As it must differ from $E$ in
some transition generated for some channel $C$, $E^{\prime}$ cannot adhere to
the correct channel function $f_{C}$, hence violates E3). ∎

##  VII Experiments

In this section, we validate our theoretical results by means of simulation
experiments. This requires two different setups: (i) To validate the CIDM, we
incorporated Algorithm 1 in our Involution Tool [8] and compared its
predictions to other models. (ii) To establish the mandatory prerequisite for
these experiments, namely, an accurate characterization of the delay
functions, we employed a fairly elaborate analog simulation environment.

Relying on the $15\text{\,}\mathrm{nm}$ Nangate Open Cell Library featuring
FreePDK15${}^{\text{TM}}$ FinFET models [15]
($V_{DD}=$0.8\text{\,}\mathrm{V}$$), we developed a Verilog description of our
circuits and used the Cadence® tools GenusTM and InnovusTM (version 19.11) for
optimization, placement and routing. We then extracted the parasitic networks
between gates from the final layout, which resulted in accurate SPICE models
that were simulated with Spectre® (version 19.1). These results were used both
for gate characterization and as a golden reference for our digital
simulations.

Like in [7], our main target circuit is a custom inverter chain. In order to
highlight the improved modeling accuracy of CIDM, it consists of seven
alternating high- and low-threshold inverters. They were implemented by
increasing the channel length of p- respectively nMOS transistors, which
varies the transistor threshold voltages [9, Fig. 2]. For comparison purposes,
we conducted experiments with a standard inverter chain as well.

Regarding gate characterization for IDM, we used two different approaches.
Recall from 4 that fixing a single discretization threshold pins the value of
all consistent $\delta_{min}$, $V_{th}^{in}$ and $V_{th}^{out}$ throughout the
circuit. In the variant of IDM called IDM*, we chose $V_{th}^{out*}=V_{DD}/2$
for the last inverter in the chain, and determined the actual value of its
matching $V_{th}^{in*}$ by means of analog simulations. To obtain consistent
discretization thresholds for the whole circuit, we repeated this
characterization, starting from $V_{th}^{out*}=V_{th}^{in*}$ for the next
inverter up the chain. We thereby obtained values in the range $[0.301,0.461]\
$\mathrm{V}$$, with $V_{th}^{in*}=$0.455\text{\,}\mathrm{V}$$ for the first
gate. Obviously, characterizing a circuit in this fashion is very time-
consuming, as only a single gate in a path can be processed at a time.

Figure 8: Accuracy, expressed as the normalized total deviation area of the
digital predictions, relative to SPICE for the standard inverter chain (top)
and high/low threshold inverter chain (bottom). Lower bars indicate better
results.

Moreover, forks (that is, joins) are problematic for this characterization,
since the input characterization thresholds of two of its end most certainly
do not coincide. Reversing the direction of characterization, i.e., starting
at the front and propagating towards the end, would solve this problem but
adds a similar difficulty at the inputs of multi-input gates. Needless to say,
feedback loops most probably make any such attempt impossible.

Alternatively, we also separately characterized every gate for
$V_{th}^{out*}=V_{DD}/2$ and determined the matching $V_{th}^{in*}$, which we
will refer to as IDM+. Note carefully that the discretization thresholds of
connected gate out- and inputs differ for IDM+, such that an error is
introduced at every interconnecting edge.

Since the signals are very steep near $V_{DD}/2$, the introduced error is
typically rather small. This is even more pronounced due to the fact that the
deviation of the input thresholds is usually smaller than that of the output
thresholds due to the natural amplification of a gate. Note that this was
verified by our simulations of the standard inverter chain. However, although
the misprediction is small, it is introduced for each transition at every
gate. While this might be negligible for small circuits like our chain, the
error quickly accumulates for larger devices leading to deviations even for
very broad pulses. Thus, the IDM* can be expected to deliver worse results
than pure/inertial delay while being a computationally much more expensive
approach. Indeed, for the gates used in our standard inverter chain, we
recognized a clear bias towards $V_{th}^{in*}<V_{DD}/2$ for
$V_{th}^{out*}=V_{DD}/2$. Results for these delay functions are shown in Fig.
8. Finally, characterizing gates for CIDM was simply executed for
$V_{th}^{out}=V_{th}^{in}=V_{DD}/2$.

The results for stimulating the standard inverter chain, with 2,500 normally
distributed pulses of average duration $\mu$ and standard deviation $\sigma$,
obtained by the Involution Tool for IDM*, IDM+, CIDM and the default inertial
delay model, are shown in Fig. 8 (top). The accuracy of the model predictions
are presented relative to our digitized SPICE simulations, which gets
subtracted from the trace obtained with a digital delay model. Summing up the
area (without considering the sign), we obtain a metric that can be used to
compare the similarity of two traces. Since the absolute values of the area
are inexpressive, we normalize the results and use the inertial delay model as
baseline.

For short pulses, IDM*, IDM+ and CIDM perform similarly. We conjecture that
this is a consequence of the narrow range for $V_{th}^{out*}$ and
$V_{th}^{in*}$ ($[0.39156,0.4]\ $\mathrm{V}$$), and therefore the induced
error due to non-perfect matchings in IDM+ is negligible. For broader pulses,
we observe a reduced accuracy of IDM* and IDM+, which is primarily an artifact
of the imperfect approximation of the real delay function by the ones
supported by the Involution Tool. We even observed settings, where CIDM does
not even beat the inertial delay model, which can also be traced to this
cause.

For our custom inverter chain [Fig. 8 (bottom)], CIDM outperforms, as
expected, the other models considerably, whereas IDM+ occasionally delivers
poor results, even compared to inertial delays. This is a consequence of the
non-matching threshold values and the accumulating error. IDM* achieves much
better predictions, but still falls short compared to CIDM. For broader
pulses, CIDM and the inertial delay model perform similar, since they use the
same maximum delay $\delta_{\uparrow}(\infty)$ and
$\delta_{\downarrow}(\infty)$. The degradation of IDM* is once again a result
of the imperfect delay function approximations.

Finally, analog simulations in Fig. 9 revealed that an oscillation slightly
below $V_{DD}/2$ at the input of a low-threshold inverter can still result in
full range switches at the end of the chain. For the fast IDM characterization
such traces get removed. Note that albeit the presented oscillation is visible
in IDM when characterized from back to front there are still infinitely many
possibilities that can not be detected. Even if these do not propagate further
it is important to know if the circuit has stabilized or not. The digital
simulation results are shown in Fig. 9. While IDM removes the oscillation and
thus does not indicate any transition at the output CIDM correctly predicts
the regeneration of the pulses.

Note that we also added the capability to display the analog waveform $u_{r}$
that corresponds to the digital threshold crossings to the Involution Tool.
This makes it possible for the user to investigate if the pulses are ill
shaped and thus the circuit needs improvements.

To summarize the results of our experiments, we highlight that the
characterization procedure for IDM either requires high effort (IDM*) or may
lead to modeling inaccuracies (IDM+). The CIDM clearly outperforms all other
models w.r.t. modeling accuracy for our custom inverter chain, and is also the
only model that can faithfully predict the “de-cancellation” of sub-threshold
pulses.

Figure 9: Recovering sub-threshold waveforms in an inverter chain using the
CIDM.

##  VIII Conclusions

We presented the Composable Involution Delay Model (CIDM), a generalization of
the Involution Delay Model (IDM) that retains its faithful glitch-propagation
properties. Its distinguishing properties are wider applicability,
composability, easier characterization of the delay functions, and exposure of
canceled pulse trains at interconnecting wires. The CIDM and our novel digital
timing simulation algorithm have been developed on sound theoretical
foundations, which allowed us to rigorously prove their properties. Analog and
digital simulations for inverter chains were used to confirm our theoretical
predictions. Despite this considerable step forward towards a faithful delay
model, there is still some room for improvement, in particular, for accurately
modeling the delay of multi-input gates.

## References

  * [1] S. H. Unger, “Asynchronous sequential switching circuits with unrestricted input changes,” _IEEE Transaction on Computers_ , vol. 20, no. 12, pp. 1437–1444, 1971.
  * [2] _CCS Timing Library Characterization Guidelines_ , Synopsis Inc., October 2016, version 3.4.
  * [3] _Effective Current Source Model (ECSM) Timing and Power Specification_ , Cadence Design Systems, January 2015, version 2.1.2.
  * [4] M. J. Bellido-Díaz, J. Juan-Chico, and M. Valencia, _Logic-Timing Simulation and the Degradation Delay Model_. London: Imperial College Press, 2006.
  * [5] M. Függer, T. Nowak, and U. Schmid, “Unfaithful glitch propagation in existing binary circuit models,” _IEEE Transactions on Computers_ , vol. 65, no. 3, pp. 964–978, March 2016.
  * [6] M. Függer, R. Najvirt, T. Nowak, and U. Schmid, “Towards binary circuit models that faithfully capture physical solvability,” in _Proceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition_, ser. DATE ’15, San Jose, CA, USA, 2015, pp. 1455–1460.
  * [7] M. Függer, R. Najvirt, T. Nowak, and U. Schmid, “A faithful binary circuit model,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 39, no. 10, pp. 2784–2797, 2020.
  * [8] D. Öhlinger, J. Maier, M. Függer, and U. Schmid, “The involution tool for accurate digital timing and power analysis,” _Integration_ , vol. 76, pp. 87 – 98, 2021.
  * [9] A. Asenov, “Random dopant induced threshold voltage lowering and fluctuations in sub-0.1 mu mosfet’s: A 3-d ”atomistic” simulation study,” _IEEE Transactions on Electron Devices_ , vol. 45, no. 12, pp. 2505–2513, 1998.
  * [10] T. Nikoubin _et al._ , “Simple exact algorithm for transistor sizing of low-power high-speed arithmetic circuits,” _VLSI Design_ , vol. 2010, Jan. 2010. [Online]. Available: https://doi.org/10.1155/2010/264390
  * [11] W. Ibrahim and V. Beiu, “Reliability of nand-2 cmos gates from threshold voltage variations,” in _2009 International Conference on Innovations in Information Technology (IIT)_ , 2009, pp. 135–139.
  * [12] H. Gupta and B. Ghosh, “Transistor size optimization in digital circuits using ant colony optimization for continuous domain,” _International Journal of Circuit Theory and Applications_ , vol. 42, no. 6, pp. 642–658, 2014.
  * [13] J. Segura, J. L. Rossello, J. Morra, and H. Sigg, “A variable threshold voltage inverter for cmos programmable logic circuits,” _IEEE Journal of Solid-State Circuits_ , vol. 33, no. 8, pp. 1262–1265, 1998.
  * [14] J. Maier, “Modeling the cmos inverter using hybrid systems,” E182 - Institut für Technische Informatik; Technische Universität Wien, Tech. Rep. TUW-259633, 2017.
  * [15] M. Martins _et al._ , “Open cell library in 15nm freepdk technology,” in _Proceedings of the 2015 Symposium on International Symposium on Physical Design_ , ser. ISPD ’15. New York, NY, USA: ACM, 2015, pp. 171–178.