\chapter{Jitter Analysis}
\label{chapter:jitter}

\textbf{The basis of this chapter was previously published in the 2013 IEEE International
Instrumentation and Measurement Technology Conference in a paper entitled Massively
Parallel Jitter Measurement from Deep Memory Digital Waveforms\cite{loken2013massively}.}

\vspace*{0.25in}

The goal of this chapter is to explore the benefits of using the Thrust
framework provided by Nvidia. The application presented compared the performance
of an implementation of the purposed method for both CPU and GPU. The CPU
implementation used the Standard Template Library(STL), this allowed the GPU
implementation to be very similar to the CPU implementation due to the parity
of the STL and Thrust.

This chapter first will delve into the background required for Digital Signal
Processing (DSP) and will more deeply explore Thrust. From there, a brief overview of
the purposed method will be discussed. After that the implementation of the
method and then the results will be discussed.

\section{Background}

As previously discussed, GPUs are highly capable at accelerating applications
which deal with problems that inherently data parallel. This is due to the
extremely specialized nature of the hardware. Another example of a problem
domain that is largely data parallel is Digital Signal Processing. Due to this,
DSP has been an attractive target for acceleration on the GPU
\cite{barford2012parallelizing,khambadkar2012massively}. The specific DSP problem explored in this
chapter is the measurement of jitter present in a given digital signal.

\subsection{Jitter}

The jitter present in a signal can be major factor considered when designing a
serial digital communications channel. As the bit error rate (BER) drops, the
allowable amount of jitter also drops. Because of the importance of some of
these channels, there is a need to accurately measure jitter. This relationship
between the BER and jitter means that it becomes more valuable to gather a
longer section of the waveform, a ``Deep Waveform''. This larger sample of the
waveform increases the probability that some rare event affecting the signal is
detected, as well as increasing the statistical significance of the tails of the
measured jitter histogram or fitted probability distribution used to extrapolate
jitter performance and BER\cite{jitterExtrap}. Jitter histograms and eye diagrams
like the one seen in Figure~\ref{fig:eye_dia} are used to not only predict the
BER, but can also provide insight into the source of the jitter in the signal.
The desire to obtain a deep waveform of a given signal is met by modern
oscilloscopes. However the computing a jitter histogram, preparing graphical
representations of signal properties and clock recovery become computationally
expensive as the size of the waveform increases. This makes both the clock
recovery and the measure of jitter for a signal an attractive target for
acceleration.

\begin{figure}
    \centering
    \includegraphics[height=\textheight,width=\textwidth,keepaspectratio]{figures/jitter/eyediagram.jpg}
    \caption{An example of a typical eye diagram with inserted jitter\cite{agilentEyediagram}}
    \label{fig:eye_dia}
\end{figure}

\subsection{Technologies Used}

\subsubsection{Standard Template Library}

The Standard Template Library (STL) is a C++ library since its release has
heavily influenced the design of the C++ Standard Library. Any reasonably current
compiler will ship with a version of the STL. The STL is broken into 4 major
categories: containers, algorithms, iterators and function objects (functors)\cite{sgiSTL}.
Each part of the STL is designed to generically work with not only the rest of
the STL but also the primitive types and constructs provided by C++. Due to this
flexibility, the use of the STL is widespread and many compilers have specially
optimized the code generation to maximize the effectiveness of the STL.

The most notable parts of the STL are the algorithms and containers. The STL
provides many common algorithms, such as a fast sort, reverse and unique. In addition,
it provides generic containers using templates for these algorithms to work on.

\subsubsection{Thrust}

As previous stated in Chapter~\ref{chapter:background}, Thrust is a framework
built upon CUDA modeled heavily after the STL\cite{nvidia2014thrust}. 
Thrust provides a much higher level of expressiveness than CUDA by providing
more abstractions from the underlying hardware. One of the most immediately
notable things abstracted away from the application programmer's control is
memory management. Thrust provides two templated containers: host\_vector and
device\_vector. These two containers are both arrays which automatically grow
when their capacity runs out. Data can be easily copied from a host\_vector to a
device\_vector using the C++ assignment operator =. Additionally, the vectors can
be used interchangeably with the rest of the the libraries provided by Thrust
and the freedom from manual memory manage allows for a more rapid pace of 
development when combined with the provided algorithms.

\section{Overview}

The goal of this application was to present a method for fixed frequency clock
recovery and jitter measurement of a two-state digital signal using massive 
parallel processors and large data sets. To accomplish, this a CPU implementation
was first done using C++ to establish that the method would produce sufficiently
accurate results. Once the correctness of the algorithms used was established,
a version which ran on the GPU was written using Thrust. The next section
discusses in depth the method used.

\section{Implementation}

The purposed method makes some assumptions about the input signal.
Other than the  assumption that the signal is digital, the most 
important of which is that transitions will occur in the signal.
Due to this, transmission protocols like 8b/10b\cite{widmer1983dc}
should be used so that transitions can be guaranteed to happen.

The purposed method is a series of transformations and reductions of
the input signal. The first and most important transformation 
preformed finding each of the
transitions in the input signal with sub-sample accuracy. This initial
transformation forms the basis of the method. This is accomplished by
first determining relative values for the high, low and middle
voltages of the input signal. Using these values, the transition points
in the signal can be found. Once the transition points are found, a
rough estimate of the number of samples per unit interval is
made. Once the rough estimate of the duration of a unit interval is
made it is further refined. This refinement is done by comparing the
number of samples to the estimated total number of unit intervals in
the input signal. With this refined estimate, a phase offset estimate
can be calculated for each of the transition points in the input
signal. Using linear regression, the phase offset and a correction for
our final estimate can be calculated. From this further analysis tools
like jitter histograms or eye diagrams can be constructed. 


While the proposed method is straight forward in its design, there are
considerations that were made to translate the algorithm to work
efficiently on the GPU. The most major change is that while the STL
provides a primitive for selecting the nth element of a container,
Thrust provides no matching call. For the CPU implementation the
nth\_element was used to obtain percentile data without the overhead
of constructing sorted data or histograms. However since this
functionality is missing from Thrust, it was necessary to sort the data each
time a percentile was needed. This is not an issue since
Thrust provides a very fast sort \cite{thrustsort}. However, the sort
destroys its input data, so it was important to maintain proper copies
of data which was to be sorted. Another concern when working on the
GPU is minimizing the total time spent transferring data over the PCI
bus to the card. Care was also taken to reduce all data transfers to
the bare minimum, especially in the case of the large data sets used.


A more in-depth explanation of the process follows.

\textbf{Step One: Determine relative high, low and middle voltage levels in the signal.}
The first step is determining  what the values for high and low will be
based on the input signal. This done by finding the 1st
percentile of the voltages in order to find the value for low and finding the
99th percentile for the high value. From these values, a middle value
can be calculated by finding the midpoint of the two values.


\textbf{Step Two: Find transition points in the signal with in sub-sample accuracy.}
The second step is finding all the points of voltage transition in
the signal. When a transition is found, its position is noted. For each
of these transition points, a linear interpolation step is done to find
the sub-sample transition time. These values are then summed to find
each transition point in the signal with sub-sample accuracy.


\textbf{Step Three: Make a rough estimate of the number of samples in the signal per unit interval.}
From these transition times, a histogram of the inter-transition
intervals is made. To make this histogram ,the inter-transition values
are found by finding the adjacent difference of the sub-sample
transition times. Using these inter-transition values, a histogram is
made. The rough estimate of the samples per unit interval is obtained
by finding the 25th percentile of these inter-transition times. Using
the 25th percentile of these inter-transition times is only valid due
to the nature of the signal.


\textbf{Step Four: Refine the rough estimate of samples per unit interval.}
The rough estimate from the last step will not be accurate enough
for further use. Due to this, the rough estimate of samples per unit
interval is refined. To do this the first thing needed is the number
of estimated unit intervals in the signal. Following that, the total
number of samples which occur from the first transition to the last
transition in the signal is calculated. That number of samples is then divided by
the estimated number of unit intervals in the signal. 


\textbf{Step Five: Eliminate remaining linear trend in time interval error.}
In this step, the estimate will be corrected a final time using linear
regression. Figure~\ref{preLinear} shows an example of the linear trend being
corrected. In addition to giving the final estimate of the samples
per clock, this linear regression step also gives the phase correction
needed for clock recovery. To correct the refined estimate, a linear
regression of estimated time interval error, given the period estimate
obtained in step 4 and the sub-sample transition times from step two is performed.
From the linear least squares fitting, a coefficient and an offset are
obtained.  The coefficient is used to correct our refined period
estimate from the last step, and the offset is the phase offset.
Figure~\ref{postLinear} shows the result of this step.

\begin{figure}
    \centering
    \includegraphics[height=\textheight,width=0.5\textwidth,keepaspectratio]{figures/jitter/errors-to-be-linear-fitted.png}
    \caption{The estimated time interval error before correction}
    \label{preLinear}
\end{figure}


\begin{figure}
    \centering
    \includegraphics[height=\textheight,width=0.5\textwidth,keepaspectratio]{figures/jitter/R-time-vs-TIE.png}
    \caption{An example of the final time interval error produced}
    \label{postLinear}
\end{figure}


\textbf{Step Six: Construct appropriate plots}
Once the phase offset is calculated and the estimate of the unit
interval has been corrected, the appropriate plots are constructed.

\section{Results}

%describe the machine
The proposed algorithm was implemented two times. One implementation
used only the CPU and was written in C++ using the primitives provided
by the STL to verify the results of the purposed method. The other
implementation written in C++ using Thrust to run code on an NVIDIA
GPU was used to measure the total speed up of the method with
increased core counts. Both implementations were tested with an actual
measured waveform obtained using the apparatus shown in
Figure~\ref{apparatus}, in which waveforms were produced by an Agilent
8133A Pulse Generator and captured by a Agilent DSA91304A Digital
Signal Analyzer.

\begin{figure}
\centering
\includegraphics[height=\textheight,width=\textwidth,keepaspectratio]{figures/jitter/apparatus.pdf}
\caption{Measurement apparatus used to verify the proposed method}
\label{apparatus}
\end{figure}

The experimental platform is an Intel Core2 Quad core CPU Q9450 at
2.66GHz with 8 GB of memory. The GPU used was an NVidia GeForce GTX
480 which contains 15 groupings of 32 compute cores for a total of 480
compute cores and has 1.5 GB of on board memory. The CPU
implementation was compiled with g++ version 4.6.3, but due to the
restrictions of Thrust the GPU implementation was compiled with the
CUDA toolkit version 5.0 and g++ version 4.4.7. All implementations
were compiled on 64 bit Ubuntu 12.04 with optimization level -O3.


The measurement results obtained by the serial and GPU versions were
identical. For example, when all 16 million samples are used, both
versions yield the standard deviation of TIE of 4.630199 samples. The
resulting plots of the time interval errors (TIEs) for each transition
and the jitter (probability density of the TIE) are shown in
Figures~\ref{postLinear}, ~\ref{TIE_probability_density} and
~\ref{TIE_histo}. (The probability density is a kernel density
estimate~\cite{silverman1986density} computed from the TIEs.)


\begin{figure}
\centering
\includegraphics[height=\textheight,width=0.5\textwidth,keepaspectratio]{figures/jitter/TIE-density.png}
\caption{The TIE probability density for a sample waveform}
\label{TIE_probability_density}
\end{figure}

\begin{figure}
\centering
\includegraphics[height=\textheight,width=0.5\textwidth,keepaspectratio]{figures/jitter/TIE-histogram.png}
\caption{The TIE histogram for a sample waveform}
\label{TIE_histo}
\end{figure}

There were three timings measured: one timing for the CPU,
one timing for the GPU which did not include the data transfer times (DTT)
and a one timing for the GPU which included the transfer times as
well. Table~\ref{cpuvgputimes} and figure~\ref{exeTime} show the 
results for these timings as the size of the input signal was 
increased, while Table~\ref{cpuvgputhroughput} and figure~\ref{throughPut}
shows the throughput of these results. For signals less than
16,000,000, samples in length sections of the input waveform were
used. The waveforms used in these timing experiments were
pseudo-random binary signals (PRBSs).


\begin{table}
\caption{Execution time in milliseconds for each implementation for each of the different input signal lengths. DTT = data transfer time.}
\label{cpuvgputimes}
\centering
\begin{tabular}{|c||c|c|c|}
\hline
Input Size (samples) & CPU & GPU (no DTT) & GPU (with DTT)\\
\hline
\hline
1,000,000 & 15.19 & 7.17 & 9.89\\
\hline
1,414,213 & 22.38 & 7.43 & 10.96\\
\hline
2,000,000 & 28.59 & 8.61 & 13.21\\
\hline
2,828,427 & 43.44 & 10.11 & 16.36\\
\hline
4,000,000 & 62.24 & 12.33 & 20.88\\
\hline
5,656,854 & 89.56 & 16.26 & 28.15\\
\hline
8,000,000 & 144.44 & 20.84 & 37.38\\
\hline
11,313,708 & 242.54 & 28.37 & 51.66\\
\hline
16,000,000 & 309.37 & 38.23 & 70.88\\
\hline
\end{tabular}
\end{table}


\begin{table}
\caption{Throughput for each implementation for each of the different input signal lengths. DTT = data transfer time, input size in samples}
\label{cpuvgputhroughput}
\centering
\begin{tabular}{|c||c|c|c|}
\hline
Input Size & CPU (MSa/s) & GPU (MSa/s, no DTT) & GPU (MSa/s, with DTT)\\
\hline
\hline
1,000,000 & 65.835 & 139.460 & 101.122\\
\hline
1,414,213 & 63.180 & 190.330 & 129.046\\
\hline
2,000,000 & 69.946 & 232.297 & 151.401\\
\hline
2,828,427 & 65.108 & 279.701 & 172.917\\
\hline
4,000,000 & 64.269 & 324.492 & 191.561\\
\hline
5,656,854 & 63.163 & 347.852 & 200.963\\
\hline
8,000,000 & 55.385 & 383.880 & 214.013\\
\hline
11,313,708 & 46.646 & 398.743 & 219.002\\
\hline
16,000,000 & 51.717 & 418.563 & 225.740\\
\hline
\end{tabular}
\end{table}

\begin{figure}
    \centering
    \includegraphics[height=\textheight,width=0.5\textwidth,keepaspectratio]{figures/jitter/Rplot11.png}
    \label{exeTime}
    \caption{The execution time of the purposed method in seconds.}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[height=\textheight,width=0.5\textwidth,keepaspectratio]{figures/jitter/Rplot01.png}
    \label{throughPut}
    \caption{The computational throughput of the purposed method measured in samples per second.}
\end{figure}

%Discuss the timings
Table~\ref{cpuvgputimes} and Figure~\ref{exeTime} show that when
considering only the computations, the difference between the serial
CPU implementation and the parallel implementation on the GPU as the
input size grows is sizable. While the CPU implementation was not
expected to keep pace with the GPU implementation, it is interesting
to note the significant speed up that is present. Another
interesting thing to note is that for even with signals as small as
1,000,000 elements, when the data transfer time is considered the
GPU implementation is able to handily beat the CPU. This result means
that it is quite practical to use this method over a pure CPU
implementation. Table~\ref{cpuvgputhroughput} and Figure~\ref{throughPut}
show the massive difference in throughput that the GPU is able to
provide over the CPU. For the entire 16 million sample signal, the GPU
implementation was able to handle 8 times as many samples as the CPU
in the same amount of time when not considering the total transfer
time of data on and off of the GPU. This is a reasonable expectation to
make as the method presented is likely to be an intermediate step in a
larger process.

%Discuss throughput versus PCI bus throughput and how the method does not
%match the speed of the PCI and can therefore be seen as a bottleneck
An interesting thing to note is that despite the relatively high
throughput shown by the GPU in Table~\ref{cpuvgputhroughput} and 
Figure~\ref{throughPut}, the application is still computationally bound.
While the method as implemented is capable of consuming 418 million 
samples a second the PCI express bus is capable of transmitting
more samples\cite{pciespeed}.

\subsection{Summary of Contributions and Future Work}

There are two novel contributions of the method purposed in this chapter: (1)
the application of massively parallel processors to do clock recovery and to
quantify jitter and (2) the use of sorting to replace building histograms when
analyzing waveforms in order to more efficiently use such processors. By using the
efficient sorting, transformation and reduction routines provided by Thrust,
the benefits of constructing a solution using the primitives offered by Thrust
were shown. Identical measurement results were obtained, so using parallel
processing did not affect the measurement uncertainty. A feature very important
when considering changing the method of a measurement.

The application discussed in this chapter, however, is not without flaws.
In order to further increase the robustness of this solution a more
complete handling of identifying voltage reference levels (high, medium 
and low) and location of state transition times is needed. Significant progress
toward achieving the second of these on GPUs has been reported
elsewhere~\cite{barford2012parallelizing,khambadkar2012massively},
and it should be possible to combine those methods with the one presented in this
chapter. The handling of these two tasks in the current application is possibly
sensitive to noise, glitches and runt pulses. Any sensitivity to this phenomena, however,
did not present itself during testing. 

In addition to become more compliant with the IEEE Standard 181-2011
\cite{ieeestd181}, we plan on experimenting with ways to build a proper histogram 
on the GPU more efficiently. The current implementation does not need histograms 
but to become IEEE Standard 181 compliant. A future implementation will require an
efficient method for building histograms on the GPU. 

Finally, the presented method is also unable to deal with non-constant
clocks. In order to add functionality to recover these non-constant clocks
a phase locked loop would be required.

