ERCIM News No.21 - April 1995 - FORTH

First LYDIA Workshop on Load Balancing

by Christos Nikolaou and Maria Karavassili

A one-day workshop on load balancing was held in Heraklion, Crete on the 25th of November 1994 within the first internal workshop of the ESPRIT Basic Research Project LYDIA. The workshop was organized by FORTH-ICS and attended by about 25 researchers.

"LYDIA - Load Balancing on High Performance Parallel and Distributed Systems" is a new ESPRIT project (BRA 8144) running since June 15, 1994 and for the next 3 years, with the following partners: Institute for Computer Science - FORTH, Ecole des Hautes Etudes en Informatique - University of Paris V, SNI, University of Zürich and University of Dortmund. The objective of the workshop was to present current research activities on the topics related to the research curried out within LYDIA.

The topics covered by the papers were job management tools, parallel programming environments and tools, queuing and scheduling, load balancing and transaction management. Five paper sessions were organized:

Distributed systems: a case study

Prof. Sape Mullender, University of Twente, presented ongoing work in Pegasus (BRA 6586). The goal of Pegasus is to create an architecture for a general-purpose distributed multimedia system and to build an operating system for it, that supports multimedia applications. Prof. Mullender presented the architecture of Pegasus and a QoS architecture and briefly discussed some ideas on scheduling the periodic processes that typically process samples and frames.

Job Management Tools

Two talks on job management tools were given within this session. In the first, "PVM applications on a world flock of condors", Prof. Miron Livny, University of Wisconsin, spoke about the growing importance of batch management tools and mainly about the Condor distributed batch system and the experiences from its operation.

The second talk by Prof. W. Gentzsch, GENIUS, concerned CODINE, that is targeted towards the optimal utilization of the compute resources of heterogeneous networked environments, in particular large heterogeneous workstation clusters with integrated compute servers like vector and parallel supercomputers. It offers a batch queuing framework by providing dynamic and static load balancing, checkpointing and by supporting batch, interactive and parallel jobs.

Parallel Programming Environments and Tools

Dr. Francoise André, IRISA-INRIA, gave an overall presentation of the PAMPA project which aims to provide the methodology for programming parallel distributed architectures. She also gave an overview of the PANDORE II compiler which compiles sequential (C or FORTRAN) programs on distributed memory computers.

In the same way, Dr. Karl Solchenbach, Pallas, described PARMACS, a message passing interface for parallel computers and workstation networks. Among PARMACS features are: synchronous and asynchronous message passing, any to any message support, optimized process to processor mapping or load levelling and support for FORTRAN and C.

Queuing and Scheduling

Prof. Isi Mitrani from the University of Newcastle, gave a talk on load balancing among nodes that are subject to random breakdowns. These breakdowns leave the job queues intact but may affect the routing of jobs during the subsequent repair periods. Several routing strategies were evaluated and compared empirically.

Prof. Andreas Stafylopatis, National Technical University of Athens, formulated an approach for finding near-optimal solutions to parallel task allocation problems. The approach employs neural network techniques and is based on the cooperation of two schemes, an optimization scheme and a constraint satisfaction scheme. Experiments based on simulation indicated that the proposed approach is fast and provides feasible solutions of good quality.

Prof. Yannis Manoussakis, University of Paris XI (Orsay), presented the most important efficient random parallel algorithms for finding maximum matchings in general graphs, and also a fast deterministic parallel algorithm for the perfect matching problem in planar graphs.

Prof. Guenter Haring, Institute of Applied Computer Science and Information Systems, University of Vienna, focused on the scalable workload and system specification (Processor-Resource-Mapping-Specification) and its automatic transformation into a petri net based performance model which is evaluated in a distributed environment.

Load Balancing and Transaction Management

Volker Bohn's contribution "Dynamic workload control in OLTP systems: implementation challenges", SNI, referred to some important problems which are barely addressed by research, in the area of dynamic workload control in OLTP systems and suggested various approaches through which research could address these problems. The conclusion was that the success of dynamic workload control equally relies on good algorithms as well as good embedding into the OS, DBMS, TP-Monitor and the application workload.

The second presentation was concerned with dynamic load balancing in parallel database systems. Prof. Erhard Rahm, University of Leipzig, presented several dynamic strategies for determining the degree of intra-query parallelism and for assigning (sub-) queries and transactions to nodes pertaining to one of the major architectures for parallel database systems, Shared Nothing and Shared Disk

Prof. Erol Gelenbe, University of Paris V, in his talk "Task redistribution to achieve dependable execution" referred to fault-tolerance and reliability in distributed systems and to various techniques that contribute to the dependable execution of applications in distributed systems.

Prof. Christos Nikolaou, University of Crete, discussed recent results on the following area of research for distributed systems: the design, analysis, implementation of and experimentation with adaptive resource management policies that satisfy performance goals set for classes of work submitted to these systems. He reported on some goal oriented resource management policies that have been studied for transaction management, CPU scheduling, memory and buffer management, and discussed open problems and new directions for research.

Before the lunch break, the workshop attendants visited the new building of FORTH and were given a guided tour and short presentations about ongoing research projects in databases, parallel processing, image processing and communications. The next LYDIA workshop is scheduled to take place around October/November 1995.

Please Contact:
Christos Nikolaou - FORTH-ICS
Tel: +30 81 39 16 76
E-mail: nikolau@ics.forth.gr
or karma@ics.forth.gr

return to the contents page