| Department of Computer and Information Science |
 |
|
|
|||
|
SaS SeminarsThis is a permanent series of open monthly seminars of the Division of Software and Systems (SaS). The objective of the seminars is to present outstanding research and ideas/problems relevant for SaS present and future activities. Two kinds of seminars are planned:
The speakers are expected to give a broad perspective of the presented research, adressing the audience with a general computer science background but possibly with no specific knowledge in the domain of the presented research. The normal length of the presentation is 60 minutes, including discussion. The SaSx seminars are coordinated by Christoph Kessler.
Spring 2012
Communication challenges in atmospheric sensing with unmanned aircraft Prof. Dr. Brown, University of Colorado at Boulder, USA Tuesday 14 feb 2012, 15:15, Room John von Neumann Abstract This talk describes the networking and communication challenges with airborne sensors in small (10kg) unmanned aircraft. In particular we discuss the roles of flight dynamics, interference, limited spectrum, and flight safety requirements. Mobility is a key feature of these networks and can be exploited to improve network performance. We also describe techniques for using so-called cognitive radios to provide sufficient spectrum for unmanned aircraft operations. Experiments with atmospheric sensing in a variety of environments will be described including a recent "tornado chasing" campaign to understand the origins of tornados. Speaker's bio Professor Brown investigates how to use adaptation in complex communication systems. His group has developed new protocols for wireless ad hoc networks and he now heads a project to test these protocols in a network of small unmanned airplanes at University of Colorado at Boulder. He has also studied cellular system design and quality of service in packet networks. Before joining the University of Colorado in 1995, he developed algorithms and architectures for hardware neural networks at Bell Communications Research and the Jet Propulsion Laboratory. He is the recipient of the NSF CAREER Award and the Colorado Junior Faculty Development Award. After the SaSx seminar there will be a short break and then another presentation (RTSLAB-seminar) by the same speaker: Random cellular deployments for analysis of multi-tier mobile radio network performance Abstract This talk addresses the carrier-to-interference ratio (CIR) and carrier-to-interference-plus-noise ratio (CINR) performance at the mobile station operating within multiple tiers of co-channel wireless networks. In each tier the base station distribution is given by the homogeneous Poisson point process. We present: (1) semi-analytical expressions for the tail probabilities of CIR and CINR; (2) a closed form expression for the tail probability of CIR in the range [1,infinity); (3) a closed form expression for the tail probability of an approximation to CINR in the entire range [0,infinity); (4) a lookup table based approach for obtaining the tail probability of CINR, and (5) a study of the effect of shadow fading and ideal sectorized antennas on the CIR and CINR. Based on these results, it is shown that, in a practical mobile radio system, the installation of additional wireless networks (microcells, picocells and femtocells) over the already existing macrocell network will always improve the CINR performance at the MS.
Research in Partial Evaluation Prof. Dr. Anders Haraldsson , IDA, Linköpings universitet Friday, 3 feb 2012, 13:15, room Alan Turing Abstract I will soon retire, so it is time again for me to make a seminar of my and others work, where I will discuss:
The seminar will be a discussion with you all, and I would like to see connections from this work to what is done today, especially optimization in compilers. Speaker's bio Anders Haraldsson is a professor at the computer science department of Linköping university. Short CV: - Datalogilaboratoriet, Uppsala university, 1969-1975. - MAI and IDA since 1976. PhDx 1977. - Division AIICS, but the founder of PELAB early 80. - Director of undergraduate studies during 80's. - Head of department during 90's. - Head of program board for all computer and media curricula at LiTHx during 00's.
To Harness The Long Tail Online, Location Does Matter As Does Time Prof. Dr. Chetan Kumar, California State University San Marcos, USA Wednesday, 25 jan 2012, 15:15, room Alan Turing Abstract: There has been a tremendous growth in the amount and range of information available on the Internet. The users' requests for online information can be captured by a long tail model. A few popular websites enjoy a high number of visitations while the majority of the rest are less frequently requested. In this study we investigate this phenomenon using real world data from ten proxy servers in four US time zones. We demonstrate that both users' physical location and time of access affect the heterogeneity of website requests. The effect may partially be explained by differences in demographic characteristics at locations and diverse user browsing behavior on weekdays and weekends. These results can be used to design better online ad pricing strategies, affiliate advertising models, and Internet caching algorithms with sensitivities to user location and time of access differences. This may be of interest to online services providers such as Google and Facebook, given the increased interest in localized and customized online deliveries. Speaker's bio: Chetan Kumar is an Associate Professor of Information Systems and Operations Management at California State University San Marcos. He received his PhDx from Purdue University. His research interests include managing computer networks, electronic commerce, web analytics, and green IT. He has published articles in refereed journals such as Decision Support Systems and Electronic Commerce Research and Applications, and in books such as Encyclopedia of E-Business Development and Management in the Global Economy. He has presented his research at conferences such as Institute for Operations Research and the Management Sciences Annual Meeting, Workshop for EBusinessx, Workshop on Information Systems and Economics, and International Conference on Information Systems Doctoral Consortium. Prior to his PhDx, he worked for Reebok International where he managed the supply chain for Asia and Africa regions. Earlier he received an MBA from Indian Institute of Management Ahmedabad and a BS in Computer Science from Bharathidasan University, Trichy, India.
Autumn 2011
System Integration at ISY, LiUx - background and status report (slides ) Dr. Ola Dahl , ISY, Linköpings universitet Wednesday 30 nov 2011, 13:15, room Alan Turing Abstract: System integration has been defined as new topic at ISY, aiming to bridge between existing disciplines such as computer engineering, communication systems, and automatic control. The work has been started, with Ola Dahl as associate professor since beginning of 2011. This talk will present system integration as of today, and two selected topics where ongoing work is done will be further described. The first topic is Energy-Aware computing. In this work, we aim at finding models and methods for optimization of the trade-off between signal processing quality and processing cost, often expressed as requirements on power consumption. Initial work, relating the underlying hardware models and the energy consumed, will be presented. It can be seen that the energy required for a certain task varies very differently with respect to the number of operations when the hardware parameters change. This means that for certain tasks, a small change in the number of operations give a large saving in power consumption, while for other tasks this sensitivity is not so large. The second topic is Requirements-driven modeling of 3GPP systems. It relates to system modeling in 3GPP systems, e.g. the currently developed systems for LTE and LTE-advanced. Our goal here is to use formal representations for selected 3GPP specifications, for the purpose of achieveing an increased system understanding, and also for making it possible to create tools, e.g. for code generation to simulators, and for code generation to products. Initial work, and ongoing discussions with Ericsson in Linköping, will be described in the talk. Speaker's bio: Ola Dahl is Associate Professor in System integration, belonging to Computer Engineering division at ISY. Before joining Linköping University, he worked at ST-Ericsson in Lund, Sweden, as senior staff engineer. He was mainly in charge of the development of virtual platforms to be able to simulate complicated hardware systems for software development in early phase. Meanwhile, he participated in system design work for advanced modem systems such as 3GPP LTE. In his earlier career, he has been working both in industry and in university, mostly in the areas of software development, real-time systems, system simulation, and control system design. He has a PhDx in Automatic Control from Lund University.
Software Engineering in the Multicore Era Dr. Victor Pankratius , Karlsruhe Institute of Technology, Germany Wednesday 23 nov 2011, 11:00 (!), room Alan Turing Abstract: Multicore processors with several cores on the same chip are standard. Parallelism is now the key to better performance on every PC, laptop, or embedded device. The great challenge is now how to make parallel programming easier for average programmers. Motivated by results from empirical studies, this talk outlines solutions and new research directions in the areas of automatic performance tuning, language design, and debugging. Speaker's bio: Dr. Pankratius heads the Multicore Software Engineering investigator group at the Karlsruhe Institute of Technology, Germany. He also serves as the elected chairman of the Software Engineering for parallel Systems (SEPARS) international working group. Dr. Pankratius' current research concentrates on how to make parallel programming easier. His work covers a range of research topics including auto-tuning, language design, debugging, software engineering in the cloud, and empirical studies. Contact him at http://www.victorpankratius.com.
Automated verification techniques for Infinite State Systems Dr. Ahmed Rezine , ESLAB, IDA, Linköpings universitet Tuesday 27 sep 2011, 13:15, room Alan Turing Abstract: I will introduce myself and my work. My research looks at ways to extend automated verification techniques in general, and Model Checking in particular, to systems with unbounded state spaces. More concretely, I concentrate on augmenting the degree of automation in the verification of imperative sequential and concurrent programs. Model checking, especially after combination with symbolic techniques, is acknowledged as a breakthrough in the automatic verification of programs with a finite number of states. Nevertheless, programs commonly exhibit state spaces that can not be a priori bounded. Possible sources for this unboundedness are concurrency, unbounded data, dynamic data-structures and recursion. The verification problem for such common programs is undecidable in general and verification algorithms are necessarily incomplete. In this context, I concentrate in my work on augmenting the degree of automation when verifying programs with some of these sources, namely: concurrency, unbounded data, and dynamic data structures. I will give examples in the presentation of the kind of properties and systems I am looking at in my work: safety, parameterized systems, heap manipulating programs, or weak memory models.
Spring 2011
Optimal Code Generation for Explicitly Parallel Processors Prof. Andreas Krall , TU Vienna, Austria Date: Tuesday, 7 june 2011 Time: 10:15 Room: Alan Turing Abstract: In this talk ongoing work from a research project with the talk title is presented. The aim of this project is to develop techniques for optimal and heuristic integrated code generation for explicitly parallel processors (EPIC). First results on register reuse scheduling are presented where spilling of registers during register allocation is minimized by a local reordering of independent operations. On average 8.9% less values are spilled resulting in 3.4% reduction of static spill cost. Other ongoing work on scheduling for clustered architectures is discussed. Speaker's biography: Since February 1995 Andreas Krall is an associate professor for computer science (Praktische Informatik) at the Institut für Computersprachen, Technische Universität Wien. Since 2002 he is also managing the Christian Doppler research laboratory ``Compilation Techniques for Embedded Processors'' which is jointly funded by government and industry (Infineon, OnDemandx Microelectronics). The main research interests of Andreas Krall are compilers and computer architecture. Current work are the development of an architecture description language with automatic generation of optimizing compilers, high performance instruction set simulators and VHDL processor descriptions. Other important topics are all kind of optimizations (instruction selection, register allocation, instruction scheduling, program analysis), static and dynamic binary translation and the Java virtual machine CACAO (www.cacaovm.org). Andreas Krall (co)authored more than 80 journal and conference articles and is a member in the ARTIST2 and HiPEACx European networks of excellence.
An End-to-End Solution for Product Quality and Reliability Dr. Xinli Gu, Huawei Technologies, USA Date: Friday May 20. Time: 13:15 Room: John von Neumann Abstract: System quality and reliability requires a complete End-to-End solution, from component design or purchase, to board and software design, board and system manufacturing, and system in-field health monitoring. Many built-in self monitors, self tests, self adjustment and self repair technologies are designed in the system. Adaptive concept is also a key to achieve the effect of the End-to-End solution. This presentation covers a best practice in industry deploying these concepts into real products with most advanced DFX technologies. Speaker's Bio: Xinli Gu is a Senior Director with Huawei Technologies, USA, leading design solution and driving corporate process for product quality and reliability. Before joining Huawei, he is a director with Cisco Systems, Inc. for more than 12 years, responsible for corporate level product quality, Time-to-Market, manufacturing test/diagnosis cost reduction, and product yield improvement. Xinli also worked for Synopsys in California and Ericsson in Sweden. He received a BScx in Computer Science from Shanghai JiaoTongx University, and MScx and PhDx in Computer Engineering from Linkoping University, Sweden. He has published over 30 technical papers and holds several US patents.
Evaluating Design Trade-offs in Customizable Processors Dr. Unmesh Bordoloi , ESLAB, IDA, Linköping university, Sweden Date: Wednesday April 27, 2011. Place: Alan Turing Time: 10:15 Abstract: The short time-to-market window for embedded systems demands automation of design methodologies for customizable processors. Recent research advances in this direction have mostly focused on single criteria optimization, e.g., optimizing performance though custom instructions under pre-defined area constraint. From the designer’s perspective, however, it would be more interesting if the conflicting trade-offs among multiple objectives (e.g., performance versus area) are exposed enabling an informed decision making. In this talk, we will present two frameworks, for uniprocessor and Multiprocessor System-on-Chips (MPSoCx), that systematically evaluate the design performance-area trade-offs. In the context of uniprocessors, we will discuss multi-tasking real-time embedded applications while for the MPSoCx setting, we will focus on multimedia streaming applications. Our proposed frameworks can efficiently and accurately evaluate the different customization choices without resorting to expensive system-level simulations. Speaker's Bio: Unmesh Bordoloi is a post‐doctoral researcher at Embedded Systems Lab, Linköping University. Prior to joining LiUx, he spent one year as a post‐doctoral researcher at the Verimag Laboratory in Grenoble, France. He obtained his PhDx from the School of Computing at the National University of Singapore in 2008. He was awarded the “President's Graduate Fellowship” and the “Sun Microsystems Ph.D. Fellowship”' for his research work at the National University of Singapore; HiPEACx Paper Award in 2009 and the Best Paper Award at 8th International Conference on Embedded and Ubiquitous Computing, 2010. His research focuses on system-level design and analysis issues like schedulability analysis, hardware/software co-design, and fault tolerance.
Self-organizing Telecom Networks Stefan Engström, Ericsson AB Date: Tuesday Apr 19, 2011. Place: Alan Turing Time: 15:15 Abstract: With the introduction of 4G in the telecom networks, the interest in self-organizing networks has suddenly awoken. The seminar briefly discusses the evolution of the mobile networks and why the operators suddenly have become interested in automatically controlling their networks. If also describes some functions to rationalize the build out and optimize the performance of the radio network.
Transactional Memory Prof. Pascal Felber , University of Neuchatel, Switzerland Date: Thursday Jan 13, 2011. Place: Alan Turing Time: 13:00 (!) Abstract: Major chip manufacturers are stirring what is perceived by many specialists as a revolution in modern computing, by changing their focus from ever higher processor speed to increased parallel processing capabilities. With multi-core and multi-processor systems becoming commonplace, applications must rely on multi-threading for performance and the lack of effective abstractions to manage the complexity of concurrent programming represents a major hurdle for software developers. Software transactional memory (STM) is a recent programming model in which concurrent threads synchronize optimistically via lightweight transactions rather than pessimistically using locks. STM has better real-time properties than lock-based synchronization primitives (e.g., there is no priority inversion problem), improves scalability for certain data access patterns, and is composable. STM provides atomicity properties that can also be used to develop robust applications. This talk will present the basic principles underlying STM, as well as recent research in building efficient STMsx.
After the SaSx seminar, there will also be another presentation (from 14:00, same room, as RTSLAB seminar) by the same speaker: SPLAY: Distributed Systems Evaluation Made Simple Date: Thursday Jan 13, 2011. Place: Alan Turing Time: 14:00 Abstract: This talk will present SPLAY, an integrated system that facilitates the design, deployment and testing of large-scale distributed applications. Unlike existing systems, SPLAY covers all aspects of the development and evaluation chain. It allows developers to express algorithms in a concise, simple language that highly resembles pseudo-code found in research papers. The execution environment has low overheads and footprint, and provides a comprehensive set of libraries for common distributed systems operations. SPLAY is freely available from http://www.splay-project.org/. Speaker's bio: Pascal Felber received his M.Sc. and Ph.D. degrees in Computer Science from the Swiss Federal Institute of Technology. From 1998 to 2002, he has worked at Oracle Corporation and Bell-Labs (Lucent Technologies) in the USA. From 2002 to 2004, he has been an Assistant Professor at Institut EURECOM in France. Since October 2004, he is a Professor of Computer Science at the University of Neuchâtel, Switzerland, working in the field of dependable and distributed systems. He has published over 80 research papers in various journals and conferences.
Testing Web Applications with the Atomic Section Model Prof. Jeff Offutt , George Mason University Date: Tuesday Jan 11, 2011. Place: Alan Turing Time: 13:15 Abstract: Web software applications are complex, sophisticated programs that use novel computing technologies. The widespread use of the Web to deploy software means faults can have far reaching consequences. This is particularly important given the current use of web software to control critical infrastructure. Although web applications share some characteristics with client-server, distributed, and traditional programs, they also introduce novel features. Web software introduces new types of execution flow, new levels of variable scoping, the ability for users to directly change the potential flow of execution, dynamic creation of parts of the user interface, and distributed integration. These allow the potential control flow to vary with each execution, preventing the possible control flows from being determined. This talk will present a novel modeling technique for web software that describes possible user interactions. The talk will present results from using this model to design tests and suggest other uses of the model, including maintenance and design. Speaker's Biography Dr. Jeff Offutt is Professor of Software Engineering at George Mason University. He has invented numerous test strategies, published over 130 refereed research papers, and is co-author of the textbook Introduction to Software Testing. He is editor-in-chief of Wiley's journal of Software Testing, Verification and Reliability; steering committee chair for the IEEE International Conference on Software Testing, Verification, and Validation; and was program chair for ICST 2009. He has consulted with numerous companies on software testing, usability, and software intellectual property issues. Offutt is on the web at http://www.cs.gmu.edu/~offutt/.
Autumn 2010
Worst-Case Analysis for Power-Awareness and Resource Sharing Dr. Jian-Jia Chen, Karlsruhe Institute of Technology, Germany Date: Thursday Dec 16, 2010. Place: Alan Turing Time: 10:15 Abstract: Embedded systems have been widely adopted and deployed in many application domains. The worst-case response time is a non-functional but important requirement for many applications to meet the needs of performance requirements. This talk consists of two parts in this research direction. The first part will present how to analyze the worst-case peak temperature of workload conserving scheduling and the worst-case behavior of on-line dynamic voltage scaling (DVS) scheduling along with customization. The second part will present how to analyze the worst-case response time for real-time tasks with shared resources in multicore era. Different resource access arbiters and different resource access models will be discussed. Speaker's Biography: Dr. Jian-Jia Chen has been a Juniorprofessor in Department of Informatics at Karlsruhe Institute of Technology (KIT) since May, 2010. He received his Ph.D. degree from Department of Computer Science and Information Engineering, National Taiwan University, Taiwan in 2006. He received his B.S. degree from the Department of Chemistry at National Taiwan University 2001. After finishing the compulsory civil service in Dec. 2007, between Jan. 2008 and April 2010, he was a postdoc researcher at Computer Engineering and Networks Laboratory (TIK) in Swiss Federal Institute of Technology (ETH) Zurich, Switzerland. His research interests include real-time systems, embedded systems, reliable and dependable systems, energy-efficient scheduling, power-aware designs, temperature-aware scheduling, and distributed computing. He has received two best paper awards, and published more than 70 papers in international journals and conferences. He has served as a committee member in Members-at-Large in ACM SIGDA Low-Power Technical Committee since Aug. 2010, TPC members in several international conferences in real-time and embedded systems, such as RTSS, RTAS, RTCSA, DATE, ICCAD, etc., and Guest Editor in IEEE Transactions on Industrial Informatics (TII) and ACM Transactions on Embedded Computing Systems (TECS).
Attacking the Performance/Productivity Challenge: Computer Synthesis of Computational Programs Prof. Markus Püschel , ETH Zürich, Switzerland Date: Monday Dec 6, 2010. Place: Alan Turing Time: 10:15 Abstract: Writing fast software has become extraordinarily difficult. For optimal performance, programs and their underlying algorithms have to be adapted to take full advantage of the platform’s parallelism, memory hierarchy, and available instruction set. To make things worse, the best implementations are often platform-dependent and platforms are constantly evolving, which quickly renders libraries obsolete. In this talk we present Spiral (www.spiral.net ), a domain-specific program generation system for important functionality used in signal processing, communication, and scientific computing including linear transforms and filters, Viterbi decoders, and basic linear algebra routines. Spiral completely replaces the human programmer. For a desired function, Spiral generates alternative algorithms, optimizes them, compiles them into programs, and “intelligently” searches for the best match to the computing platform. The main idea behind Spiral is a mathematical, declarative, domain-specific framework to represent algorithms and the use of rewriting systems to generate and optimize algorithms at a high level of abstraction. Optimization includes parallelization for vector architectures, shared and distributed memory platforms, and even FPGAsx. Experimental results show that the code generated by Spiral competes with, and sometimes outperforms, the best available human-written code. Spiral has been used to generate part of Intel’s commercial libraries IPP and MKL. Speaker Biography: Markus Püschel is a Professor of Computer Science at ETH Zürich, Switzerland. Before, he was a Professor of Electrical and Computer Engineering at Carnegie Mellon University, where he still has an adjunct status. He received his Diploma (M.Sc.) in Mathematics and his Doctorate (Ph.D.) in Computer Science, in 1995 and 1998, respectively, both from the University of Karlsruhe, Germany. From 1998-1999 he was a Postdoctoral Researcher at Mathematics and Computer Science, Drexel University. From 2000-2010 he was with Carnegie Mellon University, and since 2010 he has been with ETH Zurich. He was an Associate Editor for the IEEE Transactions on Signal Processing, the IEEE Signal Processing Letters, was a Guest Editor of the Proceedings of the IEEE and the Journal of Symbolic Computation, and served on various program committees of conferences in computing, compilers, and programming languages. He is a recipient of the Outstanding Research Award of the College of Engineering at Carnegie Mellon and the Eta Kappa Nu Award for Outstanding Teaching. He also holds the title of Privatdozent at the University of Technology, Vienna, Austria. In 2009 he cofounded Spiralgen Inc. More information is available at www.ece.cmu.edu/~pueschel .
Evaluation metric for infrastructure to access IC internals Dr. Urban Ingelsson , Embedded Systems Lab, IDA, Linköping University Date: Monday Nov 22, 2010. Place: Alan Turing Time: 15:15 Abstract: We use and depend more and more on computer systems. We use mobile phones, desktops and laptops. And we depend on computer systems in cars, airplanes and telecommunication systems. These computer systems are composed of integrated circuits (ICsx) containing billions of transistors that are squeezed into dies with sizes of a few square centimetres. Manufacturing of ICsx is cumbersome, complicated and far from perfect. Therefore there is a need to access the internals of ICsx during manufacturing, for testing and debugging, as well as during operation, for in-field test. Today, IC design companies implement ad-hoc solutions to provide the possibility to access the internals of ICsx. The basic approach is to design the IC with built-in instrumentation such as sensors, monitors, status registers, etc.. The interface of the instruments and the methodology for connecting to them are ad-hoc since no standard exist. In fact, without a standard no IC design tool vendor can develop the necessary tools to automate the process of designing ICsx with test features. However, the methodology for connecting the instruments to the IC terminals is undergoing standardisation, with a standard proposal, IEEE P1687, currently under review. In anticipation of P1687, we contribute to the development of the tools and methodologies required to replace the previous ad-hoc solutions. We have developed a metric to evaluate a P1687 network with respect to the access time to the instruments. Concerning our metric, we show that the instrument access time cannot be calculated by a closed form equation. Therefore, we present two algorithms corresponding to two types of instrument access schedules. Our analysis shows that alternative P1687 networks, for connecting to the same set of instruments, can be compared with respect to the overhead that is specific to P1687. Speaker Biography: Dr. Urban Ingelsson graduated with a M.Sc. degree in Computer Science and Engineering from Linköping University in 2005, a study which involved a year as exchange student at RWTH Aachen (Germany) and an internship at Philips Research (Eindhoven, the Netherlands). In 2009, he graduated with a Ph.D. in Electronics and Computer Science from the University of Southampton (UK) where he was supervised by Prof. Bashir M. Al-Hashimi. He is currently employed as a post-doctoral researcher in ESLAB, working for Dr. Erik Larsson.
Acumen: A Language for Modeling Cyber-Physical Systems Prof. Walid Taha , Halmstad and Rice University Date: Thursday Sep 30, 2010. Place: Alan Turing Time: 16:15 Abstract: Cyber-physical systems comprise digital components that directly interact with a physical environment. Specifying the behaviordesired of such systems requires analytical modeling of physical phenomena. Similarly, testing them requires simulation of continuous systems. While numerous tools support later stages of developing simulation codes, there is still a large gap between analytical modeling and building running simulators. This gap significantly impedes the ability of scientists and engineers to develop novel cyber-physical systems. We propose bridging this gap by automating the mapping from analytical models to simulation codes. Focusing on mechanical systems as an important class of physical systems, we study the form of analytical models that arise in this domain, along with the process by which domain experts map them to executable codes. We show that the key steps needed to automate this mapping are 1) a light-weight analysis to partially direct equations, 2) a binding-time analysis, and 3) symbolic differentiation. In addition to producing a prototype modeling environment, we highlight some limitations in the state of the art in tool support of simulation, and suggest ways in which some of these limitations could be overcome. Speaker Biography: Walid Taha is an professor at Halmstad University, and adjunct professor at Rice University.
(Previously associated professor at Rice)
Development of Automotive Electronics: Perspective and Challenges Dr. Luis Alejandro Cortes, Volvo AB Date: Wednesday Sep 29, 2010. Place: Alan Turing Time: 13:15 Abstract: Today, a modern vehicle contains a myriad of computer-controlled functions on-board, ranging from traction and steering features (such as fuel injection control and antilock braking) to telematics and comfort features (such as navigation systems and climate control). Dozens of computers (known as Electronic Control Units-ECUsx) running millions of lines of software code are interconnected via a number of communication networks. Since the 1970s the trend has been to enhance or replace mechanical or hydraulic systems by electronic systems. The advances in semiconductor technology have provided the means to fabricate smaller and cheaper electronic devices that perform more complex functions at higher speeds. This fact together with the huge potentials due to software technologies have made it possible to integrate complex functions that assist the driver, improve the vehicle performance and efficiency, and increase the safety as well as the level of comfort. However, together with the new opportunities by integrated electronics in the vehicle, new challenges have come up. This seminar provides an overview of the current situation of the automotive industry and presents a high-level perspective of the main issues in the development of automotive electronics. Also it is discussed general and specific challenges that go hand in hand with the opportunities provided by vehicle electronics. Speaker's bio: Luis Alejandro Cortes works currently as Group Manager of ''Vehicle Electronics'' at Volvo Technology and has several years of both academic experience in applied research and industrial experience in the development of automotive electronic systems, recently having a leading role in the development of a completely new electrical and electronic architecture for the next generation of trucks of the Volvo Group. He holds a Ph.D. degree in Computer Science from Linköping University where his research focused on real-time embedded systems.
Spring 2010
New Techniques for Functional Test of Systems-on-Chip Prof. Matteo Sonza Reorda, Politecnico di Torino, Italy Date: Friday June 11, 2010. Place: Grace Hopper Time: 10:15 Abstract: End of production test of Integrated Circuits is currently performed mainly resorting to structural test. However, some limitations in the defect coverage which can be achieved in this way, combined with some constraints coming from the SoCx design paradigm are pushing companies to also adopt functional test as a complementary test phase. This trend is raising the issue of devising efficient techniques for generating suitable functional test stimuli for the different modules that are usually found in a SoCx. Moreover, some reduced Design for Testability structures are sometimes introduced in SoCsx to better support functional test. The seminar will overview the state-of-the-art in functional test for SoCx and discuss the latest advancements and current activities in the area. Bio: Matteo SONZA REORDA took his MS degree in Electronic Engineering from Politecnico di Torino (Torino, Italy) in 1986, and the PhDx degree in Computer Engineering from the same Institution in 1990. Since 1990 he works with the Department of Computer Engineering and Automation of Politecnico di Torino, where he is currently a Full Professor. His main research interests include Testing and Fault Tolerant design of Electronic Systems. He has published more than 250 papers on international journals and conference proceedings. He is a Senior Member of IEEE. He has been the General (1998) and Program Co-chair (2002, 2003) of the IEEE International On-line Testing Symposium (IOLTS), the Program Chair of the IEEE Workshop on Design and Diagnostics of Electronic Circuits & Systems (DDECS) in 2006, and the General Chair of the IEEE European Test Symposium (ETS) in 2008. Currently, he is the chair of the European Test Technology Technical Council (eTTTC).
Mobile Agents Technology as an approach to Delay/Disruption Tolerant Networking Date: June 8, 2010. Place: Alan Turing Time: 16:15 Joan Borrell , Autonomous University of Barcelona Abstract: Mobile agents, understood as autonomous elements with negotiation capabilities and the ability of moving from one location to another during their execution, can be used to provide a Delay/Disruption Tolerant approach for distributed applications. As an example, the MAETT (Mobile Agent Electronic Triage Tag) application, developed by our group, will be presented. MAETT considers an emergency scenario, with several medical personnel carrying mobile terminals (PDAsx) equipped with JADE mobile agent platforms. Medical personnel classify the victims according to a medical triage protocol, trying to accelerate the transport of the most urgent cases to the field hospital or coordination point that serves the emergency. In MAETT, mobile agents act as data mules to transport triage tag data of the victims between agent platforms, without requiring any underlying network infrastructure, neither any end-to-end connectivity. Routing is opportunistic, and based on the estimated return time of each person or vehicle in the emergency zone to the coordination point. Besides MAETT initial configuration, our recent activities to improve the application will also be commented. On the one hand, to make MAETT more dynamic, we are replacing the initial RFIDsx associated to the victims with wireless sensors running Agilla mobile agents. On the other hand, to ease the collaboration between the different rescue and medical teams in the emergency scenario, we are designing a fuzzy attribute conversion mechanism to enable an interoperable access control in such a multi-domain environment.
Power-Efficient Fault Tolerant Microarchitecture for Chip Multiprocessors Virendra Singh, IIScx Bangalore Date: June 7, 2010. Place: Alan Turing Time: 15:15 Abstract: Relentless scaling of silicon fabrication technology coupled with lower design tolerances are making ICsx increasing susceptible to wear-out related permanent faults as well as transient faults. A well known technique for tackling both transient and permanent faults is redundant execution, specifically space redundancy, wherein a program is executed redundantly on different processors, pipelines or functional units and the results are compared to detect faults. In this presentation, we describe a power-efficien architecture for redundant execution on chip multiprocessors (CMPsx) which when coupled with our per-core dynamic voltage and frequency scaling (DVFS)algorithm significantly reduces the power overhead of redundant execution without sacrificing performance. Using cycle accurate simulation combined with an architectural power model we estimate that our architecture reduces dynamic power dissipation in the redundant core by an mean value of 76% with an associated mean performance overhead of only 1.2%. We also present an extension to our architecture that enables the use of cores with faulty functional units for redundant execution without a reduction in transient fault coverage. This extension enables the usage of faulty cores, thereby increasing yield and reliability with only a modest power-performance penalty over fault-free execution. Bio: Virendra Singh obtained Ph.D in Computer Science from Nara Institute of Science and Technology (NAIST), Nara, Japan in 2005. He receive B.E and M.E in Electronics and Communication Engineering from Malaviya National Institute of Technology (MNIT), Jaipur, in 1995 and 1997 respectively. Currently, he is a faculty member at Supercomputer Education and Research Centre (SERC), Indian Institute of Science (IIScx), Bangalore since May 2007. He served Central Electronics Engineering Research Institute (CEERI), Pilani (Rajasthan), as a Scientist for 10 years prior to join IIScx. He also served as a faculty at Department of Computer Science, Banasthali University from June 1996 to March 1997. His research interests are testing and verification of high performance processors, VLSI testing, formal verification, fault tolerant computing, high performance computer architecture, embedded system design, and design for reliability, complexity of test generation algorithms. He is a member of the IEEE, the ACM, the VSI, and life member of the IETE.
Arbutus: Reliable and Scalable Data Collection in Low-Power Sensor Networks Daniele Puccinelli , Univ of Applied Sciences of Southern Switzerland Date: April 16, 2010. Place: Donald Knuth Time: 15:15 Abstract: In data collection applications of low-end sensor networks, a major challenge is ensuring reliability without a significant goodput degradation. Short hops over high-quality links minimize per-hop transmissions, but long routes may cause congestion and load imbalance. Longer links can be exploited to build shorter routes, but poor links may have a high energy cost, and there exists a complex interplay among routing performance (reliability, goodput, energy-efficiency), link estimation, congestion control, and load balancing. We illustrate the design of a novel routing architecture, Arbutus, that leverages on this interplay, and we present an extensive experimental evaluation on testbeds of 100-150 Berkeley motes. Speaker's profile: Daniele Puccinelli is a postdoc at University of Applied Sciences of Southern Switzerland at Lugano. He holds a PhDx in Electrical Engineering from the University of Notre Dame, Notre Dame, Indiana, USA, 2008.
Multimedia Power Management on a Platter: From Audio, to Video and Games Date: Wednesday, February 24th, 10:15. Place: Alan Turing TIME: 10:15 Prof. Samarjit Chakraborty, TU München, Germany Abstract: Multimedia applications today constitute a sizeable workload that needs to be supported by a host of mobile devices ranging from cell phones, to PDAsx and portable game consoles. Battery life is a major design concern for all of these devices. In this talk I will discuss some of our recent efforts towards developing application-specific power management schemes for a variety of multimedia applications. Speaker's Bio: Samarjit Chakraborty is a Professor of Electrical Engineering at the Technical University of Munich, where he heads the Institute for Real-Time Computer Systems. He obtained his Ph.D. in Electrical and Computer Engineering from ETH Zurich in 2003. Prior to joining TU Munich, from 2003 -- 2008 he was an Assistant Professor of Computer Science at the National University of Singapore. His research interests are primarily in system-level power/performance analysis of real-time and embedded systems.
GPU architectures and OpenCLx: What's important and why Date: Feb 03 2010 Place: Alan Turing Time: 10:15 Dr. David Black-Schaffer, Uppsala university, Sweden Abstract: Today everyone is positioning GPUsx for general purpose computing. They claim that you can get 10-100x speedups over conventional CPUsx, and sometimes they're even right. However, to get the most out of current- (and next-) generation GPUsx, one needs to understand the architectural differences and how they effect your choice of algorithm. In this talk I will cover GPU architecture in comparison to current CPUsx, discuss the implications for getting good performance, and introduce OpenCLx as a general-purpose programming language for accessing GPUsx and CPUsx today. Speaker's profile: David Black-Schaffer received his PhDx in electrical engineering from Stanford University in 2008 focusing on parallel programming systems for many-core processors. After that he worked for at Apple designing and developing the first implementation of the new OpenCLx specification for heterogeneous parallel processing on CPUsx and GPUsx. Since the fall of 2009 he has been working as a postdoctoral researcher in the Uppsala Architecture Research Team at Uppsala University.
Autumn 2009
Testing of 3D Integrated Circuits: Challenges and Emerging Solutions Date: Thursday, Dec 17, 2009 Place: Alan Turing Time: 10:15 Prof. Krishnendu Chakrabarty , Duke university, USA Abstract Three-dimensional (3D) integrated circuits (IC) promise to overcome barriers in interconnect scaling, thereby offering an opportunity to get higher performance using CMOS technology. Despite these benefits, testing remains a major obstacle that hinders the adoption of 3D integration. Test techniques and design-for-testability (DfTx) solutions for 3D ICsx have remained largely unexplored in the research community, even though experts in industry have identified a number of test challenges related to the lack of probe access for wafers, test access to modules in stacked wafers/dies, thermal concerns, test economics, and new defects arising from unique processing steps such as wafer thinning, alignment, and bonding. In this talk, the speaker will present an overview of 3D integration, its unique processing and assembly steps, testing and DfTx challenges, and some of the solutions being advocated for these challenges. The talk will focus on the use of through-silicon-vias for 3D integration, and related processing steps such as via-first/via-last assembly, face-to-face bonding, and face-to-back bonding. The implications of these processing steps on testing will also be discussed. Speaker's Profile: Krishnendu Chakrabarty received the B. Tech. degree from the Indian Institute of Technology, Kharagpur, in 1990, and the M.S.E. and Ph.D. degrees from the University of Michigan, Ann Arbor, in 1992 and 1995, respectively. He is now Professor of Electrical and Computer Engineering at Duke University. He is also a member of the Chair Professor Group (honorary position) in Software Theory at the School of Software, Tsinghua University, Beijing, China. Prof. Chakrabarty is a recipient of the National Science Foundation Early Faculty (CAREER) award, the Office of Naval Research Young Investigator award, the Humboldt Research Fellowship from the Alexander von Humboldt Foundation, Germany, and several best papers awards at IEEE conferences. His current research projects include: testing and design-for-testability of integrated circuits; digital microfluidics and biochips, circuits and systems based on DNA self-assembly, and wireless sensor networks. He has authored nine books on these topics (including two in press), published over 320 papers in journals and refereed conference proceedings, and given over 130 invited, keynote, and plenary talks.
Interoperable agent mobility based on the IEEE-FIPA standards Date: Monday, Nov 16, 2009 Place: Alan Turing Time: 15:15 Jordi Cucurull Juan, IDA, Linköpings universitet Abstract Mobile agents are autonomous software entities driven by a set of goals and tasks. Reactivity, proactivity, social ability, autonomy, and the ability to move to different network locations, make mobile agents highly suitable for the autonomous and context aware processing of distributed information. Agent mobility has been proposed for homogeneous environments. The deployment of agent mobility in heterogeneous environments has been hindered by the absence of a common set of interoperation rules and ontologies for different agent middlewares. In this seminar an interoperable agent migration model based on the communication standards of the IEEE-FIPA organisation will be introduced. The approach encompasses the definition of several specifications to enable the migration of agents among heterogeneous environments. The result is an architecture that provides a basic and extensible common migration process that is completely independent of any specific agent middleware implementation. The architecture is flexible enough to support different kinds of migration methods and future upgrades.
Spring 2009
Stochastic Routing for Delay Tolerant Networks Date: Tuesday, June 1, 2009 Place: Visionen Time: 10:15 Prof. Zygmunt J. Haas , Cornell University, USA Abstract In this talk, I will discuss selected research results in the area of Stochastic Routing. Especially, I will concentrate on the use of Stochastic Routing as it applies to Delay/Disruption Tolerant Networks (DTNsx). DTNsx are useful for applications with lenient requirements on message latency. Stochastic Routing is especially well suited for mobile DTNsx. We demonstrate and compare the operation of some of the Stochastic Routing schemes and discuss a number of potential applications. Gossiping, an example of Stochastic Routing, is a techniques where each node resends the received message with some probability. In fact, flooding is a limiting case of Gossiping, where the retransmission probability equals 1. Numerous variants of Gossiping have been proposed and optimized to implement efficient broadcasting, multicasting, and anycasting. Epidemic Routing, another example of Stochastic Routing schemes, has been suggested as a protocol for DTNsx. Unrestricted Epidemic Routing results in shortest packet delivery time and high packet delivery probability at the destination nodes. However, this comes at the cost of excessive number of packet copies in the network, which leads to wasteful energy consumption at the nodes. I will introduce and present the performance of several schemes which, in different ways, restrict Epidemic Routing in the number of generated packet copies. The schemes are compared in regards to the tradeoff between energy consumption and delivery delay, while maintaining fixed delivery rate. Another drawback of Unrestricted Epidemic Routing is that the energy consumption is unequal at the different network nodes. Consequently, the system's lifetime is reduced. I will also discuss several approaches to extend and to maximize the system lifetime of Epidemic Routing. Speaker's profile: Prof. Zygmunt J. Haas received his Ph.D. in 1988 from Stanford University, at which time he joined the AT&T Bell Laboratories, pursuing research in wireless communications, mobility management, fast protocols, optical networks, and optical switching. In 1995, he joined the faculty of the School of Electrical and Computer Engineering at Cornell University. He heads the Wireless Network Laboratory (wnl.ece.cornell.edu), a research group with extensive contributions in the area of Ad Hoc Networks and Sensor Networks. Dr. Haas is a Fellow of the IEEE and an author of over 200 technical conference and journal papers. He holds eighteen patents in the areas of wireless networks and wireless communications, optical switching, optical networks, and high-speed networking protocols. He has organized numerous workshops, chaired and co-chaired several key conferences in the communications and networking areas, and delivered many tutorials at major IEEE and ACM conferences. His interests include: mobile and wireless communication and networks, modeling and performance evaluation of large and complex systems, and biologically-inspired networks.
Engaging students in the free and open source software (FOSS) movement Date: Thursday, May 7, 2009 Place: Alan Turing Time: 13:15 Ralph Morelli , Trinity College, USA Abstract Although it was started by computer programmers and software engineers, the free and open source software (FOSS) movement has now spread throughout the modern Internet society. The FOSS ideas of open and shared content and its collaborative and peer-based methodology have now spawned a vast number of community-based, free and open collaborative efforts ranging from the creation of repositories of human knowledge (Wikipedia) to distribution of architectural plans (Architects for Humanity) to the publication of scientific research (PLoSx). It is important for computing education and for society in general that we harness our students' interests in free and open culture and introduce the FOSS model into our curricula. This talk will describe some of the ways we are trying to incorporate the study and practice of FOSS into courses and independent studies and will make the case for getting students engaged in building FOSS that benefits society.
Introduction to Constraint Satisfaction Complexity and Applications in Spatial and Temporal Reasoning Date: Tuesday, Apr 21, 2009 Place: Alan Turing Time: 15:15 Dr. Manuel Bodirsky , Ecole Polytechnique, Laboratoire d'Informatique (LIX), Palaiseau, France Abstract: The constraint satisfaction framework is known to be sufficiently rich and expressive for representing problems occurring in a wide variety of industrial and scientific applications. This has led to the development of constraint programming languages and very successful commercial constraint solvers. Due to the importance of the constraint satisfaction problem and the fact that it is in general a computationally hard problem, much research has been devoted to understanding its computational complexity and finding restricted cases that can be solved efficiently. Qualitative temporal and spatial reasoning is a well-established area in artificial intelligence. The computational complexity of various reasoning tasks has been a central topic in this area, and there are many surprisingly rich formalisms where reasoning is polynomial-time tractable. We apply techniques from constraint satisfaction complexity to give systematic complexity results for temporal and spatial reasoning formalisms. In particular, we use the so-called universal-algebraic approach that was originally developed for finite domain constraint satisfaction problems, and generalize it to study infinite domain constraint satisfaction problems.
Register Optimisation and Instruction Level Parallelism Date: Monday, Feb 16, 2009 Place: Alan Turing Time: 10:15 Dr. Sid Touati , INRIA and Universite de Versailles, France Abstract: Registers are the fastest addressable memory visible to a program. At the same time, registers constitute the most expensive memory, consequently few registers exist inside processors. The effective use of registers is one of the most important code optimisations for all modern processor architectures, and register optimisation is an active area of research in compiler technology. The topic of register allocation involves the attention of numerous efforts bringing many fundamental advances in compilation. This talk will make a panorama on the topic, explain the subtleties in the problems of register optimisation and the knowledge we have on them. We will cover the register allocation problems for sequential programs as well as the recent advances for instruction level parallelism. Speaker's Profile: Sid TOUATI is an assistant professor at the University of Versailles Saint-Quentin en Yvelines (France). His main scientific interests are fundamental and practical research topics about code analysis and optimisation, instruction level parallelism, and compilation techniques for embedded processors. At present, he is managing some research and Ph.D. projects on these topics, with the active collaboration of INRIA and ST-microelectronics.
Modeling Public Safety Scenarios to Evaluate Wireless Communication Systems Date: Monday, Feb 9, 2009 Place: Alan Turing Time: 15:15 Dr. Nils Aschenbruck , Universität Bonn, Germany Abstract: When creating a scenario for performance evaluation of communication systems, modelling mobility and traffic is an important task. The results of the evaluation strongly depend on the models used. Typical assumptions of many models are uniform selection of destinations, nodes are allowed to move over the whole simulation area, and nodes are part of the network all the time (are not switched off and do not leave the network). An analysis in civil protection maneuvers provides characteristics influencing network performance in public safety communication networks like heterogeneous area-based movement, obstacles, joining/leaving of nodes, and non-uniformly distributed group communication. These characteristics differ significantly from the typical assumptions. The talk will present new models that realistically represent traffic and movement in disaster area scenarios. The new models show specific characteristics. Furthermore, the results of simulative network performance analysis are affected.
Searching for Contents in Mobile DTNsx Date: Tuesday, Jan 28, 2009 Place: Alan Turing Time: 15:15 Prof. Dr. Jörg Ott , Helsinki University of Technology, Finland Abstract: Delay-tolerant Networking (DTN) provides a platform for applications in environments where end-to-end paths may be highly unreliable or do not exist at all. In many applications such as distributed wikis or photo sharing, users need to be able to find content even when they do not know an unambiguous identifier. In order do bring these applications to the domain of DTNsx, a search scheme is required that works despite the unreliable network conditions. We introduce a search scheme that makes no assumptions about the underlying routing protocols and the format of search requests. We evaluate different algorithms for forwarding and terminating search queries, using simulations with different classes of DTN routing protocols for different mobility scenarios.
Autumn 2008
On Improving Real-Time Observability in Silicon Debug Date: Tuesday, Nov 11, 2008 Place: Alan Turing Time: 15:15 Nicola Nicolici, McMasterx University, Canada Abstract: To identify design errors that escape pre-silicon verification, silicon debug is becoming an important step in the implementation flow of digital integrated circuits. Embedded logic analysis is emerging as an alternative to scan chains for improving real-time observability during in-system silicon debugging. In this talk we discuss several basic techniques used in silicon debug, as well as some recent research on embedded logic analysis. Speaker's Profile: Nicola Nicolici is an Associate Professor in the Department of Electrical and Computer Engineering at McMasterx University, Canada. His research interests are in VLSI test and silicon debug.
MVC: 30 years later, the other shoe drops Date: Friday, Oct 3, 2008 Place: Alan Turing Time: 10:15 Jim Coplien , Gertrud&Cope, Mørdrup, Denmark Abstract: To its end user, software is not a product, but a service. Procedural programming made it possible to reason about these services and their logic in which most problems could be found in low-cost but dutiful desk checks. The main correlation-like entity was the procedure, which could be assembled to collect large numbers of activation record instances into a few archetypical structures. In 1967, the ability to do this was taken away by object-oriented programming, which encouraged a style of programming where this user-focused structure was subordinated to the user's cognitive model of the static world: of its objects. The algorithmic view was further muddled by inclusion polymorphism. The Smalltalk anthropomorphic view and ever small method sizes made it necessary to understand dozens of atomic algorithms to understand even the simplest functionality. Progress in methodologies reduced this static view to an even more over-simplified and more static view in classes, the almost final step in removing our ability to reason about the end user system model. The final step was Agile methods, which focus on the customer -- the middleman -- instead of the end user, enabling a product focus instead of a service focus. This is even celebrated as a good thing. Piecemeal, technology has slowly staggered roughly in the direction of the more primordial object view, and AOP has struggled to restore some of the algorithmic view. Roles and role-based modeling have brought back a bit more dynamic view of the system; we find their incarnation in Java and C# interfaces. There is renewed interest in dynamic programming languages and in the kind of flexibility one finds in traits. Trygve Reenskaug has combined these techniques and brought us full circle in the DCI paradigm. The "D" is for data modeling: what we know as traditional objects, though bereft of knowledge about scenarios. It captures the static structure of objects and their references on the heap. The "C" is for context: the mapping of roles onto objects on a per-use-case basis, implemented as a dictionary. The "I" is for interaction: an algorithm of a stateless role, written in terms only of other roles, that defines in readable terms what the system does. Object dynamics can be captured in interaction roles and melded with classes who use the roles as traits; interaction dynamics appear in a context object generated anew for every use case; and structural dynamics appear as references between elements of object data. This design approach expresses several important correlations that long have been missing in object orientation. Rather than unifying all algorithmic cross-cutting into Aspects, it teases out important facets into the context and interaction, with the object model a third correlation that is usually presumed to be the base partitioning. These correlations conceivably compose in uniform and predictable ways because of their grounding in simple object concepts such as interfaces and classes, rather than cutpoints or wrappers and whoppers. It is an extended subset of multi-paradigm design, incorporating important elements of the procedural and object paradigms. Speaker's Profile: Jim ("Cope") Coplien is a Software Architecture and Agile Consultant at Gertrud&Cope in Denmark. He has a 25-year history as an "early adopter" and innovator behind several strategic innovations in software: his C++ Idioms book was one of the major sources for Design Patterns; his work on Organizational Patterns was one of the foundations of the structural components of XP and was the inspiration for Scrums. His books cover areas as diverse as C++ programming, software design, and organizational design. He has started writing a book on Agile software development. His current professional focus areas include Lean software architecture, highlighting the challenges of test-driven development, and Scrum process improvement using Organizational Patterns. His current day-to-day work includes architecture reviews, coding, and helping organizations work more effectively in lean economic conditions through process improvement and reduction of waste. His current hobby is creating advanced (housing) architecture CAD tools based on pattern languages. He lives with his wife and son in Mørdrup, Denmark. When he grows up, he wants to be an anthropologist.
Spring 2008
Multi-Paradigm Modelling, and the quest for tool support Date: Wednesday, June 4, 2008 Place: John von Neumann Time: 15:15 Prof. Dr. Hans Vangheluwe , McGillx University, Montréal, Québec, Canada Abstract:Models are invariably used in Engineering (for design) and Science (for analysis) to precisely describe structure as well as behaviour of systems. Models may have components described in different formalisms, and may span different levels of abstraction. In addition, models are frequently transformed into domains/formalisms where certain questions can be easily answered. We introduce the term "multi-paradigm modelling" to denote the interplay between multi-abstraction modelling, multi-formalism modelling and the modelling of model transformations. The presentation will start with some ancedotal evidence of the need for multi-paradigm modelling. Subsequently, the foundations of multi-paradigm modelling will be presented. It will be shown how all aspects of multi-paradigm modelling can be explicitly (meta-)modeled enabling the efficient synthesis of (possibly domain-specific) multi-paradigm (visual) modelling environments. We have implemented our ideas in the tool AToM^3 (A Tool for Multi-formalism and Meta Modelling). AToM^3 will be introduced by means of a simple example. Finally, an overview will be given of current and future challenges of multi-paradigm modelling. Speaker's Profile:Hans Vangheluwe is an Associate Professor in the School of Computer Science at McGillx University, Montréal, Canada. He holds a D.Sc. degree, as well as M.Sc. degrees in Computer Science, and Theoretical Physics, all from Ghent University in Belgium. He has been a Research Fellow at the Centre de Recherche Informatique de Montréal, Canada, the Concurrent Engineering Research Center, WVU, Morgantown, WV, USA, at the Delft University of Technology, The Netherlands, and at the Supercomputing and Education Research Center of the Indian Institute of Science (IIScx), Bangalore, India. At McGillx University, he teaches Modelling and Simulation, as well as Software Design. He also heads the Modelling and Simulation and Design (MSDL) research lab. He has been the Principal Investigator of a number of research projects focused on the development of a multi-formalism theory for Modelling and Simulation. Some of this work has led to the WEST++ tool, which was commercialised for use in the design and optimization of bioactivated sludge Waste Water Treatment Plants. His current interests are in domain-specific modelling and simulation. The MSDL's tool AToM^3 (A Tool for Multi-formalism and Meta-Modelling) developed in collaboration with Prof. Juan de Lara uses meta-modelling and graph grammars to specify and generate domain-specific environments. Recently, he has applied model-driven techniques in a variety of areas such as modern computer games, dependable and privacy-preserving systems (the Belgian electronic ID card), embedded systems, and to the design and synthesis of advanced user interfaces.
Scalable Publish/Subscribe Infrastructures Date: Monday, April 14, 2008 Place: Alan Turing Time: 10:15 Prof. Roberto Baldoni, Univ. of Rome La Sapienzia, Italy Abstract: This talk will address recent advances in building scalable publish/subscribe communication systems as infrastructures for mature and novel large scale distributed applications (e.g., internet-based applications, scalable QoSx applications and Enterprise Data Centers Monitoring). In particular event routing schemes and p2p overlay networks will be analyzed as technology enablers for the construction of such publish/subscribe systems. Three publish/subscribe systems will be outlined and compared with respect to event routing and p2p overlay layers. The talk also will look at future applicative scenarios where these infrastructures are expected to be employed.
Reasoning on the Web: Why and how it is changing the making of computer and other science Date: Wednesday, February 20, 2008 Place: Alan Turing Time: 13:15 Prof. Francois Bry, Ludwig Maximilian University of Munich, Germany Abstract:Many researchers candidly admit, if asked, that they no longer use traditional libraries and not professional address books. Instead, they rely on search engines. Indeed, with a bit of practice, one can better follow the developments in one's field on the web than in a reading room. The reasons for this are threefold: (1) "the long tail", i.e., on the web, goods, software, and ideas with small, fragmented and/or scattered audiences are marketable, (2) on the web, "everything is miscellaneous", i.e. one can search after one's own mental model, (3) on the web, access to information is very cheap, easy and extremely fast. This already has a considerable impact on the making of sciences. In this talk, the impact still to come is investigated and novel research issues induced by emerging web-based tools for sciences are discussed: social software and specialized search for sciences. Reasoning and semantics are core aspects of these novel web-based tools. Outcomes of the Network of Excellence "Reasoning on the Web with Rules and Semantics (REWERSE)", are presented and their relevance to the aforementioned systems is discussed. Finally, open issues of reasoning for social software and search are presented.
Fall 2007
Trading coverage for fault- and partition-tolerance in MANETs Date: October 17 Place: John von Neumann Time: 10:15 Dr. Paul Ezhilchelvan , University of Newcastle upon Tyne Abstract: In a failure- and partition-prone network, such as a mobile ad-hoc network (manet), complete coverage requires that a message be transmitted until all operative nodes acknowledge reception. This is prohibitively expensive when small, mobile wireless devices collaborate by forming a manet. This talk will present an approach that intentionally sacrifices full coverage for fault- and partition-tolerance together with savings in memory and bandwidth. I will outline two novel broadcast protocols termed ◊Q and ◊R. The former ensures eventual quiescence (broadcast related transmissions stop permanently) and the latter eventual relinquishing of broadcast messages (which can be discarded permanently). Using these protocols, we will explore solutions to the consensus problem, essential to support user collaboration. We will observe that when full coverage is not guaranteed, consensus amongst n devices cannot be guaranteed if at most f of them can crash (unnoticeably) and if n ≤ 3f. We present a protocol for n > 3f and evaluate its performance through simulations. The protocol is eventually quiescent on the transmission of consensus decision and eventually relinquishing of all broadcasts message used. Professor Installation Seminar: Parallel Programming and Component Models for the Many-Core Era Date: September 27 Place: John von Neumann Time: 15:15 Professor Christoph Kessler , IDA Abstract: The multicore roadmap in microprocessor design predicts a doubling of the number of cores per processor chip about every other year, while per-core performance will hardly increase any further. Programmers will very soon be faced with hundreds of hardware threads on a single processor chip. Exploiting them efficiently is the only way to keep up with the performance potential that still follows an exponential development for the foreseeable future. This makes the introduction of parallel computing even in mainstream application domains inevitable. Unfortunately, automatic parallelization methods are often not applicable due to lack of static information, not effective due to run-time overhead, or not scalable due to limitation by the given sequential program structure. Hence, explicit parallel programming is likely to become a dominating programming paradigm for the foreseeable future. In addition to the ever growing complexity of software, programmers now must master parallelism in an effective way, which creates a whole new problem dimension. (By the way - do we prepare our undergraduate students appropriately for this paradigm shift?) Beyond the implicit shared-memory parallelism supported in many current general-purpose programming languages such as Java, future programming languages that should be able to exploit the upcoming Many-Core processor generation effectively will provide support for massive explicit parallelism, including both manual and automatic management of memory hierarchies. In this context, we advocate adopting simple and deterministic parallel programming models. In the first part of this presentation, we briefly review previous accomplishments and current trends in the design and implementation of general-purpose parallel programming languages for various parallel hardware platforms. In the second part, we give an outlook to component models and composition techniques for explicitly parallel software. In particular, we describe a novel approach to optimized composition of explicitly parallel components.
Spring 2007
Introduction to Systems Thinking and its Application Date: Tuesday, May 8 Place: Alan Turing Time: 9.00 - 11.00 ** Harold W. “Bud” Lawson **, Lawson Konsult AB Abstract: The ability to “think” and “act” in terms of systems is a prerequisite to being able to structure and operate organizations and their enterprises so that they can (pro-) actively pursue their business goals or missions. Systems thinking (also called the systemic approach) evolved, through multiple contributions, into a discipline that can be applied in gaining an understanding of broader aspects of systems including the dynamic relationships between systems in operation. Through systems and creative thinking, organizations/enterprises can learn to identify complex system problems and opportunities and to determine the need for as well as to consider the potential effect of system changes. The ability to act in terms of systems involves life cycle management and the usage of defined processes in order to accomplish system change. This seminar introduces systems thinking and its application. Further, the goals, structure and results of an academic course on the topic are reviewed. The course is based upon a new book in preparation for publication entitled: “A Journey Through the Systems Landscape”. Speaker's Profile: Harold W. “Bud” Lawson has been active in the computing and systems arena since 1958 and has broad international experience in industrial and academic environments. Received the Bachelor of Science degree from Temple University, and the PhDx degree from the Royal Technical University. Contributed to several pioneering efforts in computer hardware and software technologies. He has had professorial appointments at several universities in the USA, Europe and the Far East. Currently, Honorary Professor in the Swedish Graduate School of Computer Science and Academic Fellow in the Department of Systems Engineering and Engineering Management at Stevens Institute of Technology, Hoboken, NJ. Fellow of the Association for Computing Machinery, Fellow of the IEEE, Member of AFCEA and INCOSE. Elected architect of the ISO/IEC 15288 standard. In 2000 he was awarded the prestigious IEEE Computer Society Charles Babbage Computer Pioneer Medal for his 1964-65 invention of the pointer variable concept for programming languages. Harold Lawson is an independent consultant operating his own company Lawson Konsult AB and is, as well, a consulting partner and member of the board of directors of Syntell AB. Towards the Engineering of Modular Software for Increased Predictability Date: Thursday, April 26 Place: Alan Turing Time: 15:15 Professor Michel Schellekens, Centre for Efficiency-Oriented Languages, University College Cork Abstract: We focus in this talk on two main methods used in academia and industry to optimize/evaluate software: worst-case and average-case analysis. These methods can be used in a variety of contexts for optimization purposes. For instance in a Real-Time context, to efficiently budget resources, and in embedded systems, for optimizing power consumption. A crucial property for the predictability of software is modularity, i.e. the capacity to predict the behaviour of software from the behaviour of its components. It is shown that the worst-case measure typically does not allow for exact modularity. Current Real-Time approaches to static worst-case analysis are discussed in this light. On the other hand, we show that the average-case measure does possess inherent modularity. We show how this modularity can be exploited, based on a redesign of standard data structuring operations, to track the distribution of the data states throughout a computation. This approach in turn has enabled the specification of the novel programming language MOQA, implemented in Java 5.0, and its associated timing tool DISTRI-TRACK. MOQA (MOdular Quantitative Analysis), essentially a suite of data structure operations for modular design, is guaranteed to be modular w.r.t. the average-case time measure. This is not the case for general purpose programming languages and in particular for current languages geared towards automated average-case analysis. The approach links several, thus far largely separate, areas together, including Semantics, Complexity, Analysis of Algorithms and Real-Time Language design. The corresponding unified foundation for algorithmic analysis has led to the solution of bottle-neck problems in automated average-case timing (open problems on dynamic algorithms, first investigated by Knuth) and has given rise to novel algorithms. The talk focuses on the intuitions underlying the approach and should be accessible to anyone with a standard undergraduate background in the Analysis of Algorithms. The talk touches on some core issues which will be discussed in the book ``A Modular Calculus for the Average Cost of Data Structuring'', to appear with Springer. Speaker's Profile: Prof. Michel Schellekens obtained his PhD from Carnegie Mellon University. Following his graduation from CMU, he joined Imperial College London as an EC Marie Curie Fellow and was a Post Doc at the University of Siegen. Currently he is an Associate Professor at the Department of Computer Science at University College Cork. As Science Foundation Ireland Principal Investigator he leads the center for Efficiency-Oriented Languages, which collaborates with companies including Sun Microsystems and Synopsis. His work includes fundamental contributions to Quantitative Domain Theory, new models for Complexity Analysis and more recently foundations for modular static average-case analysis. He is an editor of the journals Annals of the Marie Curie Fellowship Association and Applied General Topology. Performance issues in emulated shared memory computing Date: Monday, March 5 Place: Alan Turing Time: 14:15 - 15.15 Dr. Martti Forsell , VTT - Technical Research Center of Finland, Oulu Abstract: Parallel machines employing an emulated shared memory system hold a great promise for scalable easy-to-program access to fine grained general purpose computing but unfortunately, realizing the full potential of them has turned out to be very difficult. In this presentation we discuss a number of performance issues, e.g. ILP- TLP co-exploitation, efficient implementation of high-level parallel language control and synchronization primitives, and active memory support related to emulated shared memory machines, and present promising techniques to address these issues. Some simulation results are provided. Speaker's Profile: Martti Forsell received his Ph.D. in Computer Science from the University of Joensuu, Finland, in 1997. He is currently a Senior Research Scientist at VTT - Technical Research Center of Finland, Oulu, Finland. Dr. Forsell is the inventor of the first scalable high- performance MP-SOC/NOC architecture armed with an easy-to-use general purpose parallel application development scheme utilizing experimental e-language and compiling tools. His current research interests include parallel processor/computer architectures, systems/ networks on chip, performance area and power modeling, models of parallel computing, functionality mapping techniques, parallel languages, compiling, and optimization. Fall 2006Modeling for Diagnostics Date: November 23 Place: Alan Turing Time: 15:15 Abstract: It's an all to familiar scene from a very famous movie: Apollo 13. The movie shows the cockpit of the Apollo 13 where astronaut Jim Lovell (played by Tom Hanks) reports back to earth: "Houston, we have a problem". The plot of the movie is based on the third American manned lunar landing mission, part of the Apollo program. Two days after the launch, a malfunction in the spacecraft caused an explosion that made one of the spacecrafts service modules to loose oxygen and electrical power. Astronauts John Swigert, Jr., James Lovell and Fred Haise Jr., who made up the crew of the US's Apollo 13 moon flight, used this phrase to report a life threatening technical problem:
Swigert(LMP): Okay, Houston With increased system complexity in recent years almost every system under deployment is exposed to component failures or is under the risk of suffering a major breakdown under its life time, as the one suffered by Apollo 13. Maintenance and repair is an ever increasing part of the total cost of a final product. Diagnosis techniques have been adopted by the after market departments of industrial systems product developers as a fast and accurate way of finding the root causes of failures. The seminar examines issues related to the development of integrated systems for system-level diagnosis. I will start by presenting the field technician's view of the problem and how they need is addressed by current software systems. Then, we will explore the fundamental issues and challenges in system diagnosis and prognostics from the computer scientist's point of view and discuss how the detection, localization and isolation of faults can be achieved by using statistical methods, decision theory, AI methods or constraint propagation techniques. In recent years, model-based diagnostics reasoning systems have provided a major advance in fault isolation and reduction of repair time contributing to the reduction of maintenance cost. Therefore, model based diagnosis techniques will receive a special attention during this seminar and their applicability will be illustrated on several real life industrial examples.
Challenges for spoken dialogue technology Date: October 26 Place: Alan Turing Time: 15:15 Dr. Johan Boye , Telia Research AB, Farsta Abstract: Speech interfaces to commercial services are becoming more and more common. Many people today have experience from speaking with machines when booking tickets or retrieving information over the telephone. This development is largely due to advances in automatic speech recognition, i.e. technology for identifying the words of an utterance. However, the commercial services of today are still rather limited in their dialogue capabilities. A typical dialogue consists of a number of questions from the system, posed in a fixed order, to which the user can reply only in a very restricted way. In order to exploit the true potential of natural language, it is necessary to develop spoken dialogue technology that allow more flexible system behavior. It is essential that users can express themselves more freely, and that dialogue systems understand the meaning of the user's utterances when uttered as part of an connected dialogue. In this talk, I will discuss some of the current challenges in spoken language understanding and spoken dialogue management, and present work carried out at TeliaSonera to meet them. The proposed approaches will be discussed in the light of two research prototypes, a database retrieval application and a 3D computer game, as well as a recently deployed commercial application for automated customer care. Speaker's Bio Johan Boye got his Ph.D. in logic programming at IDA in 1996, and is currently working at the research division at TeliaSonera in Stockholm. His main activities are research and application development in the field of spoken dialogue processing, with the aim of producing computer systems that can allow people to access various services using spoken natural language.
Toward Building Secure Systems Date: October 5 Place: Alan Turing Time: 15:15 Prof. Dr. Christoph Schuba , LiU, IDA Abstract: Society is rapidly moving toward a future that's increasingly dependent on technology, especially hardware and software systems. There are more and more computers, cell phones, PDAs, and other devices connected to one another over a digital heartbeat, providing user, business, and infrastructure services. These distributed services only function because of an intricate interplay of systems and software most users are not even aware exist. Security is one important quality that all these systems should possess. But what is meant by the term "security" in these different contexts and how can it be achieved? The term security is so hopelessly overloaded with meaning that its use captures a vast set of properties and problems we all care about today, in high technology and in society as a whole. This presentation explains what the term security means in the context of computer systems. We then explore a number of approaches that contribute to varying degrees to the quest for the holy grail, system security. Along the way we will be pointing out open research problems and ongoing work. Speaker's Bio Christoph Schuba studied mathematics and management information systems at the Universität Heidelberg and the Universität Mannheim in Germany. As a Fulbright scholar, he earned his M.S. and Ph.D. degrees in Computer Science from Purdue University in 1993 and 1997, performing most of his dissertation research in the Computer Science Laboratory at the Xerox Palo Alto Research Center (PARC). Christoph has taught undergraduate and graduate courses in computer and network security, cryptography, operating systems, and distributed systems at the Universtität Heidelberg, Germany, at the International University in Bruchsal, Germany, and at San Jose State University, USA. Since 1997 he has been working in Sun Labs and the Security Technology Office at Sun Microsystems, Inc. In January 2006, Christoph joined Linköpings Universitet in Sweden as Professor in Information Security. Spring 2006
Superinstructions and Replication in the Cacao JVM interpreter Date: June 8 Place: Alan Turing Time: 10:15 Prof. Anton M. Ertl , TU Vienna, Austria Abstract: Dynamic superinstructions and replication can provide large speedups over plain interpretation. In a JVM implementation we have to overcome two problems to realize the full potential of these optimizations: the conflict between superinstructions and the quickening optimization; and the non-relocatability of JVM instructions that can throw exceptions. In this paper, we present solutions for these problems. We also present empirical results: We see speedups of up to a factor of 4 from superinstructions with all these problems solved. The contribution of making potentially throwing JVM instructions relocatable is up to a factor of 2. Replication has a small, but usually positive effect on performance. Software Analysis in Theory and Practice Date: April 27, Place: Alan Turing, Time: 15:15 Professor Welf Löwe , Växjö University, Abstract: Software maintenance includes tasks like finding and removing design flaws and adding new functionality to a software system. These maintenance tasks are expensive today. Cost estimations of resources and time range from 50% to 80% of the total costs of ownership of a software system. In order to maintain a system, it needs to be comprehended and the effort for gaining comprehension even dominates the total maintenance effort. Estimations range from 40% up to 90%. Design documents and other kinds of documentation providing an abstract and comprehensible view on a system are often outdated or not available at all. In many cases, the code of the system is the only trustworthy source of information. However, due to the size of many systems, gaining comprehension from code needs to be supported by tools. The task of these tools is to extract information, analyze and focus it, and, finally, visualize it for the person who tries to understand the software system. Depending on the maintenance goal, the abstraction level, and the humans involved, different views of a software system are appropriate. This implies that different visualizations need to be designed, different analyses to be defined, and different kinds of information to be extracted. In this talk, we sketch some example analyses: Points-To Analysis is a static source code analysis computing possible dynamic call-, access-, and reference-relations between runtime entities like objects. Design Pattern Detection aims at identifying design and other code patterns in source code or other system specifications like UML diagrams. Architecture Recovery is the task of automatically analyzing the architecture of a system, i.e., detecting its components and connectors. Metric Analysis pushes the level of abstraction even further: they aim at numerically accessing certain properties and qualities of a system. Moreover, we present synergies between these analyses and give some practical applications. Finally, we introduce a framework, the VizzAnalyzer, for integrating different kinds of analyses and visualizations in a simple and straightforward way.
Testing Stream Cipher Generators and Pseudorandom Number Generators by State Space Exploration Date: March 23, Place: Alan Turing, Time: 15:15 Professor Joerg Keller, Fern-Universität in Hagen, Germany Abstract: Both generators for stream ciphers (such as A5/1) or pseudorandom number generators are typically initialized into a certain state by a seed value, and then obtain a sequence of states they are in. In each state they output one or more bits. The state space can thus be modeled as a directed graph where each node has exactly one outgoing edge to the follow-up state. Each weakly connected component of such a graph consists of one cycle and a number of trees directed to the root, with the root being a node on the cycle. Often one is interested in the lengths of the cycles (period lengths), as they frequently cannot be derived analytically. Also, in crypto applications, one is interested in the graph structure as a whole. If the generator shall randomize, then its graph structure should not deviate too much from the expected values for a randomly chosen graph with outdegree exactly 1. We present a parallel algorithm to explore such a graph without constructing it in memory, which is unfeasable because of its size. We report on the experimental runtimes achieved, and we report on the graph structures revealed for some generators. Fall 2005Evaluation Dependability Attributes at the Architecture Design Phase Dr. Lars Grunske, Boeing Postdoctoral Research Fellow, School of Information Technology and Electrical Engineering, The University of Queensland, Brisbane Abstract: Over the past decades, software architectures and architecture centric development received increasing attention in the context of complex dependable systems development. These dependable systems need to fulfil requirements regarding dependability attributes such as safety, reliability, availability, maintainability, security and temporal correctness. As these properties be cannot be designed directly into the system, there is also a rising need to predict and evaluate these dependability properties at the architecture design phase. This talk will give overview over the research field, discuss arising problems and challenges and reviews current architecture evaluation approaches. A Metalogic Formalisation of Legal Argumentation as Game Trees Date: November 10, Place: Alan Turing, Time: 15:15 Prof. Joergen Fischer Nilsson, Computer Science and Engineering Section, Informatics and Mathematical Modelling, Technical University of Denmark Abstract: We describe a framework for logical formalization and analysis of argumentation and dispute between two parties. The key idea is to metaphorically consider an argumentation dialogue as a board game like chess. Instead of moving pieces the parties utter speech acts comprising logical propositions in order to defend or attack a key claim. The applied principles are sought demonstrated by unravelling of a simple legal case within statutory law. However, the applied principles are by no means confined to legal reasoning. The dynamics of the argumentation dialogue is achieved conveniently also computationally by adopting a metalogic framework in which propositions are encoded as terms, and by appealing to an inference engine for defeasible logic. In the presentation we will try to stress the ideas and principles of our framework also for people with little or no background in legal reasoning and/or logic programming, taking the liberty of ignoring some intricacies in the applied logics. To this end we consider the board game tree conception useful. This is joint work with Andreas Hamfelt and Jenny Eriksson, Uppsala University. An Industrial Perspective on Technological Challenges in Deep Sub-Micron Design Date: October 21, Place: Alan Turing Time: Obs!! 13:15 Dr. Björn Fjellborg, Ericsson Abstract: Highly integrated microelectronics form the platform for signal processing in Ericsson's cellular base stations, with each new product generation presenting ever tighter demands on performance, power, and cost. This presentation gives an industrial perspective on developments in mobile applications, technology, hardware architecture, and design methodology and how they affect Ericsson's implementation strategy. 3G and 4G applications, 65 nm process technology and beyond, multi processor systems on chip, and formal methods for design all enable solutions as well as present challenges. Meeting project budgets and time-to-market requirements and still make the best use of technological opportunities requires a balance between re-use of existing solutions, development of improved architectures, and management of deep sub-micron effects.
Rational Agents in Logic Programming for the Semantic Web Date: September 29, Place: Obs Donald Knuth, Time: 15:15 Prof. Luis Moniz Pereira, Director of Centro de Inteligência Artificial (CENTRIA), Departamento de Informática,Universidade Nova de Lisboa, Portugal Abstract: We examine rational features employable by agents in the context of the Semantic Web, based on Logic Programming. In particular, we shall look at the EU project REWERSE -- Reasoning on the Web, -- and address the issues of reactivity and evolution. The slides are placed here , or, together with on-line recording of the talk, at speaker's home page . Speaker's Profile: Luís Moniz Pereira, Universidade Nova de Lisboa (UNL): He received the scientific prizes: “Prémio Estímulo à Excelência” (2005) and “Prémio da Boa Esperança” (1994), both from the Portuguese government; and “Prémio de Ciência e Tecnologia” (1984), from Calouste Gulbenkian Foundation. He is involved in co-ordination of a number of international research projects and international educational programs, funded by the European Comission or bi-lateral, including IST NoE in Computational Logic CoLogNet, REWERSE, Erasmus Mundus supported distributed European MSc in Computational Logic, Asian-Link project and several bi-lateral projects. Cross-Layer Adaptation for Quality-Aware and Energy-Efficient Next Generation Mobile Multimedia Devices Date: September 15, Place: Alan Turing, Time: 15:15 Prof. Klara Nahrstedt, Department of Computer Science, University of Illinois at Urbana-Champain
Spring 2005Investigating Software Qualities - the Blekinge Way Date: May 12, Place: Alan Turing, Time: 15:15 Dr. Mikael Svahnberg, Blekinge Institute of Technology Abstract With the contemporary ubiquitousness of software, where software is seen as strategic assets and where the society becomes more and more dependent on software we are also more susceptible to flaws in the software. Hence, it is of vital importance to develop software with adequate quality. The BESQ project at Blekinge Institute of Technology aims at researching and developing different means for achieving an overall balance of different aspects of quality. In this presentation an introduction to the BESQ project is given, together with a discussion of the challenges involved in developing for and achieving a certain and predictable balance of different quality aspects.
Modular Verification of Software Systems Date: March 17, Place: Alan Turing, Time: 15:15 Prof. Kathi Fisler, Department of Computer Science, Worcester Polytechnic Institute, Massachusetts USA Abstract Aspect-oriented programming (AOP) has become an increasingly important programming paradigm. AOP is one of a family of means for expressing abstractions that cut across the program's dominant modularity; these techniques enable the construction of software by composing features. Despite their importance, feature-based programming methods lack supporting computer-aided verification techniques, which are necessary for increasing reliability and developing confidence in systems. This talk presents a technique for verifying feature-based programs (expressed as state machines). By analogy with modular compilation, we support modular verification, both to enable independent development and to reduce the computational cost of verification. While modular verification is an old idea, feature-based programs violate fundamental assumptions underlying standard modular techniques. Using case studies for motivation, I will describe both the subtleties of feature verification and our analysis techniques. (Joint work with Shriram Krishnamurthi, Brown University) Speaker's Profile Kathi Fisler is an Assistant Professor of Computer Science at WPI. Her research centers around formal approaches to understanding and predicting functional behavior of hardware and software systems. She has a particular interest in the role of diagrammatic representations in verification. Her current work explores modular analysis of feature-oriented software systems, the computational advantages of timing diagrams as a logic for temporal specifications, and change-impact analysis for access-control policies. Kathi earned her PhD in 1996 from Indiana University, did a postdoc at Rice University and internships at Bell Labs and Intel before starting at WPI in 2000. Using reputation-based algorithms to counter the spam problem Joerg Diederich
L3S Research Center
Date: February 10, Place: Alan Turing, Time: 15:15 Abstract:Spam is definitely a major problem, that everybody using email is facing daily. Even though there are quite some spam detection techniques (e.g. rule based), which have significantly reduced the number of spam reaching your mailbox finally, still quite some spam messages remain. Furthermore, there is a permanent struggle between the spammers and the writers of the detection rules so that you are required to keep your spam filter up-to-date permanently. In this seminar, I will show an alternative distributed technique (MailRank), based on social networks that can be derived from your personal email network. It is shown to perform well in case of attacks (i.e. spammers trying to circumvent the spam detection) since it is based on the PageRank algorithm used by google to rank web pages. In addition to detecting spammers, it can also provide a ranking of non-spam emails as an automatic pre-classification of incoming emails, which is useful for those people receiving many emails per day. Fall 2004Anatomy of a worst-case efficient priority queue Date: January 20, Place: Alan Turing, Time: 15:15 Jyrki Katajainen
University of Copenhagen Jubilee lecture: 25th anniversary on the stage as university teacher. Addressing MPSoC Hardware/Software platform challenges Date: December 16, Place: Alan Turing, Time: 15:15 Prof. Luca Benini,
University of Bologna Abstract With the fast diffusion of Multiprocessor System on Chip (MPSoC) platforms in many application areas, we need a coherent and synergistic hardware-software approach to fully exploit their huge potential. In this talk I will give an overview of the research activity carried out in this area at the University of Bologna. I will touch upon various topics such as: Network on Chip (NoC) design, design flows and programming paradigms. On these topics, I will present recent research results and directions of current investigation. Speaker's Profile Luca Benini received the B.S. degree (summa cum laude) in electrical engineering from the University of Bologna, Italy, in 1991, and the M.S. and Ph.D. degrees in electrical engineering from Stanford University in 1994 and 1997, respectively. He is with the department of electronics, computer science and systems in the University of Bologna. He also holds visiting researcher positions at Stanford University and the Hewlett-Packard Laboratories, Palo Alto, CA. GridStat : A Next-Generation Communication Infrastructure for the Electric Power Grid Date: November 18, Place: Alan Turing, Time: 15:15 Prof. David E. Bakken, Washington State University Pullman, Washington USA Abstract Electric power infrastructures are extremely complex. For example, the North American power grids involve almost 3500 utility organizations. The communication system coordinating and monitoring utility operations in the US was designed largely in response to the 1965 blackout in the US Northeast, and it is similarly obsolete in Europe. However, since then network and related technologies have improved dramatically, and factors such as deregulation are putting additional strain on the communications system. In this seminar I will overview the grid's communication system and show how it greatly limits opportunities for protection and control as well as how it has been a factor in recent blackouts. I will also overview the requirements an improved communications infrastructure for the power grid must meet. I will then describe GridStatx, our middleware communications framework for the electric power grid and other critical infrastructures. GridStat a publish-subscribe middleware framework that is specialized for the delivery of status updates. It features optimizations that exploit the semantics of status flows (as opposed to generic event messages) and features a QoS management infrastructure. It is being used in a trial deployment by Avista Utilities, an electric and gas utility. Speaker's Profile Dave Bakken is an Associate Professor of Computer Science in the School of Electrical Engineering and Computer Science at Washington State University (WSU). His research interests include middleware, distributed computing systems, fault tolerance, and QoS frameworks. Prior to joining WSU, he was a scientist at BBN, where he was an original co-inventor of the Quality Objects (QuO) framework. He is on sabbatical in Norway this academic year, at the University of Oslo and also 20% at Simula Research Lab. Answer Set Programming: an Approach to Declarative Problem Solving Date: October 28, Place: Alan Turing, Time: 15:15 Prof. Ilkka Niemelä , Helsinki University of Technology Abstract The term answer set programming (ASP) was coined by Vladimir Lifschitz to refer to a new declarative programming paradigm that has its roots in the stable model (answer set) semantics of logic programs and implementations of this semantics developed in the late 90's. While ASP has its roots in logic programming, the basic idea of ASP is similar to, e.g., SAT-based planning or constraint satisfaction problems. However, these approaches are basically propositional but in ASP the goal is to provide a more powerful knowledge representation language for effective problem encoding. A number of successful ASP systems have already been developed and applied in areas such as planning, decision support for the flight controllers of space shuttles, web-based product configuration, configuration of a Linux system distribution, computer aided verification, VLSI routing, network management, security protocol analysis, network inhibition analysis, and diagnosis. The talk explains the theoretical underpinnings of ASP, introduces the ASP programming paradigm, outlines computational techniques used in current ASP solvers, and discusses some interesting applications of the approach. R&D Challenges for Resilience in Ambient Intelligence Prof. Dr.-Ing. Heinz Thielmann Director Fraunhofer Institute for Secure Telecooperation (SIT), Darmstadt/Germany Date: October 14, Place: Alan Turing, Time: 15:15 Abstract The overall goal of developing a secure and dependable Information Society calls for a better understanding of the novel issues associated with the advent of innovative and pervasive ICT. The growing autonomy & intelligence of technologies and systems together with the increasing scale and volume of their deployment pose new challenges for security and dependability. The complexity of such challenges is further magnified by the increasing volatility and growing heterogenity of products, applications, services, systems and processes in the digital environment and the inherent interdependencies resulting from the pervasiveness of technologies and systems in all aspects of our society and our economy. In this context, the objective of Fraunhofer SIT in line with the program of the European commission - is to mobilise all stakeholders and relevant scientific communities in identifying and articulate the key R&D challenges in developing a secure and dependable Information Society. Whereas the thorough investigation of the R&D challenges associated to the development of a secure and dependable Information Society may be very broad and demanding, we need to focus on a limited and selected number of themes, such as
Challenges and concerns. The information infrastructure public and enterprises - underpins most systems in our society. Critical systems can not only be involved in risks originating from inside, but increasingly now from exogenous sources, both malicious or from the interconnection with other systems. ICT is a crucial factor of these risks. The most crucial pat is the so-called Critical Information Infrastructure (CII), the nervous system that connects all other networked systems. The risks induced by the information infrastructure can affect society as a whole, an industrial or geographic sector, businesses and the single citizen. But the emerging wide-spread interconnectivity brings forth interdependencies: faults and failures can be caused by external systems through mostly uncovered links. Protecting ICT systems networked in unbounded environments needs new scientific and technological developments. Most systems (e.g. power, transport) have been designed in the past with a different paradigm in mind: isolated systems, clear jurisdictions and responsibilities, controlled access and interactions. Now we are interconnecting those systems with ICT, deploying networked systems with unbound access systems-of-systems comprising components that haven't been explicitly produced for them. Behaviours just emerge from the combination of systems and some of them are failure-prone in unknown and unpredictable ways. This constitutes a major challenge. However the protection of these infrastructures, and in particular of the information infrastructures, requires a profound understanding scientifically based, rigorous, supported by appropriate technologies. Key technological issues. We need multiple approaches that take advantage of existing models, and develop those appropriate for understanding interdependencies and hidden connections, at all levels of granularity (from devices to Personal Area networks, to LANs to WANs, to interdependent infrastructures). We need to develop technologies for protection (understanding by this the whole cycle from prevention to recovery from failures). This requires data interpretation for observation and explanation of situations, mostly in real-time and related to alert and emergency conditions. For managing the security of networked systems, it is necessary to manage all required information. A new challenge is to devise security as an intrinsic feature to systems, self-healing solutions (architectures and other needed technologies) have to be studied. In a networked society, all nodes are connected and "always on". This is a new risk situation, especially for citizens that might not be aware of the threats. The individual's domestic infrastructures are at the same time a source of vulnerability for the overall infrastructures, and a source of vulnerabilities for the individual, with effects on his/her security and privacy, and changes in the consideration of time and space issues (proximity, residence, personal spaces). Multiple stakeholders have to be taken into consideration in the monitoring, detection and reaction to failure conditions have to consider the expectations and requirements of all of them (service users, citizens, etc.). Resilience should also be applied to the control of industrial installations, where ICT is pervasive. There, systems should develop an awareness of situations scalable in different dimensions (space, time, rationality what is expected from a given device), and then acting according to dependability/security objectives. This needs to include the specification of local and general failure conditions. Large industrial control is evolving, with the inclusion of ever more networked devices. Resilience is not just the result of the composition of the properties of individual components or architectures, but also of the engineering processes. The presentation will give insight into related R&D areas and projects at Fraunhofer SIT, Speaker's Profile Prof. Dr.-Ing. Heinz Thielmann graduated in communications engineering and data processing in 1969 at the Technical University Darmstadt (Germany), where he also received his Dr.-Ing. degree in 1973 on a thesis "Analysis and Synthesis methods in analog and digital filtering". From 1974 to 1994 Prof. Thielmann worked in different functions in Philips: R&D for communication systems, product management, CEO of a worldwide business unit "Network Systems". In 1994 he joined the Fraunhofer Gesellschaft and is Managing Director of the Institute for Secure Telecooperation in Darmstadt. Since 1973 Prof. Thielmann gives lectures in communications engineering, networks, IT-security and general innovation management. He is advisor to government authorities, the EU-commission and network operators and member of industrial supervisory boards. Complexity Issues in System Development: Examples from Automotive Electronics Date: September 6, Place: Alan Turing, Time: 13:15 Jakob Axelsson, Volvo Car Corporation Abstract In this seminar, some of the major trends and drivers in the development of automotive electronics will be presented. One of the major concerns is how to deal with the increasing complexity, in particular in software. To be able to handle this, a better understanding of the nature of complexity is needed, which not only includes the system itself but also the organisation and people that participate in the development. Since the main activity of the organisation is information processing, resulting in a description of the product to be produced, the ability of humans to process information is at the heart of the problem. In this presentation, an initial attempt is made at describing some of the issues involved, and some of the strategies employed within the automotive industry to cope with the complexity. Biography Jakob Axelsson studied Computer Science in Linköping, Sweden, and Lausanne, Switzerland. He received an M.Sc. from Linköping University in 1993, and a Ph.D. in 1997 for a thesis on hardware/software codesign of real-time systems. He has been working at ABB Corporate Research and ABB Power Generation (now Alstom) in Baden, Switzerland, Volvo Technological Development (now Volvo Technology) and Carlstedt Research & Development in Göteborg, Sweden. He is currently with the Volvo Car Corporation in Göteborg, where he is program manager for research and advanced engineering for electrical and electronic systems. He is also an adjunct professor in software and systems engineering at Mälardalen University in Västerås. In addition, he is chairman of the board of the ARTES national graduate school in real-time and embedded systems, and was until recently president of the Swedish chapter of the International Council on Systems Engineering (INCOSE). Xcerpt: A Deductive Query Language for the (Semantic) Web Date: August 19, Place: Alan Turing Time: 15.15 Sebastian Schaffert, Department of Computer Science LMU, Munich Abstract Current Web query languages are special purpose in the sense that they are either only suitable for querying XML or semistructured data (like XQuery), or only suitable for querying "Semantic Web" meta data, e.g. in RDF or OWL. The language Xcerpt presented in this talk in contrast is a deductive, rule-based query language that aims at being capable of both querying "standard" Web data and "Semantic" Web data, and even allows to combine both kinds of information. Xcerpt's deductive properties also allow it to reason wit such data. This talk first introduces into Xcerpt's basic constructs with a focus on incomplete pattern queries for Web data, and then shows its application to a "standard" Web scenario, which is later extended with (simple) ontology reasoning. The talk furthermore introduces into the event and update language XChange, which builds upon Xcerpt for its querying components, and briefly summarises other related projects. Spring 2004Trace Schemata for (Multi-language) Dynamic Analyses Date: June 3, Place: Alan Turing Time: 15.15 Mireille Ducassé, Professor, Technical University INSA of Rennes Abstract In order to understand the dynamics of programs, some data about executions have to be collected and these data are analyzed, preferably by automated tools. This raises a number of questions, in particular: What data have to be collected? What does the analysis produce? How are the data collected? How does the analysis work? How are the collection and the analysis of data combined ? In the presentation I will concentrate on the first and last questions which are too often overlooked. I will first advocate that properly specifying what data to collect is a key issue. I will try to coin the name "trace schemata" for modeling trace information. Second, I will discuss that what to collect is deeply correlated with how collection and analysis are combined. We have shown with different debuggers implemented for different languages that collecting trace information driven by the analysis in a modular way is a good compromise. It is easy to port. With the addition of a filtering mechanism, it can be efficient because only the relevant part of the trace is collected for a given analysis. This enables rich trace schemata to be defined. Therefore, a given tracer can be re-used for several analyses, avoiding a lot of tedious work. Speaker's Profile Prof. Mireille Ducassé Professor Mireille Ducassé worked 11 years in industrial research centers, first at the "Laboratoire de Marcoussis" in France, then at the "European computer-Industry Research Center" in Germany. She completed a PhD at the university of Rennes in 1992. In 1993, she was appointed professor at the technical university INSA (Institut National des Sciences Appliquées) of Rennes. Her research is done within the IRISA (Institut de Recherche en Informatique et Systèmes Aléatoires) which federates the computer science research of Rennes. She has been conference chair of AADEBUG 95 (international workshop on Automated Debugging) and program chair of AADEBUG 2000. Her publications can be found at http://www.irisa.fr/lande/ducasse/ Advanced Research with Autonomous Unmanned Aerial Vehicles Date: March 25, Place: Visionen Time: 15.15 Patrick Doherty, Professor, IDA Abstract The emerging area of intelligent unmanned aerial vehicle (UAV) research has shown rapid development in recent years and offers a great number of research challenges for artificial intelligence and knowledge representation. For both military and civilian applications, there is a desire to develop more sophisticated UAV platforms where the emphasis is placed on intelligent capabilities and their integration in complex distributed software architectures. Such architectures should support the integration of deliberative, reactive and control functionalities in addition to the UAV's integration with larger network centric systems. In my talk I will present some of the research and results from the WITAS UAV Project, a long term basic research project with UAVs currently being pursued at Linköping University, Sweden. Actual missions flown for an international evaluation group in Revinge, Sweden will also be shown. Intrusion Detection, myths of the past, current state of the art and future challenges Date: February 12, Place: Alan Turing (Estraden) Time: 15.15 Marc Dacier, Professor, Corporate Communication Department, Eurecom Abstract In the course of 2003, a well known consulting group published a report
advising its customers to postpone any investment in "Intrusion Detection
Systems" (IDS) in favor of so called "Intrusion Prevention Systems" (IPS).
This led to some heated controversy in the Intrusion Detection community.
During this talk, we try to clarify the situation by offering a thorough
and historical review of existing IDS. We identify the remaining gap
between the promises offered a few years ago and today's available
solutions. We highlight the issues left open and the avenues for future
research, not only in terms of
CLP(BioNet): Towards a CLP framework for the analysis of Biochemical Networks
Date: January 15, Place: Alan Turing (Estraden) Time: 10.00 Yves Deville, Professor, Université Catholique de Louvain, Department of Computing Science and Engineeering Abstract Biochemical networks such as metabolic, regulatory or signal transduction pathways can be viewed as interconnected processes forming an intricate network of functional and physical interactions between molecular species in the cell. The amount of information available in such networks is increasing very rapidly. This is offering the possibility of performing various analyses on the structure of the full network of pathways for one organism as well as across different organisms, and has therefore generated interest in developing databases for storing this information, and methods for analyzing such networks. Analyzing these networks remains however far from straight forward due to the nature of the biological networks, which are often very large, heterogeneous, incomplete, or inconsistent. The analysis of biological networks is hence a challenging problem in systems biology, in bioinformatics, and in computer science. Various forms of data models have been devised for the representation and for the analysis of biochemical networks (e.g. bipartite graphs). An object-oriented model, which is the basis of the aMAZE database for the representation of biochemical processes, will be presented. A biochemical network represented in this framework can then be transformed into a generalized graph, where nodes and arcs have attributes. Such graphs can be used for the visualization of the network as well as for its analysis. The constraint programming framework is an attractive framework for the analysis of biochemical networks because most of the analyses can be expressed as a set of basic constraints on (extended) graphs, and various domain expertise can also be described by constraints. CLP(BioNet) is a first attempt to explicitly propose biological networks, represented by a specific form of graphs, as the underlying domain of a constraint system. Constraints, such as PathConstraint, form the basic constraints of the system. A specific analysis can then be expressed by combining basic constraints. A first prototype of CLP(BioNet) is being developed. It is implemented in Oz. It uses finite domains and ideas from finite sets. Different graph algorithms are used to ensure the incrementality and the propagation of the constraints. This approach is also tested on real biochemical networks. The specification of analysis criteria as well as the analysis of the results is done in collaboration with biologists. Fall 2003Functional Reactivity: Eschewing the Imperative Date: December 12, Place: Alan Turing (Estraden) Time: 10.15 Henrik Nilsson, The University of Nottingham, School of Computer Science an Information Technology Abstract Functional Reactive Programming (FRP) is a paradigm for reactive programming in a pure functional setting. FRP originated in Conal Elliott's and Paul Hudak's work on Functional Reactive Animation (Fran), and has since evolved in a number of different directions and into a number of different concrete implementations. FRP share many features with, on the one hand, synchronous languages, like Esterel and Lucid Synchrone, and, on the other, languages for modelling and simulation, like Simulink and Modelica. However, FRP has a number of distinct features that set it apart, for example its support for describing reactive systems with highly dynamic structure, and the fact that reactive components are first class entities, yielding considerable meta-programming capabilities for free. This talk gives an overview of Functional Reactive Programming in the context of Yampa, the latest FRP implementation from Yale University. Declarative Multi-Paradigm Programming in Curry Date: November 27, Place: Alan Turing (Estraden) Time: 15.15 Michael Hanus, Institut für Informatik und Praktische Mathematik, Christian-Albrechts-Universität zu Kiel Abstract The multi-paradigm language Curry is an attempt to combine in a seamless way features from functional programming (reduction of nested expressions, higher-order functions, lazy evaluation, polymorphic type systems), logic programming (logical variables, partial data structures, constraint solving, built-in search), and concurrent constraint programming (concurrent evaluation of constraints with synchronization on logical variables). Thanks to this combination, Curry provides new programming techniques (e.g., demand-driven search) and better structuring facilities, and it avoids impure features of logic languages like Prolog. The development of Curry is an international initiative intended to provide a common platform for the research, teaching and application of declarative multi-paradigm languages. This talk provides an introduction to Curry and related multi-paradigm programming techniques. It will be shown that functional languages can be easily extended to cover features for logic and concurrent programming. Furthermore, we discuss some advanced features of Curry for constraint or distributed programming. Finally, we demonstrate the advantages of such a multi-paradigm language by some applications, e.g., the high-level implementation of web-based systems. "Weaving the Adpative Web": Towards personalization in the Semantic Web Date: October 23, Place: Alan Turing (Estraden) Time: 15.15 Nicola Henze,
Universität Hannover, Institut fuer Informationssysteme, Abstract The idea of the Semantic Web to give information a "well-defined meaning, better enabling computers and people to work in cooperation" rises the question of an Adaptive Web which knows like a personal agent the specific requirements of a user, takes goals, preferences, or the actual context into account in order to optimize the access to electronic information. Desing and formation of an Adaptive Web are just in the beginning. Fundamental research for personalized access, retrieval and presentation of information can be found in the area of recommender systems (and their principal application area "e-commerce"), and in the area of adaptive hypermedia (and their principal application area "e-learning"). In this talk, we investigate the applicability of methods and techniques from adaptive hypermedia for designing an "Adaptive Web". A logic-based definition of adaptive hypermedia will be presented, which supports encapsulation and re-usability of adaptation techniques. This characterization allows for formulation and embodiment of personalization techniques on the logic-level of the Semantic Web Tower. A draft design for an Adaptive Web, based on rule-based reasoning enabled by Semantic Web technologies, will be presented. Traces of Randomized Distributed Algorithms As Markov Fields Date: September 25, Place: Alan Turing (Estraden) Time: 15.15 Laurent Fribourg,
Directeur de recherche, CNRS, at Ecole Normal Superieur de Cachan (in cooperation with S. Messika and C. Picaronny) Abstract Given a randomized distributed algorithm A that operates on a ring (or linear array) of N processes, we use the fact that the traces of computation via A form a Markov field (i.e., a random field governed by local interactions), and that A has a unique stationary distribution if the Markov field has no phase transition. We then use van den Berg's sufficient condition on ``paths of disagreement'' for guaranteeing the absence of phase transition of Markov fields, as an original tool for proving the uniqueness of the stationary distribution D and the rapid mixing of A towards D. This new method of proving rapid mixing is illustrated on Herman's self-stabilizing algorithm of mutual exclusion and the classical random walk on a ring. Spring 2003The Next-Generation Web: Information in the Third Millenium Date: June 5, Place: John von Neumann (Belöningen), Time: 15.15 Massimo Marchiori,
W3C, Research Scientist at the MIT, Abstract The World Wide Web has grown, and it size is now enormous. But if its size and the number of people using it is impressive, it is also true that its original architecture is showing all its limitations. Information handling has become more and more difficult, and the enormous potential of the Web seems yet unexpressed. In this presentation we will show what are the solutions that are under development and standardization to bring the Web further into the future, so to lead the Web to its next generation. Introduction to the Protein Secondary Structure Prediction (PSSP): a Model and a Metaclassifier Date: May 15, Place: Estraden, Time: 15.15 Anita Wasilewska: Professor, Department of Computer Science, State University of New York at Stony Brook Abstract The talk will discuss a joint work with Dr. Victor Robles Forcada of the Technical University of Madrid. We provide an intuitive introduction to the protein secondary structure prediction research preliminaries and problems. We explain what are the proteins in real life, provide a simple mathematical model, give an overview of some of the newest supervised classification methods and classifiers and discuss their results. The classifiers, of the third generation, are chosen from 10 available servers on the Internet. Finally, we present ideas behind our Metaclassifier based on Bayesian Network approach. The Metaclassifier is currently reaching an excellent accuracy prediction level (> 81%). Compilation for Embedded Processors Date: April 29, Place: Estraden, Time: 15.15 Y.N. Srikant, Professor and Chairman, Dept. of Computer Science and Automation, Indian Institute of Science Abstract With the advent of system level integration and system-on-chip, the centre of gravity of the computer industry is now moving from personal computing into embedded computing. The resulting upheaval is only just beginning to be widely appreciated. Embedded software is pervasive and appears in vehicles, telephones, audio-video-equipment, aircraft, toys, security systems, medical diagnostics, weapons, pacemakers, climate control systems, manufacturing systems, intelligent power systems etc. Every embedded system very often contains a DSP (digital signal processing) processor. Most embedded systems have constraints on memory size, power, and overall dimensions. However, their computing requirements are by no means low. Code running on such processors must necessarily be fast, compact and also energy-efficient. Compilers for embedded processors are difficult to design and implement. They must generate code which utilizes several features of embedded processors such as, clusters of multiple functional units, dual memory banks, large number of registers, low power operation, special instructions, etc., very efficiently. These pose interesting challenges to a compiler designer. In this talk, we survey the techniques available for efficient code generation for embedded processors and outline the ongoing research in this area. Speaker's Profile Professor Y.N. Srikant received his Ph.D in Computer Science from the Indian Institute of Science in 1986. He is currently a Professor Chairman of the Department of Computer Science and Automation at the Indian Institute of Science. His areas of interest are compiler design and tools for software design. He is one of the editors of a handbook of compiler design published by CRC Press in September 2002. Dr. Srikant is the recipient of the Young Scientist medal of the Indian National Science Academy. More details regarding his publications may be reached here. System development with Action systems Date: March 13, Place: Estraden, Time: 15.15 Kaisa Sere, Professor,Department of Computer Science, Åbo Akademi University Abstract We present an approach to system development using the Action Systems formalism as the underlying formal framework. The approach is based on viewing a system, consisting of hardware and/or software, as a set of concurrent, distributed, co-operating entities. We exemplify the development approach via a few case studies on the design of e.g. control systems and software and mobile agents. Hierarchical Approaches to Digital Test Date: February 12, Place: Estraden, Time: 15.15 Raimund Ubar, Professor, Technical University of Tallinn Abstract An overview of research fields at the Test Lab in Computer Engineering Dept. of TU Tallinn will be presented. Then a popular introduction to the main problems in the field of Digital Test will follow. A special attention will be concentrated on the hot question: how to improve the testing quality at increasing complexities of today's systems? As a promising solution, the approach of combining high-level modelling with defect orientation will be discussed. Next, a short introduction to Decision Diagrams (DD) will be given. DDs serve as a good tool for hierarchical modelling of defects in digital systems. It will be shown how DDs help to achieve efficient procedures of hierarchical test generation and fault simulation in digital systems. Finally, an overview of testing tools developed at TU Tallinn together with corresponding experimental results will be presented. Speaker's Profile Raimund Ubar is a professor at TU Tallinn, and one of the three Estonian research professors elected recently for three years by Estonian Academy of Sciences. His research interests are fault modeling, simulation and diagnosis, test generation, design for testability and fault tolerance in digital systems. He has lectured and given talks at universities of more than 10 countries, participated during the last 10 years in 8 European projects, published more than 150 papers and contributed yearly for Program Committees of about 10 international conferences. He is a member of Estonian Academy of Sciences. AN EXAM EXAMINED Date: January 30, Place: Estraden, Time: 15.15 Olle Willen, IDA Abstract Occasional Programmers are believed to demonstrate a more pragmatic approach to the knowledge area of programming than professionals or academics. Therefore the classes of qualitative knowledge they account for may prove to be based on their pragmatic intentions. Classical taxonomies of cognitive abilities emanate from the constructivists' theories that new abilities are built upon the already existing, stepwise leading to higher cognitive qualities. This is perhaps contradictory to the way the Occasional Programmer is learning, since it is assumed that he strives to keep away from too hard cognitive challenges. This paper is based on observations of written examinations from a group of Occasional Programmers. On the hypothesis that they perhaps reveal a different style of learning an experimental model of knowledge categories is designed and evaluated. Attempts are then made to categorize the same examination in accordance with established taxonomies (Bloom, SOLO) and the results studied. Our intention is to carry out experiments with these taxonomies, and in connection with the results discuss the concept of knowledge categorization in order to get better acquainted with the problem area - an attempt to approach the secrets of knowledge consctruction. It is concluded that many problems are connected to the use of models of knowledge categorization, but also that a lot could be learned from such use that will enhance a teacher's awareness of learning. Fall 2002Content-based routing of XML data Date: December 12 Place: Estraden, Time: 15.15 Pascal Felber Institute EURECOM, Sophia Antipolis, France Abstract Dramatic improvements in communications bandwidth and ubiquity have led to the emergence of a wide range of new dissemination-based applications. These applications involve selective distribution of data to large numbers of users according to their interests, defined in terms of subscriptions that are matched at runtime against the actual data. In this talk, I will present an efficient and scalable filtering engine for matching XML data against large numbers of subscriptions expressed in the XPathx language. I will also describe algorithms for "lossy" aggregation of subscriptions, designed to increase system scalability. Finally, I will discuss the use of these techniques for content-based routing in overlay networks. Modeling and verification of embedded systems in Masaccio Date: November 28 Place: Estraden, Time: 15.15 Marius Minea Department of Computing, Technical University of Timisoara, Romania Abstract The development of embedded systems is a difficult task that combines elements of hardware design, software engineering and control theory. A major problem is bridging the gap between these different design aspects, in particular between the high-level design of a controller for a system and a suitable software realization. Masaccio is a modeling language for hierarchical system design that addresses these problems. Masaccio can be viewed as a hierarchical and compositional extension of reactive modules and hybrid automata. It supports both discrete and continuous components, with arbitrary nesting of parallel and serial composition. Besides compositionality, it allows the use of circular assume-guarantee reasoning to prove refinement between system descriptions at different levels of detail, which we illustrate in a system of communicating robots. Towards the implementation level, Masaccio interfaces with Giotto, a language for time-triggered software processes. A formal correspondence between Masaccio components and Giotto processes makes it possible to check a software implementation against a high-level description. We are currently working on applying this methodology to the modeling of an automated vehicle control system. Speaker's profile Marius Minea received his Diploma-Engineer degree in Computer Science and Engineering from the Technical University of Timisoara in 1993, and his Ph.D. in Computer Science from Carnegie Mellon in 1999. He did his thesis work on partial order reduction for verification of timed systems. For the last two years he has been a postdoctoral researcher at UC Berkeley, working on modeling and verification of embedded systems. Currently, he is associate professor at the "Politehnica" University of Timisoara, Romania. In 1991 and 1993 he visited Linköping University/IDA for six months, working with CADLAB. Uniform Composition of Active Documents Date: October 17 Place: Estraden, Time: 15.15 Uwe Aßmann, IDA Abstract Experts predict that every entity found on the web (XML data, software such as applets or 3-tier applications) will be coalesced to active (shippable places). Active documents are structured documents in the spirit of OpenDoc and XML but have a life of their own. They will be able to migrate, they will be shipped everywhere on the web, they will be embedded into other active documents, and combined with others visually via drag-and-drop clients, 3-tier architectures, and complete applications: everything will be an active document. As such, active documents are software entities and should be engineered with sound software enginering methods, but none exists. This talk gives an overview on several classes of active documents and introduces a uniform composition technology for them, based on invasive software composition. The technology is developed in the European Basic Research project EASYCOMP. Its task is to investigate technology for easy component composition in the future information society. Tree Automata with Constraints for Program Analysis Date: September 23 Place: Estraden, Time: 15.15 John Gallagher, University of Bristol Abstract Our starting point is set-based program analysis. In logic or functional programs, this analysis produces a recursive description of the set of terms corresponding to each variable in the program. This has many potential applications, including compiler optimisations, type-checking, debugging, verification and planning. We present a new practical algorithm for computing precise set-based descriptions, obtained by an abstract interpretation over non-deterministic tree grammars, and show examples of the results obtained. Then we consider the extension of the abstract domain with constraints, and discuss the precision and practicality of this extension. Perspectives for Electronic Books in the World Wide Web Age Date: August 22 Place: Estraden, Time: 15.15 Francois Bry, University of Munich Abstract While the World Wide Web (WWW or Web) is steadily expanding, electronic books (eBooks) remain a niche market. It is first postulated that (1) specialized contents and device independence can make Web based eBooks compete with paper prints, and that (2) adaptive features that can be implemented by client-side computing are relevant for eBooks, while more complex forms of adaptation requiring server-side computations are not. Then, enhancements of the WWW standards (specifically of XML, XHTML, of the style-sheet languages CSS and XSL, and of the linking language XLinkx) are proposed for a better support of client-side adaptation and device independent content modeling are proposed. Finally, advanced browsing functionalities desirable for eBooks as well as their implementation in the WWW context are described. Spring 2002Application of Generative Programming to Commercially Practical Software Engineering and Maintenance TasksDate: June 11 Place: Estraden, Time: 13.15 Dr. Ira Baxter, Chief Technology Officer, Semantics Design, Inc., Austin, Texas Abstract Remarkly, much of software engineering today is still carried out by manual methods. Significant productivity enhancements require automation, which in turn require tools that deeply understand programs. Generative programming is a class of tool technology that captures knowledge about how to generate code, enabling automation. While generative programming is normally considered to enhance forward engineering of software, the bulk of software engineering goes into software enhancement and maintenance. This talk will briefly sketch generative programming, place program transformations in the generative programming space, and then show how a practical, commercial program transformation tool ("DMS") can carry out a surprisingly wide variety of software enhancment tasks, including installation of test probes, duplicate code detection and removal, and automated translation from one programming language to another. Speakers profile Ira Baxter has been building system software since 1969, and ran a software house in the late 70s offering operating systems and development tools for microprocesors. He obtained his doctorate at the University of California at Irvine in 1990, studying transformational methods for capturing and reusing design knowledge to enhance software maintenance. At Schlumberger, he was part of the Sinapse team, building a PDE-solver code generator for supercomputers. Since 1996, Dr.Baxter has been the CTO of Semantic Designs, where he is the architect of the DMS Software Reengineering Toolkit, recently used to construct a domain-specific language compiler for controlling factories. Ira is also active in software engineering research and is presently CoProgram Chair for the 2002 International Conference on Software Maintenance (Nov'02). MathModelica - An Extensible Modeling and Simulation Environment with Integrated Graphics and Literate Programming Date: May 23 Place: Estraden, Time: 15.15 Johan Gunnarsson MathCore AB, Linköping Abstract MathModelica is an integrated interactive development environment for advanced system modeling and simulation. The environment integrates Modelica-based modeling and simulation with graphic design, advanced scripting facilities, integration of program code, test cases, graphics, documentation, mathematical type setting, and symbolic formula manipulation provided via Mathematica. The user interface consists of a graphical Model Editor and Notebooks. The Model Editor is a graphical user interface in which models can be assembled using components from a number of standard libraries representing different physical domains or disciplines, such as electrical, mechanics, block-diagram and multi-body systems. Notebooks are interactive documents that combine technical computations with text, graphics, tables, code, and other elements. The accessible MathModelica internal form allows the user to extend the system with new functionality, as well as performing queries on the model representation and write scripts for automatic model generation. Furthermore, extensibility of syntax and semantics provides additional flexibility in adapting to unforeseen user needs. Speakers profile Dr. Johan Gunnarsson, is VP Product Development at MathCore, and is a member of Modelica association, and one of the designers of the Modelica modeling language. He received his Ph.D. degree in automatic control 1997 at Linköping University, where he made research on formal methods to verify control system algorithms, resulting in a thesis called "Symbolic methods and tools for Discrete Event Systems", which describes methods to test the correctness of Control Systems. This resulted in a verification system based on Mathematica and C. The research, which was part of the NUTEK complex systems project, has been conducted in cooperation with SAAB where Johans methods were applied on a control system for part of the JAS 39 Gripen. Johan has also been a research associate both at the Electrical Engineering and Computer Science departments at Linköping University. This work was made within the research school ECSEL also at Linköping University, where he coordinated interdisciplinary research between the departments. Experience from this collaboration is used in the MathModelica product. Johan was also a guest researcher at Kestrel Institute, Palo Alto, USA where he conducted research on the Modelica language. QoS Management in Real-Time Data Services Date: April 18 Place: Estraden, Time: 15.15 Sang Hyuk Song, University of Virginia at Charlottesville Abstract Many real-time systems are now being used in safety-critical applications, in which human lives or expensive machinery may be at stake. Examples include aerospace and defense systems, industrial automation, traffic control, web-based information services, etc. The unpredictable demands from the operating environments of such systems often pose rigid requirements on their timely performance. These requirements are defined as real-time constraints on their temporal behavior. As real-time systems continue to evolve, their applications become more complex, and often require timely access to temporal data, possibly from sensor devices. This need for advanced data services in real-time applications poses intellectual and engineering challenges to researchers and practitioners. The trade-offs faced by the designers of real-time data services are different from those faced by the designers of general-purpose database systems. In this talk, we first discuss characteristics of real-time systems and some of the research issues of real-time data services. We then present research work being performed at the University of Virginia, especially on supporting QoS in real-time data services. HiPE: A High Performance Erlang System Date: March 21 Place: Estraden, Time: 15.15 Kostis Sagonas, Uppsala University Abstract: Erlang is a concurrent functional programming language designed to ease the development of large-scale distributed soft real-time control applications. It has so far been quite successful in this application domain, despite the fact that its currently available implementations are emulators of virtual machines. This talk will briefly present the architecture and performance characteristics of HiPE, an efficient native code compiler for the Erlang language. HiPE is a complete implementation of Erlang, offers flexible integration between emulated and native code, and efficiently supports features crucial for Erlang's application domain such as concurrency. HiPE is currently available on SPARC and Intel/x86 architectures and has recently been included in the Open Source Erlang/OTP system from Ericsson. As our performance evaluations show, HiPE is currently the fastest among all Erlang implementations and significantly lowers the performance gap between Erlang/OTP and high-performance implementations of other functional languages. More details at the homepages of HiPE and Erlang. Management of Software Engineering Knowledge Date: February 28 Place: Estraden, Time: 15.15 Kristian Sandahl, Professor installation seminar Abstract:Since the mid-90ies we have made contributions by documenting and improving industrial practices to increase quality and productivity in large-scale software engineering. We have been active in the areas of change impact analysis, prediction of software reliability, inspections, requirements engineering and software understanding. By working with empirical methods together with industry we are quite certain that our results are both relevant and valid, and as researchers we are satisfied with the publications and PhDx exams obtained. However, we have spent only marginal effort in the problem of how to feed back the knowledge to the development organization, and the goal of the seminar is to review some of these with an emphasis on our own ideas for RiSE (Research center for integrational software engineering), a sub-set of PELAB. The standard way is to improve the processes of the organization, but this takes time, increases the mental work-load of developers and processes are rarely as detailed as is needed. The alternate approach is to provide some kind of information system where the knowledge can be found implicitly or explicitly. Experience Factories are built to store and retrieve measurement data but the results are sometimes hard to analyze and transfer to new projects. Design patterns help in experience feed-forward about structure, but not so much on quality. Non-technical solutions comprise software professional development, work-shops, open-source etc. Carlshamre suggests in his recent PhD that knowledge about requirements can be stored in predefined attributes and that the amount of knowledge can be used to measure the maturity of each requirement. In RiSE we have suggested that requirements management systems can be extended to a knowledge management system by updating the requirements with aspects of the implementation realizing the requirements. How to Analyze Real World Multi-threaded C Programs Date: February 14 Place: Estraden, Time: 15.15 Helmut Seidl, Trier University Abstract: The main topic of our research is to explore in how far program analyzer technology can help to find programming errors in real-world multi-threaded C programs. Thus, the goal is not to get analyzers which run in a few seconds -- but produce thousands of unnecessary warnings which even are expensive, as they later-on have to be checked manually by highly paid software engineers. Instead, we aim at a better balance between precision and analysis time. We are clearly willing to spend even some minutes analysis time on larger programs - given only that the number of spurious errors is dramatically decreased. In the talk, I present the background concepts and implementation tricks which we have employed in our generator for inter-procedural analyses of multi-threaded C in order to arrive at sufficiently precise analyzes, e.g., of mutual exclusion properties which still have decent runtimes. RuleML: Data Model, Language Hierarchy, and Transformations Date: January 17 Place: Estraden, Time: 15.15 Harold Boley, DFKI Kaiserslautern. Abstract: This work is motivated by the Web exchange of business rules. First, commonalities of Logic Programming and XML are examined. An XML version of pure Prolog is then shown to be at the center of the Rule Markup Language. The RuleML Data Model uses Order-Labeled trees, combining the RDF and XML models of W3C. As part of RuleML's hierarchy of sublanguages, the RuleML-Prolog DTD is developed into an XML Schema. Finally, XSLT (XSL Transformations) is employed for practical XML-to-XML and XML-to-XHTML transformations of rules on the Web. Speaker's bio: Harold Boley is a senior researcher at the German Research Center for Artificial Intelligence (DFKI), where he acts as the W3C Advisory Committee Representative, and leads the EU project Clockwork on Web-based knowledge management for collaborative engineering. He is also a senior lecturer of computer science and mathematics at the University of Kaiserslautern, where he conceived AI-oriented XML and RDF courses. Dr. Boley's present focus is XML-based knowledge markup and RDF-based Semantic Web techniques. He was a visiting researcher in the Knowledge Modeling Group at Stanford University in 1999. Before that, he led several government and industrial projects in knowledge representation, compilation, and evolution. He received his PhD and Habilitation degrees in computer science from the Universities of Hamburg and Kaiserslautern, respectively. He developed the Relational- Functional Markup Language (RFML) and, together with Dr. Said Tabet, launched the Rule Markup Initiative (RuleML). Fall 2001NASA Space Robotics: State-of-the-art Assessment and Future Capabilities Date: December 13 Place: Planck, IFM, Time: 15.15 David Kortenkamp, NASA Johnson Space Center, Houston Abstract: This talk will present the current state-of-the-art in space robotics. It will cover both robotics for planetary surface exploration and for orbital assembly and maintenance. In addition to presenting the current state-of-the-art the talk will give ten year projections on expected capabilities. These projections are based on discussions with leading robotics researchers. This assessment is driven by a detailed break-down of robotic capabilities that are necessary for space operations. The breakdown includes mobility, sensing, manipulation, planning and execution and human/robot interaction. A series of metrics for each capability are used to assess the state-of-the-art and project progress. The talk will include video of various NASA robotics projects to illustrate current capabilities. Speaker's bio: David Kortenkamp received his B.S. in computer science from the University of Minnesota in 1988. He received his M.S. and Ph.D. in computer science and engineering from the University of Michigan in 1990 and 1993 respectively. His doctoral thesis described a method for integrating stereo vision and sonar sensing data on-board a mobile robot. While at Michigan, Dr. Kortenkamp led a team of researchers to a first place finish in the 1992 American Association for Artificial Intelligence Mobile Robot Contest. After receiving his doctorate, he began working as a contractor at NASA Johnson Space Center in Houston Texas. Dr. Kortenkamp was chair of the 1999 IJCAI Workshop on Adjustable Autonomy Systems, was on the program committee for AAAI-96, AAAI-97, AAAI-98, AAAI-99 and AAAI-2000 and was the co-organizer of the 1998 AAAI Mobile Robot Contest. He was also guest editor of a special issue of the Journal of Experimental and Theoretical Artificial Intelligence devoted to robot architectures and a guest editor of a special issue of Autonomous Robots. He, along with Pete Bonasso and Robin Murphy, edited the book Artificial Intelligence and Mobile Robots published by MIT Press in 1998. Dr. Kortenkamp serves as associate editor of the MIT Press Series on Intelligent Robotics and Autonomous Agents. He is author or co-author of six journal articles and more than a dozen refereed conference papers. Multiclock Esterel: An Unified Formalism for Synchrony and Asynchrony Date: November 22 Place: Estraden, Time: 15.15 R. K. Shyamasundar, School of Technology & Computer Science, Tata Institute of Fundamental Research Abstract VLSI circuit design has gained considerably from the introduction of hardware description languages (or HDLsx). While these languages are well suited to describe circuits in great detail, they are found wanting when attempting formal verification of circuits. VHDL is the de facto standard used in the VLSI industry and given the wide variety of tools that exists to carry out simulations for circuit specifications in VHDL, it behooves one to explore the possibility of interfacing it with synchronous programming languages to handle higher levels of abstraction in circuit design. In this talk, we show how the paradigm of multiclock Esterel provides a framework for the design of multi-clocked systems and asynchronous systems. We show how Multi-clock Esterel while preserving the synchrony features embeds Communicating Reactive Processes (CRP) proposed as a formalism for integrating synchrony and asynchrony and provides a unified framework for network of synchronous systems. It can also be used for modelling distributed timed systems. Further, Multiclock Esterel can be used for modelling in conjunction with VHDL to enable formal verification of circuit behaviour. We shall also discuss modelling of VHDL features in multiclock Esterel. Further, we shall also discuss multi-clock formalisms in other synchrnous languages. Integrated Deductive Software Design with the KeY Tool Date: October 25 Place: Estraden, Time: 15.15 Reiner Hähnle, Department of Computing Science, Chalmers University of Technology Speaker's bio: Reiner Hähnle is an associate professor (docent) in computing science and director of graduate studies at the Department of Computing Science, Chalmers University of Technology. He is also a senior consultant for Safelogic AB, Gothenburg. He received a PhDx in Computer Science in 1992 from University of Karlsruhe, and the title Universitätsdozent (Habilitation) from Technical University of Vienna in 1997. He joined Chalmers in January 2000. His main research interests are in software verification, automated theorem proving, and non-classical logics. He is currently Chair of the Technical Committee on Multiple-Valued Logic of the IEEE Computer Society and President of the Steering Committee of the TABLEAUX conference. Abstract: Assessments of the prospects of formal methods in software development widely agree that one can, in principle, increase software quality considerably by using formal methods, but they are considered to be too difficult and expensive to use in industrial practice. Among the biggest obstacles in the use of formal methods are their lack of integration with CASE tools and the missing support in creating formal specifications of software requirements. The KeYx tool, jointly developed at Chalmers and Karlsruhe University, is based on a commercial UML CASE tool for object-oriented software development in Java. In addition, it features seamless integration of formal specification and verification. An important aspect is user support for creating formal specifications of requirements. This is illustrated, for example, by our usage of the knowledge embodied in software design patterns: attached to each pattern are properly formalized schmatic properties and requirements that are typically associated with it. When the user selects and applies a pattern from the CASE tool's library, he also obtains suitably instantiated and relevant requirements expressed in the language OCL (Object Constraint Language), which is a subset of the industry standard UML. Other parts of the project concern generating natural language documents from OCL specifications, a verification system for full sequential Java, and an innovative interactive/automated theorem prover. In the talk I will first give an outline of the project and tool, and then highlight selected features by example. Models of Computation in Embedded System Design Axel Jantsch, Electronic System Design Laboratory, Royal Institute of Technology Date: September 27, Place: Estraden, Time: 15.15 Speaker's bio: Axel Jantsch received his Master and PhDx degrees in computer science from Technical University of Vienna, Austria in 1987 and 1993, respectively. Since 1997 he is associate professor at the Royal Institute of Technology in Stockholm. His current research interests include modeling, design and validation of embedded systems and systems on a single chip. Abstract: This lecture will present the main models of computation and concurrency, i.e. data flow models, clocked synchronous and perfectly synchronous models, and discrete event models. All these models and many of their variants are used in embedded system design. They are used for different purposes and in different situations. It will be illustrated how these concepts define and limit the potential use of a given language. There is a clear trend today towards the integration of these different computational models and the talsk will summarize the main approaches how this is done and give an outlook on the future developments. |
| |
|
|
|
| |
|
|
||||||||||||||||||||||
