|PhD seminars 2004|
to Reduce Energy and Resources in Chip Multiprocessor Systems
opponent: Professor Margaret Martonosi, Department of Electrical Engineering,
Princeton University, USA
This thesis addresses the technical problem of how to design more efficient CMP systems in terms of energy and memory utilization. It contributes with design strategies that fall into three categories, consisting of design principles to reduce energy dissipation and main memory resources without reducing performance, design recommendations to balance the exploited instruction level parallelism (ILP) and TLP in a CMP, and a methodology to reduce simulation time when evaluating future designs.
Two of the proposed design principles can together reduce the energy dissipation in the L1-caches and translation-lookaside buffers by 30%. Secondly, it is shown that it is possible to tolerate ten times longer access latency to 70% of the main memory, which can be exploited by compression techniques to reduce the amount of memory by 30%. A novel compression scheme applied to the entire main memory is proposed and evaluated and is shown to reduce the needed memory resources by 30%. These reductions do not have any significant negative effect on performance.
Further, the trade-off between TLP and ILP is studied for applications with an abundance of TLP under a fixed area constraint. Four different design points ranging from 16 single-issue cores to two eight-issue cores are evaluated. By choosing the design point with four cores with an issue width of four it is possible to achieve close to optimal performance while still enabling single-threaded applications to run well.
Finally, a sampling technique for single-processor simulation is applied to multiprocessors. For one class of applications the technique is more efficient for multiprocessors by reducing the number of simulation points linearly with the number of processors. Another statistical technique is then proposed both for single and multiprocessor systems and reduces the required number of simulation points by one order of magnitude.
chip multiprocessor, energy efficiency, memory compression, statistical
Public defence of PhD thesis by Joakim Aidemark, Computer Engineering, Chalmers University of Technology:
Fault Tolerance for Embedded Real-Time Systems
We address cost issues of fault tolerance from both a design and a validation perspective. From a design perspective, we investigate cost-effective techniques that can make systems more resilient to transient hardware faults. We propose a two-level approach to achieve faulttolerance that combines system-level and node-level fault tolerance. Our approach relies on nodes that mask the effects of most transient faults and exhibit omission or fail-silent failures for permanent faults and transient faults that cannot be masked by the node itself. As only a subset of the faults is tolerated at the node level, we call this approach light-weight node-level fault tolerance, or light-weight NLFT. Tolerating transient faults at the node level is important in systems that rely on duplicated nodes for fault tolerance, as it allows the system to survive transient faults also when one of the nodes have failed permanently. It also improves the robustness of the system when both nodes are affected by correlated or near coincident transient faults. We have implemented a real-time kernel that supports light-weight NLFT through time redundant execution of tasks and the use of software implemented error detection. The effectiveness of light-weight NLFT is evaluated both analytically and by extensive fault injection experiments.
The thesis also deals with the cost of fault tolerance from a validation perspective. Fault injection based validation of error handling mechanisms is a time consuming and costly activity. We present a fault injection tool that can be easily extended and adapted to different target systems making fault injection less time-consuming. We also propose an analytical technique for investigating how error coverage varies for different input sequences to a system. The analysis helps us identify interesting activation patterns, e.g., those that give extremely low, or high, error coverage.
Keywords: Distributed real-time systems, error detection, error recovery, time redundancy, real-time kernels, fault injection, reliability calculations, analytical coverage estimation.
December 7, 2004, 10:15 am
Public defence of PhD thesis by Peter Ljunglöf, Computing Science, Göteborg University:
Expressivity and Complexity of the Grammatical Framework
Hörsalsvägen 4, Chalmers tekniska högskola, Göteborg
Bernard Lang, INRIA Rocquencourt, France
This thesis investigates the expressive power and parsing complexity of the Grammatical Framework (GF), a formalism originally designed for displaying formal propositions and proofs in natural language. This is done by relating gf with two more well-known grammar formalisms; generalized context-free grammar (GCFG), best seen as a framework for describing various grammar formalisms; and parallel multiple context-free grammar (PMCFG), an instance of GCFG.
Since GF is a fairly new theory, some questions about expressivity and parsing complexity have until now not been answered; and these questions are the main focus of this thesis. The main result is that the important subclass context-free GF is equivalent to PMCFG, which has polynomial parsing complexity, and whose expressive power is fairly well known.
Furthermore, we give a number of tabular parsing algorithms for PMCFG with polynomial complexity, by extending existing algorithms for context-free grammars. We suggest three possible extensions of GF/PMCFG, and discuss how the expressive power and parsing complexity are influenced. Finally, we discuss the parsing problem for unrestricted GF grammars, which is undecidable in general. We nevertheless describe a procedure for parsing grammars containing higher-order functions and dependent types.
Keywords: Grammatical Framework, generalized context-free grammar, multiple context-free grammar, context-free rewriting systems, type theory, expressive power, abstract syntax, linearization, parsing
November 25, 2004, 10:00 am
Public defence of PhD thesis by Per Johannessen, Computer Engineering, Chalmers University of Technology:
Design of Electrical Architectures for Safety Critical Automotive Systems
Faculty opponent: Professor John A. McDermid, Department of Computer Science, University of York
Increasing demands in the automotive industry in areas such as safety, driving pleasure and environmental care require new complex functionality to be implemented in cars. This evolution will to a large extent depend on the introduction of drive-by-wire systems in cars. A drive-by-wire system can replace traditional mechanical linkages, such as steering rods, with sensors, actuators, electronics, and software. Furthermore, many of these functions will be realized in distributed real-time systems with demands for high dependability and low cost. To design systems with such demands, there is a requirement for a structured design process with system focus. Important factors in such a design process are hazard analysis, design methods, and design principles. This thesis presents several approaches in the area suitable for the design of distributed drive-by-wire systems.
The main contribution of this thesis is a system perspective on the design of safety critical drive-by-wire systems. Related research tends to focus on the design of components in a system and not the whole system. However, safety is a system property and it has to be considered at the system level. Therefore, safety can not be guaranteed at component level. Even if a complete design process is not presented here, several parts of a design process for these systems are included.
The contribution of this work can be divided into several areas. Firstly, the development of two novel approaches for hazard analysis, one based on functionality described with a user focus and one based on actuators. These two approaches complement each other. Secondly, three different electrical system architectures are presented. The architectures represent different concepts for safety-critical drive-by-wire systems. Based on these electrical architectures, one design method for safety-critical control-by-wire architectures was developed. The method gives one electrical architecture with minimal communication and hardware given certain design requirements. As an integrated part of the design method, two design principles are presented. One principle is related to implementation and allocation of redundancy to meet dependability requirements. The second principle is related to timetriggered communication and arbitrary fault coverage. Further, the design methods and design principles have been successfully validated in three case studies.
Keywords: dependable systems, distributed systems, drive-by-wire, electrical architecture, hazard analysis, model-based development, system-safety, timetriggered communication
November 19, 2004, 10:15 am
Public defence of PhD thesis by Nicholas Wickström, Computer Engineering, Chalmers University of Technology:
Virtual Sensing of Combustion Quality in SI Engines using the Ion Current
Visionen, Högskolan i Halmstad
Faculty opponent: Dr. Gerard Malaczynski, Delphi Corporation
Several virtual sensors for combustion quality in spark ignited internal combustion engines are proposed. The virtual sensors estimate combustion quality based on the ion current signal measured in the center of the combustion chamber. Important properties of these sensors are their cost effective implementation and real-time operation.
A combustion variability virtual sensor for exhaust gas recycling is proposed. It estimates the coefficient of variation of indicated mean effective pressure by using the ion current integral while the combustion process is diluted with excess air or exhaust gases. With this it is possible to control, in a feedback loop, the amount of residual gases without experiencing driveability problems, producing large amounts of hydro carbons or stalling the engine.
Further, a virtual sensor is proposed for estimating the location of peak pressure to a precision of 2 degrees even under disturbances of additives or high air humidity. The estimates, made on-line while driving an experimental vehicle on the highway, were used for feedback control of the spark advance.
Finally, an air-fuel ratio virtual sensor is proposed that estimates the air-fuel ratio within 1.2% from the ion current. A second methodology is also proposed that keeps the air-fuel ratio in a multi-cylinder engine in balance, such that a typical imbalance of around 5-7% between the cylinders' air-fuel ratio is reduced.
Keywords: Internal Combustion Engines, Spark Ignition, Estimation, Control, Neural Networks, Ion Current
Public defence of PhD thesis by Håkan Sundell, Computing Science, Chalmers University of Technology:
Efficient and Practical Non-Blocking Data Structures
Room: Gustaf Dalén-salen, Origovägen 1, Chalmers tekniska högskola, Göteborg
Faculty opponent: Professor Friedhelm Meyer auf der Heide, Heinz Nixdorf Institute and Computer Science Department, University of Paderborn, Germany
This thesis deals with how to design and implement efficient, practical and reliable concurrent data structures. The design method using mutual exclusion incurs serious drawbacks, whereas the alternative non-blocking techniques avoid those problems and also admit improved parallelism. However, designing non-blocking algorithms is a very complex task, and a majority of the algorithms in the literature are either inefficient, impractical or both.
We have studied how information available in real-time systems can improve and simplify non-blocking algorithms. We have designed new methods for recycling of buffers as well as time-stamps, and have applied them on known non-blocking algorithms for registers, snapshots and priority queues.
We have designed, to the best of our knowledge, the first practical lock-free algorithm of a skip list data structure. Using our skip list construction we have designed a lock-free algorithm of the priority queue abstract data type, as well as a lock-free algorithm of the dictionary abstract data type.
We have designed, to the best of our knowledge, the first practical lock-free algorithm of a doubly linked list data structure. The algorithm supports well-defined traversals in both directions including deleted nodes. Using our doubly linked list construction we have designed a lock-free algorithm of the deque abstract data type. For the lock-free algorithms presented in this thesis, we have given correctness proofs of the strong consistency property called linearizability and the non-blocking properties.
We have made implementations for actual systems of the algorithms presented in this thesis and a representative set of related non-blocking as well as lock based algorithms in the literature. We have built a framework that combines the implementations in the form of a software library that offers a unified and efficient interface in combination with a portable design.
We have performed empirical performance studies of the data structures presented in this thesis in comparison with related alternative solutions. The experiments performed on an extensive set of multi-processor systems show significant improvements for non-blocking alternatives in general, and for the implementations presented in this thesis in particular.
Keywords: synchronization, non-blocking, shared data structure, skip list, doubly linked list, priority queue, dictionary, deque, snapshot, shared register, real-time, shared memory, lock-free, wait-free, abstract data type.
October 22, 2004, 1:15 pm
Public defence of PhD thesis by Elisabeth Uhlemann, Computer Engineering, Chalmers University of Technology:
Adaptive Concatenated Coding for Wireless Real-Time Communications
Hörsalsvägen 14, Chalmers tekniska högskola, Göteborg
Professor Stephen B. Wicker, Cornell University, New York, USA
of this thesis is to improve the performance of real-time communication
over a wireless channel, by means of specifically tailored channel coding.
The deadline dependent coding (DDC) communication protocol presented here
lets the timeliness and the reliability of the delivered information constitute
quality of service (QoS) parameters requested by the application. The
values of these QoS parameters are transformed into actions taken by the
link layer protocol in terms of adaptive coding strategies.
The applications targeted in this thesis are not necessarily replacement of cables in existing wired systems. Instead the motivation lies in the new services that wireless real-time communication enables. Hence, communication within and between cooperating embedded systems is typically the focus. The resulting IR-HARQ-DDC protocol presented here is an efficient and fault tolerant link layer protocol foundation using adaptive concatenated coding intended specifically for wireless real-time communications.
Keywords: Incremental redundancy hybrid ARQ, multiple concatenated codes, iterative decoding, rate compatible punctured codes, union bounds, EXIT charts, convergence analysis, wireless real-time communication, quality of service.
September 22, 2004, 13:15 am
Public defence of PhD thesis by Emilie Lundin-Barse, Computer Engineering, Chalmers University of Technology:
for intrusion and fraud detection
Professor Roy Maxion, Carnegie-Mellon University, Pittsburg, USA
Computer security is an area of ever increasing importance. Our society relies on computerised services, which gives many reasons for computer criminals, attackers, terrorists, hackers, crackers, fraudsters, or whatever name is appropriate, to break these systems. To deal with security problems, many types of mechanisms have been developed.
One mechanism is the intrusion detection system (IDS), designed to detect ongoing attacks, detect attacks after the fact or even detect preparations for an attack. The IDS is complementary to preventive security mechanisms, such as firewalls and authentication systems, which can never be made 100% secure. A similar type of system is the fraud detection system (FDS), specialised to detect frauds (or "attacks") in commercial services in different business areas, such as telecom, insurance and banking. Fraud detection can be considered a special case of intrusion detection.
A crucial part of intrusion or fraud detection is to have good quality input data for the analysis, as well as for training and testing the systems. However, it is difficult to acquire any training and test data and it is not known what kind of log data are most suitable to use for detection.
The contribution of this thesis is to offer guidance in matters of acquiring more suitable log data for intrusion and fraud detection. The first part is general and gives a survey of research done in intrusion detection and shows that intrusion and fraud detection reflect different aspects of the same problem. The second part is devoted to improving the availability and quality of log data used in intrusion and fraud detection. The availability of log data for training and testing detection systems can be improved by solving the privacy issues that prevent computer system owners from releasing their log data. Therefore, a method is suggested for anonymising the log data in a way that does not significantly affect their usefulness for detection. Though authentic data are convenient to use for training and testing they do not always have the desirable properties, which include flexibility and control of content. Another contribution to improve the availability and also the quality of log data is thus a method for creating synthetic training and test data with suitable properties. This part also includes a methodology for determining exactly which log data can be used for detecting specific attacks. In the ideal situation, we only collect exactly the data needed for detection, and this methodology can help us develop more efficient and adapted log sources. These new log sources will improve the quality of log data used for intrusion and fraud detection.
June 4th 2004, 1:15 am
Public defence of PhD thesis by Håkan Kvarnström, Computer Engineering, Chalmers University of Technology:
Implementation and Protection of Fraud Detection Systems
Professor Richard Kemmerer, Computer Science, University of California,
Society of today is becoming increasingly dependent on the availability and correctness of IT-systems. There are a growing number of industries that base their business almost exclusively on creating growth and economic value using IT-systems. Banks, credit card providers, online gambling brokers and providers of telecommunication services are a few examples where secure and reliable communication and computing environments are of the outmost importance for survival. These new services can create increased customer value and provide new business opportunities. However, history shows that fraudsters constantly seek economic gain by exploiting weaknesses in technical systems or business models of service offerings. Thus, minimizing economic loss due to fraud is an important goal in many enterprises. An important tool in that process is an efficient fraud detection system (FDS) that can give early indications of misuse of products and services offered to customers. This thesis addresses the subject of implementing and protecting an FDS. Specifically, we give arguments for the importance of thorough testing, training and sufficient protection when deploying a successful fraud detection system. We show how emerging computing environments put new demands on the security mechanisms and security extensions that protect the information and resources of their target environment. Fraud detection systems are no exception and we argue that detection mechanisms will play an important role in such environments. We propose and implement a methodology for generating synthetic data sets that can be used for testing and training fraud detection systems prior to real-life deployment. A comparison of fraud and intrusion detection system is made, where we highlight differences and similarities. Our study shows that the similarities clearly outweigh the differences, and research in one area is most often applicable for both types of systems. Finally, we discuss the topic of protecting fraud detection systems from malicious environments. Specifically, we study the importance of such systems from reverse engineering and propose mechanisms for achieving secrecy of the inherent information, even when deployed in hostile environments.
computer security, fraud detection, intrusion detection, fraud, security
architecture, computer misuse
June 2nd 2004, 10:15 am
Public defence of PhD thesis by Sven Eklund, Computer Engineering, Chalmers University of Technology:
Exploring Massively Parallel Models and Architectures for Efficient Computation of Evolutionary Algorithms
Högskolan i Halmstad
Faculty Opponent: Professor Wolfgang Banzhaf, Department of Computer Science, Memorial University of Newfoundland, Canada
Keywords: Evolutionary algorithms, genetic programming, linear machine code, distributed population models, Diffusion Model, symbolic function regression, time series forecasting, VHDL, FPGA.
May 28th, 2004, 1:15 am
Public defence of PhD thesis by Cecilia Ekelin, Computer Engineering, Chalmers University of Technology:
Framework for Scheduling of Embedded Real-Time Systems
Professor Gerhard Fohler, Institutionen för Datavetenskap, Mälardalens
Embedded real-time systems -- appearing in products such as cars and mobile phones -- are nowadays common in our everyday lives. Despite this fact, the design process of such systems is still cumbersome due to the large variety of design constraints that must be considered to ensure a safe operation of the system. In particular, present scheduling techniques -- that analyze the timing behavior of the system -- typically assume a too limited model to truly represent the system. In addition, to make the system cost-effective its design should be optimized regarding performance measures such as resource utilization, energy consumption and robustness. Unfortunately, optimization in general is very time-consuming process, often without guarantee that the best solution will be found.
This thesis addresses these problems by proposing a scheduling framework that not only enables arbitrary design constraints to be modelled but also allows for design optimization. The framework is based on constraint programming, and this thesis presents how the problem of scheduling embedded real-time systems can be modeled and solved using this technique. In addition, a number of novel techniques for reducing the runtime of the optimization algorithm are presented. This includes the identification and exclusion of symmetries in the solution space as well as fast and tight estimates of how good a solution may get. Finally, this thesis contains a performance comparison between the proposed framework and other state-of-the-art scheduling algorithms. The evaluation shows that both the quality of the solutions and the optimization time is improved over previous approaches --- in many cases the order of the solution time is reduced from minutes to seconds.
April 16th, 2004, 1:15 am
Public defence of PhD thesis by Fredrik Brännström, Computer Engineering, Chalmers University of Technology:
Analysis and Design of Multiple Concatenated Codes
Dr. Gerhard Kramer, Mathematics of Communications Research Department,
Bell Laboratories, Lucent Technologies, Murray Hill, New Jersey, USA.
of this thesis is to develop a methodology for designing efficient multiple
concatenated coding schemes, consisting of two or more constituent codes,
concatenated in serial or in parallel. Extrinsic information transfer
(EXIT) analysis is found to be a suitable and versatile analysis tool
for such codes and thus, the design methodology is based almost entirely
on this technique. The performance of multiple concatenated codes (MCCs)
in terms of convergence thresholds, decoding complexity required for convergence,
and resulting bit-error rate (BER) can be determined from their multi-dimensional
EXIT charts. However, multi-dimensional EXIT charts are difficult to visualize,
and hence an equivalent two dimensional EXIT chart projection is introduced,
yielding a powerful tool for the convergence analysis of MCCs. An exhaustive
search for rate-one convolutional codes with memory four or less is performed,
resulting in 98 classes of codes with unique EXIT functions. In addition,
a search for 8PSK mappings with different performance in terms of BER
and mutual information for the individual bits is conducted. Further,
optimal puncturing ratios for MCCs in terms of minimizing the convergence
threshold are found utilizing the EXIT functions of the constituent codes.
Following this approach, additional degrees of freedom for constructing
MCCs with low convergence thresholds over a range of code rates are obtained.
For an MCC with two constituent codes, decoding is performed by alternately
activating the two decoders. With more than two components, the order
of activation is no longer obvious. An algorithm that finds the optimal
decode schedule, in terms of minimizing the total decoding complexity
required to reach convergence, is proposed. Finally, a method for obtaining
unbiased estimates of the symbol energy and the noise variance without
knowledge of the transmitted bits is presented.
February 25th, 2004, 13:15
Public defence of PhD thesis by Håkan Sivencrona, Computer Engineering, Chalmers University of Technology:
Design and Validation of Fault Containment Regions in Distributed Communication
Faculty Opponent: Professor Geert Deconinck, Katholieke Universitet, Leuven, Belgium
This thesis has a two fold focus where the first is an evaluation of a time-triggered communication protocol implementation, TTP-C1, which was stressed by use of heavy-ion fault injection. The gathered result showed a novel type of failures, earlier known only from theory, so-called slightly-out-of-specification faults, that manifested as Byzantine failures with resulting system inconsistence. The second focus lies on the design and simulation of algorithms for RedCAN switches to dynamically reconfigure a CAN bus. The thesis is divided into three parts which deals with the design, validation and analysis of dependable communication with respect to the above mentioned focus.
Part I deals with the design of mechanisms for fault containment. We propose one algorithm to handle slightly-out-of-specification faults in time domain as they manifested during heavy-ion fault injections in TTP-C1 implementation. We present a novel simulation tool to test and execute the scenarios that lead to serious communication degradation using two different algorithms. A second algorithm that we propose handles a distributed recovery approach after permanent bus and node failures in a CAN communication system using RedCAN switches.
Part II presents results from heavy-ion fault injection experiments in a TTP-C1 cluster consisting of four to nine synchronized nodes. This was done to be able to evaluate the performance of the time-triggered protocol and assess the efficiency of the implemented dependability increasing mechanism in presence of faults. Part II furthermore presents performance results of different RedCAN recovery algorithms collected through a novel simulation tool, RedCAN simulation manager that we have designed. Part II additionally includes validation result of a proposed solution for isolating asymmetric faults in a time-triggered system through an active star coupler.
Part III contains analyses of the results given from presented validation results and real world experiences, especially Byzantine faults in a distributed communication system are discussed.
Keywords: Time-triggered protocol, fault containment regions, fault injection, validation, slightly-out-of-specification faults, Byzantine faults, asymmetric faults, fault handling and membership agreement.
January 27th, 2004, 13:15
Public defence of PhD thesis by Jim Nilsson, Computer Engineering, Chalmers University of Technology:
Accurate and Resource-Efficient Coherence Prediction
Faculty Opponent: Professor Stefanos Kaxiras, University of Patras, Greece
The increasing speed gap between processor microarchitectures and memory technologies can potentially slow down the historical performance growth of computer systems. Parallel applications on shared memory multiprocessors that experience cache misses due to communication are extra susceptible to this speed difference.
Prediction has been proposed as a general technique in computer architecture to anticipate and speculate about events in the processor and in the memory system. Specific prediction techniques have been successfully used in different parts of the processor, e.g. branch outcome prediction, branch target prediction, and prefetching.
Coherence message prediction has recently been proposed as a means to reduce the impact of long-latency memory operations in multiprocessors. However, this prediction can be very resource consuming and ineffective.
This thesis addresses the resource inefficiency as well as the inaccuracy of proposed coherence predictors. It proposes novel prediction mechanisms with improved accuracy and/or with lower resource requirements.
One important finding of the thesis is that specialized coherence prediction techniques to improve write-related overhead are only moderately effective for a transaction processing workload. I show that improvements are possible through the notion of load-store sequences -- a new data sharing model I contribute with in the thesis.
In the area of generalized coherence message prediction I contribute with a novel caching scheme for history tables that cuts down the static overhead by an order of magnitude. In-depth analyses of the dynamic memory requirements of generalized coherence predictors, as well as their learning time effects are also presented, with suggestions on how to reduce the dynamic overhead while increasing the accuracy of coherence predictors.
|Licentiate seminars 2004|
seminar by Ming Xiao, Computer Engineering, Chalmers University
Linsen, Rännvägen 6, Chalmers tekniska högskola, Göteborg
leader: Ingmar Land, Department of Communication Technology, Aalborg University.
Several concatenated and iterative decoding approaches are used to improve the power efficiency of continuous phase modulation (CPM). First a symbol interleaver is used for serially concatenated CPM (SCCPM). Convergence of iterative decoding for this scheme can be earlier (lower SNR: Signal-to-Noise-Ratio) compared to bit interleaved SCCPM. Then a ring convolutional code (CC) is used as the outer code in this symbol interleaved SCCPM. By setting the to the alphabet size of the system (CPM, interleaver and ring CC), a natural combination of them is achieved. Further improvements on earlier convergence or error floors are achieved with this scheme. Finally, irregular repeat accumulate (IRA) codes with CPM (IRCPM) are considered. CPM now takes the role of the accumulator. This scheme shows even earlier convergence than SCCPM.
To analyze the error floor performance, we derive the union bound for symbol interleaved SCCPM. In this bound analysis, we have to consider the order of nonzero permuted difference symbols that are not identical. We also derive the union bound for IRCPM from its equivalent structure. This structure introduces a virtual interleaver before CPM. Thus, the union bound analysis for SCCPM is now applicable.
Licentiate seminar by Markus Forsberg, Computing Science, Chalmers University of Technology:
of Functional Programming in Formal and Natural Languages
Discussion leader: Professor Viggo Kann, Institutionen för numerisk analys och datalogi, KTH, Stockholm
This thesis describes two applications of functional programming to process formal and natural languages. The techniques described in this thesis are closely connected to compiler construction, which is obvious in the work on BNF Converter.
The first part of the thesis describes the BNFC (the BNF Converter) application, a multi-lingual compiler tool. BNFC takes as its input a grammar written in Labelled BNF (LBNF) notation, and generates a compiler front-end (an abstract syntax, a lexer, and a parser). Furthermore, it generates a case skeleton usable as the starting point of back-end construction, a pretty printer, a test bench, and a Latex document usable as a language specification. The program components can be generated in Haskell, Java, C and C++, and their standard parser and lexer tools. BNFC itself was written in Haskell.
The methodology used for the generated front-end is based on Appel's books on compiler construction. BNFC has been used as a teaching tool in compiler construction courses at Chalmers. It has also beenapplied to research-related programming language development, and in an industrial application producing a compiler for a telecommunications protocol description language.
The second part of the thesis describes Functional Morphology, a toolkit for implementing natural language morphology in the functional language Haskell. The main idea behind is simple: instead of working with untyped regular expressions, which is the state of the art of morphology in computational linguistics, we use finite functions over hereditarily finite algebraic data types. The definitions of these data types and functions are the language-dependent part of the morphology. The language-independent part consists of an untyped dictionary format which is used for translation to other morphology formats and synthesis of word forms, and to generate a decorated trie, which is used for analysis.
Functional Morphology builds on ideas introduced by Huet in his computational linguistics toolkit Zen, which he has used to implement the morphology of Sanskrit. The goal has been to make it easy for linguists who are not trained as functional programmers, to apply the ideas to new languages. As a proof of the productivity of the method, morphologies for Swedish, Italian, Russian, Spanish, and Latin have already been implemented.
Licentiate seminar by Niklas Elmqvist, Computing Science, Chalmers University of Technology:
Visualization of Causal Relations
Hörsalsvägen 11, Chalmers tekniska högskola, Göteborg
leader: Professor Stephan Diehl, Katholische Universität Eichstätt-Inglostadt,
The notion of cause and effect is pervasive in human thinking and plays a significant role in our perception of time. Software systems, in particular parallel and distributed ones, are permeated by this causality, and the human mind is especially well-suited to detect instances of this concept. Unfortunately, real-world systems of causally related events are often too large and complex to be comprehended unaided. In this thesis, we explore ways of using information visualization to help humans perceive these complex systems of causal relations, not only for software systems, but also for more general application areas.
The Growing Squares visualization technique uses a combination of color, texture, and animation to present a sequence of related events in a distributed system. User studies show that this technique is significantly more effective for solving problems related to causality in distributed systems than traditional Hasse diagrams for small data sets, and more effective (though not significantly so) for large data sets.
The Growing Polygons visualization technique was designed to address some of the weaknesses of the Growing Squares technique, and presents the interacting processes in a system as color-coded polygons with sectors indicating the influences and information propagation in the system. User studies show that this technique is significantly more effective than Hasse diagrams for all data sets, regardless of size.
Finally, we have conducted a case study of causality visualization in the context of scientific citation networks, creating a bibliographic visualization tool called CiteWiz. The tool contains a modified Growing Polygons visualization, suitably adapted to citation networks with linear time windows and process hierarchies, as well as a new static timeline visualization that maps the citation count and publication date of an article or author to its size and position on the timeline, respectively.
causality visualization, causal relations, citation network
November 17, 2004, 2:15 pm
Licentiate seminar by Xing Fan, Computer Engineering, Chalmers University of Technology:
Real-time communication services for distributed computing over switched Ethernet
Visionen, Högskolan i Halmstad
leader: Professor Anna Brunström, Institutionen för informationsteknologi,
Licentiate seminar by Ulf Norell, Computing Science, Chalmers University of Technology:
Implementing Functional Generic Programming
EDIT-building, Hörsalsvägen 11, Chalmers tekniska högskola,
Discussion leader: Jeremy Gibbons, Oxford University Computing Laboratory, England
Functional generic programming extends functional programming with the ability to parameterize functions on the structure of a datatype. This allows a programmer to implement certain algorithms once and for all, instead of re-implementing them for each datatype they apply to. Examples of such algorithms include simple traversals and pretty printing as well as more complex XML processing tools.
The topic of this dissertation is the implementation of functional generic programming. More precisely we address two particular questions: how can we reduce the amount of work required to implement generic programming languages, and how can we embed generic programming in an existing functional language.
To answer the first question we show how meta-programming can be used to quickly prototype generic programming languages. In particular we describe prototype implementations of two generic programming languages: PolyP and Generic Haskell. The prototypes are extremely light-weight while still retaining most of the functionality of the original languages. One thing that is missing, though, is a way of adding type systems to the prototypes.
In answer to the second question we show how generic programming can be embedded in Haskell by exploiting the class system. We describe a new version of PolyP (version 2) together with a compiler that compiles PolyP 2 code into Haskell. By compiling the polytypic library, PolyLib, with our compiler we get a library of generic functions for Haskell.
October 29 , 2004, 10:15 am
Licentiate seminar by David Wahlstedt, Computing Science, Chalmers University of Technology:
Type Theory with First-Order Data Types and Size-Change Termination
Rännvägen 6B, Chalmers tekniska högskola, Göteborg
leader: Erik Palmgren, Matematiska institutionen, Uppsala universitet.
normalization for a dependently typed lambda-calculus extended with first-order
data types and computation schemata for first-order size-change terminating
recursive functions. Size-change termination, introduced by C.S. Lee,
N.D. Jones and A.M. Ben-Amram, can be seen as a generalized form of structural
induction, which allows inductive computations and proofs to be defined
in a straight-forward manner. The language can be used as a proof system---an
extension of Martin-Löf's Logical Framework.
October 18, 2004, 10:00 am
Licentiate seminar by Ha Hoai Phuong, Computing Science, Chalmers University of Technology:
Shared Objects for Interprocess Synchronization
leader: Professor Roger Wattenhofer, Department of Computer Science, ETH,
In parallel processing environments such as multiprocessor systems, processes are synchronized using concurrent objects, which allow many concurrent processes to access them at the same time. The performance of these concurrent objects heavily relies on the load conditions of the surrounding environment (e.g. OS, other applications, interconnection network, etc.), which are variant and unpredictable due to indeterministic interferences among processes.
Therefore, in order to minimize synchronization cost, a major overhead in parallel applications, we need to construct efficient concurrent objects that can react to the environment variations in order to achieve good performance under all possible system conditions. This thesis presents two new reactive shared objects: the "reactive multi-word compare-and-swap object" and the "self-tuning reactive tree".
The "multi-word" compare-and-swap objects are powerful constructs, which make the design of concurrent data objects much more effective and easier. The "reactive" multi-word compare-and-swap objects are advanced objects that dynamically measure the level of contention as well as the memory conflicts of the multi-word compare-and-swap operations, and in response, they react accordingly in order to guarantee good performance in a wide range of system conditions. We present two algorithms that are non-blocking (lock-free), allowing in this way a fast and dynamical behavior.
The self-tuning reactive trees distribute a set of processes to smaller groups accessing different parts of the memory in a coordinated manner, and moreover reactively adjust their size in order to attain efficient performance across different levels of contention. We present a data structure that in an on-line manner balances the trade-off between the tree traversal latency and the latency due to contention at the tree leaves.
The experiments on the SGI Origin2000, a well-known commercial ccNUMA multiprocessor, showed that the new reactive objects achieve significant improvements compared to previous results.
May 10th, 2004, 1:15 am
Licentiate seminar by Karin Hardell, Computing Science, Chalmers University of Technology:
Based Structural and Functional Modelling of the Halobacterial Transducer
of Rhodopsin II from Natronbacterium Pharaonis
The aim of this work has been to construct a functional and structural model of one of the proteins involved in archaebacterial swimming behavior, or taxis, namely the halobacterial transducer of sensory rhodopsin II from Natronobacterium pharaonis. The recently published crystal structure of this transducer, complexed with its receptor sensory rhodopsin, lacks information on functionally and structurally important parts of the transducer. Therefore, we aimed at constructing a model that could compensate for the lack of structure data and thus give us further clues about the function and structure of the transducer as well as other proteins involved in taxis.
A multiple sequence alignment of related proteins involved in bacterial and archaeal taxis enabled us to relate available structural data to conserved features among the sequences. In particular, we emphasize the role and structure of a common sequence motif involved in signaling - called the HAMP domain - in the process of taxis. We present a novel model for binding between the transducer and its sensor, in which we propose inter-dimer contacts in addition to the already know intra-dimer contacts between the transducer and sensory rhodopsin. Preliminary experimental studies have been conducted in an effort to elucidate the structure of a HAMP domain within the transducer, which plays an important role in signal transduction. These experimental studies have strengthened our proposed structural and functional models.
April 20th, 2004, 1:30 am
Licentiate seminar by Mattias Weckstén, Computing Science, Chalmers University of Technology:
Budgeting as a Tool for Reduced Development Cost for Embedded Real-Time
Wouldnt it be great if there were a systematic method for derivation of non functional constraints available at design time that made it possible to verify design and make implementation a much clearer task? This kind of methods are needed since systems of increasing complexity has to be developed, and the cost for failing has proven to bee too high. The problem is how to derive the design time constraints into implementation time constraints, maintaining the traceability for the individual constraints, and early on get indications whether a project is about to fail or not.
A method for implementation time constraint derivation has been developed and is presented in this thesis. Along with the basic method, several extensions are proposed. Evaluations of the practical usefulness of the method and the methods scalability have been done. To prove the methods importance in real development projects, a method for evaluation of the usability of this kind of methods has also been developed. The evaluation of the practicality shows that it is possible to find close to optimal solutions (within percent) in short time (within minutes). The evaluation of the scalability shows that the run time for finding implementable solutions scales polynomial with the size of the task graph. The evaluation of the usability shows that using the proposed method always leads to lower development cost than using an ad hoc method, in the case that the implementation is about to fail.
Keywords: Real-time systems, embedded, resource budgeting, design tool, tightness optimization, guarantees.
24th, 2004, 1:15 am
seminar by Mindaugas Drazdziulis, Computer Engineering,
Chalmers University of Technology:
leader: Anders Edman, Acreo AB, Norrköping
In recent years the market for portable applications, which have an increasing demand for battery life-time, has grown dramatically. Also, there is a demand for more functionality per chip, which requires more transistors to be integrated on a single chip. Due to these trends the total power dissipation of the chip is growing. This dictates a continuous need for solutions that would improve the development of power-aware electronics.
In low-power applications the control over the power dissipated due to leakage currents is as significant as the control over the switched power dissipation. In the near future, the leakage power will dramatically increase in part due to the emerging new leakage mechanisms, such as gate direct tunneling which is growing exponentially when the gate insulator thickness is shrinking. Gate direct tunneling currents, also referred to as gate leakage, will soon reach the same size as subthreshold leakage and will continue to grow if advancements in process technology or circuit (or both) levels will not be made.
The appearance of gate leakage increases the need to re-evaluate previously introduced leakage power-saving circuit techniques, since most of them initially were targeting only subthreshold leakage. In this thesis the efficiency of established techniques is evaluated in terms of total (subthreshold and gate) leakage suppression. A new gate-leakage suppression technique is proposed which efficiently reduces total leakage, when a logic circuit is in sleep mode.
February 5th, 2004, 10:15
seminar by Janna Khegai, Computing Science, Chalmers University
EC, Hörsalsvägen 11, Chalmers, Göteborg
The primary concern of this thesis is however limited to the usage of GF as a piece of software. The main results are:
Implementing a syntax editor, which provides a graphical user interface (GUI) for the command-line GF core.
Writing a part of code for automatic generation of gramletspure Java programs with limited (compared to GF) functionality that can be run on PDA (Portable Device Assistants) and as applets in a browser.
Writing the Russian resource grammar that takes care of the most basic morphological and syntactic rules and serves as a standard library for building application grammars (describing restricted language domains) in Russian. These results contribute to language engineering in GF on two di®erent levels:
Author level (end-user) constructing sentences in natural languages.
Grammarian level building a grammar description, which is later used on the author level. The last part of the thesis deals with a non-linguistic domain. In that experiment we try to apply functional parsing technique to the well-known problem of protein secondary structure prediction (bioinformatics).
Keywords: syntax editing, multilingual authoring, graphical user interface (GUI), interlingua, natural language processing (NLP), computational linguistics, machine translation (MT)
January 19th, 2004, 13:15
seminar by Carl-Johan Lillieroth, Computing Science, Chalmers University
HA2, Hörsalsvägen 4, Chalmers, Göteborg
|Webmaster: Catharina Jerkbrant||
Last modified: 050103