Skip to main content
main-content

Über dieses Buch

Die Beiträge des 5.Transputer-Anwender-Treffens TAT `93 stammen aus Industrie, Forschung, Entwicklung und Lehre und geben detailliert Auskunft über die neuen Möglichkeiten von Transputeranwendungen und Leistungssteigerungen, die mit dieser Parallelrechnertechnologie zu erzielen sind. Die Themengebiete dieses Bandes sind Algorithmen, Neuronale Netze sowie Bild- und Echtzeitverarbeitung. Hierbei wird deutlich, daß es selbst mit relativ kleinen Transputersystemen möglich ist, Aufgaben zu lösen, die früher Großrechenanlagen vorbehalten waren. So bietet dieses Buch dem Einsteiger einen Überblick über Probleme, die erfolgreich mit dem Transputer bearbeitet werden können und dem Experten eine Fülle von Anregungen und Lösungsvor- schlägen am Beispiel erfolgreicher Transputer-Anwendungen.

Inhaltsverzeichnis

Frontmatter

Einführung

Parallelverarbeitung und Politik

Zusammenfassung
Was hat ein politischer und bewußt polemischer Beitrag auf einer wissenschaftlichen Veranstaltung zu suchen?
Parallelverarbeitung ist nicht mehr nur das Arbeitsgebiet einer kleinen und verschworenen Gemeinschaft von Wissenschaftlern und einigen Industriepionieren, sondern steht kurz vor der breiten Einfuhrung in sehr unterschiedliche Industriezweige. Dies allein bedeutet ein potentielles Marktvolumen von mehreren Milliarden US-$. Noch wichtiger ist die Position der Parallelverarbeitung als Glied in unseren Technologieketten.
Andreas vom Hemdt

Algorithmen

Ein Konzept zur applikationsunabhängigen, dynamischen Lastverteilung in verteilten Systemen

Zusammenfassung
In dieser Arbeit wird ein System zur Implementierung weitgehend applikationsunabhängiger, dynamischer Lastverteilungsverfahren in verteilten Systemen vorgestellt. Wesentliche Ziele sind die einfache und portable Entwicklung paralleler Programme und die Möglichkeit, verschiedene Ansätze und Varianten für Lastverteilungs-Algorithmen implementieren und testen zu können.
Zunächst wird eine Notation eingeführt, mit der grundlegende Eigenschaften von Parallelität und parallele Programme eindeutig formal beschrieben werden können. Anschließend wird ein Überblick über grund-sätzliche Aspekte von Lastverteilung gegeben. Schließlich werden, ausgehend von den semantischen Grundelementen paralleler Programme, die Komponenten des Systems vorgestellt: Infrastruktur für die transparente Abwicklung technischer Vorgänge, Schnittstelle zu Applikationen, Schnittstelle zu Lastverteilungs-Modulen und austauschbare Lastverteilungs-Module. Zur Überwindung von unterschiedlichem Informationsbedarf verschiedener Lastverteilungsverfahren werden flexible Deskriptoren und ein Klassenkonzept vorgeschlagen.
Markus Naaf

Ein Objektverwaltungssystem für die Programmiersprache Gina unter dem Betriebssystem Helios

Zusammenfassung
Gina ist eine objektorientierte, Petrinetz-basierte Programmiersprache, deren Konzept in [Son92] vorgestellt wurde. Die Erstellung eines Gina-Prototyps wurde im Rahmen eines Projektes am Lehrstuhl für Informatik I der RWTH Aachen durchgeführt. Das Projekt umfaßte die Komponenten Compiler, Laufzeitsystem und Objektspeicher. Die Implementierung wurde auf einem Transputercluster unter dem Betriebssystem Helios vorgenommen. In diesem Beitrag werden die Prinzipien des zum Laufzeitsystem gehörigen Objektverwaltungssystems vorgestellt (vgl. [Püt92]).
Petra Krüger, Michael Sonnenschein

Anpassungsfähige Datenstrukturen und blockorientierte Algorithmen der linearen Algebra für Distributed Memory Systeme

Abstract
Die Verwendung einer blockzyklischen Datenverteilung, geeigneter Konfigurationen und Topologien sowie einer blockorientierten Programmierung werden am Beispiel des Distributed Rank-r LU Update Algorithmus als Message Passing Implementation für Transputersysteme vorgestellt.
G. Hebermehl

Zur maschinennahen Implementation und Performance von Basic Linear Algebra Subroutines (BLAS) Level 1, 2 und 3 auf dem Transputer T9000

Abstract
An ausgewählten Moduln wird der Einfluß der Speicherhierarchie des T9000 auf die Implementierungsstrategie für die BLAS untersucht. Die Notwendigkeit und die Art des Unrolling von DO-Schleifen wird dargestellt und an einem Performance-Simulator für den T9000 überprüft. Ein für eine maschinennahe Implementierung geeigneter Algorithmus für die blockweise Matrix-Matrix-Multiplikation wird formuliert und in FORTRAN auf einer SPARCstation 10/30 getestet.
Gerd Reinhardt

Verbesserte Planung und Optimierung mit Hilfe eines erweiterten Genetischen Algorithm

Zusammenfassung
In Produktion und Fertigung gibt es eine Vielzahl von Aufgabenstellungen, für die eine Optimierung unter wirtschaftlichen Gesichtspunkten notwendig oder zumindest wünschenswert ist. Andererseits sind die Randbedingungen und Anforderungen an den Einsatz von Werkzeugen zur Planung und Optimierung gerade in der industriellen Praxis sehr hoch, sodaß vor allem neue, kombinierte Techniken einen erfolgversprechenden Ansatz darstellen. Das hier vorgestellte Verfahren gelangt durch die Verbindung von Simulation, Genetischen Algorithmen und Parallelverarbeitung zu einer neuen Qualität. Zwei Anwendungsbeispiele aus dem Gebiet der Resourcenplanung demonstrieren die Tauglichkeit der neuen Methode: In einem industriellen Anwendungsfall konnten Spareffekte von über 40% im Vergleich zur state-of-the-art-Planung erreicht werden.
Christian Blume, Wilfried Jakob

Das parimod-System

(Parallele Computergraphik und Animation mit Transputern)
Abstract
Das parimod-System, welches als Abkürzung für “The Parallel Computer graphics and interactive solid modeling system” steht, verbindet in bisher einzigartiger Weise die Gebiete der parallelen Algorithmen bzw. Multiprozessor-Systeme und der Computergraphik miteinander. Es besteht aus einzelnen Modulen, die seit 1991 an der Universität Osnabrück entwickelt wurden. Intention dieser Entwicklung war es, die Flexibilität und die universelle Ersetzbarkeit von Transputer-Systemen anhand verschiedener Anwendungen aus der Computergraphik zu verdeutlichen. Entstanden ist dabei ein transputerbasiertes graphisches System zur schnellen und interaktiven Erstellung, Berechnung und Anzeige bzw. Animation von dreidimensionalen Szenen.
K. Zeppenfeld, C. Landwehr, F. Thiesing, O. Vornberger

3D-Visualisierung von Struktur- und Kommunikationsaspekten in CSP-basierten Systemen

Überblick
Im folgenden wird ein neues Verfahren zur Präsentation und Evaluierung von Struktur- und Kommunikationsaspekten in CSP-basierten Systemen vorgestellt. Dieses Verfahren zeichnet sich dadurch aus, daß hier durch gezielten Einsatz von 3D-Visualisierungs- und Interaktionstechniken der Entwickler paralleler Software beim Design und der Beurteilung seines CSP-basierten Systems optimal unterstützt wird. Durch eine einheitliche Darstellung der unterschiedlichen Aspekte und Abstraktionsebenen behält der Benutzer die Übersicht über das komplexe Gesamtsystem und gewinnt innerhalb kurzer Zeit mehr Informationen über einzelne Systemkomponenten.
Brigitta Lange, Frank Steinfath

Parallelisierung eines Programms zur Simulation von Gießvorgängen

Abstract
Vorgestellt wird eine Machbarkeitsstudie zur Parallelisierung eines kommerziellen Algorithmus zur Simulation von Aluminium-Gießvorgängen. Ausgangspunkt des Algorithmus sind die Navier-Stokes-Differentialgleichungen für turbulente Flüssigkeitsströmungen, die numerisch durch SOLA-VOF-Algorithmen gelöst werden. Dabei werden sowohl das Finite-Differenzen-Verfahren als auch die Control-Volume-Methode angewendet. Der zentrale Punkt für den effizienten Einsatz eines massiv parallelen Systems ist die optimale Aufteilung der Probleminstanzen in den verschiedenen Phasen des Algorithmus. Im Mittelpunkt steht die Parallelisierung des Jacobi-Verfahrens, mit dem der explizite Solver die Gleichungssysteme löst. Für diesen werden Ergebnisse von Laufzeitmessungen für eine unter PARIX mit FORTRAN 77 implementierte Parallelisierung auf den Parsytec Transputersystemen x’plorer und GC präsentiert.
Frank M. Thiesing, Mark Lipinski

Farming als Methode zur Parallelisierung komplexer Algorithmen auf Transputer- und Workstation-Cluster

Zusammenfassung
Die Extrahierung der wesentlichen Informationen aus einem Grauwertbild mit Hilfe eines Neuronalen Netzes ist ein Beispiel aus der Klasse der komplexen Algorithmen [5]. Dieser Algorithmus besteht im wesentlichen aus Matrizen- und Vektor Operationen, deren sequentielle Abarbeitung sehr zeitaufwendig, die Parallelisierung jedoch recht einfach möglich ist.
Als Implementierungsmethode wurde das Farmer-Prinzip ausgewählt. Dieses Modell ist aufgrund seiner Allgemeinheit eine Lösung für eine große Klasse von Problemen und erlaubt zudem eine gute Skalierbarkeit des Prozessornetzwerkes.
Neben der Implementierung dieses Algorithmus auf einem Transputer-Cluster wurden für einen Vergleich die selben Berechnungen auf Workstation-Clustern mit dem Softwarepaket PVM durchgeführt.
Mit Hüfe dieser Bildverarbeitungsaufgabe sollten die genannten Eigenschaften der Farm-Implementierung in der Praxis überprüft sowie Angaben zum Grad der Parallelisierbarkeit und zur Skalierbarkeit der Farm auf verschiedenen Topologien ermittelt werden. Theoretische Modelle zur Kommunikations- und Berechnungszeit wurden in ihrer praktischen Umsetzung überprüft.
Carsten Grzemba, Karsten Henke

Neuronale Netze

Knowledge Extraction from Artificial Neural Networks and Applications

Abstract
Knowledge acquisition is a frequent bottleneck in artificial intelligence applications. Neural learning may offer a new perspective in this field. Using Self-Organising Neural Networks, as the Kohonen model, the inherent structures in high-dimensional input spaces are projected on a low dimensional space. The exploration of structures resp. classes is then possible applying the U-Matrix method for the visualisation of data. Since Neural Networks are not able to explain the obtained results, a machine learning algorithm sig* was developed to extract symbolic knowledge in form of rules out of subsymbolic data. Combining both approaches in hybrid system results in a powerful method to solve classification and diagnosis problems. Several applications have been used to test this method. Applications on processes with dynamic characteristics, such as chemical processes and avalanche forecasting show that an extension of this method from static to dynamic data is feasible.
A. Ultsch, G. Guimaraes, D. Korus, H. Li

Ein Paralleler Wachstumsalgorithmus für Neuronale Netze

Zusammenfassung
In dieser Arbeit werden Varianten eines parallelisierten Algorithmus zum Wachstum und Belehren künstlicher neuronaler Netze, des “Cascade-Correlation Learning Architecture” — Algorithmus von [3], vorgestellt und dessen Realisierbarkeit diskutiert. Dabei werden die in [3] gemachten Vorschläge analysiert und revidiert.
Iván Santibáñez-Koref, H.-M. Voigt, Joachim Born

Simulation eines neuronalen Raumrepräsentations-netzwerkes auf einem Transputernetz

Zusammenfassung
Positionen und Formen von Objekten werden in “Aktivitätswolken” in einem neuronalen Netz repräsentiert. Bei der Bewegung in einem körperfesten Koordinatensystem bewegt sich die “Wolke” entgegengesetzt zur Körperbewegung. Dies geschieht allein durch Erzeugen und Löschen von Aktivitäten, wobei die Repräsentation der Objekte stabil bleibt und keine arithmetischen Operationen benötigt werden. Es wurde eine Simulation geschaffen, mit der zweidimensionale translatorische und rotatorische Bewegungen auf einem sequentiellen Rechner simuliert werden können, um den zweidimensionalen Raum um einen Roboter zu erkunden. Für die Simulation des dreidimensionalen Greifraumes des Roboters wurde das neuronale Netz auf einem Parallelrechner implementiert, um die nötige Rechenleistung zu erhalten.
M. Busemann, G. Hartmann, S. Drüe

Bildverabeitung

Bildverarbeitungssystem mit hochauflösendem modularen Frame-Grabber für Zeilen- und Flächenkameras

Zusammenfassung
Bei der Bestimmung der Diffusionskoeffizienten von Salzschmelzen finden die Savart-Interferometrie und die holographische Interferometrie als optische Meßmethoden Anwendung. Beide Methoden erfordern eine exakte Vermessung sowie die zeitliche Verfolgung von Grauwertmustern in Interferogrammen. Bei der Auswertung mit Kleinbildfilm und Mikroskop können nur wenige Versuche pro Tag ausgewertet werden. Eine elektronische Bilderfassung, Verarbeitung und Ausweitung bietet sich daher an. Wünschenswert ist auch eine hohe Verarbeitungsgeschwindigkeit, so daß erste Ergebnisse noch während der Durchführung des Experiments vorliegen. Etwaige Korrekturen während des Versuchs werden dadurch möglich. Ein typisches taterferogramm zeigt Abbildung 1.
M. Gollbach, J. Richter

Transputer-Framegrabber zur Steuerung autonomer mobiler Roboter

Zusammenfassung
Es wird gezeigt, daß unter günstigen Bedingungen für die sichtbasierte autonome Führung eines mobilen Roboters ein einziger Transputer-Frame-grabber (TFG Ultra) ausreichend ist. Sowohl die Bildverarbeitung als auch der Fahrzeugregler werden effizient vom Transputer des TFG abgearbeitet. Das System und die Entwicklung der Simulationsumgebung, sowie die Anwendung am Versuchsfahrzeug (ATHENE) werden beschrieben.
Lampros Tsinas, Bernhard Blöchl

Parallele Entfernungsbildsegmentierung auf Transputern durch Teilen und Verschmelzen

Zusammenfassung
Die automatische Gruppierung vieler 3D Meßpunkte in wenige, große Flächen, genannt Segmentierung, ist ein Schlüsselverfahren der Entfernungsbildverarbeitung und bildet oft einen Engpaß sowohl in Bezug auf die Qualität der Ergebnisse als auch den Rechenaufwand.
Dieser Beitrag beschreibt ein split-and-merge-Verfahren mit neuen Teilungs- und Verschmelzungskriterien und -algorithmen. Insbesondere werden Gütekriterien für Flächen und für Unterteilungen eingeführt. Ergebnisse an simulierten und realen Entfernungsbildern werden präsentiert.
Der zweite Teil diskutiert Parallelisierungsstrategien und Leistungsmessungen auf Transputerfarmen. Das hierarchisch-rekursive Verfahren bietet viel Parallelisierungspotential. Die globale und dynamische Bestimmung des Teilungspunktes und die ungleiche Auslastung durch Teilaufträge erfordern aber eine sehr flexible Verteilung, um dieses Potential auch auszuschöpfen.
Peter Kohlhepp

Parallelverarbeitende dreidimensionale Oberflächenrekonstruktion

Zusammenfassung
Das Problem der dreidimensionalen Oberflächenrekonstruktion wird behandelt. Zunächst wird das Problem formuliert und ein Lösungsansatz mittels eines Variationsproblems wird angegeben. Anschließend werden iterative Lösungsverfahren linearer Gleichungssysteme auf Parallelrechnern beschrieben, da sie zur numerischen Lösung erforderlich sind. Die Ergebnisse eines Fallbeispieles werden dann vorgestellt. Dazu wird ein äquivalentes Energiemodell der Aufgabenstellung aufgebaut, das dazugehörige kontinuierliche Variationsproblem wird aufgestellt und anschließend wird es mit Hilfe der Finite-Elemente-Methode diskretisiert. Eine Lösung des enstandenen linearen Gleichungssystems wird mit Hilfe einer Parallelimplementierung des relaxierten Gauß-Seidel-Verfahrens (SOR) bestimmt.
V. A. David Sánchez

Fertigungsintegrierte On-line Bildverarbeitung

Zusammenfassung
Bis zu 80 000 Flaschen laufen pro Stunde über das Förderband einer modernen Abfüllanlage. Plötzlich wird eine Flasche von einem Greifer herausgestoßen. Das vollautomatische Bildverarbeitungssystem hatte erkannt, daß diese mit dem falschen Kronkorken verschlossen wurde.
Peter W. Plapper

Echtzeitverarbeitung

Einsatz paralleler Sensordatenverarbeitung und einer Fuzzy Entscheidungsunterstützung in einem Echtzeit-Sensorsystem zur industriellen Prozeßsteuerung

Zusammenfassung
Zur Steigerung von Produktivität, Qualität und Flexibilität werden in der industriellen Produktion in zunehmendem Maße automatisierte Fertigungszellen eingesetzt. Bedingt durch unvermeidliche Fertigungs- und Positioniertoleranzen von zugeführten Teilen wird insbesondere zur Erfüllung der Kriterien Qualität und Flexibilität ein hohes Maß an sensorischer “Intelligenz” am ausführenden Robotersystem benötigt.
P. Drews, W. G. Trier

Offene Experimentalsteuerung für Werkzeug-maschinen auf Transputerbasis

Zusammenfassung
CNC-Steuerungen für komplexe Werkzeugmaschinen müssen heute flexibel an die unterschiedlichen Bearbeitungsaufgaben anpaßbar sein. Aus der Fertigungstechnik ergeben sich wegen erhöhter Forderungen an Bearbeitungsgeschwindigkeit und Konturgenauigkeit komplexe Anforderungen an die CNC-Steuerung. Marktgängige Steuerungen bieten nur wenige und oft ungeeignete Schnittstellen, um problemorientierte Lösungen implementieren und erproben zu können.
Roberto Feitscher, Peter Sworowski

Parallel-FUCS Einsatzsystem zur online- und realtime-Fuzzyklassifikation

Zusammenfassung
In der heutigen Zeit, die durch eine zunehmende Automatisierung der Produktion gekennzeichnet ist, kommt der automatischen Überwachung technischer Prozesse immer größere Bedeutung zu.
Immer wesentlicher wird dabei das schnelle Reagieren der Überwachungs- und Regeleinrichtungen auf Störungen in komplexen Systemen mit geringen Zeitkonstanten. Nur so kann eine wirksame Regelung und/oder Schadensminimierung erfolgen.
Holger Franke

A Transputer Based Data Acquisition System for the Baikal Neutrino Telescope

Abstract
This paper describes a reliable and extendable setup based on a transputer network and its application for data preprocessing and online monitoring of an underwater muon and neutrino detector. It is operated since April 1993 by a Russian-German group in Lake Baikal, Siberia. The net hardware was designed for medium scale experiments like the Baikal detector. It allows to set up extended transputer nets and to configure them dynamically at run time and has proved to be suitable for experiments carried out under rough environmental conditions, where the possibilities of system maintenance are limited but nevertheless computational power is needed. A small net consisting of five transputers is used as a basic component of the data acquisition system of the underwater detector currently operating.
H. Heukenkamp, S. Klimushin, H. Leich, U. Schwendicke, P. Wegner, R. Wischnewski

Backmatter

Weitere Informationen