Swedish Institute of Computer Science Publications Database
Not a member yet
2787 research outputs found
Sort by
On matrices, automata, and double counting in constraint programming
No full textMatrix models are ubiquitous for constraint problems. Many such problems have a matrix of variables M , with the same constraint C defined by a finite-state automaton A on each row of M and a global cardinality constraint "gcc" on each column of M . We give two methods for deriving, by double counting, necessary conditions on the cardinality variables of the "gcc" constraints from the automaton A . The first method yields linear necessary conditions and simple arithmetic constraints. The second method introduces the cardinality automaton, which abstracts the overall behaviour of all the row automata and can be encoded by a set of linear constraints. We also provide a domain consistency filtering algorithm for the conjunction of lexicographic ordering constraints between adjacent rows of M and (possibly different) automaton constraints on the rows. We evaluate the impact of our methods in terms of runtime and search effort on a large set of nurse rostering problem instances
VETE: Virtualizing the Trusted Execution Environment
Get PDFThis document is the final report for the SICS project Virtualizing the Trusted Execution Environment
(VETE). This project was carried out in close collaboration with Ericsson Research and with support
from ST-Ericsson.
In this project, we desig an dimplement a hypervisor for the U8500 NovaThor platform that operates inside the Secure world of the main CPUs. The hypervisor will virtualize the underlying hardware in such way that the Trusted Execution Environment either directly or with the help of the
hypervisor can provide secure isolation between the Trusted Applications, and between Trusted Applications and normal applications
Ja-be-Ja: A Distributed Algorithm for Balanced Graph Partitioning
Get PDFBalanced graph partitioning is a well known NP-complete problem with a wide range of applications. These applications include many large-scale distributed problems such as the optimal storage of large sets of
graph-structured data over several hosts, or identifying clusters in on-line social networks. In such very large-scale distributed scenarios, state-of-the-art algorithms are not directly applicable, because they typically involve frequent global operations over the entire graph. In this paper, we propose a distributed graph partitioning algorithm, called Ja-be-Ja1.
The algorithm is massively parallel: each graph node is processed independently, and only the direct neighbors of the node, and a small subset of random nodes in the graph need to be known. Strict synchronization is not required. These features allow Ja-be-Ja to be easily adapted to
any distributed graph-processing system from data centers to fully distributed networks. We perform a thorough experimental analysis, which shows that the minimal edge-cut value achieved by Ja-be-Ja is comparable to state-of-the-art centralized algorithms such as Metis. In particular, on large social networks Ja-be-Ja outperforms Metis
Understanding Computer Role-Playing Games: A Genre Analysis Based on Gameplay Features in Combat Systems
Get PDFA game genre as diverse as that of computer role-playing games is difficult to overview. This poses challenges or both developers and researchers to position their work clearly within the genre. We present an overview of the genre based on clustering games with similar gameplay features. This allows a tracing of relations between subgenres through their gameplay, and connecting this to concrete game examples. The analysis was done through using gameplay design patterns to identify gameplay features and focused upon the combat systems in the games. The resulting cluster structure makes use of 321 patterns to create 37 different subgenre classifications based solely on gameplay features. In addition to the clusters, we identify four categories of patterns that help designers and researchers understand the combat systems in computer role-playing games
On the Conceptual Design of a Dynamic Component Model for Reconfigurable AUTOSAR Systems
No full textThe automotive industry has recently developed the embedded software standard AUTOSAR, which is now being introduced widely in production vehicles. The standard structures the application into reusable components that can be deployed in a specific vehicle using a configuration scheme. However, this configuration takes place at design time, with no provision for dynamically installing components to reconfigure the system. In this paper, we present the conceptual design of a dynamic component model that extends an AUTOSAR based control unit with the possibility to add plug-in components that execute on a virtual machine. This concept is intended to give benefits in terms of much shorter deployment time for new functions, even into vehicles that have already been produced. Further, it creates opportunities for vehicles to take part in federated embedded systems together with other products. It also opens up a market for third-party developers, and fosters open innovation in an ecosystem around the automotive software business
On the Performance Analysis of Large Scale, Dynamic, Distributed and Parallel Systems
No full textEvaluating the performance of large distributed applications is an important and non-trivial task. With the onset of Internet wide applications there is an increasing need to quantify reliability, dependability and performance of these systems, both as a guide in system design as well as a means to understand the fundamental properties of large-scale distributed systems. Previous research has mainly focused on either formalised models where system properties can be deduced and verified using rigorous mathematics or on measurements and experiments on deployed applications. Our aim in this thesis is to study models on an abstraction level lying between the two ends of this spectrum. We adopt a model of distributed systems inspired by methods used in the study of large scale system of particles in physics and model the application nodes as a set of interacting particles each with an internal state whose actions are specified by the application program. We apply our modeling and performance evaluation methodology to four different distributed and parallel systems. The first system is the distributed hash table (DHT) Chord running in a dynamic environment. We study the system under two scenarios. First we study how performance (in terms of lookup latency) is affectedon a network with finite communication latency. We show that an average delay in conjunction with other parameters describing changes in the network (such as timescales for network repair and join and leave processes)induces fundamentally different system performance. We also verify our analytical predictions via simulations.In the second scenario we introduce network address translators (NATs) to the network model. This makes the overlay topology non-transitive and we explore the implications of this fact to various performance metrics such as lookup latency, consistency and load balance. The latter analysis is mainly simulation based.Even though these two studies focus on a specific DHT, many of our results can easily be translated to other similar ring-based DHTs with long-range links, and the same methodology can be applied evento DHT's based on other geometries.The second type of system studied is an unstructured gossip protocol running a distributed version of the famous Belman-Ford algorithm. The algorithm, called GAP, generates a spanning tree over the participating nodes and the question we set out to study is how reliable this structure is(in terms of generating accurate aggregate values at the root) in the presence of node churn. All our analytical results are also verified using simulations.The third system studied is a content distribution network (CDN) of interconnected caches in an aggregation access network. In this model, content which sits at the leaves of the cache hierarchy tree, is requested by end users. Requests can then either be served by the first cache level or sent further up the tree. We study the performance of the whole system under two cache eviction policies namely LRU and LFU. We compare our analytical results with traces from related caching systems.The last system is a work stealing heuristic for task distribution in the TileraPro64 chip. This system has access to a shared memory and is therefore classified as a parallel system. We create a model for the dynamic generation of tasks as well as how they are executed and distributed among the participating nodes. We study how the heuristic scales when the number of nodes exceeds the number of processors on the chip as well as how different work stealing policies compare with each other. The work on this model is mainly simulation-based
Changing perspectives of time in HCI
No full textThe aim of this workshop is to unpack different ways of thinking about time, drawing a distinction between time as experienced, and time as counted by a ticking clock or measured by a computer algorithm. The concept of time is often taken for granted within HCI, yet highlighting the assumptions that underpin it could provide a resource for research and innovation. In this extended abstract, we illustrate how this is so