ll.html

<!--

    Copyright (c) 2021, 2024 Contributors to the Eclipse Foundation

    This program and the accompanying materials are made
    available under the terms of the Eclipse Public License 2.0
    which is available at https://www.eclipse.org/legal/epl-2.0/

    SPDX-License-Identifier: EPL-2.0

-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 5.0 Transitional//EN">

<html>
<head>
    <link rel="stylesheet" type="text/css" href="../css/style.css" />
    <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
    <title>TRACE - Little's-law-based analysis</title>
</head>
<div>
<h1>TRACE Little's-law-based analysis</h1>

<p>
<b>NOTE: Analysis is applied to the current filtered view</b>
</p>

<p>
Little's law (see, e.g., <a href="https://en.wikipedia.org/wiki/Little%27s_law">here</a>)
stems from queueing theory and relates throughput, latency and work in progress (wip).
The TRACE tool supports the creation of continuous signals for these three properties from
the discrete claims and or events in the trace.
The resulting signal is added to the view, and can be removed by the "clear filters or
extensions" menu (<img src="../../icons/delete.png" />).
The Little's-law menu (<img src="../../icons/change_obj.png" />) has four items, explained below.

<h2>Event-based throughput</h2>
This analysis computes the continuous throughput signal based on events. It has four parameters:
<ul>
<li>
    <i>Window width (in seconds)</i>: this parameter determines the width of the sliding window
    that is used to convolute the <i>instantaneous throughput</i> signal. For a window width of
    <i>t</i>, the resulting signal gives the average over the last <i>t</i> time units.
    If <i>t=0</i> then the resulting signal is the instantaneous throughput. 
</li>
<li>
    <i>Value scale</i>: this parameter, a time unit, determines the scale of the signal range.
</li>
<li>
    <i>Event type</i>: this parameter is the first part of the event filter and determines which
    event types (start event of a claim, end event of a claim, or any event) to use for the
    throughput computation.   
</li>
<li>
    <i>Attribute filter</i>: this parameter is the second part of the event filter and determines
    which events to include for the throughput computation.   
</li>
</ul>

<p>
Figure 1 shows an event-based throughput signal for the <a href="example.html">running example</a>.
The window width is set to 0.1 seconds, the value scale is seconds (i.e., the throughput per second
is computed), and the event filter is set to end events with name E (start and end events of claims
have the same attributes as the parent claim).
The throughput, a continuous signal, is added to the trace in a separate section (here at the bottom).
The range of the signal gives the number of objects that are processed per second.
Note that we do not use task G because it can be preempted, resulting in multiple end events per
data object that is processed.
</p>
<figure>
<a target="_blank" href="../img/ll-1.png"><img src="../img/ll-1.png" class="open600" /> </a>
<figcaption>Figure 1: Event-based throughput.</figcaption>
</figure>

<h2>Identifier-based throughput</h2>
<p>
The identifier-based throughput analysis also has the window and value scale parameters.
Instead of specifying a filter to include events for the throughput computation, a
<i>grouping attribute</i>
is used. All claims and events with the same value for that attribute are grouped
and the analysis assumes that these all are involved by the processing of a single object.
The earliest and latest time stamps in the group of claims and events are used to construct
the throughput signal. It therefore usually gives a smoother graph than the event-based
throughput.
In the <a href="example.html">running example</a> we can use the "id" attribute for grouping; see Figure 2.
Here we have computed the identifier-based throughput in seconds with a sliding window of 0.1 s.
It is similar to the graph in Figure 1, but smoother.
</p>
<figure>
<a target="_blank" href="../img/ll-2.png"><img src="../img/ll-2.png" class="open600" /> </a>
<figcaption>Figure 2: Identifier-based throughput.</figcaption>
</figure>

<h2>Identifier-based wip</h2>
<p>
The wip analysis only needs the window width and the grouping attribute. 
It computes a signal that gives the number of objects that are being processed at the given
time. Figure 3 gives an example using the "id" attribute for grouping and with a sliding window of 0.1 s.
</p>
<figure>
<a target="_blank" href="../img/ll-3.png"><img src="../img/ll-3.png" class="open600" /> </a>
<figcaption>Figure 3: Identifier-based wip.</figcaption>
</figure>


<h2>Identifier-based latency</h2>
<p>
The latency analysis has the same parameters as the identifier-based throughput analysis.
The latency signal is computed by applying Little's law to the throughput and wip signals.
Figure 4 shows the latency signal in seconds with a
window width of 0.1 seconds and grouping by the "id" attribute.
The latency is around 30 milliseconds. Figure 2 shows that the throughput is about 120
frames/second, and Figure 3 shows that the wip approximately 3.5.
Little's law informally states that <i>wip = throughput * latency</i>, which in our case approximately means
that <i>3.5 &approx; 120 * 0.03</i> which indeed is approximatly correct.

<figure>
<a target="_blank" href="../img/ll-4.png"><img src="../img/ll-4.png" class="open600" /> </a>
<figcaption>Figure 4: Identifier-based latency.</figcaption>
</figure>
</p>

<p>
The four type of signals described above are mathematically well-defined. It is, however, out
of scope of this manual to explain those details here.
A publication is forthcoming that covers all the math <a href="references.html">[5]</a>.
</p>

</div>
</html>