Automatic Parallelization using Pipelining for Equation-Based Simulation Languages Håkan Lundvall by

by user

Category: Documents





Automatic Parallelization using Pipelining for Equation-Based Simulation Languages Håkan Lundvall by
Linköping Studies in Science and Technology
Thesis No. 1381
Automatic Parallelization using Pipelining for
Equation-Based Simulation Languages
Håkan Lundvall
Submitted to Linköping Institute of Technology at Linköping University in partial
fulfilment of the requirements for the degree of Licentiate of Engineering
Department of Computer and Information Science
Linköpings universitet
SE-581 83 Linköping, Sweden
Linköping 2008
Automatic Parallelization using Pipelining for
Equation-Based Simulation Languages
Håkan Lundvall
September 2008
ISBN 978-91-7393-799-3
Thesis No. 1381
ISSN 0280-7971
During the most recent decades modern equation-based object-oriented modeling and simulation
languages, such as Modelica, have become available. This has made it easier to build complex and
more detailed models for use in simulation. To be able to simulate such large and complex
systems it is sometimes not enough to rely on the ability of a compiler to optimize the simulation
code and reduce the size of the underlying set of equations to speed up the simulation on a single
processor. Instead we must look for ways to utilize the increasing number of processing units
available in modern computers. However to gain any increased performance from a parallel
computer the simulation program must be expressed in a way that exposes the potential
parallelism to the computer. Doing this manually is not a simple task and most modelers are not
experts in parallel computing. Therefore it is very appealing to let the compiler parallelize the
simulation code automatically. This thesis investigates techniques of using automatic translation
of models in typical equation based languages, such as Modelica, into parallel simulation code that
enable high utilization of available processors in a parallel computer.
The two main ideas investigated here are the following: first, to apply parallelization
simultaneously to both the system equations and the numerical solver, and secondly. to use
software pipelining to further reduce the time processors are kept waiting for the results of other
processors. Prototype implementations of the investigated techniques have been developed as a
part of the OpenModelica open source compiler for Modelica. The prototype has been used to
evaluate the parallelization techniques by measuring the execution time of test models on a few
parallel archtectures and to compare the results to sequential code as well as to the results
achieved in earlier work. A measured speedup of 6.1 on eight processors on a shared memory
machine has been reached. It still remains to evaluate the methods for a wider range of test models
and parallel architectures.
This work has been supported by the Swedish Foundation for Strategic Research (SSF) in the ECSEL
graduate school, by Vinnova in the Safe and Secure Modeling and Simulation Project, and by the
Swedish Research Council (VR).
I have learned a great deal during these years working towards this thesis and I have
many people to thank for this. First, I would like to express my gratitude towards
my supervisor Peter Fritzson for giving me the opportunity to work on this research
and for the guidance and encouragement he has provided. I also want to thank my
co-supervisors Christoph Kessler and Dag Fritzson for their support.
Even though I live two hours drive from the colleagues at PELAB it has always
been a pleasant drive knowing that interesting discussion and good friends await
when I arrive. Many thanks to all the employees at PELAB for that. And I would
especially like to thank Bodil for all the administrative help which has made the life
easier for all the rest of us.
Those days when I have not drove all the way to Linköping, Sogeti Sverige AB
has provided a nice working atmosphere here in Örebro, as well as a computer to
work with.
My time has been divided evenly between the PhD studies and the work as a
consultant at Sogeti and I wish to thank Atlas Copco Rock Drills AB for keeping
me busy with assignments through out these years knowing that they can only get
half of my attention.
Finally I would like to thank my lovely wife Jenny and my wonderful daughters
Emma and Lina for always being there and believing in me.
Örebro, August 13, 2008
Håkan Lundvall
Table of Contents
Part 1 Introduction
Chapter 1 Background and Introduction
Modeling and Simulation
Related Work on Task Scheduling and Clustering
Research Problem
Thesis Structure
List of Papers
Chapter 2 Implementation – The OpenModelica Parallelizing Backend
Compiler Phases
Modules of the OpenModelica Compiler
Simulation Runtime
MPI-Based Runtime System
Pthreads-Based Runtime System
Additional Load Balancing and Memory Layout Ideas
Part II Papers
Paper A
Event Handling in the OpenModelica Compiler and Runtime
Conversion of a Modelica Model to a Hybrid DAE
Simulation of Hybrid Models Based on Solving Hybrid DAEs
The Form of the Hybrid DAE System
Summary of Notation
Continuous-Time Behavior
Discrete-Time Behavior
The Complete Hybrid DAE
Hybrid DAE Solution Algorithm
Varying Structure of the Active Part of the Hybrid DAE
Finding Consistent Initial Values at Start or Restart
Detecting Events during Continuous-time Simulation
Crossing Functions
Integrating the Numerical Solver with Event-Handling
Code Generation
Measurements and Evaluation
Bouncing Ball
Full Wave Rectifier
Paper B
Automatic Parallelization of Object Oriented Models Across
Method and System
Paper C
Background – Introduction to Mathematical Modeling and
The OpenModelica Open Source Implementation
Approaches to Integrate Parallelism and Mathematical Models
Automatic Parallelization of Mathematical Models
Coarse-Grained Explicit Parallelization Using Computational
Explicit Parallel Programming
Combining Parallelization at Several Levels
Pipelining the Task Graph
Sorting Equations for Short Access Distance
Future work
Automatic Parallelization of Models using Pipeline Extraction
from Combined RHS and Inlined Solvers
Background on Mathematical Modeling and Modelica
The OpenModelica Open Source Environment
Approaches to Exploit Parallelism in Mathematical Models
Automatic Fine-Grained Parallelization of Mathematical Models
Coarse-Grained Explicit Parallelization Using Computational
Explicit Parallel Programming
Combining Parallelization from Several Levels of Abstraction
Pipelining the Task Graph
Sorting Equations for Short Access Distance
Future work
Part 1
Chapter 1
Background and Introduction
In this chapter we first give a short background and introduction to the research area
investigated. We also state the research problem and list the contributions of this
work. At the end of the chapter we present the structure of this thesis and list the
papers presenting the results of the research.
1.1 Modeling and Simulation
In many areas modeling and simulation becomes more and more important. In
product development, for example, modeling and simulation is used to allow for
shorter development time and more robust systems. Instead of embarking on a time
consuming and expensive prototype construction, a model of the system is built and
experiments are performed on this model. The model can be a physical model
where some details of the real system has been left out, but usually the model is a
mathematical one stored in a computer and the experiments carried out on the
model are computer simulations. Running the simulations on a model instead of
building the system can help us to answer about the system which would not
otherwise be possible due to reasons such as:
The experiments would be too expensive to perform on a real system.
The investigated variable may not be accessible in the real system.
Performing some experiments on the real system may be too dangerous.
It may take a too long time to perform the experiment on the real system.
In order to perform a simulation of a model on a computer we must have an
executable program that performs all the calculations needed. When computer
simulations first saw the light of day these programs were hand written in relatively
low level languages like C or Fortran. Although hand coded simulation programs
are still used and developed, more and more models are written in high level
equation-based modeling languages such as Modelica[4], gPROMS[9], and VHDLAMS[8]. One of the great benefits of these equation-based languages is that the
mathematical models behind the simulations are usually given in equations and a lot
of manual work of transforming the equations into assignment statements can be
Related Work on Task Scheduling and Clustering 7
avoided. The same submodel can also be used in several different contexts where
the dependent variables, i.e., the variables to solve for, are not necessarily the same.
This greatly reduces development time and improves reusability. The information
about which variables are dependent variables and which are independent variables
in the equations is called the causality of the system.
As the models grow larger and more accurate simulation results are desired,
more computational power is needed. Although computers have become faster,
recently most of the increased computational power of new computers can only be
utilized with extensive usage of parallelism. This puts demands on the modeling
languages used to allow the simulation programs to utilize parallelism either by
introducing language constructs to allow the modeler to express parallelism
explicitly in the models, but even better by automatically parallelizing the same
models previously used in simulations on single CPU machines.
1.2 Related Work on Task Scheduling and Clustering
When a mathematical model is translated into executable simulation code a task
graph is generated which describes all dependencies between the tasks which puts
restrictions on the order in which the tasks can be executed. Therefore it is
important to have efficient algorithms that can schedule the tasks on a parallel
computer. Much research has been done in this area. In this section we summarize
some of the previous work on task scheduling and clustering.
A classification of scheduling algorithms can be found in [13], which classifies
the algorithms in a hierarchical manner. At the top level the algorithms are divided
into local and global algorithms, where the local algorithms schedule the tasks on
one processor whereas the global algorithms consider the case of multiple
processors. The global algorithms are further divided into static and dynamic
algorithms. In this work we explore static scheduling which means the scheduling
takes place at compile time.
Static scheduling can be done optimally or sub-optimally and sub-optimal
scheduling is further divided into heuristic and approximate scheduling. Both the
optimal and the approximate sub-optimal scheduling are divided into four different
kinds: enumerative, graph-theory, mathematical programming, and queuing theory.
The work in this thesis falls under the approximate scheduling category.
There exist algorithms for automatically scheduling entire taskgraphs on a fixed
number of processors, such as the Modified Critical Path (MCP) scheduling
algorithm [14] and the Earliest Ready Task (ERT) algorithm [15].
The problem with scheduling algorithms which solves the entire scheduling
problem, including assigning each task to a processor, is the computational
complexity of such algorithms. Therefore, a clustering algorithm is used to make
the job easier for the scheduler. A cluster is a set of tasks that run on the same
processor. After the clustering face, a smaller number of clusters can be assigned to
the processors and the scheduler still need to determine the execution order within
the processor, i.e., local scheduling.
8 Background and Introduction
Existing clustering algorithms include the Internalization algorithm [16] and the
Dominant Sequence Clustering (DSC) algorithm [17]. The Internalization algorithm
works by traversing all edges of the task graph and check whether assigning the two
tasks to the same processor would lead to an increased total execution time. If this
is not the case the edge is internalized and the two tasks are put in the same cluster.
1.3 Research Problem
In this section we discuss the research problem of this work.
In the research leading to this thesis the aim has been to investigate if other
techniques to automatically translate models stated in equation-based languages into
parallel code can lead to more efficient code compared to previously tested
approaches. A second objective of this work has been to reduce the complexity of
the translation algorithm in order to speed up the translation process.
The research methodology used in this work is the traditional system oriented
computer science research method. In order to validate our hypotheses, a prototype
implementation is built. By running simulations of test models on parallel
computers we measure the amount of time needed to complete the simulations. We
can compare these measurements to test runs on a single processor and thereby
calculate the gained speed-up. In order to compare the results to earlier work the
test model used is chosen such that test data are available from the earlier work to
which we compare our results. This work shares essentially the same objectives as
the work presented in [7] by Peter Aronsson, but we continue a bit further and
develop some new methods.
Parallelizing the simulation of a mathematical model can be done at several
levels, see Paper B, page 59. The calculation of the simulation results involves a
numerical solver which iterates over the simulation problem in order to compute the
result. Parallelization can be done at the numerical method level by using a parallel
version of the solver or at the system level by using a sequential solver where each
call to the right hand side of the system of equations is parallelized.
One hypothesis explored in this work is that more speedup can be gained if
parallelization is done at both of these levels at the same time.
The methods developed in Aronssons thesis use a graph rewriting system to
automatically merge tasks into larger units to increase the granularity of the task
graph. This is done on the global full system task graph. A second hypothesis
explored in this work is that compilation time can be reduced by assigning the tasks
to processors early, guided by information about locality present in the model, to
avoid expensive work on a large task graph, and instead later merge the tasks
locally in each processor, to increase granularity.
Contributions 9
1.4 Contributions
The following are the main contributions of this work:
Contributions to the OpenModelica compiler (specifically the event
handling mechanism) which is used in several research projects. This is
described in Paper A, pages 29-50.
A new variant of topological sorting of equations to allow for simple and
fast scheduling with little communication. This is described in Paper B,
pages 53-66.
Task clustering after processor assignment to enable pipelining of
simulations steps without unnecessary waiting times. This is described in
Paper C, pages 69-85.
1.5 Thesis Structure
This thesis has the following structure.
Part I is divided into two chapters where the first gives an introduction including
the research objective, some background on the Modelica Language and a summary
of the contributions of this thesis. The second chapter describes the implementation
of the prototype system developed as a part of this thesis work.
Part II contains the papers which presents the research results of this work.
1.6 List of Papers
The research results are presented in three papers in Part II of the thesis. The papers
Paper A: Event Handling in the OpenModelica Compiler and
Runtime System
Håkan Lundvall, Peter Fritzson, and Bernhard Bachmann
Edited version of a technical report published in Technical Reports in
Computer and Information Science No. 2 Linköping Electronic Press.
2008. An earlier shorter version of this paper was published in the
Proceedings of the 46th Conference on Simulation and Modelling of the
Scandinavian Simulation Society (SIMS2005), Trondheim, Norway,
October 13-14, 2005.
10 Background and Introduction
Paper B Automatic Parallelization of Object Oriented Models Across
Method and System
Håkan Lundvall and Peter Fritzson
Edited version of a paper originally published in Proceedings of 6th
Eurosim Congress, Ljubljana, Slovenia, 2007.
Paper C Automatic Parallelization of Models using Pipeline Extraction
from Combined RHS and Inlined Solvers
Håkan Lundvall and Peter Fritzson
Edited version of a paper submitted to the 14th Workshop on Compilers for
Parallel Computing, IBM Research Center, Zurich, Switzerland, January 79, 2009
Chapter 2
Implementation – The
OpenModelica Parallelizing
In order to test and evaluate the methods and theories developed in this thesis work,
which are described in Papers A to C, a prototype implementations of these
methods have been developed as part of the OpenModelica compiler. This chapter
describes the implementation of the prototype parallelizing backend for
2.1 Background
OpenModelica is an open source project aiming at creating a complete Modelica
modeling, compilation and simulation environment. The current version includes
the following parts:
A Modelica compiler (omc).
An interactive shell (OMShell) which gives a command interface to the
The OpenModelica Notebook (OMNotebook), a Mathematica style
electronic notebook for Modelica where Modelica models can be written
and simulated within the document.
A Modelica Eclipse plugin (MDT – Modelica Development Tooling)
The OpenModelica Development Environment (OMDev).
The OpenModelica project was started at PELAB in 1998 and is now run within
The Open Source Modelica Consortium [11].
In earlier work on automatic parallelization of Modelica code, the ModPar[7]
system was developed and integrated into the OpenModelica compiler.
12 Implementation – The OpenModelica Parallelizing Backend
Some code from the ModPar system has been reused also in this implementation
to save implementation time. The ModPar system is divided into a number of
different modules, some written in MetaModelica and some in C++. A description
of the modules is presented in Section 2.3.
2.2 Compiler Phases
In this section we provide a short overview of the different compiler phases
involved when compiling a Modelica model, see also Figure 2-1.
First a Modelica parser reads the Modelica source code and produces an abstract
syntax tree (AST) that represents the Modelica model. In the next step a translator
reorganizes the model into a flat list of equations and variables. This involves,
among other things, handling inheritance, import statements and redeclarations.
After the equations have been flattened the equations are topologically sorted
according to the causal dependencies between the equations. This step involves
symbolic manipulations such as algebraic simplifications, symbolic index
reduction, and, removal of trivial equations. Once the causality has been
established, the dependent variable in each equation, not part of a strong
component, is solved for and the equations are converted to assignment statements.
Equations that are part of a strong component must be solved simultaneously. Such
systems of simultaneous equations are either solved symbolically at this stage, if
possible, or left to a numerical solver. We now have an execution order in which the
right hand side of the equations can be evaluated.
In the last step C code is generated for all the assignment statements and a
suitable C code representation (e.g. an RHS function) of the strongly connected
equations is generated, which is then linked to a numerical solver.
Modules of the OpenModelica Compiler 13
Source Code
Modelica models
Flat model
Sorted equations
Optimized sorted
C Code
C Compiler
Figure 2-1. OpenModelica compiler translation phases.
The newly developed version of ModPar only influences the last few steps;
equation sorting and code generation. An extra step has been added to the
topological sorting to keep equations with dependencies closer together, and the
code generation step is exchanged for a set of modules which generates a task graph
and performs scheduling and generation of parallel code. In section 2.3 we give a
more detailed explanation of the modules involved.
2.3 Modules of the OpenModelica Compiler
The OpenModelica compiler is divided into a number of modules, see Figure 2-2. A
description of the entire compiler and its modules can be found in the
OpenModelica system documentation [10]. Most of the modules are implemented
in MetaModelica [12]. The ModPar system adds a number of modules to the
compiler. A list of the modules implementing the ModPar system is shown in table
2-1. For each module we have a section “Added Functionality” which summarizes
the contributions to the implementation compared to the old ModPar version.
14 Implementation – The OpenModelica Parallelizing Backend
(Env, name)
Flat Modelica
C code
(Env, name)
Figure 2-2. The most important modules of the OpenModelica Compiler (omc) with
module connections and data flow (from the OpenModelica System Documentation).
There are more than 40 modules in the compiler.
When using the ModPar system the SimCodeGen module is exchanged for the
ModPar system which takes over the task of generating simulation code. Some
changes have also been made to the DAELow module which handles the
topological sorting of the equations
Module name
Specific to ModPar
Table 2-1. List of modules implementing the ModPar system.
This module takes care of sorting of the equations according to data dependency
and building the block lower triangular form of the system. Input to the module is
Modules of the OpenModelica Compiler 15
the flattened set of equations. The module provides functions for matching of
variables to solve for, to access equations and finding out the causality between the
Main Functions
Below follows explanations of the most important functions of the DAELow
public function lower
input DAE.DAElist lst;
input Boolean add_dummy;
output DAELow outDAELow;
end lower;
This function takes a list of discrete algebraic equations (DAE), which is the
flattened model, and translates it into a different form, called DAELow defined in
this module. The DAELow representation splits the DAE into equations and
variables and further divides variables into known and unknown variables and the
equations into simple and non-simple equations.
The input variable add_dummy adds a state variable and an associated equation
which is independent of all other variables. This is used if the model contains no
state variables since the numeric solver requires at least one state variable.
public function incidenceMatrix
input DAELow inDAELow;
output IncidenceMatrix outIncidenceMatrix;
end incidenceMatrix;
This function calculates the incidence matrix, i.e., which variables are present in
each equation. This matrix has rows representing each equation and columns
representing each unknown variable. A non-zero entry means that the (column)
variable is referenced in the (row) equation. See also Paper C, page 77 and the
following page.
16 Implementation – The OpenModelica Parallelizing Backend
public function matchingAlgorithm
input DAELow inDAELow;
input IncidenceMatrix inIncidenceMatrix;
input IncidenceMatrixT inIncidenceMatrixT;
input MatchingOptions inMatchingOptions;
output Integer[:] outAssignments1;
output Integer[:] outAssignments2;
output DAELow outDAELow3;
output IncidenceMatrix outIncidenceMatrix4;
output IncidenceMatrixT outIncidenceMatrixT5;
end matchingAlgorithm;
This function performs the matching algorithm, which is the first part of sorting the
equations into BLT (Block Lower Triangular) form. The BLT form is discussed in
Paper C on page 77. The matching algorithm finds a variable that is solved in each
equation. But to also find out which equations form a block of equations, the second
algorithm of the BLT sorting is run, finding strong components. This function
returns the updated DAE which, in case of index reduction, has added equations and
variables, and the incidence matrix. The variable outAssignments is returned as a
vector of variable indices, as well as its inverse, i.e., which equation a variable is
solved in as a vector of equation indices.
The variable inMatchingOptions contain options given to the algorithm.
Whether index reduction should be used or not.
Whether the equation system is allowed to be underconstrained or not,
which is used when generating code for initial equations.
public function strongComponents
input IncidenceMatrix inIncidenceMatrix1;
input IncidenceMatrixT inIncidenceMatrixT2;
input Integer[:] inAssignments1;
input Integer[:] inAssignments2;
output list<list<Integer>> components;
end strongComponents;
This is the second part of the BLT sorting. It takes the variable assignments and the
incidence matrix as input and identifies strong components, i.e., subsystems of
equations. The result is stored in the output result variable, a list of integer lists
called components. The integers stored in the innermost list represent the equation
numbers and are references to specific equations of the model. The result is a
topological sorting of the dependencies between the equations, i.e., the equations
can be solved in the order given by the outermost list. If the innermost list contains
more than one equation, it constitutes a strongly connected component and the
involved equations must be solved simultaneously.
Modules of the OpenModelica Compiler 17
public function sortBlocksForShortAccessDistance
input list<list<Integer>> comps;
input Integer[:] matching;
input IncidenceMatrix incidenceMatrix;
output list<list<Integer>> outComps;
end sortBlocksForShortAccessDistance;
This function takes an already topologically sorted list of equations and rearranges
the equations to bring equations with direct dependencies closer together. Pseudo
code for this function can be found in Paper B, after page 62.
Added Functionality
The main difference compared to the sequential version of the compiler is the
sorting step introduced in the function sortBlocksForShortAccessDistance.
This can greatly reduce the need for communication between the processors
when we schedule the tasks based on the order of the equations given by this sorting
This module replaces the SimCodegen module when generating parallel code. In
the standard OpenModelica compiler the SimCodegen module traverses the sorted
equations as they come from the DAELow module and generates C code for the
equations. When generating parallel code the TaskGraph module traverses the
equations in the same way with the difference that instead of C code, a task graph is
generated and extra tasks implementing a Runge-Kutta solver are interleaved in the
generated task graph, i.e., a kind of inlining of the solver.
Main Functions
The buildTaskgraph function is the main function and only public function of
the TaskGraph module. Its job is to generate the task graph.
public function buildTaskgraph
input DAELow.DAELow inDAELow1;
input Integer[:] inAssignments2;
input Integer[:] inAssignments3;
input list<list<Integer>> inComponets;
end buildTaskgraph;
It takes the sorted list of equations and the matching of equations to unknown
variables as input. For each equation the variable matched to the equation by the
matching algorithm is solved for so that the equation can be reorganized into an
assignment statement. Then tasks are added for the right hand side of the
assignment and one task for the result being the root of this generated subtree.
18 Implementation – The OpenModelica Parallelizing Backend
When generating tasks for the right hand side expression, references to unknown
variables are looked up in the already generated part of the task graph. Tasks for
calculating all such references are already in the generated part of the task graph
since the equations are traversed in data dependency order. All tasks are marked
with the position in the topological sorting of the equation from which they were
The function does not have a return value. Instead the task graph is stored in the
internal state of the C++ modules. Normally MetaModelica functions cannot have
internal state, but calling C++ functions makes this possible.
Added Functionality
This module now also generates tasks for the solver itself and not just for
computing the right hand side of the simulated system. This means some extra
variables are introduced to store intermediate results used by the solver tasks and
the tasks calculating the right hand side are duplicated for each solver stage.
This module constitutes the interface between the MetaModelica part and the C++
part of the backend. It exposes functions for building the task graph and generating
simulation code. Since this module and the rest of the ModPar system is
implemented as a C++ library it can unlike MetaModelica modules, hold an internal
state. The generated task graph is stored in this internal state of the C++ library and
is accessible from all the C++ modules described below.
This module implements the scheduling algorithm. Input to the module is the
generated task graph and the number of processors. The result is one task list for
each processor. The first thing the scheduler does is to split all the tasks into one set
of tasks per processor to generate code for. The position of the equation in the
topological sorting is used for this.
In the next stage a topological sorting of the tasks within a processor must be
established. This is what is discussed in Paper C. The order in which the tasks are
used when generating the C code is established using a priority queue in which all
tasks associated to a processor is stored. The queue is sorted on two properties: 1)
task set index and 2) level. The task set index refers to which task set within a given
processor the task has been assigned to and the level refers to the length of the path
from the task to the ‘end task’. The ‘end task’ being a task with inbound edges from
all the tasks representing the unknown variables, thus being the last task in any
topological sorting. The task sets are discussed in Paper C. In short all tasks within
one processor are divided into three sets executed in order and where all inbound
Modules of the OpenModelica Compiler 19
communication to a processor is gathered to the boundary between the first set (Pa,i)
and the second set (Pb,i) and where all outgoing communication is gathered to the
boundary between the second set and the third set (Pc,i).
To calculate these properties the task graph is traversed with three depth first
traversals. The first one has a visitor function which sets the level attribute of each
visited node to the maximum level of all child nodes incremented by one. The
second one is a reverse depth first search which divides all nodes into three
1. The node has at least one incoming edge from a task scheduled on a higher
ranked processor or at least one parent that was already assigned to this
category. This means that this node is dependent on results from the
previous simulation step.
2. The node has at least one incoming edge from a task scheduled on a lower
ranked processor or at least one parent was already put in this category.
This means that some inbound communication from another processor
must have preceded this task.
3. The node does not fit into either of the two categories above.
In the third traversal the tasks are clustered into the three sets (Pa,i , Pb,i , and
Pb,i). The visitor function of the third traversal works in the following way:
If the currently visited node is in category 3 and there is at least one child
in category 1 or 2, then the node is inserted in Pa,i.
If the currently visited node is in category 1 or 2 and there are at least one
child assigned to different processor, then the node is inserted in Pb,i.
Otherwise the currently visited node is inserted in Pc,i.
Main Functions
The following are the main functions of the ModePar/Schedule module.
Schedule(TaskGraph*,VertexID start, VertexID end,
int nproc);
Initializes the scheduler and performs the scheduling algorithm described above.
TaskList * get_tasklist(int proc);
Returns the sorted task list for a given processor.
set<int>* getAssignedProcessors(VertexID v);
Returns the set of tasks assigned to a given processor .
bool isAssignedTo(VertexID v, int proc);
Checks whether a given node in the task graph is assigned to a processor.
20 Implementation – The OpenModelica Parallelizing Backend
Added Functionality
This module is almost completely rewritten since a totally different scheduling
approach is used compared to the original ModPar system. The task merging code
is replaced by a new scheduler that performs processor assignment by column index
in the BLT matrix as given by the DAELow module and local scheduling of the
tasks for each processor. The job of increasing the granularity of the code is moved
from the global perspective into the local scheduling for each processor.
This module generates parallel C code from the task graph along with the schedule
provided by the modpar/Schedule module.
The schedule provides one task queue for each processor to generate code for.
One function is generated for each task queue and put in separate files so that each
function is put in a separate object file together with the data array for the
simulation variables. Before generating the simulation functions the tasks are
traversed to collect data about all the communication needs. For each pair of
processors between which messages need to be communicated, a set is kept where
all variables communicated are stored. Before beginning to generate the tasks in Pc,i
for processor a given processor i these communication sets are used to generate
message receive code for all messages with processor i as destination. All messages
between Pa,j and Pb,i, for two processors i and j, are merged into one single
message. The same happens with the message send code after the tasks of Pb,i are
Main Functions
The following are the main functions in the ModPar/Codegen module.
void initialize(TaskGraph*, Schedule *, ...);
This function initializes the code generator. It takes the global task graph and the
schedule as input parameters. Some arguments to the function have been omitted
for brevity.
void generateCode(char * init_code);
This function uses the schedule and the task graph given in the initialization and
generates C code.
Added Functionality
In the version of ModPar that existed before this work started, there was only a
runtime for MPI available. In that version the tasks reaching the code generator was
merged into larger but fewer tasks. In a merged task all result variables of one large
task was collected into one message, but there could be more than one message
Simulation Runtime 21
between one pair of processors. In the new version the original small tasks are kept,
instead they are clustered into three sets. This means that the message passing code
has been rewritten.
The simulation code for the different processors is now also generated into
separate functions in order to be usable by the pthreads runtime.
This module implements the task graph and provides primitives for accessing
properties of the task graph nodes. The task graph is implemented using the Boost
graph Library [3].
Main Functions
The following are the main functions in the ModPar/TaskGraph module.
EdgeID add_edge(VertexID parent, VertexID child,
TaskGraph *tg, string *result=0,
int prio=0);
This function adds a vertex between two nodes in the task graph. The name of the
result variable communicated from the parent is given in the result argument.
In case of more than one incoming edge to a node there is a priority given in
order to sort out which order to use the incoming data in the task.
Other graph manipulating functions are available through the Boost graph
Added Functionality
The nodes of the task graph have been equipped with a new attribute which stores
information about which variable the task is involved in evaluating the result for.
This information is used by the scheduler to assign the task to the appropriate
processor. Otherwise this module has been kept largely the same.
2.4 Simulation Runtime
When the simulation code has been generated it is linked together with a simulation
runtime. The runtime is written in C++. Two different runtime systems have been
developed. One for distributed memory using MPI [1] and one for shared memory
using pthreads [2].
22 Implementation – The OpenModelica Parallelizing Backend
MPI-Based Runtime System
In this section we give a short overview of the MPI-based runtime system.
When running a parallel program using MPI all nodes run the same executable
and the MPI system takes care of starting up the program on each node that should
be used. Since the same code is run on all processors a switch statement takes care
of calling the correct simulation code for each processor.
Each task of the task graph generates a result, but if a task only represents a subexpression of one equation then there is no simulation variable from the model to
store the result in, so a temporary variable is used. In the MPI-based runtime these
temporary variables are allocated as a global array on the heap. This is due to the
fact that in the previous version of ModPar it was possible that such a variable
would be used in a message to another processor. In the new version, however, all
tasks originating from the same equation always get assigned to the same processor.
Messages to other processors are implemented using non-blocking MPI send
and receive. Before sending all the variables involved in one message are copied to
a send buffer, since they are not necessarily placed consecutively in memory.
On the receiving end there is a corresponding receive buffer from which the
values are copied to their final destination.
The function containing the simulation code is called from within a loop which
first updates the simulation time variable and after the simulation code is called
stores the new values of all simulation variables in a result file. One result file is
generated for each processor. In this way the time it takes to store the simulation
results are also distributed over all the processors. The files must be concatenated
afterwards to get the complete simulation result.
Pthreads-Based Runtime System
In the pthreads runtime the entire simulation is running in the same process but it is
divided into several threads. Since all threads share the same memory it is possible
to just keep one array of simulation variables that all threads reference. For the
communication we just have to make sure that the task that produces the value for a
variable that is used in a task on another thread has completed before the receiving
task starts. To accomplish we use a map indexed by the communication id
consisting of the sending and receiving thread number. In this map we store how
many simulation steps the sending thread has completed. The receiving thread
performs a busy waiting loop until the sending thread has passed the point were the
needed values are available and has increased the counter in the communication
However, it turns out that the simulation goes a lot faster if we separate the
simulation variables into one array per thread, see Paper C. Thus, in the latest
version of the prototype each thread has its own copy of the simulation variable
array and the communication mechanism is extended to copy the relevant variables
between the copies.
Additional Load Balancing and Memory Layout Ideas 23
The temporary variables used to store the results of subexpressions are
generated as local variables. In this way the C compiler is able to eliminate them
during optimization. The resulting executable looks the same as if the entire
equation was generated as one single C expression instead of a series of assignment
statements using only one operator per expression.
2.5 Additional Load Balancing and Memory Layout
Some ideas have not yet found their way into the current ModPar prototype.
In Paper C we mention the possibility of load balancing when the execution cost of
all tasks are not known. The idea is to make an initial guess of assigning the tasks
evenly over two processors and then run a small test run, adjust the initial guess
based on the test run and then iterate until the tasks are balanced. Then we split each
half in two and do the same thing for four processors. If this is done inside the
compiler a large part of the compilation work can be reused for each test
compilation so the compilation time should not suffer that much. This function is
not implemented, but we made some small test manually, which indicates that a
better load balancing can be achieved compared to just splitting the tasks evenly
over the processors.
In the current version of the prototype the simulation variables are laid out in
memory in the order they appear in the model. It would be better if we made the
memory layout of the variables according to the equation sorting. This would keep
all variables used by one processor close in memory. We should also make sure that
variables that are communicated between processes should be laid out adjacent to
each other so that they need not be copied to a communication buffer before
transmission to other processors.
Message Passing Interface Forum. MPI a message-passing interface standard. Technical
Report UT-CS-94-230. 1994.
B. Nicols, D. Buttlar, and J. P. Farrel. Pthreads Programming. O’Reilly & Associates,
J Siek, LQ Lee, A Lumsdaine. The Boost Graph Library: User Guide and Reference
Manual, Addison-Wesley, 2002.
Peter Fritzson. Principles of Object-Oriented Modeling and Simulation with Modelica 2.1,
940 pp., ISBN 0-471-471631, Wiley-IEEE Press, 2004. See also
www.openmodelica.org and book web page: www.mathcore.com/drModelica
The Modelica Association. The Modelica Language Specification Version 3.0, September
2007. http://www.modelica.org.
Peter Fritzson, et al. The OpenModelica Modeling, Simulation, and Software Development
Environment. In Simulation News Europe, 44/45, December 2005 See also:
Peter Aronsson. Automatic Parallelization of Equation-Based Simulation Programs. PhD
thesis, Dissertation No. 1022, Dept, Computer and Information Science, Linköping
University, Linköping, Sweden.
Ernst Christen and Kenneth Bakalar. VHDL-AMS – A Hardware Descriptions Language for
Analog and Mixed-Signal Applications. IEEE Transactions on Circuits and Systems II:
Analog and Digital Signal Processing, 46(10):1263-1272, 1999.
Paul Inigo Barton. The Modelling and Simulation of Combined Discrete/Continuous
Processes. PhD thesis, Department of Chemical Engineering, Imperial Collage of Science,
Technology and Medicine, London, UK, 1992.
The OpenModelica System Documentation, , February 2008.
The Open Source Modelica Consortium (OSMC)
Peter Fritzson. Modelica Meta-Programming and Symbolic Transformations –
MetaModelica Programming Guide. Draft version, www.openmodelica.org, June 2007.
Thomas L. Casavant and Jon G. Kuhl. A taxonomy of scheduling in general-purpos
distributed computing systems. Software Engineering, 14(2):141-154, 1988.
C.S. Park, S.B. Choi. Multiprocessor Scheduling Algorithm Utilizing Linear Clustering of
Directed Acyclic Graphs. In Parallel and Distributed Systems, Proceedings, 1997.
C.Y. Lee, J.J. Hwang, Y.C. Chow, F.D Anger. Multiprocessor Scheduling with
Interprocessor Communication Delays. Operating Research Letters, vol. 7(no. 3), 1988.
V. Sarkar. Partitioning and Scheduling Parallel Programs for Multiprocessors. MIT Press,
Cambridge, MA, 1989.
T. Yang, A. Gerasoulis, DSC: Scheduling Parallel Tasks on Parallel and Distributed
Systems, vol. 5(no. 9), 1994.
Avdelning, institution
Division, department
Institutionen för datavetenskap
Department of Computer
and Information Science
Report category
X Engelska/English
X Licentiatavhandling
Serietitel och serienummer
Title of series, numbering
Övrig rapport
Linköping Studies in Science and Technology
URL för elektronisk version
Thesis No. 1381
Automatic Parallelization using Pipelining for Equation-Based Simulation Languages
Håkan Lundvall
During the most recent decades modern equation-based object-oriented modeling and simulation languages, such as
Modelica, have become available. This has made it easier to build complex and more detailed models for use in
simulation. To be able to simulate such large and complex systems it is sometimes not enough to rely on the ability
of a compiler to optimize the simulation code and reduce the size of the underlying set of equations to speed up the
simulation on a single processor. Instead we must look for ways to utilize the increasing number of processing units
available in modern computers. However to gain any increased performance from a parallel computer the simulation
program must be expressed in a way that exposes the potential parallelism to the computer. Doing this manually is
not a simple task and most modelers are not experts in parallel computing. Therefore it is very appealing to let the
compiler parallelize the simulation code automatically. This thesis investigates techniques of using automatic
translation of models in typical equation based languages, such as Modelica, into parallel simulation code that enable
high utilization of available processors in a parallel computer.
The two main ideas investigated here are the following: first, to apply parallelization simultaneously to both the
system equations and the numerical solver, and secondly. to use software pipelining to further reduce the time
processors are kept waiting for the results of other processors. Prototype implementations of the investigated
techniques have been developed as a part of the OpenModelica open source compiler for Modelica. The prototype
has been used to evaluate the parallelization techniques by measuring the execution time of test models on a few
parallel archtectures and to compare the results to sequential code as well as to the results achieved in earlier work. A
measured speedup of 6.1 on eight processors on a shared memory machine has been reached. It still remains to
evaluate the methods for a wider range of test models and parallel architectures.
Automatic parallelization, Equation-Based Languages, Modelica
Department of Computer and Information Science
Linköpings universitet
Linköping Studies in Science and Technology
Faculty of Arts and Sciences - Licentiate Theses
No 17
No 28
No 29
No 48
No 52
No 60
No 71
No 72
No 73
No 74
No 104
No 108
No 111
No 113
No 118
No 126
No 127
No 139
No 140
No 146
No 150
No 165
No 166
No 174
No 177
No 181
No 184
No 187
No 189
No 196
No 197
No 203
No 212
No 230
No 237
No 250
No 253
No 260
No 283
No 298
No 318
No 319
No 326
No 328
No 333
No 335
No 348
No 352
No 371
No 378
No 380
No 381
No 383
No 386
No 398
Vojin Plavsic: Interleaved Processing of Non-Numerical Data Stored on a Cyclic Memory. (Available at:
FOA, Box 1165, S-581 11 Linköping, Sweden. FOA Report B30062E)
Arne Jönsson, Mikael Patel: An Interactive Flowcharting Technique for Communicating and Realizing Algorithms, 1984.
Johnny Eckerland: Retargeting of an Incremental Code Generator, 1984.
Henrik Nordin: On the Use of Typical Cases for Knowledge-Based Consultation and Teaching, 1985.
Zebo Peng: Steps Towards the Formalization of Designing VLSI Systems, 1985.
Johan Fagerström: Simulation and Evaluation of Architecture based on Asynchronous Processes, 1985.
Jalal Maleki: ICONStraint, A Dependency Directed Constraint Maintenance System, 1987.
Tony Larsson: On the Specification and Verification of VLSI Systems, 1986.
Ola Strömfors: A Structure Editor for Documents and Programs, 1986.
Christos Levcopoulos: New Results about the Approximation Behavior of the Greedy Triangulation, 1986.
Shamsul I. Chowdhury: Statistical Expert Systems - a Special Application Area for Knowledge-Based Computer Methodology, 1987.
Rober Bilos: Incremental Scanning and Token-Based Editing, 1987.
Hans Block: SPORT-SORT Sorting Algorithms and Sport Tournaments, 1987.
Ralph Rönnquist: Network and Lattice Based Approaches to the Representation of Knowledge, 1987.
Mariam Kamkar, Nahid Shahmehri: Affect-Chaining in Program Flow Analysis Applied to Queries of Programs, 1987.
Dan Strömberg: Transfer and Distribution of Application Programs, 1987.
Kristian Sandahl: Case Studies in Knowledge Acquisition, Migration and User Acceptance of Expert Systems, 1987.
Christer Bäckström: Reasoning about Interdependent Actions, 1988.
Mats Wirén: On Control Strategies and Incrementality in Unification-Based Chart Parsing, 1988.
Johan Hultman: A Software System for Defining and Controlling Actions in a Mechanical System, 1988.
Tim Hansen: Diagnosing Faults using Knowledge about Malfunctioning Behavior, 1988.
Jonas Löwgren: Supporting Design and Management of Expert System User Interfaces, 1989.
Ola Petersson: On Adaptive Sorting in Sequential and Parallel Models, 1989.
Yngve Larsson: Dynamic Configuration in a Distributed Environment, 1989.
Peter Åberg: Design of a Multiple View Presentation and Interaction Manager, 1989.
Henrik Eriksson: A Study in Domain-Oriented Tool Support for Knowledge Acquisition, 1989.
Ivan Rankin: The Deep Generation of Text in Expert Critiquing Systems, 1989.
Simin Nadjm-Tehrani: Contributions to the Declarative Approach to Debugging Prolog Programs, 1989.
Magnus Merkel: Temporal Information in Natural Language, 1989.
Ulf Nilsson: A Systematic Approach to Abstract Interpretation of Logic Programs, 1989.
Staffan Bonnier: Horn Clause Logic with External Procedures: Towards a Theoretical Framework, 1989.
Christer Hansson: A Prototype System for Logical Reasoning about Time and Action, 1990.
Björn Fjellborg: An Approach to Extraction of Pipeline Structures for VLSI High-Level Synthesis, 1990.
Patrick Doherty: A Three-Valued Approach to Non-Monotonic Reasoning, 1990.
Tomas Sokolnicki: Coaching Partial Plans: An Approach to Knowledge-Based Tutoring, 1990.
Lars Strömberg: Postmortem Debugging of Distributed Systems, 1990.
Torbjörn Näslund: SLDFA-Resolution - Computing Answers for Negative Queries, 1990.
Peter D. Holmes: Using Connectivity Graphs to Support Map-Related Reasoning, 1991.
Olof Johansson: Improving Implementation of Graphical User Interfaces for Object-Oriented KnowledgeBases, 1991.
Rolf G Larsson: Aktivitetsbaserad kalkylering i ett nytt ekonomisystem, 1991.
Lena Srömbäck: Studies in Extended Unification-Based Formalism for Linguistic Description: An Algorithm
for Feature Structures with Disjunction and a Proposal for Flexible Systems, 1992.
Mikael Pettersson: DML-A Language and System for the Generation of Efficient Compilers from Denotational Specification, 1992.
Andreas Kågedal: Logic Programming with External Procedures: an Implementation, 1992.
Patrick Lambrix: Aspects of Version Management of Composite Objects, 1992.
Xinli Gu: Testability Analysis and Improvement in High-Level Synthesis Systems, 1992.
Torbjörn Näslund: On the Role of Evaluations in Iterative Development of Managerial Support Sytems,
Ulf Cederling: Industrial Software Development - a Case Study, 1992.
Magnus Morin: Predictable Cyclic Computations in Autonomous Systems: A Computational Model and Implementation, 1992.
Mehran Noghabai: Evaluation of Strategic Investments in Information Technology, 1993.
Mats Larsson: A Transformational Approach to Formal Digital System Design, 1993.
Johan Ringström: Compiler Generation for Parallel Languages from Denotational Specifications, 1993.
Michael Jansson: Propagation of Change in an Intelligent Information System, 1993.
Jonni Harrius: An Architecture and a Knowledge Representation Model for Expert Critiquing Systems, 1993.
Per Österling: Symbolic Modelling of the Dynamic Environments of Autonomous Agents, 1993.
Johan Boye: Dependency-based Groudness Analysis of Functional Logic Programs, 1993.
No 402
No 406
No 414
No 417
No 436
No 437
No 440
FHS 3/94
FHS 4/94
No 441
No 446
No 450
No 451
No 452
No 455
FHS 5/94
No 462
No 463
No 464
No 469
No 473
No 475
No 476
No 478
FHS 7/95
No 482
No 488
No 489
No 497
No 498
No 503
FHS 8/95
FHS 9/95
No 513
No 517
No 518
No 522
No 538
No 545
No 546
FiF-a 1/96
No 549
No 550
No 557
No 558
No 561
No 563
No 567
No 575
No 576
No 587
No 589
No 591
No 595
No 597
Lars Degerstedt: Tabulated Resolution for Well Founded Semantics, 1993.
Anna Moberg: Satellitkontor - en studie av kommunikationsmönster vid arbete på distans, 1993.
Peter Carlsson: Separation av företagsledning och finansiering - fallstudier av företagsledarutköp ur ett agentteoretiskt perspektiv, 1994.
Camilla Sjöström: Revision och lagreglering - ett historiskt perspektiv, 1994.
Cecilia Sjöberg: Voices in Design: Argumentation in Participatory Development, 1994.
Lars Viklund: Contributions to a High-level Programming Environment for a Scientific Computing, 1994.
Peter Loborg: Error Recovery Support in Manufacturing Control Systems, 1994.
Owen Eriksson: Informationssystem med verksamhetskvalitet - utvärdering baserat på ett verksamhetsinriktat och samskapande perspektiv, 1994.
Karin Pettersson: Informationssystemstrukturering, ansvarsfördelning och användarinflytande - En komparativ studie med utgångspunkt i två informationssystemstrategier, 1994.
Lars Poignant: Informationsteknologi och företagsetablering - Effekter på produktivitet och region, 1994.
Gustav Fahl: Object Views of Relational Data in Multidatabase Systems, 1994.
Henrik Nilsson: A Declarative Approach to Debugging for Lazy Functional Languages, 1994.
Jonas Lind: Creditor - Firm Relations: an Interdisciplinary Analysis, 1994.
Martin Sköld: Active Rules based on Object Relational Queries - Efficient Change Monitoring Techniques,
Pär Carlshamre: A Collaborative Approach to Usability Engineering: Technical Communicators and System
Developers in Usability-Oriented Systems Development, 1994.
Stefan Cronholm: Varför CASE-verktyg i systemutveckling? - En motiv- och konsekvensstudie avseende arbetssätt och arbetsformer, 1994.
Mikael Lindvall: A Study of Traceability in Object-Oriented Systems Development, 1994.
Fredrik Nilsson: Strategi och ekonomisk styrning - En studie av Sandviks förvärv av Bahco Verktyg, 1994.
Hans Olsén: Collage Induction: Proving Properties of Logic Programs by Program Synthesis, 1994.
Lars Karlsson: Specification and Synthesis of Plans Using the Features and Fluents Framework, 1995.
Ulf Söderman: On Conceptual Modelling of Mode Switching Systems, 1995.
Choong-ho Yi: Reasoning about Concurrent Actions in the Trajectory Semantics, 1995.
Bo Lagerström: Successiv resultatavräkning av pågående arbeten. - Fallstudier i tre byggföretag, 1995.
Peter Jonsson: Complexity of State-Variable Planning under Structural Restrictions, 1995.
Anders Avdic: Arbetsintegrerad systemutveckling med kalkylkprogram, 1995.
Eva L Ragnemalm: Towards Student Modelling through Collaborative Dialogue with a Learning Companion, 1995.
Eva Toller: Contributions to Parallel Multiparadigm Languages: Combining Object-Oriented and Rule-Based
Programming, 1995.
Erik Stoy: A Petri Net Based Unified Representation for Hardware/Software Co-Design, 1995.
Johan Herber: Environment Support for Building Structured Mathematical Models, 1995.
Stefan Svenberg: Structure-Driven Derivation of Inter-Lingual Functor-Argument Trees for Multi-Lingual
Generation, 1995.
Hee-Cheol Kim: Prediction and Postdiction under Uncertainty, 1995.
Dan Fristedt: Metoder i användning - mot förbättring av systemutveckling genom situationell metodkunskap
och metodanalys, 1995.
Malin Bergvall: Systemförvaltning i praktiken - en kvalitativ studie avseende centrala begrepp, aktiviteter och
ansvarsroller, 1995.
Joachim Karlsson: Towards a Strategy for Software Requirements Selection, 1995.
Jakob Axelsson: Schedulability-Driven Partitioning of Heterogeneous Real-Time Systems, 1995.
Göran Forslund: Toward Cooperative Advice-Giving Systems: The Expert Systems Experience, 1995.
Jörgen Andersson: Bilder av småföretagares ekonomistyrning, 1995.
Staffan Flodin: Efficient Management of Object-Oriented Queries with Late Binding, 1996.
Vadim Engelson: An Approach to Automatic Construction of Graphical User Interfaces for Applications in
Scientific Computing, 1996.
Magnus Werner : Multidatabase Integration using Polymorphic Queries and Views, 1996.
Mikael Lind: Affärsprocessinriktad förändringsanalys - utveckling och tillämpning av synsätt och metod,
Jonas Hallberg: High-Level Synthesis under Local Timing Constraints, 1996.
Kristina Larsen: Förutsättningar och begränsningar för arbete på distans - erfarenheter från fyra svenska företag. 1996.
Mikael Johansson: Quality Functions for Requirements Engineering Methods, 1996.
Patrik Nordling: The Simulation of Rolling Bearing Dynamics on Parallel Computers, 1996.
Anders Ekman: Exploration of Polygonal Environments, 1996.
Niclas Andersson: Compilation of Mathematical Models to Parallel Code, 1996.
Johan Jenvald: Simulation and Data Collection in Battle Training, 1996.
Niclas Ohlsson: Software Quality Engineering by Early Identification of Fault-Prone Modules, 1996.
Mikael Ericsson: Commenting Systems as Design Support—A Wizard-of-Oz Study, 1996.
Jörgen Lindström: Chefers användning av kommunikationsteknik, 1996.
Esa Falkenroth: Data Management in Control Applications - A Proposal Based on Active Database Systems,
Niclas Wahllöf: A Default Extension to Description Logics and its Applications, 1996.
Annika Larsson: Ekonomisk Styrning och Organisatorisk Passion - ett interaktivt perspektiv, 1997.
Ling Lin: A Value-based Indexing Technique for Time Sequences, 1997.
No 598
No 599
No 607
No 609
FiF-a 4
FiF-a 6
No 615
No 623
No 626
No 627
No 629
No 631
No 639
No 640
No 643
No 653
FiF-a 13
No 674
No 676
No 668
No 675
FiF-a 14
No 695
No 700
FiF-a 16
No 712
No 719
No 723
No 725
No 730
No 731
No 733
No 734
FiF-a 21
FiF-a 22
No 737
No 738
FiF-a 25
No 742
No 748
No 751
No 752
No 753
No 754
No 766
No 769
No 775
FiF-a 30
No 787
No 788
No 790
No 791
No 800
No 807
Rego Granlund: C3Fire - A Microworld Supporting Emergency Management Training, 1997.
Peter Ingels: A Robust Text Processing Technique Applied to Lexical Error Recovery, 1997.
Per-Arne Persson: Toward a Grounded Theory for Support of Command and Control in Military Coalitions,
Jonas S Karlsson: A Scalable Data Structure for a Parallel Data Server, 1997.
Carita Åbom: Videomötesteknik i olika affärssituationer - möjligheter och hinder, 1997.
Tommy Wedlund: Att skapa en företagsanpassad systemutvecklingsmodell - genom rekonstruktion, värdering och vidareutveckling i T50-bolag inom ABB, 1997.
Silvia Coradeschi: A Decision-Mechanism for Reactive and Coordinated Agents, 1997.
Jan Ollinen: Det flexibla kontorets utveckling på Digital - Ett stöd för multiflex? 1997.
David Byers: Towards Estimating Software Testability Using Static Analysis, 1997.
Fredrik Eklund: Declarative Error Diagnosis of GAPLog Programs, 1997.
Gunilla Ivefors: Krigsspel coh Informationsteknik inför en oförutsägbar framtid, 1997.
Jens-Olof Lindh: Analysing Traffic Safety from a Case-Based Reasoning Perspective, 1997
Jukka Mäki-Turja:. Smalltalk - a suitable Real-Time Language, 1997.
Juha Takkinen: CAFE: Towards a Conceptual Model for Information Management in Electronic Mail, 1997.
Man Lin: Formal Analysis of Reactive Rule-based Programs, 1997.
Mats Gustafsson: Bringing Role-Based Access Control to Distributed Systems, 1997.
Boris Karlsson: Metodanalys för förståelse och utveckling av systemutvecklingsverksamhet. Analys och värdering av systemutvecklingsmodeller och dess användning, 1997.
Marcus Bjäreland: Two Aspects of Automating Logics of Action and Change - Regression and Tractability,
Jan Håkegård: Hiera rchical Test Architecture and Board-Level Test Controller Synthesis, 1998.
Per-Ove Zetterlund: Normering av svensk redovisning - En studie av tillkomsten av Redovisningsrådets rekommendation om koncernredovisning (RR01:91), 1998.
Jimmy Tjäder: Projektledaren & planen - en studie av projektledning i tre installations- och systemutvecklingsprojekt, 1998.
Ulf Melin: Informationssystem vid ökad affärs- och processorientering - egenskaper, strategier och utveckling, 1998.
Tim Heyer: COMPASS: Introduction of Formal Methods in Code Development and Inspection, 1998.
Patrik Hägglund: Programming Languages for Computer Algebra, 1998.
Marie-Therese Christiansson: Inter-organistorisk verksamhetsutveckling - metoder som stöd vid utveckling
av partnerskap och informationssystem, 1998.
Christina Wennestam: Information om immateriella resurser. Investeringar i forskning och utveckling samt
i personal inom skogsindustrin, 1998.
Joakim Gustafsson: Extending Temporal Action Logic for Ramification and Concurrency, 1998.
Henrik André-Jönsson: Indexing time-series data using text indexing methods, 1999.
Erik Larsson: High-Level Testability Analysis and Enhancement Techniques, 1998.
Carl-Johan Westin: Informationsförsörjning: en fråga om ansvar - aktiviteter och uppdrag i fem stora svenska
organisationers operativa informationsförsörjning, 1998.
Åse Jansson: Miljöhänsyn - en del i företags styrning, 1998.
Thomas Padron-McCarthy: Performance-Polymorphic Declarative Queries, 1998.
Anders Bäckström: Värdeskapande kreditgivning - Kreditriskhantering ur ett agentteoretiskt perspektiv,
Ulf Seigerroth: Integration av förändringsmetoder - en modell för välgrundad metodintegration, 1999.
Fredrik Öberg: Object-Oriented Frameworks - A New Strategy for Case Tool Development, 1998.
Jonas Mellin: Predictable Event Monitoring, 1998.
Joakim Eriksson: Specifying and Managing Rules in an Active Real-Time Database System, 1998.
Bengt E W Andersson: Samverkande informationssystem mellan aktörer i offentliga åtaganden - En teori om
aktörsarenor i samverkan om utbyte av information, 1998.
Pawel Pietrzak: Static Incorrectness Diagnosis of CLP (FD), 1999.
Tobias Ritzau: Real-Time Reference Counting in RT-Java, 1999.
Anders Ferntoft: Elektronisk affärskommunikation - kontaktkostnader och kontaktprocesser mellan kunder
och leverantörer på producentmarknader,1999.
Jo Skåmedal: Arbete på distans och arbetsformens påverkan på resor och resmönster, 1999.
Johan Alvehus: Mötets metaforer. En studie av berättelser om möten, 1999.
Magnus Lindahl: Bankens villkor i låneavtal vid kreditgivning till högt belånade företagsförvärv: En studie
ur ett agentteoretiskt perspektiv, 2000.
Martin V. Howard: Designing dynamic visualizations of temporal data, 1999.
Jesper Andersson: Towards Reactive Software Architectures, 1999.
Anders Henriksson: Unique kernel diagnosis, 1999.
Pär J. Ågerfalk: Pragmatization of Information Systems - A Theoretical and Methodological Outline, 1999.
Charlotte Björkegren: Learning for the next project - Bearers and barriers in knowledge transfer within an
organisation, 1999.
Håkan Nilsson: Informationsteknik som drivkraft i granskningsprocessen - En studie av fyra revisionsbyråer,
Erik Berglund: Use-Oriented Documentation in Software Development, 1999.
Klas Gäre: Verksamhetsförändringar i samband med IS-införande, 1999.
Anders Subotic: Software Quality Inspection, 1999.
Svein Bergum: Managerial communication in telework, 2000.
No 809
FiF-a 32
No 808
No 820
No 823
No 832
FiF-a 34
No 842
No 844
FiF-a 37
FiF-a 40
FiF-a 41
No. 854
No 863
No 881
No 882
No 890
FiF-a 47
No 894
No 906
No 917
No 916
No 919
No 915
No 931
No 933
No 938
No 942
No 956
FiF-a 58
No 964
No 973
No 958
FiF-a 61
No 985
No 982
No 989
No 990
No 991
No 999
No 1000
No 1001
No 988
FiF-a 62
No 1003
No 1005
No 1008
No 1010
No 1015
No 1018
No 1022
FiF-a 65
Flavius Gruian: Energy-Aware Design of Digital Systems, 2000.
Karin Hedström: Kunskapsanvändning och kunskapsutveckling hos verksamhetskonsulter - Erfarenheter
från ett FOU-samarbete, 2000.
Linda Askenäs: Affärssystemet - En studie om teknikens aktiva och passiva roll i en organisation, 2000.
Jean Paul Meynard: Control of industrial robots through high-level task programming, 2000.
Lars Hult: Publika Gränsytor - ett designexempel, 2000.
Paul Pop: Scheduling and Communication Synthesis for Distributed Real-Time Systems, 2000.
Göran Hultgren: Nätverksinriktad Förändringsanalys - perspektiv och metoder som stöd för förståelse och
utveckling av affärsrelationer och informationssystem, 2000.
Magnus Kald: The role of management control systems in strategic business units, 2000.
Mikael Cäker: Vad kostar kunden? Modeller för intern redovisning, 2000.
Ewa Braf: Organisationers kunskapsverksamheter - en kritisk studie av ”knowledge management”, 2000.
Henrik Lindberg: Webbaserade affärsprocesser - Möjligheter och begränsningar, 2000.
Benneth Christiansson: Att komponentbasera informationssystem - Vad säger teori och praktik?, 2000.
Ola Pettersson: Deliberation in a Mobile Robot, 2000.
Dan Lawesson: Towards Behavioral Model Fault Isolation for Object Oriented Control Systems, 2000.
Johan Moe: Execution Tracing of Large Distributed Systems, 2001.
Yuxiao Zhao: XML-based Frameworks for Internet Commerce and an Implementation of B2B
e-procurement, 2001.
Annika Flycht-Eriksson: Domain Knowledge Management inInformation-providing Dialogue systems,
Per-Arne Segerkvist: Webbaserade imaginära organisationers samverkansformer: Informationssystemarkitektur och aktörssamverkan som förutsättningar för affärsprocesser, 2001.
Stefan Svarén: Styrning av investeringar i divisionaliserade företag - Ett koncernperspektiv, 2001.
Lin Han: Secure and Scalable E-Service Software Delivery, 2001.
Emma Hansson: Optionsprogram för anställda - en studie av svenska börsföretag, 2001.
Susanne Odar: IT som stöd för strategiska beslut, en studie av datorimplementerade modeller av verksamhet
som stöd för beslut om anskaffning av JAS 1982, 2002.
Stefan Holgersson: IT-system och filtrering av verksamhetskunskap - kvalitetsproblem vid analyser och beslutsfattande som bygger på uppgifter hämtade från polisens IT-system, 2001.
Per Oscarsson:Informationssäkerhet i verksamheter - begrepp och modeller som stöd för förståelse av informationssäkerhet och dess hantering, 2001.
Luis Alejandro Cortes: A Petri Net Based Modeling and Verification Technique for Real-Time Embedded
Systems, 2001.
Niklas Sandell: Redovisning i skuggan av en bankkris - Värdering av fastigheter. 2001.
Fredrik Elg: Ett dynamiskt perspektiv på individuella skillnader av heuristisk kompetens, intelligens, mentala
modeller, mål och konfidens i kontroll av mikrovärlden Moro, 2002.
Peter Aronsson: Automatic Parallelization of Simulation Code from Equation Based Simulation Languages,
Bourhane Kadmiry: Fuzzy Control of Unmanned Helicopter, 2002.
Patrik Haslum: Prediction as a Knowledge Representation Problem: A Case Study in Model Design, 2002.
Robert Sevenius: On the instruments of governance - A law & economics study of capital instruments in limited liability companies, 2002.
Johan Petersson: Lokala elektroniska marknadsplatser - informationssystem för platsbundna affärer, 2002.
Peter Bunus: Debugging and Structural Analysis of Declarative Equation-Based Languages, 2002.
Gert Jervan: High-Level Test Generation and Built-In Self-Test Techniques for Digital Systems, 2002.
Fredrika Berglund: Management Control and Strategy - a Case Study of Pharmaceutical Drug Development,
Fredrik Karlsson: Meta-Method for Method Configuration - A Rational Unified Process Case, 2002.
Sorin Manolache: Schedulability Analysis of Real-Time Systems with Stochastic Task Execution Times,
Diana Szentiványi: Performance and Availability Trade-offs in Fault-Tolerant Middleware, 2002.
Iakov Nakhimovski: Modeling and Simulation of Contacting Flexible Bodies in Multibody Systems, 2002.
Levon Saldamli: PDEModelica - Towards a High-Level Language for Modeling with Partial Differential
Equations, 2002.
Almut Herzog: Secure Execution Environment for Java Electronic Services, 2002.
Jon Edvardsson: Contributions to Program- and Specification-based Test Data Generation, 2002
Anders Arpteg: Adaptive Semi-structured Information Extraction, 2002.
Andrzej Bednarski: A Dynamic Programming Approach to Optimal Retargetable Code Generation for
Irregular Architectures, 2002.
Mattias Arvola: Good to use! : Use quality of multi-user applications in the home, 2003.
Lennart Ljung: Utveckling av en projektivitetsmodell - om organisationers förmåga att tillämpa
projektarbetsformen, 2003.
Pernilla Qvarfordt: User experience of spoken feedback in multimodal interaction, 2003.
Alexander Siemers: Visualization of Dynamic Multibody Simulation With Special Reference to Contacts,
Jens Gustavsson: Towards Unanticipated Runtime Software Evolution, 2003.
Calin Curescu: Adaptive QoS-aware Resource Allocation for Wireless Networks, 2003.
Anna Andersson: Management Information Systems in Process-oriented Healthcare Organisations, 2003.
Björn Johansson: Feedforward Control in Dynamic Situations, 2003.
Traian Pop: Scheduling and Optimisation of Heterogeneous Time/Event-Triggered Distributed Embedded
Systems, 2003.
Britt-Marie Johansson: Kundkommunikation på distans - en studie om kommunikationsmediets betydelse i
affärstransaktioner, 2003.
No 1024
No 1034
No 1033
FiF-a 69
No 1049
No 1052
No 1054
FiF-a 71
No 1055
No 1058
FiF-a 73
No 1079
No 1084
FiF-a 74
No 1094
No 1095
No 1099
No 1110
No 1116
FiF-a 77
No 1126
No 1127
No 1132
No 1130
No 1138
No 1149
No 1156
No 1162
No 1165
FiF-a 84
No 1166
No 1167
No 1168
FiF-a 85
No 1171
FiF-a 86
No 1172
No 1183
No 1184
No 1185
No 1190
No 1191
No 1192
No 1194
No 1204
No 1206
No 1207
No 1209
No 1225
No 1228
No 1229
No 1231
No 1233
No 1244
No 1248
No 1263
FiF-a 90
No 1272
Aleksandra Tešanovic: Towards Aspectual Component-Based Real-Time System Development, 2003.
Arja Vainio-Larsson: Designing for Use in a Future Context - Five Case Studies in Retrospect, 2003.
Peter Nilsson: Svenska bankers redovisningsval vid reservering för befarade kreditförluster - En studie vid
införandet av nya redovisningsregler, 2003.
Fredrik Ericsson: Information Technology for Learning and Acquiring of Work Knowledge, 2003.
Marcus Comstedt: Towards Fine-Grained Binary Composition through Link Time Weaving, 2003.
Åsa Hedenskog: Increasing the Automation of Radio Network Control, 2003.
Claudiu Duma: Security and Efficiency Tradeoffs in Multicast Group Key Management, 2003.
Emma Eliason: Effektanalys av IT-systems handlingsutrymme, 2003.
Carl Cederberg: Experiments in Indirect Fault Injection with Open Source and Industrial Software, 2003.
Daniel Karlsson: Towards Formal Verification in a Component-based Reuse Methodology, 2003.
Anders Hjalmarsson: Att etablera och vidmakthålla förbättringsverksamhet - behovet av koordination och
interaktion vid förändring av systemutvecklingsverksamheter, 2004.
Pontus Johansson: Design and Development of Recommender Dialogue Systems, 2004.
Charlotte Stoltz: Calling for Call Centres - A Study of Call Centre Locations in a Swedish Rural Region,
Björn Johansson: Deciding on Using Application Service Provision in SMEs, 2004.
Genevieve Gorrell: Language Modelling and Error Handling in Spoken Dialogue Systems, 2004.
Ulf Johansson: Rule Extraction - the Key to Accurate and Comprehensible Data Mining Models, 2004.
Sonia Sangari: Computational Models of Some Communicative Head Movements, 2004.
Hans Nässla: Intra-Family Information Flow and Prospects for Communication Systems, 2004.
Henrik Sällberg: On the value of customer loyalty programs - A study of point programs and switching costs,
Ulf Larsson: Designarbete i dialog - karaktärisering av interaktionen mellan användare och utvecklare i en
systemutvecklingsprocess, 2004.
Andreas Borg: Contribution to Management and Validation of Non-Functional Requirements, 2004.
Per-Ola Kristensson: Large Vocabulary Shorthand Writing on Stylus Keyboard, 2004.
Pär-Anders Albinsson: Interacting with Command and Control Systems: Tools for Operators and Designers,
Ioan Chisalita: Safety-Oriented Communication in Mobile Networks for Vehicles, 2004.
Thomas Gustafsson: Maintaining Data Consistency im Embedded Databases for Vehicular Systems, 2004.
Vaida Jakoniené: A Study in Integrating Multiple Biological Data Sources, 2005.
Abdil Rashid Mohamed: High-Level Techniques for Built-In Self-Test Resources Optimization, 2005.
Adrian Pop: Contributions to Meta-Modeling Tools and Methods, 2005.
Fidel Vascós Palacios: On the information exchange between physicians and social insurance officers in the
sick leave process: an Activity Theoretical perspective, 2005.
Jenny Lagsten: Verksamhetsutvecklande utvärdering i informationssystemprojekt, 2005.
Emma Larsdotter Nilsson: Modeling, Simulation, and Visualization of Metabolic Pathways Using Modelica,
Christina Keller: Virtual Learning Environments in higher education. A study of students’ acceptance of educational technology, 2005.
Cécile Åberg: Integration of organizational workflows and the Semantic Web, 2005.
Anders Forsman: Standardisering som grund för informationssamverkan och IT-tjänster - En fallstudie
baserad på trafikinformationstjänsten RDS-TMC, 2005.
Yu-Hsing Huang: A systemic traffic accident model, 2005.
Jan Olausson: Att modellera uppdrag - grunder för förståelse av processinriktade informationssystem i transaktionsintensiva verksamheter, 2005.
Petter Ahlström: Affärsstrategier för seniorbostadsmarknaden, 2005.
Mathias Cöster: Beyond IT and Productivity - How Digitization Transformed the Graphic Industry, 2005.
Åsa Horzella: Beyond IT and Productivity - Effects of Digitized Information Flows in Grocery Distribution,
Maria Kollberg: Beyond IT and Productivity - Effects of Digitized Information Flows in the Logging
Industry, 2005.
David Dinka: Role and Identity - Experience of technology in professional settings, 2005.
Andreas Hansson: Increasing the Storage Capacity of Recursive Auto-associative Memory by Segmenting
Data, 2005.
Nicklas Bergfeldt: Towards Detached Communication for Robot Cooperation, 2005.
Dennis Maciuszek: Towards Dependable Virtual Companions for Later Life, 2005.
Beatrice Alenljung: Decision-making in the Requirements Engineering Process: A Human-centered
Approach, 2005
Anders Larsson: System-on-Chip Test Scheduling and Test Infrastructure Design, 2005.
John Wilander: Policy and Implementation Assurance for Software Security, 2005.
Andreas Käll: Översättningar av en managementmodell - En studie av införandet av Balanced Scorecard i ett
landsting, 2005.
He Tan: Aligning and Merging Biomedical Ontologies, 2006.
Artur Wilk: Descriptive Types for XML Query Language Xcerpt, 2006.
Per Olof Pettersson: Sampling-based Path Planning for an Autonomous Helicopter, 2006.
Kalle Burbeck: Adaptive Real-time Anomaly Detection for Safeguarding Critical Networks, 2006.
Daniela Mihailescu: Implementation Methodology in Action: A Study of an Enterprise Systems Implementation Methodology, 2006.
Jörgen Skågeby: Public and Non-public gifting on the Internet, 2006.
Karolina Eliasson: The Use of Case-Based Reasoning in a Human-Robot Dialog System, 2006.
Misook Park-Westman: Managing Competence Development Programs in a Cross-Cultural OrganisationWhat are the Barriers and Enablers, 2006.
Amra Halilovic: Ett praktikperspektiv på hantering av mjukvarukomponenter, 2006.
Raquel Flodström: A Framework for the Strategic Management of Information Technology, 2006.
No 1277
No 1283
FiF-a 91
No 1286
No 1293
No 1302
No 1303
No 1305
No 1306
No 1307
No 1309
No 1312
No 1313
No 1317
No 1320
No 1323
No 1329
No 1331
No 1332
No 1333
No 1337
No 1339
No 1351
No 1353
No 1356
No 1359
No 1361
No 1363
No 1371
No 1373
No 1381
Viacheslav Izosimov: Scheduling and Optimization of Fault-Tolerant Embedded Systems, 2006.
Håkan Hasewinkel: A Blueprint for Using Commercial Games off the Shelf in Defence Training, Education
and Research Simulations, 2006.
Hanna Broberg: Verksamhetsanpassade IT-stöd - Designteori och metod, 2006.
Robert Kaminski: Towards an XML Document Restructuring Framework, 2006
Jiri Trnka: Prerequisites for data sharing in emergency management, 2007.
Björn Hägglund: A Framework for Designing Constraint Stores, 2007.
Daniel Andreasson: Slack-Time Aware Dynamic Routing Schemes for On-Chip Networks, 2007.
Magnus Ingmarsson: Modelling User Tasks and Intentions for Service Discovery in Ubiquitous Computing,
Gustaf Svedjemo: Ontology as Conceptual Schema when Modelling Historical Maps for Database Storage,
Gianpaolo Conte: Navigation Functionalities for an Autonomous UAV Helicopter, 2007.
Ola Leifler: User-Centric Critiquing in Command and Control: The DKExpert and ComPlan Approaches,
Henrik Svensson: Embodied simulation as off-line representation, 2007.
Zhiyuan He: System-on-Chip Test Scheduling with Defect-Probability and Temperature Considerations,
Jonas Elmqvist: Components, Safety Interfaces and Compositional Analysis, 2007.
Håkan Sundblad: Question Classification in Question Answering Systems, 2007.
Magnus Lundqvist: Information Demand and Use: Improving Information Flow within Small-scale Business
Contexts, 2007.
Martin Magnusson: Deductive Planning and Composite Actions in Temporal Action Logic, 2007.
Mikael Asplund: Restoring Consistency after Network Partitions, 2007.
Martin Fransson: Towards Individualized Drug Dosage - General Methods and Case Studies, 2007.
Karin Camara: A Visual Query Language Served by a Multi-sensor Environment, 2007.
David Broman: Safety, Security, and Semantic Aspects of Equation-Based Object-Oriented Languages and
Environments, 2007.
Mikhail Chalabine: Invasive Interactive Parallelization, 2007.
Susanna Nilsson: A Holistic Approach to Usability Evaluations of Mixed Reality Systems, 2008.
Shanai Ardi: A Model and Implementation of a Security Plug-in for the Software Life Cycle, 2008.
Erik Kuiper: Mobility and Routing in a Delay-tolerant Network of Unmanned Aerial Vehicles, 2008.
Jana Rambusch: Situated Play, 2008.
Martin Karresand: Completing the Picture - Fragments and Back Again, 2008.
Per Nyblom: Dynamic Abstraction for Interleaved Task Planning and Execution, 2008.
Fredrik Lantz:Terrain Object Recognition and Context Fusion for Decision Support, 2008.
Martin Östlund: Assistance Plus: 3D-mediated Advice-giving on Pharmaceutical Products, 2008.
Håkan Lundvall: Automatic Parallelization using Pipelining for Equation-Based Simulation Languages,
Fly UP