%%% Please DO NOT EDIT this file - it was automatically generated. %%% Licentiate Theses from the Department of Information Technology, %%% Uppsala University, Sweden. %%% Series ISSN 1404-5117. %%% %%% ==================================================================== %%% BibTeX-file{ %%% author = "Bj{\"o}rn Victor", %%% date = "08 May 2012", %%% filename = "itlic.bib", %%% url = "http://www.it.uu.se/research/publications/reports/lic/itlic.bib", %%% www-home = "http://www.it.uu.se/research/publications/reports/lic/", %%% address = "Department of Information Technology, %%% Uppsala University, %%% Box 337, %%% SE-751 05 Uppsala, SWEDEN", %%% telephone = "+46 18 471 0000", %%% FAX = "+46 18 511925", %%% email = "Bjorn.Victor at it.uu.se", %%% dates = {2000--}, %%% keywords = "", %%% supported = "yes", %%% supported-by = "Bj{\"o}rn Victor", %%% abstract = "Licentiate Theses from the Department of %%% Information Technology at Uppsala University" %%% } %%% ==================================================================== @STRING{cb = "Centre for Image Analysis" } @STRING{csd = "Computing Science Division" } @STRING{docs = "Division of Computer Systems" } @STRING{hci = "Division of Human-Computer Interaction" } @STRING{it = "Department of Information Technology, Uppsala University" } @STRING{syscon = "Division of Systems and Control" } @STRING{tdb = "Division of Scientific Computing" } @PhDThesis{ itlic:2012-005, author = {Egi Hidayat}, title = {On Identification of Endocrine Systems}, school = it, department = syscon, year = 2012, number = {2012-005}, type = {Licentiate thesis}, month = jun, day = 1, note = {To appear}, abstract = {System identification finds nowadays application in various areas of biomedical research as a tool of empiric mathematical modeling and model individualization. Hormone regulation is a classical example of biological feedback where control theories, in general, and system identification, in particular, are indispensable in unraveling the regulation mechanisms and explicating the complex dynamical phenomena arising in endocrine systems. The main function of endocrine feedback regulation is to maintain the hormone levels within a particular physiological range as well as to sustain an appropriate hormone secretion pattern. Therefore, a natural operating mode of a closed-loop endocrine system is a stable periodic cycle. This property significantly reduces the repertoire of readily available identification techniques, not least due to the fact that the regulation (input) signal is immeasurable in many practical cases. There are two approaches to blind identification of hormone dynamics presented in this thesis. The first one is based on constrained nonlinear least-squares method. Weighting functions play an important role in satisfying the biological conditions on the identified model. The second approach is derived from a novel time-delay system identification method in Laguerre domain. In the latter, the time delay appears due to a specific input signal model and is estimated along with the finite-dimensional dynamics of hormone kinetics. } } @PhDThesis{ itlic:2012-004, author = {Soma Tayamon}, title = {Nonlinear System Identification with Applications to Selective Catalytic Reduction Systems}, school = it, department = syscon, year = 2012, number = {2012-004}, type = {Licentiate thesis}, month = jun, day = 7, note = {To appear} } @PhDThesis{ itlic:2012-003, author = {Magnus Gustafsson}, title = {Towards an Adaptive Solver for High-Dimensional {PDE} Problems on Clusters of Multicore Processors}, school = it, department = tdb, year = 2012, number = {2012-003}, type = {Licentiate thesis}, month = mar, day = 4, note = {Included papers available at \url{http://dx.doi.org/10.1007/978-3-642-11795-4_44}, \url{http://dx.doi.org/10.1007/978-3-642-28145-7_36}, \url{http://www.it.uu.se/research/publications/reports/2011-022} and \url{http://www.it.uu.se/research/publications/reports/2012-001}.} , abstract = {Accurate numerical simulation of time-dependent phenomena in many spatial dimensions is a challenging computational task apparent in a vast range of application areas, for instance quantum dynamics, financial mathematics, systems biology and plasma physics. Particularly problematic is that the number of unknowns in the governing equations (the number of grid points) grows exponentially with the number of spatial dimensions introduced, often referred to as the curse of dimensionality. This limits the range of problems that we can solve, since the computational effort and requirements on memory storage directly depend on the number of unknowns for which to solve the equations. In order to push the limit of tractable problems, we are developing an implementation framework, HAParaNDA, for high-dimensional PDE-problems. By using high-order accurate schemes and adaptive mesh refinement (AMR) in space, we aim at reducing the number of grid points used in the discretization, thereby enabling the solution of larger and higher-dimensional problems. Within the framework, we use structured grids for spatial discretization and a block-decomposition of the spatial domain for parallelization and load balancing. For integration in time, we use exponential integration, although the framework allows the flexibility of other integrators to be implemented as well. Exponential integrators using the Lanzcos or the Arnoldi algorithm has proven a succesful and efficient approach for large problems. Using a truncation of the Magnus expansion, we can attain high levels of accuracy in the solution. As an example application, we have implemented a solver for the time-dependent Schr{\"o}dinger equation using this framework. We provide scaling results for small and medium sized clusters of multicore nodes, and show that the solver fulfills the expected rate of convergence.} } @PhDThesis{ itlic:2012-002, author = {Fredrik Bjurefors}, title = {Measurements in Opportunistic Networks}, school = it, department = docs, year = 2012, number = {2012-002}, type = {Licentiate thesis}, month = mar, day = 2, note = {To appear}, abstract = {Opportunistic networks are a subset of delay tolerant networks where the contacts are unscheduled. Such networks can be formed ad hoc by wireless devices, such as mobile phones and laptops. In this work we use a data-centric architecture for opportunistic networks to evaluate data dissemination overhead, congestion in nodes' buffer, and the impact of transfer ordering. Dissemination brings an overhead since data is replicated to be spread in the network and overhead leads to congestion, i.e., overloaded buffers. We develop and implement an emulation testbed to experimentally evaluate properties of opportunistic networks. We evaluate the repeatability of experiments in the emulated testbed that is based on virtual computers. We show that the timing variations are on the order of milliseconds. The testbed was used to investigate overhead in data dissemination, congestion avoidance, and transfer ordering in opportunistic networks. We show that the overhead can be reduced by informing other nodes in the network about what data a node is carrying. Congestion avoidance was evaluated in terms of buffer management, since that is the available tool in an opportunistic network, to handle congestion. It was shown that replication information of data objects in the buffer yields the best results. We show that in a data-centric architecture were each data item is valued differently, transfer ordering is important to achieve delivery of the most valued data.} } @PhDThesis{ itlic:2012-001, author = {Gunnika Isaksson-Lutteman}, title = {Future Train Traffic Control -- Development and deployment of new principles and systems in train traffic control}, school = it, department = hci, year = 2012, number = {2012-001}, type = {Licentiate thesis}, month = apr, day = 3, abstract = {The train traffic control system of the future requires new solutions and strategies in order to better meet tomorrow's demands and goals. Uppsala University and Trafikverket has been collaborating for several years in research regarding train traffic control and how to improve traffic controllers' work environment. At an early stage in the collaboration there have been studies and analysis of important aspects of the traffic controller's tasks, strategies, decision making, use of information and support systems. This research resulted in new control paradigms, from control by exception to control by re-planning. By using this paradigm we developed and designed prototype systems and interfaces that better could meet future goals and contribute to more optimal use of infrastructure capacity. Based on this research, a new operational traffic control system called STEG, was developed in an iterative and user-centred design process. The system was deployed and tested operatively at a train traffic control centre in Sweden. The following evaluations focused on what happens when STEG is introduced in train traffic controllers' work places. The evaluation of STEG showed satisfied users with a feeling of active involvement during the design and deployment processes, and the new control strategies are functioning. STEG was seen as successful and was thereafter developed into MULTI-STEG, intended to be used by several users simultaneously and supporting them to share information in a new way. MULTI-STEG was deployed and tested at another train traffic control centre in Sweden. The following evaluations of MULTI-STEG focused on what happens when several users are involved and how train traffic controllers felt of sharing information with each other that before have been only in their own minds. Some complications occurred due to mistakes in the deployment process, but all together the evaluation showed positive attitudes towards the new system and MULTI-STEG was received as an efficient system for train traffic control. The main results are that STEG and MULTI-STEG can be used as an efficient train traffic control system and the new system can reduce the unnecessary cognitive load that the traffic controllers suffer from with today´s system. Also the deployment process is crucial whether the users are going to accept a new system or not. STEG was developed in a user-centred design process, but it is important that the deployment process is user-centered as well.} } @PhDThesis{ itlic:2011-006, author = {Anette L{\"o}fstr{\"o}m}, title = {Intranet Use as a Leadership Strategy}, school = it, department = hci, year = 2011, number = {2011-006}, type = {Licentiate thesis}, month = dec, day = 9, abstract = {This thesis presents results from an investigation of a virtual leadership strategy, which is utilised in the city of Stockholm. The Intranet is used as a strategic tool to implement a steering document in a similar way among all employees in the organisation. In this frame, features like sensemakings of the distributed information, influences of experienced lifeworlds, circumstances at local workplaces, cultural aspects and technological issues are explored. The investigation is fully qualitative. Interviews have been processed, recorded and transcribed. A survey with open and unstructured questions has broadened empirical results. The aim is to explore opinions towards and driving forces behind taking part of an Intranet based leader strategy and to investigate what circumstances at local workplaces affect the potential success of such a leader strategy. A new interpretation of Geert Hofstede~s work is suggested in future works. This is framed in a cultural model.} } @PhDThesis{ itlic:2011-005, author = {Elena Sundkvist}, title = {A High-Order Accurate, Collocated Boundary Element Method for Wave Propagation in Layered Media}, school = it, department = tdb, year = 2011, number = {2011-005}, type = {Licentiate thesis}, month = sep, day = 9, abstract = {The ultimate goal of this research is to construct a hybrid model for sound propagation in layered underwater environments with curved boundaries by employing a differential formulation for inhomogeneous layers and a boundary integral formulation for homogeneous layers. The discretization of the new hybrid model is a combination of a finite difference method for the Helmholtz equation for inhomogeneous media and a collocated boundary element method (BEM) for the integral equation for homogeneous media, while taking special care of the open boundaries and the common interface. Our focus is on sound wave propagation in layered piecewise \emph{homogeneous} fluid media. A boundary integral formulation of the Helmholtz equation governing the acoustic pressure is employed. A fourth-order accurate, collocated BEM is constructed for this equation in a systematic way, facilitating its generalization to even higher orders of accuracy. A novel approach (for boundary element techniques) is proposed for modelling the open vertical boundaries. We introduce artificial near- and far-field boundaries and apply nonlocal radiation boundary conditions at these. The collocated BEM is implemented in \textsc{Matlab} and the numerical experiments show the expected convergence rate. A strong benefit of the collocated BEM is that only the boundary is discretized, thus, reducing the number of dimensions by one. By a comparison with a fourth-order finite difference method (FD) it is illustrated that both methods have memory requirements of the same order, however, the number of unknowns in the collocated BEM is an order of magnitude less than in FD and the ratio grows with the problem size. } } @PhDThesis{ itlic:2011-004, author = {Niclas Finne}, title = {Towards Adaptive Sensor Networks}, school = it, department = docs, year = 2011, number = {2011-004}, type = {Licentiate thesis}, month = may, day = 30, abstract = {Wireless sensor networks consist of many small embedded devices that are equipped with sensors and a wireless communication unit. These devices, or sensor nodes, are typically low cost, resource constrained and battery-powered. Sensor network applications include environmental monitoring, industrial condition monitoring, building surveillance, and intelligent homes. Sensor network applications today are often developed either using standard software components which enables simpler development but leads to far from optimal performance, or software customized for the specific application which complicates development, software updates, and software reuse. We suggest that logic is separated from configuration and other information, for instance, network statistics and estimated power consumption. Software components publish their configuration and other information using a generalized programming abstraction. Configuration policies are separate modules that react on changes and reconfigure the sensor node as needed. These configuration policies are responsible for coordinating the configuration between the components and optimize the sensor network towards the application objectives. One of our contributions is that we demonstrate the need for self-monitoring and self-configuration based on experiences from two deployed sensor networks. Our main contribution is that we devise a configuration architecture that solves the problem of cross-layer optimization for sensor network applications without tight coupling between components, thus enabling standard and easily replaceable components to be used. The configuration architecture makes it possible to reach the same level of performance as specialized cross-layer optimizations but without adding application-specific knowledge to the components.} } @PhDThesis{ itlic:2011-003, author = {Rebecka Janols}, title = {Tailor the System or Tailor the User? How to Make Better Use of Electronic Patient Record Systems}, school = it, department = hci, year = 2011, number = {2011-003}, type = {Licentiate thesis}, month = may, day = 6, abstract = {Health care organisations are extremely complex because they consist of heterogeneous groups of people (clinical professions, patients, managers), use advanced technology (medical devices and patient record systems), and apply many organisational and clinical routines. When introducing Electronic Patient Record systems (EPR) in health care organisations, all these aspects get affected. Using a sociotechnical perspective is necessary in order to get a ``successful'' EPR usage. The aim of my PhD studies is to provide health care organisations with knowledge and insights into how they can improve their organisation and practice in relation to usage of EPR systems. In my research I have used a grounded theory methodology for studying, analysing and reflecting on how electronic patient record systems are used by professionals in their practice. Studies have been conducted during a 2.5 years collaborative research project. Within the studied health care organisation there are differing opinions if an EPR system is mainly a technical system or a tool to support the clinical organisation. This conceptual division leads to an uncertainty in who is responsible for the proper function of the EPR system and have a major effect for the clinicians in their clinical practice. During the research seven potential problems areas, \emph{mandate, usability, education, participation, improvements, support} and \emph{evaluation} have been identified as crucial for the health care organisation to manage to achieve an effective EPR usage. The main results are 1) The health care organisation needs to establish a problem-solving strategy that questions the reasons behind the problems occurred, 2) The different stakeholder groups need to interact, create a better understanding for each other~s perspective and agree on the same goal for the EPR system, 3) The clinical organisation needs help to improve their clinical practice in relation to the EPR system, 4) The EPR deployment and usage affect the clinicians in different ways. Their attitude towards the EPR system is dependent on the usability of the EPR system, the deployment process, their experience of participation, education, support and possibilities to improve the system.} } @PhDThesis{ itlic:2011-002, author = {Xin He}, title = {Robust Preconditioning Methods for Algebraic Problems, Arising in Multi-Phase Flow Models}, school = it, department = tdb, year = 2011, number = {2011-002}, type = {Licentiate thesis}, month = apr, day = 18, pages = 52, copies-printed= 80, abstract = {The aim of the project is to construct, analyse and implement fast and reliable numerical solution methods to simulate multi-phase flow, modeled by a coupled system consisting of the time-dependent Cahn-Hilliard and incompressible Navier-Stokes equations with variable viscosity and variable density. This thesis mainly discusses the efficient solution methods for the latter equations aiming at constructing preconditioners, which are numerically and computationally efficient, and robust with respect to various problem, discretization and method parameters. In this work we start by considering the stationary Navier-Stokes problem with constant viscosity. The system matrix arising from the finite element discretization of the linearized Navier-Stokes problem is nonsymmetric of saddle point form, and solving systems with it is the inner kernel of the simulations of numerous physical processes, modeled by the Navier-Stokes equations. Aiming at reducing the simulation time, in this thesis we consider iterative solution methods with efficient preconditioners. When discretized with the finite element method, both the Cahn-Hilliard equations and the stationary Navier-Stokes equations with constant viscosity give raise to linear algebraic systems with nonsymmetric matrices of two-by-two block form. In Paper I we study both problems and apply a common general framework to construct a preconditioner, based on the matrix structure. As a part of the general framework, we use the so-called element-by-element Schur complement approximation. The implementation of this approximation is rather cheap. However, the numerical experiments, provided in the paper, show that the preconditioner is not fully robust with respect to the problem and discretization parameters, in this case the viscosity and the mesh size. On the other hand, for not very convection-dominated flows, i.e., when the viscosity is not very small, this approximation does not depend on the mesh size and works efficiently. Considering the stationary Navier-Stokes equations with constant viscosity, aiming at finding a preconditioner which is fully robust to the problem and discretization parameters, in Paper II we turn to the so-called augmented Lagrangian (AL) approach, where the linear system is transformed into an equivalent one and then the transformed system is iteratively solved with the AL type preconditioner. The analysis in Paper II focuses on two issues, (1) the influence of a scalar method parameter (a stabilization constant in the AL method) on the convergence rate of the preconditioned method and (2) the choice of a matrix parameter for the AL method, which involves an approximation of the inverse of the finite element mass matrix. In Paper III we consider the stationary Navier-Stokes problem with variable viscosity. We show that the known efficient preconditioning techniques in particular, those for the AL method, derived for constant viscosity, can be straightforwardly applicable also in this case. One often used technique to solve the incompressible Navier-Stokes problem with variable density is via operator splitting, i.e., decoupling of the solutions for density, velocity and pressure. The operator splitting technique introduces an additional error, namely the splitting error, which should be also considered, together with discretization errors in space and time. Insuring the accuracy of the splitting scheme usually induces additional constrains on the size of the time-step. Aiming at fast numerical simulations and using large time-steps may require to use higher order time-discretization methods. The latter issue and its impact on the preconditioned iterative solution methods for the arising linear systems are envisioned as possible directions for future research. When modeling multi-phase flows, the Navier-Stokes equations should be considered in their full complexity, namely, the time-dependence, variable viscosity and variable density formulation. Up to the knowledge of the author, there are not many studies considering all aspects simultaneously. Issues on this topic, in particular on the construction of efficient preconditioners of the arising matrices need to be further studied.} } @PhDThesis{ itlic:2011-001, author = {David Ekl{\"o}v}, title = {Efficient Methods for Application Performance Analysis}, school = it, department = docs, year = 2011, number = {2011-001}, type = {Licentiate thesis}, month = feb, day = 18, abstract = {To reduce latency and increase bandwidth to memory, modern microprocessors are designed with deep memory hierarchies including several levels of caches. For such microprocessors, the service time for fetching data from off-chip memory is about two orders of magnitude longer than fetching data from the level-one cache. Consequently, the performance of applications is largely determined by how well they utilize the caches in the memory hierarchy, captured by their miss ratio curves. However, efficiently obtaining an application's miss ratio curve and interpreting its performance implications is hard. This task becomes even more challenging when analyzing application performance on multicore processors where several applications/threads share caches and memory bandwidths. To accomplish this, we need powerful techniques that capture applications' cache utilization and provide intuitive performance metrics. In this thesis we present three techniques for analyzing application performance, StatStack, StatCC and Cache Pirating. Our main focus is on providing memory hierarchy related performance metrics such as miss ratio, fetch ratio and bandwidth demand, but also execution rate. These techniques are based on profiling information, requiring both runtime data collection and post processing. For such techniques to be broadly applicable the data collection has to have minimal impact on the profiled application, allow profiling of unmodified binaries, and not depend on custom hardware and/or operating system extensions. Furthermore, the information provided has to be accurate and easy to interpret by programmers, the runtime environment and compilers. StatStack estimates an application's miss ratio curve, StatCC estimates the miss ratio of co-running application sharing the last-level cache and Cache Pirating measures any desired performance metric available through hardware performance counters as a function of cache size. We have experimentally shown that our methods are both efficient and accurate. The runtime information required by StatStack and StatCC can be collected with an average runtime overhead of 40\%. The Cache Pirating method measures the desired performance metrics with an average runtime overhead of 5\%. } } @PhDThesis{ itlic:2010-005, author = {Mikael Laaksoharju}, title = {Let Us Be Philosophers! Computerized Support for Ethical Decision Making}, school = it, department = hci, year = 2010, number = {2010-005}, type = {Licentiate thesis}, month = sep, day = 24, abstract = {This thesis presents a computerized tool for ethical decision making. For someone who is unfamiliar with the psychological theory that the tool is based on, it will perhaps first appear as a pointless piece of software. It does not give any guidance to what an ethically correct decision is, it does not suggest relevant ethical principles or guidelines and it does not even make reference to known cases of good moral conduct. In fact, it does not make any moral claims at all. The only two things that the tool does are that it stimulates reflective, analytical and holistic reasoning and blocks automatic, biased and constrained impulses. This approach is chosen to improve the decision maker~s ability to consider the relevant circumstances in a situation. By focusing on relevant interests of stakeholders, the scope of consideration in a moral situation can be expanded and the impact of decisions can be evaluated with respect to these. To justify this non-normative approach, the functionality of normative ethics is analyzed. The conclusion stresses the importance of self-conscious deliberation. Further arguments for advocating a systematic, holistic and self-critical handling of moral problems are collected from both philosophy and psychology. The structure and functionality of the tool is founded in psychological theory and especially the problem of cognitive biases in moral decision making is addressed. The tool has been evaluated in two studies, which both indicate that it actually delivers what it was designed to do. Statistically significant results show that the tool helped users to expand the scope of consideration in a moral problem situation compared to using an equivalent paper-and-pen-based method.} } @PhDThesis{ itlic:2010-004, author = {Kenneth Duru}, title = {Perfectly Matched Layers for Second Order Wave Equations}, school = it, department = tdb, year = 2010, number = {2010-004}, type = {Licentiate thesis}, month = may, day = 7, pages = 102, copies-printed= 80, abstract = {Numerical simulation of propagating waves in unbounded spatial domains is a challenge common to many branches of engineering and applied mathematics. Perfectly matched layers (PML) are a novel technique for simulating the absorption of waves in open domains. The equations modeling the dynamics of phenomena of interest are usually posed as differential equations (or integral equations) which must be solved at every time instant. In many application areas like general relativity, seismology and acoustics, the underlying equations are systems of second order hyperbolic partial differential equations. In numerical treatment of such problems, the equations are often rewritten as first order systems and are solved in this form. For this reason, many existing PML models have been developed for first order systems. In several studies, it has been reported that there are drawbacks with rewriting second order systems into first order systems before numerical solutions are obtained. While the theory and numerical methods for first order systems are well developed, numerical techniques to solve second order hyperbolic systems is an on-going research. In the first part of this thesis, we construct PML equations for systems of second order hyperbolic partial differential equations in two space dimensions, focusing on the equations of linear elasto-dynamics. One advantage of this approach is that we can choose auxiliary variables such that the PML is strongly hyperbolic, thus strongly well-posed. The second is that it requires less auxiliary variables as compared to existing first order formulations. However, in continuum the stability of both first order and second order formulations are linearly equivalent. A turning point is in numerical approximations. We have found that if the so-called geometric stability condition is violated, approximating the first order PML with standard central differences leads to a high frequency instability for any given resolution. The second order discretization behaves much more stably. In the second order setting instability occurs only if unstable modes are well resolved. The second part of this thesis discusses the construction of PML equations for the time-dependent Schr\"odinger equation. From mathematical perspective, the Schr\"odinger equation is unique, in the sense that it is only first order in time but second order in space. However, with slight modifications, we carry over our ideas from the hyperbolic systems to the Schr\"odinger equations and derive a set of asymptotically stable PML equations. The new model can be viewed as a modified complex absorbing potential (CAP). The PML model can easily be adapted to existing codes developed for CAP by accurately discretizing the auxiliary variables and appending them accordingly. Numerical experiments are presented illustrating the accuracy and absorption properties of the new PML model. We are hopeful that the results obtained in this thesis will find useful applications in time-dependent wave scattering calculations.} } @PhDThesis{ itlic:2010-003, author = {Salman Zubair Toor}, title = {Managing Applications and Data in Distributed Computing Infrastructures}, school = it, department = tdb, year = 2010, number = {2010-003}, type = {Licentiate thesis}, month = mar, day = 31, abstract = {Over the last few decades, the needs of computational power and data storage by collaborative, distributed scientific communities have increased very rapidly. Distributed computing infrastructures such as computing and storage grids provide means to connect geographically distributed resources and helps in addressing the needs of these communities. Much progress has been made in developing and operating grids, but several issues still need further attention. This thesis discusses three different aspects of managing large-scale scientific applications in grids: \begin{itemize} \item Using large-scale scientific applications is often in itself a complex task, and to set them up and run experiments in a distributed environment adds another level of complexity. It is important to design general purpose and application specific frameworks that enhance the overall productivity for the scientists. The thesis present further development of a general purpose framework where existing portal technology is combined with tools for robust and middleware independent job management. Also, a pilot implementation of a domain-specific problem solving environment based on a grid-enabled R solution is presented. \item Many current and future applications will need large-scale storage systems. Centralized systems are eventually not scalable enough to handle huge data volumes and also have can have additional problems with security and availability. An alternative is a reliable and efficient distributed storage system. In the thesis the architecture of a self-healing, grid-aware distributed storage cloud, Chelonia, is described and performance results for a pilot implementation are presented. \item In a distributed computing infrastructure it is very important to manage and utilize the available resources efficiently. The thesis presents a review of different resource brokering techniques and how they are implemented in different production level middlewares. Also, a modified resource allocation model for the Advanced Resource Connector (ARC) middleware is described and performance experiments are presented. \end{itemize}} } @PhDThesis{ itlic:2010-002, author = {Carl Nettelblad}, title = {Using {M}arkov Models and a Stochastic {L}ipschitz Condition for Genetic Analyses}, school = it, department = tdb, year = 2010, number = {2010-002}, type = {Licentiate thesis}, month = mar, day = 19, abstract = {A proper understanding of biological processes requires an understanding of genetics and evolutionary mechanisms. The vast amounts of genetical information that can routinely be extracted with modern technology have so far not been accompanied by an equally extended understanding of the corresponding processes. The relationship between a single gene and the resulting properties, phenotype of an individual is rarely clear. This thesis addresses several computational challenges regarding identifying and assessing the effects of quantitative trait loci (QTL), genomic positions where variation is affecting a trait. The genetic information available for each individual is rarely complete, meaning that the unknown variable of the genotype in the loci modelled also needs to be addressed. This thesis contains the presentation of new tools for employing the information that is available in a way that maximizes the information used, by using hidden Markov models (HMMs), resulting in a change in algorithm runtime complexity from exponential to log-linear, in terms of the number of markers. It also proposes the introduction of inferred haplotypes to further increase the power to assess these unknown variables for pedigrees of related genetically diverse individuals. Modelling consequences of partial genetic information are also treated. Furthermore, genes are not directly affecting traits, but are rather expressed in the environment of and in concordance with other genes. Therefore, significant interactions can be expected within genes, where some combination of genetic variation gives a pronounced, or even opposite, effect, compared to when occurring separately. This thesis addresses how to perform efficient scans for multiple interacting loci, as well as how to derive highly accurate empirical significance tests in these settings. This is done by analyzing the mathematical properties of the objective function describing the quality of model fits, and reformulating it through a simple transformation. Combined with the presented prototype of a problem-solving environment, these developments can make multi-dimensional searches for QTL routine, allowing the pursuit of new biological insight.} } @PhDThesis{ itlic:2010-001, author = {Anna Nissen}, title = {Absorbing Boundary Techniques for the Time-dependent Schr{\"o}dinger Equation}, school = it, year = 2010, number = {2010-001}, type = {Licentiate thesis}, month = feb, day = 11, abstract = {Chemical dissociation processes are important in quantum dynamics. Such processes can be investigated theoretically and numerically through the time-dependent Schr{\"o}dinger equation, which gives a quantum mechanical description of molecular dynamics. This thesis discusses the numerical simulation of chemical reactions involving dissociation. In particular, an accurate boundary treatment in terms of artificial, absorbing boundaries of the computational domain is considered. The approach taken here is based on the perfectly matched layer technique in a finite difference framework. The errors introduced due to the perfectly matched layer can be divided into two categories, the modeling error from the continuous model and numerical reflections that arise for the discretized problem. We analyze the different types of errors using plane wave analysis, and parameters of the perfectly matched layer are optimized so that the modeling error and the numerical reflections are of the same order. The level of accuracy is determined by estimating the order of the spatial error in the interior domain. Numerical calculations show that this procedure enables efficient calculations within a given accuracy. We apply our perfectly matched layer to a three-state system describing a one-dimensional IBr molecule subjected to a laser field and to a two-dimensional model problem treating dissociative adsorbtion and associative desorption of a H2 molecule on a solid surface. Comparisons made to standard absorbing layers in chemical physics prove our approach to be efficient, especially when high accuracy is of importance.} } @PhDThesis{ itlic:2009-005, author = {Martin Kronbichler}, title = {Numerical Methods for the {N}avier-{S}tokes Equations Applied to Turbulent Flow and to Multi-Phase Flow}, school = it, department = tdb, year = 2009, number = {2009-005}, type = {Licentiate thesis}, month = dec, day = 16, abstract = {This thesis discusses the numerical approximation of flow problems, in particular the large eddy simulation of turbulent flow and the simulation of laminar immiscible two-phase flow. The computations for both applications are performed with a coupled solution approach of the Navier-Stokes equations discretized with the finite element method. Firstly, a new implementation strategy for large eddy simulation of turbulent flow is discussed. The approach is based on the variational multiscale method, where scale ranges are separated by variational projection. The method uses a standard Navier-Stokes model for representing the coarser of the resolved scales, and adds a subgrid viscosity model to the smaller of the resolved scales. The scale separation within the space of resolved scales is implemented in a purely algebraic way based on a plain aggregation algebraic multigrid restriction operator. A Fourier analysis underlines the importance of projective scale separations and that the proposed model does not affect consistency of the numerical scheme. Numerical examples show that the method provides better results than other state-of-the-art methods for computations at low resolutions. Secondly, a method for modeling laminar two-phase flow problems in the vicinity of contact lines is proposed. This formulation combines the advantages of a level set model and of a phase field model: Motion of contact lines and imposition of contact angles are handled like for a phase field method, but the computational costs are similar to the ones of a level set implementation. The model is realized by formulating the Cahn-Hilliard equation as an extension of a level set model. The phase-field specific terms are only active in the vicinity of contact lines. Moreover, various aspects of a conservative level set method discretized with finite elements regarding the accuracy of force balance and prediction in jump of pressure between the inside and outside of a circular bubble are tested systematically. It is observed that the errors in velocity are mostly due to inaccuracies in curvature evaluation, whereas the errors in pressure prediction mainly come from the finite width of the interface. The error in both velocity and pressure decreases with increasing number of mesh points.} } @PhDThesis{ itlic:2009-004, author = {Katharina Kormann}, title = {Numerical Methods for Quantum Molecular Dynamics}, school = it, department = tdb, year = 2009, number = {2009-004}, type = {Licentiate thesis}, month = oct, day = 9, abstract = {The time-dependent Schr{\"o}dinger equation models the quantum nature of molecular processes. Numerical simulations of these models help in understanding and predicting the outcome of chemical reactions. In this thesis, several numerical algorithms for evolving the Schr{\"o}dinger equation with an explicitly time-dependent Hamiltonian are studied and their performance is compared for the example of a pump-probe and an interference experiment for the rubidium diatom. For the important application of interaction dynamics between a molecule and a time-dependent field, an efficient fourth order Magnus--Lanczos propagator is derived. Error growth in the equation is analyzed by means of a posteriori error estimation theory and the self-adjointness of the Hamiltonian is exploited to yield a low-cost global error estimate for numerical time evolution. Based on this theory, an $h,p$-adaptive Magnus--Lanczos propagator is developed that is capable to control the global error. Numerical experiments for various model systems (including a three dimensional model and a dissociative configuration) show that the error estimate is effective and the number of time steps needed to meet a certain accuracy is reduced due to adaptivity. Moreover, the thesis proposes an efficient numerical optimization framework for the design of femtosecond laser pulses with the aim of manipulating chemical reactions. This task can be formulated as an optimal control problem with the electric field of the laser being the control variable. In the algorithm described here, the electric field is Fourier transformed and it is optimized over the Fourier coefficients. Then, the frequency band is narrowed which facilitates the application of a quasi-Newton method. Furthermore, the restrictions on the frequency band make sure that the optimized pulse can be realized by the experimental equipment. A numerical comparison shows that the new method can outperform the Krotov method, which is a standard scheme in this field.} } @PhDThesis{ itlic:2009-003, author = {Marta L{\'a}rusd{\'o}ttir}, title = {Listen to Your Users - The Effect of Usability Evaluation on Software Development Practice}, school = it, year = 2009, number = {2009-003}, type = {Licentiate thesis}, month = oct, day = 2, abstract = {A vast majority of the people in the western world use software systems on daily basis for achieving their goals. To be able to do that each person needs to communicate what he or she wants to do to the system and receive a response. This communication needs to be easy for the user, especially when the system is new to him or her. Otherwise, the user either quits using the system; it takes a very long time or gets very irritated. A software team that is making new software needs to evaluate the usability of the system and various methods have been introduced in the literature to do that. My research focus in this thesis is on usability evaluation. I study particularly, how usability evaluation methods can be compared, what data should be gathered in usability evaluation to gain knowledge on how the software affects users who are getting new software for their daily work and how useful this data is to the recipients. Two experiments are reported in this thesis where results from using three different usability evaluation methods are compared. The main result from these two studies is that the think-aloud evaluation method should be used, if the goal of the evaluation is to gather as realistic information as possible on usability problems that the users will have when using the system. Furthermore four case studies are described in the thesis, in which usability evaluation was done by using the think-aloud method in co-operation with real users in their real work situation. These studies give much richer information on the actual use of the systems involved. The findings from one of these case studies indicate that the results from user observation done on a system that users have not seen before or used only for few days are rather similar to the results from usability evaluation done when users have used the system for a longer period. So the common practice of doing user observation on a software system that the participants have not seen before and then interpreting that the results will be the same for actual usage of the system when users will use the system for their real tasks for shorter or longer period is adequate.} } @PhDThesis{ itlic:2009-002, author = {Elina Eriksson}, title = {Making Sense of Usability - Organizational Change and Sensemaking when Introducing User-Centred Systems Design in Public Authorities}, school = it, department = hci, year = 2009, number = {2009-002}, type = {Licentiate thesis}, month = oct, day = 2, abstract = {Computers have become an everyday encounter, not at least in work settings. These computers must support the user in order for her to work in an effective and efficient manner. The field of Human-Computer Interaction (HCI) has among other things been focusing on this issue, and there are numerous methods and activities that aim at helping developers to develop usable computer systems. However, the methods and activities must be used in practice in order to be beneficial, not only within research, thus the methods must make sense to the system developers, as well as the organization in which they shall be applied. Furthermore, the organization must change in order to incorporate these methods and activities, and this change must impact a larger part of the organization than just the IT-department. My research has revolved around the introduction of usability methods in public authorities, in particular user-centred systems design (UCSD). My methodology has been action research, which implies a close collaboration with practitioners. Some of the methods used to gather data have been interviews, participatory observations, research diaries and field studies. In this licentiate thesis I present my work up to date and the theories that have informed my understanding of organizations and organizational change. Furthermore I have been influenced by the sensemaking theory, which can be used in order to understand how people make sense of technology, methods and organizational change. With the help of these theories, I extend my results further than presented in the papers. The notion of organizational change when introducing usability issues has not achieved sufficient attention in the HCI-field. This thesis is a step towards an understanding of this issue. Furthermore, I have, with the results from my papers together with the theories presented shown that although formal documents can be used to promote change, it is not enough. Rather there is a need to further explore the interplay between formal aspects and the situated work, and how to enhance sensegiving in this sensemaking process.} } @PhDThesis{ itlic:2009-001, author = {Joakim Eriksson}, title = {Detailed Simulation of Heterogeneous Wireless Sensor Networks}, school = it, department = docs, year = 2009, number = {2009-001}, type = {Licentiate thesis}, month = may, day = 14, abstract = {Wireless sensor networks consist of many small nodes. Each node has a small microprocessor, a radio chip, some sensors, and is usually battery powered which limits network lifetime. Applications of wireless sensor networks range from environmental monitoring and health-care to industrial automation and military surveillance. Since the nodes are battery powered and communication consumes more than computation much of the research focuses on power efficient communication. One of the problems is however to measure the power consumption and communication quality of the different solutions. Simulation of sensor networks can greatly increase development speed and also be used for evaluating power consumption as well as communication quality. Simulation experiments typically give easier access to fine grained results than corresponding real-world experiments. The problem with simulators is that it is hard to show that a simulation experiment corresponds well with a similar real-world experiment. This thesis studies how detailed simulation of wireless sensor networks can be validated for accuracy and also shows several important uses of detailed simulation such as power consumption profiling and interoperability testing. Both of them represent important topics in today's wireless sensor network research and development. The results of the thesis are the simulation platform COOJA/MSPSim and that we show that MAC-protocol experiments performed in our simulator COOJA/MSPSim correspond well with experiments performed in our testbed. We also show that using COOJA/MSPSim any software running in the simulation can be power profiled.} } @PhDThesis{ itlic:2008-003, author = {Andreas Hellander}, title = {Numerical Simulation of Well Stirred Biochemical Reaction Networks Governed by the Master Equation}, school = it, department = tdb, year = 2008, number = {2008-003}, type = {Licentiate thesis}, month = oct, day = 15, pages = 34, note = {Included papers available at \url{http://dx.doi.org/10.1016/j.jcp.2007.07.020}, \url{http://dx.doi.org/10.1007/s10543-008-0174-z}, and \url{http://dx.doi.org/10.1063/1.2897976}}, abstract = {Numerical simulation of stochastic biochemical reaction networks has received much attention in the growing field of computational systems biology. Systems are frequently modeled as a continuous-time discrete space Markov chain, and the governing equation for the probability density of the system is the (chemical) master equation. The direct numerical solution of this equation suffers from an exponential growth in computational time and memory with the number of reacting species in the model. As a consequence, Monte Carlo simulation methods play an important role in the study of stochastic chemical networks. The stochastic simulation algorithm (SSA) due to Gillespie has been available for more than three decades, but due to the multi-scale property of the chemical systems and the slow convergence of Monte Carlo methods, much work is currently being done in order to devise more efficient approximate schemes. In this thesis we review recent work for the solution of the chemical master equation by direct methods, by exact Monte Carlo methods and by approximate and hybrid methods. We also describe two conceptually different numerical methods to reduce the computational time when studying models using the SSA. A hybrid method is proposed, which is based on the separation of species into two subsets based on the variance of the copy numbers. This method yields a significant speed-up when the system permits such a splitting of the state space. A different approach is taken in an algorithm that makes use of low-discrepancy sequences and the method of uniformization to reduce variance in the computed density function.} } @PhDThesis{ itlic:2008-002, author = {Ioana Rodhe}, title = {Query Authentication and Data Confidentiality in Wireless Sensor Networks}, school = it, department = docs, year = 2008, number = {2008-002}, type = {Licentiate thesis}, month = jun, day = 11, abstract = {In this thesis we consider different aspects of security in sensor networks, in particular query authentication and confidential data aggregation. Authenticating the queries is important so attackers cannot modify existing queries because this would lead to wrong readings; or insert new queries into the network because this would lead to waste of energy. When answering to queries, in-network aggregation in sensor networks is an efficient way to save energy. Nevertheless, node capture in hostile environments require protocols for data aggregation where the intermediate nodes contribute with their own values to the aggregated data without getting access to it. Our contributions are two protocols for query authentication and confidential data aggregation together with a common layered key distribution scheme. Both static and mobile base stations are supported. The proposed protocols use symmetric cryptography, which is preferred in sensor networks because of the sensor's limited computational power, energy supply and memory storage. The results from our simulations show that, if an attacker captures a small number of nodes, the attacker can only introduce unauthorized queries into a limited part of the network and can only get access to a small part of the data that is aggregated into the network.} } @PhDThesis{ itlic:2008-001, author = {Mattias Wiggberg}, title = {Unwinding Processes in Computer Science Student Projects}, school = it, department = docs, year = 2008, number = {2008-001}, type = {Licentiate thesis}, month = mar, day = {19}, abstract = {This thesis investigates computer science student projects and some of the processes involved in the running of such projects. The reason for this investigation is that there are some interesting claims concerning the use of projects as learning approach. For example, they are supposed to give an extra challenge to the students and prepare them for working life, by adding known development methods from industry the sense of reality is emphasized, and involving industry partners as mock clients also increases the feeling of reality, but still unclear if these features contribute to the students' learning and what can be done to increase the potential for learning. There are thus interesting pedagogical challenges with computer science student projects. There is a need to better understand the effects on learning outcomes as a function of how a student project is designed. The focus in this thesis is on the effects of role taking in the project groups, work allocation, and goal setting in student projects. In this thesis, three studies investigating different aspects of processes in computer science student projects are presented. A number of conclusions are drawn, which serve as a starting point for further research. The first study investigates how power is distributed within a group of students in a full semester computer science project course. Perceived competence of fellow students contributes to personal influence in the student project groups, and three qualitatively different ways of experiencing competence among other students have been identified. The second study investigates experiences of the process of decision-making in a full semester computer science project course. Six categories describing the experience of decision-making have been identified spanning from the experience of decision-making in individual decisions too small and unimportant to handle by anyone else than the individual to the experience of decision-making as a democratic process involving both the full group and the context in which the group acts. The third study investigates Swedish engineering students' conceptions of engineering, where dealing with problems and their solutions and creativity are identified as core concepts. Subject concepts, as math, and physics do not appear in any top position. ``Math'', for example, accounts for only five percent of the total mentioned engineering terms. ``Physics'', the second highest ranked subject term, only accounts for circa 1 percent. By combining the results from the three studies, four central areas of general interest for designing and running student projects have been identified. These four features are: 1) the mechanism for work allocation; 2) students connection to external stakeholders; 3) focus on result or process; and 4) level of freedom in the project task. These four features are related to the results from the three studies in this thesis. The thesis is concluded by proposing an analytical framework based on those four features. The intention with the framework is to provide a useful tool for the analysis and development of future computer science student projects. } } @PhDThesis{ itlic:2007-006, author = {Bj{\"o}rn Halvarsson}, title = {Interaction Analysis and Control of Bioreactors for Nitrogen Removal}, school = it, department = syscon, year = 2007, number = {2007-006}, type = {Licentiate thesis}, month = dec, abstract = {Efficient control of wastewater treatment processes are of great importance. The requirements on the treated water (effluent standards) have to be met at a feasible cost. This motivates the use of advanced control strategies. In this thesis the activated sludge process, commonly found in the biological wastewater treatment step for nitrogen removal, was considered. Multivariable interactions present in this process were analysed. Furthermore, control strategies were suggested and tested in simulation studies. The relative gain array (RGA), Gramian-based interaction measures and an interaction measure based on the $\mathcal{H}_2$ norm were considered and compared. Properties of the $\mathcal{H}_2$ norm based measure were derived. It was found that the Gramian-based measures, and particularly the $\mathcal{H}_2$ norm based measure, in most of the considered cases were able to properly indicate the interactions. The information was used in the design of multivariable controllers. These were found to be less sensitive to disturbances compared to controllers designed on the basis of information from the RGA. The conditions for cost-efficient operation of the activated sludge process were investigated. Different fee functions for the effluent discharges were considered. It was found that the economic difference between operation in optimal and non-optimal setpoints may be significant even though the treatment performance was the same. This was illustrated graphically in operational maps. Strategies for efficient control were also discussed. Finally, the importance of proper aeration in the activated sludge process was illustrated. Strategies for control of a variable aeration volume were compared. These performed overall well in terms of treatment efficiency, disturbance rejection and process economy.} } @PhDThesis{ itlic:2007-005, author = {Mahen Jayawardena}, title = {Parallel Algorithms and Implementations for Genetic Analysis of Quantitative Traits}, school = it, department = tdb, year = 2007, number = {2007-005}, type = {Licentiate thesis}, month = sep, day = 28, note = {Typo corrected Sep 10 2007. Included papers available at \url{http://www.it.uu.se/research/publications/lic/2007-005/paperA.pdf}, \url{http://www.it.uu.se/research/publications/lic/2007-005/paperB.pdf}, \url{http://www.it.uu.se/research/publications/lic/2007-005/paperC.pdf}, and \url{http://www.it.uu.se/research/publications/lic/2007-005/paperD.pdf}} , abstract = {Many important traits in plants, animals and humans are quantitative, and most such traits are generally believed to be regulated by multiple genetic loci. Standard computational tools for analysis of quantitative traits use linear regression models for relating the observed phenotypes to the genetic composition of individuals in a population. However, using these tools to simultaneously search for multiple genetic loci is very computationally demanding. The main reason for this is the complex nature of the optimization landscape for the multidimensional global optimization problems that must be solved. This thesis describes parallel algorithms and implementation techniques for such optimization problems. The new computational tools will eventually enable genetic analysis exploiting new classes of multidimensional statistical models, potentially resulting in interesting results in genetics. We first describe how the algorithm used for global optimization in the standard, serial software is parallelized and implemented on a grid system. Then, we also describe a parallelized version of the more elaborate global optimization algorithm DIRECT and show how this can be deployed on grid systems and other loosely-coupled architectures. The parallel DIRECT scheme is further developed to exploit both coarse-grained parallelism in grid or clusters as well as fine-grained, tightly-coupled parallelism in multi-core nodes. The results show that excellent speedup and performance can be archived on grid systems and clusters, even when using a tightly-coupled algorithms such as DIRECT. Finally, a pilot implementation of a grid portal providing a graphical front-end for our code is implemented. After some further development, this portal can be utilized by geneticists for performing multidimensional genetic analysis of quantitative traits on a regular basis.} } @PhDThesis{ itlic:2007-004, author = {Olof Rensfelt}, title = {Tools and Methods for Evaluation of Overlay Networks}, school = it, department = docs, year = 2007, number = {2007-004}, type = {Licentiate thesis}, month = sep, day = 27, abstract = {Overlay networks is a popular method to deploy new functionality which does not currently exist in the Internet. Such networks often use the peer-to-peer principle where users are both servers as well as clients at the same time. We evaluate how overlay networks performs in a mix of strong and weak peers. The overlay system of study in this thesis is Bamboo, which is based on a distributed hash table (DHT). For the performance evaluation we use both simulations in NS-2 and emulations in the testbed PlanetLab. One of our contributions is a NS-2 implementation of the Bamboo DHT. To simulate nodes joining and leaving, NS-2 is modified to be aware of the identity of overlay nodes. To control experiments on PlanetLab we designed Vendetta. Vendetta is both a tool to visualize network events and a tool to control the individual peer-to-peer nodes on the physical machines. PlanetLab does not support bandwidth limitations which is needed to emulate weak nodes. Therefore we designed a lightweight connectivity tool called Dtour. Both the NS-2 and PlanetLab experiments indicate that a system like Bamboo can handle as much as 50 \% weak nodes and still serve requests. Although, the lookup latency and the number of successful lookups suffer with the increased network dynamics.} } @PhDThesis{ itlic:2007-003, author = {Thabotharan Kathiravelu}, title = {Towards Content Distribution in Opportunistic Networks}, school = it, department = docs, year = 2007, number = {2007-003}, type = {Licentiate thesis}, month = jun, day = 8, note = {Typo corrected 2007-06-01}, abstract = {Opportunistic networking is a new communication paradigm. Content Distribution in opportunistic networks is challenging due to intermittent connectivity, short connection durations and a highly dynamic topology. Research is needed to develop new applications and protocols that can distribute content in opportunistic networks. This thesis explores and evaluates approaches to developing mobile P2P systems for content distribution, focusing mainly on the problem of modeling device contacts. Contact duration and patterns of connections influence routing and forwarding strategies. To model device contacts we need to capture the characteristics of the network and be able to model its behavior. Connectivity models capture the aggregated network behavior by modeling the social connectedness of the network. A model of inter-device relationships can be constructed using parameters are extracted from connectivity traces collected in the field using real devices. These traces represent how connectivity might look in an opportunistic network. Altering and fine tuning these parameters enables us to change the stochastic behavior of the network and study the behavior of applications and protocols. Another approach is mobility modeling. There are two major drawbacks to using mobility models. First, in ad hoc networks traces have been collected which estimate the connectivity of the network. Typically traces are then used to model node mobility which in turn generates nodal connectivity during a simulation. This is a wasteful process and as the network size grows it becomes a tedious job. Second, the inter-contact time distribution observed in traces differs greatly from what is generated by popular mobility models. We have developed a connectivity model to generate synthetic device contact traces for opportunistic networks. We present the preliminary validation results from a comparative study of synthetic traces and traces collected in the field.} } @PhDThesis{ itlic:2007-002, author = {Jonas Boustedt}, title = {Students Working with a Large Software System: Experiences and Understandings}, school = it, year = 2007, number = {2007-002}, pages = 162, copies-printed= 80, type = {Licentiate thesis}, month = may, day = 24, abstract = {This monograph describes an empirical study with the overall aim of producing insights about how students experience the subject Computer Science and its learning environments, particularly programming and software engineering. The research takes a start in the students' world, from their perspective, using their stories, and hence, we have chosen a phenomenographic approach for our research. By interpreting the students' descriptions and experiences of various phenomena and situations, it is possible to gain knowledge about which different conceptions students can have and how teaching and the learning environment affect their understanding. In this study, we focus specifically on students' conceptions of aspects of object-oriented programming and their experiences of problem solving situations in connection with object-oriented system development. The questions posed enlighten and focus on the students' conceptions of both tangible and abstract concepts; the study investigates how students experienced a task concerning development in a specific software system, how they conceived the system itself, and how the students describe the system's plugin modules. Academic education in programming deals with abstract concepts, such as interfaces in the programming language Java. Hence, one of the questions in this study is how students describe that specific abstract concept, in a context where they are conducting a realistic software engineering task. The results show that there is a distinct variation of descriptions, spanning from a concrete to-do list, to a more advanced description where the interface plays a crucial role in order to produce dynamic and adaptive systems. The discussion interprets the results and suggests how we can use them in teaching to provide an extended and varied understanding, where the educational goal is to provide for and strengthen the conditions for students to be able to learn how to develop and understand advanced software.} } @PhDThesis{ itlic:2007-001, author = {Manivasakan Sabesan}, title = {Querying Mediated Web Services}, school = it, department = csd, year = 2007, number = {2007-001}, type = {Licentiate thesis}, month = feb, day = 5, abstract = {Web services provide a framework for data interchange between applications by incorporating standards such as XMLSchema, WSDL SOAP, HTTP etc. They define operations to be invoked over a network to perform the actions. These operations are described publicly in a WSDL document with the data types of their argument and result. Searching data accessible via web services is essential in many applications. However, web services don't provide any general query language or view capabilities. Current web services applications to access the data must be developed using a regular programming language such Java, or C#. The thesis provides an approach to simplify querying web services data and proposes efficient processing of database queries to views of wrapped web services. To show the effectiveness of the approach, a prototype, web Service MEDiator system (WSMED), is developed. WSMED provides general view and query capabilities over data accessible through web services by automatically extracting basic meta-data from WSDL descriptions. Based on imported meta-data, the user can then define views that extract data from the results of calls to web service operations. The views can be queried using SQL. A given view can access many different web service operations in different ways depending on what view attributes are known. The views can be specified in terms of several declarative queries to be applied by the query processor. In addition, the user can provide semantic enrichments of the meta-data with key constraints to enable efficient query execution over the views by automatic query transformations. We evaluated the effectiveness of our approach over multi-level views of existing web services and show that the key constraint enrichments substantially improve query performance.} } @PhDThesis{ itlic:2006-012, author = {Stefan Blomkvist}, title = {User-Centred Design and Agile Development of {IT} Systems}, school = it, department = hci, year = 2006, number = {2006-012}, type = {Licentiate thesis}, month = dec, day = 7, abstract = {Despite the knowledge on the interaction between humans and computers, too many IT systems show great deficits when it comes to usability. Every day we run into technology that makes our every day life and our work unnecessarily complex and difficult because of the IT systems that are not designed to support our tasks in a usable way. This thesis deals with different aspects of usability and the process of how to develop usable IT systems effectively. Primarily, the systems concerned are used in professional work, such as case handling systems in large government organisations. The main objective of this research is to understand which essential factors in the system development process that facilitate the development of usable IT systems. Another key subject is how Human-computer interaction (HCI) knowledge can be integrated into systems development, in particular the integration of user-centred design (UCD) and agile software development. The research is based on a qualitative approach and on reflections from my own experience in development projects. It also includes exploratory studies and design cases. The attempts of bridging the gap between HCI and software engineering have not been notably successful in practice. To address some of these problems, there is a need for a more precise definition of user-centred design, which is proposed in the thesis. Also, the complicated reality of systems development is not considered enough by HCI researchers and practitioner. To reach better results, UCD has to be integrated as a natural part of the development process. In the thesis, I argue that the agile approach together with UCD can be a good starting point for this integration. The agile approach emphasises that responding to change in development is more important than strictly adhering to a plan. Also, it prioritises regular deliveries of working software over extensive models and documentation. However, from a HCI perspective, agile processes do not inherently provide the required support for user-centred design. Nevertheless, the basic values and specific methods of agile development may have the potential to work very well together with UCD. For instance, iterative development is fundamental to both user-centred design and agile development. Finally, the research addresses how iterative methods can be used to find design solutions that support the users to cope with the problems of overview and control in case handling work.} } @PhDThesis{ itlic:2006-011, author = {{\AA}sa Cajander}, title = {Values and Perspectives Affecting {IT} Systems Development and Usability Work}, school = it, department = hci, year = 2006, number = {2006-011}, pages = {126}, copies-printed= {80}, type = {Licentiate thesis}, month = dec, day = 7, abstract = {Computer supported work is often stressful and inadequate computer systems and poor usability contribute to the problem. Still the work situation, and work environment of users are seldom considered when developing computer systems, and it is difficult to incorporate the ideas of User Centred Systems Design (UCSD) in practice. Hence, this research addresses the difficulty in integrating usability, UCSD and occupational health issues in IT systems development in order to improve the resulting work situation and well-being of users. How do basic values and perspectives of stakeholders in systems development projects affect the work with UCSD, usability and users’ health issues in the organisations studied? This research aims at influencing systems development in practice; hence, research is carried out in real life settings with an action research approach. Data is gathered and analysed with a qualitative research approach with interview studies, meetings with stakeholders, analysis of documentation, observations and field studies. The theoretical framework adheres to situated action, participatory design, and UCSD that stresses the importance of involving users in the design process. This research shows that several basic values and perspectives affect systems development and hinder the usability work, for example, the perspective on user representatives, the value of rationality and objectivity, and the perspective underpinning descriptions and discourse on work. Moreover, this research indicates that the strong business values of automation, efficiency and customer satisfaction shape the development of new technology, and ultimately the tasks and work practices of the civil servants. In short, the studies show that there are some contradictions in business values and the implementation of user-centred systems design, usability and health issues in systems development. Attitudes and perspectives are not easily changed, and change comes gradually. In these organisations, we continuously discuss the integration of health issues in systems development, and by introducing and changing the models of systems development these will hopefully enable communication and change forwards of new perspectives and values. However, a focus on models alone is insufficient and therefore we need to develop a systematic approach to include reflection and new perspectives. Perhaps the reflection itself would help us see our values and perspectives and to alter them?} } @PhDThesis{ itlic:2006-010, author = {Henrik Johansson}, title = {Performance Characterization and Evaluation of Parallel PDE Solvers}, school = it, department = tdb, year = 2006, number = {2006-010}, type = {Licentiate thesis}, month = nov, day = {22}, pages = {90}, copies-printed= {80}, note = {Included papers available at \url{http://www.it.uu.se/research/publications/lic/2006-010/paperA.pdf}, \url{http://www.it.uu.se/research/publications/lic/2006-010/paperB.pdf}, and \url{http://www.it.uu.se/research/publications/lic/2006-010/paperC.pdf}} , abstract = {Computer simulations that solve partial differential equations (PDEs) are common in many fields of science and engineering. To decrease the execution time of the simulations, the PDEs can be solved on parallel computers. For efficient parallel implementations, the characteristics of both the hardware and the PDE solver must be taken into account. In this thesis, we explore two ways to increase the efficiency of parallel PDE solvers. First, we use full-system simulation of a parallel computer to get detailed knowledge about cache memory usage for three parallel PDE solvers. The results reveal cases of bad cache memory locality. This insight can be used to improve the performance of the PDE solvers. Second, we study the adaptive mesh refinement (AMR) partitioning problem. Using AMR, computational resources are dynamically concentrated to areas in need of a high accuracy. Because of the dynamic resource allocation, the workload must repeatedly be partitioned and distributed over the processors. We perform two comprehensive characterizations of partitioning algorithms for AMR on structured grids. For an efficient parallel AMR implementation, the partitioning algorithm must be dynamically selected at run-time with regard to both the application and computer state. We prove the viability of dynamic algorithm selection and present performance data that show the benefits of using a large number of complementing partitioning algorithms. Finally, we discuss how our characterizations can be used in an algorithm selection framework.} } @PhDThesis{ itlic:2006-009, author = {Eddie Wadbro}, title = {Topology Optimization for Acoustic Wave Propagation Problems}, school = it, department = tdb, year = 2006, number = {2006-009}, type = {Licentiate thesis}, month = oct, day = 13, copies-printed= {80}, pages = {112}, abstract = {The aim of this study is to develop numerical techniques for the analysis and optimization of acoustic horns for time harmonic wave propagation. An acoustic horn may be viewed as an impedance transformer, designed to give an impedance matching between the feeding waveguide and the surrounding air. When modifying the shape of the horn, the quality of this impedance matching changes, as well as the angular distribution of the radiated wave in the far field (the directivity). The dimensions of the horns considered are in the order of the wavelength. In this wavelength region the wave physics is complicated, and it is hard to apply elementary physical reasoning to enhance the performance of the horn. Here, topology optimization is applied to improve the efficiency and to gain control over the directivity of the acoustic horn.} } @PhDThesis{ itlic:2006-008, author = {Agnes Rensfelt}, title = {Nonparametric Identification of Viscoelastic Materials}, school = it, department = syscon, year = 2006, number = {2006-008}, type = {Licentiate thesis}, month = oct, day = 6, abstract = {Viscoelastic materials can today be found in a wide range of practical applications. In order to make efficient use of these materials in construction, it is of importance to know how they behave when subjected to dynamic load. Characterization of viscoelastic materials is therefore an important topic, that has received a lot of attention over the years. This thesis treats different nonparametric methods for identifying the complex modulus of an viscoelastic material. The complex modulus is a frequency dependent material function, that describes the deformation of the material when subjected to uniaxial stress. With knowledge about this and other material functions, it is possible to simulate and predict how the material behaves under different kinds of dynamic loads. The complex modulus is often identified through wave propagation testing. An important aspect of identification is the accuracy of the estimates. For the identification to be as accurate as possible, it is important that the experimental data contains as much valuable information as possible. Different experimental condition, such as sensor locations and choice of excitation, can influence the amount of valuable information in the data. The procedure of determining optimal values for such design parameters is known as optimal experiment design. The first two papers of the thesis treats optimal experiment design for nonparametric identification of the complex modulus, based on wave propagation tests on large homogenous specimens. Optimal sensor locations is treated in the first paper, and optimal excitation in the second. In the third paper, a technique for estimating the complex modulus for a small pellet-sized specimen is presented. Three different procedures are considered, and an analysis of the accuracy of the estimates is carried out.} } @PhDThesis{ itlic:2006-007, author = {Stefan Engblom}, title = {Numerical Methods for the Chemical Master Equation}, school = it, department = tdb, year = 2006, number = {2006-007}, type = {Licentiate thesis}, month = sep, day = 27, copies-printed= 80, pages = 112, note = {Included papers available at \url{http://www.it.uu.se/research/publications/lic/2006-007/paperA.pdf}, \url{http://www.it.uu.se/research/publications/lic/2006-007/paperB.pdf}, and \url{http://www.it.uu.se/research/publications/lic/2006-007/paperC.pdf}} , abstract = {The numerical solution of chemical reactions described at the meso-scale is the topic of this thesis. This description, the \emph{master equation of chemical reactions}, is an accurate model of reactions where stochastic effects are crucial for explaining certain effects observed in real life. In particular, this general equation is needed when studying processes inside living cells where other macro-scale models fail to reproduce the actual behavior of the system considered. The main contribution of the thesis is the numerical investigation of two different methods for obtaining numerical solutions of the master equation. The first method produces statistical quantities of the solution and is a generalization of a frequently used macro-scale description. It is shown that the method is efficient while still being able to preserve stochastic effects. By contrast, the other method obtains the full solution of the master equation and gains efficiency by an accurate representation of the state space. The thesis contains necessary background material as well as directions for intended future research. An important conclusion of the thesis is that, depending on the setup of the problem, methods of highly different character are needed.} } @PhDThesis{ itlic:2006-006, author = {Anna Eckerdal}, title = {Novice Students' Learning of Object-Oriented Programming}, school = it, department = tdb, year = 2006, number = {2006-006}, type = {Licentiate thesis}, month = oct, day = 6, abstract = {This thesis investigates students' experiences of learning to program. Learning to program is a complex activity. It involves elements of learning abstract concepts as well as both learning and using advanced resources like computers and compilers. The learning experience is affected by factors like students' motives to learn and their general understanding of what learning to program means. These issues form the basis for the four research themes addressed in this thesis, specifically: students' experiences of what learning to program means; how students understand central concepts in programming; how students use and experience help from resources; and students' motives to learn to program. The thesis presents a qualitative study on novice students' experiences of learning object-oriented programming. Data was collected via semi-structured interviews. The interviews were analysed mainly using a phenomenographic research approach. The analysis resulted in the formulation of categories of description of students' qualitatively different ways to understand what learning to program means. In addition, categories describing different ways to understand the concepts \emph{object} and \emph{class} in object-oriented programming were formulated. From an educational point of view, these results can be used to identify aspects of learning to program that are critical from the students' perspective. The analysis of students' use of resources revealed that some resources were mainly used in a search-for-meaning way that promotes good learning, while another group of resources were mainly used in a superficial way. The two groups of resources seem however to interact with each other when students take responsibility for their own learning, which in particular characterizes their work with the larger computer assignments. When working with those, the students describe that both groups of resources were important for the learning. The analysis of students' descriptions of their motives to learn pinpoints motives that can enhance learning. In the study there were students who expressed that they had problems to know how to go about to study computer programming. This might indicate problems about knowing how to use available resources efficiently. Students who do not know how to use resources like the compiler in an efficient way, will have difficulties to perform assignments, which is expressed by the students as very important for the learning of concepts. The results also indicate the importance for educators to provide a learning environment with a variety of resources which can connect to students' different motives to learn, pointed to in the study. In this way all four aspects of the learning experience examined in the present study are important for students' learning of object-oriented programming. } } @PhDThesis{ itlic:2006-005, author = {Arvid Kauppi}, title = {A Human-Computer Interaction Approach to Train Traffic Control}, school = it, department = hci, year = 2006, number = {2006-005}, pages = 112, copies-printed= 80, type = {Licentiate thesis}, month = may, day = 30, abstract = {Train traffic in Sweden have increased over the last years and is today at an all time high. At the same time demands for improved punctuality and better predictability are increasing. If it would be possible to improve punctuality and thereby the possibility to use the infrastructural resources more optimally by providing improved systems for controlling train traffic, this could be a very cost efficient way to improve the train traffic. This thesis addresses research with a primary goal to investigate how, from a Human-Computer Interaction perspective, systems could be designed to better support the human's capacity and capabilities to control train traffic in an efficient way. Earlier research on humans in control of complex systems contributes to this work. One important part of the research is to gain knowledge on how train dispatchers perform their work today and which difficulties that exist. The research has a user centered approach. In close co-operation with train traffic professionals we try to discuss and develop solutions for improving the situation Since the project started in 1996 proposals of new strategies for control and also solutions for how such a system can be designed have been developed and to some extent evaluated. The Swedish National Rail Administration (Banverket) is now planning to build an operative control system based on control strategies and ideas from this research project.} } @PhDThesis{ itlic:2006-004, author = {Mikael Erlandsson}, title = {Usability in Transportation -- Improving the Analysis of Cognitive Work Tasks}, school = it, department = hci, year = 2006, number = {2006-004}, type = {Licentiate thesis}, month = jun, day = 02, note = {ISSN of originally printed version should be 1404-5117}, abstract = {In most vehicle domains within the transportation sector, traffic is increasing and vehicles are becoming more technologically advanced. In addition to this, drivers are faced with conflicting goals, such as punctuality, maintaining safety, minimizing fuel consumption, ensuring passenger comfort, etc. When accidents occur, the drivers' actions and mishaps are often in focus, even though the work environment, the organization behind the drivers, and the educational level may provide equally important explanations for incidents and actions. In this thesis, factors influencing operators' behaviour are acknowledged and attempts are made to understand how these factors affect vehicle operators in their daily work. Even though modern vehicles are equipped with new technology that supposedly aids drivers, studies of actual work typically reveal that these tools are not necessarily suited for their purpose. In a larger perspective, it is necessary not only to improve this technology, but to redesign how vehicle drivers perform their work. In practice, also traditional processes for development of technology affect how the operators work, although then simply a side effect of technology being introduced. Based on a deep understanding of the operators' work, the long-term goal here is to instead design new ways of working that allows the operators to use their skills to do meaningful driving tasks supported by technology. To acquire this understanding of how the operators work, a new method of information acquisition has been developed and tested within the rail and marine domains. These studies resulted with an understanding of what train and high-speed ferry operators are occupied with during their journeys, as well as insights into why they perform in certain manners and how they think and reason about these tasks.} } @PhDThesis{ itlic:2006-003, author = {Therese Berg}, title = {Regular Inference for Reactive Systems}, school = it, department = docs, year = 2006, number = {2006-003}, type = {Licentiate thesis}, month = apr, day = 27, pages = 132, abstract = {Models of reactive systems play a central role in many techniques for verification and analysis of reactive systems. Both a specification of the system and the abstract behavior of the system can be expressed in a formal model. Compliance with the functional parts in the specification can be controlled in different ways. Model checking techniques can be applied to a model of the system or directly to source code. In testing, model-based techniques can generate test suites from specification. A bottleneck in model-based techniques is however to construct a model of the system. This work concerns a technique that automatically constructs a model of a system without access to specification, code or internal structure. We assume that responses of the system to sequences of input can be observed. In this setting, so called regular inference techniques build a model of the system based on system responses to selected input sequences. There are three main contributions in this thesis. The first is a survey on the most well-known techniques for regular inference. The second is an analysis of Angluin's algorithm for regular inference on synthesized examples. On a particular type of examples, with prefix-closed languages, typically used to model reactive systems, the required number of input sequences grow approximately quadratically in the number of transitions of the system. However, using an optimization for systems with prefix-closed languages we were able to reduce the number of required input sequences with about 20\%. The third contribution is a developed regular inference technique for systems with parameters. This technique aims to better handle entities of communications protocols where messages normally have many parameters of which few determine the subsequent behavior of the system. Experiments with our implementation of the technique confirm a reduction of the required number of input sequences, in comparison with Angluin's algorithm.} } @PhDThesis{ itlic:2006-002, author = {Anders Hessel}, title = {Model-Based Test Case Selection and Generation for Real-Time Systems}, school = it, department = docs, year = 2006, number = {2006-002}, type = {Licentiate thesis}, month = mar, day = 7, copies-printed= 80, pages = 106, abstract = {Testing is the dominating verification technique used in industry today, and many man-hours and resources are invested in the testing of software products. To cut down the cost of testing, automated test execution becomes more and more popular. However, the selection of which tests to be executed is still mainly a manual process that is error prone, and often without sufficient guarantees that the system will be systematically tested. A way to achieve systematic testing is to ensure that the tests satisfy a required coverage criterion. In this thesis two main problems are addressed: the problem of how to formally specify coverage criteria, and the problem of how to generate a test suite from a formal system model, such that the test suite satisfies a given coverage criterion. We also address the problem of how to generate an optimal test suite, e.g., with respect to the total time required to execute the test suite. Our approach is to convert the test case generation problem into a reachability problem. We observe that a coverage criterion consists of a set of items, which we call coverage items. The problem of generating a test case for each coverage item can be treated as separate reachability problems. We use an on-the-fly method, where coverage information is added to the states of the analyzed system model, to solve the reachability problem of a coverage item. The coverage information is used to select a set of test cases that together satisfy all the coverage items, and thus the full coverage criterion. Based on the view of coverage items we define a language, in the form of parameterized observer automata, to formally describe coverage criteria. We show that the language is expressive enough to describe a variety of common coverage criteria in the literature. Two different ways to generate test suites form a system model and a given coverage criterion are presented. The first way is based on model annotations and uses the model checker Uppaal. The second way, where no annotations are needed, is a modified reachability analysis algorithm that is implemented in an extended version of the Uppaal tool. } } @PhDThesis{ itlic:2006-001, author = {Linda Brus}, title = {Recursive Black-box Identification of Nonlinear State-space {ODE} Models}, school = it, department = syscon, year = 2006, number = {2006-001}, type = {Licentiate thesis}, month = jan, abstract = {Nonlinear system identification methods is a topic that has been gaining interest over the last years. One reason is the many application areas in controller design and system development. However, the problem of modeling nonlinear systems is complex and finding a general method that can be used for many different applications is difficult. This thesis treats recursive identification methods for identification of systems that can be described by nonlinear ordinary differential equations. The general model structure enables application to a wide range of processes. It is also suitable for usage in combination with many nonlinear controller design methods. The first two papers of the thesis illustrates how a recursive prediction error method (RPEM) can be used for identification of an anaerobic digestion process and a solar heating system. In the former case the model complexity is significantly reduced compared to a semi-physical model of the system, without loosing much in model performance. In the latter case it is shown that it is possible to reach convergence even for a small data set, and that the resulting model is of comparable quality as a previously published grey-box model of the same system. The third paper consists of a convergence analysis of the studied RPEM. The analysis exploits averaging analysis using an associated ordinary differential equation, and formulates conditions for convergence to a minimum of the criterion function. Convergence to a true parameter set is also illustrated by an example. The fourth, and last, paper of this thesis addresses the problem of finding suitable initial parameters \textit{e.g.} for the RPEM. With a potentially non-convex criterion function the choice of initial parameters becomes decisive for whether the algorithm converges to the global optimum, or a local one. The suggested initialization algorithm is a Kalman filter based method. Experiments using a simulated example show that the Kalman based method can, under beneficial circumstances, be used for initialization of the RPEM. The result is further supported by successful identification experiments of a laboratory scale cascaded tanks process, where the Kalman based method was used for initialization. } } @PhDThesis{ itlic:2005-011, author = {Bj{\"o}rn Holmberg}, title = {Towards Markerless Analysis of Human Motion}, school = it, department = syscon, year = 2005, number = {2005-011}, type = {Licentiate thesis}, month = dec, day = 16, abstract = {The topic for this thesis is the analysis of human movement, or more specifically, markerless analysis of human movement from video material. By markerless analysis is meant that the full image material is used as input in contrast with the traditional marker systems that only use the position of marker centers. The basic idea is to use more of the information in the images to improve the analysis. Starting off with the aim of markerless analysis an application is designed that use to the subject added texture to estimate the position of the knee joint center in real images. The approach show the plausibility of using subject texture for estimation purposes. Another issue that is addressed is how one can generate synthetic image data. Using basic tools of graphics programming a virtual environment used to synthesize data is created. This environment is also used to evaluate some different camera solutions. One method to make three dimensional reconstruction from multiple images of an object is tested using the synthetic data. The method is based on a \emph{"brute force"} approach and does not show good performance in terms of computing speed. With appropriate representations of the three dimensional objects, mathematica methods might speed up the analysis. } } @PhDThesis{ itlic:2005-010, author = {Paul Sj{\"o}berg}, title = {Numerical Solution of the {F}okker-{P}lanck Approximation of the Chemical Master Equation}, school = it, department = tdb, year = 2005, number = {2005-010}, type = {Licentiate thesis}, month = dec, day = 15, copies-printed= {84}, pages = {100}, abstract = {The chemical master equation (CME) describes the probability for the discrete molecular copy numbers that define the state of a chemical system. Each molecular species in the chemical model adds a dimension to the state space. The CME is a difference-differential equation which can be solved numerically if the state space is truncated at an upper limit of the copy number in each dimension. The size of the truncated CME suffers from an exponential growth for an increasing number of chemical species. In this thesis the chemical master equation is approximated by a continuous Fokker-Planck equation (FPE) which makes it possible to use sparser computational grids than for CME. FPE on conservative form is used to compute steady state solutions by computation of an extremal eigenvalue and the corresponding eigenvector as well as time-dependent solutions by an implicit time-stepping scheme. The performance of the numerical solution is compared to a standard Monte Carlo algorithm. The computational work for a solutions with the same estimated error is compared for the two methods. Depending on the problem, FPE or the Monte Carlo algorithm will be more efficient. FPE is well suited for problems in low dimensions, especially if high accuracy desirable.} } @PhDThesis{ itlic:2005-009, author = {Magnus Evestedt}, title = {Parameter and State Estimation using Audio and Video Signals}, school = it, department = syscon, year = 2005, number = {2005-009}, pages = {110}, copies-printed= {80}, month = nov, day = {29}, type = {Licentiate thesis}, abstract = {The complexity of industrial systems and the mathematical models to describe them increases. In many cases point sensors are no longer sufficient to provide controllers and monitoring instruments with the information necessary for operation. The need for other types of information, such as audio and video, has grown. Suitable applications range in a broad spectrum from microelectromechanical systems and bio-medical engineering to papermaking and steel production. This thesis is divided into five parts. First a general introduction to the field of vision-based and sound-based monitoring and control is given. A description of the target application in the steel industry is included. In the second part, a recursive parameter estimation algorithm that does not diverge under lack of excitation is studied. The focus is on the stationary properties of the algorithm and the corresponding Riccati equation. The third part compares the parameter estimation algorithm to a number of well-known estimation techniques, such as the Normalized Least Mean Squares and the Kalman filter. The benchmark for the comparison is an acoustic echo cancellation application. When the input is insufficiently exciting, the studied method performs best of all considered schemes. The fourth part of the thesis concerns an experimental application of vision-based estimation. A water model is used to simulate the behaviour of the steel bath in a Linz-Donawitz steel converter. The water model is captured from the side by a video camera. The images together with a nonlinear model is used to estimate important process parameters, describing the heat and mass transport in the process. The estimation results are compared to those obtained by previous researchers and the suggested approach is shown to decrease the estimation error variance by $50\%$. The complexity of the parameter estimation procedure by means of optimization makes the computation time large. In the final part, the time consumption of the estimation is decreased by using a smaller number of data points. Three ways of choosing the sampling points are considered. An observer- based approach decreases the computation time significantly, with an acceptable loss of accuracy of the estimates. } } @PhDThesis{ itlic:2005-008, author = {Niklas Johansson}, title = {Usable IT Systems for Mobile Work}, school = it, department = hci, year = 2005, number = {2005-008}, type = {Licentiate thesis}, month = dec, day = 9, pages = 188, copies-printed= 80, abstract = {Today, mobile technology is making its entry into working life within all sorts of occupations. When the purpose of the technology is to support mo-bile work, new requirements appear - for both the technology itself and for the emerging new work processes - as a result of these new conditions. Con-sequently, the introduction of a new IT system will affect the organisation and the way work is performed. This thesis addresses these changes in work processes and ways to provide a supporting IT system. An underlying com-ponent of my research work is the belief that the personnel from the organi-sation itself must participate in a large extent when developing new work processes and when designing supporting IT systems, since they will be us-ing the IT system as a tool in their future work practice. To understand the nature of mobility in a work context and how it affects usability in IT systems, I have initiated studies of the area where mobile work is supported by technology. Important characteristics have been found that affect mobile work. My research work has concerned traditional profes-sions, primarily professions within mobile healthcare. An exhaustive study of how to design new work processes within the area of home care of the elderly has been carried out, accompanied by field studies of mobile work within the mobile healthcare sector. The results have been described in terms of aspects of future work processes that are effective and sustainable. Moreover, important characteristics of mobile technology that support this kind of mobile work have been identified. The two perspectives are then merged, in order to design usable IT systems for mobile work.} } @PhDThesis{ itlic:2005-007, author = {Mei Hong}, title = {On Two Methods for Identifying Dynamic Errors-in-Variables Systems}, school = it, department = syscon, year = 2005, number = {2005-007}, type = {Licentiate thesis}, month = nov, day = 16, pages = {108}, copies-printed= {80}, abstract = {Identification of dynamic errors-in-variables systems, where both inputs and outputs are affected by errors (measurement noises), is a fundamental problem of great interest in many areas, such as process control, econometrics, astronomical data reduction, image processing, \textit{etc.}. This field has received increased attention within several decades. Many solutions have been proposed with different approaches. In this thesis, the focus is on some specific problems concerning two time domain methods for identifying linear dynamic errors-in-variables systems. The thesis is divided into four parts. In the first part, a general introduction to the problem of identifying errors-in-variables systems and different approaches to solve the problem are given. Also, a summary of the contributions and some topics for future works are presented. The second part of the thesis considers the instrumental variables based approaches. They are studied under the periodic excitation condition. The main motivation is to analyze what type of instrumental variables should be chosen to maximally utilize the information of the periodic measurements. A particular overdetermined instrumental variable estimator is proposed, which can achieve optimal performance without weighting. The asymptotic convergence properties of the Bias-eliminating least squares (BELS) methods are investigated in the third part. By deriving an error dynamics equation for the parameter estimates, it is shown that the convergence of the bias-eliminating algorithms is determined by the largest magnitude of the eigenvalues of the system matrix. To overcome the possible divergence of the iteration-type bias-eliminating algorithms under very low signal-to-noise ratio, we re-formulate the bias-elimination problem as a minimization problem and develop a variable projection algorithm to perform consistent parameter estimation. Part four contains an analysis of the accuracy properties of the BELS estimates. It is shown that the estimated system parameters and the estimated noise variances are asymptotically Gaussian distributed. An explicit expression for the normalized asymptotic covariance matrix of the estimated system parameters and the estimated noise variances is derived. } } @PhDThesis{ itlic:2005-006, author = {Erik B{\"a}ngtsson}, title = {Robust Preconditioned Iterative Solution Methods for Large-Scale Nonsymmetric Problems}, school = it, department = tdb, year = 2005, number = {2005-006}, type = {Licentiate thesis}, month = nov, day = 3, note = {Typos corrected 2005-11-21}, abstract = {We study robust, preconditioned, iterative solution methods for large-scale linear systems of equations, arising from different applications in geophysics and geotechnics. The first type of linear systems studied here, which are dense, arise from a boundary element type of discretization of crack propagation in brittle material. Numerical experiment show that simple algebraic preconditioning strategies results in iterative schemes that are highly competitive with a direct solution method. The second type of algebraic systems are nonsymmetric and indefinite and arise from finite element discretization of the partial differential equations describing the elastic part of glacial rebound processes. An equal order finite element discretization is analyzed and an optimal stabilization parameter is derived. The indefinite algebraic systems are of 2-by-2-block form, and therefore block preconditioners of block-factorized or block-triangular form are used when solving the indefinite algebraic system. There, the required Schur complement is approximated in various ways and the quality of these approximations is compared numerically. When the block preconditioners are constructed from incomplete fac\-toriza\-tions of the diagonal blocks, the iterative scheme show a growth in iteration count with increasing problem size. This growth is stabilized by replacing the incomplete factors with an inner iterative scheme with a (nearly) optimal order multilevel preconditioner.} } @PhDThesis{ itlic:2005-005, author = {Peter Naucl{\'e}r}, title = {Modeling and Control of Vibration in Mechanical Structures}, school = it, department = syscon, year = 2005, number = {2005-005}, type = {Licentiate thesis}, month = oct, day = {26}, abstract = {All mechanical systems exhibit vibrational response when exposed to external disturbances. In many engineering applications vibrations are undesirable and may even have harmful effects. Therefore, control of mechanical vibration is an important topic and extensive research has been going on in the field over the years. In active control of vibration, the ability to actuate the system in a controlled manner is incorporated into the structure. Sensors are used to measure the vibrations and secondary inputs to the system are used to actuate the flexible body in order to obtain some desired structural response. In this thesis, feedback and feedforward control of active structures are addressed. The thesis is divided into four parts. The first part contains a general introduction to the subject of active vibration control and also provides an outline of the thesis. The second part of the thesis treats modeling and feedback control of a beam system with strain sensors and piezoelectric actuators. Physical modeling and system identification techniques are utilized in order to obtain a low order parametric model that is suitable for controller design. The third part introduces the concept of a mechanical wave diode, which is based on feedforward control. A controller is derived on the basis of equations that describe elastic waves in bars. The obtained controller is shown to have poor noise properties and is therefore modified and further analyzed. The final part of the thesis treats the same type of wave diode system as part three, but with more general feedforward filters. Especially, a controller based on Wiener filter theory is derived and shown to drastically improve the performance of the mechanical wave diode.} } @PhDThesis{ itlic:2005-004, author = {Oskar Wibling}, title = {Ad Hoc Routing Protocol Validation}, school = it, department = docs, year = 2005, number = {2005-004}, type = {Licentiate thesis}, month = sep, day = 23, abstract = {We explore and evaluate methods for validation of ad hoc routing protocols which are used to set up forwarding paths in spontaneous networks of mobile devices. The focus is automatic formal verification but we also make an initial account of a protocol performance comparison using structured live testing. State explosion is a major problem in algorithmic verification of systems with concurrently executing components. We comment on some of the best reduction methods and their applicability to our work. For reactively operating ad hoc routing protocols we provide a broadcast abstraction which enables us to prove correct operation of the Lightweight Underlay Network Ad hoc Routing protocol (LUNAR) in scenarios of realistic size. Our live testing effort has thus far uncovered significant problems in the inter-operation between TCP and ad hoc routing protocols. Severe performance degradation results in networks of just a few nodes when very little mobility is introduced. This indicates that verification for smaller network sizes is also interesting since those configurations may be the only useful ones for certain types of applications.} } @PhDThesis{ itlic:2005-003, author = {Magnus {\AA}gren}, title = {High-Level Modelling and Local Search}, school = it, year = 2005, number = {2005-003}, type = {Licentiate thesis}, month = sep, abstract = {Combinatorial optimisation problems are ubiquitous in our society and appear in such varied guises as DNA sequencing, scheduling, configuration, airline-crew and nurse rostering, combinatorial auctions, vehicle routing, and financial portfolio design. Their efficient solution is crucial to many people and has been the target for much research during the last decades. One successful area of research for solving such problems is constraint programming. Yet, current-generation constraint programming languages are considered by many, especially in industry, to be too low-level, difficult, and large. In this thesis, we argue that solver-independent, high-level relational constraint modelling leads to a simpler and smaller language, to more concise, intuitive, and analysable models, as well as to more efficient and effective model formulation, maintenance, reformulation, and verification. All this can be achieved without sacrificing the possibility of efficient solving, so that even time-pressed modellers can be well assisted. Towards this, we propose the ESRA relational constraint modelling language, showcase its elegance on some real-life problems, and outline a compilation philosophy for such languages. In order to compile high-level languages such as ESRA to current generation constraint programming languages, it is essential that as much support as possible is available in these languages. This is already the case in the constructive search area of constraint programming where, e.g., different kinds of domain variables, such as integer variables and set variables, and expressive global constraints are readily available. However, in the local search area of constraint programming, this is not yet the case and, until now, set variables were for example not available. This thesis introduces set variables and set constraints in the local search area of constraint programming and, by doing this, considerably improves the possibilities for using local search. This is true both for modelling and solving problems using constraint-based local search, as well as for using it as a possible target for the compilation of ESRA models. Indeed, many combinatorial optimisation problems have natural models based on set variables and set constraints, three of which are successfully solved in this thesis. When a new set constraint is introduced in local search, much effort must be spent on the design and implementation of an appropriate incremental penalty function for the constraint. This thesis introduces a scheme that, from a high-level description of a set constraint in existential second-order logic with counting, automatically synthesises an incremental penalty function for that constraint. The performance of this scheme is demonstrated by solving real-life instances of a financial portfolio design problem that seem unsolvable in reasonable time by constructive search.} } @PhDThesis{ itlic:2005-002, author = {H{\aa}kan Zeffer}, title = {Hardware-Software Tradeoffs in Shared-Memory Implementations}, school = it, department = docs, year = 2005, number = {2005-002}, type = {Licentiate thesis}, month = may, abstract = {Shared-memory architectures represent a class of parallel computer systems commonly used in the commercial and technical market. While shared-memory servers typically come in a large variety of configurations and sizes, the advance in semiconductor technology have set the trend towards multiple cores per die and multiple threads per core. Software-based distributed shared-memory proposals were given much attention in the 90s. But their promise of short time to market and low cost could not make up for their unstable performance. Hence, these systems seldom made it to the market. However, with the trend towards chip multiprocessors, multiple hardware threads per core and increased cost of connecting multiple chips together to form large-scale machines, software coherence in one form or another might be a good intra-chip coherence solution. This thesis shows that data locality, software flexibility and minimal processor support for read and write coherence traps can offer good performance, while removing the hard limit of scalability. Our aggressive fine-grained software-only distributed shared-memory system exploits key application properties, such as locality and sharing patterns, to outperform a hardware-only machine on some benchmarks. On average, the software system is 11 percent slower than the hardware system when run on identical node and interconnect hardware. A detailed full-system simulation study of dual core CMPs, with multiple hardware threads per core and minimal processor support for coherence traps is on average one percent slower than its hardware-only counter part when some flexibility is taken into account. Finally, a functional full-system simulation study of an adaptive coherence-batching scheme shows that the number of coherence misses can be reduced with up to 60 percent and bandwidth consumption reduced with up to 22 percent for both commercial and scientific applications.} } @PhDThesis{ itlic:2005-001, author = {Jesper Wilhelmsson}, title = {Efficient Memory Management for Message-Passing Concurrency --- part {I}: Single-threaded execution}, school = it, department = csd, year = 2005, number = {2005-001}, type = {Licentiate thesis}, month = may, abstract = {Manual memory management is error prone. Some of the errors it causes, in particular memory leaks and dangling pointers, are hard to find. Manual memory management becomes even harder when concurrency enters the picture. It therefore gets more and more important to overcome the problems of manual memory management in concurrent software as the interest in these applications increases with the development of new, multi-threaded, hardware. To ease the implementation of concurrent software many programming languages these days come with automatic memory management and support for concurrency. This support, called the concurrency model of the language, comes in many flavors (shared data structures, message passing, etc.). The performance and scalability of applications implemented using such programming languages depends on the concurrency model, the memory architecture, and the memory manager used by the language. It is therefore important to investigate how different memory architectures and memory management schemes affect the implementation of concurrent software and what performance tradeoffs are involved. This thesis investigates ways of efficiently implementing the memory architecture and memory manager in a concurrent programming language. The concurrency model which we explore is based on message passing with copying semantics. We start by presenting the implementation of three different memory architectures for concurrent software and give a detailed characterization of their pros and cons regarding message passing and efficiency in terms of memory management. The issue examined is whether to use private memory for all processes in a program or if there may be benefits in sharing all or parts of the memory. In one of the architectures looked at, called hybrid, a static analysis called message analysis is used to guide the allocation of message data. Because the hybrid architecture is the enabling technology for a scalable multi-threaded implementation, we then focus on the hybrid architecture and investigate how to manage the memory using different garbage collection techniques. We present pros and cons of these techniques and discuss their characteristics and their performance in concurrent applications. Finally our experiences from turning the garbage collector incremental are presented. The effectiveness of the incremental collector is compared to the non-incremental version. On a wide range of benchmarks, the incremental collector we present is able to sustain high mutator utilization (about 80\% during collection cycles) at a low cost. This work is implemented in an industrial-strength implementation of the concurrent functional programming language Erlang. Our eventual goal is to use the hybrid architecture and the incremental garbage collector as the basis for an efficient multi-threaded implementation of Erlang. The work described in this thesis is a big step in that direction.} } @PhDThesis{ itlic:2004-006, author = {Stefan Johansson}, title = {High Order Difference Approximations for the Linearized Euler Equations}, school = it, department = tdb, year = 2004, number = {2004-006}, type = {Licentiate thesis}, month = dec, abstract = {The computers of today make it possible to do direct simulation of aeroacoustics, which is very computational demanding since a very high resolution is needed. In the present thesis we study issues of relevance for aeroacoustic simulations. Paper A considers standard high order difference methods. We study two different ways to apply boundary conditions in a stable way. Numerical experiments are done for the 1D linearized Euler equations. In paper B we develop difference methods which give smaller dispersion errors than standard central difference methods. The new methods are applied to the 1D wave equation. Finally in Paper C we apply the new difference methods to aeroacoustic simulations based on the 2D linearized Euler equations. Taken together, the methods presented here lead to better approximation of the wave number, which in turn results in a smaller L2-error than obtained by previous methods found in the literature. The results are valid when the problem is not fully resolved, which usually is the case for large scale applications.} } @PhDThesis{ itlic:2004-005, author = {Henrik L{\"o}f}, title = {Parallelizing the Method of Conjugate Gradients for Shared Memory Architectures}, school = it, year = 2004, number = {2004-005}, type = {Licentiate thesis}, month = nov, abstract = {Solving Partial Differential Equations (PDEs) is an important problem in many fields of science and engineering. For most real-world problems modeled by PDEs, we can only approximate the solution using numerical methods. Many of these numerical methods result in very large systems of linear equations. A common way of solving these systems is to use an iterative solver such as the method of conjugate gradients. Furthermore, due to the size of these systems we often need parallel computers to be able to solve them in a reasonable amount of time. Shared memory architectures represent a class of parallel computer systems commonly used both in commercial applications and in scientific computing. To be able to provide cost-efficient computing solutions, shared memory architectures come in a large variety of configurations and sizes. From a programming point of view, we do not want to spend a lot of effort optimizing an application for a specific computer architecture. We want to find methods and principles of optimizing our programs that are generally applicable to a large class of architectures. In this thesis, we investigate how to implement the method of conjugate gradients efficiently on shared memory architectures. We seek algorithmic optimizations that result in efficient programs for a variety of architectures. To study this problem, we have implemented the method of conjugate gradients using OpenMP and we have measured the runtime performance of this solver on a variety of both uniform and non-uniform shared memory architectures. The input data used in the experiments come from a Finite-Element discretization of the Maxwell equations in three dimensions of a fighter-jet geometry. Our results show that, for all architectures studied, optimizations targeting the memory hierarchy exhibited the largest performance increase. Improving the load balance, by balancing the arithmetical work and minimizing the number of global barriers showed to be of lesser importance. Overall, \emph{bandwidth minimization} of the iteration matrix showed to be the most efficient optimization. On non-uniform architectures, proper data distribution showed to be very important. In our experiments we used page migration to improve the data distribution during runtime. Our results indicate that page migration can be very efficient if we can keep the migration cost low. Furthermore, we believe that page migration can be introduced in a portable way into OpenMP in the form of a directive with a \emph{affinity-on-next-touch} semantic.} } @PhDThesis{ itlic:2004-004, author = {El Shobaki, Mohammed}, title = {On-Chip Monitoring for Non-Intrusive Hardware/Software Observability}, school = it, year = 2004, number = {2004-004}, type = {Licentiate thesis}, month = sep, abstract = {The increased complexity in today s state-of-the-art computer systems make them hard to analyse, test, and debug. Moreover, the advances in hardware technology give system designers enormous possibilities to explore hardware as a means to implement performance demanding functionality. We see examples of this trend in novel microprocessors, and Systems-on-Chip, that comprise reconfigurable logic allowing for hardware/software co-design. To succeed in developing computer systems based on these premises, it is paramount to have efficient design tools and methods. An important aspect in the development process is observability, i.e., the ability to observe the system s behaviour at various levels of detail. These observations are required for many applications: when looking for design errors, during debugging, during performance assessments and fine-tuning of algorithms, for extraction of design data, and a lot more. In real-time systems, and computers that allow for concurrent process execution, the observability must be obtained without compromising the system s functional and timing behaviour. In this thesis we propose a monitoring system that can be used for nonintrusive run-time observations of real-time and concurrent computer systems. The monitoring system, designated Multipurpose/Multiprocessor Application Monitor (MAMon), is based on a hardware probe unit (IPU) which is integrated with the observed system s hardware. The IPU collects process-level events from a hardware Real-Time Kernel (RTK), without perturbing the system, and transfers the events to an external computer for analysis, debugging, and visualisation. Moreover, the MAMon concept also features hybrid monitoring for collection of more fine-grained information, such as program instructions and data flows. We describe MAMon s architecture, the implementation of two hardware prototypes, and validation of the prototypes in different case-studies. The main conclusion is that process level events can be traced non-intrusively by integrating the IPU with a hardware RTK. Furthermore, the IPU s small footprint makes it attractive for SoC designs, as it provides increased system observability at a low hardware cost. } } @PhDThesis{ itlic:2004-003, author = {Yngve Sel{\'e}n}, title = {Model Selection}, school = it, year = {2004}, number = {2004-003}, type = {Licentiate thesis}, month = oct, abstract = {Before using a parametric model one has to be sure that it offers a reasonable description of the system to be modeled. If a bad model structure is employed, the obtained model will also be bad, no matter how good is the parameter estimation method. There exist many possible ways of validating candidate models. This thesis focuses on one of the most common ways, i.e., the use of information criteria. First, some common information criteria are presented, and in the later chapters, various extentions and implementations are shown. An important extention, which is advocated in the thesis, is the multi-model (or model averaging) approach to model selection. This multi-model approach consists of forming a weighted sum of several candidate models, which then can be used for inference.} } @PhDThesis{ itlic:2004-002, author = {Markus Nord{\'e}n}, title = {Parallel {PDE} Solvers on cc-{NUMA} Systems}, school = it, department = tdb, year = 2004, number = {2004-002}, type = {Licentiate thesis}, month = mar, note = {Included papers are available at: Paper A: \url{http://www.sciencedirect.com/science/article/B6V06-49W6S4M-1/2/23cb25585b2742595f319f4cedd0b65f}, Paper C: \url{http://www.it.uu.se/research/publications/lic/2004-002/2004-002-C.pdf}, Paper D: \url{http://www.it.uu.se/research/publications/reports/2004-006}} , abstract = {The current trend in parallel computers is that systems with a large shared memory are becoming more and more popular. A shared memory system can be either a uniform memory architecture (UMA) or a cache coherent non-uniform memory architecture (cc-NUMA). In the present thesis, the performance of parallel PDE solvers on cc-NUMA computers is studied. In particular, we consider the shared namespace programming model, represented by OpenMP. Since the main memory is physically, or \emph{geographically} distributed over several multi-processor nodes, the latency for local memory accesses is smaller than for remote accesses. Therefore, the \emph{geographical locality} of the data becomes important. The questions posed in this thesis are: (1)~How large is the influence on performance of the non-uniformity of the memory system? (2)~How should a program be written in order to reduce this influence? (3)~Is it possible to introduce optimizations in the computer system for this purpose? Most of the application codes studied address the Euler equations using a finite difference method and a finite volume method respectively and are parallelized with OpenMP. Comparisons are made with an alternative implementation using MPI and with PDE solvers implemented with OpenMP that solve other equations using different numerical methods. The main conclusion is that geographical locality is important for performance on cc-NUMA systems. This can be achieved through self optimization provided in the system or through migrate-on-next-touch directives that could be inserted automatically by the compiler. We also conclude that OpenMP is competitive with MPI on cc-NUMA systems if care is taken to get a favourable data distribution. } } @PhDThesis{ itlic:2004-001, author = {Niclas Sandgren}, title = {Parametric Methods for Frequency-Selective {MR} Spectroscopy}, school = it, department = syscon, year = 2004, number = {2004-001}, type = {Licentiate thesis}, month = mar, abstract = {Accurate and efficient quantitation of the data components in magnetic resonance spectroscopy (MRS) signals can be an important step in the analysis of biochemical substances. In several practical applications of MR spectroscopy the user is interested only in the data components lying in a small frequency band of the spectrum. A frequency-selective, or sub-band, analysis deals precisely with this kind of spectroscopy: estimation of only those spectroscopic components that lie in a selected frequency band of the (MR) data spectrum, with as little interference as possible from the out-of-band components and in a computationally efficient way. One obvious application for such a sub-band technique is to lower the computational burden in situations when the measured data sequence contains too many samples to be processed using a standard full-spectrum method. This thesis deals with several parametric methods to perform a frequency-selective data analysis. In addition, the possibility to incorporate prior knowledge about some of the components in the data is considered, a procedure that generally increases the parameter estimation performance significantly. A data model of exponentially damped sinusoids is assumed for the presented methods, which are applied to both simulated and experimental (in-vitro) MR data. Keywords: frequency-selective spectroscopy; frequency-domain data processing; sub-band analysis; SVD-based parameter estimation; damped sinusoidal model.} } @PhDThesis{ itlic:2003-015, author = {Erik Berg}, title = {Methods for Run Time Analysis of Data Locality}, school = it, department = docs, year = 2003, number = {2003-015}, type = {Licentiate thesis}, month = dec, abstract = {The growing gap between processor clock speed and DRAM access time puts new demands on software and development tools. Deep memory hierarchies and high cache miss penalties in present and emerging computer systems make execution time sensitive to data locality. Therefore, developers of performance-critical applications and optimizing compilers must be aware of data locality and maximize cache utilization to produce fast code. To aid the optimization process and help understanding data locality, we need methods to analyze programs and pinpoint poor cache utilization and possible optimization opportunities. Current methods for run-time analysis of data locality and cache behavior include functional cache simulation, often combined with set sampling or time sampling, other regularity metrics based on strides and data streams, and hardware monitoring. However, they all share the trade-off between run-time overhead, accuracy and explanatory power. This thesis presents methods to efficiently analyze data locality at run time based on cache modeling. It suggests source- interdependence profiling as a technique for examining the cache behavior of applications and locating source code statements and/or data structures that cause poor cache utilization. The thesis also introduces a novel statistical cache-modeling technique, StatCache. Rather than implementing a functional cache simulator, StatCache estimates the miss ratios of fully-associative caches using probability theory. A major advantage of the method is that the miss ratio estimates can be based on very sparse sampling. Further, a single run of an application is enough to estimate the miss ratio of caches of arbitrary sizes and line sizes and to study both spatial and temporal data locality.} } @PhDThesis{ itlic:2003-014, author = {Kajsa Ljungberg}, title = {Numerical Methods for Mapping of Multiple {QTL}}, school = it, department = tdb, year = 2003, number = {2003-014}, type = {Licentiate thesis}, month = nov, abstract = {This thesis concerns numerical methods for mapping of multiple quantitative trait loci, QTL. Interactions between multiple genetic loci influencing important traits, such as growth rate in farm animals and predisposition to cancer in humans, make it necessary to search for several QTL simultaneously. Simultaneous search for $n$ QTL involves solving an $n$-dimensional global optimization problem, where each evaluation of the objective function consists of solving a generalized least squares problem. In Paper A we present efficient algorithms, mainly based on updated QR factorizations, for evaluating the objective functions of different parametric QTL mapping methods. One of these algorithms reduces the computational work required for an important function class by one order of magnitude compared with the best of the methods used by other authors. In Paper B previously utilized techniques for finding the global optimum of the objective function are compared with a new approach based on the DIRECT algorithm of Jones et al. The new method gives accurate results in one order of magnitude less time than the best of the formerly employed algorithms. Using the algorithms presented in Papers A and B, simultaneous search for at least three QTL, including computation of the relevant empirical significance thresholds, can be performed routinely.} } @PhDThesis{ itlic:2003-013, author = {Stina Nylander}, title = {The Ubiquitous Interactor - Mobile Services with Multiple User Interfaces}, school = it, department = hci, year = 2003, number = {2003-013}, type = {Licentiate thesis}, abstract = {This licentiate thesis addresses design and development problems that arise when service providers, and service end-users face the variety of computing devices available on the market. The devices are designed for many types of use in various situations and settings, which means that they have different capabilities in terms of presentation, interaction, memory, etc. Service providers often handle these differences by creating a new version for each device. This creates a lot of development and maintenance work, and often leads to restrictions on the set of devices that services are developed for. For service end-users, this means that it can be difficult to combine devices that fit the intended usage context and services that provide the needed content. New development methods that target multiple devices from the start are needed. The differences between devices call for services that can adapt to various devices, and present themselves with device specific user interfaces. We propose a way of developing device independent services by using interaction acts to describe user-service interaction. Devices would interpret the interaction acts and generate user interfaces according to their own specific capabilities. Additional presentation information can be encoded in customization forms, to further control how the user interface would be generated. Different devices would generate different user interfaces from the same interaction acts, and a device could generate different user interfaces from the same interaction acts combined with different customization forms. In this thesis, the interaction act and customization form concepts are described in detail. A system prototype handling them and two sample services have been implemented. Preliminary evaluations indicate that interaction acts and customization forms constitute a feasible approach for developing services with multiple user interfaces. The thesis concludes with a discussion of the problems arising when evaluating this kind of systems, and some conclusions on how to continue the evaluation process.} } @PhDThesis{ itlic:2003-012, author = {Olivier Amoignon}, title = {Adjoint-Based Aerodynamic Shape Optimization}, school = it, department = tdb, year = 2003, number = {2003-012}, type = {Licentiate thesis}, month = oct, note = {In the first printed version, many references to the bibliography are off by one. The online version does not have this error}, abstract = {An adjoint system of the Euler equations of gas dynamics is derived in order to solve aerodynamic shape optimization problems with gradient-based methods. The derivation is based on the fully discrete flow model and involves differentiation and transposition of the system of equations obtained by an unstructured and node-centered finite-volume discretization. Solving the adjoint equations allows an efficient calculation of gradients, also when the subject of optimization is described by hundreds or thousands of design parameters. Such a fine geometry description may cause wavy or otherwise irregular designs during the optimization process. Using the one-to-one mapping defined by a Poisson problem is a known technique that produces smooth design updates while keeping a fine resolution of the geometry. This technique is extended here to combine the smoothing effect with constraints on the geometry, by defining the design updates as solutions of a quadratic programming problem associated with the Poisson problem. These methods are applied to airfoil shape optimization for reduction of the wave drag, that is, the drag caused by gas dynamic effects that occur close to the speed of sound. A second application concerns airfoil design optimization to delay the laminar-to-turbulent transition point in the boundary layer in order to reduce the drag. The latter application has been performed by the author with collaborators, also using gradient-based optimization. Here, the growth of convectively unstable disturbances are modeled by successively solving the Euler equations, the boundary layer equations, and the parabolized stability equations.} } @PhDThesis{ itlic:2003-011, author = {Tobias Amnell}, title = {Code Synthesis for Timed Automata}, school = it, department = docs, year = 2003, number = {2003-011}, type = {Licentiate thesis}, month = oct, abstract = {In this thesis, we study executable behaviours of timed models. The focus is on synthesis of executable code with predictable behaviours from high level abstract models. We assume that a timed system consists of two parts: the control software and the plant (i.e. the environment to be controlled). Both are modelled as timed automata extended with real time tasks. We consider the extended timed automata as design models. We present a compilation procedure to transform design models to executable code including a run-time scheduler (run time system) preserving the correctness and schedulability of the models. The compilation procedure has been implemented in a prototype C-code generator for the brickOS operating system included in the Times tool. We also present an animator, based on hybrid automata, to be used to describe a simulated environment (i.e. the plant) for timed systems. The tasks of the hybrid automata define differential equations and the animator uses a differential equations solver to calculate step-wise approximations of real valued variables. The animated objects, described as hybrid automata, are compiled by the Times tool into executable code using a similar procedure as for controller software. To demonstrate the applicability of timed automata with tasks as a design language we have developed the control software for a production cell. The production cell is built in LEGO and is controlled by a Hitachi H8 based LEGO-Mindstorms control brick. The control software has been analysed (using the Times tool) for schedulability and other safety properties. Using results from the analysis we were able to avoid generating code for parts of the design that could never be reached, and could also limit the amount of memory allocated for the task queue.} } @PhDThesis{ itlic:2003-010, author = {Dan Wallin}, title = {Exploiting Data Locality in Adaptive Architectures}, school = it, department = docs, year = 2003, number = {2003-010}, type = {Licentiate thesis}, month = sep, abstract = {The speed of processors increases much faster than the memory access time. This makes memory accesses expensive. To meet this problem, cache hierarchies are introduced to serve the processor with data. However, the effectiveness of caches depends on the amount of locality in the application's memory access pattern. The behavior of various programs differs greatly in terms of cache miss characteristics, access patterns and communication intensity. Therefore a computer built for many different computational tasks potentially benefits from dynamically adapting to the varying needs of the applications. This thesis shows that a cc-NUMA multiprocessor with data migration and replication optimizations efficiently exploits the temporal locality of algorithms. The performance of the self-optimizing system is similar to a system with a perfect initial thread and data placement. Data locality optimizations are not for free. Large cache line coherence protocols improve spatial locality but yield increases in false sharing misses for many applications. Prefetching techniques that reduce the cache misses often lead to increased address and data traffic. Several techniques introduced in this thesis efficiently avoid these drawbacks. The bundling technique reduces the coherence traffic in multiprocessor prefetchers. This is especially important in snoop-based systems where the coherence bandwidth is a scarce resource. Bundled prefetchers manage to reduce both the cache miss rate and the coherence traffic compared with non-prefetching protocols. The most efficient bundled prefetching protocol studied, lowers the cache misses by 27 percent and the address snoops by 24 percent relative to a non-prefetching protocol on average for all examined applications. Another proposed technique, capacity prefetching, avoids false sharing misses by distinguishing between cache lines involved in communication from non-communicating cache lines at run-time.} } @PhDThesis{ itlic:2003-009, author = {Martin Karlsson}, title = {Cache Memory Design Trade-offs for Current and Emerging Workloads}, school = it, department = docs, year = 2003, number = {2003-009}, type = {Licentiate thesis}, month = sep, abstract = {The memory system is the key to performance in contemporary computer systems. When designing a new memory system, architectural decisions are often arbitrated based on their expected performance effect. It is therefore very important to make performance estimates based on workloads that accurately reflect the future use of the system. This thesis presents the first memory system characterization study of Java-based middleware, which is an emerging workload likely to be an important design consideration for next generation processors and servers. Manufacturing technology has reached a point where it is now possible to fit multiple full-scale processors and integrate board-level features on a chip. The raised competition for chip resources has increased the need to design more effective caches without trading off area or power. Two common ways to improve cache performance is to increase the size or associativity of the cache. Both of these approaches come at a high cost in chip area as well as power. This thesis presents two new cache organizations, each aimed at more efficient use of either power or area. First, the Elbow cache is presented, which is shown to be a power-efficient alternative to highly set-associative caches. Secondly, a selective cache allocation algorithm is presented, RASCAL, that significantly reduces the miss ratio at a limited cost in area.} } @PhDThesis{ itlic:2003-008, author = {Zoran Radovic}, title = {Efficient Synchronization and Coherence for Nonuniform Communication Architectures}, school = it, department = docs, year = 2003, number = {2003-008}, type = {Licentiate thesis}, month = sep, abstract = {Nonuniformity is a common characteristic of contemporary computer systems, mainly because of physical distances in computer designs. In large multiprocessors, the access to shared memory is often nonuniform, and may vary as much as ten times for some nonuniform memory access (NUMA) architectures, depending on if the memory is close to the requesting processor or not. Much research has been devoted to optimizing such systems. This thesis identifies another important property of computer designs, nonuniform communication architecture (NUCA). High-end hardware-coherent machines built from a few large nodes or from chip multiprocessors, are typical NUCA systems that have a lower penalty for reading recently written data from a neighbor's cache than from a remote cache. The first part of the thesis identifies node affinity as an important property for scalable general-purpose locks. Several software-based hierarchical lock implementations that exploit NUCAs are presented and investigated. This type of lock is shown to be almost twice as fast for contended locks compared with other software-based lock implementations, without introducing significant overhead for uncontested locks. Physical distance in very large systems also limits hardware coherence to a subsection of the system. Software implementations of distributed shared memory (DSM) are cost-effective solutions that extend the upper scalability limit of such machines by providing the ``illusion'' of shared memory across the entire system. This also creates NUCAs with even larger local-remote penalties, since the coherence is maintained entirely in software. The major source of inefficiency for traditional software DSM implementations comes from the cost of interrupt-based asynchronous protocol processing, not from the actual network latency. As the raw hardware latency of internode communication decreases, the asynchronous overhead in the communication becomes more dominant. This thesis introduces the DSZOOM system that removes this type of overhead by running the entire coherence protocol in the requesting processor.} } @PhDThesis{ itlic:2003-007, author = {Maria Karlsson}, title = {Market Based Programming and Resource Allocation}, school = it, department = csd, year = 2003, number = {2003-007}, type = {Licentiate thesis}, month = jun, abstract = {The subject of this thesis is the concept of market-oriented programming and market protocols. We want to solve an allocation problem where some resources are to be divided among a number of agents. Each agent has a utility function telling how much the current allocation is worth for it. The goal is to allocate the resources among the agents in a way that maximizes the sum of the utilities of all agents. To solve this problem we use the concept of markets to create mechanisms for computational implementation. To achieve the advantages of market oriented programming, we have to consider the conceptual view of the problem a main design issue. We want to investigate the possibilities to build computationally effective mechanisms which maintain the intuitive, easy-to-understand structure of market-based approaches. In the first paper we look at two examples from the literature and show that conceptual improvements of the approaches will make agent behavior more realistic. This will also make the examples fit into a more general theory. In the second paper we create a market mechanism for handling combinatorial markets. The mechanism includes an auction, where each iteration runs in polynomial time. The mechanism shows good performance when the number of resources is relatively small compared to the number of agents. } } @PhDThesis{ itlic:2003-006, author = {Tomas Olsson}, title = {Bootstrapping and Decentralizing Recommender Systems}, school = it, department = csd, year = 2003, number = {2003-006}, type = {Licentiate thesis}, month = jun, abstract = {This thesis consists of three papers on recommender systems. The first paper addresses the problem of making decentralized recommendations using a peer-to-peer architecture. Collaborating recommender agents are connected into a network of neighbors that exchange user recommendations to find new items to recommend. We achieved a performance comparable to a centralized system. The second paper deals with the bootstrapping problem for centralized recommender systems. Most recommender systems learn from experience but initially there are no users and no rated items to learn from. To deal with this problem we have developed the Genesis method. The method bootstraps a recommender system with artificial user profiles sampled from a probabilistic model built from prior knowledge. The paper describes how this was done for a k- nearest neighbor recommender algorithm in the movie domain. We were able to improve the performance of a k-nearest neighbor algorithm for single predictions but not for rank ordered lists of recommendations. The third paper identifies a new domain for recommendations -- product configuration -- where new recommender algorithms are needed. A system that helps users configuring their own PCs is described. Recommendations and a cluster-based help system together with a rule-based configurator assist the users in selecting appropriate features or complete PC configurations. The configurator ensures that users cannot choose incompatible components while the recommender system adds social information based on what other users have chosen. This introduces new complexity in the recommendation process on how to combine the recommendations from the configurator and the recommender system. The paper proposes (1) three new recommender algorithms on how to make recommendations in the domain of product configuration, (2) a method for adding social recommendations to a rule-based configurator and (3) a method for applying the Genesis method in this domain. In this case the Genesis method is implemented by a Bayesian belief net that captures the designers' prior knowledge on how to configure PCs. Then instances of complete configurations are sampled from the model and added to the recommender algorithm. } } @PhDThesis{ itlic:2003-005, author = {Mats Ekman}, title = {Urban Water Management - Modelling, Simulation and Control of the Activated Sludge Process}, school = it, department = syscon, year = 2003, number = {2003-005}, type = {Licentiate thesis}, month = may, note = {Errata (updated Jan 2004) available at \url{http://www.it.uu.se/research/publications/lic/2003-005/Errata.pdf} and \url{http://www.it.uu.se/research/publications/lic/2003-005/Errata.ps.gz}} , abstract = {During the last few decades, wastewater treatment processes in urban water management have become more and more efficient and complex. Several factors such as urbanization, stricter legislations on effluent quality, economics, increased knowledge of the involved biological, chemical and physical processes as well as technical achievements have been important incentives for the development of more efficient procedures for wastewater treatment plants. Future requirements on more sustainable urban water systems, in combination with increasing wastewater loads, will most probably further increase the need for optimization and control of both existing and emerging wastewater treatment processes. In this thesis estimation, modelling and control strategies are developed in order to improve the efficiency of the activated sludge process. The first part of the thesis presents a JAVA based simulator of the activated sludge process. An overview of its features, with some emphasis on implemented control strategies, is given. In particular, a new control strategy for the internal recycling flow rate is described. A summary of experiences from using the simulator as a teaching and training tool is also given. The second part of the thesis includes a derivation of reduced order models for the activated sludge process. The resulting models, a time-varying linear state-space model for the anoxic part and a time-varying bilinear state-space model for the aerobic part, are intended to be used for control applications. In the third part, an adaptive control strategy for control of the nitrate level using an external carbon source is presented. The controller adapts and compensates for changes in the system dynamics since important system parameters are estimated adaptively and incorporated on-line in the control design. The estimated system parameters and model states also give guidance about the state of the process and the characteristics of the wastewater. Several simulation examples are used to illustrate the control law. Finally, a new suboptimal control law for the bilinear quadratic regulator problem with infinite final time is presented. The control strategy is evaluated in a simulation study, where special concern is devoted to controlling the activated sludge process, using the bilinear model developed in the second part of this thesis. } } @PhDThesis{ itlic:2003-004, author = {Malin Ljungberg}, title = {Handling of Curvilinear Coordinates in a {PDE} Solver Framework}, school = it, department = tdb, year = 2003, number = {2003-004}, type = {Licentiate thesis}, month = may, abstract = {By the use of object-oriented analysis and design combined with variability modeling a highly flexible software model for the metrics handling functionality of a PDE solver framework was obtained. This new model was evaluated in terms of usability, particularly with respect to efficiency and flexibility. The efficiency of a pilot implementation is similar to, or even higher than that of a pre-existing application-specific reference code. With regards to flexibility it is shown that the new software model performs well for a set of four change scenarios selected by an expert user group.} } @PhDThesis{ itlic:2003-003, author = {Inger Boivie}, title = {Usability and Users' Health Issues in Systems Development}, school = it, department = hci, year = 2003, number = {2003-003}, type = {Licentiate thesis}, month = mar, abstract = {The figures of reported health problems in computer-supported, administrative, work are alarmingly high and increasing. The main health problems are visual discomfort, repetitive strain injuries (RSI) and stress-related disorders. Some important risk factors are poor workstation design, constrained work postures, repetitive work and long hours of computer use every day. Others are high demands, poor control over workload and work pace and poor relations to management and colleagues. There is also evidence that poor design and usability of the computer systems as well as technical problems with the computer add to the pressure perceived by the user, which may in its turn cause stress-related disorders. Systems (software) development is often technology-driven and the design and contents of the resulting system shapes the work situation, including factors affecting the users' health and well-being. There are numerous examples in the literature describing how poorly designed systems fail to support the real work practices, introducing new ones that are inadequate and more time-consuming. Thus these, supposedly supporting, computer systems get in the way of efficient and effective work, adding a burden on the workers rather than helping them out. This thesis tries to describe some of the relations between the systems development process and users' health complaints, in a work context. I also discuss whether or not the concepts of usability and user experience can be used to address users' health issues in the systems development process. The main results indicate that although usability must be addressed, it is not sufficient. Occupational health issues must be explicitly integrated in systems development, and be given priority. This thesis also describes some potential methods and techniques for doing that. } } @PhDThesis{ itlic:2003-002, author = {Jenny Persson}, title = {Basic Values in Software Development and Organizational Change}, school = it, department = hci, year = 2003, number = {2003-002}, type = {Licentiate thesis}, month = mar, abstract = {This thesis is to be seen as a preliminary version of my doctoral thesis. It deals with problems concerning how our basic values influence development processes, mainly within the areas of software development and organizational change. Two main foci are presented, one theoretical and one empirical. The theoretical focus deals with the question: Is there objectivity in the theoretical framework, the knowledge and the experience on which the choices of strategies are based? The empirical focus deals with the question: How can knowledge about healthy work, usability and organizational matters be put into practice in the organizational and software development process? The preliminary conclusion shows that, when put under pressure, basic values are often clearly evident, though not necessarily evident to the individual herself. The will to grasp at models or methods that follow contemporary trends increases as well. In the end, time and money control the process, and all the magnificent ideas of a system built for a better work environment have soon faded away. This loss reflects the basic values in the organization, as well as it reflects a lack of awareness of the consequences of different strategic decisions. Key Words: Basic Values, Management, Organizational Change, Metaphors, Organizational Learning, Systems Development, Computer Ethics, Occupational Health, Work Environment, Usability} } @PhDThesis{ itlic:2003-001, author = {Per Sundqvist}, title = {Preconditioners and Fundamental Solutions}, school = it, department = tdb, year = 2003, number = {2003-001}, type = {Licentiate thesis}, month = mar, abstract = {New preconditioning techniques for the iterative solution of systems of equations arising from discretizations of partial differential equations are considered. Fundamental solutions, both of differential and difference operators, are used as kernels in discrete, truncated convolution operators. The intention is to approximate inverses of difference operators that arise when discretizing the differential equations. The approximate inverses are used as preconditioners. The technique using fundamental solutions of differential operators is applied to scalar problems in two dimensions, and grid independent convergence is obtained for a first order differential equation. The problem of computing fundamental solutions of difference operators is considered, and we propose a new algorithm. It can be used also when the symbol of the difference operator is not invertible everywhere, and it is applicable in two or more dimensions. Fundamental solutions of difference operators are used to construct preconditioners for non-linear systems of difference equations in two dimensions. Grid independent convergence is observed for two standard finite difference discretizations of the Euler equations in a non-axisymmetric duct.} } @PhDThesis{ itlic:2002-008, author = {Henrik Lundgren}, title = {Implementation and Real-world Evaluation of Routing Protocols for Wireless Ad hoc Networks}, school = it, year = 2002, number = {2002-008}, type = {Licentiate thesis}, month = nov, abstract = {A wireless ad hoc network consists of a number of mobile nodes that temporarily form a dynamic infrastructure-less network. To enable communication between nodes that do not have direct radio contact, each node must function as a wireless router and potentially forward data traffic on behalf of the others. New routing protocols are needed as the existing protocols used in wired networks adapt too slowly to the frequent topology changes induced by mobility and are inefficient in terms of resource consumption. During the last five to ten years more than 60 different ad hoc routing protocols have been proposed, optimized and partially compared based on simulation studies. However, we believe that these simulation studies need to be complemented with real-world experiments in order to gain practical experience and reveal real-world effects that may not be visible in simulations. This thesis surveys the field of ad hoc routing and related real-world testbeds. We also describe our research results from three included papers: In our active networking approach to ad hoc routing, protocol logic is carried inside data packets, which enables new protocols to be independently deployed at run-time. As a proof of concept, we have implemented two ad hoc routing protocols and successfully used them for routing a real-time sensitive audio stream. This prototype gave us a good understanding of the practical aspects of wireless networking and prepared good ground for protocol comparisons. We have implemented a testbed called APE which enables easy management and analysis of real-world experiments. In real-world experiments, with up to 37 mobile nodes, we used the APE testbed to assess the reproducibility between repeated testruns and compared three different routing protocols. This testbed has become a crucial tool for discovering flaws in proposed protocols, as well as for benchmarking different routing styles. During our implementation of the AODV protocol we discovered a performance problem that we could relate to some invalid assumptions about the wireless link characteristics. We explored this `communication gray zone' problem and implemented three countermeasures which we compared by using the APE testbed. As a result we could eliminate the performance discrepancy between simulated AODV and its implementation in the real-world.} } @PhDThesis{ itlic:2002-007, author = {Samuel Sundberg}, title = {Semi-Toeplitz Preconditioning for Linearized Boundary Layer Problems}, school = it, department = tdb, year = 2002, number = {2002-007}, type = {Licentiate thesis}, month = nov, note = {Included papers available at \url{http://www.it.uu.se/research/publications/lic/2002-007/2002-007-paperA.pdf}, \url{http://www.it.uu.se/research/publications/lic/2002-007/2002-007-paperA.ps.gz}, \url{http://www.it.uu.se/research/publications/lic/2002-007/2002-007-paperB.ps.gz}, and \url{http://www.it.uu.se/research/publications/lic/2002-007/2002-007-paperB.pdf}} , abstract = {We have defined and analyzed a semi-Toeplitz preconditioner for time-dependent and steady-state convection-diffusion problems. Analytic expressions for the eigenvalues of the preconditioned systems are obtained. An asymptotic analysis shows that the eigenvalue spectrum of the time-dependent problem is reduced to two eigenvalues when the number of grid points go to infinity. The numerical experiments sustain the results of the theoretical analysis, and the preconditioner exhibits a robust behavior for stretched grids. A semi-Toeplitz preconditioner for the linearized Navier--Stokes equations for compressible flow is proposed and tested. The preconditioner is applied to the linear system of equations to be solved in each time step of an implicit method. The equations are solved with flat plate boundary conditions and are linearized around the Blasius solution. The grids are stretched in the normal direction to the plate and the quotient between the time step and the space step is varied. The preconditioner works well in all tested cases and outperforms the method without preconditioning both in number of iterations and execution time.} } @PhDThesis{ itlic:2002-006, author = {Kalyani Munasinghe}, title = {On Using Mobile Agents for Load Balancing in High Performance Computing}, school = it, department = tdb, year = 2002, number = {2002-006}, type = {Licentiate thesis}, month = jun, abstract = {One recent advance in software technology is the development of software agents that can adapt to changes in their environment and can cooperate and coordinate their activities to complete a given task. Such agents can be distributed over a network. Advances in hardware technology have meant that clusters of workstations can be used to create parallel virtual machines that bring the power of parallel computing to a much wider research and development community. Many software packages are now being developed to utilise such cluster environments. In a cluster, each processor will be multitasking and running other jobs simultaneously with a distributed application that uses a message passing environment such as MPI. A typical application might be a large scale mesh-based computation, such as a finite element code, in which load balancing is equivalent to mesh partitioning. When the load is varying between processors within the cluster, distributing the computation in equal amounts may not deliver the optimum performance. Some machines may be very heavily loaded by other users while other processors may have no such additional load. It may be beneficial to measure current system information and use this information when balancing the load within a single distributed application program. This thesis presents one approach to distributing workload more efficiently in a multi-user distributed environment by using mobile agents to collect system information which is then transmitted to all the MPI tasks. The thesis contains a review of software agents and mesh partitioning together with some numerical experiments and a paper. } } @PhDThesis{ itlic:2002-005, author = {Kaushik Mahata}, title = {Identification of Dynamic Errors-in-Variables Models}, school = it, department = syscon, year = 2002, number = {2002-005}, type = {Licentiate thesis}, month = may, abstract = {The problem of identifying dynamic errors-in-variables models is of fundamental interest in many areas like process control, array signal processing, astronomical data reduction. In recent years, this field has received increased attention of the research community. In this thesis, some time domain and frequency domain approaches for identifying the errors-in-variables model is studied. The first chapter gives an overview of various methods for identifying dynamic errors-in-variables systems. Several approaches are classified and a qualitative comparison of different existing methods is also presented. The second chapter deals with instrumental variables based approaches. The least squares and the total least squares methods of solving the Yule-Walker equation is of central interest here. The methods are compared from the view point of asymptotic performance, numerical robustness and computation. The method presented in the third chapter uses prefiltered data. The input-output data is passed through a pair of user defined prefilters and the output data from the prefilters is subjected to a least-squares like algorithm. Compared to the IV approach, the proposed method shows a significant improvement in the small-sample properties of the MA parameter estimates, without any increase in the computational load. In the fourth chapter, we show that the two-dimensional process composed of the input-output data admits a finite order ARMA representation. Then we propose a parametric identification algorithm and another non-parametric identification method based on the ARMA representation. } } @PhDThesis{ itlic:2002-004, author = {Martin Nilsson}, title = {Iterative Solution of Maxwell's Equations in Frequency Domain}, school = it, department = tdb, year = 2002, number = {2002-004}, type = {Licentiate thesis}, month = jun, abstract = {We have developed an iterative solver for the Moment Method. It computes a matrix vector product with the multilevel Fast Multipole Method, which makes the method scale with the number of unknowns. The iterative solver is of Block Quasi-Minimum Residual type and can handle several right hand sides at once. The linear system is preconditioned with a Sparse Approximate Inverse, which is modified to handle dense matrices. The solver is parallelized on shared memory machines using OpenMP. To verify the method some tests are conducted on varying geometries. We use simple geometries to show that the method works. We show that the method scales on several processors of a shared memory machine. To prove that the method works for real life problems, we do some tests on large scale aircrafts. The largest test is a one million unknown simulation on a full scale model of a fighter aircraft. } } @PhDThesis{ itlic:2002-003, author = {Emad Abd-Elrady}, title = {Harmonic Signal Modeling Based on the Wiener Model Structure}, school = it, department = syscon, year = 2002, number = {2002-003}, type = {Licentiate thesis}, month = may, url = {http://www.it.uu.se/research/publications/lic/2002-003/files/} , abstract = {The estimation of frequencies and corresponding harmonic overtones is a problem of great importance in many situations. Applications can, for example, be found in supervision of electrical power transmission lines, in seismology and in acoustics. Generally, a periodic function with an unknown fundamental frequency in cascade with a parameterized and unknown nonlinear function can be used as a signal model for an arbitrary periodic signal. The main objective of the proposed modeling technique is to estimate the fundamental frequency of the periodic function in addition to the parameters of the nonlinear function. The thesis is divided into four parts. In the first part, a general introduction to the harmonic signal modeling problem and different approaches to solve the problem are given. Also, an outline of the thesis and future research topics are introduced. In the second part, a previously suggested recursive prediction error method (RPEM) for harmonic signal modeling is studied by numerical examples to explore the ability of the algorithm to converge to the true parameter vector. Also, the algorithm is modified to increase its ability to track the fundamental frequency variations. A modified algorithm is introduced in the third part to give the algorithm of the second part a more stable performance. The modifications in the RPEM are obtained by introducing an interval in the nonlinear block with fixed static gain. The modifications that result in the convergence analysis are, however, substantial and allows a complete treatment of the local convergence properties of the algorithm. Moreover, the Cramer-Rao bound (CRB) is derived for the modified algorithm and numerical simulations indicate that the method gives good results especially for moderate signal to noise ratios (SNR). In the fourth part, the idea is to give the algorithm of the third part the ability to estimate the driving frequency and the parameters of the nonlinear output function parameterized also in a number of adaptively estimated grid points. Allowing the algorithm to automatically adapt the grid points as well as the parameters of the nonlinear block, reduces the modeling errors and gives the algorithm more freedom to choose the suitable grid points. Numerical simulations indicate that the algorithm converges to the true parameter vector and gives better performance than the fixed grid point technique. Also, the CRB is derived for the adaptive grid point technique.} } @PhDThesis{ itlic:2002-002, author = {Anders Berglund}, title = {On the Understanding of Computer Network Protocols}, school = it, department = docs, year = 2002, number = {2002-002}, type = {Licentiate thesis}, month = mar, url = {http://www.docs.uu.se/~andersb/lic/}, oldnote = {Included papers available at \url{http://www.it.uu.se/research/publications/lic/2002-002/paperA-2002-002.pdf} and \url{http://www.it.uu.se/research/publications/lic/2002-002/paperB-2002-002.pdf}} , abstract = {How students learn about network protocols is studied in a project-centred, internationally distributed, university course in computer systems taught jointly by two universities. Insights into students' understanding of basic concepts within computer networks are gained through an empirical phenomenographic research approach. The use of phenomenography as a research approach makes it possible to learn about computer science, as it is experienced by the students. The context in which the research is carried out and issues concerning by whom the context is experienced, are investigated and form a part of the methodological basis. Students' understanding of some protocols that are used within the project, as well as their experience of the general concept of network protocols are investigated, and different ways of experiencing the protocols are discerned. Some aspects that indicate good learning outcomes are identified, such as being capable of understanding a protocol in different ways and of making relevant choices between the ways it could be experienced according to the context in which it appears. Based on these results a discussion on learning and teaching is developed. It is argued that a variation in the context in which the protocol is experienced promotes good learning, since different ways of experiencing a protocol are useful with different tasks to hand. A student with a good understanding of network protocols can choose in a situationally relevant way between different ways of experiencing a protocol. } } @PhDThesis{ itlic:2002-001, author = {Eva Mossberg}, title = {Higher Order Finite Difference Methods for Wave Propagation Problems}, school = it, department = tdb, year = 2002, month = feb, number = {2002-001}, type = {Licentiate thesis}, abstract = {Wave propagation is described by the wave equation, or in the time-periodic case, by the Helmholtz equation. For problems with small wavelengths, high order discretizations must be used to resolve the solution. Two different techniques for finding compact finite difference schemes of high order are studied and compared. The first approach is Numerov's idea of using the equation to transfer higher derivatives to lower order ones for the Helmholtz equation, or, for the wave equation, from time to space. The second principle is the method of deferred correction, where a lower order approximation is used for error correction. For the time-independent Helmholtz problem, sharp estimates for the error is derived, in order to compare the arithmetic complexity for both approaches with a non-compact scheme. The characteristics of the errors for fourth order as well as sixth order accuracy are demonstrated and the advantages and disadvantages of the methods are discussed. A time compact, Numerov-type, fourth order method and a fourth order method using deferred correction in time are studied for the wave equation. Schemes are derived for both the second order formulation of the equation, and for the system in first order form. Stability properties are analyzed and numerical experiments have been performed, for both constant and variable coefficients in the equations. For the first order formulation, a staggered grid is used. } } @PhDThesis{ itlic:2001-016, author = {Furun{\"a}s {\AA}kesson, Johan}, title = {Interprocess Communication Utilising Special Purpose Hardware}, school = it, department = docs, year = 2001, number = {2001-016}, type = {Licentiate thesis}, month = dec, abstract = {Real-Time Systems are computer systems with constraints on the timing of actions. To ease the development and maintenance of application software, Real-time Systems often make use of a Real-Time Operating System (RTOS). Its main task is scheduling of application processes (tasks). Other functions can be inter process communication, interrupt handling, memory management etc. Sometimes it is hard (or even impossible) to meet the time constraints specified for a real-time system, resulting in an incorrectly functioning application. A possible remedy is to redesign the system by upgrading the processor and/or remove functionality, etc. An alternative solution could be the use of a special purpose hardware accelerated RTOS. The aim of such an accelerator is to speedup RTOS functions that impose big overhead i.e. to reduce the kernel overhead by offloading the application processor. Accordingly, the processor gets more time for executing application software, and hopefully the time constraints can be met. The main drawback is the cost of extra hardware. This thesis presents results from implementing RTOS functions in hardware, especially inter process communication (IPC) functions. The types of systems considered are uniprocessor and shared memory multiprocessor real-time systems. IPC is used in systems with co-operating processes. The operating systems on the market support a large variation of IPC mechanisms. We will here present and evaluate three different IPC implementations. The first is an extended message queue mechanism that is used in commercial robot control applications. The second is the signal mechanism in OSE, a commercial RTOS predominantly used in telecommunication control applications, and the third is the semaphore and message queue mechanisms supported by the leading commercial RTOS VxWorks. All the implementations are based on a pre-emptive priority-based hardware real-time kernel accelerator. We show that it is not optimal, practical or desirable to implement every kernel function into hardware, regarding systems in the scope of this thesis. However, an accelerator allows new functionality to be implemented. We illustrate this by implementing a message queue mechanism that supports priority inheritance for message arrival in hardware, which is too expensive to implement in software. Also, we show that substantial speedups are possible, and that a crucial mechanism in achieving speedup is the accelerator-processor interconnect. We further note that application speedups are possible, even in cases with an IPC-mechanism slow-down. The main reasons for this is that the accelerator can off-load the processor by handling the RTOS timing mechanism (clock-ticks), reducing the RTOS code to be executed on the processor, and handling interrupts. } } @PhDThesis{ itlic:2001-015, author = {Stefan S{\"o}derberg}, title = {A Parallel Block-Based {PDE} Solver with Space-Time Adaptivity}, school = it, department = tdb, year = 2001, month = dec, number = {2001-015}, type = {Licentiate thesis}, abstract = {A second order space and time adaptive method for parallel solution of hyperbolic PDEs on structured grids is presented. The grid is adapted to the underlying solution by successive refinement in blocks. Therefore, there may be jumps in the cell size at the block faces. Special attention is needed at the block boundaries to maintain second order accuracy and stability. The stability of the method is proven for a model problem. The step sizes in space and time are selected based on estimates of the local truncation errors and an error tolerance provided by the user. The global error in the solution is also computed by solving an error equation similar to the original problem on a coarser grid. The performance of the method depends on the number of blocks used in the domain. A method of predicting the optimal number of blocks is presented. The cells are distributed in blocks over the processor set using a number of different partitioning schemes. The method is used to successfully solve a number of test problems where the method selects the appropriate space and time steps according to the error tolerance. } } @PhDThesis{ itlic:2001-014, author = {Abraham Zemui}, title = {Fourth Order Symmetric Finite Difference Schemes for the Wave Equation}, school = it, department = tdb, year = 2001, number = {2001-014}, type = {Licentiate thesis}, month = dec, abstract = {The solution of the acoustic wave equation in one space dimension is studied. The PDE is discretized using finite element approximation. A cubic piecewise Lagrange polynomial is used as basis. Consistent finite element and lumped mass schemes are obtained. These schemes are interpreted as finite difference schemes. Error analysis is given for these finite differences (only for constant coefficients).} } @PhDThesis{ itlic:2001-013, author = {Alexandre David}, title = {Practical Verification of Real-time Systems}, type = {Licentiate thesis}, school = it, department = docs, year = 2001, number = {2001-013}, month = oct, abstract = {Formal methods are becoming mature enough to be used on non trivial examples. They are particularly well fitted for real-time systems whose correctness is defined in terms of correct responses at correct times. Most common real-time systems are of reasonable size and can therefore be handled by an automatic verification tool such as \textsc{Uppaal}. Unfortunately the application of such techniques is not widely spread. This thesis presents advances in making formal techniques more accessable technology for system development and analysis. As the first contribution, we report on an industrial case study to show that model checkers can be used for debugging and error localization. We shall present a number of abstraction techniques applied in the case study to avoid the state explosion problem. As the second contribution, we have developed a hierarchical extension of timed automata to enable more structured, compact, and more complex descriptions of systems by the users. Such a hierarchical representation is better suited for abstraction and expected to give better searching algorithms. Finally we present a hybrid animation system serving as a plug-in module for model-checkers to improve features for modelling and simulation. } } @PhDThesis{ itlic:2001-012, author = {Per {\AA}hgren}, title = {Teleconferencing, System Identification and Array Processing}, school = it, department = syscon, year = 2001, number = {2001-012}, type = {Licentiate thesis}, month = oct, abstract = {The area of teleconferencing has long yielded great interest in the signal processing community. The main reasons for this are probably the huge interest from the industry and the challenging problems of the topic. The problems of teleconferencing are relevant for several different disciplines in signal processing. Three of these are Acoustic Echo Cancellation, System Identification and Sensor Array Signal Processing. In this thesis some problems related to these disciplines are studied. The thesis is divided into 6 parts, one for each paper included. In the first part a new adaptive algorithm is applied to the acoustic echo cancellation problem. It is shown to perform much better than the Normalized Least Mean Squares (NLMS) algorithm and while it performs worse than the standard Recursive Least Squares (RLS) algorithm it is shown to be computationally simpler than this. In the second part the hierarchical RLS algorithm is analyzed. The extraordinary results presented for this algorithm in previous papers are discussed and explained. In the third part a new initialization method for RLS is presented that yields the exact Least Squares estimates while not being computationally more demanding than RLS. This is an important contribution since the standard initialization of the RLS algorithm is somewhat arbitrary. In the fourth part a method is presented that deals with the problem of estimating the common factors out of an arbitrary number of polynomials. Two problems of array processing and system identification are stated as problems for common factor estimation and the presented method is applied to these. For these two problems the method is shown to perform better than existing methods. In the fifth part a method for beamforming using few sensors is presented. Data-dependent beamformers usually perform badly when there are few sensors in the array, particularly when the beamformer constraints are numerous. The method presented deals with this problem by approximately fulfilling the beamformer constraints and hence getting extra degrees of freedom for suppressing interferences. In the sixth part the previously unsolved problem of array processing of non-zero mean signals is solved for the colored noise case. Methods are presented both for the estimation problem and the detection problem and are shown to perform well in numerical examples. } } @PhDThesis{ itlic:2001-011, author = {P{\"a}r Samuelsson}, title = {Modelling and control of activated sludge processes with nitrogen removal}, school = it, department = syscon, year = 2001, number = {2001-011}, type = {Licentiate thesis}, month = aug, abstract = {Stricter legislations on nitrogen removal together with increasing wastewater loads have successively increased the need for optimization and control of activated sludge processes. The aim of this thesis is primarily to propose and illustrate methods for modelling and control of activated sludge processes, and thus possibly improve process efficiency. The first part of this thesis describes a JAVA based simulator of the activated sludge process. Its features are discussed, and some control strategies are illustrated. The second part of the thesis presents a simple model based feedforward controller for controlling the nitrate level by using an external carbon source. Several simulation examples are used to illustrate the control law. In the third part, a model based strategy for control of the ammonium level by manipulating the aeration volume in the activated sludge process is presented. The strategy is based on exact linearization combined with some logical programming rules in order to deal with discrete volume changes. The control law is also evaluated in simulations.} } @PhDThesis{ itlic:2001-010, author = {Johan Edlund}, title = {A Parallel, Iterative Method of Moments and Physical Optics Hybrid Solver for Arbitrary Surfaces}, school = it, department = tdb, year = 2001, number = {2001-010}, type = {Licentiate thesis}, month = aug, abstract = {We have developed an MM-PO hybrid solver designed to deliver reasonable accuracy inexpensively in terms of both CPU-time and memory demands. The solver is based on an iterative block Gauss-Seidel process to avoid unnecessary storage and matrix computations, and can be used to solve the radiation and scattering problems for both disjunct and connected regions. It supports thin wires and dielectrica in the MM domain and has been implemented both as a serial and parallel solver. Numerical experiments have been performed on simple objects to demonstrate certain keyfeatures of the solver, and validate the positive and negative aspects of the MM/PO hybrid. Experiments have also been conducted on more complex objects such as an model aircraft, to demonstrate that the good results from the simpler objects are transferrable to the real life situation. The complex geometries have been used to conduct tests to investigate how well parallelised the code is, and the results are satisfactory. } } @PhDThesis{ itlic:2001-009, author = {Johan Bengtsson}, title = {Efficient Symbolic State Exploration of Timed Systems: Theory and Implementation}, school = it, department = docs, year = 2001, number = {2001-009}, type = {Licentiate thesis}, month = may, abstract = {Timing aspects are important for the correctness of safety-critical systems. It is crucial that these aspects are carefully analysed in designing such systems. UPPAAL is a tool designed to automate the analysis process. In UPPAAL, a system under construction is described as a network of timed automata and the desired properties of the system can be specified using a query language. Then UPPAAL can be used to explore the state space of the system description to search for states violating (or satisfying) the properties. If such states are found, the tool provides diagnostic information, in form of executions leading to the states, to help the desginers, for example, to locate bugs in the design. The major problem for UPPAAL and other tools for timed systems to deal with industrial-size applications is the state space explosion. This thesis studies the sources of the problem and develops techniques for real-time model checkers, such as UPPAAL, to attack the problem. As contributions, we have developed the notion of committed locations to model atomicity and local-time semantics for timed systems to allow partial order reductions, and a number of implementation techniques to reduce time and space consumption in state space exploration. The techniques are studied and compared by case studies. Our experiments demonstrate significant improvements on the performance of UPPAAL. } } @PhDThesis{ itlic:2001-008, author = {Markus Bylund}, title = {Personal Service Environments --- Openness and User Control in User-Service Interaction}, school = it, department = csd, year = 2001, number = {2001-008}, type = {Licentiate thesis}, month = jun, abstract = {This thesis describes my work with making the whole experience of using electronic services more pleasant and practical. More and more people use electronic services in their daily life - be it services for communicating with colleagues or family members, web-based bookstores, or network-based games for entertainment. However, electronic services in general are more difficult to use than they would have to be. They are limited in how and when users can access them. Services do not collaborate despite obvious advantages to their users, and they put the integrity and privacy of their users at risk. In this thesis, I argue that there are structural reasons for these problems rather than problems with content or the technology per se. The focus when designing electronic services tends to be on the service providers or on the artifacts that are used for accessing the services. I present an approach that focus on the user instead, which is based on the concept of personal service environments. These provide a mobile locale for storing and running electronic services of individual users. This gives the user increased control over which services to use, from where they can be accessed, and what personal information that services gather. The concept allows, and encourages, service collaboration, but not without letting the user maintain the control over the process. Finally, personal service environments allow continuous usage of services while switching between interaction devices and moving between places. The sView system, which is also described, implements personal service environments and serves as an example of how the concept can be realized. The system consists of two parts. The first part is a specification of how both services for sView and infrastructure for handling services should be developed. The second part is a reference implementation of the specification, which includes sample services that adds to and demonstrates the functionality of sView.} } @PhDThesis{ itlic:2001-007, author = {Hans Norlander}, title = {Parameterization of State Feedback Gains for Pole Assignment}, school = it, department = syscon, year = 2001, number = {2001-007}, type = {Licentiate thesis}, month = may, abstract = {The pole assignment problem has been subject for research for a long time. For single-input single-output systems this problem is well understood but for multi-input multi-output systems the pole assignment problem is more complex. In this thesis a parameterization of state feedback gains for pole assignment is characterized with respect to completeness, redundancy and existence. In order to make a systematic examination of this parameterization a number of classes are introduced. This parameterization depends on two matrices that can be regarded as design parameters. In the thesis it is shown how the degree of freedom in the pole assignment problem for multi-input systems is characterized by these two matrices. It turns out that the properties of the parameterization depends on whether the characteristic polynomials of the open and the closed loop systems are coprime or not. It is shown in the thesis that if the characteristic polynomials are coprime, every possible feedback gain can be parameterized in this way, and in this sense the parameterization is complete. If the characteristic polynomials have factors in common the parameterization is not complete. In the thesis the shortcomings of the parameterization for this case are characterized. The design parameters seem to offer a greater degree of freedom than what can be offered in the pole assignment problem. This indicates a certain degree of overparameterization. This redundancy in the design parameters is characterized in the thesis. The parameterization implies that a certain matrix is invertible. Necessary conditions for when this matrix is invertible are given in terms of the two design parameters. It is shown that this matrix is invertible for almost every value of the design parameters when the characteristic polynomials are coprime, and hence that the parameterized gains are generally applicable. The parameterization and its properties are illustrated on a linear model of the military aircraft JAS Gripen. } } @PhDThesis{ itlic:2001-006, author = {Bengt G{\"o}ransson}, title = {Usability Design: A Framework for Designing Usable Interactive Systems in Practice}, school = it, department = hci, year = 2001, number = {2001-006}, type = {Licentiate thesis}, month = apr, abstract = {Today many companies have started to become aware of the advantages of doing user-centred design. However, it is extremely rare that companies adopt a fully integrated user-centred design approach in one strategic shift. Rather, companies tend to adopt practices and methods in stages or adopt a particular method or practice only when a complex set of factors align to create readiness. There is a big market for companies vending usability methods, but poor usability of systems and products is still very common, the vendors often blaming it on factors outside their immediate influence. This among other things is a call for us to work for a user-centred design attitude as a major strategy for the system development process. The content of this thesis is dedicated to the question of how to develop usable interactive systems in practice. Main focus is on how we can raise the awareness of usability; articulate the need for user-centred design within the industry and development organisations; and practice user-centred design. A framework for usability design as an unpretentious way of applying user-centred design is described and discussed.} } @PhDThesis{ itlic:2001-005, author = {Per Carlsson}, title = {Market and Resource Allocation Algorithms with Application to Energy Control}, school = it, department = csd, year = 2001, number = {2001-005}, type = {Licentiate thesis}, month = apr, abstract = {The energy markets of today are markets with rather few active participants. The participants are, with few exceptions, large producers and distributors. The market mechanisms that are used are constructed with this kind of a market situation in mind. With an automatic or semiautomatic approach, the market mechanism would be able to incorporate a larger number of participants. Smaller producers, and even consumers, could take an active part in the market. The gain is in more efficient markets, and --- due to smaller fluctuations in demand --- better resource usage from an environmental perspective. The energy markets of the Nordic countries (as well as many others) were deregulated during the last few years. The change has been radical and the situation is still rather new. We believe that the market can be made more efficient with the help of the dynamics of the small actors. The idealised world of theory (of economics) often relies on assumptions such as continuous demand and supply curves. These assumptions are useful, and they do not introduce problems in the power market situation of today, with relatively few, large, participants. When consumers and small producers are introduced on the market, the situation is different. Then it is a drawback if the market mechanims cannot handle discontinuous supply and demand. The growth in accessibility to computational power and data communications that we have experienced in the last years (and are experiencing) could be utilised when constructing mechanisms for the energy markets of tomorrow. In this thesis we suggest a new market mechanism, \textsc{ConFAst}, that utilises the technological progress to make it possible to incorporate a large number of active participants on the market. The mechanism does not rely on the assumptions above. The gain is a more efficient market with less fluctuations in demand over the day. To make this possible there is a need for efficient algorithms, in particular this mechanism relies on an efficient aggregation algorithm. An algorithm for aggregation of objective functions is part of this thesis. The algorithm handles maximisation with non concave, even noisy, objective functions. Experimental results show that the approach, in practically relevant cases, is significantly faster than the standard algorithm. } } @PhDThesis{ itlic:2001-004, author = {Bengt Eliasson}, title = {Numerical Simulation of Kinetic Effects in Ionospheric Plasma}, school = it, department = tdb, year = 2001, number = {2001-004}, type = {Licentiate thesis}, month = apr, abstract = {In this thesis, we study numerically the one-dimensional Vlasov equation for a plasma consisting of electrons and infinitely heavy ions. This partial differential equation describes the evolution of the distribution function of particles in the two-dimensional phase space $(x,v)$. The Vlasov equation describes, in statistical mechanics terms, the collective dynamics of particles interacting with long-range forces, but neglects the short-range ``collisional'' forces. A space plasma consists of electrically charged particles, and therefore the most important long-range forces acting on a plasma are the Lorentz forces created by electromagnetic fields. What makes the numerical solution of the Vlasov equation to a challenging task is firstly that the fully three-dimensional problem leads to a partial differential equation in the six-dimensional phase space, plus time, making it even hard to store a discretized solution in the computer's memory. Secondly, the Vlasov equation has a tendency of structuring in velocity space (due to free streaming terms), in which steep gradients are created and problems of calculating the $v$ (velocity) derivative of the function accurately increase with time. The method used in this thesis is based on the technique of Fourier transforming the Vlasov equation in velocity space and then solving the resulting equation. We have developed a method where the small-scale information in velocity space is removed through an outgoing wave boundary condition in the Fourier transformed velocity space. The position of the boundary in the Fourier transformed variable determines the amount of small-scale information saved in velocity space. The numerical method is used to investigate a phenomenon of tunnelling of information through an ionospheric layer, discovered in experiments, and to assess the accuracy of approximate analytic formulae describing plasma wave dispersion. The numerical results are compared with theoretical predictions, and further physical experiments are proposed. } } @PhDThesis{ itlic:2001-003, author = {Erik K. Larsson}, title = {On Identification of Continuous-Time Systems and Irregular Sampling}, school = it, department = syscon, year = 2001, number = {2001-003}, type = {Licentiate thesis}, month = mar, abstract = {The problem of identifying continuous-time systems is of fundamental interest in various areas, such as, astrophysics, economics, control and signal processing. Over the years there has been an extensive research going on in this field, which has resulted in numerous publications. The most obvious reason for working with continuous-time systems is that most physical systems are inherently continuous in time. Therefore, the parameters in the models often have a physical interpretation. In this thesis some specific problems concerning identification of continuous-time autoregressive (CAR) processes are studied. The main approach is based on replacing the differentiation operator with some approximations and forming a discrete-time linear regression model. The continuous-time system parameters are then obtained by using the least squares method. It is, however, well known that this approach will result in biased estimates unless some modifications are introduced. The first part of the thesis explores the possibility to extend some of the existing methods for identifying CAR-processes, using the approach described above, to the case of unevenly sampled data. Some computationally very efficient methods are presented. In the second part of the thesis a simple method for computing the CRB for CAR-processes, given arbitrary sampling patterns, is introduced. Several simulation studies are considered with some interesting results. In the third part of the thesis the problem of identifying CAR-processes, using limiting properties of sampled stochastic systems, is addressed. The presented method is intuitively clear and numerically sound, it is based on some new results regarding sampling of CAR-processes that are presented as well. } } @PhDThesis{ itlic:2001-002, author = {Johan Steensland}, title = {Domain-based partitioning for parallel {SAMR} applications}, school = it, department = tdb, year = 2001, number = {2001-002}, type = {Licentiate thesis}, month = mar, abstract = {This thesis presents a study of domain-based partitioning techniques for dynamic structured grid hierarchies, occuring in structured adaptive mesh refinement (SAMR) methods. Such methods for obtaining the numerical solution to partial differential equations yield highly advantageous ratios for cost/accuracy as compared to methods based upon static uniform approximations. Distributed implementations of these techniques have the potential for enabling realistic simulations of complex systems. These implementations however, present significant challenges in dynamic data-distribution and load balancing. That is, when SAMR is executed on a parallel computer, the work load will change dynamically. Thus, there is need for \textit{dynamic} load balancing in order to efficiently utilize the resourses of the parallel computer. Inverse space-filling curve partitioning (ISP) is appealing for load balancing in parallel SAMR, because of its speed. In this work, ISP is considered as \textit{part} of a partitioning approach, which combines structured and unstructured techniques. Various design decisions for the structured partitioning are considered. Different design choices lead to graphs with different properties. One objective is to investigate how these differences affect the behavior of ISP. This thesis contributes by identifying certain design choices as being advantageous, and by presenting four new partitioning algorithms that correspond to these design decisions. An experimental comparison of dynamic partitioning techniques for \textit{blockwise} parallel structured adaptive mesh refinement applications is presented. It is shown that an ISP-based technique can compete with other approaches for certain classes of applications. Moreover, an extended experimental characterization of dynamic partitioning\-/load-balancing techniques for \textit{general} adaptive grid hierarchies is presented. Techniques studied include newly proposed as well as existing approaches. It was found that two of the proposed algorithms were particularly useful: pBD-ISP for the more communication dominated applications, and G-MISP+SP for the computation dominated applications. Policies for the automatic selection of partitioner based on application and system state are outlined. Recommendations for appropriate partitioning techniques, given application and system state, are given. The overall motivation is the formulation of policies required to drive a \textit{dynamically adaptive} meta-partitioner for SAMR grid hierarchies capable of selecting the most appropriate partitioning strategy at runtime, based on current application and system state. Such a partitioner may significantly decrease application execution time.} } @PhDThesis{ itlic:2001-001, author = {Erik Bor{\"a}lv}, title = {Design and Usability in Telemedicine}, school = it, department = hci, year = 2001, number = {2001-001}, type = {Licentiate thesis}, month = feb, abstract = {A design of computer systems, that effectively supports the user, is a major goal within human-computer interaction. To achieve this, we must understand and master several tasks. These tasks concern firstly what to develop and secondly how to develop the system. The design and implementation of effective and efficient user interfaces is a prerequisite for the successful introduction of computer support in the medical domain. We base our work on a fundamental understanding of cognitive aspects of human-computer interaction, as well as on detailed analysis of the specific needs and requirements of the end users, i.e. the medical professionals. This thesis presents several approaches for development of systems for computer-supported work in health care. The solutions described concern vital problem areas: (1) the focus on the work tasks to be performed, (2) the cost of software and the way competition works in a networked world. Solutions to these problems can lead to more usable systems from a user's perspective but may also change the nature of computer applications. } } @PhDThesis{ itlic:2000-011, author = {Bharath Bhikkaji}, title = {Model Reduction for Diffusion Systems}, school = it, department = syscon, year = 2000, number = {2000-011}, type = {Licentiate thesis}, month = dec, abstract = {Diffusion phenomena has been studied with a lot of interest, for a long time, due to its historical and practical significance. In the recent days it has thrown a lot of interest among control engineers, as more and more practical systems, varying from stock markets to environmental pollution, have been observed to involve diffusion. Diffusion systems are normally modeled by linear partial differential equations (LPDE's) of the form \[ \frac{\partial T(x,t)}{\partial x} = \mathcal{L}T(x,t) \label{eq1.0} \] where $ \mathcal{L}$ is a second order linear spatial differential operator and $ T(x,t) $ is the physical quantity, whose variations in the spatial domain cause diffusion. To characterise diffusion phenomena, one has to obtain the solution of (\ref{eq1.0}) either analytically or numerically. Note that, since (\ref{eq1.0}) involves a second order spatial operator and a first order time derivative, one needs at least two boundary conditions in the spatial domain, $x$, and an initial condition at time $t=0$, for determining $ T(x,t) $. LPDE's of the type (\ref{eq1.0}) can be interpreted as infinite order linear time invariant systems (LTI systems) with inputs as boundary conditions. To compute the solution of (\ref{eq1.0}) numerically, one has to approximate, explicitly or implicitly, the underlying infinite order system by a finite order system. Any numerical scheme, which computes the solution of (\ref{eq1.0}), essentially approximates the underlying infinite order LTI system by a finite order LTI system. The efficiency of the approximation, for a given problem, varies for the different numerical schemes. In this thesis, we make an attempt to explore more about diffusion systems in general. As a starting point, we consider a simple case of one dimensional heat diffusion across a homogeneous region. The resulting LPDE is first shown explicitly to be an infinite order dynamical system. An approximate solution is computed from a finite order approximation of the true infinite order dynamical system. In this thesis, we first construct the finite order approximations using certain standard PDE solvers based on Chebyshev polynomials. From these finite order approximations we choose the best one, from a model reduction perspective, and use it as a benchmark model. We later construct two more approximate models, by exploiting the given structure of the problem and we show by simulations that these models perform better than the chosen benchmark. } } @PhDThesis{ itlic:2000-010, author = {Markus Lindgren}, title = {Measurement and Simulation Based Techniques for Real-Time Analysis}, school = it, department = docs, year = 2000, type = {Licentiate thesis}, number = {2000-010}, month = dec, note = {Also published as report MRTC 00/25 at M{\"a}lardalens h{\"o}gskola}, abstract = {Rigorous methods for design and implementation of safety critical real-time systems are vital to avoid loss of human lives and/or severe economic losses. Unfortunately, many of these systems are designed and evaluated using ad-hoc techniques. There are, on the other hand, relatively well developed scientific theories for modeling and analysis of timing and reliability. These theories are, however, only very slowly being introduced in industrial development. Important reasons for this are the simplifying model assumptions and lack of appropriate tools for timing analysis. This thesis presents two new methods aimed to narrow the gap between scientific results and industrial practice in evaluation and design of real-time systems. The first contribution is a method that from execution time measurements on the target system can derive worst-case execution time estimates of programs. Such estimates are essential when verifying if a system fulfills its timing requirements. The second contribution is a simulation based technique that can be used to evaluate timing aspects of distributed real-time systems, as well as calculating reliability estimates of these systems. Such estimates are essential in determining if a system meets its requirements sufficiently well. Compared to proposed analytical methods for execution time analysis and schedulability analysis, the starting point for both these methods are real target systems, rather than an abstract model with limited correspondance to reality. The presented initial case-studies give clear evidence that the proposed methods have potential of being both applicable and useful. } } @PhDThesis{ itlic:2000-009, author = {Jan Nystr{\"o}m}, title = {A formalisation of the {ITU-T} {I}ntelligent {N}etwork standard}, school = it, department = docs, year = 2000, type = {Licentiate thesis}, number = {2000-009}, month = dec, abstract = {Telecommunication systems are today among the largest and most heterogeneous computer systems that exist. The functionality offered by them is rapidly increasing, by numerous features: call waiting, credit-card billing and call-forwarding to name a few. The realisation of extra services poses a challenge to implementors, in particular since different services are developed at different times and places, by different people. Not only is the number and complexity of services increasing but some vendors want to enable users to tailor their own services and ultimately design them entirely. This of course calls for rigorous control of the services so that they do not come into conflict with the interest of the vendors, other users or surprise the users with their behaviours. One way of aiding the service designers is to provide a service creation environment containing a set of well defined building blocks that would be uniform for all features, irrespective of vendor or service. Such an environment also needs tool support for writing, checking, validating and analysing for possible conflicts. We have constructed a formalism for compactly specifying the interface behaviour of the switching and service logic system underlying a service creation environment, and for specifying the behaviour of components of an environment for service creation. For this formalism we supply tool support in the form of a simulator. We have further made a formalisation, in our framework, of the ITU-T Intelligent Network model, Capability Set-1. The formalisation concerns both the underlying service architecture, in which service logic is perform by a dedicated Service Control Function, and the component language, in which Service Independent Building Blocks are composed to yield new services. } } @PhDThesis{ itlic:2000-008, author = {Marcus Nilsson}, title = {Regular Model Checking}, school = it, department = docs, year = 2000, type = {Licentiate thesis}, number = {2000-008}, month = dec, abstract = {We present \emph{regular model checking}, a framework for algorithmic verification of infinite-state systems with, e.g., queues, stacks, integers, or a parameterized linear topology. States are represented by strings over a finite alphabet and the transition relation by a regular length-preserving relation on strings. Both sets of states and the transition relation are represented by regular sets. Major problems in the verification of parameterized and infinite-state systems are to compute the set of states that are reachable from some set of initial states, and to compute the transitive closure of the transition relation. We present an automata-theoretic construction for computing a non-finite composition of regular relations, e.g., the transitive closure of a relation. The method is incomplete in general, but we give sufficient conditions under which it works. We show how to reduce model checking of $\omega$-regular properties of parameterized systems into a non-finite composition of regular relations. We also report on an implementation of regular model checking, based on a new package for non-deterministic finite automata. } } @PhDThesis{ itlic:2000-007, author = {Magnus Larsson}, title = {Applying Configuration Management Techniques to Component-Based Systems}, school = it, department = docs, year = 2000, number = {2000-007}, type = {Licentiate thesis}, month = dec, note = {Also published as report MRTC 00/24 at M{\"a}lardalens h{\"o}gskola}, abstract = {Building software from components, rather than writing the code from scratch has several advantages, including reduced time to market and more efficient resource usage. However, component based development without consideration of all the risks and limitations involved may give unpredictable results, such as the failure of a system when a component is used in an environment for which it was not originally designed. One of the basic problems when developing component-based systems is that it is difficult to keep track of components and their interrelationships. This is particularly problematic when upgrading components. One way to maintain control over upgrades is to use component identification and dependency analysis. These are well known techniques for managing system configurations during development, but are rarely applied in managing run-time dependencies. The main contribution of this thesis is to show how Configuration Management (CM) principles and methods can be applied to component-based systems. This thesis presents a method for analysing dependencies between components. The method predicts the influence of a component update by identifying the components in a system and constructing a graph describing their dependencies. Knowledge of the possible influences of an update is important, since it can be used to limit the scope of testing and be a basis for evaluating the potential damage of the update. The dependency graphs can also be used to facilitate maintenance by identifying differences between configurations, e.g., making it possible to recognise any deviations from a functioning reference configuration. For evaluation of the method, a prototype tool which explores dependencies and stores them under version control has been developed. The prototype has been used for partial analysis of the Windows 2000 platform, for which it has been important to remain aware of dynamic dependencies. Preliminary experiments indicate that most components have only a few dependencies. The method has thus given an indication that the analysis of the effects of component updates may not be as difficult as might be expected.} } @PhDThesis{ itlic:2000-006, author = {Gustaf Naeser}, title = {A Flexible Framework for Detection of Feature Interactions in Telecommunication Systems}, school = it, department = docs, year = 2000, number = {2000-006}, type = {Licentiate thesis}, month = oct, abstract = {The complexity of today's telecommunications systems grows with each new feature introduced. As the number of services an operator provides can be used to gain advantage over competitors the number of services will continue to increase. As the complexity grows, so does the possibility for feature interactions, situations where the operation of features interfere with the operation of other features. Interactions cost more to resolve the later during the introduction of a new feature they are detected. This makes the need for analysis of feature interactions during development preeminent. There exists a multitude of frameworks and techniques for specification and analysis of models of telecommunications systems. However, we have identified that they often impose unnecessary design decisions on the models, making them untoward. In this thesis we propose a framework for specification of models of telecommunications systems. The framework is designed to describe them as general systems of communicating processes in a flexible way which allows alterations to be made late during the design. We also present definitions of interactions and how the interaction definitions are used in the framework to detect undesired interactions. A model for telephony systems is derived through observations made of common telephony concepts and constructs. Delving into concepts early in the design of the system is shown to avoid several sources of interactions. To demonstrate the potential of the framework we present a case study where the system and services described in the first interaction detection contest has been implemented and searched for interactions. } } @PhDThesis{ itlic:2000-005, author = {Fredrik Edelvik}, title = {Finite Volume Solvers for the {M}axwell Equations in Time Domain}, school = it, department = tdb, year = 2000, number = {2000-005}, type = {Licentiate thesis}, month = oct, abstract = {Two unstructured finite volume solvers for the Maxwell equations in 2D and 3D are introduced. The solvers are a generalization of FD-TD to unstructured grids and they use a third-order staggered Adams--Bashforth scheme for time discretization. Analysis and experiments of this time integrator reveal that we achieve a long term stable solution on general triangular grids. A Fourier analysis shows that the 2D solver has excellent dispersion characteristics on uniform triangular grids. In 3D a spatial filter of Laplace type is introduced to enable long simulations without suffering from late time instability. The recursive convolution method proposed by Luebbers et al. to extend FD-TD to permit frequency dispersive materials is here generalized to the 3D solver. A better modelling of materials which have a strong frequency dependence in their constitutive parameters is obtained through the use of a general material model. The finite volume solvers are not intended to be stand-alone solvers but one part in two hybrid solvers with FD-TD. The numerical examples in 2D and 3D demonstrate that the hybrid solvers are superior to stand-alone FD-TD in terms of accuracy and efficiency. } } @PhDThesis{ itlic:2000-004, author = {Anders Wall}, title = {A Formal Approach to Analysis of Software Architectures for Real-Time Systems}, school = it, department = docs, year = 2000, number = {2000-004}, type = {Licentiate thesis}, month = sep, note = {Also published as report MRTC 00/21 at M{\"a}lardalens h{\"o}gskola}, abstract = {A software architecture is a high-level design description of a software system. In terms of the architecture, early design decisions can be analyzed to improve the quality of a real time software system, which depends very much on how it is structured rather than how it is implemented. Architectural analysis techniques vary in their degree of formality. The least formal is based on reviews and scenarios, whereas the most formal analysis methods are based on mathematics. In this thesis, we propose to use a formal approach to software architectural analysis. We use networks of timed automata to model the architecture of real time systems and transform architectural analysis problems to reachability problems that can be checked by the existing tools for timed automata. The typical properties that can be handled using this approach are schedulability and safety properties. As the first technical contribution, we extend the classic model of timed automata with a notion of real time tasks. This yields a general model for real-time systems in which tasks may be periodic and non-periodic. We show that the schedulability problem for the extended model can be transformed to a reachability problem for standard timed automata, and thus it can be checked by existing model-checking tools, e.g. UPPAAL for timed automata. As the second contribution, we present a method to check general high level temporal requirements e.g. timing constraints on data flowing in multi-rate transactions, which can not be handled by traditional approach to schedulability analysis. We have developed an algorithm that given a data dependency model and a schedule for a transaction constructs a timed automaton describing the behavior of the transaction. Thus, by using existing verification tools we can verify that a given architecture is schedulable and more importantly, it is correctly constructed with respect to the high level temporal constraints. } } @PhDThesis{ itlic:2000-003, author = {Fredrik Larsson}, title = {Efficient Implementation of Model-Checkers for Networks of Timed Automata}, school = it, department = docs, year = 2000, number = {2000-003}, type = {Licentiate thesis}, month = may, abstract = {Since real-time systems often operate in safety-critical environments it is extremely important that they function correctly. \textsc{uppaal} is a tool that can be used for validation and verification of real-time systems. The user models the system using networks of timed automata and uses a simple logic to express safety requirements that the modelled system must satisfy to guarantee its correct behaviour. \textsc{uppaal} then performs reachability analysis using constraint solving techniques to check if the model satisfies the given requirements. In addition, the tool is also able to provide the user with a sample execution that explains why a requirement is (or is not) satisfied by the model. The analysis is fully automated. This thesis describes various techniques adopted when implementing \textsc{uppaal}. Some of he techniques have improved the performance of \textsc{uppaal} significantly. We have studied the techniques with performance measurements in several case-studies. One of the main contributions is the comparison of different strategies in implementing the basic data structures and searching algorithms. The measurements can be used as hints on what parts of the model-checker that are most important to optimise. Though the techniques are studied in the context of timed automata, we believe that they are applicable to the implementation of general software tools for automated analysis. } } @PhDThesis{ itlic:2000-002, author = {Susanne Remle}, title = {Modeling and Parameter Estimation of the Diffusion Equation}, school = it, department = syscon, year = 2000, number = {2000-002}, type = {Licentiate thesis}, month = may, abstract = {In many applications such as heat diffusion and flow problems, it is of interest to describe the process behavior inside a particular medium. An example can be the strive for estimating certain parameters related to the material. These processes are often modeled by a partial differential equation. Certain methods for identifying unknown material constants require the model to be of finite order. This thesis describes how the diffusion process can be approximated with finite order model, and how the accuracy of an estimated model depends on the model order. In particular, a detailed analysis is carried out for the case when the approximate model accounts for solving the diffusion by a difference method. } } @PhDThesis{ itlic:2000-001, author = {Katarina Boman}, title = {Low-Angle Estimation: Models, Methods and Bounds}, school = it, department = syscon, year = 2000, type = {Licentiate thesis}, number = {2000-001}, month = feb, abstract = {In this work we study the performance of elevation estimators and lower bounds on the estimation error variance for a low angle target in a smooth sea scenario using an array antenna. The article is structured around some key assumptions on multipath knowledge, signal parameterization and noise covariance, giving the reader a framework in which Maximum-Likelihood estimators exploiting different {\'a} priori information can be found. The crucial factor that determines the estimator accuracy is the multipath modeling, and there are three alternative levels of knowledge that can be used: 1) two unknown target locations 2) the target and its corresponding sea-reflection are related via simple geometry 3) the sea reflection coefficient is known as a function of grazing angle. A compact expression for the Cram{\'e}r-Rao lower bound is derived, including all special cases of the key assumptions. We prove that the Cram{\'e}r-Rao bound is highly dependent on the multipath model, while it is the same for the different signal parameterizations and that it is independent of the noise covariance. However, the Cram{\'e}r-Rao bound is sometimes too optimistic and not achievable. The tighter Barankin bound is derived to predict the threshold behavior seen at low SNR. At high SNR the Barankin bound coincides with the Cram{\'e}r-Rao bound. Simulations show that the Maximum Likelihood methods are statistically efficient and achieve the theoretical lower bound on error variance, in case of high enough SNR. The bounds are also useful tools to design an improved array structure that can give better performance than the standard uniform linear array structure. The influence of the number of sensors and the number of snapshots on the error variance is also studied, showing the rate of improvement with more sensors or snapshots. Finally we discuss the use of multiple frequencies, which is mainly a tool for suppressing ambiguities. We show for which signal models it provides improved performance. } }