Storage Management as Means to cope with Exponential Information Growth - Scheideler, Christian; Salzwedel, Kay; Meyer auf der Heide, Friedhelm; Brinkmann, André; Vodisek, Mario; Rückert, Ulrich (Proceedings of SSGRR 2003)
The advances in Internet technology have led to tremendous improvements in business, education, and science and have changed the way we think, live, and communicate. Information exchange has become ubiquitous by the possibilities offered through modern technologies. We are able to offer information 24 hours a day through our web sites and can leave messages every time and from anywhere in the world. This change in communication has led to new challenges. Enterprises have to deal with an information amount that doubles every year. The technological foundation to cope with this information explosion is given by Storage Area Networks (SANs), which are able to connect a great number of storage systems over a fast interconnection network. However, to be able to use the benefits of a SAN, an easy-to-use and efficient management support has to be given to the storage administrator. In this paper, we will suggest new storage management concepts and we will introduce a new management environment that is able to significantly reduce management costs and increases the performance and resource utilization of the given SAN infrastructure.

Performance of distributed algorithms for topology control in wireless networks - Rührup, Stefan; Schindelhauer, Christian; Volbert, Klaus; Grünewald, M. (Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS))
We try to close the gap between theoretical investigations of wireless network topologies and realistic wireless environments. For point-to-point communication, we examine theoretically well-analyzed sparse graphs, i.e. the Yao-graph, the SparsY-graph, and the SymmY-graph. We present distributed algorithms that can be used to build up these graphs in time $O(log n)$ per node without the use of any geo-graphical positioning system. Our algorithms are based only on local knowledge and local decisions and make use of power control to establish communication links with low energy-cost. We compare these algorithms with respect to congestion, dilation, and energy. For congestion we introduce different measures that allow us to investigate the difference between real-world wireless networks and models for wireless communication at a high level of abstraction. For more realistic simulations we extend our simulation environment SAHNE. We use a realistic transmission model for directed communication that uses sector subdivision. Finally, our experimental results show that our topologies and algorithms work well in a distributed environment and we give some recommendations for the topology control based on our simulations.

Implementierung und Vergleich von Verfahren zum Information Retrieval im World Wide Web - Mahlmann, Peter

Directed power-variable infrared communication for the mini robot Khepera - Volbert, Klaus; Grünewald, Matthias; Schindelhauer, Christian; Rückert, Ulrich (Proceedings of the 2nd International Conference on Autonomous Minirobots for Research and Edutainment)
Communication facilities are important in Robotics if several robots have to work together. In this paper, we describe problems and solutions encountered while designing an infrared-based communication device for the mini robot Khepera. In contrast to traditional omnidirectional systems, it features directed, power-variable transmission in eight directions at unit[23.4]kbps up to a range of unit[1m]. It can differentiate incoming data signals from interference from adjacent sectors and can estimate their direction-of-arrival. We model the transmission over the infrared channel and show how interference influences the reception of the data signals. We also describe methods how to reduce these effects. We have tested the performance of the resulted signal processing in a worst case scenario by simulations and in experiments with a prototype implementation. The resulted module is especially suited for experimental evaluation of ad hoc network protocols and for position estimation.

ADB-Trees: Controlling the Error of Time-Critical Collision Detection - Klein, Jan; Zachmann, Gabriel (Proc. 8th International Fall Workshop Vision, Modeling, and Visualization (VMV 2003))
We present a novel framework for hierarchical collision detection that can be applied to virtually all bounding volume (BV) hierarchies. It allows an application to trade quality for speed. Our algorithm yields an estimation of the quality, so that applications can specify the desired quality. In a timecritical system, applications can specify the maximum time budget instead, and quantitatively assess the quality of the results returned by the collision detection afterwards.

Time-Critical Collision Detection Using an Average-Case Approach - Klein, Jan; Zachmann, Gabriel (Proc. ACM Symposium on Virtual Reality Software and Technology (VRST 2003))

Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up - Fomin, Fedor V.; Thilikos, Dimitrios M. (Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003))
Graph minors theory, developed by Robertson & Seymour, provides a list of powerful theoretical results and tools. However, the wide spread opinion in Graph Algorithms community about this theory is that it is mainly of theoretical importance. The main purpose of this paper is to show how very deep min-max and duality theorems from Graph Minors can be used to obtain essential speed-up to many known algorithms on different domination problems.

TKDM – A Reconfigurable Co-processor in a PC's Memory Slot - Plessl, Christian; Platzner, Marco (Proc. Int. Conf. on Field Programmable Technology (ICFPT))
This paper presents TKDM, a PC-based high-performance reconfigurable computing environment. The TKDM hardware consists of an FPGA module that uses the DIMM (dual inline memory module) bus for high-bandwidth and low-latency communication with the host CPU. The system's firmware is integrated with the Linux host operating system and offers functions for data communication and FPGA reconfiguration. The intended use of TKDM is that of a dynamically reconfigurable co-processor for data streaming applications. The system's firmware can be customized for specific application domains to facilitate simple and easy-to-use programming interfaces.
Keywords: coprocessor; DIMM; memory bus; FPGA; high performance computing

The Case for Reconfigurable Hardware in Wearable Computing - Plessl, Christian; Enzler, Rolf; Walder, Herbert; Beutel, Jan; Platzner, Marco; Thiele, Lothar; Tröster, Gerhard (Personal and Ubiquitous Computing)
Wearable computers are embedded into the mobile environment of their users. A design challenge for wearable systems is to combine the high performance required for tasks such as video decoding with the low energy consumption required to maximise battery runtimes and the flexibility demanded by the dynamics of the environment and the applications. In this paper, we demonstrate that reconfigurable hardware technology is able to answer this challenge. We present the concept and the prototype implementation of an autonomous wearable unit with reconfigurable modules (WURM). We discuss experiments that show the uses of reconfigurable hardware in WURM: ASICs-on-demand and adaptive interfaces. Finally, we present an experiment with an operating system layer for WURM.

Instance-Specific Accelerators for Minimum Covering - Plessl, Christian; Platzner, Marco (Journal of Supercomputing)
This paper presents the acceleration of minimum-cost covering problems by instance-specific hardware. First, we formulate the minimum-cost covering problem and discuss a branch & bound algorithm to solve it. Then we describe instance-specific hardware architectures that implement branch & bound in 3-valued logic and use reduction techniques similar to those found in software solvers. We further present prototypical accelerator implementations and a corresponding design tool flow. Our experiments reveal significant raw speedups up to five orders of magnitude for a set of smaller unate covering problems. Provided that hardware compilation times can be reduced, we conclude that instance-specific acceleration of hard minimum-cost covering problems will lead to substantial overall speedups.
Keywords: reconfigurable computing; instance-specific acceleration; minimum covering

Virtualizing Hardware with Multi-Context Reconfigurable Arrays - Enzler, Rolf; Plessl, Christian; Platzner, Marco (Proc. Int. Conf. on Field Programmable Logic and Applications (FPL))
In contrast to processors, current reconfigurable devices totally lack programming models that would allow for device independent compilation and forward compatibility. The key to overcome this limitation is hardware virtualization. In this paper, we resort to a macro-pipelined execution model to achieve hardware virtualization for data streaming applications. As a hardware implementation we present a hybrid multi-context architecture that attaches a coarse-grained reconfigurable array to a host CPU. A co-simulation framework enables cycle-accurate simulation of the complete architecture. As a case study we map an FIR filter to our virtualized hardware model and evaluate different designs. We discuss the impact of the number of contexts and the feature of context state on the speedup and the CPU load.
Keywords: Zippy; multi-context; FPGA

Co-simulation of a Hybrid Multi-Context Architecture - Enzler, Rolf; Plessl, Christian; Platzner, Marco (Proc. Int. Conf. on Engineering of Reconfigurable Systems and Algorithms (ERSA))
Reconfigurable computing architectures aim to dynamically adapt their hardware to the application at hand. As research shows, the time it takes to reconfigure the hardware forms an overhead that can significantly impair the benefits of hardware customization. Multi-context devices are one promising approach to overcome the limitations posed by long reconfiguration times. In contrast to more traditional reconfigurable architectures, multi-context devices hold several configurations on-chip. On demand, the device can quickly switch to another context. In this paper we present a co-simulation environment to investigate design trade-offs for hybrid multi-context architectures. Our architectural model comprises a reconfigurable unit closely coupled to a CPU core. As a case study, we discuss the implementation of a FIR filter partitioned into several contexts. We outline the mapping process and present simulation results for single- and multi-context reconfigurable units coupled with both embedded and high-end CPUs.
Keywords: Zippy; co-simulation

Verteiltes Rendern durch dynamische Bildaufteilung - Terbahl, Martina; Krokowski, Jens (Proceedings of 5. GI-Informatiktage 2003)

Stability versus Speed in a Computable Algebraic Model - Ziegler, Martin (Proc. 5th Conference on Real Numbers and Computers (RNC5), INRIA)

Computable Operators on Regular Sets - Ziegler, Martin (Computability and Complexity in Analysis)

Behavioral Subtyping Relations for Active Objects - Wehrheim, Heike (Formal Methods in System Design)

Preserving Properties Under Change - Wehrheim, Heike (Formal Methods for Components and Objects, Second International Symposium, FMCO 2003, Leiden, The Netherlands, November 4-7, 2003, Revised Lectures)

Inheritance of Temporal Logic Properties - Wehrheim, Heike (Formal Methods for Open Object-Based Distributed Systems, 6th IFIP WG 6.1 International Conference, FMOODS 2003, Paris, France, November 19.21, 2003, Proceedings)

Checking Consistency in UML Diagramms: Classes and State Machines - Rasch, Holger; Wehrheim, Heike (Formal Methods for Open Object-Based Distributed Systems, 6th IFIP WG 6.1 International Conference, FMOODS 2003, Paris, France, November 19.21, 2003, Proceedings)

Using Coupled Simulations in Non-atomic Refinement - Derrick, John; Wehrheim, Heike (ZB 2003: Formal Specification and Development in Z and B, Third International Conference of B and Z Users, Turku, Finland, June 4-6, 2003, Proceedings)