112 lines
15 KiB
TeX
112 lines
15 KiB
TeX
|
|
\section{Source-to-Source Compiler}\label{sec:Source-to-Source-Compiler}
|
|
|
|
|
|
In our MWRE workflow environment, we employ the Insieme compiler\footnote{http://www.insieme-compiler.org} to convert a workflow specification written in IWIR into a C++ workflow program using our engine. Insieme is a research source-to-source compiler targeted at automatically optimizing parallel programs for homogeneous and heterogeneous multi-core architectures, which currently supports C, Cilk, OpenMP and OpenCL languages. Insieme uses a single high-level parallel intermediate representation (IR) called INSPIRE~\cite{jordan2013inspire} in all stages of the compilation process. INSPIRE is the best-suited compiler-based IR because it allows us to concentrate on a single language (unlike e.g. \texttt{gcc}, which uses different IR languages in different compiler stages), it includes constructs for high-level constructs like \texttt{for} loops (unlike e.g. LLVM whose IR language only consists of simple assembler-like instructions), and it additionally includes constructs directly representing parallel concepts (like e.g. \texttt{parallel for} loops). High-level constructs ease program analysis, while dedicated parallel constructs allow to precisely represent an IWIR workflow. Furthermore, INSPIRE has been designed as an extensible IR allowing to easily add new data types or program constructs.
|
|
|
|
The conversion process from an IWIR workflow specification into an equivalent MWRE workflow program consists of three phases: (1) translation of the IWIR specification into INSPIRE, (2) compiler transformations on the INSPIRE IR, and (3) conversion of the INSPIRE IR into a MWRE workflow program.
|
|
|
|
|
|
\subsection{Phase 1: IWIR translation into INSPIRE}\label{sec:Source-to-Source-Compiler-phase1}
|
|
IWIR is a block-structured, data flow-oriented workflow language with control flow constructs very similar to modern imperative programming languages like C. Therefore, IWIR workflows can also be represented by IR languages originally designed for imperative languages, for example by replacing all IWIR constructs with their corresponding INSPIRE high-level counterparts.
|
|
|
|
\lstdefinelanguage{INSPIRE}{
|
|
language=XML,
|
|
commentstyle=\color{gray}\upshape,
|
|
morestring=[b][\color{black}\itshape\mdseries]",
|
|
morestring=[s][\bfseries]{>}{<},
|
|
morecomment=[s]{<?}{?>},
|
|
stringstyle=\color{black},
|
|
identifierstyle=\color{black}\bfseries,
|
|
keywordstyle=\color{black}\bfseries, % keyword style
|
|
tagstyle=\color{black}\bfseries
|
|
}
|
|
|
|
\begin{listing}[!t]
|
|
\lstinputlisting[language=INSPIRE]{mwre/povray.inspire}
|
|
\caption{INSPIRE representation of the POV-Ray workflow.}
|
|
\label{lst:povray_inspire}
|
|
\end{listing}
|
|
|
|
Listing~\ref{lst:povray_inspire} shows the INSPIRE program representing our POV-Ray example workflow. To ease the program analysis, each activity is represented by a function that encapsulates the code implementing the activity and whose signature represents the activity input and output ports. In our example, function \texttt{fun003} (lines~\ref{povray:inspire:wfstart:start}~--~\ref{povray:inspire:wfstart:end}) represents the start of the workflow and defines the workflow input (lines~\ref{povray:inspire:wfinputs:start}~--~\ref{povray:inspire:wfinputs:end}) and output ports (line~\ref{povray:inspire:wfoutput}). The \texttt{\_iwir\_wf\_input\_} and \texttt{\_iwir\_wf\_output\_} functions are helper functions whose only purpose is to help identify the workflow input and output ports. The \texttt{fun002} function (lines~\ref{povray:inspire:toplevel:start}~--~\ref{povray:inspire:toplevel:end}) represents the \texttt{toplevel} activity corresponding to the IWIR snippet between lines~\ref{povray:iwir:toplevel:start}~--~\ref{povray:iwir:toplevel:end} in Listing~\ref{lst:povray_iwir}. The \texttt{fun001} (lines~\ref{povray:inspire:pfor:start}~--~\ref{povray:inspire:pfor:end}) and \texttt{fun000} (lines~\ref{povray:inspire:pfor_lambda:start}~--~\ref{povray:inspire:pfor_lambda:end}) functions represent the \texttt{parallel for} \texttt{ParallelFor} activity corresponding to the IWIR snippet between lines~\ref{povray:iwir:pfor:start}~--~\ref{povray:iwir:pfor:end} in Listing~\ref{lst:povray_iwir}. The \texttt{fun001} function defines the parallel loop itself and the activity ports, while the \texttt{fun000} function represents the loop body. Finally, line~\ref{povray:inspire:programroot} represents the root of the workflow program. The \texttt{\_iwir\_input\_wrapper\_} and \texttt{\_iwir\_output\_wrapper\_} functions in each function call are helper functions used to determine the function arguments representing the input and the output ports. Atomic activities are represented by a call to the \texttt{\_iwir\_atomic\_} function, the first parameter being the name of the atomic activity type, the second parameter being the atomic activity type, and the rest of the parameters representing the input and output ports and their names.
|
|
|
|
Imperative languages, including INSPIRE, use variables and operations upon variables to describe the data flow. Data flow-driven programs like IWIR can easily be converted into an imperative program by representing every data dependency as a variable using a \emph{single static assignment}, meaning that every variable is written only once, which ensures that we can easily analyse the data flow to recreate the data dependencies. The only exceptions are loop ports that can be written more than once, however, they can only be written once per loop iteration, which makes them still easy to analyse. IWIR also does not allow any data manipulations outside of atomic activities, therefore, an INSPIRE program representing an IWIR workflow is only allowed to transport data from one activity to another, but not to manipulate this data.
|
|
|
|
|
|
\subsection{Phase 2: INSPIRE compiler transformations}\label{sec:Source-to-Source-Compiler:phase2}
|
|
|
|
Compiler transformations are usually applied to a program in order to optimize one or more program characteristics, such as execution time or program size. They can also be applied to an INSPIRE representation of a workflow application. However, compiler transformations for MWRE workflows have different optimizations goals and constraints. Traditional compiler transformations are mostly targeted towards exploiting hardware characteristics and loop optimisation, their only constraint being program correctness. In contrast, MWRE workflows only contain an abstract specification of the workflow structure translated into a WEP by the workflow engine that executes the workflow by traversing it. Furthermore, IWIR and consequently MWRE do not allow any data manipulation outside of atomic activities that are treated as blackboxes and may have more than one implementation. This excludes most traditional compiler transformations which require data manipulations or operate on low-level program constructs or on individual instructions.
|
|
However, compiler transformations having other optimization goals can be applied to workflows, as described in the following:
|
|
|
|
\begin{itemize}
|
|
\item \emph{Reduce the number of executed atomic activities}, where the most effort is spent when executing a workflow. Therefore, this transformation category is the most likely to achieve good results. When applying traditional compiler transformations, atomic activities should be treated as single instructions.
|
|
|
|
\item \emph{Reduce the engine overhead} by reducing the number of composite activities and/or transforming the workflow structure. Since the time spent in the workflow engine is usually a fraction of the total workflow execution there is only limited benefits from such transformations with respect to the execution time. However, optimizations falling into this category may help with the next optimization goal.
|
|
|
|
\item \emph{Improve and/or facilitate scheduling} by modifying the workflow structure so that the scheduler can find better mappings leading to faster execution plans.
|
|
\end{itemize}
|
|
|
|
A compiler transformation is legal when the resulting program is semantically equivalent to the original program, which means that the transformed program produces the same results as the original program. When applying compiler transformation to a workflow program, we may change the order of atomic activities, or eliminate an individual atomic activity. This poses a problem because, according to the workflow paradigm, atomic activities are regarded as black-boxes without any knowledge of its internals. There could be a hidden state governing the execution of atomic activities, and by applying compiler transformations we could accidentally alter it in a way that causes the transformed program to produce false results.
|
|
|
|
To solve this problem, we need to relax the black-box principle and provide (limited) information on what happens inside an activity. To achieve this, we use a tag systems which allows attaching tags to activities. For example, we use a \emph{side-effect freeness} tag (the term comes from functional programming indicating functions that always produce the same output for the same input) to indicate that the tagged activities do not have a global state influencing their execution of an atomic activity. The tags are stored inside the activity repository as part of the activity description. All tags added to an activity also need to be valid for all implementations of that activity. Before a workflow transformation is applied, the source-to-source compiler checks the tags of the affected activities to determine whether the transformation can be safely applied.
|
|
|
|
There are traditional compiler transformations that fall into one of the categories mentioned above, and can be theoretically applied to workflow programs. But there are practical implications that hinder the application of traditional transformations without tailoring them specifially to workflow programs first. To demonstrate the problem let us try to apply an existing compiler transformation to our POV-Ray workflow example. The first step is to analyse the workflow program to identify optimization possibilities. In our example a data-flow analysis would reveal that the input value of the \texttt{SceneFile} atomic activity are loop invariant, and therefore we can move this activity out of the loop and place it right before it using a traditional compiler transformation called \emph{loop-invariant code hoisting}, and thus improve performance by having the affected activities executed only once instead of every loop iteration.
|
|
|
|
However, when applying the loop-invariant code hoisting transformation of a traditional compiler, the \texttt{SceneFile} activity would be placed before the \texttt{parallel for} loop (between lines~\ref{povray:inspire:pfor:start} and~\ref{povray:inspire:pfor:loopstart} in Listing~\ref{lst:povray_inspire}). This would break the rule that every composite activity needs to be encapsulated in its own function, which violates the INSPIRE workflow structure outlined in Section~\ref{sec:Source-to-Source-Compiler-phase1} that can no longer be translated into a MWRE workflow program in the next step. Instead, a workflow-aware version of the loop-invariant code hoisting transformation needs to place the \texttt{SceneFile} activity inside the function representing the \texttt{toplevel} activity (line~\ref{povray:inspire:toplevel:start} in Listing~\ref{lst:povray_inspire}).
|
|
|
|
|
|
|
|
\subsection{Phase 3: MWRE workflow generation}
|
|
|
|
The last phase deals with the conversion the (optimized) INSPIRE program into a MWRE workflow program. It consists of three sub-phases: In the first sub-phase, we generate C data structures (i.e. \texttt{struct}s) representing the input and output ports of each activity. In the second sub-phase, we replace the functions representing the individual activities and the contained INSPIRE constructs with equivalent MWRE constructs and construct tables representing the complete workflow structure. Finally in the third sub-phase, we analyse the variables and their data-flow to reconstruct the original data-flow and generate the callback functions implementing said data-flow.
|
|
|
|
\begin{listing}[!t]
|
|
\scriptsize
|
|
\begin{algorithmic}[1]
|
|
\StructStart[toplevel\_input] \label{alg:povray_structs:toplevel_input:start}
|
|
\State string string;
|
|
\State int totalFrames;
|
|
\State int framesPerActivity;
|
|
\StructEnd \label{alg:povray_structs:toplevel_input:end}
|
|
|
|
\StructStart[toplevel\_output] \label{alg:povray_structs:toplevel_output:start}
|
|
\State string finalMovie;
|
|
\StructEnd \label{alg:povray_structs:toplevel_output:end}
|
|
|
|
\StructStart[SceneFile\_input]
|
|
\State string scene;
|
|
\StructEnd
|
|
|
|
\StructStart[SceneFile\_output]
|
|
\State string povFile;
|
|
\StructEnd
|
|
|
|
\StructStart[PForLoop\_input]
|
|
\State string povFile;
|
|
\State int totalFrames;
|
|
\State int numFrames;
|
|
\State string scene;
|
|
\StructEnd
|
|
|
|
\StructStart[PForLoop\_output]
|
|
\State collection frames;
|
|
\StructEnd
|
|
|
|
\StructStart[RenderTask\_input]
|
|
\State string povFile;
|
|
\State int startFrame;
|
|
\State int numFrames;
|
|
\StructEnd
|
|
|
|
\StructStart[RenderTask\_output]
|
|
\State collection frames;
|
|
\StructEnd
|
|
\end{algorithmic}
|
|
\caption{Data structures representing the ports of a POV-Ray workflow
|
|
(we omitted the boolean \texttt{``valid data''} flag for each structure component and the structures
|
|
for the \texttt{Convert} activity for brevity reasons).}
|
|
\label{alg:povray_structs}
|
|
\end{listing}
|
|
|
|
We again use our example POV-Ray workflow to describe the translation process. First, we traverse the entire INSPIRE workflow program and look at the signatures of the functions and function-calls representing the workflow activities to learn about their input- and output-ports. Using that information we generate the structures (\texttt{struct}s) representing the ports of each activity (see Listing~\ref{alg:povray_structs}). Afterwards, we again traverse the INSPIRE workflow program, only this time we create the tables representing the workflow structure (see Listing~\ref{alg:povray_structure}). The INSPIRE program structure outlined in Section~\ref{sec:Source-to-Source-Compiler-phase1} allows us to identify the individual workflow activities in the INSPIRE workflow program, and for each identified activity we create a row in our activity table (Lines~\ref{alg:povray_structure:activities:start}~--~\ref{alg:povray_structure:activities:end} in Listing~\ref{alg:povray_structure}). For each encountered atomic activity we consult the activity implementation repository to retrieve all available implementations and construct a table representing these implementations (e.g. Lines~\ref{alg:povray_structure:SceneFileImpls:start}~--~\ref{alg:povray_structure:SceneFileImpls:end} in Listing~\ref{alg:povray_structure} lists the available implementations for the \texttt{SceneFile} activity). Also we generate the callback function implementing the semantics of composite activities like e.g. the callback function that evaluates the loop counter of our \texttt{parallel for} loop. Finally, we analyse the variables of the INSPIRE program and their data-flow to reconstruct the original data-flows and generate the callback functions implementing the found data-flow (see Listing~\ref{alg:povray_callbacks}).
|