MISO: An intermediate language to express
parallel and dependable programs
Alcides Fonseca, Raul Barbosa

arXiv:1608.06171v1 [cs.DC] 22 Aug 2016

CISUC, Department of Informatics Engineering
University of Coimbra
P-3030 290, Coimbra, Portugal
Email: {amaf, rbarbosa}@dei.uc.pt

Abstract—One way to write fast programs is to explore the
potential parallelism and take advantage of the high number
of cores available in microprocessors. This can be achieved by
manually specifying which code executes on which thread, by
using compiler parallelization hints (such as OpenMP or Cilk),
or by using a parallel programming language (such as X10,
Chapel or Æminium). Regardless of the approach, all of these
programs are compiled to an intermediate lower-level language
that is sequential, thus preventing the backend compiler from
optimizing the program and observing its parallel nature.
This paper presents MISO, an intermediate language that
expresses the parallel nature of programs and that can be
targeted by front-end compilers. The language defines ‘cells’,
which are composed by a state and a transition function from
one state to the next. This language can express both sequential
and parallel programs, and provides information for a backendcompiler to generate efficient parallel programs. Moreover, MISO
can be used to automatically add redundancy to a program, by
replicating the state or by taking advantage of different processor
cores, in order to provide fault tolerance for programs running
on unreliable hardware.

I. I NTRODUCTION
In recent years, processor architectures have evolved towards processors with multiple CPU cores, rather than increasing the operating frequency. In order to improve the performance of programs, developers have to design (or redesign)
programs to execute code in parallel. Writing parallel code
can be done through the usage of libraries, such as Pthreads,
or with special parallel programming-languages. In any of the
cases, the parallel code is translated to a sequential intermediate language. Regardless of being compiled or interpreted, the
intermediate language can be used to perform optimizations at
the lower-level code. These optimizations are unaware of the
parallel nature of the program and cannot take into account.
Intermediate languages handle a program as a list of operations, organized in blocks expected to be executed sequentially.
Parallel programs are also considered to be sequential, and
the parallel nature of a program is hidden behind system calls
for which the compiler does not know the semantics. This is
true for LLVM, B3 and Swift intermediate languages, which
are compiled, as well for virtual machine bytecode languages,
such as Java bytecode, .NET Intermediate Language, Python
bytecode and others.
Since these intermediate languages are shared between
several high-level front-end programming languages, they are

the focus of optimization. Parallelization is one type of optimization that can result in very significant speedups for large
programs. Polly [1] is a tool that performs automatic parallelization of loops at the LLVM-IR level. Universal Translation
Library [2] is another approach that takes LLVM-IR, translates
to its own representation of the parallel program and then
generates the resulting LLVM-IR. Both these approaches use
internal representations that are not intended to be a target of
compilation.
SPIRE [3] has tackled this issue by extending LLVM with
detach, attach and barrier constructs that allow asynchronous
execution. This simple extension makes LLVM able to represent parallel languages such as OpenCL, Cilk, OpenMP, X10
and Chapel, while maintaining some lower-level semantics.
Despite this effort, there are some other parallel semantics
not being represented, such as parallel for-loops and task
dependencies, among others. The limited semantics of SPIRE
prevent some optimizations that could have been done otherwise.
In this paper, we present MISO, an intermediate language
for representation of parallel programs, supporting both Single
Instruction Multiple Data (SIMD) and Multiple Instructions
Multiple Data (MIMD). MISO can be used for performing
optimization at the parallelization level, as well as for improving the dependability of programs running on unreliable
hardware.
II. A MISO P RIMER
MISO stands for Multiple-Input Single-Output, which describes the semantics of each MISO block. MISO is organized
in ‘cells’, of which there can be several instances. A cell has
two components: the state definition and the state transition
function.
Listing 1 shows the example code of a program that
progressively blends one image into another. The ImageBlend
cell is defined as having three memory slots: r, g and b, all
integers (the state). That cell also has a transition function
that performs a weighted sum of the value of each color in
the previous state, and the same color from the second image
in the previous state as well. The saved values are stored in
a new state that will be feed into the next transition. In the
bottom of the program, we can see the instantiation of several
cells, one for each pixel of the two images. The source code

for StaticImage is omitted, as it is similar to ImageBlend with
an empty transition function.

particle strikes, that must be corrected in order for programs
to produce correct results. We introduce redundancy in MISO
in order to tolerate hardware errors.
Listing 1. An example of a MISO program
In MISO, all state transitions are isolated from one another.
Since the state of one cell is only written by one state-transition
c e l l I m ag eBlen d {
function, replication of operations can be achieved through
var r : In t = 0;
the same means as parallelization. Given that each cell has
var g : In t = 0;
its own memory, the memory contents may be duplicated and
var b : In t = 0;
the state-transition function can operate on both replicas. This
replication can be applied in parallel in different CPU cores or
transition {
processors. In NUMA architectures, the state duplication can
r = . 9 9 ∗ r + . 0 1 ∗ im ag e2 ( t h i s . p o s ) . r ; be achieved even in different memories. Identifying a soft error
g = . 9 9 ∗ g + . 0 1 ∗ im ag e2 ( t h i s . p o s ) . g ; can be done by comparing the two new states. If there is a
b = . 9 9 ∗ b + . 0 1 ∗ im ag e2 ( t h i s . p o s ) . b ; mismatch, a third equal transition should be executed to decide
}
between the two possible outcomes. By identifying MISO cells
}
that are frequently erroneous, it is possible to detect permanent
failures in hardware requiring maintenance.
im ag e1 = new I m ag eBlen d ( 3 0 0 ∗ 2 0 0 )
Replication is managed by the runtime environment, and
im ag e2 = new S t a t i c I m a g e ( 3 0 0 ∗ 2 0 0 )
therefore the same MISO program may be executed with
One aspect of MISO is that loading input and output data different levels of redundancy. In some circumstances a given
can be performed by the runtime. In this case, the program piece of code may be crucial for a specific application, thereby
could load the two images from file and could output all requiring full duplication and comparison of MISO cells, while
intermediate states to screen, resulting in a video animation the same piece of code may play a secondary role in a
non-critical application and require no replication. Selective
transition from one image to another.
The state transition moves each cell from one state to the replication of key cells may also be applied by the runtime,
next. In order to achieve this safely, there can be only writes in order to balance the fault tolerance and the overhead.
to the current state, or local variables. Reads can be performed
V. C ONCLUSION
from the previous state of either the current cell or any other
This paper presented MISO, an intermediate language that
cell. This semantic restriction allows for further optimizations.
can represent programs with both task and data parallelism
implicit in its semantics. By isolating state and state transiIII. PARALLELIZATION OF MISO
One of the main challenges for automatic parallelization is tions, compiler tools can reason about the program in order to
the extraction of data-flow information, in order to understand perform optimizations in terms of parallelization. Furthermore,
what computations can influence further operations, in order to the state isolation of MISO cells allows for replication in
establish dependencies and guarantee that the parallel program different hardware processors and memories, in order to detect
has the same semantics of the sequential version. MISO de- and recover from transient hardware faults.
The MISO toolset is currently under development, and a
scribes those dependencies explicitly in the transition function.
prototype
is available at https://github.com/alcides/miso-dsl,
Cells that have dependencies can be synchronously executed,
featuring
a
sequential and parallel runtime execution system.
while cells without any direct or indirect dependency can be
The
toolset
is open source and open to improvements and
executed in parallel, removing the need for a global barrier
suggestions
from
the community.
per transition step.

Furthermore, both task and data parallelism can be described
in MISO. Task parallelism (Multiple Instructions, Multiple
Data) can be represented using different types of cell and
Data parallelism (Single Instruction, Multiple Data) can be
expressed by having several instances of the same cell. Data
parallelism in MISO can be directly translated to GPU languages, such as CUDA or OpenCL.
IV. D EPENDABILITY

OF

MISO

Integrated circuits are continually evolving toward higher
density and greater number of transistors, as well as smaller
gates and lower operating voltages. Although this trend vastly
increases the performance of microprocessors, it also increases
the rate at which soft errors occur. Soft errors are incorrect
states in the hardware, caused by transient events such as

ACKNOWLEDGMENT
The first author was supported by the Portuguese National
Foundation for Science and Technology (FCT) through a
Doctoral Grant (SFRH/BD/84448/2012).
R EFERENCES
[1] T. Grosser, H. Zheng, R. Aloor, A. Simbürger, A. Größlinger, and L.N. Pouchet, “Polly-polyhedral optimization in llvm,” in Proceedings of
the First International Workshop on Polyhedral Compilation Techniques
(IMPACT), vol. 2011, 2011.
[2] A. Y. Drozdov, S. Novikov, V. Vladislavlev, E. Kochetkov, and P. Ilin,
“Program auto parallelizer and vectorizer implemented on the basis of
the universal translation library and llvm technology,” Programming and
Computer Software, vol. 40, no. 3, pp. 128–138, 2014.
[3] D. Khaldi, P. Jouvelot, F. Irigoin, and C. Ancourt, “Spire: A methodology
for sequential to parallel intermediate representation extension,” in 17th
Workshop on Compilers for Parallel Computing (CPC 2013), 2012.

