Home > Research Groups > Algorithms and Complexity > Projects > Collaborative Research Centre 376

Collaborative Research Centre 376

The CRC (Collaborative Research Centre, Sonderforschungsbereich) 376:"Massively Parallel Computing: Algorithms, Design Methods, Applications'' was approved by the Deutsche Forschungsgemeinschaft (DFG) in 1995 and was funded until end of 2006. It started with the aim of developing methods and techniques for exploiting the computational capabilities of parallel processor networks, and of demonstrating the performance of the algorithmic solutions and the design methods produced for embedded, distributed (technical) systems on the basis of a variety of applications. Since then, the CRC has made essential contributions to this topic area and acquired international reputation. In addition, it takes account of the rapidly growing importance of networks as communication and information systems. Apart from the aspect of parallel high-performance computers, research has therefore begun to focus increasingly on areas such as usability of heterogeneous dynamic networks, for example mobile, wireless communication networks consisting of notebooks or mobile phones. During the last years, the aspect of self-organization of such systems gains more and more impact on our work.

The CRC is structured into the three project areas

  • Algorithms
  • Design Methods
  • Applications

The algorithmic orientation contributes to particularly efficient, i.e., runtime-optimizing solutions. Design techniques for embedded real-time systems and for specialized hardware are being developed in the method-based area. Both the algorithmic and methodological work is evaluated in applications. We therefore consciously selected applications that present challenges for our methods and techniques.

Project Area A: Algorithms

This area has started with the goal to develop parallel algorithms as well as algorithmic techniques that are needed to obtain efficient parallel algorithms. We have contributed parallel algorithms for basic problems from graph theory, geometry, cryptography, and numerical simulation. Our goal is to support the development of such algorithms and programs with the help of tools and software libraries that are comfortable to use and platform independent on the one hand, and yield efficient programs on the other hand. All this work is based on solid theoretical insights, and results in software libraries like VDS (load balancing), DIVA (global variables) and PUB (Programming library supporting the bulk synchronous parallel programming style) with many users worldwide. Over the years, we have more and more moved from monolithic parallel computers towards networks with a strong focus on dynamics and heterogeneity. The last years and much of our current work focuses strongly on the dynamics and the necessity for self-organization by simple local rules, and explores, e.g., game theoretic methods for such tasks.

 This area consists of three subprojects:

  • A1 Efficient Parallel Algorithms (Meyer auf der Heide)
  • A2 Universal Basic Services (Meyer auf der Heide, Monien)
  • A3 Balancing Dynamics Networks: Foundations and Applications (Blazy, Monien)

Project Area B: Design Methods

This area has investigated techniques and tools which support the design, the realization and the comfortable use of massively parallel systems. We have specifically focussed on reactive parallel systems with real-time constraints. Also in this project area, our latest work takes mobility of components and self-modification as a response to changes in the environment into account.

This area contains only one subproject:

  • B1 Design Methods for Massively Parallel Real-Time Systems (Rammig)

Project Area C: Applications

This area aims at demonstrating the usefulness and quality of our algorithms and design methods in a variety of application scenarios. Each of them constitutes a challenge for the findings of areas A and B and of the respective problem-specific research on the one hand, and has scientific and/or economic impact on the other hand. Much of our latest work explicitly extends applications so that dynamic scenarios have to be dealt with, e.g., in mobile ad-hoc networks or compounds of spacecrafts.

 The subprojects in this area are:

  • C1 Cross-way Management (Lückel)
  • C2 Nearly real-time hierarchical Planning and Controlling of Networked Production Systems (Dangelmaier, Rosenberg, Bock)
  • C6 Mobile Ad-Hoc-Networks (Meyer auf der Heide, Rückert, Schindelhauer)
  • C10 Efficient Control of Formation Flying Spacecraft (Dellnitz, Junge, Preis)

For further details see the Website SFB 376  (German only).