Base Header Level:  3
latex input:        document-info
latex input:        x3-util
latex footer:       x3-paper-end

<!--\clearpage-->
# Introduction and Motivation

Embedded platforms and applications are being used throughout many industries, including telecommunication, robotics, medical and automotive <!--\citep{Wang2013}-->. <!--\citet{Campeanu2013}--> states that nowadays it is increasingly common to build embedded systems on heterogenous platforms, containing multiple computational units such as multi-core CPUs, GPUs and FPGAs. If all these components are used to the full extent of their capabilities, such a setup enables better performance than could be previously achieved on embedded platforms.

This is an important shift, since applications running on these platforms become more and more complex, and their performance requirements have to be satisfied. In the past, not only on embedded platforms, this was commonly achieved by boosting processor clock rates. But due to both intractable physical limitations as well as practical engineering considerations, increasing processor clock rates is no longer a feasible approach <!--\citep{Cantrill2008}-->.

The performance gains possible on heterogenous embedded platforms are a result of the hardware-level parallelism that is achievable on these platforms. But unfortunately, exploiting these parallelism features still is a considerable challenge, given the tools and programming concepts widely in use today <!--\citep{Wang2013,Cantrill2008}-->.

Because of the mentioned increase in complexity and performance requirements in embedded applications, and considering that clock rates can't be expected to increase significantly anymore, research in the area of concurrent applications has taken an important place in the computer science research community. This can be seen in <!--\autoref{fig:concurrency-publications}-->, which shows an increasing number of publications related to concurrency over the last years.

<!--\fig{concurrency-publications}{A strong increase in publications related to concurrency can be observed over the last years. These numbers were researched from the \citet{IEEEXplore2013} digital library as well as the \citet{ACMDigitalLibrary2013} digital library.}-->


In context of the <!--\citet{FAUST2013}--> at the Hamburg University of Applied Sciences, a specific embedded application in need of parallelization is an obstacle detection system in cooperation with a lane guiding control. Evaluating the distance data measured by a laser scanner and the image stream providing extracted road marking parameters constitues a dataflow parallelization problem, for which suitable algorithms must be researched and compared. Therefore, this essay focuses on the literature evaluation of techniques that allow for the exploitation of potential sources of parallelism, especially those which are suitable for dataflow problems. Said evaluation is done in context of a modern multiprocessor system-on-chip platform (MPSoC), the Xilinx Zynq 7000. The goal is to get a broad overview of the state-of-the-art techniques being used, as well as their up- and downsides, especially in resource-constrained environments. Additionally, the current lack of widely used tools and languages crafted for use in concurrent environments is addressed by giving a short overview of the "Go" programming language, and of how it might be used on embedded platforms to increase developer efficiency.

The evaluation is confined to the area of Symmetric Multiprocessor (SMP) systems, i.e. those having multiple processors or processing cores with a shared memory. Other parallelism concepts for architectures such as Distributed Memory Access or Nonuniform Memory Access will not be discussed.

<!--\todoin{Übersicht zu den einzelnen Kapiteln, sodass der rote Faden zu den Zielvorstellungen deutlich wird.}-->




# Platform and problem description

In the <!--\citet{FAUST2013}-->, the Zynq 7000 SoC manufactured by Xilinx is currently being used for embedded application development. At present, there are two major subsystems that need to run in parallel on this platform, which are part of a technology field trial of advanced driver assistance systems:

1. An obstacle detection system (<!--\autoref{obstacle-detection}-->)
1. A lane guiding control system (<!--\autoref{lane-guiding-control}-->)

The Xilinx Zynq 7000 architecture is composed of a dual-core ARM Cortex-A9 CPU as well as an on-chip programmable logic unit (FPGA). The ARM Cortex-A9 additionally contains the ARM NEON general-purpose SIMD engine, for which an overview will be given in <!--\autoref{arm-neon}--> <!--\citep{Xilinx2013}-->.



## Obstacle detection system [obstacle-detection]

This laserscanner-based obstacle detection system was realized by <!--\citet{Jestel2013}-->, providing an implementation in the Java programming language running on the Android 4 operating system. Because of the fact that the Zynq 7000 platform was not yet available when development on the system started, it is currently running on the "Open Multimedia Application Platform 4430" (OMAP4), which features similar specifications to the Zynq platform, but lacks the integration of an FPGA.

<!--\todoin{Expand a bit on laserscanner and perhaps current implementation}-->



## Lane guiding control system [lane-guiding-control]

<!--\citep{Andresen2013}-->

<!--\todoin{Base this on Andresen's MA thesis}-->




<!--\clearpage-->
# Parallel computing architectures

<!--\citet{Flynn1972}-->, in what is often referred to as "Flynn's Taxonomy", states that there are four broad categories of computer architectures:

<!--
\begin{tabular}{ll}
\textbf{SISD} & Single instruction, single data\\
\textbf{MISD} & Multiple instruction, single data\\
\textbf{SIMD} & Single instruction, multiple data\\
\textbf{MIMD} & Multiple instruction, multiple data\\
\end{tabular}
-->

SISD is what can be found in most single-core computers, where a single stream of input data is processed by a single stream of instructions. SISD is not further discussed since it has no parallel elements, and MISD is completely ommited because there are no well-known systems that fit into this category <!--\citep{Mattson2004}-->.

In this essay, the focus is on SIMD and MIMD architectures, which offer a potentially high degree of parallel execution.



## Multiple Instruction, Multiple Data

The MIMD category in Flynn's taxonmy, as depicted in <!--\autoref{fig:MIMD}-->, features multiple control-units which provide instructions to a number of processors, each with their own data input stream. Additionally, the MIMD processing units may be interconnected. This category is the most general, and applies to all multi-processor system currently available <!--\citep{Mattson2004}-->.

<!--\figw{MIMD}{Visualization of a Multiple instruction, multiple data architecture. There are three different processing units, each featuring its own control unit and processor. All processing units have disjoint instruction and input data streams. The processors may be interconnected among each other.}-->



## Single Instruction, Multiple Data

Given a single stream of instructions and multiple streams of data, an SIMD architecture is one that applies each instruction to all of the data streams **in parallel**. This process is visualized in <!--\autoref{fig:SIMD}-->, where there is a single control unit providing the processors with instructions. For every instruction, every processor takes an item out of its own input stream and applies the instruction.

As such, SIMD architectures are a good fit for specialized applications that consist of high data parallelism as well as little interprocess communication. As an example, in digital signal processing, e.g. decoding a video stream, the situation is common that the same operations need to be applied continously to a large stream of data (in case of a 1080p high-quality H.264 movie, the bitrate is usually above 17Mbit/s). As such, SIMD instruction sets have become a generic feature of most high-end processors because of the possible performance improvements that they can provide <!--\citep{Jang2011}-->.

A Graphics Processing Unit (GPU) can also be seen as a heavily parallel SIMD system. GPUs usually consist of an array of multiprocessors, each in turn consisting of multiple processing units (ALUs), which all share a single control unit (exactly as depicted in <!--\autoref{fig:SIMD}-->). Each of these ALUs is then able to execute instructions provided by the control unit, potentially providing a many-fold performance increase.

<!--\fig{SIMD}{Visualization of a Single instruction, multiple data architecture, containing three processing units. Heavily inspired by \citet{Mattson2004}}-->



<!--\newpage-->
# Parallelization Techniques

In this section, selected techniques will be explained in context of the concrete problem at hand, that is the parallelization of the obstacle detection system on an ARM Cortex-A9 CPU. Since there are a multitude of techniques, and not enough time available to evaluate all of them, the selection was mostly based on the information provided by <!--\citet{Mattson2004}-->. If available, current research based on these techniques will be highlighted.

## ARM NEON SIMD [arm-neon]

The ARM NEON extension is a general-purpose 128-bit SIMD architecture available in ARMv7. It is included in the ARM Cortex-A9 processors that can be found on the Zynq 7000 <!--\citep{Jang2011}-->.

The NEON extension is composed of 32 64-bit registers, which can alternatively be used as 16 128-bit registers. In NEON terminology, a register is a vector of elements of the same data-type (possible data-types 8-bit to 64-bit signed and unsigned integers as well as single precision floats). Every instruction given to the NEON engine is then performed on all elements of one or more such vectors. A "lane" is the part of all registers which shares the same operation. This process is visualized in <!--\autoref{fig:NEON-SIMD}-->.

<!--\fig{NEON-SIMD}{Visualization of the NEON SIMD data flow. Assuming 64-bit source registers, each of the operands is 16-bit wide. The blue squares represent the operations applied to the registers. Four operations are applied, and thus there are four lanes.}-->

<!--\todoin{Add a few standard operations, and maybe a short example}-->

Even though the NEON engine is realized as part of the ARM core, it has a completely independent execution pipeline as well as a register bank that is separate from the ARM core register bank <!--\citep{Jang2011}-->. As a result, it is possible to signal the ARM core memory system to pre-load memory (using the `PLD` instruction, see <!--\citet{ARMAssembler2013}-->) while the SIMD engine is computing, so that the data for the next SIMD operation will already be available in the cache. Since cache misses can impose a significant performance overhead <!--\citep{Zang2013}-->, pre-loading can




<!--\todoin{Overview of how the NEON engine applies SIMD techniques}-->

<!--\todoin{Point to results at \citep{AlchemyLab2013} after verifying them, since they show the possible performance increase with SIMD very well.}-->



## Pipeline Pattern



<!--\todoin{Describe Pipeline Pattern as well as applications, pros and cons}-->

<!--\todoin{Try to make a nice transition from pipeline pattern to Go, so that the reader can follow along}-->



<!--\clearpage-->
# The "Go" programming language

This section will give a short overview of the programming language "Go", as well as provide a comparison to C, since it is the most common programming language used on embedded platforms<!--\todo{citation needed}-->. To wrap up this section, an example implementation of the pipeline pattern will be presented and explained.

Go is a general-purpose programming language first released in 2009, and currently being developed as an open-source project <!--\citep{Golang2013}-->. Its main goal was to increase developer productivity, especially when working in environments featuring multicore processors, networked systems and massive computation clusters. It also aspires to be easy to learn. An additional focus when developing the language was the reduction of compile time, since some modern languages, like C++, suffer from very high compilation times for larger projects <!--\citep{DAngelo2012}-->, which in turn reduces developer efficiency.

<!--\citet{Pike2012}--> states that most of the languages widely in use today were created in environments that are, in large parts, unrelated to the current computing landscape. He is referring to the paradigm shift from sequential to concurrent applications, where it becomes necessary to reason about and implement concurrent software in order to exploit the available resources. Languages such as C/C++, Java and Python were built when the importance of multi-processor programming had not yet developed, and as such, all of the parallelism concepts that can be found in them are the result of the adjustment of the language to current requirements. As an example, the building blocks for concurrent applications that can be found in the `java.util.concurrent` package were introduced in Java version 1.5, eight years after the initial language release <!--\citep{Peierls2005}-->. As a result, writing concurrent applications in these languages can often feel like a workaround <!--\citep{Pike2012}-->.

Go was developed with concurrency as one of the main language features. The compiler inserts a small runtime environment into every compiled binary, which measures around 400KB in size on a x64 platform in Go v1.1.1. This runtime, apart from providing convenient features such as garbage collection, is able to distribute the so-called "goroutines" onto a pool of operating system threads. As a result, goroutines are much more "lightweight" than OS threads, since no interaction with the operating system is necessary to create and schedule them (other than the management of the thread pool). Creating a goroutine does not require additional work for the developer compared to calling a function, as can be seen in <!--\autoref{code:goroutine}-->.

<!--
\includego{goroutine.go}{goroutine}{Example of the sequential invocation of a function compared to the concurrent execution using a goroutine.}
-->

The communication between goroutines is realized through channels (the language keyword being `chan`), which have a capacity defining how many messages each channel can hold. Go's communication model can thus be regarded as a "message-passing" model. If any goroutine tries to insert or retrieve data from a channel, and if this channel is full or empty respectively, then the invoking goroutine will block until data becomes available. As a result, channels are also the synchronization primitive in Go.

<!--
\includego{channels.go}{gochannels}{Syntactical overview of channel usage in Go.}
-->



## Comparison to C

<!--\todoin{Syntactical/Semantical differences as well as performance comparisons, if possible. Context switch time, garbage collection impact, plain performance (e.g. loops) compared to C, all that stuff.}-->



## Example: Pipeline Pattern in Go





<!--\clearpage-->
# Summary

<!--\todoin{Komprimierte Darstellung der wesentlichen Inhalte}-->

<!--\todoin{Ausblick (wie geht es weiter?)}-->










<!--
% Bibliography
\clearpage
\begin{flushleft}
    \bibliography{bibliography}
\end{flushleft}
-->
