Special Research Area (SFB) 342: Methods and tools for the utilization of parallel systems

Chairman: Prof. Dr. Arndt Bode
Email: bode@informatik.tu-muenchen.de

The starting point for the planning of special research area 342 (SFB 342) originated from the fact that since the end of the 80's, the main reason for the lack of utilization of parallel system was not so much a problem of supplying the appropriate hardware, but rather the appropriate software, programming methods, and algorithms. The goal of the SFB 342 was therefore to establish a more effective utilization of parallel methods and tools while mainly using commercially available computing systems. It is the intention to support the whole process of design and development of parallel and distributed application with the goal to achieve improvements in all areas, starting with the conception of parallel algorithms with appropriate complexity estimation, over the specification, and the late phases of the design, all the way to the execution and evaluation on the target system. Additionally, it was a substantial goal to test and evaluate the developed methods and tools on the basis of a whole range of strategic applications with extensive requirement profiles. Accordingly, the entire SFB was initially divided into two project areas; one dealing with methods and tools and the other working on the applications. Due to the inclusion of further subprojects from industrial partners (presently from Siemens AG), the SFB was later extended by another project area. With the addition of new subprojects and the ending of others, less than 50 % of the projects of the initial project application are involved. This fluctuation of the work of the SFB also shows the flexibility of this funding instrument with respect to modifications of the research focus.

The SFB was created on January 1st, 1990 to (first provisionally) December 31st, 1991. After three successful reviews, it is currently in its fourth and last funding period from January 1st, 1998 to December 31th, 2000. Of its research staff consisting of around 100 people, approximately 25 % are financed through the DFG, the German science foundation. The remainder receive funding through the federal states and the industrial partners. According to the locality principle of the DFG, the SFB is composed only of research scientists from the Munich area. Nearly all subprojects are conducted by the Department of Computer Science at the Munich University of Technology (TUM). The only exceptions to this are the subprojects B1 and B4 (conducted by the Department of Electrical Engineering at TUM) and the work done by the industrial partners. Additionally, two subprojects from the Humboldt University Berlin, a university located in the former GDR, were temporarily associated with the SFB. The integration of (internal) industrial partners into the work of the special research area (SFB) also included their participation in the reviews required by the German Science Foundation (DFG) at the end of each founding period, although they did not receive funding from the DFG for their work. This participation in the reviews was voluntary with the goal of improving the cooperation between academic and industrial research within the SFB. Besides the current cooperation of the two subprojects with the Department for Research and Development at Siemens AG, Munich, one subproject was also in temporarily cooperation with the European Supercomputing Development Center of Intel GmbH in Feldkirchen near Munich. Besides these (internal) formal cooperations, the special research area also held contact with a large number of (external) partners in academia and research in Germany and abroad. However, mentioning them all would exceed the scope of this report. Since its establishment, the Graduiertenkolleg "Cooperation and Resource Management in Distributed Systems" on January 1st 1995 (chairman: Prof. Dr. P. P. Spies) at the Technische Universität München (TUM) also strongly cooperates with the SFB.

Programming parallel and distributed computer architectures, in contrast to the programming of PCs, workstations, and mainframes, is still to a large extent architecture and manufacturer-dependent. However, differentiation of at least three classes of similar programming models can be distinguished:

Message based programming of systems with distributed memory
Parallel programming on the base of shared memory
Parallel programming on the base of (virtual) shared memory on top of physically distributed memory

Due to the need for explicit parallelization, the message-based programming model is commonly seen as the most difficult model. However, due to its principal scalability, it is also regarded as potentially the most powerful. Consequently, SFB 342 initially focused primarily on multiprocessor systems with distributed memory and message passing. These systems also have a comparable programming model as networks or clusters of workstations and PCs, which are currently gaining increasing importance. Besides these systems, several other classes of machines have also been utilized, mainly to provide a basis for comparison. This includes shared memory architectures, virtual shared memory systems, traditional super computers based on the (vector-) pipeline principle as well as single PCs and workstations. For this purpose, the special research area had and has access to a large number of systems maintained by the department of computer science as well as systems provided by partners that can be accessed using the Internet. A shift of the emphasis in the work of the special research area arises as a result of the integration of heterogeneous networks of systems: While the systems mentioned above generally consist of homogeneous processor nodes, which in addition are often exclusively used by a single application, networks of systems exhibit heterogeneity in relation to both functionality and performance. In addition, the effects of the utilization of systems in multiuser mode on parallel and distributed applications need to be taken into account. Futhermore,a combination and integration of shared memory and message passing programming models is an obvious point of interest due to wide spread use of symmetric multiprocessor systems. These systems have increasingly become popular as their multiprocessor internal bus system is directly supported by the newest microprocessor generation. Based on fast interconnection technology, SMPs are often used as building blocks for larger systems which possess distributed memory properties, but may be organized based on the distributed shared memory principle.

A Foundations and tools for the virtualization of parallel architectures

A1 Integration of tool environments and system architectures suited for parallelization (Bode, Hellwagner)
A3 Specification, analysis, and modelling (SAM) (Brauer, Esparza)
A5 Parallelization in inference systems (PARIS) (Fronhöfer, Jessen, Radig)
A6 Methods for the design of distributed systems (Broy)
A7 Efficient parallel algorithms and schedules (EPAS) (Mayr, Steger)
A8 Concepts and methods for constructing heteromorph parallel systems (Spies)

B Methods and applications for the virtualization of parallel architectures

B1 Parallelization and design methods for highly integrated circuits (Antreich, Johannes)
B2 Parallelization of database systems (Bayer, Mitschang, Paul)
B3 Parallelization of hierarchically structured, numerical algorithms. (Zenger, Huckle)
B4 Parallel simulation of highly complex digital systems (Antreich, Johannes)

C Industrial subproject, Siemens AG (Gonauser)

C1 Architecture driven load balancing of database loads on NUMA-architectures; reliability and error tolerance of parallel and distributed systems (Borrmann, Schiemann)
C3 Parallel and distributed simulation of complex systems (Gilg)

Project area A: Foundations and tools for the visualization of parallel architectures

Based on results achieved during the last funding period, project area A continues the development of methods for parallelization and tools for the design and analysis of parallel methods and architectures. In all activities, the emerging change of paradigms towards distributed shared memory and network computers is taken into account. Continuing the efforts from the beginning of the special research area (SFB), all results from the project area A are being utilized by project area B for development of efficient algorithms as well as for the evaluations and experience. Contemporaneously, results from project area B will influence the further development of tools.

As in the previous funding period, the goal of the work done in subproject A1 is research in the area of the functionality and implementation of tools for the late design phases and the execution of parallel and distributed programs on a wide variety of architectures. Moreover, a second goal, likewise with the previous funding periods, is to provide these tools to other subprojects within the SFB as well as to external partners. During the next funding period, work is concentrated on shared memory systems and clusters of systems with distributed shared memory. A parallel object oriented programming model on top of an SCI based cluster of PCs with distributed shared memory is provided and supported by an OMIS compliant monitoring system and an interactive performance analysis tool. This system is then tested and evaluated with the help of applications from within the SFB. The main motivation for this is to allow applications to take advantage of the high performance communication of SCI clusters. It is one of the main topics in the coming funding period to prove that the portability of tools for message passing systems can be extended to distributed shared memory and network computer systems.

During the last funding period subproject A3 has been working in the areas of the specification, analysis, and modelling of distributed systems. The work in the area of analysis within the work fields "Concepts and Methods for Base Calculus" and "Verification Based on Model Checking" has lead to several new questions. Consequently, there has been a shift and a concentration of focus topics in the area of analysis and verification compared to the last funding period. The main goal in the next funding period is the design, implementation, and evaluation of automatic and interactive verification techniques for reactive and distributed systems with finite or infinite state spaces. During the last funding period, two verification formulations for finite state spaces have been examined. Building on the results from this work, there are two new work areas for the next funding period. A third work area is the continuation of the examination of systems with infinite state spaces, which is now extended to calculus with structural variability. The fourth work area is the development of software tools needed to perform case studies.

The central goal of subproject A5 during the next funding period is the development of further new and powerful paradigms for parallel theorem provers and to achieve the broad practical application of parallel theorem provers for real world applications. The research in subproject A5 has so far concentrated mainly on a new quality in prover performance of the already powerful parallel proving systems SPTHEA and RCTHEO, mainly to be able to solve harder proof problems. The result was the concept for the cooperative theorem prover CPTHEO. During the next funding period, the already theoretically developed cooperation concept of CPTHEO will be implemented and enhanced. Focus points in this research are techniques for evaluating and filtering. Experience shows that with current high performance proving systems appropriately prepared proofs can be solved. The optimal tuning of the parameters for a proof run, however, requires detailed knowledge about theorem proving on the user's side. This reduces the level of acceptance with non-experts. A proving system that conducts a parallel competition between several strategies and parameter settings can help to solve this problem. It is the goal of the next funding period to develop the theorem prover STRATHEO based on this new paradigm of dynamic competition between strategies and to enable a stable integration into application systems that are important for the SFB.

During the last funding period, methods for the formal application-oriented program development have been prepared in subproject A6 to an extent that is was already possible to deploy some of them in a few application areas, like dynamic or object oriented systems. Future plans involve a methodical extension of the Focus-approach to a general model and with that a further development of description techniques with industrial character. Another focal point will be the work on approaches for the conduction and methodical support of proofs. The tool prototype AutoFocus must be extended to be able to integrate it with interactive and automatic proving tools. According to the increasing orientation towards applications, the development of concrete methods for specific applications, like for instance broadband multimedia networks, is planned as well as a tight cooperation with the work in subproject A8 and the analysis for security in computer systems.

Subproject A7 deals with the development of efficient parallel algorithms, the parallelization of basic programming paradigms, the projection of program constructs onto architectures, and the development and analysis of algorithms for the solution of load-balancing and scheduling problems. These problems, for which efficient parallel algorithms are being sought, are partially deducted from problems in other application oriented subprojects. A focal point of the work in A7 lies in the handling of scheduling problems. In addition to others, efficient parallel algorithms for the solution of polynomial scheduling problems and online algorithms for the scheduling of parallel job systems are being developed and analyzed. Furthermore, the scheduling of communication connections in networks is also receiving attention. This is increasingly becoming important due to the increasing spread of new network technologies in the area of parallel and distributed systems. The goal of the research in subproject A8 is the development of concepts and methods for the specification and automatic realization of distributed applications on the basis of networked hardware configurations. With the help of a language based, top--down oriented systemwide approach, distributed systems for parallel problem solving at a high degree of abstraction will be developed. The realization of this will be accomplished based on application specific information in several steps which are structurally non-altering. The goal of the next funding period is the development of an innovative ready-to-use distributed system which can be incrementally improved by use of the capabilities of dynamic reversibility of this stepping process and by its incremental extensibility. A further goal is to apply the developed methods to secure systems and demonstrate their contribution for high quality systems.

Projekt Area B: Methods and applications for the virtualization of parallel architectures

It is the goal of project area B to evaluate, demonstrate, and apply the foundations and methods for parallelization mainly from project area A based on real-world applications.

The close connection between fundamental research projects and and both application and industrial side projects within a single special research area offers the best prerequisite to achieve this goal. It also allows to directly utilize the knowledge and results from earlier funding periods for better solutions of the applications problems without any delay. Reciprocally, the experience from parallelizing applications are directly influencing the research projects in project area A. The installation of cross topics as well as the emphasized continuation of bilateral cooperations will in the next funding period also form the basis for the successful conduction of successful application projects.

A special matter of concern of project area B is the examination of praxis relevant real-world applications and the preparation of the developed prototypes for industrial usage. These goals are supported by the continuation of the close cooperation with project area C, the industrial side project of the special research area (SFB), and the technology transfer area that has been positively evaluated as pre-applications.

The applications projects are therefore targeted towards two goals: on one hand, they are being used for the evaluation of concepts and methods while on the other several important real-world application problems are being parallelized. Depending on the problem and the hardware architecture on which they are based, several different optimizing criteria are emphasised: First, it seemed to be most important to increase the efficiency (the speedup) of the parallel processing. However, with the rapidly growing problem of size and complexity, the structure of the growing data set sizes in a distributed memory is gaining increasing importance. In general, development towards hybrid forms of networks with shared and distributed memory can be seen, meaning the computer architectures are increasingly becoming heterogeneous. To solve the problems coming out of this kind of environment, methods for automatic load balancing and partitioning of the distributed resources are becoming of greater interest.

During the next funding period, project area B will comprise five subprojects including subproject B5 which has been split off from subproject B2 due to thematical reasons without causing any extra workload for the overall project. These five subprojects cover a wide variety of application areas allowing the special research area to evaluate its concepts for parallelization on the basis of very different requirements and prerequisites.

Like before, subproject B1 deals with the two applications layout synthesis and test preparation from the area of automation of integrated circuit design. Initiated by large technology advanced in the area of production- and design technologies, more complex systems with up to one million cells on a single IC can be implemented. Along with increased demand for fast and bug free designs, the performance boundaries of current sequential machines are pushed to the limits. This is especially true for the very demanding problems mentioned above. To overcome bottlenecks, it is of special interest to utilize networks of workstations. The level of acceptance of parallel design tools in the industrial environment depends to a large degree on the fact to what extent existing environments in the form of desktop workstations can be directly utilized. Because of this, the following goals will be perused during the next funding period: Based on the previous work that was mainly intended for homogenous workstation clusters, new methods for the circuit design will be developed that are also applicable in heterogeneous environments. In addition, more sophisticated and complex models will be used to improve the design quality as well as the integration and concurrent solving of previously separated costly design steps.

The research area of the subproject B2 is parallel database systems. This modern database technology offers the potential to overcome the limitations of current database systems with respect to data capacity, response time, and transaction rates and to also fulfill future requirements. The planned work in this subproject is based on the available sequential relational database system TransBase and will continue the development of the prototypical parallel database system Midas during the next funding period step by step. This system is a shared disk database system that is running on networks of workstations. The emphasis during the development is put on flexible optimization and parallel processing in the request processor, integration of parallel processing and extended database functionality, the parallelization of given applications systems, and the integration of a transaction and activity management.

The subproject B3 deals with the design, the analysis, and the implementation of parallel numerical algorithms. The focal point of the research are hierarchically structured problems that can also be increasingly found in real-world applications. Especially for the solution of highly complex problems that are predestined for parallelization, hierarchical approaches and the deployment of "divide and conquer" strategies offer significant advantages. Due to the recursive structures of the algorithms and the data structures on the one and the mostly already present networks of workstations at the site of the potential users on the other side, the target architecture for this subproject will be tree- and dual-hypercube-like structured networks of workstations. In continuation of the work conducted in the previous project phases, the numerical methods will be prototypically examined on the basis of two applications: the simulation of currents and the layout computation of integrated circuits. For both algebraic multi-grid methods will be further developed with the goal to reduce the communication significantly by applying problem-specific raw grids and mostly local computation. A further focal point of the research is the solvers for partial differential equations. With the help of the functional dataflow language FASAN that has been developed during the last funding period, an automatic generator for the communication tasks will be implemented and form the base for the implementation of a load balancing system.

The central topic of the subproject B4 is the simulation of integrated circuits. Application implementations for this kind of problem are very well suited for parallelization. The main goal of the circuit design process is to guarantee the correct functionality. This is also the reason why simulators are deployed by circuit designers more than any other tool. However, often the simulation times form a bottleneck. This problem is futhered worsened because increasing requirements with respect to error provness and reliability of circuits call for both the simulation of whole systems as well as more precise and complex models. Both lead to a more complex and demanding simulation. Three topics will be dealt with within this subproject: The planned research work is based on an optimistic simulation strategy, the time--warp--method, which has already been deployed very successfully in previous project periods. The goal in this area is to develop improved dynamic load balancing and flexible partitioning strategies to allow an efficient simulation on networks of workstations with heterogeneously distributed resources. Building on this intense experience with the time-warp-method that is available in this subproject, a parallel simulator will be implemented that is suited for circuits that are corresponding to the well normed modelling rules of Vital. This will allow an evaluation of the parallelization methods on the basis of real-world, industrial examples and with that also increase the level of acceptance in the industrial environment. In close cooperation with the subproject C3, powerful partitioning methods for simulations at transistor level will also be developed. This is becoming increasingly important due to the increase in the utilization of analog circuits parts.

The new subproject B5 deals with questions of load balancing in object-oriented distributed environments. Load balancing, fault tolerance, and exception handling have been examined during the last funding periods in subproject B2 with respect to database applications. Implementation studies on the basis of prototypical implementations show encouraging results. This work will be evaluated on a general basis for several application areas. Consequently, the group for this project will be taken out of subproject B2 and will form a new subproject on its own during the next funding period. The goal of this subproject is the development and prototypical implementation of an object oriented framework with the intention to support the application programmer of CORBA applications to realize load balancing. During this work, modern object oriented software development methods will also be taken into account and software patterns will be developed which will help in the integration of the load balancing techniques. The integration of an observation and analysis tool will ease the evaluation and improvement of the load balancing. The CORBA standard for distributed object oriented application has been chosen as a basis due to its increase in acceptance in the commercial area and its large flexibility with respect of communication in heterogenous networks of workstations. Load balancing, however, is currently not sufficiently supported in CORBA. The planned work will close this gap and will aid the application programmer in the development and analysis of load balancing systems.

Projekt Area C: Industrial sideproject, Siemens AG

Due to the increasing software complexity, the coupling of several workstations to parallel systems over LAN (Local Area Network) or WAN (Wide Area Network) interconnection networks is increasingly gaining importance. Those systems need management and software mechanisms to solve the architecturally inherent problems; heterogenous subsystems should cooperate with each other and a high total system performance should be delivered.

The boundary conditions under which load balancing with the goal of increasing the system performance in heterogenous systems can be applied are not sufficiently known. This includes the selection and offering of distribution mechanisms and administrative interfaces as well as the efficient cooperation of different distribution strategies. Finally, the increasing utilization of mobile systems calls for new paradigms of load balancing and a fault tolerant approach to temporary connections.

In cooperation mainly with subproject B5, the requirements for systems and applications will be examined in order to effectively deploy middleware like CORBA (Common Object Request Broker Architecture) or JAVA. This includes the integration of load-balancing. In addition, new application areas for middleware will identified and opened up for future work.

Besides this, the successful applications from subproject C3 will be further extended. Additional influences from the deployment of the parallel systems mentioned above have to be analyzed and taken into account. The positive experience from subprojects C3 and B4 from the last funding period form an encouraging basis for the continuation of the close cooperation between academia and industry. The knowledge from subproject B4 in the area of partitioning and the application experience of the circuit simulation team of the Siemens AG will together influence the work on new approaches which will be immediately tested with highly complex industrial circuit designs.

The subdivision of the special research area in project areas and subprojects is according to the guidelines for this kind of funding program. Orthogonal to this division, several common questions and research areas arise which are solved by the staff of several or even all subprojects. To organize this endeavor, several so called cross section projects have been initiated. These projects form the framework for the scientific cooperation for specific topics. Like the subprojects, these cross section projects are also subject to constant change according the current research activities. Currently the following topics are examined:

HEUROPA (Heuristic optimization of parallel execution)
UPAS (Universal programmable architecture and base software)
IBIS (Special interest group proving systems in the special research area)
ALV (Application oriented load-xbalancing)
Efficient algorithm
Change of paradigms in hardware and software

The efficient utilization of parallel and distributed systems is the topic of intensive research worldwide. Despite this, many problems with respect to scaling properties, portability, observation abilities, and productiveness or programming have not yet been solved. A new challenge for the future will be the support of heterogenous systems that are becoming widely available due to the current development in new network technologies with significantly improved latency and bandwidth properties. These allow the utilization of heterogenous workstations of different hardware, computational power, and system software as parallel systems. Due to the heterogeneity with respect to hardware and software as well as to the general existing multi-user utilization of individual systems, new requirements for a global system and resource management emerge. The newest microprocessor systems call for systems with shared memory multiprocessor in the small and networked systems with distributed memories in the large scale. To accomplish this, programming models for shared memory and message passing have to be combined. As for the tools for the development of parallel programs, the gap between methods for the early stages of the design, for instance formal specification, and the late stages have to be closed. The solution of these problems will also greatly influence the deployment of parallel and distributed systems in the industrial environment.