Parallel Processes and Related Automata / Parallele Prozesse und damit zusammenhängende Automaten

Frontmatter

Geometric Parallelism Enforces Parallel Algorithms

Abstract

Geometrie Parallelism Enforces Parallel Algorithms. The connections between parallelisms in Geometry and Complexity are demonstrated in examples of error-correcting codes: For this purpose linear codes, whose duals — the eontrol spaces — are generated by indicence struetures with parallelism, are given by their encoders and decoders. The decoders are parallel processing units according to the parallelism in the incidence structure.

Th. Beth

Vektorprozessoren zur Sonar-Feldverarbeitung

Zusammenfassung

Vektorprozessoren zur Sonar-Feldverarbeitung. Diese Arbeit soll zunächst einen Einblick in einige Aufgaben und Methoden der passiven digitalen Sonar-Feldverarbeitung, wie Beamforming, Spektralanalyse über Frequenz und Winkel, und gewisse Feinauflösungsmethoden geben. Die entsprechenden Berechnungsprobleme werden zusammengestellt und passende Algorithmen angedeutet, wenn mit Vektorprozessoren gerechnet wird. Wir diskutieren einige Vektorprozessoren, die in rechnerkontrollierten Systemen von Forschungslabors zur Sonar-Feldverarbeitung benutzt werden. Unterschieden wird zwischen aufwendigeren Vektorprozessoren, in denen der größte Teil des Gesamtrechenaufwandes bewältigt wird, und kleineren Prozessoren, bei denen die Aufgaben auf mehrere parallel arbeitende Prozessoren verteilt werden. In kurzer Form wird über Software-Hilfsmittel zum Programmieren von Feldverarbeitungsmethoden und über erste Realisierungen von höheren Signalverarbeitungssprachen berichtet.

J. F. Böhme

Parallelstruktur des Simulators GPSS-FORTRAN — Entwurf für ein angepaßtes Multiprozessorsystem

Zusammenfassung

Parallelstruktur des Simulators GPSS-FORTRAN — Entwurf für ein angepaßtes Multiprozessorsystem. Zeitdiskrete Systeme zeichnen sich durch einen hohen Grad an Parallelität aus. Simulationsprogramme, die bei der Modellbildung für zeitdiskrete Systeme eingesetzt werden, erhalten die Parallelität, da bei der Simulation die einzelnen Abläufe des Systems direkt nachgespielt werden.

Um die in Simulationsprogrammen für zeitdiskrete Systeme enthaltene Parallelität auszunutzen, wird eine Rechnerstruktur mit Mikroprozessoren eingesetzt, die* sich dem Aufgabenbereich anpaßt.

Zunächst wird die Parallelstruktur beschrieben, die Simulationsprogrammen zugrunde liegt. Hieraus werden Forderungen abgeleitet, die sich auf die Rechnerarchitektur und das Softwaresystem des Simulators beziehen. Es folgt eine ausführliche Beschreibung des Konstitutionskonzepts für das Rechensystem, das diese Forderungen zu erfüllen vermag.

K. U. Hellmold, B. Schmidt

Einführung in die Methodik der Verkehrstheorie und ihre Anwendung bei Multiprozessor-Rechenanlagen

Zusammenfassung

Einführung in die Methodik der Verkehrstheorie und ihre Anwendung bei Multiprozessor-Rechenanlagen. Untersuchung, Bewertung und Optimierung des dynamischen Ablaufgeschehens ist die Aufgabe der Verkehrstheorie. Die vorliegende Arbeit gibt eine Übersicht über verkehrstheoretische Problemstellungen bei Rechenanlagen und eine Einführung in die Methodik zur Lösung dieser Aufgaben: Systemstudien, Modellierung, Analyse und Synthese.

Neuartige Probleme bei Multiprozessor-Systemen (Synchronisation von Teilabläufen, Übergabezeiten, optimale Aufgabenverteilung, etc.) werden diskutiert und exemplarisch behandelt.

U. Herzog, W. Kleinöder

Hardware Measurements and Their Application on Performance Evaluation in a Processor-Array

Abstract

Hardware Measurements and Their Application on Performance Evaluation in a Processor-Array. The applicability of hardware measurements to different performance measures is discussed. As an example it is shown that software events, e.g. the process-flow, can be evaluated by means of pure hardware measurements if a good machine architecture supports the system’s organization by appropriate hardware.

R. Klar

On the Reachability Problem for Persistent Vector Replacement Systems

Abstract

On the Reachability Problem for Persistent Vector Replacement Systems. The reachability problem for persistent vector replacement systems is shown to be decidable by giving an algorithm for constructing a semilinear representation of the reachability set.

H. Müller

Application of Graph Rewriting to Optimization and Parallelization of Programs

Abstract

Application of Graph Rewriting to Optimization and Parallelization of Programs. Classical automatic optimization is starting with linearized intermediate code and builds up graph-like data struetures (flow graph, DAGs, data flow analysis data). Most of the information which was already known by the upper part of the compiler now has to be detected again. We start with a graph-like intermediate code in which all structural information of the source is still present. Optimization is then carried out by graph manipulations. This is sketched by some examples, namely local common subexpression elimination, motion of loop invariant computations, and induction variable elimination. The usual way in parallelization is also to build up graph-like information (data graph) from flattened code. Here, the parallelization of linear programs and microparallelization within expressions are regarded, starting again with a graph-like intermediate code. There are a lot of further tasks in the context of reliable software generation which can be efficiently performed on high-level intermediate code.

M. Nagl

CAD und Kollaterale

Zusammenfassung

CAD und Kollaterale. Zusammenhänge zwischen Computer Aided Design und Paralleloperationen im Sinn von Bündeln kollateral ablaufender Prozesse werden untersucht. CAD-methodologische Ansätze, die Verknüpfungsmöglichkeiten mit dem Parallelrechnen erkennen lassen, werden danach unterschieden, ob sie Simulation verwenden oder nicht. Behandelt werden die Designtheorien von Goldstein und Miller sowie von Radhakrishna Murty, Radju, Bashmakov. Das bekannte Dreiblockbeispiel wird im Rahmen der Goldstein-Millerschen sowie der Raulefschen Theorie betrachtet. Die Simulatoren von Rieger und Grinberg, ferner von Hendrix werden mit dem Kausalbegriff in Verbindung gebracht. Kollateralität tritt auch im Zusammenhang mit Bearbeitungsautomaten auf. Ein interaktiver Ansatz des Verfassers steht am Schluß der Arbeit.

G. Nees

A Program System of Parallel Processes for Understanding Continuous Speech

Abstract

A Program System of Parallel Processes for Understanding Continuous Speech. A system concept is shown which enables several independent processes, each having specialized knowledge about one aspect of a complex real world pattern, to cooperate in parallel, analyzing and understanding this pattern automatically.

A software environment is introdueed, providing an experimenter with tools to define different system configurations and to develop reasonable control strategies for them.

Intended is a usage for the automatic understanding of continuously spoken german sentences. The principles of the various knowledge modules which will be needed for this pattern analysis task are given also.

H. Niemann, H.-W. Hein

Micro-Modules Implementation of a Learning Pattern-Recognition System

Abstract

Micro-Modules Implementation of a Learning Pattern-Recognition System. A Brazilian/German computer architecture project of a special purpose multi-microprocessor system implemented by using a set of micro-modules is described. The system is organized as a macro-pipeline proposed by Händler [7]. High performance at a low cost, an arbitrary configurability and expandibility, and potential reliability are the main features of such systems. The modules are interconnected by multiport access to the blocks of the distributed main memory. A nine module system for a learning classification process used in pattern recognition, previously simulated and evaluated on three conventional general purpose computers, is presently being built up in Erlangen. The design of the modules consisting of the 16-bit- microprocessor Intel 8086 and specifically designed multiport memories is described, together with the intermodule communication protocol of the system.

H. Rohrer, H. Schreiber, V. Sigmund

Ein Modell für diskrete Systeme mit reellem Zeitparameter

Zusammenfassung

Ein Modell für diskrete Systeme mit reellem Zeitparameter. Die bisher bekanntgewordenen System- und Prozeß-Modelle verfügen ähnlich wie die Petri-Netze nicht über einen reellen Zeitparameter, was in manchen Situationen nachteilig ist. Ausgehend vom Modell des Moore-Automaten wird daher eine Verallgemeinerung erarbeitet, bei der keine Taktung mehr erfolgt, sondern eine reelle Zeitachse zugrunde gelegt wird. Solche direkt aus Moore-Automaten hervorgehenden Elementar-Systeme können zu komplexen Systemen zusammengeschaltet werden. Ein Algorithmus für die genaue Simulation komplexer, rückgekoppelter Systeme wird angegeben. Der Algorithmus kann z. B. dazu benutzt werden, um insbesondere Zeitprobleme in großen Schaltwerken aufzudecken. Einige offene Fragen über das neue Systemmodell werden diskutiert.

A. Schmitt

Algebraic Specification of the Software Controlling a Parcels Distribution Machine

Abstract

Algebraic Specification of the Software Controlling a Parcels Distribution Machine. The algebraic method of software specification has proved its worth in many examples closely related to mathematical problems. In this paper, the method is applied to the development of the software controlling a parcels distribution machine. We show how to derive the axioms from the verbal problem formulation. Our example differs from those often cited in the literature because of the necessity to specify the synchronization between hardware and software.

H. J. Schneider

On Cellular Automata with a Finite Number of State Changes

Abstract

On Cellular Automata with a Finite Number of State Changes. The number of state changes is introduced as a complexity measure for the recognition of languages in cellular automata. The relation of the simplest class — i.e. the one with a constant number of changes per single automaton — to the Chomsky hierarchy is investigated and a comparison with sequential tape complexity is made.

R. Vollmar

Models to Describe Those Features of Cellular Computer Nets Which Are Relevant to the Operating System

Abstract

Models to Describe Those Features of Cellular Computer Nets Which Are Relevant to the Operating System. A cellular computer net seems adequate to execute user problems which have a high computational complexity and which exhibit a high degree of parallelism. The cellular net is seen as a subsystem of a hierarchical modular computer system. A structure-model and a state-model will be presented. The flrst describes the topological features of a cellular net which are static, the second mainly models dynamic faults and the status of allocation. Finally three alternatives for realizing cellular nets are discussed.

K. Wendler

Backmatter