1. Abstract
High computing performance can only be achieved by a combination of
powerful computer systems and algorithms that solve the given
application problems as efficiently as possible. Therefore, the
development of efficient algorithms has established itself as a
classical branch of computer science. In our research area, we
concentrate on solutions where current technological possibilities
such as computer networks used as high-performance computers pose new
challenges for algorithm development.
2. Focus in research and education
Modern
computer systems enable expanding application areas: Parallel
computer networks can deal with extremely complex algorithmic
problems; the Internet realizes global exchange of information and
the interconnected computers may possibly serve as one giant parallel
computing device; wireless communication systems allow flexible
communication between mobile stations; graphics applications with
hardware support display real-time navigation in complex virtual
scenes. A special challenge is given by computing systems consisting
of heterogenous components (e.g. Different powerful processors,
storage devices or communication capabilities) with structural
changes within time. In this year our focus turned on the algorithmic
challenges imposed by the realisation and efficient usage of such
heterogenous, dynamic systems.
Parallel computer networks can potentially supply unlimited computing power. However, the efficient use of these networks is an extremely complex problem. We provide users with a programming environment, the PUB-libarary, that is easy to handle and guides them towards the development of efficient algorithms. In order to support such an environment, efficient implementations of basic routines for communication and synchronization are needed. Meanwhile our PUB-library is used by an international audience, valueing an efficient and straight-forward environment for parallel computing. The latest extension of the PUB-library takes into account the special problems of heterogenous local area networks (LAN) and makes efficient use of the idle-times of the participating computers.
To be able to navigate in a virtual 3-dimensional space, and to give a realistic optical impression of the changing scene, enormous demands are imposed on the underlying data structures that handle the scene. Above all, we have to guarantee real time processing in order to guarantee a realistic impression of the scene. Our work on the development of such new types of data structures are incorporated into our prototype walk-through system ParSIWal.
Dynamic networks,i.e., networks whose nodes change their (geometric, geographic) position over time, play a major role in many areas: They can, e.g., be used as data structures for moving objects in Computer Graphics, as well as models for wireless mobile communication networks. We systematically model various kinds of dynamic networks, design algorithms, and apply them to the above mentioned Computer Graphics and communication problems.
The algorithmic work described above has shown us that using randomized procedures can produce amazing gains in efficiency. We are therefore systematically studying the potential of randomized algorithms and using, or developing, probability theory for analyzing such algorithms.
Our research is closely linked to our teaching. Our courses deal with methods and concepts of the development and analysis of efficient algorithms. We also run project groups and support diploma thesis that apply our theoretical insights in order to design efficient algorithms and libraries.
A prominent reason for this difficulty is the variety of different hardware systems which makes it hard to write portable parallel programs or maintain large parallel software systems. Hence, an abstract model is needed that includes all of the important performance-relevant features and hides hardware specific solutions - a so-called bridging model, that means a "parallel analogue" to the von Neumann model. We extended Valiant's Bulk Synchronous Parallel (BSP) bridging model and implement and evaluate the PUB library (Paderborn University BSP) that enables the programmer to write portable efficient parallel programms that can be run on a variety of different parallel computers.
Interconnecting different, but "usual" PCs by fast networks allows to employ such heterogeneous PC Clusters as parallel computers. Our PUB library has been ported to a PC cluster under the operating system Linux. The migration of processes has been realised, that means that a single PC that is heavily loaded by many processes (even from other users) can send some of its jobs to less loaded Pcs. Due to the fact that such a network may consist of single machines with quite different performance and that in such a network the load and, hence, the available computing power, of the single machines can vary quite considerably during the runtime, new algorithmic challenges emerge in the context of load balancing and of scheduling.
As PC Clusters are considerably less stable than classical parallel computers, for it is quite probable that from time to time single machines are switched off or are installed newly in the network, we enhance the PUB library by functionalities that ensure a stable behaviour of the overall system.
Dr. rer. nat. Rolf Wanka Phone: +49 (0)52 51 60 64 34 Fax: +49 (0)52 51 60 64 82 Email: wanka@upb.de URL: www.upb.de/cs/wanka.html
Mobile electronic devices (PDA, laptop, mobile phones) are connected
to wired networks, e.g. the Internet, by centralized protocols (e.g.
GPRS, UMTS). In such hierarchically structured networks an increase in
the number of participants results in reduced quality of service.
Mobile ad hoc networks (MANET) rely on a different, namely decentralised, approach. Without a fixed infrastructure a MANET imposes less restrictions for mobility and increasing network density even improves network properties like connectivity and data throughput.
Our research concentrates on the analysis and implementation of suitable algorithms for network management and routing in MANETs. In cooperation with the system and circuit technology working group we implement a prototypical MANET based on the mini-robot Khepera.
In this first period of our project we model, analyze and simulate mobile ad hoc networks. On the physical level we allow variable transmission power and for each station sectorized parallel communication. One result of our work is the development of meaningful complexity measures for the efficiency of the routing in such a wireless network: Dilation, Energy and Congestion. We provide distributed algorithms which build up basic networks, which are optimized with respect to these measures. However, in general it is not possible to construct a protocol, that optimizes more than one measure at the same time. Two of these parameters, energy and dilation, are even incompatible.
On the positive side it turns out that there exists a sparse general-purpose network which enables effieient routing with respect to all these complexity measures (one at a time). Our simulations show that such a communication network as well as a sectorized version can be realized on an embedded, distributed system like a herd of Khepera robots.
PD Dr. rer. nat. Christian Schindelhauer Phone: +49 (0)52 51 60 64 52 Fax: +49 (0)52 51 60 64 82 Email: schindel@upb.de URL: www.upb.de/cs/schindel.html
Recently, we were able to improve our heterogeneous distribution strategy. We could show that our two new approaches, namely SHARE and SIEVE, are close to an optimal solution. Because such techniques are of high practical interest in modern storage systems we used the SHARE strategy to implement a storage virtulization prototype. It was realized under Linux and consists of a device driver and a graphical management tool. With this virtualization we are capable of decreasing the management of large storage systems and providing transparent and vendor indepentent storage solution.
Kay Salzwedel Phone: +49 (0)5251 606458 Fax: +49 (0)5251 606482 Email: nkz@upb.de URL: www.upb.de/cs/salzwedel.html
In large parallel and distributed systems the bandwidth of the
interconnection
network is usually the major bottleneck for the performance of
distributed
applications. In these systems a data management strategy has to
ensure that
the communication overhead caused by remote accesses to shared data
objects is
as low as possible. Therefore it is important to distribute the load
evenly
among all network resources and not necessarily evenly among the hard
disks, as
in the storage network scenario.
We have developed data management and routing strategies that obtain the optimal communication load up to a polylogarithmic factor in general topology networks. The routing strategy has the remarkable property that it is oblivious, i.e., the routing paths are chosen completely independent from the current traffic in the network. Hence, these strategies can be implemented very efficiently due to their simple structure.
Harald Räcke Phone: +49 (0)5251 606457 Fax: +49 (0)5251 606482 Email: harry@upb.de URL: www.upb.de/cs/raecke.html
Another example for huge data sets can be found in telecommunication industry. AT&T, for example, maintains call-detail statistics which contain the called number, the caller's phone number, time, date, and length of the call, as well as data about the billing. Overall, AT&T serves about 200-300 million calls per day and the size of the gathered call-detail data is more than 7 GB. It is often impossible to process data sets of this size with standard linear time algorithms and thus there is a lot of research in new techniques to deal with huge data sets.
One of these techniques is the so called 'Property Testing'. The goal of property testing is to decide whether a given huge object has a (global) property or is far away from any object that has the property. This task should be achieved by only looking at a small sample of the object. We introduced a general framework to analyze property testing algorithms with one-sided error. We analyzed property testers for clustering problems, graph and hypergraph coloring, and a reversal distance property using our framework.
Related to property testing are the so-called sublinear approximation
algorithms. The goal of a sublinear approximation algorithm is to find
an approximate solution to an optimization problem in sublinear time,
that is, without looking at the whole input. In this area we developed
an algorithm that uses a sublinear number of range queries (e.g.,
orthogonal range queries, simplex range queries) to approximate the
weight of the Euclidean minimum spanning tree of a point set. Such
range queries are supported by many fundamental data structures.
We also proposed to use 'smoothed analysis' instead of 'worst case analysis' as a measure for the complexity of motion. We consider a set of moving objects and we want to maintain a combinatorial structure uniquely defined by the position of these objects. In such a scenario one can measure the complexity of maintaining this particular structure by analyzing the maximum number of changes that occurs in the structure under linear motion. Smoothed analysis means to analyze the worst case when the input is subject to small random perturbations. Since practical inputs often do not behave exactly like the worst case (e.g., when the worst case occurs in lower dimensions) we think that smoothed analysis is better suited for the analysis of the complexity of motion.
Using this method we analyzed the smoothed number of combinatorial changes that occur when the smallest bounding rectangle of a point set is maintained under continuous motion.
Dipl. Inf. Christian Sohler Phone: +49 (0)5251 606427 Fax: +49 (0)5251 606482 Email: csohler@upb.de URL: www.upb.de/cs/csohler.html
The main focus of our research consists of the development of virtual
reality systems for highly complex scenes that cannot completely be
stored in main memory:
For the computation of an approximate image of the scene, a sampling technique is used. In the preprocessing, a so-called sample tree is built whose nodes contain randomly selected polygons from the scene. This tree only uses space that is linear in the number of polygons. In order to produce an image of the scene, the tree is traversed and polygons stored in the visited nodes are rendered. During the interactive walkthrough, parts of the sample tree are loaded from local or remote hard disk.
We implemented our algorithm in a prototypical walkthrough system.
Analysis and experiments show that the quality of our images is
comparable to images computed by the conventional z-buffer algorithm
regardless of the scene topology.
Jens Krokowski Phone: +49 (0)5251 606491 Fax: +49 (0)5251 606482 Email: kroko@upb.de URL: www.upb.de/cs/kroko.html
The paper of Matthias Grünewald, Tamas Lukovszki, Christian
Schindelhauer und Klaus Volbert "Distributed Maintenance of Resource
Efficient Wireless Network Topologies" was rewarded as one of two
"Distinguished Papers" at the Euro-Par-Conference.
4.4 Appointments/Chairs
Friedhelm Meyer auf der Heide declined a call to a professorship at
the University of Augsburg.
Program comittee memberships:
Rolf Wanka:
Secretary of the Special Interest Group on Parallel and Distributed
Algorithms of the German Computer Society
Foreign Relationship Officer of the Paderborn Computer Science.
4.5 Projects
