Markus Strasser, Joachim Baumann, Markus Schwehm
A mobile agent based framweork for the transparant distribution and concurrent execution of computations is presented. The framework uses design patterns like the master-slave, abstract factory or the strategy pattern. The architecture of the framework is built on top of a mobile agent system. A performance model allows to identify performance bottlenecks and unbalanced situations within the framework. The Framework has been implemented and tested on top of the mobile agent system MoleIn: H. R. Arabnia (Ed.): `Int. Conf. Parallel and Distributed Processing Techniques and
Applications (PDPTA'99)', CSREA 1999 Volume I, pp. 376-382. Paper (57.530 bytes)
Fritz Hohl, Uwe Kubach, Alexander Leonhardi, Kurt Rothermel and Markus Schwehm
Due to the lack of a generic platform for location- and spatial-aware systems, many basic services have to be reimplemented in each application that uses spatial-awareness. A cooperation among different applications is also difficult to achieve without a common platform. In this paper we present a platform that solves these problems. It provides an infrastructure that is based on computer models of regions of the physical world, which are augmented by virtual objects. We show how virtual objects make the integration of existing information systems and services in spatial-aware systems easier. Furthermore, our platform supports interactions between the computer models and the real world and integrates single models in a global "Augmented World".Bericht 1999/02, Fakultät Informatik, Universität Stuttgart. (accepted for publication at ACM/IEEE Mobicom '99) Paper (257.386 bytes)
Uwe Kubach, Alexander Leonhardi, Kurt Rothermel and Markus Schwehm
New applications in the area of mobile computing make heavy use of knowledge about the application's run-time environment. Applications running on mobile devices in particular exploit knowledge about their current geographical position or query for the location of other interesting objects. To manage such queries some applications provide a location service specifically tailored for their needs. The efficient and application-independent handling of such queries calls for a global and universal location service. Considering a large number of users and queries to be handled, a distributed implementation of a location service is necessary. This paper analyses three schemes for the partitioning of location information and derives a performance model for these partitioning schemes. Finally, an example for the application of the analysis' results is presented for a universal location service within the Nexus system, an infrastructure for location aware mobile computing.Bericht 1999/01, Fakultät Informatik, Universität Stuttgart. (submitted for publication) Paper (166.901 bytes)
K. Rothermel and M. Schwehm
After a classification of agent technologies and a definition of mobile agents this article proceeds with an introduction to basic concepts of mobile agents like agent mobility, agent types and places and agent communication. Then benefits of the usage of mobile agents are summarized and illustrated by selected applications. The next section lists requirements and desirable properties for mobile agent languages and systems. The article continues with an overview of existing mobile agent systems. Finally a selection of open challenges in mobile agent research and a conclusion is given.In: A. Kent and J. G. Williams (Eds.): Encyclopedia for Computer Science and Technology, Volume 40 - Supplement 25, New York: M. Dekker Inc., pp. 155-176. Paper (59.362 bytes)
J. Baumann, F. Hohl, K. Rothermel, M. Schwehm and M. Straßer
Mole is one of the first Java-based mobile agent systems. It runs on an unmodified Java virtual machine on PCs under Windows 95/NT and on workstations under several UNIX dialects. Earlier versions of Mole have provided a basic infrastructure for communication and migration of mobile agents. Version 3.0 of Mole has been strongly revised and several requests and proposals from users of the earlier versions of Mole were integrated into the new release. In particular Mole supports communication between agent groups and the concept of sessions. The infrastructure of Mole includes a resource manager, a directory service and a global naming scheme for agents. In order to support the design of agents, a graphical agent monitor allows to visualize the system behavior as a whole or of a single agent in particular. Mole further provides a thread management unit to overcome some shortcomings of the Java virtual machine. Mole provides a simple means for installation and configuration of the system. This paper describes the architecture and infrastructure of Mole 3.0.In: N. Davies, K. Raymond and J. Seitz, (Eds.): 'Proceedings Middleware 98', Springer Verlag London, pp. 355 - 370. Paper (78.820 bytes)
Klaudia Dussa-Zieger and Markus Schwehm
The scheduling of programs on parallel hardware is investigated in order to minimize the response time of the resulting system. In particular the scheduling problem considered in this paper includes - next to the search for an optimal mapping of the tasks and their sequence of execution - also the search for an optimal configuration of the parallel hardware. An approach for the simultaneous optimization of all three components using genetic algorithms is presented and its performance is evaluated in comparison with an exact reference method based on an branch-and-bound-with-underestimates algorithm. The comparison is based on a large set of problem instances and includes regular task graphs with varying structure and scalable size, which had to be mapped onto a configurable parallel hardware consisting of 4 up to 16 transputers respectively. Small problem instances with less than 8 tasks can be solved by both solution methods. For larger problem instances the reference method fails due to runtime complexity while the genetic algorithm can still find (suboptimal) solutions for problem instances with up to 120 tasks in an acceptable amount of time.Journal on Approximative Reasoning, Special Issue on `Approximative Methods in Scheduling' Vol 19 No. 1, pp. 23-38. Paper (40.252 bytes)
Markus Straßer and Markus Schwehm
A performance model for the interaction of agents in mobile agent systems is presented. Two interaction models, namely the remote procedure call and the agent migration are considered. Performance models for a single interaction are introduced, which are then used to derive a performance model for a sequence of interactions. This performance model can be used to evaluate the performance of any possible behaviour of an agent in a given scenario. The application of the performance model for a typical scenario in mobile computing shows that the optimal behaviour of an agent is achieved by a mixed sequence of remote procedure calls and agent migrations. The performance model is validated by measurements of interactions of real agents in the mobile agent system Mole.In: H. R. Arabnia (Ed.): `Int. Conf Parallel and Distributed Processing Techniques and Applications (PDPTA'97)', CSREA 1997 Volume II, pp. 1132-1140, Paper (59.720 bytes)
Klaudia Dussa-Zieger and Markus Schwehm
Abstract: The scheduling problem considered in this paper includes - next to the search for an optimal mapping of the tasks and their sequence of execution - also the search for an optimal configuration of the parallel hardware. All three components of this optimization problem are highly dependent from each other and should thus not be optimized seperately. An approach for the simultaneous optimization of all three components using genetic algorithms is presented and its performance is evaluated in comparision with an exact reference method based on an branch-and-bound-with-underestimates algorithm. The comparison is based on a large set of problem instances and includes regular task graphs with varying structure and scalable size, which had to be mapped onto a configurable parallel hardware consisting of 4 up to 16 transputers respectively. Small problem instances can be solved by both solution methods. For larger problem instances the reference method fails due to runtime complexity while the genetic algorithm can still find (suboptimal) solutions for problem instances with up to 120 tasks in an acceptable amount of time.In: W. Slany (Ed.): First International Workshop on Approximate Reasoning for Scheduling (ARS'97) in Zürich, Switzerland, 11. February 1997, Paper (33.979 bytes)
Thesis Summary by Markus Schwehm
Global optimization problems belong to the class of NP-hard problems. This means, that the exact solution to such problems is not feasible within acceptable time limits. The same holds for approximative solutions. But many problems that arise in practice are global optimization problems, and the practitioner has to find a solution anyway. In such cases he must rely either on brute force, e.g. by utilization of massively parallel computing power or on probabilistic algorithms or even ad hoc designed heuristics. Unfortunately many of such heuristics are not parallelizable. It is the goal of this thesis, to provide the practitioner with a flexible and parallelizable heuristic. To approach this goal, global optimization methods are reviewed and genetic algorithms are selected as basis for a parallel optimization package. After the introduction of genetic algorithms in terms of a set of operators and a discussion of several parallel population models, the conception for a flexible optimization package is presented. Basic features of the conception are an object oriented layout of the genetic algorithm kernel together with tools for resource management, dynamic configuration and visualization of the internal dynamics of the population. Packages that realize the above conception have been implemented on two very different parallel architectures, namely theMPGA: A Massively Parallel Genetic Algorithm on the array processor MasPar MP-1 with 1024 up to 16384 processing elements
VPGA: A Distributed Parallel Genetic Algorithm on PVM, the Parallel Virtual Machine which consists of a heterogeneous cluster of workstations.
Both packages are first used for experiments concerning the population size and structure, which indicate that the implemented parallel population model also improves the genetic algorithm in the sequential case. The packages are then applied to solve some realistic problems, namely the mapping and scheduling problem, the optimization of Kanban-controlled JIT production lines and the inference of stochastic regular grammars. From the experience gained by the application of the two parallel genetic algorithm packages, it can be concluded that genetic algorithms are at least a good method to start the investigation of a given optimization problem. Moreover the object oriented layout allows to extend the package in order to include other evolutionary algorithms or even general global optimization methods due to the similarity of their structure. In particular, the thesis consists of the following main chapters:
Global Optimization: Global optimization methods are classified due to their potential parallelizability into parallel, generational and sequential methods.
Genetic Algorithms: An introduction to genetic algorithms with respect to their application as global optimization method is given and their modular structure is illuminated.
Parallel Models: Parallel implementations of genetic algorithms are classified due to their underlying parallel population model into global, regional and local models.
Parallel Implementation: The conception of a flexible massively parallel genetic algorithm package is proposed and two implementations of this package are described.
Experimental Results: Some experiments investigate the influence of population size, neighbourhood topology and mating selection on the performance of genetic algorithms.
Applications: The application of the packages to the mapping and scheduling problem, the optimization of a Kanban-controlled JIT production line and the inference of stochastic regular grammars is described.
Dissertation, Universität Erlangen-Nürnberg, Arbeitsberichte des IMMD Band 30 Nummer 1 (1997) Kurzfassung (60.170 bytes)
Markus Schwehm and Alexander Ost
A genetic approach to the inference of stochastic regular grammars from a given finite set of sample words is presented. The goal of the inference problem is not only to find a grammar that covers the given finite sample, but possibly also the infinite language from which the sample was taken (generalization). We propose two different bitstring representation methods for stochastic regular grammars and have a closer look at the objective function. Due to the large complexity of the problem, a massively parallel implementation of genetic algorithms was used. The algorithm was applied to a workload-modeling problem. The results are compared with reference methods like the successor-, k-tail- and k-TLSS-method.In: L. J. Eshelman (Ed.): `Genetic Algorithms: Proceedings of the sixth Int. Conf. (ICGA95)', Morgan Kaufmann Publishers 1995, pp. 520-527, Paper (56.857 bytes)
Markus Ettl and Markus Schwehm
One way to reduce costs in high volume production lines is to smooth and balance the material flow by means of controlled inventories. Kanban systems are now being implemented worldwide due to their ability of reducing inventories and production lead times. This paper addresses two fundamental design issues in kanban systems and presents an efficient heuristic method for designing such systems. An analytical method for modelling kanban systems and a general-purpose genetic algorithm are integrated in a heuristic desigh methodology which evaluates the performance of kanban systems using alternative network partitions and allocations of kanbans. As we demonstrate, the heuristic method provides a useful procedure to evaluate the impact of design alternatives and can thus serve as a rough-cut decision support tool which assists managers in the planning of large-scale manufacturing systems.In: J. Biethahn and V. Nissen, `Evolutionary Algorithms in Management Applications', Springer Verlag 1995, pp.139-152, Paper (167.233 bytes)
M. Schwehm
Dieser Beitrag ist ein Erfahrungsbericht über die Anwendung genetischer Algorithmen auf ein realitätsnahes Problem aus dem Bereich der Just-in-Time-Fertigung. Ein vorhandenes Softwarepaket für genetische Algorithmen (VPGA) wurde mit Analysemethoden für sektorisierte Kanbansysteme zu einer kombinierten Methode für den Entwurf und die Optimierung solcher Systeme zusammengebunden.In: J. Kuhl and V. Nissen, 'Evolutionäre Algorithmen in Management-Anwendungen', 1995, pp. 11-20
Markus Schwehm, Thilo Opaterny und Karlheinz Kirsch
Genetische Algorithmen imitieren den Evolutionsprozeß der Natur, um eine möglichst gute Lösung für ein Optimierungsproblem zu finden. In diesem Beitrag wird eine parallele Implementation dieses heuristischen Verfahrens vorgestellt und auf die Plazierung von Makrozellen angewendet. Der Algorithmus erweist sich als sehr gut parallelisierbar, sowohl für Workstation-Cluster, Multiprozessoren und Feldrechner. Darüberhinaus kann der Algorithmus leicht an unterschiedliche Optimierungsziele (Fläche, Netzlänge) angepaßt werden. Ein Vergleich mit Simulated Annealing zeigt, daß der genetische Algorithmus genauso gute Plazierungen schneller liefert und mit geringerer Wahrscheinlichkeit in einem lokalen Optimum hängen bleibt.In: PARS-Workshop in Potsdam, PARS-Mitteilungen Nr. 13, November 1994, pp. 69-74
Markus Ettl and Markus Schwehm
One way to reduce costs in high volume production lines is to smooth and balance the material flow by means of controlled inventories. Kanban systems are now being implemented worldwide due to their ability of reducing inventories and production lead times. This paper addresses two fundamental design issues in kanban systems and presents an efficient heuristic method for designing such systems. An analytical technique for modelling kanban systems and a general-purpose genetic algorithm are integrated in a heuristic design methodology which evaluates the performance of kanban systems using alternative network partitions and allocations of kanbans. As we demonstrate, the heuristic method provides a useful procedure to evaluate the impact of design alternatives and can thus serve as a rough-cut decision support tool which assists managers in the planning of large-scale manufacturing systems.In: Tenth Int. Conf. System Engineering ICSE`94 in Coventry, UK, Coventry University Press 1994, pp. 307-314, Paper (42.169 bytes)
Markus Schwehm and Thomas Walter
A massively parallel genetic algorithm for the mapping and scheduling problem is presented. It turns out that a standard genetic algorithm package can easily be adapted to the mapping and scheduling problem. The resulting algorithm is able to exploit parallelism of a massively parallel hardware and can solve larger problems than a reference algorithm. Moreover the algorithm is well suited if the algorithm has to be restarted with a slightly modified problem input. The algorithm is implemented on the array processor MasPar MP-1.In: Buchberger, B. and Volkert, J. (Eds.): `Parallel Processing: CONPAR 94 - VAPP VI' Third Joint Int. Conf. Vector and Parallel Processing in Linz, Austria, September 1994, Springer Verlag 1994, LNCS 854, pp. 832-841, Paper (50.555 bytes)
M. Schwehm
The genetic algorithm is an iterative random search technique for nonlinear or combinatorial problems. In this contribution, first the development from the classical genetic algorithm (GA) via the parallel genetic algorithm (PGA) to the massively parallel genetic algorithm (MPGA) is described. Then experimental results with an implementation of the MPGA on the array processor MasPar MP-1 are displayed, which exemplify robustness and adaptive behavior of the algorithm. The observed properties of the MPGA are finally combined for an improved method of mapping load onto a massively parallel hardware.In: Dekker, L. (Ed.): `Massively Parallel Processing - Applications and Development', Proc. Int. Conf. MPP `94 in Delft, The Netherlands, Elsevier Science Publ.1994, pp.505-512, Paper (51.296 bytes)
M. Schwehm, K.D. Reinartz, T. Walter, S.S. Gold, C. Schäftner, T. Opaterny, A. Ost und N. Engst
Interner Bericht IMMD VII - 8/93, Universität Erlangen-Nürnberg 1993, Paper (318.003 bytes)
Markus Schwehm
This contribution describes the implementation of a fine-grained parallel genetic algorithm `MPGA' on the MasPar MP-1, a massively parallel mesh connected array processor with global router and 1024 (up to 16384) 4-bit processing elements. The implementation uses object oriented methods to provide a large set of standard strategies which can be adapted for a given application. Report modules support the investigation of the performance of the GA. The Implementation shows a good performance compared to other implementations on parallel hardware.In: Albrecht R.F. et al (Eds.): `Artificial Neural Nets and Genetic Algorithms' Proc. Int. Conf. ANNGA `93 in Innsbruck, Austria, Springer-Verlag Wien 1993, pp.502-507, Paper (59.575 bytes)
Markus Schwehm
In diesem Beitrag wird zunächst die Entwicklung vom klassischen genetischen Algorithmus (GA) über den parallelen genetischen Algorithmus (PGA) zum massiv parallelen genetischen Algorithmus (MPGA) nachgezeichnet. Eine Implementation des Programmsystems `MPGA' auf dem feinkörnigen Parallelrechner MasPar MP-1 mit 1024 Prozessor-Elementen wird beschrieben, und seine Leistungsfähigkeit anhand zweier Anwendungen demonstriert.In: PARS-Workshop in Dresden `Feinkörnige und massive Parallelität', PARS-Mitteilungen Nr. 12, Juli 1993, pp.181-191, Paper (92.312 bytes)
Markus Schwehm
This contribution describes the implementation of a fine-grained parallel genetic algorithm on the MasPar MP-1, a massively parallel mesh connected array processor with global router and 1024 (up to 16384) 4-bit processing elements. In this paper the impact of changing the topology of the environment of the individuals on the performance of a genetic algorithm is investigated. The interconnection networks are emulated using the global router of the MP-1.In: Valero M. et al (Eds.): `Parallel Computing and Transputer Applications I' Proc. Int. Conf. PACTA `92 in Barcelona, Spain IOS Press/CIMNE, Barcelona 1992, pp.195-203, Paper (55.163 bytes)
Michael Schäfer, Michael M. Gutzmann and Markus Schwehm
An algorithm for the numerical simulation of the fluid flow in a crystal growth process is presented. The algorithm is implemented on three parallel architectures. The performance analysis shows that special care has to be taken for the efficient realization of communication patterns on massively parallel systems.In: Bouge, L. et al (Eds.): `Parallel Processing: CONPAR 92 - VAPP V', Proc. Int. Conf. CONPAR/VAPP in Lyon, France, 1992 Springer-Verlag 1992, LNCS 634, pp.229-240
Markus Schwehm
Zuerst erfolgt eine kurze Beschreibung des Feldrechners `Data Transport Computer' (DTC) der Firma Wavetracer. Dann wird ein Überblick über die ANSI C - Erweiterung `multiC' für den DTC gegeben. Erfahrungen mit dieser Sprache während einer dreiwöchigen Probeinstallation des DTC an der Universität Erlangen werden vorgestellt. multiC wurde im Hinblick auf Algorithmen der Strömungsmechanik entwickelt und ermöglicht problem- und rechnergrößenunabhängige Programmierung. Der gewählte Ansatz zur maschinenunabhängigen Programmierung führt allerdings bei komplizierteren Algorithmen (z.B. Mehrgitterverfahren) zu ineffizienten Programmen.In: PARS-Workshop Dagstuhl `Parallelrechner und Programmiersprachen', PARS-Mitteilungen Nr. 10, Juli 1992, pp.5-11
Markus Schwehm and Alfred Strey
A comparision of some static interconnection networks with different topologies for the use in large SIMD parallel computers is presented. The criterion of the comparision is the efficient realization of communication patterns often used in algorithms that are based on large one- or multidimensional arrays with regular communication structure.In: Mirenkov, N. N. (Ed.): `Parallel Computing Technologies' Proc. Int. Conf. PaCT-91 in Novosibirsk, USSR, World Scientific, Singapore 1991, pp.223-234